Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework

• URL: http://arxiv.org/abs/2004.02593v1
• Date: Mon, 6 Apr 2020 12:14:00 GMT
• Title: Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework
• Authors: Floris Geerts, Filip Mazowiecki and Guillermo A. P\'erez
• Abstract summary: 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.
• Score: 5.835421173589977
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we cast neural networks defined on graphs as message-passing neural networks (MPNNs) in order to study the distinguishing power of different classes of such models. We are interested in whether certain architectures are able to tell vertices apart based on the feature labels given as input with the graph. We consider two variants of MPNNS: anonymous MPNNs whose message functions depend only on the labels of vertices involved; and degree-aware MPNNs in which message functions can additionally use information regarding the degree of vertices. The former class covers a popular formalisms for computing functions on graphs: graph neural networks (GNN). The latter covers the so-called graph convolutional networks (GCNs), a recently introduced variant of GNNs by Kipf and Welling. We obtain lower and upper bounds on the distinguishing power of MPNNs in terms of the distinguishing power of the Weisfeiler-Lehman (WL) algorithm. Our results imply that (i) the distinguishing power of GCNs is bounded by the WL algorithm, but that they are one step ahead; (ii) the WL algorithm cannot be simulated by "plain vanilla" GCNs but the addition of a trade-off parameter between features of the vertex and those of its neighbours (as proposed by Kipf and Welling themselves) resolves this problem.

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)
• Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning [3.236774847052122]
  We study the expressive power of graph neural networks through the lens of graph partitioning. We introduce a novel GNN architecture, namely Graph Partitioning Neural Networks (GPNNs)
  arXiv  Detail & Related papers  (2023-12-14T06:08:35Z)
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations [26.77596449192451]
  Graph neural networks (GNNs) have emerged as a promising tool for solving machine learning problems on graphs. In this paper, we define a distance function between nodes which is based on the hierarchy produced by the Weisfeiler-Leman (WL) algorithm. We propose a model that learns representations which preserve those distances between nodes.
  arXiv  Detail & Related papers  (2022-11-04T15:03:41Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• KerGNNs: Interpretable Graph Neural Networks with Graph Kernels [14.421535610157093]
  Graph neural networks (GNNs) have become the state-of-the-art method in downstream graph-related tasks. We propose a novel GNN framework, termed textit Kernel Graph Neural Networks (KerGNNs) KerGNNs integrate graph kernels into the message passing process of GNNs. We show that our method achieves competitive performance compared with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-01-03T06:16:30Z)
• Graph Neural Networks with Learnable Structural and Positional Representations [83.24058411666483]
  A major issue with arbitrary graphs is the absence of canonical positional information of nodes. We introduce Positional nodes (PE) of nodes, and inject it into the input layer, like in Transformers. We observe a performance increase for molecular datasets, from 2.87% up to 64.14% when considering learnable PE for both GNN classes.
  arXiv  Detail & Related papers  (2021-10-15T05:59:15Z)
• Identity-aware Graph Neural Networks [63.6952975763946]
  We develop a class of message passing Graph Neural Networks (ID-GNNs) with greater expressive power than the 1-WL test. ID-GNN extends existing GNN architectures by inductively considering nodes' identities during message passing. We show that transforming existing GNNs to ID-GNNs yields on average 40% accuracy improvement on challenging node, edge, and graph property prediction tasks.
  arXiv  Detail & Related papers  (2021-01-25T18:59:01Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  Graph Neural Networks (GNNs) are information processing architectures for signals supported on graphs. They are generalizations of convolutional neural networks (CNNs) in which individual layers contain banks of graph convolutional filters.
  arXiv  Detail & Related papers  (2020-08-04T18:57:36Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  We show that Folklore Graph Neural Networks (FGNN) are the most expressive architectures proposed so far for a given tensor order. FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms.
  arXiv  Detail & Related papers  (2020-06-28T16:35:45Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)

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.