Full-Spectrum Graph Neural Networks: Expressive and Scalable

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, FSpecGNNs admit 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, FSpecGNNs validate the predicted expressivity on substructure-counting benchmarks and delivers strong performance on heterophilic benchmarks. Our code is available at https://github.com/xwangxshi/FSpecGNN.

Many AI systems work with network data, such as users linked by interactions or molecules made of connected atoms. A common kind of graph neural network studies a graph through its “frequencies,” a way of breaking the network into broad and fine-grained connection patterns. These models are good at processing information attached to individual nodes, but they miss important patterns involving pairs of nodes, especially when connected nodes often belong to different groups rather than the same group. We propose Full-Spectrum Graph Neural Network (FSpecGNN), which lets the model reason about pairs of nodes while still using the graph’s frequency patterns. Instead of adjusting one frequency at a time, FSpecGNN can combine pairs of frequencies, giving it a richer view of how information should move through the network. We also show how to implement this idea efficiently. This makes spectral graph neural networks more expressive while keeping them practical for larger graphs. In experiments, the method performs strongly on challenging graphs where neighborhood similarity is a poor assumption.