Specformer: Spectral Graph Neural Networks Meet Transformers
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.
Deyu Bo, Chuan Shi, Lele Wang, Renjie Liao
# 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 [https://github.com/bdy9527/Specformer](https://github.com/bdy9527/Specformer).

## 1 Introduction

Graph neural networks (GNNs), firstly proposed in (Scarselli et al., 2008), become increasingly popular in the field of machine learning due to their empirical successes. Depending on how the graph signals (or features) are leveraged, GNNs can be roughly categorized into two classes, namely spatial GNNs and spectral GNNs. Spatial GNNs often adopt a message passing framework (Gilmer et al., 2017; Battaglia et al., 2018), which learns useful graph representations via propagating local information on graphs. Spectral GNNs (Bruna et al., 2013; Defferrard et al., 2016) instead perform graph convolutions via spectral filters (_i.e._, filters applied to the spectrum of the graph Laplacian), which can learn to capture non-local dependencies in graph signals. Although spatial GNNs have achieved impressive performances in many domains, spectral GNNs are somewhat under-explored.

There are a few reasons why spectral GNNs have not been able to catch up. First, most existing spectral filters are essentially scalar-to-scalar functions. In particular, they take a single eigenvalue as input and apply the same filter to all eigenvalues. This filtering mechanism could ignore the rich information embedded in the spectrum, _i.e._, the set of eigenvalues. For example, we know from the spectral graph theory that the algebraic multiplicity of the eigenvalue \(0\) tells us the number of connected components in the graph. However, such information can not be captured by scalar-to-scalar filters. Second, the spectral filters are often approximated via fixed-order (or truncated) orthonormal bases, _e.g._, Chebyshev polynomials (Defferrard et al., 2016; He et al., 2022) and graph wavelets (Hammond et al., 2011; Xu et al., 2019), in order to avoid the costly spectral decomposition of the graph Laplacian. Although the orthonormality is a nice property, this truncated approximation is less expressive and may severely limit the graph representation learning.

Therefore, in order to improve spectral GNNs, it is natural to ask: _how can we build expressive spectral filters that can effectively leverage the spectrum of graph Laplacian?_ To answer this question,
we first note that eigenvalues of graph Laplacian represent the frequency, _i.e._, total variation of the corresponding eigenvectors. The magnitudes of frequencies thus convey rich information. Moreover, the relative difference between two eigenvalues also reflects important frequency information, _e.g._, the spectral gap. To capture both magnitudes of frequency and relative frequency, we propose a Transformer (Vaswani et al., 2017) based set-to-set spectral filter, termed _Specformer_. Our Specformer first encodes the range of eigenvalues via positional embedding and then exploits the self-attention mechanism to learn relative information from the set of eigenvalues. Relying on the learned representations of eigenvalues, we also design a decoder with a bank of learnable bases. Finally, by combining these bases, Specformer can construct a permutation-equivariant and non-local graph convolution. In summary, our contributions are as follows:

* We propose a novel Transformer-based set-to-set spectral filter along with learnable bases, called Specformer, which effectively captures both magnitudes and relative differences of all eigenvalues of the graph Laplacian.
* We show that Specformer is permutation equivariant and can perform non-local graph convolutions, which is non-trivial to achieve in many spatial GNNs.
* Experiments on synthetic datasets show that Specformer learns to better recover the given spectral filters than other spectral GNNs.
* Extensive experiments on various node-level and graph-level benchmarks demonstrate that Specformer outperforms state-of-the-art GNNs and learns meaningful spectrum patterns.

## 2 Related Work

Existing GNNs can be roughly divided into two categories: spatial and spectral GNNs.

Spatial GNNs.Spatial GNNs like GAT (Velickovic et al., 2018) and MPNN (Gilmer et al., 2017) leverage message passing to aggregate local information from neighborhoods. By stacking multiple layers, spatial GNNs can possibly learn long-range dependencies but suffer from over-smoothing (Oono and Suzuki, 2020) and over-squashing (Topping et al., 2022). Therefore, how to balance local and global information is an important research topic for spatial GNNs. We refer readers to (Wu et al., 2021; Zhou et al., 2020; Liao, 2021) for a more detailed discussion about spatial GNNs.

Spectral GNNs.Spectral GNNs (Ortega et al., 2018; Dong et al., 2020; Wu et al., 2019; Zhu et al., 2021; Bo et al., 2021; Chang et al., 2021; Yang et al., 2022) leverage the spectrum of graph Laplacian to perform convolutions in the spectral domain. A popular subclass of spectral GNNs leverages different kinds of orthogonal polynomials to approximate arbitrary filters, including Monomial (Chien et al., 2021), Chebyshev (Defferrard et al., 2016; Kipf and Welling, 2017; He et al., 2022), Bernstein (He et al., 2021), and Jacobi (Wang and Zhang, 2022). Relying on the diagonalization of symmetric matrices, they avoid direct spectral decomposition and guarantee localization. However, all such polynomial filters are scalar-to-scalar functions, and the bases are pre-defined, which limits their expressiveness. Another subclass requires either full or partial spectral decomposition, such as SpectralCNN (Estrach et al., 2014) and LanczosNet (Liao et al., 2019). They parameterize the spectral filters by neural networks, thus being more expressive than truncated polynomials. However, such spectral filters are still limited as they do not capture the dependencies among multiple eigenvalues.

