Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach
Li, Guoming
Li, Guoming
Author
Supervisor
Department
Machine Learning
Embargo End Date
2026-05-30
Type
Thesis
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Spectral graph neural networks (GNNs) leverage the intrinsic spectral properties of graph-structured data by applying polynomial-based graph filters, achieving notable success in various graph-based web applications. However, recent studies have revealed that the performance of spectral GNNs is highly sensitive to the choice of polynomial, making polynomial selection a critical yet unresolved challenge. While previous work has suggested a link between the approximation capabilities of different polynomials and the overall efficacy of spectral GNNs, the theoretical basis for this relationship has remained underexplored, resulting in a selection process that is predominantly heuristic. This thesis addresses the challenge by reexamining polynomial selection from the perspective of an errorsum over disjoint function slices. Inspired by traditional signal decomposition techniques, we conceptualize graph filters as a sum of distinct function slices, each capturing a specific frequency band of the graph signal. Under this framework, we derive a rigorous theoretical relationship that connects the polynomial approximation error on each function slice to the overall construction error of a graph convolution layer. Specifically, we prove that the total error incurred in constructing the convolutional layer is bounded by the sum of the approximation errors over these function slices, thus providing a clear and quantifiable measure for assessing polynomial suitability. Motivated by this theoretical insight, we develop an advanced filtering strategy based on trigonometric polynomials, which are wellsuited for approximating narrow signal slices due to their favorable convergence properties. Complementing this, we introduce a novel Taylor-based parameter decomposition method that not only enhances the parameter efficiency of the proposed filter but also streamlines its implementation. Building on these advancements, we propose TFGNN - a scalable spectral GNN operating under a decoupled paradigm that separates filter design from graph convolution operations. We validate the performance of TFGNN through comprehensive experiments on benchmark node classification tasks and demonstrate its practical utility via a graph anomaly detection case study. The experimental results corroborate our theoretical findings and highlight the potential of our approach to significantly improve the robustness and effectiveness of spectral GNNs in real-world applications.
Citation
Guoming Li, “Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach,” Master of Science thesis, Machine Learning, MBZUAI, 2025.
Source
Conference
Keywords
Graph neural networks, Polynomial approximation, Spectral graph theory, Graph signal processing, Vertex classification, Numerical analysis