揭示谱不变量GNN在计数特定树状图时的精确表达能力
Homomorphism Expressivity of Spectral Invariant Graph Neural Networks
- 基于同态表达性分析谱不变量GNN的理论性能
- 可精确计数一类称为并行树的特殊树状图
- 为GNN深度与结构设计提供定量依据，适合理论研究者
图谱是图结构中一类重要特征，在增强图神经网络（GNN）方面已展现出良好效果。尽管其应用广泛，但关于谱不变量——特别是其对GNN贡献的理论理解仍不完整。本文从同态表达性视角出发，对谱不变量GNN的表达能力进行系统且量化的分析。我们证明，谱不变量GNN能精确计数一类特定的树状图，称为并行树。该结果在多个方面具有重要意义：建立不同架构变体之间的表达力层次关系，揭示GNN深度的影响，并阐明谱不变量GNN的子图计数能力。特别地，本工作显著扩展了Arvind等（2024）的工作，解决了其遗留问题。最后，我们将分析推广至高阶GNN，并回答了Zhang等（2024）提出的一个开放问题。
原文摘要 · Abstract (English)
Graph spectra are an important class of structural features on graphs that have shown promising results in enhancing Graph Neural Networks (GNNs). Despite their widespread practical use, the theoretical understanding of the power of spectral invariants -- particularly their contribution to GNNs -- remains incomplete. In this paper, we address this fundamental question through the lens of homomorphism expressivity, providing a comprehensive and quantitative analysis of the expressive power of spectral invariants. Specifically, we prove that spectral invariant GNNs can homomorphism-count exactly a class of specific tree-like graphs which we refer to as parallel trees. We highlight the significance of this result in various contexts, including establishing a quantitative expressiveness hierarchy across different architectural variants, offering insights into the impact of GNN depth, and understanding the subgraph counting capabilities of spectral invariant GNNs. In particular, our results significantly extend Arvind et al. (2024) and settle their open questions. Finally, we generalize our analysis to higher-order GNNs and answer an open question raised by Zhang et al. (2024).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。