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

• URL: http://arxiv.org/abs/2006.09499v1
• Date: Tue, 16 Jun 2020 20:24:01 GMT
• Title: Walk Message Passing Neural Networks and Second-Order Graph Neural Networks
• Authors: Floris Geerts
• Abstract summary: We introduce a new type of MPNN, $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. In particular, to match W[$ell$] in expressive power, we allow $ell-1$ matrix multiplications in each layer.
• Score: 4.355567556995855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network [2.766564215769441]
  MPNNs' ability to distinguish between graphs is limited to graphs separable by the Weisfeiler-Lemann (WL) graph isomorphism test. We show that our MPNN is competitive with standard MPNNs for several graph learning tasks and is far more accurate in over-squashing long-range tasks.
  arXiv  Detail & Related papers  (2024-10-10T18:11:23Z)
• Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
  We propose textitsubstructure encoding function to uplift the expressive power of any $K$-hop message-passing GNN. Our method is provably more powerful than previous works on $K$-hop graph neural networks and 1-WL subgraph GNNs.
  arXiv  Detail & Related papers  (2024-06-27T15:10:56Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  We propose Spatio-Spectral Graph Networks (S$2$GNNs) S$2$GNNs combine spatially and spectrally parametrized graph filters. We show that S$2$GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs.
  arXiv  Detail & Related papers  (2024-05-29T14:28:08Z)
• Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
  We consider continuous extensions of both $1$-WL and MPNNs to graphons. We show that the continuous variant of $1$-WL delivers an accurate topological characterization of the expressive power of MPNNs on graphons. We also evaluate different MPNN architectures based on their ability to preserve graph distances.
  arXiv  Detail & Related papers  (2023-06-06T14:12:23Z)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. We propose an extension, $(k,t)$-FWL, which considers any equivariant set as neighbors instead of all nodes. N$2$-GNN achieves record-breaking results on ZINC-Subset (0.059), outperforming previous SOTA results by 10.6%.
  arXiv  Detail & Related papers  (2023-06-05T21:35:32Z)
• WL meet VC [9.468816647649104]
  We study the expressive power of graph neural networks (GNNs) through the lens of Vapnik--Chervonenkis (VC) dimension theory. We derive an upper bound for GNNs' VC dimension using the number of colors produced by the $1text-mathsfWL$ and GNNs' VC dimension.
  arXiv  Detail & Related papers  (2023-01-26T11:29:36Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  Link prediction is one important application of graph neural networks (GNNs) Most existing GNNs for link prediction are based on one-dimensional Weisfeiler-Lehman (1-WL) test. We study a completely different approach which can directly obtain node pair (link) representations based on textittwo-dimensional Weisfeiler-Lehman (2-WL) tests.
  arXiv  Detail & Related papers  (2022-06-20T04:50:38Z)
• Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
  We propose a novel graph isomorphism test method, namely Twin-WL, which simultaneously passes node labels and node identities. We prove that the two Twin-GNNs both have higher expressive power than traditional message passing GNNs.
  arXiv  Detail & Related papers  (2022-03-22T12:58:03Z)
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework [5.835421173589977]
  We cast neural networks defined on graphs as message-passing neural networks (MPNNs) We consider two variants of MPNNs: anonymous MPNNs and degree-aware MPNNs. We obtain lower and upper bounds on the distinguishing power of MPNNs in terms of the distinguishing power of the Weisfeiler-Lehman (WL) algorithm.
  arXiv  Detail & Related papers  (2020-04-06T12:14:00Z)
• $\Pi-$nets: Deep Polynomial Neural Networks [86.36557534288535]
  $Pi$-Nets are neural networks in which the output is a high-order of the input. We empirically demonstrate that $Pi$-Nets have better representation power than standard DCNNs. Our framework elucidates why recent generative models, such as StyleGAN, improve upon their predecessors.
  arXiv  Detail & Related papers  (2020-03-08T18:48:43Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.