Specformer: Spectral Graph Neural Networks Meet Transformers
Authors: Deyu Bo
Chuan Shi
Lele Wang
Renjie Liao
Venue: ICLR 2023 poster (2023)
Keywords: Spectral Graph Neural Networks
Transformer

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.

Published as a conference paper at ICLR 2023
SPECFORMER: SPECTRAL GRAPH NEURAL NETWORKS MEET TRANSFORMERS
Deyu Bo', Chuan Shi' Lele Wang', Renjie Liao Beijing University of Posts and Telccommunications!. University of British Columbia (bodeyu, shichuan @bupt edu en, flelewang, rjliao]eece. ubc...cceeubccca
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 the spectral domain, leading learnable set-to-set spectral filter. We also design 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-trut -trth 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 http::/://..ta.....oo//////////p
com
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 al,, 2013 Defferrard et al., (016)) instead perform graph convolutions via spectral filters (i.e., filters applied 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 essentially -o-salrto-scalar functions. In particular, they take single eigenvalue as input and apply the same filter to all eigenvalues. This filtering mechanism could ignore the know
rich information embedded in the spectrum, i.e., the set of eigenvalues. For example, from the spectral graph theory that the algebraic multiplicity of the eigenvalue 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 2016 He al. 2022) and graph wavelets (Hammond et al. 2 Xu et al., 2019), in order to avoid the costly spectral decomposition of the graph Laplacian. Although the orthonormality a nice property, this truncated approximation is less expressive and may severely limit the graph representation learning.
Therefore, order to improve spectral GNNs, natural to ask: how can we build expressive spectral filters that can effectively leverage the spectrum of graph Laplacian? To answer this question,
"Co-corresponding authors

---

