Walk Message Passing Neural Networks and Second-Order Graph Neural Networks

Floris GeertsarXiv 2020 · arXiv

Introduction: The 1-WL Barrier

Standard Message Passing Neural Networks (MPNNs) have become the foundation of deep learning on graphs. However, their expressive power is theoretically bounded by the 1-dimensional Weisfeiler-Leman (1-WL) graph isomorphism test. This limitation means that standard MPNNs cannot distinguish between certain non-isomorphic graph structures, such as a single hexagon versus two disjoint triangles. To achieve higher expressivity, researchers often look toward higher-dimensional WL tests, but these typically come with a prohibitive $O(n^3)$ memory complexity, making them impractical for large-scale applications.

$\ell$-Walk MPNNs and Walk Refinement

This research introduces $\ell$-walk MPNNs, a novel theoretical framework designed to bridge the gap between efficiency and expressivity. Unlike standard MPNNs that pass messages between individual vertices and their immediate neighbors, $\ell$-walk MPNNs operate on pairs of vertices. Messages are aggregated along walks of length $\ell$ within the graph.

The paper establishes a rigorous link between these networks and the $\ell$-walk refinement procedure ($W[\ell]$). Through a series of mathematical proofs, the author demonstrates that $\ell$-walk MPNNs exactly match the expressive power of $W[\ell]$. Most significantly, it is proven that 2-walk MPNNs match the distinguishing power of the 2-WL test, providing a clear path to higher-order expressivity.

From Theory to Practice: Learnable Architectures

To translate these theoretical constructs into practical models, the paper formulates concrete, learnable GNN architectures. These architectures utilize Multi-Layer Perceptrons (MLPs) to approximate the injective hash functions required by WL tests. A key contribution is the demonstration that 2-WL expressiveness can be achieved using only $O(n^2)$ memory by leveraging non-linear layers and matrix-style operations, a significant improvement over the $O(n^3)$ requirements of linear third-order GNNs.

Table of GNN architectures and their corresponding dimensions for $\mathbf{A}^{(t)}$, illustrating the learnable formulations of the $\ell$-walk framework.

As shown in the table above, the paper provides specific update rules for various tensor dimensions. These formulations allow for the simulation of walk refinement procedures in both discrete (countable) and continuous (uncountable) feature domains.

Theoretical Insights: The Ceiling of Expressivity

A major open question in the field of second-order GNNs was whether increasing the number of matrix multiplications per layer (i.e., using higher-degree polynomial layers) would yield strictly greater expressive power. This research provides a definitive answer: no.

While higher $\ell$-walk MPNNs (which utilize more complex matrix operations) do not increase the ultimate ceiling of expressivity beyond what 2-walk MPNNs can achieve, they do offer a "speed" advantage. Specifically, they can distinguish the same set of graphs in fewer rounds of message passing. This suggests a trade-off between the complexity of individual layers and the total depth of the network required to reach maximum expressivity.

Conclusion and Future Directions

The framework of $\ell$-walk MPNNs provides a robust theoretical foundation for designing expressive and efficient GNNs. By proving the equivalence to 2-WL with $O(n^2)$ memory, the work opens new avenues for practical second-order graph learning.

However, challenges remain. For uncountable feature domains (continuous real numbers), the required feature dimensions in these architectures currently grow combinatorially with each round. Future work is needed to find more efficient ways to handle continuous features without dimensionality explosion. Additionally, empirical validation on real-world benchmarks will be essential to determine how these theoretically optimal architectures perform in the presence of noise and varied graph topologies.

Summary updated

Abstract

The expressive power of message passing neural networks (MPNNs) is known to match the expressive power of the 1-dimensional Weisfeiler-Leman graph (1-WL) isomorphism test. To boost the expressive power of MPNNs, a number of graph neural network architectures have recently been proposed based on higher-dimensional Weisfeiler-Leman tests. In this paper we consider the two-dimensional (2-WL) test and introduce a new type of MPNNs, referred to as $\ell$-walk MPNNs, which aggregate features along walks of length $\ell$ between vertices. We show that $2$-walk MPNNs match 2-WL in expressive power. More generally, $\ell$-walk MPNNs, for any $\ell\geq 2$, are shown to match the expressive power of the recently introduced $\ell$-walk refinement procedure (W[$\ell$]). Based on a correspondence between 2-WL and W[$\ell$], we observe that $\ell$-walk MPNNs and $2$-walk MPNNs have the same expressive power, i.e., they can distinguish the same pairs of graphs, but $\ell$-walk MPNNs can possibly distinguish pairs of graphs faster than $2$-walk MPNNs. When it comes to concrete learnable graph neural network (GNN) formalisms that match 2-WL or W[$\ell$] in expressive power, we consider second-order graph neural networks that allow for non-linear layers. In particular, to match W[$\ell$] in expressive power, we allow $\ell-1$ matrix multiplications in each layer. We propose different versions of second-order GNNs depending on the type of features (i.e., coming from a countable set, or coming from an uncountable set) as this affects the number of dimensions needed to represent the features. Our results indicate that increasing non-linearity in layers by means of allowing multiple matrix multiplications does not increase expressive power. At the very best, it results in a faster distinction of input graphs.
BibTeX
@misc{geerts2020walk,
  author = {Floris Geerts},
  title = {{Walk Message Passing Neural Networks and Second-Order Graph Neural Networks}},
  year = {2020},
  eprint = {2006.09499},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.09499},
}
Figure