证明了谱图神经网络在简单谱图上仍不完整，提出新方法提升表达能力。
Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
- 用最大特征值重数分类图，构建谱图神经网络表达力层级
- 发现多数谱增强模型在特征值互异的图上仍无法区分非同构图
- 引入旋转等变网络改进谱表示，适合研究图神经网络理论的读者
谱特征广泛用于图神经网络（GNN）以增强其区分非同构图的能力。例如，图拉普拉斯特征向量常用于MPNN和图Transformer的位置编码。现有评估方法如k-WL同构测试和同态计数与图谱关联性弱，难以准确衡量谱增强型GNN（SGNN）的表达力。本文基于最大特征值重数的图分类范式，建立SGNN的表达力层次结构，并证明即使在特征值均不同的简单谱图上，许多SGNN仍不完整。为弥补此缺陷，我们将旋转等变神经网络适配至图谱场景，提出一种可证明提升复杂谱图表达力的方法。通过在MNIST超像素数据集上的图像分类实验及ZINC数据集中特征向量规范化的实证，验证了理论结论。
原文摘要 · Abstract (English)
Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One popular example is the usage of graph Laplacian eigenvectors for positional encoding in MPNNs and Graph Transformers. The expressive power of such Spectrally-enhanced GNNs (SGNNs) is usually evaluated via the k-WL graph isomorphism test hierarchy and homomorphism counting. Yet, these frameworks align poorly with the graph spectra, yielding limited insight into SGNNs' expressive power. We leverage a well-studied paradigm of classifying graphs by their largest eigenvalue multiplicity to introduce an expressivity hierarchy for SGNNs. We then prove that many SGNNs are incomplete even on graphs with distinct eigenvalues. To mitigate this deficiency, we adapt rotation equivariant neural networks to the graph spectra setting to propose a method to provably improve SGNNs' expressivity on simple spectrum graphs. We empirically verify our theoretical claims via an image classification experiment on the MNIST Superpixel dataset and eigenvector canonicalization on graphs from ZINC.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。