Message-passing graph neural networks (MPGNNs) are commonly compared with the Weisfeiler-Lehman (WL) test, but this comparison does not quantify the resource parameters a network needs to implement a step of the WL test with bounded-size messages and finite numerical precision. We study the cost of simulating a single step of the WL test on unattributed graphs. We distinguish input-independent, or oblivious, simulation from instance-dependent simulation. In the former, the parameters, or their distributions in randomized models, are fixed before the input instance is known. Our results show that the local update rule of the WL test hides a global relabeling problem. In the oblivious setting, deterministic and zero-error randomized MPGNNs cannot solve this problem in the worst case using only shallow networks with small messages. We complement this lower bound with a nearly matching construction in a stronger rooted, port-aware model. By contrast, when the color set is large, bounded-error randomness can greatly reduce the cost, and a one-layer MPGNN with messages of logarithmic size and a logarithmic number of random bits suffices. We show that this logarithmic number of random bits is essentially necessary for shallow, small-message simulations. When the color set is small, we still obtain a rooted, port-aware simulation, but this construction requires more layers or larger messages. We also prove that this extra cost is partly unavoidable, as small color sets force a nontrivial trade-off between the number of layers and the message size. Finally, instance-dependent simulation can be much shallower, but the required instance-specific parameters are not necessarily easy to find. Together, these results reveal quantitative structure hidden behind the statement that MPGNNs match the WL test.
Table 1: Summary of results. Here n and m denote the numbers of nodes and edges, respectively; D denotes the diameter; d , w , and p denote the depth, message width, and message precision of an MPGNN, respectively, as defined in Section 2.2 ; R denotes the number of random bits used; C denotes the size of the color set, as defined in Section 2.4 ; and pf denotes the failure probability. The parameter c0≥2 depends on pf . In our upper-bound constructions, we focus on communication resources (such as d , w and p ), and assume sufficiently large local states and sufficiently expressive local functions, including in the rooted, port-aware model.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Function
Deterministic
Randomized
Private Coin
Public Coin
D(⋅)
R0prv(⋅)
R1/3prv(⋅)
R0pub(⋅)
R1/3pub(⋅)
EQn
Θ(n)†
Θ(n)†
Θ(logn)†
Θ(n) *
Θ(1)†
Appendix
Table 2: Communication complexity of the EQn function under different settings.
Figure 1: The constructed basic graph. The edges {x(σ),uj(σ)} and {x(σ),vj(σ)} are omitted, and the connecting path is simplified.
Figure 2: The constructed virtually colored hard instance graph. The edges {x(σ),uj(σ)} and {x(σ),vj(σ)} are omitted, and the connecting path is simplified.
Figure 3: An illustration of the decolorization process.
Figure 4: The constructed basic graph. The connecting path is simplified.
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.
The Weisfeiler--Lehman (WL) test and its simplicial extension (SWL) characterize the combinatorial expressivity of message passing networks, but they are blind to geometry, i.e., meshes with identical connectivity but different embeddings are indistinguishable. We introduce the Geometric Simplicial Weisfeiler--Lehman (GSWL) test, which incorporates vertex coordinates into color refinement for geometric simplicial complexes. In addition, we show that (i) the expressivity of geometry-aware simplicial message passing schemes is bounded above by GSWL, and (ii) that there exist parameters such that the discriminating power of GSWL is matched by these schemes on any fixed finite family of geometric simplicial complexes. Combined with the Euler Characteristic Transform (ECT), a complete invariant for geometric simplicial complexes, this yields a geometric expressivity characterization together with an approximation framework. Experiments on synthetic and mesh datasets serve to validate our theory, showing a clear hierarchy from combinatorial to geometry-aware models.
Elena Xinyi Wang, Bastian Rieck
AIDOS Lab, University of Fribourg Fribourg, Switzerland
The stable coloring of the Weisfeiler-Leman (1-WL) test is a cornerstone of Graph Neural Networks because it provides an upper bound to the expressive power of message-passing architectures. Unfortunately, computing it presents two fundamental bottlenecks. First, classic algorithms are inherently sequential and cannot exploit modern massively parallel hardware. Second, these are global algorithms, i.e., they require availability in memory of the full graph, severely limiting applicability to real-world instances. We leverage a linear-algebraic interpretation of 1-WL stable coloring and introduce two key contributions: (i)~a randomized refinement algorithm with tight probabilistic guarantees and (ii)~a correctness-preserving batching scheme that decomposes the graph into independently processable subgraphs while provably returning a stable coloring of the original graph. This approach maps directly to GPU-efficient primitives. In numerical experiments, our CUDA implementation delivers speedups up to two orders of magnitude over classical CPU-based partition refinement and, for the first time, successfully computes stable colorings on web-scale graphs with over 30 billion edges, where CPU baselines time out or fail.
Filippo Biondi, Mirco Tribastone, Max Tschaikowski
IMT Lucca, Italy · Sapienza University Rome, Italy