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.
We investigate message-passing graph neural networks with random node features. Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically. Here, we establish a novel universality result focusing on permutation-equivariant neural networks (PENNs), a class of GNNs built from feedforward neural network components that subsumes many prominent GNN architectures. We show that PENNs, combined with partially random node features, can approximate arbitrarily well in probability any measurable permutation-invariant or permutation-equivariant function on directed graphs of fixed size with multidimensional node and edge features. For k-times continuously differentiable functions, k≥2, we also derive upper bounds on the approximation rates, relating the complexity of the feedforward components of a PENN in terms of layer depth and number of nonzero weights to the desired approximation accuracy.
Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber
School of Computer Science University of St. Gallen St. Gallen, 9000, Switzerland · Department of Mathematics LMU Munich Munich, 80333, Germany
We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2 iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.
Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.
Chendi Qian, Christopher Morris, Stefanie Jegelka +1
RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1