Back

Specformer: Spectral Graph Neural Networks Meet Transformers

Deyu BoChuan ShiLele WangRenjie Liao

article2023ICLR146 citations

Proposes Specformer, a spectral graph neural network that applies Transformer self-attention across the entire eigenvalue spectrum to learn flexible, set-to-set spectral filters for both node- and graph-level representation learning.

Listen

Graph neural networks are widely used to analyze complex, interconnected data across various domains. However, standard spectral approaches often rely on fixed, scalar-to-scalar approximations that treat each frequency individually, missing broader structural patterns in the graph's overall spectrum. Spatial approaches, on the other hand, frequently struggle with over-smoothing and failing to capture long-range global context.

The article introduces and evaluates Specformer, a model designed to overcome these limitations by applying an attention-based mechanism directly in the spectral domain. By treating the set of graph frequencies as a whole rather than evaluating each one in isolation, the architecture aims to learn more flexible, data-driven transformations capable of capturing both local and global graph structures.

To evaluate this architecture, the authors conducted controlled experiments across synthetic graph benchmarks, eight real-world node classification datasets covering diverse connectivity patterns, and four large-scale molecular graph datasets. The approach was benchmarked against traditional spatial models, fixed polynomial spectral baselines, and modern spatial graph attention methods.

The evaluation revealed several key findings:

  1. Synthetic filter recovery: Specformer accurately reconstructed complex target filters, such as sharp band-rejection and comb filters, where traditional polynomial methods consistently underperformed due to rigid basis constraints.
  2. Node classification performance: The model outperformed state-of-the-art baselines across seven out of eight real-world datasets, achieving a notable 12% relative accuracy gain on challenging heterophilic benchmarks where connected nodes have dissimilar labels.
  3. Molecule-level modeling: Specformer set top results on benchmark graph regression tasks such as ZINC and MolPCBA without relying on hand-crafted structural descriptors.
  4. Parameter and computational efficiency: Shared basis variants matched or exceeded competing models while maintaining smaller parameter footprints and avoiding out-of-memory errors on large graphs via truncated frequency decomposition.

These findings demonstrate that learning spectral patterns directly via set-to-set attention provides a mathematically expressive and practical middle ground between local spatial passing and rigid polynomial approximations. For organizations deploying graph-based systems, this capability enhances model accuracy on complex network topologies, such as financial fraud networks, biochemical interactions, and citation webs, while avoiding the excessive memory overhead common in spatial attention models.

Organizations evaluating this architecture should select model variants based on task complexity, as smaller models perform best on simple tasks while larger configurations are suited for complex molecular analysis. To scale cost-effectively to very large graphs, teams should implement truncated eigenvalue decomposition to manage computational overhead. Future work should focus on sparsifying spectral attention to further improve training speeds and exploring automated hyperparameter tuning for frequency truncation thresholds.

Beijing University of Posts and TelecommunicationsUniversity of British Columbiaencoder-decodergraph neural networksdirected graphsSpecformerspectral graph neural networksgraph Transformers
arXiv: 2303.01028bdy9527/Specformer
  • Paper: Benchmarking Graph Neural Networks, Vijay Prakash Dwivedi et al. (2023). Provides a standardized, multi-task benchmarking suite to rigorously evaluate and compare novel graph architectures like Specformer against established message-passing and attention baselines.
Cover for Specformer: Spectral Graph Neural Networks Meet Transformers

Abstract

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 this https URL.

Topics

encoder-decodergraph neural networksdirected graphsfrequency bandsnetwork architectureeigenvectorsspectral correlationtime frequency domain

Keywords

Specformerspectral graph neural networksgraph Transformersspectral attentiongraph signal processingspectral filtersspectral decompositiongraph convolutionsspatial GNNs

Table of Contents

  • 1 Introduction
  • 2 Related Work
  • 3 Background
  • 4 Specformer
  • 4.1 Eigenvalue Encoding
  • 4.2 Eigenvalue Decoding
  • 4.3 Graph Convolution
  • 4.4 Key Properties Compared to Related Models
  • 5 Experiments
  • 5.1 Learning Spectral Filters on Synthetic Data
  • 5.2 Node Classification
  • 5.3 Graph Classification and Regression
  • 5.4 Ablation Studies
  • 5.5 Visualizations
  • 6 Conclusion
  • References
  • A Experimental Details
  • A.1 Datasets
  • A.2 Detailed experimental setup
  • B Implementation Details
  • B.1 Specformer Layer
  • B.2 Condensation of self-attention
  • C More experimental results
  • C.1 Eigenvalue encoding
  • C.2 Time and space overhead
  • C.3 Spatial perspective of synthetic data
  • C.4 Experiments on large-scale molecular datasets.
  • D Theoretical results
  • D.1 Permutation equivariance
  • D.2 Approximating univariate and multivariate functions