Published as a conference paper at ICLR 2023
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 Transformer (Vaswani al., 7b) 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 learn relative information from the set of cigenvalues. Relying on the learned representations of eigenvalues, we also design decoder with a bank of learnable bases. Finally, by combining these bases, Specformer can construct permutation -uuuitaiioonuuiaiiiint and non-local graph convolution. In summary, our contributions are as follows:
We propose novel Transformer-based set-to-set spectral filter along with learnable bases, called Specformer, which effectively captures both magnitudes and relative differences of all cigenvalues 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 -ftt-of--hheart 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 al. 2018 and MPNN Giimer 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- smoothng (Oono & 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
ct al.
2021 Zhou et al. 2020 Liao 2021) for more detailed discussion about spatial GNNs.
Spectral GNNs. 202T Bo et al. 202T: Chang et al.
Spectral GNNs Ortega al. 2018 Dong al. 2020 Wu al.) 2019 Zhu et al.
2021 Yang et al. 2022) leverage the spectrum of graph Laplacian to perform convolutions in the spectral domain. popular subclass of spectral GNNs leverages different kinds of orthogonal polynomials to approximate arbitrary filters, including Monomial
(Chien af., 2021), Chebyshev (Defferrard al. 2016 Kipf Welling 2017 He et al.. 2022). Bernstein (He et al., 2021). and Jacobi (Wang & 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 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 weighted adjacency matrix of fully connected graph. Graph Trans- formers Dwivedi & Bresson (2200) combine both and have gained popularity recently. Graphormer (Ying et al. (2022), SAN (Kreuzer et al., (202T). and GPS (Rampásek 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).
BACKGROUND
In this section, we introduce some preliminaries of graph signal processing (GSP) (Ortega et al. 2018) and Transformer (Vaswani et al. 2017a).
2

---

Published as a conference paper at ICLR 2023
Preliminary. Assume that have graph G EV, where V denotes the node set with |V] and & the edge set. The corresponding adjacency matrix A E {0.1)*x0 where Aty = there is edge between nodes i and j. and Aij 0 otherwise. The normalized graph Laplacian matrix is defined as In D AD 1/2, where In is the diagonal degree matrix with diagonal entries Dú - Ej Aij for all E V and off-diagonal entries Dij for # j. We assume g is undirected. Hence, is a real symmetric matrix, whose spectral decomposition can be written as L = UAU where the columns U are the eigenvectors and diag((A1, (2,,,,,.. An]) the corresponding eigenvalues ranged in [0, 2].
identity matrix and D the
Graph Signal Processing (GSP). Spectral GNNs rely several important concepts from GSP, namely, spectral filtering, graph Fourier transform and its inverse. The graph Fourier transform written as 2 U where æ [ is graph signal and & [ represents the Fourier coefficients. Then a spectral filter Go is used to scale æ. Finally, the inverse graph Fourier transform is applied to yield the filtered signal in spatial domain ズ = UGg The key task in GSP is to design a powerful spectral filter Gg so that we can exploit the useful frequency information.
Transformer. Transformer powerful deep learning model, which is widely used in natural language processing (Devlin et al., 2019), vision (Dosovitskiy et al. 202T), and graphs (Ying) al., [022]] Rampásek et al., (2022). Each Transformer layer consists of two components: multi- head self-attention (MHA) module and token-wise ferd-forward network (FFN). Given the input representations H = [h] ...... h Raadd where the hidden dimension, MHA first projects H into query, key and value through three matrices (W'2 W and WV) 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 dy. For simplicity, omit the bias and the description of multi-head attention.
QK
Attention Q K, V) Sootmmx
V
ddl
(1)
Q HW? K HWK HWV
4 SPECFORMER
In this section, we introduce our Specformer model. Fig. illustrates the model architecture. first explain how we encode the eigenvalues and use Transformer capture their dependencies to yield useful representations. Then we turn to the decoder, which learns new eigenvalues from the represen- tations and reconstructs the graph Laplacian matrix for graph convolution. Finally, discuss the relationship between Specformer and other methods, including MPNNs, polynomial GNNs, and graph Transformers.
Lincar
LX
Lx
Add & Norn
Residual
Feed Forward Network
Graph
Convolution
Add & Norn
Filter
Multi-head Attention
Decoder
4.1 EIGENVALUE ENCODING
Eigenvalue Representations
Node Representations
We design powerful set-to-set spectral filter using Transformer to leverage both magnitudes and relative differences all eigen- values. However, the expressiveness of self-attention will be restricted heavily if we directly use the sealar eigenvalues to calculate the attention maps. Therefore, it is important find a suitable function, p(A) I - Rdd to map each eigenvalue from scalar meaningful vector. We use an eigenvalue encoding function as follows.
Eigenvalue Encoding
Eigenvalues
Figure 1: Illusrationn of the pro- posed Specformer.
( 21) sin(eA/100000*//4
(A 2i cos(e\/ (<((A//0000//d))
where is the dimension of the representations and is hyperparameter. The benefits p(X) are three-fold: (1) It can capture the relative frequency shifts of eigenvalues and provides high-dimension
3

---

Published as a conference paper at ICLR 2023
vector representations. (2) It has the wavelengths from 2TT to 10000 2n, which forms multi-scale representation for eigenvalues. (3) can control the influence of À by adjusting the value of
The choice of is crucial because find that only the first few dimensions of p()) can distinguish different eigenvalues we simply set e = 1. The reason is that cigenvalues lie in the range [0, 2/. and the value \/100002:/4 will change slightly when i becomes larger. Therefore, is important to assign a large value of to enlarge the influence of X. Experiments can be seen in Appendix C.1
Notably, although the eigenvalue encoding (EE) is similar to the positional encoding (PE) of Trans- former, they 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 the spatial positions (i.e., indices) of eigenvalues will destroy the permutation cquivariance property, thereby impairing the learning ability.
The initial representations of eigenvalues the concatenation of eigenvalues and their encodings, Z [Vi ())()), A, p(A..)]] [xx((+1) Then standard Transformer block is used to learn the dependency between eigenvalues. We first apply layer normalization (LNN) on the representations before feeding them into other sub-layers, Le., MHA and FFN. This pre-norm trick has been used widely to improve the optimization of Transformer (Ying et al. 2022)
Ż MHA(LN Z)) + Z,
2 FFN(LN ()) - 2.
After stacking multiple Transformer blocks, we obtain the expressive representations of the spectrum.
4.2 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 & Zhang 2022) show that assigning each feature dimension 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 much as possible. For this purpose, we utilize the multi-heat head attention mechanism because each head has its own self-attention module. Specifically, the representations Icarned by each head will be fed into the decoder to perform spectral filtering to get the new eigenvalues.
Zm Attention QW m: KWK T VWW), A.. = o 2m Wx),
(4)
where Zm denotes the representations learned by the m-th heads, and é is the activation, e.g., ReLU or Tanh, which optional. Am Rnx1 the m-th eigenvalues after the spectral filtering.
Learnable bases. After get M filtered eigenvalues, we use FFN: M+1 + Rd to construct the learnable bases. We first reconstruct individual new bases, concatenate them along the channel dimension, and feed them to FFN as below,
S. = Udiag( TT, = S ... ([)))))
(5)
where Sm E Raxx is the m-th new basis and E R 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 $ is shared across all graph convolutional layers. (2) Shared filters and layer-specific FFN, which compromises between parameters and performance, e.g., 5(t) = (F || ... ||Sa)) where the superscript 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., $ = FFN(") (II,IS ... | We refer these three models Specformer-Small. Specformer- Specformer-Medium,, and Specformer-Large.
4

---

Published as a conference paper at ICLR 2023
4.3 GRAPH CONVOLUTION
Finally, we assign each feature dimension a separate graph Laplacian matrix based on the learned
basis S, which can be written as follows:
(1--1) Si ((- X x = (X(-- - + ((1)),
(6)
where (1) is the node representations in the 1-th layer, X the i-th channel dimension, ( is the transformation, and is the activation. The residual connection is optional choice. By stacking multiple graph convolutional layers, Specformer can effectively learn node representations.
4.4 KEY PROPERTIES COMPARED TO RELATED MODELS
Specformer v.s. Polynomial GNNs. Specformer replaces the fixed bases of polynomials, e.g., with learnable bases, which has two major advantages: (1) Universality. Polynomial approximate any polyno- mials. (2) Flexibility. Polynomial GNNs are designed to learn a shared function for all eigenvalues whereas Specformer can learn eigenvalue-specifie functions, thus being more flexible.
X, A........,. X²
GNNs are the special cases of Specformer because the learnable bases
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 inherently non-local due to the use of (often dense) eigenvectors. The learned graph Laplacian UG = 8 un + +... + 6, U U Because u, a eigenvector, u.u. constructs fully-connected graph. Therefore, our Specformer can break the localization of MPNNs and leverage global information.
Specformer Graph Transformers. Graphormer (Yin 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 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 Specformer is permutation equivariant.
Proposition 2. Specformer can approximate any univariate and multivariate continuous functions.
Proposition 1 shows that Specformer can learn permutation-equivarian node representations. Propo- sition | 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
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 O(n²). The forward complexity has three parts: Transformer, learnable bases, and graph convolution. Their corresponding complexities are O(n2d + ndd?), O(Mn²) and O (LLd), respectively, where n, M, L represent the number of nodes, filters, and layers, and d' is the hidden dimension. The overall forward complexity is On (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 simple summation of the two. See Appendix C.2 for more discussion.
large graphs, one can use the Sparse Generalized Eigenvalue (SGE) algorithms (Cai et al. (021) to calculate q eigenvalues and eigenvectors, in which case the forward complexity will reduce to (q + M) + ndd T. + d)).
Scalability. When applying Specformer
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.
5

---

Published as a conference paper at ICLR 2023
Table 1: Node regression results, mean of the sum of squared error & R² score, on synthetic data.
Low-pass
High-pass
Band-pass
Band-rejection
Comb
Model
(~2k param.)
10X²)
exp(- 10A?)
exp(-10(A 1)9)
exp(- 1)9)
[sin(*A)]
GCN
3,4799(.9872)
67. (7.664
25.8755(.1143)
21.0747(9438)
50,5120(,297)
GAT
21.9118(.559) 2.3574(9905)
14,4526(,8823)
12.63844,9652
23.1813(,957))
ChebyNet
(8220(997.3)
0.7867(
0.2722(-914)
2.5296( 9934)
+.0735(99477
GPR-GNN
0.4169(.9998 .984)
0,0943(
3.5121(8551)
3,7917(
4.6549(.931]
BerNeet
(4999)
0.0113(. 0.0113(_999)
0.0411(9984)
0.9313(997)
0.9982(9868)
JacobiCunv 0.0993.9999)
0.0064( (969)
0.02134.999)
0.01 9999)
0.2933(,9995)
Specformer
0.0002(9999)
0.0026(,999)
0,0017(9999)
0.0014(9999)
0.0057(9999)
10p) 1889
1000
2.0
3.3
Now Eperraeeee Aga
1.0
0.0
GFS SHH
64
675-54h
0.
GF GNV
02
Spechmme
bankiit
tennec
Spectormar
Bonkit
Specbimar
Ban Epenoaluee OX
Raw Cppnntionn 20
Raw Dag
(a) High-pass
(b) Band-rejection
(c) Comb
Figure 2: Illustrations of filters learned by two polynomial GNNs and Specformer.
5.1 LEARNING SPECTRAL FILTERS ON SYNTHETIC DATA
Dataset description. We take 50 images with the resolution of 100x 100 from the Image Processing Toolbox Each image is processed as 2D regular neighhboroo grid graph, and the values of pix- els are the node features. Therefore, these images share the same adjacency matrix A E R 10000x 10000 and the m-th image has its graph signal 2m E IR. 10000x1, Five predefined graph filters are used to gen- erate ground truth graph signals. For example, if we use the low-pass filter with Gg exp(-10X²). the filtered graph signal is calculated by 2m. Udiiglexp((1100
exp( 10A ] 3mm
Setup. We choose six Spectral GNNs as baselines: GCN (Kipf Welling 2017). GAT (Velickovic cet al. 2018). ChebyNet (Defferrard al. 2016), GPR-GNN (Chien et al. 2021). BernNet (He et al. 2021). and JacobiConv (Wang& & Zhang 2022). Each method takes A and am as inputs, and tries to minimize the sum of squared error between the outputs &,m and the pre-filtered graph signal 7..- We tune the number of hidden units to ensure that each method has nearly 2K trainable parameters. The polynomial order is set 10 for ChebyNet, GPR-GNN, and BernNet. For model, Specformer-Smi with 16 hidden units and I head. In training, the maximum number of epochs 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 evaluate each method: sum of squared error and R² 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 improve- ments on challenging graphs, such as Band-rejection and Comb. This validates the effectiveness of Specformer learning complex graph filters. 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-GR 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 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-basee GNNs cannot learn the narrow bands in Band-rejection and Comb, e.g., A E [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

---

Published as a conference paper at ICLR 2023
Table 2: Results on real-world node classification tasks. Mean accuracy (%) - 95% confidence interval. means re-implemented basclines. "OOM" means out of GPU memory.
Heterophilic
Homophilic
Param. on Photo
Chameleon
Squirrel
Actor
Penn94
Cora
Citeseer
Photo
arXiv
Spatial-bssed GNNss
GCN H,GCN
48K
59.61+2.21
46,78=0.87 87
33,23+1.16
82,47=0.27
87,14=1001
79 86+0.67
88, 2620.6
71.74+0.29
49K
13.1331.93
44.49+0.85
33,9342.47
81.53+0.55
88.03=0.799
80 50.5220.71
90.94+0.68
71.
60K
57.11#1.58 18
36.42:1889
35.86t1
OOM
86.92=1.37
77.0741.64
93.02:0.91
O0M
GCNII
49K
63.44+0.85
41,96=1.02
36,89+0.95
82.92=0.59
88,46=0.82
79.9740.65
89. 39.94#0.31
12.04+0.19
Spectral-hased GNNs
LanezosNer
50K
64.81+1.56
48.64e
18. 16.6640.9
31.55=0.26
87.77=1.45
80.05+1.65
71 41.4690.39 93.21+0.85
ChebyNet
48K
59. 09.28++1.22 1.25
40.55=0.42
37.61+0.89
81.09=0.33
86, 36.67=0.82
79.11=0.75
93.77=0.32
71.12+0.22
GPR-GNN
48K
67.2841.09
50.15a1.92
39,9240.67
81.3820.16
88.57=0.69
80.1240.83
93.85a00.2
71.7840.15
BemNet
48K
1.58
51.35=0.73
41.79+1.01
82.47=0.21
88.52=0.95
80.09=0.79
93.63+0.35
71 11.9640.27
ChebNeell
48K
71.37+1.01
57.72a0.59
41.75x1.07
83. 12:1222222
88.71=0.93
80.5340.79
94.92s0..3
72. 72.3240.23
JacobiCoav
48K
74,20:1.03
57.38:1.25
41.1720.64
83.3520.11
88.98:0.46
80.78.0.79
95.4320.23
72.1420.17
Graph Transformers
Transformee"
37K
46,3911.97 .97
31.90=3.16
39,95+1.64
OOM
71.83=1.68
70.55+1.20
90.0521.50 1.5
OOM
Graphormer
139K
54.49+3.11
36.96s1.75
38.45+1.38
0OM
67.71=0.78
73. 13.30+1.21
85, 85.20=4. 12
00M
Specformer
32K
74.72+1.29
64.6420.81
41.93+1.04
84.32:0.32
88.5721011
81.4920.94
95.4820.32
72.3720.18
5.2 NODE CLASSIFICATION
Datasets.
For the node classification task, we perform experiments on four homophilic datasets, ie., Cora, Citeser, Amazon-Phone 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. (020), 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, includ- ing 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. (021). All methods run 10 times and report the mean accuracy with a 95% confidence interval. For polyno- mial GNNs, we set the order of polynomials K 10. For other methods, we use 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 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 and Therefore, we use eigenvectors with the smallest 3000 (ow-frequency) and largest 3000 eigenvalues (ligh-frequency) for Penn94, and eigenvectors with the smallest 5000 eigenvalues (low cow-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 datasets and achieves 12% relative improvement on the Squirrel dataset, which validates the superior learning ability of Specformer. datasets than on homophilic datasets. This is probably caused by the easier fitting of the low-pass filters in homophilic datasets. The same phenomenon 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 prevent overfitting. On the two large graph datasets, memory contorrn 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
addition, the improvement more pronounced on heterophilic
that graph Transformers are
5.3 GRAPH CLASSIFICATION AND REGRESSION
Datasets. We conduct experiments on three graph-level datasets with different scales. ZINC (Dwivedi al. 2020) is small subset of a large molecular dataset, which contains 12K graphs in
7

---

Published as a conference paper at ICLR 2023
Table 3: Results on graph-level datasets. 1 means lower the better, and means higher the better. Model
ZINC(L)
MolHIV(()
MolPCBA(1)
GCN
0.367 + 0.011
0.7599 = 0.0119
0.2424 + 0.0034
GIN
0.526 0.051
0.7707 0.0149
0.2703 0.0023
GatedGCN
0.090 0.001
0.266 0.002
CIN
0.079 0.006
0.8094 = 0.0057
GIN-AK+
0.080 + 0.001 0.001
0.7961 = 0.0119
0.2930 0.0044
GSN
0.101 0.010
0.7799 = 0.0100
DGN
0.168 0.003
0.7970 0.0097
0.2885 0.0030
PNA
0.7905 0.0132
0.2838 0.0035
Spec-GN GN
0,070 0.002
0.2965 0.0028
SAN
0.139 0.006
0.7785 = 0.0025
0.2765 0.0042
Graphorme
0.122 0.006
0.7640 = 0.0022
0.2643 0.0017
GPS
0.070 0.004
0,7880 = 0.0101
0,2907 0.0028
Specformer
0.066 0.003
0.7889 0.0124
0.2972 # 0.0023
Table 4: Ablation studies node-level and graph-level tasks.
Encoder
Decoder
Node-level
Graph-level
(\)
Attention
Small
Medium
Large
Squirrel (1)
Citeseer (f)
MalPCBA (f)
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
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 datasets, nodes represent the atoms, and edges indicate the bonds.
Baselines and Settings. formers 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 hyperparametters of Specformer ensure that the total parameters around 500K.
choose popular MPNNs (GCN, GIN, and GatedGNN), graph Trans-
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 a promising way construct powerful GNNs.
5.4 ABLATION STUDIES
We perform ablation studies two node-level datasets and one graph-level dataset to evaluate the effectiveness of each component. The results are shown in Table [ 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 that the spectral filter of Squirrel more difficult 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 different scales. We can 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 slightly better than the Medium model but outperforms the Small model a lot, implying that adding the number of parameters can boost the performance. summary, important to consider the difficulty of tasks when selecting models.
We retrain Graphomer MolHIV and MolPCBA datasets without using pre-training and augmentation.
8

---

Published as a conference paper at ICLR 2023
Depiendonge
Dopendencc
Dependence
Dependinne
Dependonos
LoN
660
035
0.5
641
145
0.45
0.
6:5
0.31
19A
0:35
High
high
1831
High
0.35
Ldw Mozuu high
Low Mad 1ig
J5n Pickut
Mickun High
Ldn Molku high
(a) Low-pass
(b) High-pass
Band-pass
(d) Band-rejection
(e) Comb
Figure 3: The dependency of eigenvalues on synthetic graphs.
Dependence
Graph niter
Dependence
Graph fiberr
0.42
Low
0.96
0.30
2.0-
Lnn
0.15
0.18
2.0
9.24
3.5-
1.0-
WA MAAAAAA
0.09
1..
High
0.12
05
High
53
:0003
Law
Medium High
Low
Meduam High
(a) Dependency of Citeseer
(b) Filter of Citeseer
(c) Dependency Squirrel
(d) Filter Squirrel
Figure 4: The dependency and learned filters of heterophilic and homophilic datasets.
Dependence
Gireph fiter
Dependence
Graph filwr
0.14
0.14
75
Mediu
0.32
Medium
0.12
25
0.10
-25
High
High
0.08
000 325 6:5 0.75 150
200
026
5.75 150
2.58
(a) dependency of S1
(b) Filter of S₁
(c) dependency of S
(d) Filter of S
Figure 5: The dependency and basic filters of ZINC dataset.
5.5 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 [0, )), Medium E [ 4). and High [ 2]. We then compute the quantized dependency. More details are given in Appendix B.2
The results are shown in Figures Similar dependency patterns can be learned on different graphs. In low-pass filtering, e.g., Citeseer and Low-pass, all frequency bands tend use the low-frequency information. While, the band- related filtering, e.g., Squirrel, Band-pass, and Band-rejection, the low- and high-frequency highly depend on the medium- -ertuuucrrrruuecy.... and the situation of the medium- freuuuncc is opposite. (2) The more difficult the task, the less obvious the dependency. On Comb and ZINC, the dependency of eigenvalues is inconspicuous.
and from which we have some interesting observations. (1)
(3) On graph-level datasets, the decoder can learn different filters. Figure 55) shows two basic filters. can be seen that $ and S2 have different dependencies and patterns, which different from node-level tasks, where only 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.
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 a permutation eetiiiiriinuvviiiinttt 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.

---

Published as a conference paper at ICLR 2023
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) 10), the NSERC Discovery Grants (No. HMPPN-2001-054493 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.
REFERENCES
Anson Bastos, Abhishek Nadgeri, Kuldeep Singh, Hiroki Kanezashi, Toyotaro Suzumura, and Isa- iah Onando Mulang'. How expressive transformers in spectral domain for graphs? Transactions on Machine Learning Research, 2022.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzaez-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.012611
2018.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low-freqyyncy information in graph convolutional networks. In AAAI, pp. 3950-3957. AAAI Press, 2021.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 122.6203, 2013.
Yunfeng Cai, Guanhua Fang, and Ping Li. A note sparse generalized eigenvalue problem. In NeurIPS, pp. 23036-23048, 2021.
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 NewrlPS, pp. 25058 25071, 2021.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. ICLR, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In NeurlPS, pp. 3837-3845, 2016.
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACI-HLT, pp. 4171-4186. Association for Computational Linguistics, 2019.
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., 17-6): 2020.
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.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks graphs. CoRR, abs/2012.0900 2.09699, 2020.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982, 2020.
Joan Bruma Estrach, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks graphs. In ICLR, 2014.
10

---

Published as a conference paper at ICLR 2023
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.
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):22--150, 2011.
Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. In NeurIPS, 2021.
Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks graphs with chebyshev approximation. revisited. In NeurIPS, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning on graphs. In NeurIPS, 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB-LSC: large-scale challenge for machine learning on graphs. NeurlPS Datasets and Benchmarks, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NeurlPS, 2021.
Renjie Liao. Deep Learning on Graphs: Theory, Models, Algorithms and Applications. University of Toronto (Canada), 2021.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanezosnet: Multi-scale deep graph convolutional networks. In ICLR, 2019.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. In NeurlPS, pp. 20887-20902, 2021.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In ICLR (Poster). OpenReview.net, 2019.
Hadrien Montanelli and Haizhao Yang. Error bounds for deep relu networks using the kolmogorov- arnold superposition theorem. Neural Networks, 129:1-6, 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR. OpenReview.net, 2020.
Antonio Ortega, Pascal Frossard, Jelena Kovacevie, José M. F. Moura, and Pierre Vandergheynst.
Graph signal processing: Overview, challenges, and applications. Proc. IEEE, 10665))808-828, 2018.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR. OpenReview.net, 2020.
Ladislav Rampásck, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. CoRR, ab4/2205.12454, 2022.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
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.

---

Published as a conference paper at ICLR 2023
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 graph. CoRR, abs/2202.08625, 2022.
Elias M Stein and Rami Shakarchi. Fourier analysis: an introduction, volume Princeton University Press, 2011.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. ICLR. OpenReview.net, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPSS pp. 5998-6008, 2017a.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017b.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICI.R, 2018.
Peihao Wang, Wenqing Zheng, Tianlong Chen, and Zhangyang Wang. Anti-oversmoothhng in deep vi- sion transformers via the fourier domain analysis: From theory to practice. CoRR, abs/2203.05962, 2022.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 23341-2222 223662. PMLR, 2022.
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.
PMLR, 2019.
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., (1):4-24, 2021.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. arXiv preprint arXiv:/904 00778777,, 2019.
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 /CML, volume 162 of Proceedings Machine Learning Research, pp. 25261-25279. PMLR, 2022.
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.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. In NIPS, pp. 3391-3401, 2017.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. Al Open, 11, 2020.
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.
12

---

Published as a conference paper at ICLR 2023
A EXPERIMENTAL DETAILS
A.1 DATASETS
Table 5: Detailed information of node-level datasets.
Graphs
Nodes
Edges
Features
Classes
Chameleon
2,277
36,101
2,325
5
Squirrel
5,201
217,073
2,089
Actor
7,600
33.544
932
5
Cora
2,708
5,429
1,433
Citeseer
3,327
4,732
3,703
Photo
7,650
110,081
745
Penn94
41,554
1,362,229
4,814
arXiv
169,343
1,116,243
128
40
Table 6: Detailed information of graph-level datasets.
# Graphs
Avg. nodes
Avg. edges
Min nodes
Max nodes
Tasks
Metric
12,000
23.2
24.9
Regression
MolHIV
41,127
Classification
AUROC
MolPCRA
437,929
26.0
28.1
332
Classification
AP
PCQM4Mv2
3,746,620
14.1
14.6
20
Regression
MAE
A.2 DETAILED EXPERIMENTAL SETUP
Data splitting. In the node classification task, Lim al. (2021) provides five official splits for Penn94 dataset, Hu et al. (2020) provides one time-based split for arXiv dataset. Therefore, we run the Penn94 dataset five times, each with a different split. And we run the arXiv dataset ten times, each with the same split and different initialization. For other datasets, we run the experiments ten times, each with different split and initialization because there is no official splitting. In the graph-level tasks, we use the official splitting provided by Hu et al. (2020) and run the experiments ten times, each with a different initialization.
Optimizer. For the node classification task, we use the Adam (Kingma & Ba 2015) optimizer, as suggested by He et al. (2021): Wang & Zhang (2022). For graph-level tasks, we use the AdamW (Loshchilov & Hutter 2019) optimizer, with the default parameters of =le-8 and (31,8)) (2) (0.99, 0.999), as suggested by Ying et al. (2022); Rampásek et al. (2022). Besides, we also use learning rate scheduler for graph-level tasks, which first linear warm-up stage followed by cosine decay.
Model selection. In the node classification task, we run the experiments with 2000 epochs and stop the training in advance if the validation loss does not continuously decrease for 200 epochs. In the graph-level tasks, with the lowest validation loss for evaluation.
the experiments without early stop. Then choose the model checkpoint
Environment.
The environment in which we run experiments is:
Operating system: Linux version 3.10.0-693.el7.x66.
CPU information: Intel(R) Xeon(R) Silver 4210 CPU 2.20GHz
GeForce RTX 3090 (24GB)
Hyperparameters.
The hyperparameters of specformer can be in Tables and
13

---

Published as a conference paper at ICLR 2023
Table 7: Hyperparameters of node-level datasets.
Hyperparaeter
Synthetic
Chameleon
Squirrel
Actor
Cora
Citeseer
Photo
Penn94
arXiv
Layer
2
2
2
2
2
2
Heads
4
Hidden dim
16
32
32
32
32
32
32
512
Epoch
2000
2000
2000
2000
2000
2000
2000
2000
2000
Learning rate
0.01
le:3
le-3
2e-4
2e-4
2e-4
2e-4
1e:3
Weight decuy
5e-4
1e-3
Te-4
1e-4
Te:3
1e.4
le-3
Transformer dropout
0
0.2
0.1
0,5
0.2
0
0.2
0.0
0.1
Feature dropout
Propagation dropout
0
0,5
0,4
0.5
0.2
0.5
0.2
0,4
0.1
Combination
Small 2,084
Medium 82,445
Medium 74,787
Medium 37,680
Medium 53,885
Medium 126,840
Medium 32,044
Medium 338,179
Medium 1,931,305
Parameters
Table 8: Hyperparameters of graph-level datasets.
Hyperparameter
ZINC
MolHIV
MolPCBA
PCQM4My2
Layer
4
8
8
8
Heads
8
8
8
Hidden dim
160
80
256
320
Graph pooling
mean
mean
mean
mean
Epoch
1000
50
30
150
Warmup
50
5
5
10
Batch size
32
64
64
256
Learning rate
1e-3
le-4
5e-4
le-4
Weight decay
5e-4
le-4
5e-3
0
Transformer dropout
0.1
0.1
0.3
0.1
Feature dropout
0.05
0.1
0.1
0.1
Propagation dropout
0
0.3
0.1
0.1
Combination
Small 529,609
Medium 226,645
Large 3,025,048
Medium 4,117,129
Parameter
B IMPLEMENTATION DETAILS
B. SPECFORMER LAYER
Here we explain how to incorporate the Specformer layer with edge features. Specifically, we first broadeast the node features the edges and filter the mixed edge features. Finally, the filtered edge features are aggregated to yield new node features.
E H .unsqueeze(()) + E,
E S @ E,
A E.uum())
where H -g.xdd is the node feature matrix and E NxXxd is the edge feature matrix.
B.2 CONDENSATION OF CELE-ITTENTIO
In this section, we explain the details the condensation of self-attention. We use B and to represent the self-attention matrix and its condensation.
QK dd
B = Softmax
V
(8)
B Condense B).
14

---

Published as a conference paper at ICLR 2023
Since B is row-normalized, hope the condensation B is still approximately now-normalized, For this purpose, we first sum the columns of B through the pre-defined frequency bands, e.g., Low, Medium, and High, and then average the rows.
B = E
B p.g
|xxsi
AyEfi AuE
where fi and f, the frequency bands, and [1xe,, indicates the number of eigenvalues belonging to the frequency band fi-
Through this condensation strategy, approximately preserve the self-attention matrix's infor- mation and find the frequency bands' dependency patterns.
C MORE EXPERIMENTAL RESULTS
C. EIGENVALUE ENCODING
8=1
E=1
E=1
4D
Eigenvalver
Elgenvalless
Elgenvalvess
30
20
20
20
40
20
40
20
40
60
Dimension
Dimension
Dimension
(a) =
(b)
10
(c) 100
Figure 6: Eigenvalue encoding with different values of c. Best viewed in color.
Here we visualize the outputs of eigenvalue encoding with different values of c. Specifically, we uniformly sample 50 eigenvalues from the region [0. 2] and map them into representations with 64. The results are shown in Figure 6 We can find that when e = 1, only the first 20 dimensions can distinguish different eigenvalues. As increases, the resolution of eigenvalue encoding becomes higher.
C.2 TIME AND SPACE OVERHEAD
We test the time and space overheads of Specformer and two popular polynomial GNNs, i.e., GPR- GNN and BernNet. Polynomial GNNs implemented with sparse matrices and sparse matrix multiplication. We choose three datasets, i.e., Squirrel, Penn94, and ZINC, two for node classification and one for graph regression. For ZINC dataset, sample 2,000 molecular graphs as the inputs of the forward process and omit the edge features that cannot be used by polynomial GNNs.
Setup. In the complexity analysis, mentioned that spectral decomposition only needs to be calculated once and can be reused in the forward process. To perform a fair comparison, we run each model for 1000 epochs and report the total time and space costs. For polynomial GNNs, set K = 10 as suggested by the original papers; for Specformer, we use full eigenvectors for Squirrel and ZINC, and 6,000 eigenvectors for Penn94. The hidden dimension is d 64 for all methods.
Results. From the time overheads in Table D| we can find that the spectral decomposition of small graphs, e.g., Squirrel and ZINC, does not bring much computational cost. And the forward time of Specformer is close to GPR-GNN and less than BernNet. This is because polynomial GNNs need to calculate AX or LX recurrently. Specformer only needs to calculate once, due to the non-local capability. Besides, BernNet needs to calculate all the combinations of L and 2I L, i.e., ΣK (2) (2I (L)) which requires lot of computations. In the Penn94 dataset, we use truncated spectral decomposition to reduce the forward complexity from O(n (d M) + nd(T. To + d)) to O (d M) nd([. [. d)), where is the number of eigenvalues.
(diag(X))U X
15

---

Published as a conference paper at ICLR 2023
Table shows the space overheads, where Specformer is higher than polynomials GNNs because of the dense eigenvectors. One can use fewer eigenvectors to reduce the space cost.
Table 9: Time overheads (s)
GPR-GNN
BernNet
Specformer
Decomposition
Squirrel
4.65
14.86
7.11
2.71
Penn94
14.77
41.26
21.74
629.6
ZINC-2k
15.06
49.78
30.59
1.28
Table 10: Space overheads (MB)
GPR-GNN
BernNet
Specformer
Squirel
1,257
1,277
1,845
Penn94
3,787
3,799
4,993
ZINC
1,417
1,585
4,397
C.3 SPATIAL PERSPECTIVE OF SYNTHETIC DATA
In addition to visual comparisons of learned spectral filters, we also compare Specformer and polynomial GNNs from the spatial perspective. Figure. 7 we show the raw images, ground truth images filtered by Comb filter, i.e. [sin( and images filtered by Specformer and GPR-GNN We can see that Specformer similar to the ground truth, and the contrast of GPR-GNN is darker than the ground truth, implying that Specformer is better than polynomial GNNs at capturing global information.
Raw Image
Specformer
GroundTruth
GPR-GNN
(a) Image #19
Specformer
GroundTruth
GPR-GNN
The term watershed refers ridge
The terna atershed
The terma atershed
The term watershed
ridge
ridge
ridge
Grides Crabbedyy Coterent
divides areas drained by different river systems.
flver sy systmm..
divides areas river system..
Cividss Crainedyy river
(b) Image #28
Figure 7: Synthetic data filtered by GPR-GNN and Specformer. Best viewed in color.
C.4 EXPERIMENTS ON LARGE-SCALE MOLECULAR DATASETS.
PCQM4Mv2 is a large-scale graph regression dataset Huu et al. 2021), which has 3.7M graphs, and the goal is regress the HOMO-LUMO gap. We follow the experimental setting of GPS (Rampásek et al. 2022). Because the original test set is unreachable, we use the original validation set as the test set and randomly sample 150K molecules for validation
Due to the time limitation, we only run Specformer- Medium on the largest molecular datasets. The results are shown in Table 11 We see that due the share of learnable bases, the number of
16

---

Published as a conference paper at ICLR 2023
parameters of Specformer-Mediuee is relatively small. That is say, there is only Transformer block in Specformer ppecformerMeddimm. But the performance of Specformer- Medium is better than the baselines with similar parameters, e.g., GCN, GIN, and GPS-small.
Table 11: Results on large-scale graph dataset PCQM4Mv2.
PCQM4Mv2
Model
MAE())
Param.
GCN
0.1379
2.0M
GCN-VN
0.1153
4.9M
GIN
0.1195
3.8M
GIN-VN
0.1083
6.7M
GPS-small
0.0938
6.2M
Specformer-medium
0.0916
4.1M
GRPE
0.0890
46.2M
EGT
0.0869
89.3M
Graphormer
0.0864
48.3M
GPS-medium
0.0858
19.4M
D THEORETICAL RESULTS
D.1 PERMUTATION EQUIVARIANCE
Proposition 1. Specformer is permutation equivariant.
Proof. We show that Specformer permutation equivariant by proving that all the components of Specformer permutation equivariant. First, the element-wise functions, i.e., eigenvalue encoding, feed-forward networks, and layer normalization, are permutation equivariant because they are applied in node-independent manner. Second, the self-attention mechanism permutation equivariant because (PZP (PZPT) =P(ZZ* ) where Z is the data representation matrix and P is an arbitrary permutation matrix. Third, the construction of learnable bases is permutation equivariant because (PUP (PAP (PUP = P(UAU '
Based all the conclusions above, we prove that Specformer is permutation equivariant.
D.2 APPROXIMATING UNIVARIATE AND MULTIVARIATE FUNCTIONS
Theorem 1. (Uniform convergence of Fourier series) (Stein & Shakarchi 2017) For any continuous real-valued function (x) on [a, b) and f (x)) is piece-wise continuous (a, b] and any O, there exists a Fourier series P(x)) converges to f(x) uniformly such that
mar aSe<b
PP())
f(x) <.
(10)
Theorem (Kolmogorov-Aroold representation theorem) Zaheer et al. 2017) Let f [0, 1 - be an arbitrary multivariate continuous function. Then it has the representation
RR
(II,,.., uM) =
Σ Am (3m)
(11)
with continuous outer and inner functions p 1B2M+1 IR and Φ IR
- 22 The inner function
is independent of the function f.
Proposition 2. Specformer can approximate any wnivariate and multivariate continuous functions.
Proof. We first prove that Specformer can approximate any univariate continuous functions. We set the self-attention matrix to be identity matrix. Then Specformer becomes scalar-to-scalar
17

---

Published as a conference paper at ICLR 2023
function, and the spectral filter is learned through the eigenvalue encoding p()) in Equation 2 a linear transformation w E Rd+1, the eigenvalue encoding becomes a Fourier series:
Given
d/2
4/2
p(X) wp + Σ
W2i sin
10000
EA
Σ
12:11 cOS(
10000
eA
(12)
where the period is determined by 10000 Because the eigenvalues fall in the range [0, based on Theorem [ Specformer can approximate any univariate continuous functions in the interval [0, To choose orthogonal bases, one can set p(A, 2i) sin(iA), p(>, 2i + 1) = cos(iA).
We then prove that Specformer approximate any multivariate continuous functions. Theorem states that any multivariate function is superposition of continuous functions of single variable. Let Φ be the eigenvalue encoding, Am be the self-attention weight, and p be the FFN decoder in Equation 4 Because eigenvalue encoding can approximate any continuous univariate functions and Montanelli & Yang (2020) proves that deep ReLU networks can approximate the outer function p. Specformer approximate any continuous multivariate functions.
18


Reviews:
[{"review_id": "wREO0JC8Ztg", "reviewer": "Reviewer_JCjn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, authors challenge a usual way of designing a spectral function with a dimensional-wise mapping on Graph diffusion. Based on this, authors pay more attention on the global pattern of the specturm rather than single eigenvalue and propose a learnable set2set spectral filter. Based on the new spectral filter, more powerful spectral graph neural network is built. In experiments, authors demonstrate the convincing result for the proposed method.", "summary_of_the_review": "This paper is very interesting, although there are some shortcomings in implementations. It opens an promising direction for GNN. I am optimistic about these issues. Thus I make the recommendation to accept.", "strength_and_weaknesses": "Strength\n1. The idea is novel because all of spectral GNNs only focus on the spectral filter on the single eigenvalues. And it is very easy to find the rationality, even if the whitening is used in images, we still need nxnxk convolution filter rather than nxnx1 convolution filter. Thus I believe the motivation is reasonable, and we all ignore this.\n2. The proposed method also inspires me. Although it still has some drawbacks but still surprises me.\n3. Comprehensive experiments are convincing in my opinion.\n\nWeaknesses:\n1. I am curious if the set2set filter is able to find some interesting patterns from a spatial perspective. Because existing experiments are so quantitive, is there any possibility of digging up some quantitative experiments to demonstrate what kind of pattern the proposed method is able to find and the scalar-based spectral filter cannot?\n2. The computational complexity is quite high because of eigenvalues. So is it possible to explicitly use eigenvalues rather than implictly work on eigenvalues? Because I notice the experiments on small datasets. Although this method is promising, I still hope there is any possibility for a large-scale version.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "nPygH3H9rYk", "reviewer": "Reviewer_Ge61", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes Specformer, a Transformer-based graph spectral filter that captures the magnitudes and relative dependencies of all Laplacian eigenvalues. Specformer is permutation equivariant and can perform non-local graph convolutions. Extensive experiments on the node-level and graph-level datasets demonstrate Specformer's promising performance.", "summary_of_the_review": "The motivation of this paper is clear, and the proposed method is promising. However, Specformer's quadratic time complexity is a serious limitation, and the experimental results are incomplete since some baseline results are missing. Due to the negative aspects of this work, I am slightly inclined to recommend rejection, but I would encourage the authors to address some of the issues raised in the comments in the rebuttal.", "strength_and_weaknesses": "Strengths：\n\n1)\tThe motivation for using self-attention in the spectral domain is clear and inspiring.\n\n2)\tThe authors' theoretical comparisons of Specformer to Polynomial GNNs, MPNNs, and Graph Transformers indicate Specformer's flexibility and universality, which looks sound to me.\n\n3)\tExperiments demonstrate that Specformer can learn a flexible and expressive filter and outperform baselines on node-level and graph-level tasks, particularly on heterophilic graph datasets.\n\n4)\tThis paper is well-written and easy to follow.\n\nWeaknesses:\n\n1)\tThe scalability of Specformer is seriously limited by its quadratic time complexity.\n\n2)\tIt would be helpful to empirically compare Specformer with baselines in terms of time and space overhead, even as the Specformer's time complexity is theoretically analyzed.\n\n3)\tSome baseline experimental results are missing, and no explanation. For example, the results of the Graphormer on MolHIV and MolPCBA are not displayed in Table 3 but are reported in the Graphormer's paper.\n\n4)\tThe experimental datasets are small and a bit old. Using large and latest datasets (such as ogbn-arxiv in OGB and Penn94 in LINKX [1]) may significantly enhance the paper's quality.\n\n[1] Lim, Derek, et al. \"Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.\" In NeurIPS 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RgZWCqTfI4", "reviewer": "Reviewer_T8vi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a spectral graph filter via introducing transformer structure, the idea seems novel, but the following points need to be concerned and explained.\n", "summary_of_the_review": "This paper proposes a spectral graph filter via introducing transformer structure, the idea seems novel, but the following points need to be concerned and explained. The author introduces some weaknesses for current spectral fitler, but the explaination is not convincing enough. How to understand the benifits of Eq.(2)-the EE form which encodes the eigenvalues? The proposed model needs to calculate all eigenvectors U and eigenvalues (O(n^3)), the complexity analysis is not true. More questions can been seen above.", "strength_and_weaknesses": "1. The author introduces some weaknesses for current spectral fitler, but the explaination is not convincing enough. \n1) At first, the authors propose -- \"mapping a single eigenvalue to a single filtered value, thus\nignoring the global pattern of the spectrum\", which means that the interaction among eigenvalues are lacked. However, how to understand the interaction among different eigenvalues (frequiences in Graph Signal Processing)? \nI think that this assumption should be supported via theoretical analysis. \n2) Secondly, the authors propose -- \"these filters are often constructed based on some fixed-order polynomials, which have limited expressiveness and flexibility\". \nIn fact, the polynomials paradigm was proposed to avoid the huge cost of eigenvalue decomposition for calculating U of Laplacian matrix. \nHowever, the proposed model needs to calculate U, which introduces huge cost. In other words, we can also learn the fiter parameters based on other networks (without transformer) if we ignore the cost of eigenvalue decomposition. \nThus I think the proposed model does not handle the trade-off between computation cost and expressiveness.\n2. I also have some questions for the architecture of proposed model, includes,\n1) How to understand the benifits of Eq.(2)-the EE form which encodes the eigenvalues? \n2) The proposed model needs to calculate all eigenvectors U and eigenvalues (O(n^3)), the complexity analysis is not true. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-VnVtEz1XP", "reviewer": "Reviewer_ur3z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces Specformer, a novel Transformer-based architecture for node- and graph-level prediction tasks. A Specformer layer embeds structure (eigenvalues) and node features separately, and then combines the obtained representations using graph convolutions. The model performs self-attention in the spectral domain. Experiments on synthetic and real-world datasets show the effectiveness of the proposed method.", "summary_of_the_review": "Overall, the paper is relatively well-written and introduces a promising architecture for node- and graph-level prediction tasks. I have raised some concerns regarding the significance of the empirical evaluation, the computational cost/scalability, reproducibility, and clarity. Also, the paper provides limited theoretical insights about the proposed architecture, and the motivation behind some model choices is unclear/ not strong. Therefore, I am ranking this paper as marginally below the acceptance threshold.", "strength_and_weaknesses": "\nStrengths\n - Simplicity. The idea is easy-to-follow. \n - The paper introduces synthetic datasets for which it reports the approximation capability of Specformer.\n - Good performance. The proposed method yields good performance overall. For instance, it gets 0.066 MAE on the ZINC dataset.\n\nWeaknesses\n - Limited evaluation setup. Despite the promising results, the paper lacks relevant benchmarks for node-level tasks and only considers molecular datasets (small graphs) for graph classification. \n - It is unclear whether the computational overhead of the proposed method is significant or not, and how it compares to other GNNs. \n - The paper provides limited theoretical insights about the proposed architecture.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster