Introduction
Graph Neural Networks (GNNs) have become the standard for learning on graph-structured data. A critical metric for evaluating these models is their "distinguishing power"—their ability to tell different graph structures apart. Historically, the gold standard for measuring this expressive power has been the Weisfeiler-Lehman (WL) algorithm, a classical method for testing graph isomorphism. Previous research established that standard GNNs are, at best, as powerful as the WL test.
However, many popular architectures, such as Graph Convolutional Networks (GCNs), utilize node degree information to normalize messages. This "degree-awareness" fell outside the scope of earlier theoretical frameworks. This paper investigates how degree-aware GNNs relate to the WL algorithm, whether knowing a node's degree helps a GNN "see" structures more clearly, and if standard GCNs can truly simulate the WL algorithm.
Categorizing Message-Passing Neural Networks
To systematically analyze these models, the authors use the Message-Passing Neural Network (MPNN) framework to categorize GNNs into two primary classes:
- Anonymous MPNNs: Message functions depend solely on the labels or features of the nodes involved, without explicit structural hints.
- Degree-aware MPNNs: Message functions explicitly incorporate the degree of the sender and receiver nodes (as seen in GCNs).
Through rigorous theoretical analysis using algebraic numbers—which allow for the exact representation of square roots used in GCN normalization—the authors compare these classes against the WL algorithm. Crucially, they evaluate the number of rounds (or layers) required to distinguish vertices, providing a granular look at computational efficiency rather than just asymptotic power.
Key Insights: Succinctness and the GCN Gap
The analysis yields several surprising insights about how GNNs process structural information:
- The "One Step Ahead" Rule: Degree-aware MPNNs are more efficient. The authors prove that a degree-aware model can distinguish certain vertices in $t$ rounds that an anonymous model would need $t+1$ rounds to tell apart. In practical terms, including degree information allows for shallower, more efficient networks.
- The GCN Simulation Gap: Surprisingly, "plain vanilla" GCNs (as originally proposed) cannot simulate the WL algorithm. They are actually weaker than the WL test because they struggle to balance a node's own features with those of its neighbors.
- The Importance of the Trade-off Parameter: To bridge this gap, GCNs require a learnable trade-off parameter ($p$) that weights the self-loop versus the neighbors. While this was suggested empirically in the original GCN paper, this work provides the theoretical justification: without it, the GCN cannot reach the full distinguishing power of the WL algorithm.
- Succinctness vs. Power: While degree information makes a GNN "smarter" per layer (more succinct), it doesn't raise the theoretical ceiling. Even the most advanced degree-aware MPNN is still ultimately bounded by the distinguishing power of the WL algorithm.
Theoretical Results
The paper formalizes these insights through a series of theorems and propositions mapping the exact hierarchy of GNN expressivity:
- Anonymous MPNNs: The authors confirm that anonymous MPNNs are exactly as strong as the WL algorithm when given enough rounds.
- Degree-Aware Hierarchy: Degree-aware models are proven to be stronger than anonymous ones per round (denoted by the $\prec_{+1}$ relationship), but still cannot exceed the WL algorithm's overall capabilities.
- GCN Expressivity (Propositions 18 & 19): These propositions are the "smoking guns" for GCNs. Proposition 18 proves that standard GCNs fail to match WL power. Conversely, Proposition 19 proves that adding a specific learnable parameter allows a modified GCN variant to finally match the WL algorithm.
Limitations and Future Work
The theoretical proofs in this paper rely heavily on specific activation functions, namely ReLU and Sign functions. The authors note that "smooth" functions like Sigmoid or Softplus are harder to analyze because they do not easily allow for the matrix transformations used in their proofs.
Furthermore, while the paper focuses on degree as the primary structural hint, future work could explore Graph Attention Networks (GATs). In GATs, message weights are learned dynamically, which could potentially offer even higher levels of succinctness or power. Finally, while the paper proves degree-aware models need fewer rounds, deep GNNs in practice often suffer from "over-smoothing." These findings provide a strong theoretical foundation for designing more effective, shallower architectures to mitigate this issue.
Summary updated