Theoretical Analysis of Spectral Graph Neural Networks

Abstract

Spectral Graph Neural Networks (GNNs) have demonstrated strong performance in graph node classification tasks, yet factors affecting their performance remains insufficiently understood. We provide theoretical analysis of factors affecting the performance of spectral GNNs in node classification task: the optimization process, the node distinguishability, and the generalization of spectral GNNs.

Optimizing spectral GNNs remains a critical challenge in the field. The underlying processes are not well understood. We investigate the inherent differences between graph convolution parameters and feature transformation parameters in spectral GNNs and their impact on the optimization landscape. Our analysis reveals that these differences contribute to a poorly conditioned problem, resulting in suboptimal performance. We introduce the concept of the block condition number of the Hessian matrix, which characterizes the difficulty of poorly conditioned problems in spectral GNN optimization. We then propose an asymmetric learning approach, dynamically preconditioning gradients during training to alleviate poorly conditioned problems. Theoretically, we demonstrate that asymmetric learning can facilitate optimization. Extensive experiments show that asymmetric learning consistently improves the performance of spectral GNNs for both heterophilic and homophilic graphs.

The node distinguishability of spectral GNNs are under explored. We analyze how the interplay between graph matrices and node features influences node distinguishability. We derive a theoretical lower bound of distinguishable nodes, proving that it is determined by two key factors: the number of distinct eigenvalues of the graph matrix and the nonzero frequency components of node features. Building on this, we propose SpecMat, an adaptive graph matrix generation module designed to generate graph matrices adapting to different tasks. SpecMat can be integrated with any spectral GNN architecture to enhance their node distinguishability. We prove that spectral GNNs augmented with SpecMat preserve permutation equivariance, ensuring that node embeddings remain invariant to node ordering. Extensive experiments validate the effectiveness of SpecMat.

The generalization properties of spectral GNNs also remain insufficiently understood. To advance the understanding of generalization of spectral GNNs in node classification task, we introduce a stability-based framework for transductive generalization in spectral GNNs. In particular, we derive a uniform transductive stability bound and provide an explicit analysis in a two-class setting, revealing how homophily and heterophily drive generalization. Our findings show that spectral GNNs generalize well on graphs with strong homophily or heterophily but struggle on graphs with weaker structural properties. We also identify conditions under which increasing the polynomial order may degrade generalization. Empirical evaluations corroborate these theoretical insights.

Uniform transductive stability fail to provide non-vacuous bounds due to the accumulation of perturbations during iterative training. To derive a non-vacuous generalization error bound, we introduces a novel PAC-Bayes framework specifically designed for spectral GNNs in node classification tasks. Firstly, we extend PAC-Bayes theory from its inductive setting to the transductive setting, capturing dependency between training and testing nodes on graph. Secondly, we propose a parameter-specific prior-posterior assignment method to take the distinction between graph convolution parameter \(\Theta\) and feature transformation parameter \(W\) into account. Then, we use a tailored PAC-Bayes optimization framework to minimize empirical loss and generalization error simultaneously. Extensive experiments on real-world graph datasets show that transductive PAC-Bayes bounds are much tighter than those derived from uniform transductive stability. Show more