从电路复杂度看图神经网络的计算极限，揭示其理论瓶颈。
On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
- 用电路复杂度分析GNN，而非传统同构测试
- 在低深度、小嵌入下无法解决连通性等关键问题
- 为理解GNN能力边界提供新视角，适合理论研究者
图神经网络（GNN）已成为关系数据学习与推理的标准方法，依赖消息传递机制在图结构中迭代传播节点嵌入。尽管GNN在实践中取得显著成功，其理论局限仍是活跃研究方向。现有工作主要通过魏斯费勒-莱曼（WL）图同构测试刻画表达能力。本文提出全新视角：从电路复杂度出发分析GNN的计算限制。我们证明，在常数层深、线性或次线性嵌入维度、多项式精度约束下，除非 $\mathsf{TC}^0 = \mathsf{NC}^1$，否则GNN无法解决图连通性与图同构等核心问题。该结果揭示了GNN经验成功背后的内在表达力限制，并建立了可推广至更广泛GNN模型与图决策问题的新分析框架。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。