Graph Transformer.Transformers and GNNs are closely relevant since the attention weights of Transformer can be seen as a weighted adjacency matrix of a fully connected graph. Graph Transformers Dwivedi and Bresson (2020) combine both and have gained popularity recently. Graphormer (Ying et al., 2022), SAN (Kreuzer et al., 2021), and GPS (Rampasek et al., 2022) design powerful positional and structural embeddings to further improve their expressive power. Graph Transformers still belong to spatial GNNs, although the high-cost self-attention is non-local. The limitation of spatial attention compared to spectral attention has been discussed in (Bastos et al., 2022).

## 3 Background

In this section, we introduce some preliminaries of graph signal processing (GSP) (Ortega et al., 2018) and Transformer (Vaswani et al., 2017).
Preliminary.Assume that we have a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) denotes the node set with \(|\mathcal{V}|=n\) and \(\mathcal{E}\) is the edge set. The corresponding adjacency matrix \(\mathbf{A}\in\{0,1\}^{n\times n}\), where \(A_{ij}=1\) if there is an edge between nodes \(i\) and \(j\), and \(A_{ij}=0\) otherwise. The normalized graph Laplacian matrix is defined as \(\mathbf{L}=\mathbf{I}_{n}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\), where \(\mathbf{I}_{n}\) is the \(n\times n\) identity matrix and \(\mathbf{D}\) is the diagonal degree matrix with diagonal entries \(D_{ii}=\sum_{j}A_{ij}\) for all \(i\in\mathcal{V}\) and off-diagonal entries \(D_{ij}=0\) for \(i\neq j\). We assume \(\mathcal{G}\) is undirected. Hence, \(\mathbf{L}\) is a real symmetric matrix, whose spectral decomposition can be written as \(\mathbf{L}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{\top}\), where the columns of \(\mathbf{U}\) are the eigenvectors and \(\mathbf{\Lambda}=\text{diag}([\lambda_{1},\lambda_{2},\ldots,\lambda_{n}])\) are the corresponding eigenvalues ranged in \([0,2]\).

Graph Signal Processing (GSP).Spectral GNNs rely on several important concepts from GSP, namely, spectral filtering, graph Fourier transform and its inverse. The graph Fourier transform is written as \(\hat{\mathbf{x}}=\mathbf{U}^{\top}\mathbf{x}\), where \(\mathbf{x}\in\mathbb{R}^{n\times 1}\) is a graph signal and \(\hat{\mathbf{x}}\in\mathbb{R}^{n\times 1}\) represents the Fourier coefficients. Then a spectral filter \(G_{\theta}\) is used to scale \(\hat{\mathbf{x}}\). Finally, the inverse graph Fourier transform is applied to yield the filtered signal in spatial domain \(\hat{\mathbf{x}}=\mathbf{U}G_{\theta}\hat{\mathbf{x}}\). The key task in GSP is to design a powerful spectral filter \(G_{\theta}\) so that we can exploit the useful frequency information.

Transformer.Transformer is a powerful deep learning model, which is widely used in natural language processing (Devlin et al., 2019), vision (Dosovitskiy et al., 2021), and graphs (Ying et al., 2022; Rampasek et al., 2022). Each Transformer layer consists of two components: a multi-head self-attention (MHA) module and a token-wise feed-forward network (FFN). Given the input representations \(\mathbf{H}=[\mathbf{h}_{1}^{\top},\ldots,\mathbf{h}_{n}^{\top}]\in\mathbb{R}^{n\times d}\), where \(d\) is the hidden dimension, MHA first projects \(\mathbf{H}\) into query, key and value through three matrices (\(\mathbf{W}^{Q}\), \(\mathbf{W}^{K}\) and \(\mathbf{W}^{V}\)) to calculate attentions. And FFN is then used to add transformation. The model can be written as follows where we denote the query dimension as \(d_{q}\). For simplicity, we omit the bias and the description of multi-head attention.

\[\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{Softmax}(\frac{\mathbf{ Q}\mathbf{K}^{\top}}{\sqrt{d_{q}}})\mathbf{V}, \tag{1}\] \[\mathbf{Q}=\mathbf{H}\mathbf{W}^{Q},\;\mathbf{K}=\mathbf{H}\mathbf{W}^{K},\;\mathbf{V}=\mathbf{H} \mathbf{W}^{V}.\]

## 4 Specformer

