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

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2020.

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

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Geometric Deep Learning on Molecular Representations](https://mlsanity.com/paper/2107.12375/) (2021)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [Non-IID Transfer Learning on Graphs](https://mlsanity.com/paper/2212.08174/) (2022)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)
- [Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks](https://mlsanity.com/paper/2107.10234/) (2021)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Learning from the Dark: Boosting Graph Convolutional Neural Networks with Diverse Negative Samples](https://mlsanity.com/paper/2210.00728/) (2022)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processes](https://mlsanity.com/paper/2212.02055/) (2022)
- [Layer-diverse Negative Sampling for Graph Neural Networks](https://mlsanity.com/paper/2403.11408/) (2024)
- [Investigating the Interplay between Features and Structures in Graph Learning](https://mlsanity.com/paper/2308.09570/) (2023)
- [Framelet Message Passing](https://mlsanity.com/paper/2302.14806/) (2023)
- [The PWLR Graph Representation: A Persistent Weisfeiler-Lehman scheme with Random Walks for Graph Classification](https://mlsanity.com/paper/2208.13427/) (2022)
- [Dispatcher: A Message-Passing Approach To Language Modelling](https://mlsanity.com/paper/2105.03994/) (2021)

## Abstract (arXiv)

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.