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

Floris Geerts, Filip Mazowiecki, Guillermo A. Pérez

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.

Introduction

In the study of Graph Neural Networks (GNNs), "distinguishing power" serves as the primary metric for measuring expressivity: the ability of an architecture to differentiate between distinct graph structures. Prior research has established that standard GNNs are at most as powerful as the 1-dimensional Weisfeiler-Lehman (WL) algorithm, a classic heuristic for the graph isomorphism problem.

However, many popular architectures—most notably Kipf and Welling’s Graph Convolutional Networks (GCNs)—explicitly incorporate node degrees for normalization. This paper addresses the theoretical gap in understanding how this degree information affects a model's power. Specifically, we investigate whether knowing node degrees from the outset makes a GNN fundamentally more powerful than the WL test or simply more efficient.

The Message-Passing Framework

To analyze these models, we unify various GNN architectures under the Message-Passing Neural Network (MPNN) framework, categorized into two main classes:

  1. Anonymous MPNNs: Message functions depend solely on the labels or features of the involved vertices.
  2. Degree-aware MPNNs: Message functions can additionally utilize the degree of the vertices.

As a theoretical study, this work bypasses standard empirical benchmarks in favor of synthetic counterexample graphs. These carefully constructed small graphs possess specific symmetries that allow us to prove whether certain architectures can distinguish between nodes that the WL algorithm can, and vice versa.

Theoretical Insights

Our analysis reveals several critical nuances in GNN expressivity:

  • The "Head Start" of Degrees: Degree-aware MPNNs (like GCNs) are "one step ahead" of the WL algorithm. While WL only discovers node degrees after its first iteration of neighborhood aggregation, degree-aware GNNs possess this structural information in their initial state.
  • The Vanilla GCN Paradox: Surprisingly, "plain vanilla" GCNs as originally formulated cannot simulate the WL algorithm due to their rigid normalization schemes.
  • The Trade-off Parameter: We find that adding a learnable trade-off parameter between a node's own features and its neighbors' features—a minor relaxation suggested by Kipf and Welling—is the essential component that allows GCNs to match the power of the WL algorithm.
  • Efficiency Gains: We refine previous results by showing that the WL algorithm can be simulated using only one ReLU layer per step, improving upon prior suggestions that two layers were necessary.

Key Results

Hierarchy of distinguishing power between various GNN architectures and the Weisfeiler-Lehman (WL) algorithm.

The core theoretical contributions establish a hierarchy of distinguishing power:

  • Equivalence of Anonymous MPNNs: We prove that the class of all anonymous MPNNs is exactly as powerful as the WL algorithm ($M_{anon} \equiv M_{WL}$).
  • GCN Bounds: The distinguishing power of GCNs is bounded by the WL algorithm, though they maintain a "one step ahead" advantage ($M_{deg} \preceq_{+1} M_{WL}$).
  • Simulation Proof: On a fixed graph, we demonstrate that GNNs using ReLU or sign activation functions can simulate the WL algorithm step-by-step. While standard GCNs fail this simulation, those with a learnable trade-off parameter succeed, providing theoretical justification for the parameter's use in practice.

Discussion and Future Work

A primary limitation of this work is that the simulation results (matching GNN power to WL) are performed on a fixed input graph, meaning the weights and biases are tailored to that specific structure. A major open question remains: does there exist a single GNN architecture with a fixed set of weights that can simulate the WL algorithm across all possible graphs simultaneously? Future research should also extend this analysis to higher-order WL tests (k-WL) and more complex message-passing schemes.

Summary updated

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.
BibTeX
@inproceedings{geerts2021let,
  author = {Floris Geerts and Filip Mazowiecki and Guillermo A. Pérez},
  title = {{Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=XtUQoJxuhXL},
}
Figure