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

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jan 2025.

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

- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [High-Order Matching for One-Step Shortcut Diffusion Models](https://mlsanity.com/paper/2502.00688/) (2025)
- [On Computational Limits of FlowAR Models: Expressivity and Efficiency](https://mlsanity.com/paper/2502.16490/) (2025)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Models](https://mlsanity.com/paper/2505.04946/) (2025)
- [Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent](https://mlsanity.com/paper/2504.04702/) (2025)
- [Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria](https://mlsanity.com/paper/2508.07102/) (2025)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions](https://mlsanity.com/paper/2508.13214/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)

## Abstract (arXiv)

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. Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and polynomial precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism unless mathsfTC0 = mathsfNC1. These results reveal the intrinsic expressivity limitations of GNNs behind their empirical success and introduce a novel framework for analyzing GNN expressiveness that can be extended to a broader range of GNN models and graph decision problems.