Expressive Power and the WL Test

Understanding the capabilities and limitations of Graph Neural Networks requires evaluating their expressive power: their ability to distinguish between different graph structures and learn functions that depend on these structures. A fundamental question in graph theory is the graph isomorphism problem: determining if two graphs are structurally identical, even if their node labeling or drawing differs. While solving graph isomorphism efficiently is a long-standing open problem, certain heuristics offer valuable information about graph similarity. One such heuristic, highly relevant to GNNs, is the Weisfeiler-Lehman (WL) test.

The Weisfeiler-Lehman Test (1-WL)

The most common variant discussed in the GNN literature is the 1-dimensional Weisfeiler-Lehman test (1-WL), also known as naive vertex refinement. It's an iterative algorithm designed to produce a canonical labeling or signature for a graph based on local neighborhood structures. If two graphs produce different signatures after any iteration, they are definitively non-isomorphic. However, if they produce the same signature, they might be isomorphic, but it's not guaranteed (the test is necessary but not sufficient for isomorphism).

Here's how the 1-WL test works:

1. Initialization (Iteration $k=0$): Assign an initial label (or color) $l_v^{(0)}$ to each node $v$. Typically, all nodes start with the same label unless initial node features or degrees are used.
2. Iterative Refinement (Iteration $k \ge 1$): For each node $v$, collect the labels of its neighbors $\mathcal{N}(v)$ from the previous iteration $k-1$. Form a multiset of these labels: $S_v^{(k)} = \{ \{ l_u^{(k-1)} \mid u \in \mathcal{N}(v) \} \}$.
3. Label Update: Generate a new label $l_v^{(k)}$ for node $v$ by hashing the pair $(l_v^{(k-1)}, S_v^{(k)})$. This hash combines the node's own previous label with the multiset signature of its neighborhood. The important point is that nodes with the same previous label and the same multiset of neighbor labels receive the same new label.
4. Termination: Repeat steps 2 and 3 until the set of unique labels across the graph no longer changes between iterations. The final distribution of labels (or the sequence of distributions over iterations) serves as the graph's signature.

Consider two simple graphs:

Initial state ($k=0$) for two graphs. All nodes have the same initial label (gray).

After one iteration of 1-WL:

• Graph G1: Each node has two neighbors, both with the initial gray label. The multiset $S_v^{(1)}$ is {gray, gray} for all nodes $v$. The hash of (gray, {gray, gray}) yields a new label, say 'blue'. All nodes in G1 become blue.
• Graph G2: Node a2 has one gray neighbor (b2). Its $S_{a2}^{(1)}$ is {gray}. Node b2 has two gray neighbors (a2, c2). Its $S_{b2}^{(1)}$ is {gray, gray}. Node c2 has one gray neighbor (b2). Its $S_{c2}^{(1)}$ is {gray}.
  • Nodes a2 and c2 hash (gray, {gray}) and get a new label, say 'orange'.
  • Node b2 hashes (gray, {gray, gray}) and gets a new label, say 'blue'.

State after one iteration ($k=1$). G1 has one label type (blue), G2 has two (orange, blue). The label distributions differ, so 1-WL distinguishes these graphs.

Since the label distributions differ after $k=1$, the 1-WL test concludes that G1 and G2 are non-isomorphic.

Connecting WL Test to Message Passing GNNs

Now, let's revisit the message passing framework introduced earlier:

$$\mathbf{h}_v^{(k)} = \text{UPDATE}^{(k)} \left( \mathbf{h}_v^{(k-1)}, \text{AGGREGATE}^{(k)} \left( \{ \mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v) \} \right) \right)$$

Observe the similarity:

1. The AGGREGATE function collects information from neighbors, analogous to collecting neighbor labels $l_u^{(k-1)}$ into the multiset $S_v^{(k)}$ in the WL test. Common aggregators like sum, mean, or max operate on the multiset of neighbor features $\{\mathbf{h}_u^{(k-1)}\}$.
2. The UPDATE function combines the aggregated neighborhood information with the node's own previous state $\mathbf{h}_v^{(k-1)}$, similar to how the WL test uses the pair $(l_v^{(k-1)}, S_v^{(k)})$ to compute the new label $l_v^{(k)}$.

This structural similarity is not coincidental. It has been formally shown that the expressive power of message-passing GNNs (MPNNs) is upper-bounded by the power of the 1-WL test. This means:

• If two graphs can be distinguished by the 1-WL test, an appropriately designed MPNN might also be able to distinguish them by learning node representations that differ between the graphs. The GNN's aggregation and update functions need to be sufficiently powerful (e.g., injective functions mapping distinct multisets to distinct outputs).
• If two graphs cannot be distinguished by the 1-WL test, then no standard MPNN can distinguish them. Regardless of the specific AGGREGATE and UPDATE functions (as long as they follow the message-passing framework) or the number of layers, the node representations learned by the GNN for structurally equivalent nodes (according to 1-WL) will converge to the same values in both graphs.

Limitations and Implications

The 1-WL test, and therefore standard MPNNs, cannot distinguish certain graph structures. A classic example is distinguishing different regular graphs (graphs where all nodes have the same degree). For instance, the 1-WL test cannot distinguish a 6-node cycle graph (degree 2 for all nodes) from two disconnected 3-node cycle graphs (also degree 2 for all nodes). An MPNN would compute identical node embeddings for all nodes in both scenarios after a sufficient number of layers.

Example graphs G3 (6-cycle) and G4 (two disjoint 3-cycles). Both are 2-regular. The 1-WL test (and standard MPNNs) cannot distinguish between them, assigning the same final label/embedding to all nodes in both graphs.

This limitation highlights that standard GNNs primarily capture local neighborhood structures effectively but struggle with certain global properties or distinguishing structures that appear locally similar according to the 1-WL refinement process.

Understanding this connection is significant for selecting or designing GNN architectures. If a task requires distinguishing graph structures past the capability of the 1-WL test, standard MPNN architectures like GCN or GraphSAGE might be insufficient. This motivates the development of more powerful GNNs, often inspired by higher-order WL tests ($k$-WL) or incorporating mechanisms like graph substructure counting or positional encodings, which we will examine in later chapters. Knowing the theoretical ceiling of standard message passing helps appreciate why more advanced architectures are sometimes necessary.