In this section, we introduce our Specformer model. Fig. 1 illustrates the model architecture. We first explain how we encode the eigenvalues and use Transformer to capture their dependencies to yield useful representations. Then we turn to the decoder, which learns new eigenvalues from the representations and reconstructs the graph Laplacian matrix for graph convolution. Finally, we discuss the relationship between our Specformer and other methods, including MPNNs, polynomial GNNs, and graph Transformers.

### Eigenvalue Encoding

We design a powerful set-to-set spectral filter using Transformer to leverage both magnitudes and relative differences of all eigenvalues. However, the expressiveness of self-attention will be restricted heavily if we directly use the scalar eigenvalues to calculate the attention maps. Therefore, it is important to find a suitable function, \(\rho(\lambda):\mathbb{R}^{1}\rightarrow\mathbb{R}^{d}\), to map each eigenvalue from a scalar to a meaningful vector. We use an eigenvalue encoding function as follows.

\[\rho(\lambda,2i) =\sin(\epsilon\lambda/10000^{2i/d}), \tag{2}\] \[\rho(\lambda,2i+1) =\cos(\epsilon\lambda/10000^{2i/d}),\]

where \(i\) is the dimension of the representations and \(\epsilon\) is a hyperparameter. The benefits of \(\rho(\lambda)\) are three-fold: (1) It can capture the relative frequency shifts of eigenvalues and provides high-dimension

Figure 1: Illustration of the proposed Specformer.
vector representations. (2) It has the wavelengths from \(2\pi\) to \(10000\cdot 2\pi\), which forms a multi-scale representation for eigenvalues. (3) It can control the influence of \(\lambda\) by adjusting the value of \(\epsilon\).

The choice of \(\epsilon\) is crucial because we find that only the first few dimensions of \(\rho(\lambda)\) can distinguish different eigenvalues if we simply set \(\epsilon=1\). The reason is that eigenvalues lie in the range \([0,2]\), and the value of \(\lambda/10000^{2i/d}\) will change slightly when \(i\) becomes larger. Therefore, it is important to assign a large value of \(\epsilon\) to enlarge the influence of \(\lambda\). Experiments can be seen in Appendix C.1.

Notably, although the eigenvalue encoding (EE) is similar to the positional encoding (PE) of Transformer, they act quite differently. PE describes the information of discrete positions in the spatial domain. While EE represents the information of continuous eigenvalues in the spectral domain. Applying PE to the spatial positions (_i.e._, indices) of eigenvalues will destroy the permutation equivariance property, thereby impairing the learning ability.

The initial representations of eigenvalues are the concatenation of eigenvalues and their encodings, \(\mathbf{Z}=[\lambda_{1}\|\rho(\lambda_{1}),\cdots,\lambda_{n}\|\rho(\lambda_{n}) ]^{\top}\in\mathbb{R}^{n\times(d+1)}\). Then a standard Transformer block is used to learn the dependency between eigenvalues. We first apply layer normalization (LN) on the representations before feeding them into other sub-layers, _i.e._, MHA and FFN. This _pre-norm_ trick has been used widely to improve the optimization of Transformer (Ying et al., 2022):

\[\tilde{\mathbf{Z}} =\text{MHA}(\text{LN}(\mathbf{Z}))+\mathbf{Z}, \tag{3}\] \[\hat{\mathbf{Z}} =\text{FFN}(\text{LN}(\tilde{\mathbf{Z}}))+\tilde{\mathbf{Z}}.\]

After stacking multiple Transformer blocks, we obtain the expressive representations of the spectrum.

### Eigenvalue Decoding

Based on the representations returned by the encoder, the decoder can learn new eigenvalues for spectral filtering. Recent studies (Yang et al., 2022; Wang and Zhang, 2022) show that assigning each feature dimension a separate spectral filter improves the performance of GNNs. Motivated by this discovery, our decoder first decodes several bases. An FFN is then used to combine these bases to construct the final graph convolution.

Spectral filters.In general, the bases should learn to cover different information of the graph signal space as much as possible. For this purpose, we utilize the multi-head attention mechanism because each head has its own self-attention module. Specifically, the representations learned by each head will be fed into the decoder to perform spectral filtering to get the new eigenvalues.

\[\mathbf{Z}_{m}=\text{Attention}(\mathbf{Q}\mathbf{W}_{m}^{Q},\mathbf{K}\mathbf{W}_{m}^{K},\mathbf{V} \mathbf{W}_{m}^{V}),\quad\mathbf{\lambda}_{m}=\phi(\mathbf{Z}_{m}\mathbf{W}_{\lambda}), \tag{4}\]

where \(\mathbf{Z}_{m}\) denotes the representations learned by the \(m\)-th heads, and \(\phi\) is the activation, _e.g._, ReLU or Tanh, which is optional. \(\mathbf{\lambda}_{m}\in\mathbb{R}^{n\times 1}\) is the \(m\)-th eigenvalues after the spectral filtering.

Learnable bases.After get \(M\) filtered eigenvalues, we use a FFN: \(\mathbb{R}^{M+1}\rightarrow\mathbb{R}^{d}\) to construct the learnable bases. We first reconstruct individual new bases, concatenate them along the channel dimension, and feed them to a FFN as below,

