PaperlayerView exact revision on arXiv

Source-linked AI summary

Specformer: Spectral Graph Neural Networks Meet Transformers

Deyu Bo, Chuan Shi, Lele Wang, Renjie Liao

arXiv:2303.01028v1cs.LGcs.AIcs.SI

TL;DR

Existing spectral GNN filters often process eigenvalues independently or rely on fixed-order approximations, limiting their use of global spectral structure and flexibility. Specformer applies Transformer self-attention to the eigenvalue set and decodes learned representations with learnable bases for permutation-equivariant, non-local graph convolution. It better recovers synthetic spectral filters and outperforms state-of-the-art GNNs across real-world node- and graph-level tasks while learning meaningful spectrum patterns.

  • Problem

    Existing spectral filters are scalar-to-scalar and often based on fixed-order approximations, so they overlook global eigenvalue patterns and have limited expressiveness.

  • Method

    Specformer encodes all graph-Laplacian eigenvalues, applies spectral self-attention, and decodes the representations with learnable bases into permutation-equivariant non-local graph convolutions.

  • Results

    Specformer better recovers given spectral filters synthetically and outperforms state-of-the-art GNNs on real-world node- and graph-level benchmarks.

  • Takeaways & Limitations

    The results support learning graph spectra directly with neural networks as a promising approach for constructing powerful GNNs and meaningful spectrum patterns.

  • Takeaways & Limitations

    Specformer has a costly spectral decomposition with O(n^3) complexity, while its forward complexity includes quadratic terms in the number of nodes.

Abstract

from arXiv · show

Spectral graph neural networks (GNNs) learn graph representations via spectral-domain graph convolutions. However, most existing spectral graph filters are scalar-to-scalar functions, i.e., mapping a single eigenvalue to a single filtered value, thus ignoring the global pattern of the spectrum. Furthermore, these filters are often constructed based on some fixed-order polynomials, which have limited expressiveness and flexibility. To tackle these issues, we introduce Specformer, which effectively encodes the set of all eigenvalues and performs self-attention in the spectral domain, leading to a learnable set-to-set spectral filter. We also design a decoder with learnable bases to enable non-local graph convolution. Importantly, Specformer is equivariant to permutation. By stacking multiple Specformer layers, one can build a powerful spectral GNN. On synthetic datasets, we show that our Specformer can better recover ground-truth spectral filters than other spectral GNNs. Extensive experiments of both node-level and graph-level tasks on real-world graph datasets show that our Specformer outperforms state-of-the-art GNNs and learns meaningful spectrum patterns. Code and data are available at https://github.com/bdy9527/Specformer.

1 INTRODUCTION

Spectral GNNs are limited by scalar-to-scalar filters and fixed-order approximations that overlook global spectral structure and restrict expressiveness. Specformer addresses these limitations with Transformer-based set-to-set filtering, learnable bases, and permutation-equivariant non-local convolution, achieving stronger synthetic recovery and real-world benchmark performance.

  • Motivation: Existing spectral filters process each eigenvalue independently, potentially ignoring global spectrum information such as eigenvalue multiplicities.The algebraic multiplicity of eigenvalue 0 indicates the number of connected components, but scalar-to-scalar filters cannot capture this information.
  • Motivation: Fixed-order polynomial and wavelet approximations avoid costly spectral decomposition but can reduce expressiveness and limit graph representation learning.The passage identifies Chebyshev polynomials and graph wavelets as examples of truncated orthonormal bases.
  • Specformer: Specformer encodes eigenvalue magnitudes and uses self-attention to learn relative information across the full eigenvalue set.Eigenvalue encoding represents continuous spectral values, while self-attention models dependencies among them.
  • Specformer: Learnable bases combined by Specformer produce permutation-equivariant, non-local graph convolutions.The decoder constructs graph convolution operators from learned eigenvalue representations and a bank of learnable bases.
  • Results: Synthetic experiments show better recovery of given spectral filters, while real-world node- and graph-level benchmarks show stronger performance than state-of-the-art GNNs.The real-world experiments also report meaningful learned spectrum patterns.

2 RELATED WORK

Related work divides GNNs into spatial and spectral approaches, with spatial methods aggregating neighborhood information and spectral methods operating on graph-Laplacian spectra. Graph Transformers combine attention with graph processing but remain spatial models, while spectral methods commonly use polynomial approximations.

  • Spatial GNNs: Spatial GNNs use message passing to aggregate local neighborhood information and may learn long-range dependencies by stacking layers.The passage also associates deeper spatial models with over-smoothing and over-squashing.
  • Spectral GNNs: Spectral GNNs perform convolutions in the graph-Laplacian spectral domain.This family includes methods based on spectral representations and graph filtering.
  • Spectral GNNs: A common spectral-GNN subclass approximates arbitrary filters with orthogonal polynomial bases such as Monomial, Chebyshev, Bernstein, and Jacobi polynomials.These bases provide a recurring construction strategy for spectral filters.
  • Graph Transformer: Graph Transformers combine Transformer attention with graph processing, but they remain spatial GNNs despite their non-local self-attention.The related-work passage distinguishes their attention mechanism from spectral-domain convolution.

