Fine-grained Expressivity of Graph Neural Networks

Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, Christopher Morris

Abstract

Numerous recent works have analyzed the expressive power of message-passing graph neural networks (MPNNs), primarily utilizing combinatorial techniques such as the $1$-dimensional Weisfeiler-Leman test ($1$-WL) for the graph isomorphism problem. However, the graph isomorphism objective is inherently binary, not giving insights into the degree of similarity between two given graphs. This work resolves this issue by considering continuous extensions of both $1$-WL and MPNNs to graphons. Concretely, we show that the continuous variant of $1$-WL delivers an accurate topological characterization of the expressive power of MPNNs on graphons, revealing which graphs these networks can distinguish and the level of difficulty in separating them. We identify the finest topology where MPNNs separate points and prove a universal approximation theorem. Consequently, we provide a theoretical framework for graph and graphon similarity combining various topological variants of classical characterizations of the $1$-WL. In particular, we characterize the expressive power of MPNNs in terms of the tree distance, which is a graph distance based on the concept of fractional isomorphisms, and substructure counts via tree homomorphisms, showing that these concepts have the same expressive power as the $1$-WL and MPNNs on graphons. Empirically, we validate our theoretical findings by showing that randomly initialized MPNNs, without training, exhibit competitive performance compared to their trained counterparts. Moreover, we evaluate different MPNN architectures based on their ability to preserve graph distances, highlighting the significance of our continuous $1$-WL test in understanding MPNNs' expressivity.

Introduction

For years, the gold standard for measuring the expressive power of a Graph Neural Network (GNN) has been the 1-dimensional Weisfeiler-Leman (1-WL) test. If the 1-WL test can distinguish two graphs, a sufficiently powerful GNN can too. However, this approach is inherently binary: it determines if two graphs are isomorphic or not, but provides no insight into the degree of similarity between them. In practical applications, structural "closeness" is vital; for instance, a small change in a molecule's structure should ideally result in a proportional change in its neural representation.

Furthermore, existing Universal Approximation theorems for GNNs often rely on edit distance, which counts edge flips. Edit distance is often a poor metric for machine learning because graphs with different vertex counts are automatically considered distant, even if they share identical underlying structural patterns. This paper addresses these limitations by moving toward a continuous framework of similarity.

Methodology

The authors bridge the gap between discrete isomorphism and continuous similarity using Graphon Theory. Graphons are continuous limit objects that represent the structure of large, dense graphs.

Continuous 1-WL and Iterated Degree Measures

The core contribution is the extension of the discrete 1-WL test to graphons via Iterated Degree Measures (IDMs). Instead of assigning discrete labels to nodes, the continuous 1-WL assigns measures that describe the distribution of their neighbors' structures. This process is illustrated in Figure 1, where node labels evolve over iterations $h$ to capture increasingly complex neighborhood information.

The continuous 1-WL process. Node labels are iteratively updated to reflect neighborhood distributions, forming Iterated Degree Measures (IDMs) that allow for a continuous measure of graph similarity.

To quantify the distance between these IDMs, the authors introduce two new metrics:

  1. $\delta_P$: Based on the Prokhorov metric.
  2. $\delta_W$: Based on an unbalanced Wasserstein metric.

Topological Framework and Universal Approximation

By treating the space of all graphs as a subset of the compact space of graphons, the authors apply the Stone-Weierstrass theorem. This leads to a Universal Approximation Theorem: MPNNs can approximate any continuous function on graphons that is invariant to the 1-WL test. This unifies several disparate ways of measuring graph similarity—including tree homomorphism densities and "tree distances"—into a single topological framework.

Experimental Evaluation

The theoretical findings were evaluated on standard benchmarks from the TUDataset, including bioinformatics (MUTAG, NCI1, PROTEINS) and social networks (IMDB, REDDIT). Synthetic sequences generated via Stochastic Block Models (SBM) and Erdős-Rényi (ER) models were also used to test structural distance preservation.

Key Results

  • Untrained MPNNs: A striking empirical result is that randomly initialized, untrained MPNNs perform competitively with trained ones. For instance, on the MUTAG dataset, an untrained GIN model achieved 82.56% accuracy, compared to 79.01% for a trained version. This suggests that the message-passing architecture itself, mimicking the 1-WL process, captures essential topological features.
  • Distance Preservation: Experiments demonstrate that as the hidden dimensionality of an MPNN increases, the Euclidean distance between graph embeddings converges to the structural distance ($\delta_W$) between them.
  • Efficiency: Untrained MPNNs offer significant speedups (20%–46% time savings) as they only require optimizing the final linear readout layer.

Discussion and Limitations

While the metrics $\delta_P$ and $\delta_W$ are polynomial-time computable, their upper bounds ($O(h \cdot n^7)$ and $O(h \cdot n^5 \log n)$) may be prohibitive for very large datasets. In such cases, MPNNs can serve as efficient proxies to lower-bound these distances.

Future work remains in extending this fine-grained analysis beyond the 1-WL/MPNN framework to more powerful $k$-WL tests or GNNs capable of counting cycles. Additionally, while the current theory focuses on graph structure and sum-aggregation, exploring other aggregation methods (e.g., max, mean) and a full quantitative treatment of graphs with node features are promising directions for further research.

Summary updated

Abstract

Numerous recent works have analyzed the expressive power of message-passing graph neural networks (MPNNs), primarily utilizing combinatorial techniques such as the $1$-dimensional Weisfeiler-Leman test ($1$-WL) for the graph isomorphism problem. However, the graph isomorphism objective is inherently binary, not giving insights into the degree of similarity between two given graphs. This work resolves this issue by considering continuous extensions of both $1$-WL and MPNNs to graphons. Concretely, we show that the continuous variant of $1$-WL delivers an accurate topological characterization of the expressive power of MPNNs on graphons, revealing which graphs these networks can distinguish and the level of difficulty in separating them. We identify the finest topology where MPNNs separate points and prove a universal approximation theorem. Consequently, we provide a theoretical framework for graph and graphon similarity combining various topological variants of classical characterizations of the $1$-WL. In particular, we characterize the expressive power of MPNNs in terms of the tree distance, which is a graph distance based on the concept of fractional isomorphisms, and substructure counts via tree homomorphisms, showing that these concepts have the same expressive power as the $1$-WL and MPNNs on graphons. Empirically, we validate our theoretical findings by showing that randomly initialized MPNNs, without training, exhibit competitive performance compared to their trained counterparts. Moreover, we evaluate different MPNN architectures based on their ability to preserve graph distances, highlighting the significance of our continuous $1$-WL test in understanding MPNNs' expressivity.
BibTeX
@inproceedings{boker2023fine,
  author = {Jan Böker and Ron Levie and Ningyuan Huang and Soledad Villar and Christopher Morris},
  title = {{Fine-grained Expressivity of Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=jt10uWlEbc},
}
Figure