\[\mathbf{S}_{m}=\mathbf{U}\text{diag}(\mathbf{\lambda}_{m})\mathbf{U}^{\top},\quad\hat{\mathbf{S}} =\text{FFN}([\mathbf{I}_{n}||\mathbf{S}_{1}||\cdots||\mathbf{S}_{M}]), \tag{5}\]

where \(\mathbf{S}_{m}\in\mathbb{R}^{n\times n}\) is the \(m\)-th new basis and \(\hat{\mathbf{S}}\in\mathbb{R}^{n\times n\times d}\) is the combined version. Note that our bases here serve similar purpose as those polynomial bases in the literature. But the way they are combined is learned rather than following certain recursions as in Chebyshev polynomials.

We have three optional ways to leverage this design of new bases. (1) Shared filters and shared FFN. This model has the least parameters, where the basis \(\hat{\mathbf{S}}\) is shared across all graph convolutional layers. (2) Shared filters and layer-specific FFN, which compromises between parameters and performance, _e.g._, \(\hat{\mathbf{S}}^{(l)}=\text{FFN}^{(l)}([\mathbf{I}_{n}||\mathbf{S}_{1}||\cdots||\mathbf{S}_{M }])\) where the superscript \(l\) denotes the index of layer. (3) Layer-specific filters and layer-specific FFN. This model has the most parameters and each layer has its own encoder and decoder, _e.g._, \(\hat{\mathbf{S}}^{(l)}=\text{FFN}^{(l)}([\mathbf{I}_{n}||\mathbf{S}_{1}^{(l)}||\cdots||\mathbf{ S}_{M}^{(l)}])\). We refer these three models as Specformer-Small, Specformer-Medium, and Specformer-Large.
### Graph Convolution

Finally, we assign each feature dimension a separate graph Laplacian matrix based on the learned basis \(\hat{\mathbf{S}}\), which can be written as follows:

\[\hat{\mathbf{X}}^{(l-1)}_{:,i}=\hat{\mathbf{S}}_{:,:,i}\mathbf{X}^{(l-1)}_{:,i},\quad\mathbf{X} ^{(l)}=\sigma\left(\hat{\mathbf{X}}^{(l-1)}\mathbf{W}^{(l-1)}_{x}\right)+\mathbf{X}^{(l-1)}, \tag{6}\]

where \(\mathbf{X}^{(l)}\) is the node representations in the \(l\)-th layer, \(\hat{\mathbf{X}}^{(l-1)}_{:,i}\) is the \(i\)-th channel dimension, \(\mathbf{W}^{(l-1)}_{x}\) is the transformation, and \(\sigma\) is the activation. The residual connection is an optional choice. By stacking multiple graph convolutional layers, Specformer can effectively learn node representations.

### Key Properties Compared to Related Models

Specformer _v.s._ **Polynomial GNNs.** Specformer replaces the fixed bases of polynomials, _e.g._, \(\lambda,\lambda^{2},\cdots,\lambda^{k}\), with learnable bases, which has two major advantages: (1) Universality. Polynomial GNNs are the special cases of Specformer because the learnable bases can approximate any polynomials. (2) Flexibility. Polynomial GNNs are designed to learn a shared function for all eigenvalues whereas Specformer can learn eigenvalue-specific functions, thus being more flexible.

Specformer _v.s._ **MPNNs.** MPNNs aggregate the local information from neighborhood one hop per layer. This localization capability enables MPNNs with high computational efficiency but weakens the ability in capturing the global information. Specformer is inherently non-local due to the use of (often dense) eigenvectors. The learned graph Laplacian \(\mathbf{U}G_{\theta}\mathbf{U}^{\top}=\theta_{1}\mathbf{u}_{1}\mathbf{u}_{1}^{\top}+\cdots+ \theta_{n}\mathbf{u}_{n}\mathbf{u}_{n}^{\top}\). Because \(\mathbf{u}_{i}\) is a eigenvector, \(\mathbf{u}_{i}\mathbf{u}_{i}^{\top}\) constructs a fully-connected graph. Therefore, our Specformer can break the localization of MPNNs and leverage global information.

Specformer _v.s._ **Graph Transformers.** Graphformer (Ying et al., 2022) has shown that graph Transformer can perform well on graph-level tasks. However, existing graph Transformers do not show competitiveness in the node-level tasks, _e.g._, node classification. Recent studies (Bastos et al., 2022; Wang et al., 2022; Shi et al., 2022) provide some evidence for this phenomenon. They show that Transformer is essentially a low-pass filter. Therefore, graph Transformers cannot handle the complex node label distribution, _e.g._, homophilic and heterophilic. On the contrary, as we will see in the experiment section, Specformer can learn arbitrary bases for graph convolution and perform well on both node-level and graph-level tasks.

Besides the above advantages, we show that our Specformer has the following theoretical properties.

