# A Theoretical Comparison of Graph Neural Network Extensions

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 30 Jan 2022.

## Builds on (most cited first, 27 of 27)

- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [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)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks](https://mlsanity.com/paper/2107.10957/) (2021)
- [The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs](https://mlsanity.com/paper/1908.05268/) (2019)

## Built on by (most cited first, 30 of 48)

- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Provably Powerful Graph Neural Networks for Directed Multigraphs](https://mlsanity.com/paper/2306.11586/) (2023)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [On the Expressivity of Persistent Homology in Graph Learning](https://mlsanity.com/paper/2302.09826/) (2023)
- [From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks](https://mlsanity.com/paper/2305.04963/) (2023)
- [Efficient Subgraph GNNs by Learning Effective Selection Policies](https://mlsanity.com/paper/2310.20082/) (2023)
- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [An Efficient Subgraph GNN with Provable Substructure Counting Power](https://mlsanity.com/paper/2303.10576/) (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)
- [What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding](https://mlsanity.com/paper/2305.14814/) (2023)
- [Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs](https://mlsanity.com/paper/2304.11140/) (2023)
- [Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products](https://mlsanity.com/paper/2402.08450/) (2024)
- [A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening](https://mlsanity.com/paper/2406.09291/) (2024)
- [Generalizing Downsampling from Regular Data to Graphs](https://mlsanity.com/paper/2208.03523/) (2022)
- [Learning Graph Algorithms With Recurrent Graph Neural Networks](https://mlsanity.com/paper/2212.04934/) (2022)
- [Union Subgraph Neural Networks](https://mlsanity.com/paper/2305.15747/) (2023)
- [Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality](https://mlsanity.com/paper/2501.03113/) (2025)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings](https://mlsanity.com/paper/2312.05905/) (2023)

## Abstract (arXiv)

We study and compare different Graph Neural Network extensions that increase the expressive power of GNNs beyond the Weisfeiler-Leman test. We focus on (i) GNNs based on higher order WL methods, (ii) GNNs that preprocess small substructures in the graph, (iii) GNNs that preprocess the graph up to a small radius, and (iv) GNNs that slightly perturb the graph to compute an embedding. We begin by presenting a simple improvement for this last extension that strictly increases the expressive power of this GNN variant. Then, as our main result, we compare the expressiveness of these extensions to each other through a series of example constructions that can be distinguished by one of the extensions, but not by another one. We also show negative examples that are particularly challenging for each of the extensions, and we prove several claims about the ability of these extensions to count cliques and cycles in the graph.