3 BACKGROUND

The background defines graph Fourier analysis through the eigendecomposition of the normalized Laplacian and uses spectral filters to transform graph signals. Transformer layers provide self-attention and feed-forward transformations over token representations.

  • Graph Signal Processing: For an undirected graph, the normalized Laplacian is real symmetric and decomposes as L = UΛU^⊤, with eigenvalues in [0, 2].The columns of U are eigenvectors and Λ contains the corresponding eigenvalues.
  • Graph Signal Processing: The graph Fourier transform maps a signal x to coefficients x̂ = U^⊤x, which a spectral filter scales before inverse transformation returns the filtered signal.The spatial-domain output is x̃ = UGθx̂.
  • Graph Signal Processing: Designing a powerful spectral filter is the central graph-signal-processing task because it determines how useful frequency information is exploited.The filtering operation is performed between the forward and inverse graph Fourier transforms.
  • Transformer: A Transformer layer combines multi-head self-attention with a token-wise feed-forward network.The attention module projects input representations into query, key, and value representations using learned matrices.

4 SPECFORMER

Specformer encodes all Laplacian eigenvalues with a Transformer, decodes learnable spectral bases, and uses them for non-local graph convolution. It is permutation equivariant and theoretically supports broader filter functions than scalar-to-scalar or fixed polynomial filters.

  • 4.1 EIGENVALUE ENCODING: Specformer encodes continuous eigenvalues with positional-style embeddings and Transformer self-attention to capture both frequency magnitudes and relative differences.Unlike spatial positional encoding, eigenvalue encoding represents continuous spectral values and preserves permutation equivariance.
  • 4.2 EIGENVALUE DECODING: The decoder produces multiple filtered eigenvalue sets from Transformer representations, then combines their reconstructed matrices into learnable spectral bases.Each attention head can generate a distinct filtered spectrum before an FFN combines the resulting bases.
  • 4.2 EIGENVALUE DECODING: Specformer replaces fixed polynomial bases with learnable bases whose combinations are learned rather than determined by polynomial recursions.The design can approximate polynomial bases while also learning eigenvalue-specific functions.
  • 4.3 GRAPH CONVOLUTION: The learned bases assign feature-specific graph Laplacian matrices, enabling stacked graph-convolution layers and inherently non-local information propagation.Dense eigenvectors allow the learned operator to construct fully connected graph interactions rather than restricting aggregation to local neighborhoods.
  • 4.4 KEY PROPERTIES COMPARED TO RELATED MODELS: Specformer is permutation equivariant and can approximate both univariate and multivariate continuous functions, extending scalar-to-scalar spectral filters.The multivariate capability lets it model functions of multiple eigenvalues, while permutation equivariance supports consistent node representations under graph relabeling.
  • 4.4 KEY PROPERTIES COMPARED TO RELATED MODELS: Specformer has O(n^3) precomputed spectral-decomposition complexity and forward complexity O(n^2(d + M) + nd(L + d)).Here n, M, L, and d denote nodes, filters, layers, and hidden dimension, respectively.

5 EXPERIMENTS

Experiments evaluate Specformer on synthetic filter recovery, node classification, graph-level tasks, ablations, and learned spectrum dependencies. Results show strong benchmark performance and meaningful frequency interactions, while model size should match task difficulty.

  • Specformer is evaluated on synthetic node regression, real-world node classification, graph-level datasets, ablations, and spectrum-dependency analyses.The experiments include synthetic and real-world graph datasets with node-level and graph-level tasks.
  • Graph-level tasks: Specformer outperforms state-of-the-art models on ZINC and MolPCBA without hand-crafted features or pre-defined polynomials.The authors interpret this as evidence that directly learning graph spectra with neural networks is promising for constructing powerful GNNs.
  • Ablation studies: Eigenvalue encoding matters more on Squirrel than Citeseer, while self-attention consistently improves performance by capturing dependencies among eigenvalues.The ablation compares encoder components on two node-level datasets.
  • Ablation studies: Large models overfit easy Citeseer tasks but outperform smaller models on difficult Squirrel and MolPCBA tasks.The results imply that model capacity should be selected according to task difficulty.
  • Spectrum analysis: Learned dependencies vary with filtering difficulty: low-pass filters use low-frequency information, whereas band-related filters strongly connect low and high frequencies to the medium band.The reported patterns are observed across synthetic, homophilic, and heterophilic datasets.

