Abstract
Standard Message-Passing Neural Networks (MPNNs) are fundamentally limited in their ability to capture graph topology, often failing to distinguish between non-isomorphic graphs that are 1-WL equivalent. We present Structural Message-Passing (SMP), a novel architecture that breaks this expressivity ceiling. SMP replaces traditional node feature vectors with local context matrices that track node identities while maintaining permutation equivariance. This allows the model to learn complex topological properties like cycle detection and graph diameter. SMP achieves state-of-the-art results on the ZINC molecular dataset and demonstrates exceptional generalization from small to large graphs.
Introduction
Graph Neural Networks (GNNs) have become the standard for processing relational data due to their permutation equivariance and strong inductive bias toward local structures. However, most GNNs are at most as powerful as the 1-dimensional Weisfeiler-Lehman (1-WL) isomorphism test. This theoretical limit renders them "topologically blind," unable to compute basic properties such as connectivity, shortest path lengths, or the presence of cycles. While adding unique node identifiers can increase expressivity, it typically breaks permutation equivariance, leading to poor generalization as the model overfits to specific ID assignments.
Structural Message-Passing (SMP)
The authors propose Structural Message-Passing (SMP) to bridge the gap between the efficiency of local message-passing and the power of node identifiers.
Local Context Matrices
In SMP, each node $i$ maintains a matrix $U_i \in \mathbb{R}^{n \times c}$ instead of a single feature vector. This "local context matrix" serves as a map where the $j$-th row represents node $i$'s knowledge about node $j$. This representation provides a much larger bandwidth for structural information to flow, mitigating the "over-squashing" bottleneck common in standard GNNs.
Equivariant Initialization and Propagation
These matrices are initialized with a one-hot encoding of node identities. The core innovation lies in the design of message and update functions that ensure the model remains permutation equivariant. As shown in Figure 1, if nodes are reordered by a permutation $\pi$, the rows of the local context matrices are permuted accordingly, but the underlying structural relationships remain invariant.
Efficient Implementations and Graph Coloring
To manage the $O(n^2)$ memory requirement of these matrices, the authors introduce:
- Fast SMP: An efficient variant using pointwise multiplications, acting as a local version of Provably Powerful Graph Networks (PPGN).
- Graph Coloring: A technique where nodes outside each other's receptive fields share identifiers, preventing "collisions" while significantly reducing memory overhead.
Experimental Results
SMP was evaluated on synthetic topological tasks and the real-world ZINC molecular dataset.
Synthetic Topological Tasks
SMP achieved perfect accuracy in cycle detection (lengths 4, 6, and 8), connectivity testing, and graph diameter estimation. Standard MPNNs failed these tasks entirely, and even higher-order models like PPGN struggled to maintain accuracy as graph size increased.
Molecular Benchmarks
On the ZINC dataset, SMP achieved a Mean Absolute Error (MAE) of 0.138 (using edge features), setting a new state-of-the-art for models not utilizing expert-crafted chemical features. Crucially, SMP showed superior "out-of-distribution" generalization, maintaining high performance when trained on small graphs and tested on significantly larger ones.
Complexity and Limitations
While SMP offers significant gains in expressivity, it comes with increased computational costs compared to standard GNNs.
As summarized in the table above, SMP's memory and time complexities are higher than GIN or MPNN. Even with graph coloring, the $O(n \chi c)$ memory requirement makes it challenging to scale to massive social networks with millions of nodes. Future work aims to explore more aggressive sparsification of the local context matrices to improve scalability.
Conclusion
Structural Message-Passing represents a significant step forward in GNN design. By treating node identity as a structural feature and propagating it equivariantly, SMP overcomes the 1-WL limit without sacrificing generalization. Its success on both synthetic and real-world benchmarks highlights the importance of providing sufficient bandwidth for structural information in graph representation learning.
Summary updated