Continuous random node features increase the expressivity of message-passing neural networks (MPNNs), but existing theoretical analyses are not fine-grained enough to capture their limitations, particularly in approximating functions across graph sizes or under a fixed number of random bits. We develop a population-level framework for size-uniform approximation. For MPNNs with a graph-size-independent Lipschitz bound in their initial features, including standard mean, max, and order-normalized sum architectures, we show that continuous random features can be quantized to finitely many colors with arbitrarily small uniform error in expected output. This reduction lets us transfer limitations on finite-color distinguishability to limitations on size-uniform approximation with continuous random features. We use this framework to prove that these MPNNs are not size-uniformly universal, analyze the expressivity gains from colors and independent trials, and establish incomparability between random-color MPNNs and higher-order Weisfeiler-Leman methods. We also give finite-color MPNN constructions for tree subgraph isomorphism via color coding and a local MST task.
Figures & tables
Figure 1: Overview of our random-feature MPNN framework. Size-uniform quantization with a finite palette S⊂K . Here (QSx)v=qS(xv) , δ(S)=supz∈K∥z−qS(z)∥ , and FS(G)=E[F(G,QSξG)] . Both branches use the same MPNN and coupled initializations.
Figure 2: Balanced test accuracy 1−21(FNR+FPR) for detecting bridges of smaller-side size b . Error bars show SE over five training seeds.
Figure 3: Rooted tree detection with different numbers of colors and trials. Cells show mean node test accuracy (%) ± SE across five training seeds.
Setting
Continuous
2 colors/coordinate
EXP: graph accuracy (%)
1 coordinate
98.68±0.17
98.62±0.19
64 coordinates
97.90±0.39
97.83±0.48
TRIANGLE: node ROC-AUC (%), n=100
1 coordinate
93.98±0.05
93.35±0.05
Table 1: Inference-time performance under quantization. Mean ± SE across ten folds for EXP, and ten single-trial feature draws of one trained model for TRIANGLE.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: The parity/CFI gadget.
Figure 5: The CFI graph pair with four input pairs ( k=4 ). The intermediate pairs (z10,z11) and (z20,z21) are each shared by a child gadget and the root gadget. Shading indicates vertex roles, not random colors. The diameter-two variants are obtained by adding one virtual node adjacent to every vertex shown in each graph.
Table 3: Exact-side bridge detection: balanced test error (%), mean ± SE across five training seeds.
b
Colors
Side b−1 FPR
Side b+1 FPR
Precision
4
2
54.08
38.79
42.29
4
4
27.96
10.87
61.67
4
16
0.97
4.65
90.60
4
32
0.39
1.79
93.18
5
2
87.38
93.02
11.91
5
4
67.23
68.02
29.65
Appendix
Table 4: Neighboring-side false-positive rates and overall precision (%) at n=512 , averaged over five training seeds. Bridges of sizes b−1 and b+1 are negatives for target b ; precision is the fraction of predicted positives with the correct label.
q
s
Seed 0
Seed 1
Seed 2
Seed 3
Seed 4
2
1
46.45
46.52
46.44
46.52
46.52
2
16
38.17
39.46
41.93
41.02
42.89
2
64
36.00
36.77
37.01
36.94
36.19
8
1
36.86
37.64
37.10
37.89
37.44
8
16
10.71
14.26
11.60
12.11
11.02
8
64
2.96
25.66
1.30
2.31
15.18
Appendix
Table 5: Tree detection test error (%) for each training seed, with q colors and s trials. All models use the same 16,000 labeled roots on 1,000 unseen graphs.
Figure 7: TRIANGLE inference-time quantization of one frozen rGIN trained with continuous features on 20-vertex cubic graphs. Test sets contain 1,000 graphs at each size. Points and error bars show mean ROC-AUC ± SE across ten paired single-trial feature draws; squares and dashed lines mark the continuous baseline. The axis break omits 51–86% ROC-AUC. These error bars do not measure training-seed variability.
Graph neural network expressivity studies which graph structures and functions a model can distinguish or represent, and how its design shapes those limits.