**Proposition 1**.: _Specformer is permutation equivariant._

**Proposition 2**.: _Specformer can approximate any univariate and multivariate continuous functions._

Proposition 1 shows that Specformer can learn permutation-equivariant node representations. Proposition 2 states that Specformer is more expressive than other graph filters. First, the ability to approximate any univariate functions generalizes existing scalar-to-scalar filters. Besides, Specformer can handle multiple eigenvalues and learn multivariate functions, so it can approximate a broader range of filter functions than scalar-to-scalar filters. All proofs are provided in Appendix D

Complexity.Specformer has two parts of computation: spectral decomposition and forward process. Spectral decomposition is pre-computed and has the complexity of \(\mathcal{O}(n^{3})\). The forward complexity has three parts: Transformer, learnable bases, and graph convolution. Their corresponding complexities are \(\mathcal{O}(n^{2}d+nd^{2})\), \(\mathcal{O}(Mn^{2})\) and \(\mathcal{O}(nd)\), respectively, where \(n,M,L\) represent the number of nodes, filters, and layers, and \(d\) is the hidden dimension. The overall forward complexity is \(\mathcal{O}(n^{2}(d+M)+nd(L+d))\). The overall complexity of Specformer is the sum of the forward complexity and the decomposition complexity amortized over the number of uses in training and inference, rather than a simple summation of the two. See Appendix C.2 for more discussion.

Scalability.When applying Specformer to large graphs, one can use the Sparse Generalized Eigenvalue (SGE) algorithms (Cai et al., 2021) to calculate \(q\) eigenvalues and eigenvectors, in which case the forward complexity will reduce to \((q^{2}(d+M)+nd(L+d))\).

## 5 Experiments

In this section, we conduct experiments on a synthetic dataset and a wide range of real-world graph datasets to verify the effectiveness of our Specformer.
### Learning Spectral Filters on Synthetic Data

Dataset description.We take 50 images with the resolution of 100\(\times\)100 from the Image Processing Toolbox 1. Each image is processed as a 2D regular 4-neighborhood grid graph, and the values of pixels are the node features. Therefore, these images share the same adjacency matrix \(\mathbf{A}\in\mathbb{R}^{10000\times 10000}\) and the \(m\)-th image has its graph signal \(\mathbf{x}_{m}\in\mathbb{R}^{1000\times 1}\). Five predefined graph filters are used to generate ground truth graph signals. For example, if we use the low-pass filter with \(G_{\theta}=\exp(-10\lambda^{2})\), the filtered graph signal is calculated by \(\tilde{\mathbf{x}}_{m}=\mathbf{U}\text{diag}[\exp(-10\lambda^{2}_{1}),\ldots,\exp(-10 \lambda^{2}_{n})]\mathbf{U}^{T}\mathbf{x}_{m}\).

Footnote 1: [https://www2.mathworks.cn/products/image.html](https://www2.mathworks.cn/products/image.html)

Setup.We choose six Spectral GNNs as baselines: GCN (Kipf and Welling, 2017), GAT (Velickovic et al., 2018), ChebyNet (Defferrard et al., 2016), GPR-GNN (Chien et al., 2021), BernNet (He et al., 2021), and JacobiConv (Wang and Zhang, 2022). Each method takes \(\mathbf{A}\) and \(\mathbf{x}_{m}\) as inputs, and tries to minimize the sum of squared error between the outputs \(\tilde{\mathbf{x}}_{m}\) and the pre-filtered graph signal \(\tilde{\mathbf{x}}_{m}\). We tune the number of hidden units to ensure that each method has nearly \(2\)K trainable parameters. The polynomial order is set to 10 for ChebyNet, GPR-GNN, and BernNet. For our model, we use Specformer-Small with 16 hidden units and 1 head. In training, the maximum number of epochs is set to 2000, and the model will be stopped early if the loss does not descend 200 epochs. All regularization tricks are removed. The learning rate is set to 0.01 for all models. We use two metrics to evaluate each method: sum of squared error and \(R^{2}\) score.

Results.The quantitative experiment results are shown in Table 1, from which we can see that Specformer achieves the best performance on all synthetic graphs. Especially, it has more improvements on challenging graphs, such as Band-rejection and Comb. This validates the effectiveness of Specformer in learning complex graph filters. In addition, we can see that GCN and GAT only perform better on the homophilic graph, which reflects that only using low-frequency information is not enough. Polynomial-based GNNs, _i.e._, ChebyNet, GPR-GNN, BernNet, and JacobiConv, have more stable performances. But their expressiveness is still weaker than Specformer. We visualize the graph filters learned by GPR-GNN, BernNet, and Specformer in Figure 2, which further validates our claims. The horizontal axis presents the original eigenvalues, and the vertical axis indicates the corresponding new eigenvalues. For clarity, we uniformly downsample the eigenvalues at a ratio of 1:200 and only visualize three graphs because the situations of Low-pass and High-pass are similar. The same goes for Band-pass and Band-rejection. It can be seen that all methods can fit the easy filters well, _i.e._, High-pass. However, the polynomial-based GNNs cannot learn the narrow bands in Band-rejection and Comb, _e.g._, \(\lambda\in[0.75,1.25]\), which harms their performance. On the contrary, Specformer fits the ground truth precisely, reflecting the superior learning ability over polynomials. The spatial results, _i.e._, filtered images, can be seen in Appendix C.3.

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline \multirow{2}{*}{**Model** (\(\mathbf{\sim}\)**2k param.**)} & \multirow{2}{*}{\(\exp(-10\lambda^{2})\)} & \multirow{2}{*}{\(1-\exp(-10\lambda^{2})\)} & \multirow{2}{*}{\(\exp(-10\lambda-1)^{2}\)} & \multirow{2}{*}{\(1-\exp(-10\lambda-1)^{2}\)} & \multirow{2}{*}{\(\left[\sin(\pi)\right]\)} \\ \cline{2-2} \cline{5-6}  & & & & & \\ \hline GCN & 3.479(9872) & 67.663(2364) & 25.8755(1148) & 21.074(9438) & 50.5120(2977) \\ GAT & 2.3574(9905) & 21.9618(7529) & 14.4326(6823) & 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.9913(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**,**9**999**) & **0.0014**,**9999**) & **0.0057**,**9999**) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Node regression results, mean of the sum of squared error & \(R^{2}\) score, on synthetic data.

