# The Expressive Power of Graph Neural Networks: A Survey

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 89 of its 139 references that are in the map.
- First posted on arXiv 16 Aug 2023.

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

- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [KGAT: Knowledge Graph Attention Network for Recommendation](https://mlsanity.com/paper/1905.07854/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Auto-Encoding Scene Graphs for Image Captioning](https://mlsanity.com/paper/1812.02378/) (2018)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (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)
- [Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs](https://mlsanity.com/paper/2202.04579/) (2022)

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

- [Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges](https://mlsanity.com/paper/2311.07073/) (2023)
- [Expressivity and Generalization: Fragment-Biases for Molecular GNNs](https://mlsanity.com/paper/2406.08210/) (2024)
- [Homomorphism Counts as Structural Encodings for Graph Learning](https://mlsanity.com/paper/2410.18676/) (2024)
- [Future Directions in the Theory of Graph Machine Learning](https://mlsanity.com/paper/2402.02287/) (2024)
- [Multi-Type Point Cloud Autoencoder: A Complete Equivariant Embedding for Molecule Conformation and Pose](https://mlsanity.com/paper/2405.13791/) (2024)
- [Heterogeneous Graph Auto-Encoder for CreditCard Fraud Detection](https://mlsanity.com/paper/2410.08121/) (2024)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [The Role of Fibration Symmetries in Geometric Deep Learning](https://mlsanity.com/paper/2408.15894/) (2024)
- [On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks](https://mlsanity.com/paper/2508.14338/) (2025)
- [Understanding the Robustness of Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2406.13920/) (2024)
- [Khan-GCL: Kolmogorov-Arnold Network Based Graph Contrastive Learning with Hard Negatives](https://mlsanity.com/paper/2505.15103/) (2025)
- [Exploring Graph-Transformer Out-of-Distribution Generalization Abilities](https://mlsanity.com/paper/2506.20575/) (2025)
- [Heat Kernel Goes Topological](https://mlsanity.com/paper/2507.12380/) (2025)
- [Contraction and Hourglass Persistence for Learning on Graphs, Simplices, and Cells](https://mlsanity.com/paper/2604.17548/) (2026)
- [SE-VGAE: Unsupervised Disentangled Representation Learning for Interpretable Architectural Layout Design Graph Generation](https://mlsanity.com/paper/2406.17418/) (2024)
- [Enhancing Missing Data Imputation through Combined Bipartite Graph and Complete Directed Graph](https://mlsanity.com/paper/2411.04907/) (2024)
- [Graph Attention Networks Unleashed: A Fast and Explainable Vulnerability Assessment Framework for Microgrids](https://mlsanity.com/paper/2503.00786/) (2025)
- [Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networks](https://mlsanity.com/paper/2504.16360/) (2025)
- [A method for the systematic generation of graph XAI benchmarks via Weisfeiler-Leman coloring](https://mlsanity.com/paper/2505.12437/) (2025)
- [Chordless Structure: A Pathway to Simple and Expressive GNNs](https://mlsanity.com/paper/2505.19188/) (2025)
- [Topology-Assisted Spatio-Temporal Pattern Disentangling for Scalable MARL in Large-scale Autonomous Traffic Control](https://mlsanity.com/paper/2506.12453/) (2025)
- [PAC-Bayesian Generalization Bounds for Graph Convolutional Networks on Inductive Node Classification](https://mlsanity.com/paper/2509.06600/) (2025)
- [On The Expressive Power of GNN Derivatives](https://mlsanity.com/paper/2510.02565/) (2025)
- [Hyperbolic Heterogeneous Graph Transformer](https://mlsanity.com/paper/2601.08251/) (2026)
- [A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining](https://mlsanity.com/paper/2601.12751/) (2026)
- [Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks](https://mlsanity.com/paper/2605.00725/) (2026)
- [Polarity-Asymmetric Structural Calibration for Link Sign Prediction](https://mlsanity.com/paper/2609.05896/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) are effective machine learning models for many graph-related applications. Despite their empirical success, many research efforts focus on the theoretical limitations of GNNs, i.e., the GNNs expressive power. Early works in this domain mainly focus on studying the graph isomorphism recognition ability of GNNs, and recent works try to leverage the properties such as subgraph counting and connectivity learning to characterize the expressive power of GNNs, which are more practical and closer to real-world. However, no survey papers and open-source repositories comprehensively summarize and discuss models in this important direction. To fill the gap, we conduct a first survey for models for enhancing expressive power under different forms of definition. Concretely, the models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.