Building powerful and equivariant graph neural networks with structural message-passing

Clément Vignac, Andreas Loukas, Pascal Frossard

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.

Permutation equivariance in SMP: Reordering nodes results in a corresponding permutation of rows in the local context matrices, preserving structural information.

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.

Complexity comparison: Memory and time complexity per layer for SMP variants versus standard GNNs and higher-order WL models.

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

Abstract

Message-passing has proved to be an effective way to design graph neural networks, as it is able to leverage both permutation equivariance and an inductive bias towards learning local structures in order to achieve good generalization. However, current message-passing architectures have a limited representation power and fail to learn basic topological properties of graphs. We address this problem and propose a powerful and equivariant message-passing framework based on two ideas: first, we propagate a one-hot encoding of the nodes, in addition to the features, in order to learn a local context matrix around each node. This matrix contains rich local information about both features and topology and can eventually be pooled to build node representations. Second, we propose methods for the parametrization of the message and update functions that ensure permutation equivariance. Having a representation that is independent of the specific choice of the one-hot encoding permits inductive reasoning and leads to better generalization properties. Experimentally, our model can predict various graph topological properties on synthetic data more accurately than previous methods and achieves state-of-the-art results on molecular graph regression on the ZINC dataset.
BibTeX
@inproceedings{vignac2020building,
  author = {Clément Vignac and Andreas Loukas and Pascal Frossard},
  title = {{Building powerful and equivariant graph neural networks with structural message-passing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=rQ2djSH1mb6},
}
Figure