Knowls

  1. Knowl 1 — Specformer Architecture and Set-to-Set Spectral Filtering Framework

    model/method

    Specformer is a spectral graph neural network architecture that models the entire graph Laplacian spectrum as a set, learning set-to-set spectral filters via self-attention rather than applying fixed scalar-to-scalar polynomial filters.

    Let an undirected graph be G=(V,E)G = (V, E) with ∣V∣=n|V| = n, adjacency matrix A∈{0,1}n×nA \in \{0, 1\}^{n \times n}, and degree matrix D=diag(D11,…,Dnn)D = \text{diag}(D_{11}, \dots, D_{nn}) where Dii=∑jAijD_{ii} = \sum_j A_{ij}. The normalized graph Laplacian is L=In−D−1/2AD−1/2∈Rn×nL = I_n - D^{-1/2} A D^{-1/2} \in \mathbb{R}^{n \times n}, with eigendecomposition L=UΛU⊤L = U \Lambda U^\top, where U∈Rn×nU \in \mathbb{R}^{n \times n} is an orthogonal matrix of eigenvectors and Λ=diag([λ1,…,λn])\Lambda = \text{diag}([\lambda_1, \dots, \lambda_n]) contains eigenvalues λi∈[0,2]\lambda_i \in [0, 2].

    The Specformer pipeline operates in four main stages:

    1. Eigenvalue Encoding: Each eigenvalue λi∈[0,2]\lambda_i \in [0, 2] is mapped to a continuous multi-scale vector ρ(λi)∈Rd\rho(\lambda_i) \in \mathbb{R}^d. The initial spectrum representation is Z=[λ1∥ρ(λ1),…,λn∥ρ(λn)]⊤∈Rn×(d+1)Z = [\lambda_1 \parallel \rho(\lambda_1), \dots, \lambda_n \parallel \rho(\lambda_n)]^\top \in \mathbb{R}^{n \times (d+1)}, where ∥\parallel denotes concatenation.

    2. Transformer Encoder: The token sequence ZZ is processed by stacked Transformer blocks using pre-layer normalization (Pre-LN): Z~=MHA(LN(Z))+Z\tilde{Z} = \text{MHA}(\text{LN}(Z)) + Z Z^=FFN(LN(Z~))+Z~\hat{Z} = \text{FFN}(\text{LN}(\tilde{Z})) + \tilde{Z} where MHA\text{MHA} is multi-head self-attention, LN\text{LN} is layer normalization, and FFN\text{FFN} is a token-wise feed-forward network.

    3. Eigenvalue Decoding and Learnable Bases: Multi-head attention outputs are transformed into MM distinct filtered eigenvalue sets λm∈Rn×1\lambda_m \in \mathbb{R}^{n \times 1}. The model reconstructs MM base matrices Sm=Udiag(λm)U⊤∈Rn×nS_m = U \text{diag}(\lambda_m) U^\top \in \mathbb{R}^{n \times n}, which are combined by a feed-forward network into a channel-specific basis tensor S^∈Rn×n×d\hat{S} \in \mathbb{R}^{n \times n \times d}.

    4. Non-Local Graph Convolution: Node feature representations X∈Rn×dX \in \mathbb{R}^{n \times d} are convolved channel-by-channel with the slices of S^\hat{S}.

  2. Knowl 2 — Continuous Eigenvalue Encoding with Frequency Scaling

    model/method

    To enable the self-attention mechanism in the Transformer encoder to distinguish eigenvalues within the bounded range [0,2][0, 2] of the normalized graph Laplacian, Specformer applies a continuous sinusoidal eigenvalue encoding function ρ(λ):R1→Rd\rho(\lambda): \mathbb{R}^1 \to \mathbb{R}^d:

    ρ(λ,2i)=sin⁡(ϵλ100002i/d)\rho(\lambda, 2i) = \sin\left(\frac{\epsilon \lambda}{10000^{2i/d}}\right) ρ(λ,2i+1)=cos⁡(ϵλ100002i/d)\rho(\lambda, 2i+1) = \cos\left(\frac{\epsilon \lambda}{10000^{2i/d}}\right)

    where i∈{0,1,…,d/2−1}i \in \{0, 1, \dots, d/2 - 1\} indexes the embedding dimension, dd is the representation dimension, and ϵ>0\epsilon > 0 is a scaling hyperparameter.

    Because eigenvalues λ\lambda lie in [0,2][0, 2], setting ϵ=1\epsilon = 1 causes the factor λ/100002i/d\lambda / 10000^{2i/d} to change negligibly for larger ii, leaving only the first few dimensions capable of separating eigenvalues. Setting ϵ\epsilon to larger values (e.g., 1010 or 100100) increases the frequency of the sinusoidal basis, yielding multi-scale wavelengths from 2π/ϵ2\pi / \epsilon to 10000⋅2π/ϵ10000 \cdot 2\pi / \epsilon.

    Unlike positional encodings that encode discrete spatial vertex indices (which violate graph permutation equivariance), the continuous eigenvalue encoding represents scalar frequency values in the spectral domain, preserving full permutation equivariance.

  3. Knowl 3 — Learnable Spectral Bases Decoding and Model Variants

    model/method

    Specformer decodes eigenvalue representations into a set of learnable spectral bases that are dynamically weighted across feature channels.

    From the Transformer encoder representations ZZ, the mm-th attention head computes head-specific representations Zm∈Rn×dvZ_m \in \mathbb{R}^{n \times d_v} and generates the mm-th filtered eigenvalue vector λm∈Rn×1\lambda_m \in \mathbb{R}^{n \times 1}:

    Zm=Attention(QWmQ,KWmK,VWmV),λm=ϕ(ZmWλ)Z_m = \text{Attention}(Q W_m^Q, K W_m^K, V W_m^V), \quad \lambda_m = \phi(Z_m W_\lambda)

    where WmQ,WmK,WmV∈Rd×dkW_m^Q, W_m^K, W_m^V \in \mathbb{R}^{d \times d_k} are projection matrices, Wλ∈Rdv×1W_\lambda \in \mathbb{R}^{d_v \times 1} is a linear mapping, and ϕ\phi is an optional non-linear activation (e.g., ReLU\text{ReLU} or Tanh\text{Tanh}).

    Using the Laplacian eigenvector matrix U∈Rn×nU \in \mathbb{R}^{n \times n}, MM individual basis matrices are formed and combined along the channel dimension by a feed-forward network FFN:RM+1→Rd\text{FFN}: \mathbb{R}^{M+1} \to \mathbb{R}^d:

    Sm=Udiag(λm)U⊤,S^=FFN([In∥S1∥⋯∥SM])∈Rn×n×dS_m = U \text{diag}(\lambda_m) U^\top, \quad \hat{S} = \text{FFN}([I_n \parallel S_1 \parallel \dots \parallel S_M]) \in \mathbb{R}^{n \times n \times d}

    where InI_n is the n×nn \times n identity matrix.

    Specformer provides three architectural configurations:

    • Specformer-Small: The basis tensor S^\hat{S} and the combining FFN\text{FFN} are shared across all graph convolutional layers.
    • Specformer-Medium: The base matrices S1,…,SMS_1, \dots, S_M are shared, but each graph convolutional layer ll applies a separate combination network: S^(l)=FFN(l)([In∥S1∥⋯∥SM])\hat{S}^{(l)} = \text{FFN}^{(l)}([I_n \parallel S_1 \parallel \dots \parallel S_M]).
    • Specformer-Large: Each convolutional layer ll employs an independent Transformer encoder, decoder, and combination network: S^(l)=FFN(l)([In∥S1(l)∥⋯∥SM(l)])\hat{S}^{(l)} = \text{FFN}^{(l)}([I_n \parallel S_1^{(l)} \parallel \dots \parallel S_M^{(l)}]).

  4. Knowl 4 — Spectral Graph Convolution and Edge Feature Integration

    model/method

    Specformer applies channel-specific non-local convolutions to update node representations. Let X(l−1)∈Rn×dX^{(l-1)} \in \mathbb{R}^{n \times d} denote the node representations at layer l−1l-1, and let S^∈Rn×n×d\hat{S} \in \mathbb{R}^{n \times n \times d} denote the learned 3D basis tensor.

    For each feature channel dimension i∈{1,…,d}i \in \{1, \dots, d\}, convolution is applied using the slice S^:,:,i∈Rn×n\hat{S}_{:,:,i} \in \mathbb{R}^{n \times n}:

    X^:,i(l−1)=S^:,:,iX:,i(l−1)\hat{X}_{:,i}^{(l-1)} = \hat{S}_{:,:,i} X_{:,i}^{(l-1)} X(l)=σ(X^(l−1)Wx(l−1))+X(l−1)X^{(l)} = \sigma\left(\hat{X}^{(l-1)} W_x^{(l-1)}\right) + X^{(l-1)}

    where Wx(l−1)∈Rd×dW_x^{(l-1)} \in \mathbb{R}^{d \times d} is a trainable weight matrix, σ\sigma is an activation function, and the residual connection is optional.

    When edge features E∈Rn×n×dE \in \mathbb{R}^{n \times n \times d} are present, node features H∈Rn×dH \in \mathbb{R}^{n \times d} are integrated with edge attributes as follows:

    Ebroad=H.unsqueeze(0)+EE_{\text{broad}} = H.\text{unsqueeze}(0) + E E^=S⊙Ebroad\hat{E} = S \odot E_{\text{broad}} H^=∑j=1nE^j,:,:\hat{H} = \sum_{j=1}^n \hat{E}_{j,:,:}

    where ⊙\odot is element-wise multiplication, and SS is the learned basis.

  5. Knowl 5 — Permutation Equivariance of Specformer

    theoretical result

    Let P∈{0,1}n×nP \in \{0, 1\}^{n \times n} be an arbitrary permutation matrix applied to the graph vertex set, transforming node features to X′=PXX' = P X, edge features to E′=PEP⊤E' = P E P^\top, and the Laplacian to L′=PLP⊤L' = P L P^\top with spectral decomposition L′=(PU)Λ(PU)⊤L' = (P U) \Lambda (P U)^\top.

    Specformer is permutation equivariant; that is, the learned node representations transform equivariantly under vertex permutation:

    1. Element-wise operations: Eigenvalue encoding ρ(λ)\rho(\lambda), feed-forward networks, and layer normalization act on individual tokens independently of vertex indexing.
    2. Self-attention mechanism: For representation matrix ZZ, permutation transforms the attention map as: (PZP⊤)(PZP⊤)⊤=P(ZZ⊤)P⊤(P Z P^\top)(P Z P^\top)^\top = P (Z Z^\top) P^\top
    3. Learnable basis construction: The basis matrix for each head transforms equivariantly: Sm′=(PUP⊤)(Pdiag(λm)P⊤)(PUP⊤)⊤=P(Udiag(λm)U⊤)P⊤=PSmP⊤S_m' = (P U P^\top)(P \text{diag}(\lambda_m) P^\top)(P U P^\top)^\top = P (U \text{diag}(\lambda_m) U^\top) P^\top = P S_m P^\top
    4. Convolution step: Each channel convolution satisfies S^:,:,i′X:,i′=(PS^:,:,iP⊤)(PX:,i)=P(S^:,:,iX:,i)\hat{S}_{:,:,i}' X_{:,i}' = (P \hat{S}_{:,:,i} P^\top)(P X_{:,i}) = P (\hat{S}_{:,:,i} X_{:,i}).

  6. Knowl 6 — Universal Approximation of Univariate and Multivariate Spectral Filters

    theoretical result

    Specformer is a universal approximator for both univariate and multivariate continuous spectral graph filters on the domain [0,2][0, 2].

    Univariate Approximation: When the self-attention matrix in the Transformer encoder is set to the identity matrix, Specformer reduces to a scalar-to-scalar spectral filter. Given a linear transformation vector w=[w0,w1,…,wd]⊤∈Rd+1w = [w_0, w_1, \dots, w_d]^\top \in \mathbb{R}^{d+1}, the eigenvalue encoding ρ(λ)\rho(\lambda) yields a Fourier series representation:

    ρ(λ)w=w0λ+∑i=1d/2w2isin⁡(ϵλ100002i/d)+∑i=1d/2w2i−1cos⁡(ϵλ100002i/d)\rho(\lambda) w = w_0 \lambda + \sum_{i=1}^{d/2} w_{2i} \sin\left(\frac{\epsilon \lambda}{10000^{2i/d}}\right) + \sum_{i=1}^{d/2} w_{2i-1} \cos\left(\frac{\epsilon \lambda}{10000^{2i/d}}\right)

    By the uniform convergence theorem of Fourier series, for any continuous function f(λ)f(\lambda) on [0,2][0, 2] with piecewise continuous derivative, and for any ϵ>0\epsilon > 0, there exists an eigenvalue encoding projection that converges uniformly to f(λ)f(\lambda) on [0,2][0, 2].

    Multivariate Approximation: By the Kolmogorov-Arnold representation theorem, any multivariate continuous function f(x1,…,xM)f(x_1, \dots, x_M) on [0,1]M[0, 1]^M can be decomposed as:

    f(x1,…,xM)=ρ(∑m=1Mλmϕ(xm))f(x_1, \dots, x_M) = \rho\left(\sum_{m=1}^M \lambda_m \phi(x_m)\right)

    where ϕ\phi is continuous and ρ\rho is an outer continuous function. In Specformer, the eigenvalue encoding represents the inner continuous functions ϕ\phi, the self-attention weights parameterize the coefficients λm\lambda_m, and deep ReLU feed-forward networks in the decoder approximate the continuous outer function ρ\rho. Specformer can therefore approximate any continuous multivariate spectral filter.

  7. Knowl 7 — Computational Complexity and Scalable Truncated Spectral Filtering

    model/method

    The computational workflow of Specformer separates into a one-time precomputation and a forward pass.

    Full Eigendecomposition Complexity:

    • Spectral Decomposition: Precomputed once offline with time complexity O(n3)O(n^3) for an nn-node graph.
    • Transformer Encoder: O(n2d+nd2)O(n^2 d + n d^2), where nn is the number of eigenvalues/nodes and dd is hidden dimension.
    • Learnable Bases Construction: O(Mn2)O(M n^2), where MM is the number of attention heads/filters.
    • Graph Convolution: O(Lnd)O(L n d) across LL layers.
    • Overall Forward Complexity: O(n2(d+M)+nd(L+d))O(n^2(d + M) + n d(L + d)).

    Truncated Spectral Approximation for Large Graphs: For large graphs where full eigendecomposition is prohibitive, Sparse Generalized Eigenvalue (SGE) algorithms extract the q≪nq \ll n most relevant eigenvalues and eigenvectors. The forward complexity is thereby reduced to:

    O(q2(d+M)+nd(L+d))O(q^2(d + M) + n d(L + d))

    For homophilic graphs, the qq smallest eigenvalues (low-frequency spectrum) are retained; for heterophilic graphs, a combination of the smallest (low-frequency) and largest (high-frequency) eigenvalues are retained (e.g., q=6000q = 6000 for Penn94 split equally between low and high frequencies; q=5000q = 5000 smallest eigenvalues for ogbn-arXiv).

  8. Knowl 8 — Node Classification Performance across Homophilic and Heterophilic Graphs

    data/table

    Specformer was evaluated on node classification benchmarks under a 60%/20%/20% train/val/test split across 10 independent runs, reporting mean classification accuracy (%) with 95% confidence intervals.

    Model Heterophilic Homophilic
    Chameleon Squirrel Actor Penn94 Cora Citeseer Photo arXiv
    GCN 59.61±\pm2.21 46.78±\pm0.87 33.23±\pm1.16 82.47±\pm0.27 87.14±\pm1.01 79.86±\pm0.67 88.26±\pm0.73 71.74±\pm0.29
    GAT 63.13±\pm1.93 44.49±\pm0.88 33.93±\pm2.47 81.53±\pm0.55 88.03±\pm0.79 80.52±\pm0.71 90.94±\pm0.68 71.82±\pm0.23
    H2GCN\text{H}_2\text{GCN} 57.11±\pm1.58 36.42±\pm1.89 35.86±\pm1.03 OOM 86.92±\pm1.37 77.07±\pm1.64 93.02±\pm0.91 OOM
    GCNII 63.44±\pm0.85 41.96±\pm1.02 36.89±\pm0.95 82.92±\pm0.59 88.46±\pm0.82 79.97±\pm0.65 89.94±\pm0.31 72.04±\pm0.19
    LanczosNet 64.81±\pm1.56 48.64±\pm1.77 38.16±\pm0.91 81.55±\pm0.26 87.77±\pm1.45 80.05±\pm1.65 93.21±\pm0.85 71.46±\pm0.39
    ChebyNet 59.28±\pm1.25 40.55±\pm0.42 37.61±\pm0.89 81.09±\pm0.33 86.67±\pm0.82 79.11±\pm0.75 93.77±\pm0.32 71.12±\pm0.22
    GPR-GNN 67.28±\pm1.09 50.15±\pm1.92 39.92±\pm0.67 81.38±\pm0.16 88.57±\pm0.69 80.12±\pm0.83 93.85±\pm0.28 71.78±\pm0.18
    BernNet 68.29±\pm1.58 51.35±\pm0.73 41.79±\pm1.01 82.47±\pm0.21 88.52±\pm0.95 80.09±\pm0.79 93.63±\pm0.35 71.96±\pm0.27
    ChebNetII 71.37±\pm1.01 57.72±\pm0.59 41.75±\pm1.07 83.12±\pm0.22 88.71±\pm0.93 80.53±\pm0.79 94.92±\pm0.33 72.32±\pm0.23
    JacobiConv 74.20±\pm1.03 57.38±\pm1.25 41.17±\pm0.64 83.35±\pm0.11 88.98±\pm0.46 80.78±\pm0.79 95.43±\pm0.23 72.14±\pm0.17
    Transformer 46.39±\pm1.97 31.90±\pm3.16 39.95±\pm1.64 OOM 71.83±\pm1.68 70.55±\pm1.20 90.05±\pm1.50 OOM
    Graphormer 54.49±\pm3.11 36.96±\pm1.75 38.45±\pm1.38 OOM 67.71±\pm0.78 73.30±\pm1.21 85.20±\pm4.12 OOM
    Specformer 74.72±\pm1.29 64.64±\pm0.81 41.93±\pm1.04 84.32±\pm0.32 88.57±\pm1.01 81.49±\pm0.94 95.48±\pm0.32 72.37±\pm0.18

    Specformer outperforms all spatial GNNs, polynomial spectral GNNs, and spatial Graph Transformers on 7 out of 8 benchmarks. Gains are most pronounced on heterophilic graphs, where Specformer achieves a 12.6% relative improvement over the best baseline on Squirrel (64.64% vs 57.38%). Standard spatial Graph Transformers encounter Out of Memory (OOM) errors on large graphs (Penn94 and arXiv), whereas Specformer scales via truncated spectral decomposition.

  9. Knowl 9 — Graph-Level Property Prediction on Benchmark Datasets

    data/table

    Specformer was evaluated on graph classification and regression across standard molecular benchmarks: ZINC (MAE, lower is better), MolHIV (AUROC, higher is better), and MolPCBA (Average Precision, higher is better).

    Model ZINC (↓\downarrow) MolHIV (↑\uparrow) MolPCBA (↑\uparrow)
    GCN 0.367 ±\pm 0.011 0.7599 ±\pm 0.0119 0.2424 ±\pm 0.0034
    GIN 0.526 ±\pm 0.051 0.7707 ±\pm 0.0149 0.2703 ±\pm 0.0023
    GatedGCN 0.090 ±\pm 0.001 - 0.267 ±\pm 0.002
    CIN 0.079 ±\pm 0.006 0.8094 ±\pm 0.0057 -
    GIN-AK+ 0.080 ±\pm 0.001 0.7961 ±\pm 0.0119 0.2930 ±\pm 0.0044
    GSN 0.101 ±\pm 0.010 0.7799 ±\pm 0.0100 -
    DGN 0.168 ±\pm 0.003 0.7970 ±\pm 0.0097 0.2885 ±\pm 0.0030
    PNA 0.188 ±\pm 0.004 0.7905 ±\pm 0.0132 0.2838 ±\pm 0.0035
    Spec-GN 0.070 ±\pm 0.002 - 0.2965 ±\pm 0.0028
    SAN 0.139 ±\pm 0.006 0.7785 ±\pm 0.0025 0.2765 ±\pm 0.0042
    Graphormer 0.122 ±\pm 0.006 0.7640 ±\pm 0.0022 0.2643 ±\pm 0.0017
    GPS 0.070 ±\pm 0.004 0.7880 ±\pm 0.0101 0.2907 ±\pm 0.0028
    Specformer 0.066 ±\pm 0.003 0.7889 ±\pm 0.0124 0.2972 ±\pm 0.0023

    Specformer-Small on ZINC achieved an MAE of 0.066 with approximately 500K parameters, outperforming GPS (0.070) and CIN (0.079). Specformer-Large achieved 0.2972 AP on MolPCBA without using manual structural features or domain-engineered subgraph descriptors. On PCQM4Mv2 (3.7M molecules, HOMO-LUMO gap regression), Specformer-Medium achieved an MAE of 0.0916 with 4.1M parameters, outperforming GPS-small (0.0938 with 6.2M parameters).

  10. Knowl 10 — Synthetic Graph Spectral Filter Recovery Evaluation

    data/table

    Specformer was evaluated on synthetic 2D 4-neighborhood grid graphs constructed from 50 100×100100 \times 100 images (n=10000n = 10000 nodes), sharing the same Laplacian matrix LL. Five target graph filters were applied to create pre-filtered ground-truth signals x~=UGθ(Λ)U⊤x\tilde{x} = U G_\theta(\Lambda) U^\top x.

    Models with comparable capacity (∼2K\sim 2\text{K} parameters) were trained to minimize the sum of squared error against x~\tilde{x}, reporting mean squared error (MSE) and R2R^2 score in parentheses:

    Model Low-pass High-pass Band-pass Band-rejection Comb
    (∼\sim2k param.) exp⁡(−10λ2)\exp(-10\lambda^2) 1−exp⁡(−10λ2)1-\exp(-10\lambda^2) exp⁡(−10(λ−1)2)\exp(-10(\lambda-1)^2) 1−exp⁡(−10(λ−1)2)1-\exp(-10(\lambda-1)^2) ∣sin⁡(πλ)∣|\sin(\pi\lambda)|
    GCN 3.4799 (.9872) 67.6635 (.2364) 25.8755 (.1148) 21.0747 (.9438) 50.5120 (.2977)
    GAT 2.3574 (.9905) 21.9618 (.7529) 14.4326 (.4823) 12.6384 (.9652) 23.1813 (.6957)
    ChebyNet 0.8220 (.9973) 0.7867 (.9903) 2.2722 (.9104) 2.5296 (.9934) 4.0735 (.9447)
    GPR-GNN 0.4169 (.9984) 0.0943 (.9986) 3.5121 (.8551) 3.7917 (.9905) 4.6549 (.9311)
    BernNet 0.0314 (.9999) 0.0113 (.9999) 0.0411 (.9984) 0.9313 (.9973) 0.9982 (.9868)
    JacobiConv 0.0003 (.9999) 0.0064 (.9999) 0.0213 (.9999) 0.0156 (.9999) 0.2933 (.9995)
    Specformer 0.0002 (.9999) 0.0026 (.9999) 0.0017 (.9999) 0.0014 (.9999) 0.0057 (.9999)

    Specformer achieved lowest error across all five filter types. Polynomial GNNs (ChebyNet, GPR-GNN, BernNet, JacobiConv) struggle with narrow frequency bands (e.g., λ∈[0.75,1.25]\lambda \in [0.75, 1.25] in Band-rejection and oscillating peaks in Comb), whereas Specformer fits complex multi-frequency responses without localized polynomial oscillation artifacts.

  11. Knowl 11 — Quantized Self-Attention Condensation for Frequency Dependency Analysis

    model/method

    To analyze how Specformer captures dependencies among different frequency components, the continuous self-attention matrix is quantized across discrete frequency bands.

    The normalized Laplacian eigenvalues λ∈[0,2]\lambda \in [0, 2] are partitioned into three disjoint frequency bands:

    • Low=[0,2/3)\text{Low} = [0, 2/3)
    • Medium=[2/3,4/3)\text{Medium} = [2/3, 4/3)
    • High=[4/3,2]\text{High} = [4/3, 2]

    Let B=Softmax(QK⊤dq)∈Rn×nB = \text{Softmax}\left(\frac{Q K^\top}{\sqrt{d_q}}\right) \in \mathbb{R}^{n \times n} denote the row-normalized self-attention weight matrix. The condensed attention matrix B^∈R3×3\hat{B} \in \mathbb{R}^{3 \times 3} is defined by summing columns over the target frequency band fjf_j and averaging rows over the source frequency band fif_i:

    B^i,j=1∣1λ∈fi∣∑λp∈fi∑λq∈fjBp,q\hat{B}_{i,j} = \frac{1}{|\mathbf{1}_{\lambda \in f_i}|} \sum_{\lambda_p \in f_i} \sum_{\lambda_q \in f_j} B_{p,q}

    where ∣1λ∈fi∣|\mathbf{1}_{\lambda \in f_i}| denotes the number of eigenvalues in band fif_i.

    Empirical visualization reveals consistent spectral attention patterns:

    1. In low-pass tasks (e.g., Citeseer), all frequency bands predominantly attend to the low-frequency band.
    2. In band-related tasks (e.g., Squirrel, Band-pass, Band-rejection), low- and high-frequency bands attend strongly to the medium-frequency band, while the medium band attends to the low/high bands.
    3. On graph-level tasks (e.g., ZINC), different decoder heads learn distinct, complementary attention distributions and filter responses.

