PaperlayerView exact revision on arXiv

Source-linked AI summary

How Powerful are Spectral Graph Neural Networks

Xiyuan Wang, Muhan Zhang

arXiv:2205.11172v2cs.LGcs.AI

TL;DR

The paper studies the under-researched expressive power of spectral GNNs and differences among spectral-filter bases. It proves universality for linear spectral GNNs under mild conditions, analyzes optimization, and proposes JacobiConv, which outperforms baselines without nonlinearity.

  • Problem

    The expressive power of spectral GNNs and the advantages and disadvantages of their different spectral-filter bases remain insufficiently studied.

  • Method

    The paper analyzes linear spectral GNN universality, its connection to Graph Isomorphism testing, and basis-dependent optimization, then proposes JacobiConv with Jacobi filters and Polynomial Coefficient Decomposition.

  • Results

    JacobiConv outperforms BernNet by up to 12% on real-world datasets without nonlinearity, verifying the paper’s theory.

  • Takeaways & Limitations

    Linear spectral GNNs can reach high expressiveness without nonlinearity under mild conditions, while an appropriate orthogonal basis can improve convergence speed.

  • Takeaways & Limitations

    The optimization analysis assumes convergence to a global minimum, and bias does not complete frequency components missing from the original node features.

Abstract

from arXiv · show

Spectral Graph Neural Network is a kind of Graph Neural Network (GNN) based on graph signal filters. Some models able to learn arbitrary spectral filters have emerged recently. However, few works analyze the expressive power of spectral GNNs. This paper studies spectral GNNs' expressive power theoretically. We first prove that even spectral GNNs without nonlinearity can produce arbitrary graph signals and give two conditions for reaching universality. They are: 1) no multiple eigenvalues of graph Laplacian, and 2) no missing frequency components in node features. We also establish a connection between the expressive power of spectral GNNs and Graph Isomorphism (GI) testing, the latter of which is often used to characterize spatial GNNs' expressive power. Moreover, we study the difference in empirical performance among different spectral GNNs with the same expressive power from an optimization perspective, and motivate the use of an orthogonal basis whose weight function corresponds to the graph signal density in the spectrum. Inspired by the analysis, we propose JacobiConv, which uses Jacobi basis due to its orthogonality and flexibility to adapt to a wide range of weight functions. JacobiConv deserts nonlinearity while outperforming all baselines on both synthetic and real-world datasets.

1. Introduction

This paper addresses the under-researched expressive power of spectral GNNs and differences among their spectral-filter bases. It proves that linear spectral GNNs can be universal, analyzes optimization, and proposes JacobiConv.

  • Spectral GNNs’ expressive power and the advantages and disadvantages of different spectral-filter bases remain under-researched.
  • Existing spectral GNNs transform node signals, apply polynomial filters of the normalized Laplacian, and then apply another MLP.Learned polynomial coefficients can simulate low-pass, band-pass, and high-pass filters.
  • Linear spectral GNNs can produce arbitrary predictions under mild conditions, without relying on MLPs or nonlinearity.The paper also connects their universality conditions with Graph Isomorphism testing.
  • Different polynomial bases can have the same expressive power but different empirical performance, motivating optimization analysis through the Hessian near a global minimum.An orthogonal basis weighted by graph-signal spectral density can maximize convergence speed.
  • JacobiConv removes nonlinearity, uses a flexible Jacobi basis, and adds Polynomial Coefficient Decomposition to improve filter-coefficient optimization.Its weight-function flexibility supports adaptation to a wide range of graph-signal densities.
  • JacobiConv achieves the lowest synthetic filter-learning loss and outperforms all baselines on ten real-world datasets by up to 12%.

2. Preliminaries

