Weisfeiler-Lehman Test

The core algorithm operates through iterative label propagation. In each round, every node aggregates the labels of its immediate neighbors, hashes this multiset together with its own current label, and is assigned a new, refined label.

• Initialization: All nodes start with an identical label (or one based on atomic number).
• Aggregation: Collect neighbor labels into a multiset.
• Hashing: Injectively map the pair (own label, neighbor multiset) to a new label.
• Termination: The algorithm stops when the partition of nodes into label groups stabilizes.

The WL test establishes a strict theoretical limit: no message-passing GNN can distinguish two non-isomorphic graphs that the WL test itself cannot distinguish. This is a direct consequence of the fact that MPNN aggregators are never more powerful than the injective hash functions used in WL.

• A GNN's representational capacity is at most equal to the 1-WL test.
• Architectures like Graph Isomorphism Networks (GIN) are designed to achieve this exact bound.
• Failure cases for WL are failure cases for standard GNNs, such as distinguishing regular graphs with identical degree sequences.

The 1-WL test fails on graphs where every node has the same degree and local neighborhood structure, such as strongly regular graphs. In these cases, all nodes receive identical labels at every iteration, causing the algorithm to incorrectly report the graphs as isomorphic.

• Example: A pair of non-isomorphic strongly regular graphs with parameters (16,6,2,2) are indistinguishable by 1-WL.
• Molecular Relevance: This failure is critical for distinguishing complex molecular cages or highly symmetric metal-organic frameworks.
• Solution: Higher-order WL variants (k-WL) or architectures incorporating geometric information like SE(3) equivariance.

To overcome the limitations of 1-WL, the k-dimensional Weisfeiler-Lehman test (k-WL) colors k-tuples of nodes instead of individual nodes. This creates a strict hierarchy of discriminative power.

• 1-WL: Equivalent to standard message-passing GNNs.
• 2-WL: Equivalent to 2-Folklore WL, capable of distinguishing strongly regular graphs that 1-WL fails on.
• 3-WL: Strictly more powerful than 2-WL, but computationally prohibitive for large graphs.
• Trade-off: Higher-order tests provide more power but scale exponentially with k, making them impractical for large molecular datasets.

The Graph Isomorphism Network is architected specifically to be as powerful as the 1-WL test. It achieves this by using a sum aggregator and a multi-layer perceptron to approximate an injective function over multisets.

• Aggregation: Sum is used because it is injective over multisets, unlike mean or max.
• Update: An MLP processes the aggregated features to ensure the function is universal.
• Readout: A concatenation of sum-pooled features from all layers mimics the WL color histogram.
• GIN's theoretical alignment with WL makes it the standard baseline for maximum expressivity in MPNNs.

The sequence of labels assigned to a node across iterations captures its rooted subtree structure—the pattern of connectivity expanding outward. This WL subtree kernel is a powerful, deterministic molecular fingerprint.

• Iteration 0: Represents the atom type.
• Iteration 1: Captures the atom and its immediate bonding environment.
• Iteration N: Encodes the molecular fragment within a radius of N bonds.
• This directly parallels the Extended Connectivity Fingerprint (ECFP), a standard in cheminformatics, making WL a natural bridge between classical fingerprints and learned GNN representations.