Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach
Li, Guoming Yang, Jian Liang, Shangsong Luo, Dongsheng
Li, Guoming
Yang, Jian
Liang, Shangsong
Luo, Dongsheng
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Spectral graph neural networks are proposed to harness spectral information inherent in graph-structured data through the application of polynomial-defined graph filters, recently achieving notable success in graph-based web applications. Existing studies reveal that various polynomial choices greatly impact spectral GNN performance, underscoring the importance of polynomial selection. However, this selection process remains a critical and unresolved challenge. Although prior work suggests a connection between the approximation capabilities of polynomials and the efficacy of spectral GNNs, there is a lack of theoretical insights into this relationship, rendering polynomial selection a largely heuristic process. To address the issue, this paper examines polynomial selection from an error-sum of function slices perspective. Inspired by the conventional signal decomposition, we represent graph filters as a sum of disjoint function slices. Building on this, we then bridge the polynomial capability and spectral GNN efficacy by proving that the construction error of graph convolution layer is bounded by the sum of polynomial approximation errors on function slices. This result leads us to develop an advanced filter based on trigonometric polynomials, a widely adopted option for approximating narrow signal slices. The proposed filter remains provable parameter efficiency, with a novel Taylor-based parameter decomposition that achieves streamlined, effective implementation. With this foundation, we propose TFGNN, a scalable spectral GNN operating in a decoupled paradigm. We validate the efficacy of TFGNN via benchmark node classification tasks, along with an example graph anomaly detection application to show its practical utility. © 2025 Copyright held by the owner/author(s).
Citation
G. Li, J. Yang, S. Liang, and D. Luo, “Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach,” WWW 2025 - Proceedings of the ACM Web Conference, pp. 3276–3287, Apr. 2025, doi: 10.1145/3696410.3714760
Source
WWW 2025 - Proceedings of the ACM Web Conference
Conference
34th ACM Web Conference, WWW 2025
Keywords
Node classification, Polynomial approximation, Polynomial graph filters, Spectral graph neural networks
Subjects
Source
34th ACM Web Conference, WWW 2025
Publisher
Association for Computing Machinery