# Fine-grained Expressivity of Graph Neural Networks

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 60 of its 113 references that are in the map.
- First posted on arXiv 6 Jun 2023.

## Builds on (most cited first, 30 of 60)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters](https://mlsanity.com/paper/1705.07664/) (2017)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Stability Properties of Graph Neural Networks](https://mlsanity.com/paper/1905.04497/) (2019)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Convolutional Neural Network Architectures for Signals Supported on Graphs](https://mlsanity.com/paper/1805.00165/) (2018)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)

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

- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Network](https://mlsanity.com/paper/2410.09118/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [On the H"older Stability of Multiset and Graph Neural Networks](https://mlsanity.com/paper/2406.06984/) (2024)
- [Graph neural networks and non-commuting operators](https://mlsanity.com/paper/2411.04265/) (2024)
- [Structural Node Embeddings with Homomorphism Counts](https://mlsanity.com/paper/2308.15283/) (2023)
- [Contextualized Messages Boost Graph Representations](https://mlsanity.com/paper/2403.12529/) (2024)
- [Link Prediction with Untrained Message Passing Layers](https://mlsanity.com/paper/2406.16687/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum](https://mlsanity.com/paper/2506.05530/) (2025)
- [CosmoBench: A Multiscale, Multiview, Multitask Cosmology Benchmark for Geometric Deep Learning](https://mlsanity.com/paper/2507.03707/) (2025)
- [Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guarantees](https://mlsanity.com/paper/2508.09427/) (2025)
- [What Expressivity Theory Misses: Message Passing Complexity for GNNs](https://mlsanity.com/paper/2509.01254/) (2025)
- [On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry](https://mlsanity.com/paper/2510.10101/) (2025)
- [Towards Graph Prompt Learning: A Survey and Beyond](https://mlsanity.com/paper/2408.14520/) (2024)
- [WILTing Trees: Interpreting the Distance Between MPNN Embeddings](https://mlsanity.com/paper/2505.24642/) (2025)
- [HeSRN: Representation Learning On Heterogeneous Graphs via Slot-Aware Retentive Network](https://mlsanity.com/paper/2510.09767/) (2025)
- [If you can distinguish, you can express: Galois theory, Stone--Weierstrass, machine learning, and linguistics](https://mlsanity.com/paper/2510.09902/) (2025)
- [Neural Networks With Dense Weights Are Not Universal Approximators](https://mlsanity.com/paper/2602.07618/) (2026)
- [Learning to Approximate Uniform Facility Location via Graph Neural Networks](https://mlsanity.com/paper/2602.13155/) (2026)
- [A Topological Characterization of Graph Neural Networks via Stochastic Block Model Embeddings on the n-Sphere](https://mlsanity.com/paper/2606.07598/) (2026)
- [Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction](https://mlsanity.com/paper/2609.34729/) (2026)
- [Warm-starting PDE solvers with any-dimensional machine learning](https://mlsanity.com/paper/2609.38916/) (2026)

## Abstract (arXiv)

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.