The preliminaries define graph spectral representations, spectral filters, and expressiveness classes. They then specialize to linear GNNs and establish their relationship to general spectral GNNs.

  • The preliminaries define matrix condition numbers using the magnitudes of minimum and maximum eigenvalues, with singular matrices assigned infinite condition number.
  • The normalized Laplacian is eigendecomposed as ˆL = UΛU^T, with U containing eigenvectors and Λ containing eigenvalues.
  • The graph Fourier transform is ˜X = U^T X, and each eigenvector column of U is a frequency component associated with an eigenvalue.A frequency component is missing when its transformed signal coefficient is zero.
  • Spectral filtering scales each frequency component by applying a function g to the Laplacian eigenvalues, typically parameterized as a degree-K polynomial.
  • Spectral GNNs generally combine input and output functions with a polynomial spectral filter; PFME models express all polynomial filters, while FME models express arbitrary real-valued filters.
  • A linear GNN has the form Z = g(ˆL)XW, where g is a learnable polynomial and W is a learnable feature-to-output matrix.
  • Linear GNNs provide a lower bound on general spectral GNN expressiveness and can differentiate every node pair that linear GNNs can differentiate.
  • The analysis assumes fixed graphs, fixed node features, node-property prediction, and sufficiently high-degree polynomial filters.On a fixed graph, interpolation allows polynomial filters to reproduce arbitrary filter outputs at the discrete eigenvalues.

3. Related Work

Related work covers fixed- and learnable-filter spectral GNNs, linear graph models motivated by scalability, and the Weisfeiler–Lehman framework for characterizing node and graph distinguishability.

  • Spectral GNNs include fixed-filter models such as APPNP and GNN-LF/HF, alongside learnable-filter models such as ChebyNet.
  • Prior linear GNNs precompute graph propagations or use PPR, heat kernels, and random walks, mainly to improve scalability with restricted filters.
  • This paper differs by analyzing the expressive power and optimization properties of linear GNNs with arbitrary polynomial filters.
  • The 1-WL test iteratively aggregates neighborhood labels and is used to assess whether nodes or graphs can be distinguished.Isomorphic nodes receive the same label, while most non-isomorphic graphs can be distinguished.

4. Expressive Power of Linear GNNs

Linear spectral GNNs can be universal without nonlinearities when predictions are one-dimensional, the Laplacian has no repeated eigenvalues, and node features contain every frequency component. Their expressivity is linked to 1-WL and graph symmetries, while multidimensional outputs require separate filters per channel.

  • Linear GNNs can produce any one-dimensional prediction when the normalized Laplacian has no multiple eigenvalues and node features contain all frequency components.
  • The three expressivity bottlenecks are one-dimensional prediction, repeated Laplacian eigenvalues, and missing frequency components.
  • 4.1. Multidimensional Prediction: Different output channels may require different polynomial filters, so a shared filter cannot realize simultaneous low-pass and high-pass predictions.
  • 4.1. Multidimensional Prediction: If node features are not full-row-rank, linear GNNs cannot produce some multidimensional predictions for any output dimension k > 1.
  • 4.2–4.3. Spectral Bottlenecks: Missing frequency components cannot appear in filtered outputs, while repeated eigenvalues force equal scaling for components sharing an eigenvalue.
  • 4.4. Connection to Graph Isomorphism: Under the two universality conditions, 1-WL differentiates all non-isomorphic nodes, and the graph has no automorphism beyond the identity-related low-order cases.
  • 4.5. Role of Nonlinearity: Nonlinearities can mix frequency components, but the paper omits them experimentally because real-world datasets largely satisfy the universality conditions.

5. Choice of Basis for Polynomial Filters

Complete polynomial bases have equal expressive power but differ in optimization behavior. The analysis favors orthogonal bases matched to graph-signal density, motivating Jacobi polynomials because they flexibly adapt weight functions.

  • All complete polynomial bases have the same expressive power, but their empirical performance differs.
  • 5.1. Hessian Matrix and Polynomial Basis: The analysis studies convergence near a global minimum under squared loss, focusing on the Hessian condition number for polynomial coefficients.
  • 5.1. Hessian Matrix and Polynomial Basis: The Hessian condition number is minimized when the polynomial basis is orthonormal under a weight function matching graph-signal density.
  • 5.2. Jacobi Polynomial Basis: The exact signal-density weight function is difficult to compute efficiently on large graphs, motivating orthogonal polynomials with flexible weight functions.
  • 5.3. A Discussion on Popular Filter Bases: The Monomial basis is not orthogonal under any valid inner-product weight function.
  • 5.2. Jacobi Polynomial Basis: The Jacobi basis is more general than Chebyshev because it can adapt to a wide range of weight functions.
  • 5.3. A Discussion on Popular Filter Bases: Jacobi outperforms Bernstein when its weight function approximates the data distribution, and experiments report better performance on synthetic and real-world datasets.

6. JacobiConv Architecture