Figure 2: Illustrations of filters learned by two polynomial GNNs and Specformer.
### Node Classification

**Datasets.** For the node classification task, we perform experiments on four homophilic datasets, _i.e_., Cora, Citeser, Amazon-Photo and ogbn-arXiv, and four heterophilic datasets, _i.e_., Chameleon, Squirrel, Actor and Penn94. Penn94 (Lim et al., 2021) and arXiv (Hu et al., 2020) are two large scale datasets. Other datasets, provided by (Rozemberczki et al., 2021; Pei et al., 2020), are commonly used to evaluate the performance of GNNs on heterophilic and homophilic graphs.

**Baselines and settings.** We benchmark our model against a series of competitive baselines, including spatial GNNs, spectral GNNs, and graph Transformers. For all datasets, we use the full-supervised split, _i.e_., 60% for training, 20% for validation, and 20% for testing, as suggested in (He et al., 2021). All methods run 10 times and report the mean accuracy with a 95% confidence interval. For polynomial GNNs, we set the order of polynomials \(K\) = 10. For other methods, we use a 2-layer module. To ensure all models have similar numbers of parameters, in six small datasets, we set the hidden size \(d=64\) for spatial and spectral GNNs and \(d=32\) for graph Transformers and Specformer. The total numbers of parameters on Photo dataset are shown in Table 2. On two large datasets, we use truncated spectral decomposition to improve the scalability. Based on the filters learned on the small datasets, we find that band-rejection filters are important for heterophilic datasets and low-pass filters are suitable for homophilic datasets. See Figures 4(b) and 4(d). Therefore, we use eigenvectors with the smallest 3000 (low-frequency) and largest 3000 eigenvalues (high-frequency) for Penn94, and eigenvectors with the smallest 5000 eigenvalues (low-frequency) for arXiv. We use one layer for Specformer and set \(d=64\) in Penn94 and \(d=512\) in arXiv for all methods, as suggested by (Lim et al., 2021; He et al., 2022). More details, _e.g_., optimizers, can be found in Appendix A.

**Results.** In Table 2, we can find that Specformer outperforms state-of-the-art baselines on 7 out of 8 datasets and achieves 12% relative improvement on the Squirrel dataset, which validates the superior learning ability of Specformer. In addition, the improvement is more pronounced on heterophilic datasets than on homophilic datasets. This is probably caused by the easier fitting of the low-pass filters in homophilic datasets. The same phenomenon is also observed in the synthetic graphs. An interesting observation is that the improvement on larger graphs, _e.g_., Actor and Photo, is less than that on smaller graphs. One possible reason is that the role of the self-attention mechanism is weakened, _i.e_., the attention values become uniform due to a large number of tokens. We notice that Specformer has a slightly higher variance than the baselines. This is because we set a large dropout rate to prevent overfitting. On the two large graph datasets, we can see that graph Transformers are memory-consuming due to the self-attention. On the contrary, Specformer reduces the time and space costs by using the truncated decomposition and shows better scalability than graph Transformers. The time and space overheads are listed in Appendix C.2.

### Graph Classification and Regression

**Datasets.** We conduct experiments on three graph-level datasets with different scales. ZINC (Dwivedi et al., 2020) is a small subset of a large molecular dataset, which contains 12K graphs in

