Standard Graph Neural Networks (GNNs) are theoretically limited by the 1-Weisfeiler-Leman (1-WL) isomorphism test. This means they often fail to distinguish even simple non-isomorphic graphs, such as a graph with two triangles versus one with a six-node cycle.
While many researchers have proposed extensions to break this limit—such as counting subgraphs or removing nodes—these extensions are usually only compared to the classical $k$-WL hierarchy. However, the $k$-WL hierarchy is often too "coarse" for practical GNNs; most meaningful extensions are already more powerful than 1-WL but much weaker than 3-WL.
This paper provides a rigorous theoretical map of the "landscape of power" for GNN extensions, comparing hierarchies based on subgraph counting, neighborhood preprocessing, and node marking. The core finding? No single extension is strictly superior to the others.
Three Hierarchies of GNN Extensions
The authors formalize and compare three distinct "hierarchies" of local GNN extensions:
- $S_k$ (Counting Substructures): The GNN is given the counts of all connected subgraphs of size up to $k$ incident to each node as initial features.
- $N_k$ (Neighborhood Knowledge): The GNN is given the isomorphism class of the $k$-hop induced neighborhood of each node. This is a very strong local feature but computationally expensive.
- $M_k$ (GNNs with Markings): Introduced as a more powerful version of "node removal" GNNs. Instead of deleting $k$ nodes, the model runs multiple passes where $k$ nodes are "marked" (given a special label). This preserves the graph's connectivity while breaking symmetry.
The paper uses proof by construction: for any two extensions $A$ and $B$, the authors find specific graph pairs that $A$ can distinguish but $B$ cannot, and vice versa. They utilize specific synthetic graph constructions designed to probe structural limits, such as Rook’s $4 \times 4$ vs. Shrikhande graphs, cycle-based constructions, and CFI graphs.
Key Insights and The Landscape of Power
The most striking finding is that these hierarchies are often incomparable. For example, $N_1$ (knowing your immediate neighbors' connections) can distinguish some graphs that $M_k$ (marking $k$ nodes) cannot, even for very large $k$.
Other major takeaways include:
- Marking > Removal: The authors prove that "marking" nodes is strictly more expressive than "removing" them. Removing a node destroys information about the edges connected to it; marking it allows the GNN to "see" those edges while still breaking the symmetry.
- The 2-WL Barrier: Relatively simple extensions can beat the 2-WL test, which is a common baseline for "powerful" GNNs. For instance, $M_2$ (marking 2 nodes) and $S_4$ (counting 4-node subgraphs) are both strictly more powerful than 2-WL ($M_2 \succ \text{2-WL}$).
- Counting Ability: The paper provides a theoretical mapping for what each extension can count. For example, $M_k$ can count cliques of size $k+2$, while $S_k$ is limited to size $k$. However, sufficiently large subgraph counting can eventually overtake marking in certain scenarios ($S_{2k+2} \succ M_k$).
- Limits of Locality: For all three hierarchies, there exist graphs that cannot be distinguished unless the parameter $k$ scales linearly with the number of nodes in the graph.
Limitations and Future Directions
While these extensions offer significant theoretical power, they come with practical trade-offs:
- Computational Complexity: Computing the isomorphism class of a $k$-hop neighborhood ($N_k$) is essentially solving the Graph Isomorphism problem locally, which is hard to scale.
- Feature Explosion: For $S_k$, the number of non-isomorphic subgraphs grows exponentially with $k$, making it difficult to use large $k$ in practice.
Future work will need to explore how well these models approximate these features when using practical, bounded-size neural networks, and whether this increased representational power translates to better generalization on unseen data.
Summary updated