Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach
This work addresses a critical, unresolved problem in spectral GNNs for graph-based web applications, offering a theoretical foundation to replace heuristic polynomial selection, though it is incremental as it builds on existing spectral GNN frameworks.
The paper tackles the challenge of polynomial selection in spectral graph neural networks by analyzing it through an error-sum of function slices perspective, proving that graph convolution layer error is bounded by polynomial approximation errors, and introduces TFGNN, a scalable spectral GNN using trigonometric polynomials that achieves competitive performance in node classification tasks, such as improving accuracy by up to 3.2% on benchmark datasets.
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.