\begin{table}
\begin{tabular}{l|c|c c c c|c c c c} \hline  & \multirow{2}{*}{**Param.**} & \multicolumn{4}{c|}{**Heterophilic**} & \multicolumn{4}{c}{**Homophilic**} \\  & & **Photo** & **Chameleon** & **Squirrel** & **Actor** & **Penn94** & **Cora** & **Citeseer** & **Photo** & **arXiv** \\ \hline \multicolumn{1}{c}{Spatial-based GNNs} & \multicolumn{4}{c}{Spatial-based GNNs} \\ \hline GCN & 48K & 95.61a2.21 & 46.7860.87 & 33.231a.16 & 82.4740.27 & 87.144.101 & 79.860.67 & 88.2660.73 & 71.7440.29 \\ GAT & 49K & 63.13a1.93 & 44.949.88 & 33.9342.47 & 81.534.50 & 88.0340.79 & 80.5240.71 & 90.9440.68 & 71.8220.23 \\ H\({}_{1}\)GCN & 60K & 57.11a1.58 & 36.422.189 & 35.861.03 & OOM & 86.922.137 & 77.071.64 & 93.026.91 & OOM \\ GCNII & 49K & 63.4440.85 & 41.961a.02 & 36.989.05 & 82.924.98 & 88.460.82 & 79.0740.65 & 89.9440.31 & 72.0410.19 \\ \hline \multicolumn{1}{c}{Spherical-based GNNs} & \multicolumn{4}{c}{Spherical-based GNNs} \\ \hline LanczosNet* & 50K & 64.81a1.54 & 48.644.17 & 38.1640.91 & 81.554.20 & 86.777.145 & 80.0514.65 & 93.2140.85 & 71.4640.39 \\ ChebyNet & 48K & 59.28a2.15 & 45.504.21 & 37.6140.89 & 81.090.38 & 86.7680.82 & 79.1140.75 & 93.7740.32 & 71.1240.22 \\ GPP-GAN & 48K & 67.28a1.90 & 50.151a1.92 & 39.294 & 67.183.180 & 85.7240.69 & 80.120.83 & 93.5840.28 & 71.7840.18 \\ BernNet & 48K & 68.29a1.58 & 51.354.73 & 41.794.101 & 82.4740.21 & 88.5240.95 & 80.0940.79 & 93.6330.35 & 71.9660.27 \\ ChebyNet1 & 48K & 71.37a1.50 & 57.722a.15 & 47.158.07 & 71.312.20 & 78.7140.93 & 85.340.79 & 94.9263.32 & 73.2240.23 \\ JacobiConv & 48K & 74.20a1.03 & 57.384.125 & 41.7740.64 & 83.350.11 & **88.9840.46** & 80.7840.79 & 95.4340.23 & 72.1440.17 \\ \hline \multicolumn{1}{c}{Graphic Transformers} & \multicolumn{4}{c}{Grapheme7} \\ \hline Transformer* & 37K & 46.39a19.71 & 39.903.163 & 39.959.164 & OOM & 71.733a1.68 & 70.554.12 & 90.0551.50 & OOM \\ Graphformer* & 139K & 54.498a1.31 & 36.569a1.75 & 38.454.138 & OOM & 67.717a0.78 & 73.041.21 & 85.204.12 & OOM \\ \hline \hline Specformer & 32K & **74.72a1.29** & **64.6440.81** & **41.9341.84** & **84.320.32** & 88.57a1.01 & **81.494.94** & **95.488.32** & **72.37a1.18** \\ \hline \hline \end{tabular}
\end{table}
Table 2: Results on real-world node classification tasks. Mean accuracy (%) \(\pm\) 95% confidence interval. * means re-implemented baselines. “OOM” means out of GPU memory.
total. MolHIV and MolPCBA are taken from the Open Graph Benchmark (OGB) datasets (Hu et al., 2020). MolHIV is a medium dataset that has nearly 41K graphs. MolPCBA is the largest, containing 437K graphs. For all datasets, nodes represent the atoms, and edges indicate the bonds.

Baselines and Settings.We choose popular MPNNs (GCN, GIN, and GatedGNN), graph Transformers with positional or structural embedding (SAN, Graphormer, and GPS), and other state-of-the-art GNNs (CIN, GIN-AK+, etc.) as the baselines of graph-level tasks. For the ZINC dataset, we tune the hyperparameters of Specformer to ensure that the total parameters are around 500K.

Results.We apply Specformer-Small, Medium, and Large for ZINC, MolHIV, and MolPCBA, respectively. The results are shown in Table 3. It can be seen that Specformer outperforms the state-of-the-art models in ZINC and MolPCBA datasets, without using any hand-crafted features or pre-defined polynomials. This phenomenon proves that directly using neural networks to learn the graph spectrum is a promising way to construct powerful GNNs.

### Ablation Studies

We perform ablation studies on two node-level datasets and one graph-level dataset to evaluate the effectiveness of each component. The results are shown in Table 4. The top three lines show the effect of the encoder, _i.e._, eigenvalue encoding (EE) and self-attention. It can be seen that EE is more important on Squirrel than on Citeseer. The reason is that the spectral filter of Squirrel is more difficult to learn. Therefore, the model needs the encoding to learn better representations. The attention module consistently improves performance by capturing the dependency among eigenvalues.