6 CONCLUSION

The conclusion presents Specformer as a Transformer-based set-to-set spectral filter with learnable bases. It captures eigenvalue magnitudes and dependencies, supports non-local graph convolution, and performs strongly across synthetic and real-world evaluations.

  • Specformer uses a Transformer and learnable bases to construct a set-to-set spectral filter.
  • Specformer captures eigenvalue magnitudes and relative dependencies in a permutation-equivariant fashion.
  • Specformer can perform non-local graph convolution and learns meaningful spectrum patterns across synthetic and real-world datasets.
  • The authors identify sparsifying Transformer self-attention as a future direction for improving Specformer efficiency.

A.2 DETAILED EXPERIMENTAL SETUP

The detailed setup specifies repeated dataset splits, optimizers, learning-rate scheduling, checkpoint selection, computing hardware, and hyperparameter tables for node- and graph-level experiments.

  • Data splitting: Penn94 uses five official splits, arXiv uses one time-based split with ten initializations, and other datasets use ten split-and-initialization runs.
  • Optimization: Node classification uses Adam, whereas graph-level tasks use AdamW with a linear warm-up followed by cosine decay.
  • Model selection: Node-level training runs for up to 2000 epochs with early stopping after 200 epochs without continuously decreasing validation loss; graph-level training has no early stopping.
  • Environment: Experiments run on Linux with an Intel Xeon Silver 4210 CPU and an NVIDIA GeForce RTX 3090 with 24GB memory.
  • Hyperparameters: Node-level and graph-level hyperparameters are reported separately in Tables 7 and 8.

B IMPLEMENTATION DETAILS

This section describes implementation details for edge features, attention condensation, encoding experiments, and computational overhead. It reports that Specformer’s forward time is competitive with polynomial GNNs, while its dense eigenvectors increase space use.

  • Specformer incorporates edge features by broadcasting node features to edges, filtering mixed edge features, and aggregating them into new node features.
  • Condensation of self-attention: The condensation computes frequency-band column sums of self-attention and then averages rows to approximately preserve row normalization and reveal band dependencies.
  • Eigenvalue encoding: Eigenvalue encoding resolution increases as ϵ grows; with ϵ = 1, only the first 20 of 64 dimensions distinguish sampled eigenvalues.
  • Time overhead: Specformer’s forward time is close to GPR-GNN and below BernNet because it computes Udiag(λ)U ⊤X once rather than recurrently multiplying AX or LX.
  • Complexity: Truncated spectral decomposition reduces Penn94 forward complexity from O(n2(d + M) + nd(L + d)) to O(q2(d + M) + nd(L + d)).
  • Space overhead: Specformer has higher space overhead than polynomial GNNs because of dense eigenvectors, although using fewer eigenvectors can reduce the cost.

C.3 SPATIAL PERSPECTIVE OF SYNTHETIC DATA

The spatial comparison evaluates images filtered by Specformer and GPR-GNN against raw and ground-truth filtered images. Specformer more closely matches the ground truth, while GPR-GNN produces darker contrast.

  • Specformer’s filtered images are similar to the ground truth produced by the Comb filter |sin(πλ)|.
  • GPR-GNN’s darker contrast than the ground truth indicates weaker capture of the global information represented in the synthetic filtering pattern.

C.4 EXPERIMENTS ON LARGE-SCALE MOLECULAR DATASETS.

On the large-scale PCQM4Mv2 molecular regression dataset, Specformer-Medium uses one Transformer block and relatively few parameters. It nevertheless performs better than similarly sized baselines.

  • PCQM4Mv2 contains 3.7M graphs and evaluates regression of the HOMO-LUMO gap.
  • Specformer-Medium has relatively few parameters because its learnable bases are shared, with only one Transformer block.
  • Specformer-Medium performs better than similarly parameterized GCN, GIN, and GPS-small baselines.

D THEORETICAL RESULTS

The theoretical results establish permutation equivariance and universal approximation properties for Specformer. Its eigenvalue encoding can approximate continuous univariate functions, while the architecture extends this capability to multivariate functions.

  • Permutation equivariance: Specformer is permutation equivariant because its element-wise functions, self-attention, and learnable-basis construction each preserve permutation transformations.
  • Permutation equivariance: The self-attention mechanism is permutation equivariant because permuting representations transforms their similarity matrix by the same permutation.
  • Multivariate approximation: The multivariate result follows by combining eigenvalue encoding for continuous univariate functions with continuous outer functions represented by deep ReLU networks.
  • Approximation properties: Specformer can approximate any univariate and multivariate continuous functions.
  • Univariate approximation: With identity self-attention, eigenvalue encoding becomes a Fourier series and can approximate continuous univariate functions on [0, 2].
Loading 2303.01028v1…