JacobiConv first linearly transforms node features, then applies multiple learned filters using Jacobi bases. It also uses recursion for efficient computation and polynomial coefficient decomposition to improve optimization.

  • JacobiConv linearly transforms node features before filtering and uses multiple filter functions, Jacobi bases, and polynomial coefficient decomposition.
  • Each output dimension receives an individual filter function, reflecting the need for channel-specific spectral filtering.
  • Jacobi-basis recursion computes all bases in O(K) time with K message-passing operations.
  • Polynomial Coefficient Decomposition factorizes coefficients into channel-dependent terms and shared bounded factors to address differing coefficient magnitudes.

7. Experiment

Experiments evaluate JacobiConv on synthetic filter-learning tasks, real-world node classification, basis choices, ablations, and resource use. Across these settings, its orthogonal, adaptable basis supports strong performance without nonlinearity while reducing parameter counts.

  • 7.1. Evaluating Models on Learning Filters: JacobiConv achieves the lowest loss among state-of-the-art spectral GNNs on synthetic filter-learning datasets.The comparison covers models that can all learn arbitrary polynomial filters.
  • 7.3. Ablation Analysis: Jacobi basis outperforms every other tested basis on all synthetic datasets and achieves 10 times lower loss than any other basis.Bernstein also improves over Monomial on all datasets.
  • 7.3. Ablation Analysis: Jacobi basis outperforms other bases by more than 0.8% on average in the real-world ablation study.The comparison removes PCD to account for differences in coefficient distributions.
  • 7.3. Ablation Analysis: Nonlinear variants reduce performance relative to JacobiConv, with NL losing 6% on average while NL-Res outperforms NL by 2%.The results support sufficient expressiveness from the linear model; the authors attribute the nonlinear loss partly to overfitting from extra parameters.
  • 7.4. Scalability: JacobiConv uses about 10% as many parameters as comparable-depth baselines while retaining time complexity O(Kmd).It has similar computational overhead to other baselines, though it takes more time than APPNP and GPRGNN because of more complex bases.

8. Conclusion

The paper establishes the expressive power of spectral GNNs, showing that linear spectral GNNs can produce arbitrary signals under appropriate conditions and connecting their behavior to graph isomorphism testing.

  • 8. Conclusion: Under distinct Laplacian eigenvalues and nonzero transformed node-feature rows, a linear GNN can produce any one-dimensional prediction.The proof constructs a polynomial spectral filter by solving a nonsingular Vandermonde system.
  • 8. Conclusion: For multidimensional outputs, linear GNNs cannot express targets whose transformed rows require differing values across output dimensions in certain dependent feature rows.The limitation follows from the resulting requirement that all transformed output columns be equal.

B.3. Proof of Proposition 4.3 and Corollary 4.4

The proof connects linear spectral GNN predictions to K + 1-layer GNNs and establishes their relationship with Weisfeiler–Lehman node distinguishability. It also derives polynomial-degree and approximation consequences for realizing graph signals.

  • Proof of Proposition 4.3: A K-degree polynomial filter can be formulated as a K + 1-layer GNN, linking linear spectral GNNs to the standard GNN framework.The construction uses layerwise COMBINE and AGGREGATE functions.
  • Proof of Proposition 4.3: If two nodes share the same (K + 1)-step WL label, the linear GNN produces the same output for them.This follows from the correspondence between the final GNN layer and the linear spectral GNN output.
  • Corollary 4.4: Linear GNNs can distinguish any pair of non-isomorphic nodes, implying that 1-WL can also differentiate those nodes.The passage states this as the conclusion of Corollary 4.4.
  • Proof of Proposition 4.3: For graphs without repeated normalized-Laplacian eigenvalues, every graph automorphism has order 1 or 2.The proof uses the one-dimensionality of eigenspaces associated with distinct eigenvalues.
  • Proof of Proposition 4.3: When the Laplacian has no repeated eigenvalues and every frequency component is present in the node features, the relevant permutation matrix must be the identity.Under these conditions, the spectral-domain relation forces D = I and hence P = I.
  • Polynomial construction: With Gaussian features, the transformed features remain Gaussian, and arbitrary target signals can be produced with probability 1 under the stated construction.The argument handles repeated eigenvalues by constructing the corresponding frequency blocks before producing the remaining rows.
  • Polynomial construction: The expected polynomial degree needed to realize the constructed filter is O(n), while approximation error depends on both polynomial degree and filter smoothness.Polynomial approximation bounds are then translated into a squared-loss bound for linear GNNs.