Coverage note — None was omitted; all key architectural components, theoretical results (Propositions 1 and 2), synthetic experiments, node classification, graph classification/regression benchmarks, and visualization analyses are covered.

References

  1. 1.Anson Bastos, Abhishek Nadgeri, Kuldeep Singh, Hiroki Kanezashi, Toyotaro Suzumura, and Isaiah Onando Mulang'. How expressive are transformers in spectral domain for graphs? Transactions on Machine Learning Research, 2022.
  2. 2.Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.
  3. 3.Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In AAAI, pp. 3950–3957. AAAI Press, 2021.
  4. 4.Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203, 2013.
  5. 5.Yunfeng Cai, Guanhua Fang, and Ping Li. A note on sparse generalized eigenvalue problem. In NeurIPS, pp. 23036–23048, 2021.
  6. 6.Heng Chang, Yu Rong, Tingyang Xu, Yatao Bian, Shiji Zhou, Xin Wang, Junzhou Huang, and Wenwu Zhu. Not all low-pass filters are robust in graph convolutional networks. In NeurIPS, pp. 25058–25071, 2021.
  7. 7.Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
  8. 8.Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurIPS, pp. 3837–3845, 2016.
  9. 9.Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT, pp. 4171–4186. Association for Computational Linguistics, 2019.
  10. 10.Xiaowen Dong, Dorina Thanou, Laura Toni, Michael M. Bronstein, and Pascal Frossard. Graph signal processing for machine learning: A review and new perspectives. IEEE Signal Process. Mag., 37(6):117–127, 2020.
  11. 11.Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
  12. 12.Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. CoRR, abs/2012.09699, 2020.
  13. 13.Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020.
  14. 14.Joan Bruna Estrach, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In ICLR, 2014.
  15. 15.Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263–1272. PMLR, 2017.
  16. 16.David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011.
  17. 17.Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In NeurIPS, 2021.
  18. 18.Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. In NeurIPS, 2022.
  19. 19.Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020.
  20. 20.Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB-LSC: A large-scale challenge for machine learning on graphs. In NeurIPS Datasets and Benchmarks, 2021.
  21. 21.Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
  22. 22.Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
  23. 23.Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NeurIPS, 2021.
  24. 24.Renjie Liao. Deep Learning on Graphs: Theory, Models, Algorithms and Applications. University of Toronto (Canada), 2021.
  25. 25.Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR, 2019.
  26. 26.Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, pp. 20887–20902, 2021.
  27. 27.Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In ICLR (Poster). OpenReview.net, 2019.
  28. 28.Hadrien Montanelli and Haizhao Yang. Error bounds for deep relu networks using the kolmogorov-arnold superposition theorem. Neural Networks, 129:1–6, 2020.
  29. 29.Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR. OpenReview.net, 2020.
  30. 30.Antonio Ortega, Pascal Frossard, Jelena Kovacevic, José M. F. Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proc. IEEE, 106(5):808–828, 2018.
  31. 31.Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks. In ICLR. OpenReview.net, 2020.
  32. 32.Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. CoRR, abs/2205.12454, 2022.
  33. 33.Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
  34. 34.Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61–80, 2008.
  35. 35.Han Shi, Jiahui Gao, Hang Xu, Xiaodan Liang, Zhenguo Li, Lingpeng Kong, Stephen M. S. Lee, and James T. Kwok. Revisiting over-smoothing in BERT from the perspective of graph. CoRR, abs/2202.08625, 2022.
  36. 36.Elias M Stein and Rami Shakarchi. Fourier analysis: an introduction, volume 1. Princeton University Press, 2011.
  37. 37.Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR. OpenReview.net, 2022.
  38. 38.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS, pp. 5998–6008, 2017a.
  39. 39.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017b.
  40. 40.Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
  41. 41.Peihao Wang, Wenqing Zheng, Tianlong Chen, and Zhangyang Wang. Anti-oversmoothing in deep vision transformers via the fourier domain analysis: From theory to practice. CoRR, abs/2203.05962, 2022.
  42. 42.Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 23341–23362. PMLR, 2022.
  43. 43.Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6861–6871. PMLR, 2019.
  44. 44.Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 32(1):4–24, 2021.
  45. 45.Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. arXiv preprint arXiv:1904.07785, 2019.
  46. 46.Mingqi Yang, Yanming Shen, Rui Li, Heng Qi, Qiang Zhang, and Baocai Yin. A new perspective on the effects of spectrum in graph neural networks. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 25261–25279. PMLR, 2022.
  47. 47.Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform bad for graph representation? In NeurIPS, 2022.
  48. 48.Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. In NIPS, pp. 3391–3401, 2017.
  49. 49.Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI Open, 1:57–81, 2020.
  50. 50.Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In WWW, pp. 1215–1226. ACM / IW3C2, 2021.

Citation

MLA
Bo, D., et al. “Specformer: Spectral Graph Neural Networks Meet Transformers”. arXiv, 2023, http://arxiv.org/abs/2303.01028v1.
APA
Bo, D., Shi, C., Wang, L., & Liao, R. (2023). Specformer: Spectral Graph Neural Networks Meet Transformers. arXiv. http://arxiv.org/abs/2303.01028v1
Chicago
Bo, D., C. Shi, L. Wang, and R. Liao. 2023. “Specformer: Spectral Graph Neural Networks Meet Transformers”. arXiv. http://arxiv.org/abs/2303.01028v1.
Harvard
Bo, D. et al. (2023) “Specformer: Spectral Graph Neural Networks Meet Transformers”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2303.01028v1.
Vancouver
1. Bo D, Shi C, Wang L, Liao R (2023) Specformer: Spectral Graph Neural Networks Meet Transformers. arXiv

BibTeX

@article{bo2023specformer,
  title = {Specformer: Spectral Graph Neural Networks Meet Transformers},
  author = {Bo, Deyu and Shi, Chuan and Wang, Lele and Liao, Renjie},
  year = {2023},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2303.01028v1},
  eprint = {2303.01028}
}
Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Authors