2025

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective

Li, Xiaoyu, Liang, Yingyu, Shi, Zhenmei et al.

Understand

Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data, leveraging the message-passing mechanism that iteratively propagates node embeddings through graph structures.

While GNNs have achieved significant empirical success, their theoretical limitations remain an active area of research.
Existing studies primarily focus on characterizing GNN expressiveness through Weisfeiler-Lehman (WL) graph isomorphism tests.
In this paper, we take a fundamentally different approach by exploring the computational limitations of GNNs through the lens of circuit complexity.

Built on

A reduction of a graph to a canonical form and an algebra arising during this reduction
Andrei Leman and Boris Weisfeiler · 1968
Earlier work this paper cites.
On uniform circuit complexity
Walter L Ruzzo · 1981
Earlier work this paper cites.
A taxonomy of problems with fast parallel algorithms
Stephen A Cook · 1985
Earlier work this paper cites.
Problems complete for deterministic logarithmic space
Stephen A Cook and Pierre McKenzie · 1987
Earlier work this paper cites.
The complexity of graph connectivity
Avi Wigderson · 1992
Earlier work this paper cites.
Time, hardware, and uniformity
D Mix Barrington and Neil Immerman · 1994
Earlier work this paper cites.
Introduction to circuit complexity: a uniform approach
Heribert Vollmer · 1999
Earlier work this paper cites.
On the hardness of graph isomorphism
Jacobo Torán · 2004
Earlier work this paper cites.
Computational complexity: a modern approach
Sanjeev Arora and Boaz Barak · 2009
Earlier work this paper cites.
Introduction to Graph Theory
R.J. Wilson · 2010
Earlier work this paper cites.
Graph isomorphism in quasipolynomial time
László Babai · 2016
Earlier work this paper cites.
Neural message passing for quantum chemistry
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl · 2017
Earlier work this paper cites.
Inductive representation learning on large graphs
Will Hamilton, Zhitao Ying, and Jure Leskovec · 2017
Earlier work this paper cites.
Semi-supervised classification with graph convolutional networks
Thomas N. Kipf and Max Welling · 2017
Earlier work this paper cites.
Graph attention networks
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio · 2018
Earlier work this paper cites.
How powerful are graph neural networks?
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka · 2018
Earlier work this paper cites.
Link prediction based on graph neural networks
Muhan Zhang and Yixin Chen · 2018
Earlier work this paper cites.
An end-to-end deep learning architecture for graph classification
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen · 2018
Earlier work this paper cites.
Graph neural networks for social recommendation
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin · 2019
Earlier work this paper cites.
Provably powerful graph networks
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman · 2019
Earlier work this paper cites.

Similar

Weisfeiler and leman go neural: Higher-order graph neural networks
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe · 2019
Cited alongside, same era.
Neural graph collaborative filtering
Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua · 2019
Cited alongside, same era.
Simplifying graph convolutional networks
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger · 2019
Cited alongside, same era.
Position-aware graph neural networks
Jiaxuan You, Rex Ying, and Jure Leskovec · 2019
Cited alongside, same era.
The logical expressiveness of graph neural networks
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva · 2020
Cited alongside, same era.
Generalization and representational limits of graph neural networks
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola · 2020
Cited alongside, same era.
The graph isomorphism problem
Martin Grohe and Pascal Schweitzer · 2020
Cited alongside, same era.
Lightgcn: Simplifying and powering graph convolution network for recommendation
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang · 2020
Cited alongside, same era.
Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings
Christopher Morris, Gaurav Rattan, and Petra Mutzel · 2020
Cited alongside, same era.
A survey on the expressive power of graph neural networks
Original
Ryoma Sato · 2020
Cited alongside, same era.
Analyzing the expressive power of graph neural networks in a spectral perspective
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine · 2021
Cited alongside, same era.
Reconstruction for powerful graph representations
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro · 2021
Cited alongside, same era.

Then

Saturated transformers are constant-depth threshold circuits
William Merrill, Ashish Sabharwal, and Noah A Smith · 2022
Later among the works it cites.
A theoretical comparison of graph neural network extensions
Pál András Papp and Roger Wattenhofer · 2022
Later among the works it cites.
Ordered subgraph aggregation networks
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris · 2022
Later among the works it cites.
A new perspective on ”how graph neural networks go beyond weisfeiler-lehman?”
Asiri Wijesinghe and Qing Wang · 2022
Later among the works it cites.
Molecular contrastive learning of representations via graph neural networks
Yuyang Wang, Jianren Wang, Zhonglin Cao, and Amir Barati Farimani · 2022
Later among the works it cites.
The expressive power of pooling in graph neural networks
Filippo Maria Bianchi and Veronica Lachi · 2023
Later among the works it cites.
Mamba: Linear-time sequence modeling with selective state spaces
Original
Albert Gu and Tri Dao · 2023
Later among the works it cites.
Transformers learn shortcuts to automata
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang · 2023
Later among the works it cites.
The parallelism tradeoff: Limitations of log-precision transformers
William Merrill and Ashish Sabharwal · 2023
Later among the works it cites.
A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang · 2023
Later among the works it cites.
Transformers in uniform 𝖳𝖢 0 \mathsf{TC}^{0}
Original
David Chiang · 2024
Later among the works it cites.
Circuit complexity bounds for rope-based transformer architecture
Original
Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, and Zhao Song · 2024
Later among the works it cites.
The computational limits of state-space models and mamba via the lens of circuit complexity
Original
Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song · 2024
Later among the works it cites.
Rethinking the expressiveness of gnns: A computational model perspective
Original
Guanyu Cui, Zhewei Wei, and Hsin-Hao Su · 2024
Later among the works it cites.
On the expressive power of modern hopfield networks
Original
Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, and Zhao Song · 2024
Later among the works it cites.
Theoretical constraints on the expressive power of rope-based tensor attention transformers
Original
Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Mingda Wan · 2024
Later among the works it cites.
A logic for expressing log-precision transformers
William Merrill and Ashish Sabharwal · 2024
Later among the works it cites.
Roformer: Enhanced transformer with rotary position embedding
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu · 2024
Later among the works it cites.
Beyond weisfeiler-lehman: A quantitative framework for GNN expressiveness
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang · 2024
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…