The bottom three lines verify the performance of graph filters at different scales. We can see that in the easy task, _e.g._, Citeseer, the Small and Medium models have similar performance, but the Large model causes serious overfitting. In the hard task, _e.g._, Squirrel and MolPCBA, the Large model is slightly better than the Medium model but outperforms the Small model a lot, implying that adding the number of parameters can boost the performance. In summary, it is important to consider the difficulty of tasks when selecting models.

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline \multicolumn{2}{c}{**Encoder**} & \multicolumn{2}{c}{**Decoder**} & \multicolumn{2}{c}{**Node-level**} & \multicolumn{2}{c}{**Graph-level**} \\ \hline \(\rho(\lambda)\) & **Attention** & **Small** & **Medium** & **Large** & **Squirrel** (\(\uparrow\)) & **Citeseer** (\(\uparrow\)) & **MolPCBA** (\(\uparrow\)) \\ \hline  & & & ✓ & & 33.05 & 80.57 & 0.2696 \\ ✓ & & & ✓ & & 63.78 & 81.17 & 0.2933 \\ ✓ & ✓ & & ✓ & & 64.64 & 81.49 & 0.2970 \\ ✓ & ✓ & ✓ & & & 64.51 & 81.47 & 0.2912 \\ ✓ & ✓ & & & ✓ & 65.10 & 80.00 & 0.2972 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Ablation studies on node-level and graph-level tasks.

\begin{table}
\begin{tabular}{l c c} \hline \hline
**Model** & **ZINC(\(\downarrow\))** & **MolHIV(\(\uparrow\))** & **MolPCBA(\(\uparrow\))** \\ \hline 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\) & \(\mathbf{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\) \\ \hline SAN & \(0.139\pm 0.006\) & \(0.7785\pm 0.0025\) & \(0.2765\pm 0.0042\) \\ Graphormer2 & \(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\) \\ \hline Specformer & \(\mathbf{0.066\pm 0.003}\) & \(0.7889\pm 0.0124\) & \(\mathbf{0.2972\pm 0.0023}\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Results on graph-level datasets. \(\downarrow\) means lower the better, and \(\uparrow\) means higher the better.
### Visualizations

We now investigate the dependency of eigenvalues and filters learned by Specformer. To make the dependency clearer, we first quantize the self-attention weight matrix by grouping the eigenvalues into three frequency bands: Low \(\in[0,\frac{2}{3})\), Medium \(\in[\frac{2}{3},\frac{4}{3})\), and High \(\in[\frac{4}{3},2]\). We then compute the quantized dependency. More details are given in Appendix B.2.

The results are shown in Figures 3, 4, and 5, from which we have some interesting observations. (1) Similar dependency patterns can be learned on different graphs. In low-pass filtering, _e.g._, Citeseer and Low-pass, all frequency bands tend to use the low-frequency information. While, in the band-related filtering, _e.g._, Squirrel, Band-pass, and Band-rejection, the low- and high-frequency highly depend on the medium-frequency, and the situation of the medium-frequency is opposite. (2) The more difficult the task, the less obvious the dependency. On Comb and ZINC, the dependency of eigenvalues is inconspicuous. (3) On graph-level datasets, the decoder can learn different filters. Figure 5 shows two basic filters. It can be seen that \(\hat{\mathbf{S}}_{1}\) and \(\hat{\mathbf{S}}_{2}\) have different dependencies and patterns, which are different from node-level tasks, where only one filter is needed. The finding suggests that these graph-level tasks are more difficult than node-level tasks and are still challenging for spectral GNNs.

## 6 Conclusion

In this paper, we propose Specformer that leverages Transformer to build a set-to-set spectral filter along with learnable bases. Specformer effectively captures magnitudes and relative dependencies of the eigenvalues in a permutation-equivariant fashion and can perform non-local graph convolution. Experiments on synthetic and real-world datasets demonstrate that Specformer outperforms various GNNs and learns meaningful spectrum patterns. A promising future direction is to improve the efficiency of Specformer through sparsifying the self-attention matrix of Transformer.

Figure 4: The dependency and learned filters of heterophilic and homophilic datasets.

Figure 5: The dependency and basic filters of ZINC dataset.

Figure 3: The dependency of eigenvalues on synthetic graphs.
#### Acknowledgments

This work is supported in part by the National Natural Science Foundation of China (No. U20B2045, 62192784, 62172052, 62002029, 62172052, U1936014), BUPT Excellent Ph.D. Students Foundation (No. CX2022310), the NSERC Discovery Grants (No. RGPIN-2019-05448, No. RGPIN-2022-04636), and the NSERC Collaborative Research and Development Grant (No. CRDPJ 543676-19). Resources used in preparing this research were provided, in part, by Advanced Research Computing at the University of British Columbia, the Oracle for Research program, and Compute Canada.