D. Random Feature. Why? Why not?

Random features eliminate missing frequency components with probability 1 and can address repeated eigenvalues, but their required polynomial degree can make them impractical on large graphs. The section also shows that bias alone cannot always restore missing components.

  • Why random features?: Random features have Gaussian graph-Fourier coefficients, so the probability that any frequency component is missing is 0.The graph Fourier transform preserves the isotropic Gaussian distribution.
  • Why random features?: Concatenating random features with node features removes missing frequency components and helps address the multiple-eigenvalue problem.Theorem D.2 states that sufficiently dimensional Gaussian random features enable arbitrary no-missing-frequency predictions with probability 1.
  • Why not random features?: O(n)-degree polynomials are required when Gaussian random features predict a nonzero target under the proposition’s assumptions.The target’s frequency coefficients may themselves be expressible by an O(1)-degree polynomial.
  • Why not random features?: Constant-degree polynomials, such as degree 10 in the experiments, cannot afford the O(n)-degree requirement on large real-world graphs.The paper identifies the resulting time and memory cost as a reason random features often worsen performance.
  • Empirical verification: Learnable random features perform much better than fixed random features and outperform JacobiConv on two datasets.The comparison suggests that node features may contain little useful information in some datasets.
  • Why not bias?: Adding a bias may introduce new frequency components, but there are graphs and feature matrices for which every bias and linear transformation still leave some components missing.The counterexample uses two isolated nodes to force a zero transformed component.
  • Optimization perspective: As the number of samples grows, the polynomial-regression Gram-matrix condition number equals the condition number of the linear GNN Hessian.This connects basis conditioning in polynomial regression with optimization conditioning for linear GNNs.

H. Experimental Settings

The experiments use controlled hyperparameter searches and Adam optimization across synthetic and real-world settings. JacobiConv outperforms the other tested bases, while PCD provides little additional benefit on synthetic data.

  • Baselines: JacobiConv and linear GNNs with alternative bases use fewer parameters than the reported baselines.Linear GNN parameter counts are fixed by the node-feature and output dimensions.
  • Synthetic datasets: Synthetic-dataset hyperparameters are selected by random search to minimize average loss over 50 images.Learning rates, weight decay, PCD parameters, and Jacobi-basis parameters are searched over specified ranges.
  • Real-world datasets: Real-world hyperparameters are selected to optimize validation accuracy, including separate dropout probabilities for X and XW.Other parameters are searched using the same general procedure as for the synthetic datasets.
  • Training process: Training uses Adam with at most 1000 forward and backward processes, plus early stopping after 200 epochs without validation improvement on real-world datasets.The early-stopping rule is applied to real-world validation scores.
  • Results: JacobiConv outperforms all other bases, while models with and without PCD show little performance difference on the synthetic datasets.The paper attributes PCD’s limited effect possibly to convergence to a global minimum under squared loss.

J. Analysis Using Gradient Flow

The paper analyzes linear spectral GNN optimization using gradient flow and proves convergence to a global minimum under mild conditions. Empirically, Jacobi basis achieves lower loss and faster convergence than most compared bases, while JacobiConv outperforms its FullCoef variant on 9 of 10 datasets.

  • J. Analysis Using Gradient Flow: Gradient flow analyzes whether linear spectral GNNs converge to a global minimum of the loss function.The method uses gradient descent with infinitesimal steps.
  • J. Analysis Using Gradient Flow: Linear GNNs always converge to the global minimum for squared loss when each σ_l > 0.The condition uses the minimum eigenvalue of M^(l) + S^(l).
  • J. Analysis Using Gradient Flow: The analysis guarantees linear convergence to a global minimum for graphs with σ_min > 0.Here σ_min is defined as min_l σ_l.
  • Empirical Basis Comparison: Jacobi basis achieves the lowest loss and higher convergence rate than Monomial and Chebyshev bases on all five datasets.Bernstein converges quickly in the first few epochs but Jacobi becomes faster after approaching the local minimum.
  • M. FullCoef vs JacobiConv: JacobiConv outperforms FullCoef JacobiConv on 9 out of 10 datasets, while FullCoef's additional expressive power is minor.FullCoef assigns filter functions to each input-output dimension pair and adds parameters that may worsen generalization.
Loading 2205.11172v2…