提出新型谱图神经网络，提升对复杂图结构的建模能力。
Full-Spectrum Graph Neural Networks: Expressive and Scalable
- 将节点信号扩展到节点对域，使用双变量谱滤波增强表达力。
- 可通用逼近节点对信号，在异质图任务中表现更优。
- 支持大规模图计算，适合处理真实世界复杂网络数据。
经典谱图神经网络虽能普遍逼近节点信号，但其表达能力受限于一维Weisfeiler-Lehman测试，无法有效处理高阶信号。为此，本文提出全谱图神经网络（FSpecGNN），作为经典谱GNN的二阶推广。FSpecGNN从两个方向推进谱滤波：一是将信号从节点域提升至节点对域；二是将单变量特征值滤波扩展为双变量特征值对滤波。我们证明经典谱GNN是FSpecGNN的对角特例，并理论表明其表达力最多与局部2-阶图神经网络相当，但能普遍逼近节点对信号，这对异质图学习尤为有益。此外，FSpecGNN具备可扩展实现，避免显式节点对计算；结合低秩近似将全谱卷积降为多项式谱滤波组合，使其适用于大规模图。实验验证了预测的表达力，且在异质图基准上表现强劲。
原文摘要 · Abstract (English)
It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored in their lack of universality for higher-order signals. To go beyond this bound, we propose the Full-Spectrum GNNs (FSpecGNNs), a second-order generalization of classical spectral GNNs. FSpecGNN advances spectral filtering from two perspectives: (1) it lifts signals from the node domain to the node-pair domain; and (2) it extends the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. We show that classical spectral GNNs arise as a diagonal special case of FSpecGNNs, and prove that FSpecGNNs can be at most as expressive as Local 2-GNN while universally approximating node-pair signals, the latter being particularly beneficial for heterophilic graph learning. Moreover, FSpecGNN admits scalable implementations that avoid explicit node-pair-level computations; combined with a low-rank approximation that reduces full-spectrum convolution to a combination of polynomial spectral filters, it enables learning on large graphs. Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。