Abstract
Graph neural networks process structured data by iteratively aggregating features from local neighborhoods, but theoretical analysis shows that most standard GNN architectures cannot distinguish certain pairs of non-isomorphic graphs, limiting their representational power. The connection to the Weisfeiler-Leman (WL) graph isomorphism test, formalized by Xu et al. in 2019, sparked a wave of research into higher-order GNNs, positional encodings, and randomized techniques that extend expressivity without prohibitive computational cost. Understanding these limits is practically important because real-world graph tasks - molecular property prediction, circuit simulation, knowledge graph completion - can require distinguishing structural patterns that lie in the WL blind spot.
The WL Hierarchy and GNN Equivalence
The 1-WL test iteratively relabels each node with a hash of its label and its neighbors’ label multiset, terminating when labels stabilize. Two graphs are declared non-isomorphic if their label histograms diverge at any iteration; otherwise the test is inconclusive. Xu et al. showed that message-passing GNNs (MPGNNs) with injective aggregation functions - such as Graph Isomorphism Networks (GIN) with sum aggregation - are maximally expressive within the 1-WL class. This means GINs cannot distinguish pairs of graphs that 1-WL fails to separate, including regular graphs of the same degree and certain bipartite structures relevant to chemistry. The k-WL hierarchy generalizes the test to k-tuples of nodes, exponentially increasing expressivity and computational cost with k.
Practical Approaches to Increased Expressivity
| Rather than scaling k-WL directly, several tractable alternatives have emerged. Random feature GNNs (Sato et al., Abboud et al.) augment node features with random identifiers at inference time, breaking structural symmetry and separating most WL-equivalent graphs in expectation, at the cost of non-deterministic outputs. Structural positional encodings derived from eigenvectors of the graph Laplacian (as used in Graphormer, Microsoft Research, and later GRIT) provide deterministic position-like signals, though the sign ambiguity of eigenvectors requires careful normalization. Subgraph GNNs extract ego-network features for each node by running a base GNN on each node-deleted subgraph, achieving 3-WL expressivity at the cost of an | V | -fold compute multiplier. Equivariant message-passing networks for molecular graphs (e.g., SchNet, DimeNet, PaiNN) exploit geometric invariances - distances, angles, torsions - to implicitly exceed WL expressivity within the domain of 3D molecular data. |
Molecular Property Prediction as a Stress Test
Predicting quantum chemical properties of molecules is a benchmark where expressivity limits have direct practical consequences. Graphs representing different molecular configurations can be WL-equivalent while having distinct physical properties. The OGB-LSC PCQM4Mv2 benchmark has been a proving ground: top entries as of mid-2025 use hybrid architectures that combine MPGNN layers for local chemistry with Transformer attention for global structure, paired with 3D conformation features when available. The MACE architecture (Kovacs et al., Cambridge), designed for interatomic potentials, uses higher-body-order equivariant features and has shown strong data efficiency on MD-17 and rMD17 datasets. These gains come from domain-specific inductive bias rather than general WL expressivity, illustrating that theoretical expressivity bounds are necessary but not sufficient guides to practical architecture design.
Future Directions
Establishing expressivity hierarchies for heterogeneous graphs, hypergraphs, and dynamic graphs remains largely open. For most application domains, the binding constraint is not expressivity in the WL sense but generalization under limited labeled data, sensitivity to graph size distribution shift, and scalability to graphs with millions of nodes. Research into how expressivity relates to generalization - rather than worst-case separation - is beginning to attract attention and may reframe which theoretical properties practitioners should prioritize.