On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929671584612352 |
|---|---|
| author | Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Wang, Wei Zhang, Jiahao |
| author_facet | Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Wang, Wei Zhang, Jiahao |
| contents | 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 $\mathsf{TC}^0 = \mathsf{NC}^1$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06444 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Wang, Wei Zhang, Jiahao Machine Learning Artificial Intelligence Computational Complexity 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 $\mathsf{TC}^0 = \mathsf{NC}^1$. 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. |
| title | On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective |
| topic | Machine Learning Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2501.06444 |