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

arXiv: https://arxiv.org/abs/2006.09499 · HTML: https://mlsanity.com/paper/2006.09499/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

## Built on by (most cited first, 4 of 4)

- [Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing](https://mlsanity.com/paper/2102.08786/) (2021)
- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers](https://mlsanity.com/paper/2404.03380/) (2024)

## Abstract (arXiv)

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 ℓ-walk MPNNs, which aggregate features along walks of length ℓ between vertices. We show that 2-walk MPNNs match 2-WL in expressive power. More generally, ℓ-walk MPNNs, for any ℓ≥ 2, are shown to match the expressive power of the recently introduced ℓ-walk refinement procedure (W[ℓ]). Based on a correspondence between 2-WL and W[ℓ], we observe that ℓ-walk MPNNs and 2-walk MPNNs have the same expressive power, i.e., they can distinguish the same pairs of graphs, but ℓ-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[ℓ] in expressive power, we consider second-order graph neural networks that allow for non-linear layers. In particular, to match W[ℓ] in expressive power, we allow ℓ-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.