SpecTRA: Spectral Transformer for Graph Representation Learning
Authors: Anson Bastos
Abhishek Nadgeri
Kuldeep Singh
Hiroki Kanezashi
Toyotaro Suzumura
Isaiah Onando Mulang'
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Representation Learning
Transformer
GNNs

Abstract: Transformers have recently been applied in the more generic domain of graphs. For the same, researchers proposed various positional and structural encoding schemes to overcome the limitation of transformers in modeling the positional invariance in graphs and graph topology. Some of these encoding techniques use the spectrum of the graph. In addition to graph topology, graph signals could be multi-channeled and contain heterogeneous information. We argue that transformers cannot model multichannel signals inherently spread over the graph spectrum. To this end, we propose SpecTRA, a novel approach that induces a spectral module into the transformer architecture to enable decomposition of graph spectrum and selectively learn useful information akin to filtering in the frequency domain. Results on standard benchmark datasets show that the proposed method performs comparably or better than existing transformer and GNN based architectures.

Under review as a conference paper at ICLR 2022
SPECTRA: SPECTRAL TRANSFORMER FOR GRAPH REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Several positional and structural encodings are recently proposed into vanilla transformer architecture to overcome its inability to model graph's 's positional in- variance and topology. However, in addition to graph topology, graph signals could multi-channeled and contain heterogeneous information which cannot be inherently captured by the transformer. Hence, we propose an approach to induce a spectral module into the transformer architecture to enable decomposition of graph spectrum and selectively learn useful information akin to filtering in the fre- quency domain. Empirical results suggest that SpecTRA provides homogeneous performance gain against vanilla transformer across all tasks standard bench- marks. Furthermore, incorporating SpecTTRA instead of vanilla transformer model with recently proposed position encoding schemes have resulted in comparable better performance than existing transformer and GNN based architectures.
INTRODUCTION
Several graph neural network (GNN) approaches have been devised as generic and efficient frame- work to learn from graph-structured data for tasks such graph classification, node classification, graph regression, and link property prediction (Zhou et al. 2020). Among them, message-passing GNNs (MPGNNs) have been prominently used obtain latent encoding of graph structures, achiev- ing good results on related tasks (Gilmer et al.] [0117] Veličković et al., 2018 Xu et al.] 2019a). Although effective, these methods suffer from performance issues such as over-smoo (Zhao &
Akoglu 2020), suspended animation (Zhang & Meng. 2019). and over-squashing (Alon & Yahav) 2021 Recently, researchers (Zhang et al. [2200 Li et al. 2018) have attempted to use transformers Vaswani et al. (017) for graph representation learning. However, transformers are inherently inca- pable of learning the topological information of graphs (Dwivedi et al., 2020). Hence, more recent works have added gamut of effective positional and structural encoding methods (Mialon et al.) 2021
Kreuzer et al. 2021) to alleviate limitation of transformers to learn topological information.
Background and Hypothesis: Viewed from classical signal processing domain, signals graph could contain heterogencous information spread over a wider frequency domain (Ortega et al.] 2018 The message passing graph convolutional networks (MPGCNs) such GCN (Kipf & Welling 2017) and GAT (Veličković et al., 2018) have low-pass characteristics (Muhammet et al., 2020). Furthermore, researchers aim go beyond static low or highpass filters design adaptive fil- ters to capture entire graph spectrum in GNNs (Gao et al. 2021
(022]/or Bo et al. [202 Chien et al. 2021 We argue that similar issue plagues the transformers that cannot effectively segregate the noise from the signal for the entire spectral components of a graph. Gleaning from the work on MPGNNs as transformer can be special case of GNNs (Joshi 2020), we we hypothesize that inducing transformers with the ability to selectively use the signals in the frequency domain will enable better representa- tion learning on broader range of tasks. As graphs have different topologies, we further postulate that having an approach to dynamically select filters, opposed to dataset-specific single static fil- ter, will be more expansive to permit effective learning of graph representations using transformers.
This work, instead of devising new position encoding scheme, proposes novel direction. Our work aims to empower transformers to learn the essential components of the graph spectrum while filtering out the noise. We propose SpecTRA that effectively integrates the attention of the transformer with the spectrum of the graph. SpecTRA consists a filtering module built on top of the vanilla transformer (Vaswani et al. 2017) to learn distinct filter coefficients for
Proposed Approach:

---

Under review as a conference paper at ICLR 2022
each input graph. The transformer naturally gives diverse attention sub-spaces, which are utilized by SpecTRA to design multiple filters covering a broad spectrum of the graph. Specifically, we utilize the spatial information learned by the attention heads of the transformer to dynamically de- cide the filter coefficients. This enables interpreting the association between a particular frequency component with each head for given graph. Furthermore, it also helps select the useful range of information in the frequency domain for different sub-spaces (attention heads in SpecTRA's case). Our rationale emerges from the following: 1) If the graph spectrum consists of several underlying components, which are relevant for different bub-graphs, then it is paramount to dynamically learn filter coefficient. This also provides an extra advantage conceming interpretability in spectral space per graph (cf., section 5.1). 2) In cases where certain classes are skewed, a task-specific filter would learn generie coefficients for the majority class, keeping a limit on the number of filters. SpecTRA handles these special cases by learning filters after observing the input graph (cf., section A.5)
Contributions: To summarize, this work make the following key contributions:
Our primary contribution is SpecTRA, novel approach for empowering vanilla trans- former with the ability to perform graph-specific filtering in multiple sub-spaces of the attention heads. We study the efficacy of SpecTRA by conducting extensive experiments on standard benchmark datasets of graph classfficaionn/eeression and node classification resulting in superior performance compared to vanilla transformer.
We provide an exhaustive empirical study on the effect of inducing a variety of recently proposed consformer-basee positional encoding schemes (Dwivedi et al. 2020 Kreuzer ct al., 2021; Mialon et al., 2021] into the SpecTRA architecture. Empirical results show comparable or better performance against current statc-of-the-art transformer and GNN based approaches. Hence, transformers, when induced with the ability to decompose and attend to signals spectrally, can effectively capture representations on wide range of tasks complementing the effect of position encoding schemes.
The remainder of the paper is organized as follows: we describe the related works in section 2 Section provides the preliminaries and problem definition. In section { we explain the proposed approach for graph specific dynamic filtering. Dataset details, experimental results, and ablations are given in sections 5 and 5.1 Section 6 concludes the paper.
RELATED WORK
GNNs and Graph Transformers: In this section, we stick to the work closely related to our ap- proach (detailed survey in (Chen et al.] 2020b)). Since the early attempts for GNNs (Scarselli et al.) 2008 many variants of the message passing scheme were developed for graph structures such as
GCN Kipf & Welling 2017). GIN (Xu et al. 2018), and GraphSAGE (Hamilton et al., 2017). The message passing paradigm employs neural networks for updating representation of neighboring nodes by exchanging messages between them. The use of transformer-style attention to GNNs for aggregating local information within the graphs is also an extensive research topic in recent literature
[Thekumparmmpi et al. 2018 Shi et al. 2020: Li et al. 2018). Dwivedi & Bresson (2020) the eigenvectors of the graph laplacian to induce positional information into the graph. Kreuzer et al.) (222I) propose learnable position encoding module that applies a transformer on the eigenvectors and cigenvalues of the graph laplacian. Ying et al. (222)) provide the concept of relative positional encoding in which the positional information is induced in the attention weights rather than in the input by obtaining correlation matrices of the spatial, edge, and centrality encoding. Similarly, Mi- Mi- alon et al. (202T) induce relative position information in the form of diffusion and random walk kernels along with structural information using the Graph Convolutional Kernel network (GCKN). In contrast with existing transformer-baat based attempts that inherit vanilla transformer model (Vaswani et al.) 2017) for inducing position and topological encoding, we aim to improve the capabilities of the vanilla transformer model by empowering it to decompose the spectrum of a graph.
Filtering in the frequency domain is generalized to graphs using the spectral graph theory (Chung et al. 1997; Shuman et al.) 2013). The GCN model (Kipf & Welling, 2017) and variants such as (Zhang & Mengi 2019) approximate convolution for graph structures in the spatial domain. However, these models suffer from operating in the low-frequency regime, leaving rich information in graph data available in the middle- and high-frequency components (Gao al.
Filters on Graphs:
2

---

Under review as a conference paper at ICLR 2022
Other approaches in the spectral domain attempt to reduce the computationally complex eigen decomposition of the laplacian by adopting certain functions of the graph laplacian such as Chebyshev polynomials (Defferrard et al. 2016), Cayley polynomials (Levie al. 2018). and auto regressive moving average (ARMA) filters (lsufi et al. 2016). These approaches focus on designing specific filters with desirable characteristics such bandpass and highpass. Our work focuses the design of learnable filters, whose frequency response can be represented in polynomial functions in multiple sub-spaces of the signal. Gao al. (202I) is closely related to part of our work which also designs filter banks, albeit task-specific, for heterogeneous and multi chatn-chaanel signals on graphs. However, our work differs from Gao et al. (202I) in that we learn graph-specift filters enable interpretability in spectral space per graph and filtering into the transformer architecture.
2021
3 PRELIMINARIES AND PROBLEM DEFINITION
Graph Fourier Transform: We denote a graph as (V,e) where V is the set of N nodes and represents the edges between them. The adjacency matrix is denoted by A. Here, we consider the setting of an undirected graph, hence, A is symmetric. The diagonal degree matrix D is defined as (D)a = Σ, (A)sj- The normalized laplacian L of the graph is defined as L = D AD 3. The laplacian L can be decomposed into its eigenvectors and eigenvalues as:
where U is the N N matrix; the columns of which are the eigenvectors corresponding to the eigenvalues Åι, A2,-..,AA and A = diag( (1 A2.-.., Au)). A.)...
Let X E Rxxd be the signal on the nodes of the graph. The Fourier Transform X of X is then given as: X = U-X. Similarly, the inverse Fourier Transform is defined as: X U.. Note U is the transposed conjugate of U. By the convolution theorem (Blackledge 2005). the convolution of the signal X with a filter G having its frequency response G' is given by (below, Um is the m²th node in the graph):
(X (um) ((A))G(A)UU
Σ (U=N)(A))GAA)))U Ax) = UG(AJU" ((MA)))(X(())))))) (I)
Transformers and Position encoding: The recent works (Dwivedi & Bresson 2020
Kreuzer et al,
2021) established the necessity of encoding schemes for inducing positional encoding into the trans- former architecture. The relative encoding schemes proposed by GraphiT (Millon et al., 2021 use diffusion and random walk kernels for relative positional encodings. The diffusion kernel KD for graph with laplacian given by the equation below,
KD = - lim (1 (1- L)"
3
pinn
For physical interpretation, diffusion kernels can be interpreted as the amount of substance that accumulates at a given node if injected into another node and allowed to diffuse through the graph. Similarly, the random walk kernel generalizes this notion of diffusion for fixed-step walks on the graph. described by the equation below,
KORW = =( -T-
We can see that above equation becomes the diffusion kernel if y 1 and p + inf. However, the difference with respect to the diffusion kernel that the random walk kernel is sparse. GraphiT also makes use of GCKN (Chen et 2020a) for learning structural position encoding and we inherit in our approach describe in Section 4 We refer the readers to (Mialon et al., 2021) for more details.
Spectral GNN: Spectral GNNs rely on the spectral graph theory (Chung al. 1997). Consider graph with U as its eigen vectors, À the eigen values, and L the laplacian. The graph convolution operation the frequency domain can be written as below,
H
Udiag(Gsa.)U'I
where H is the feature vector of the 1th node in the (1)th th layer, di is the dimension of the signal in the 1th layer, G.,u. i is the learnable weight vector for the 8th and 5th node in the tth layer. This
3

---

Under review as a conference paper at ICLR 2022
dog
Module
Scaled Product Altention
Arcndoon HOaT Maps
Leamed Filer Coeflitents
the MPSNN
Lineer
Lineor
Postioo Encoding mraau
Dynamic Filniing Moxulo
Mult Heaaed Allention with Dynamic Filtriig Moduee
Figure I:
SpecTRA architecture. Besides introducing a dynamic filtering module for learning mul- tiple filters per attention head, position encoding schemes are used in plug-and-play manner.
formulation is non-transferable multigraph learning problem Gūj, is re-parametrized as below,
Muhammeet et al. 2020). Thus,
G B[W!) w!..... w!.5]
where E RNXS S is the number of convolutional supports and W is the learnable matrix. The Equation 4 depends on the computation of the eigen vectors U of L, which is computationally costly for large graphs. In our work, we consider the polynomial approximations as proposed by Hammond al. (011). Specifically, the frequency response of the desired filter can be approximated as,
K
(A)
(5)
where T(k) is the polynomial basis such as Chebyshev polynomials (Defferrard al., 2016). Ä 2A Amus I, Amar is the maximum eigen value and a the corresponding filter coefficients.
recursive formulation could be used for the Chebyshev polynomials with basis To(x) = 1, (z) and beyond that (xx 2xTx-1(x)) T2-2(x). Thus, the convolution operation in Equation can be approximated as
K (UTT(UA
K Σ (T)
x T'
Σ k=0
k=
k=
This corresponds an FIR filter of order K (Smith al. 1997.. Setting learnable parameter help us learn the filter for the upstream task.
Problem definition In this work, aim to learn the filter coefficients from the attention weights of the transformer. Formally, given the transformer attention for the head h at layer / as A E: R XN aim to define mapping M RNNxN + RK where K is the filter order. The mapping M would take us from the space in the attention weights to the filter coefficient space.
4 SPECTRA:SPETRAL TRANSFORMER
In this section, we present our approach, SpecTRA. We first describe the notion of dynamic filtering module of SpecTRA architecture followed by its position encoding module (cf., Figure
4.1 MULTI HEADED ATTENTION WITH DYNAMIC FILTERING MODULE
We view the graph as of node features to be fed to the vanilla transformer Vaswani et al.) 2017) that learns the pairwise similarity between these nodes using its attention mechanism as follows:
QKT
AttentionW eights (Q, = softmaa
Voont
4

---

Under review as a conference paper at ICLR 2022
Here, Q" Whxx and K" W where W W E Adouxxxa are the projection matrices for the query and key respectively for the head The output X at the head h can be obtained from:
QK? )V
X Allentionn (Q, V) softmart
Vdlut
Learning filter coefficients: In order to obtain the filter coefficients from the weights of each atten- tion head, we message passing framework. The spectral and spatial domains interchange- able, and transformers traditionally learn good latent representations of spatial domain (Vaswani al. 2017: Devlin al. 2019). Hence, attention map provides inference the connectivity of a graph implicitly, using which, we can deduce the frequency band to filter out the noise. each node's is signal 2; is considered with its neighhorhood (x;,) which represents the non-zero attention weights obtained from Equation 7
then the message passing is defined as:
x zm A(ryla, E (xx))) 4+1 = U( .....)
where ot and dim are the signals and the aggregated message at node v; in the layer l. Here, A and U the aggregation and update functions respectively. This framework enables the usage of popular message passing schemes such as GCN (Kipf & Welling 2017). For example, in GCN, the aggregation is simple projection of the signals followed by summation weighted by the normalized laplacian with self loops. Next, the updation is an activation function such as ReLU. The final equation is now represented as below:
h,-11 a( Σ 4r.:l(a.h) )
(TEA((Z))
where xr)"" is the node embedding for the j node in the 1-th layer of the GNN(to learn coefficients) for the /-th head of the transformer, = I D AD- is the normalized laplacian and W is the learnable projection matrix at layer 1. This GNN is common for all the heads and all layers of the transformer. Here, the node embeddings reside in the coefficient space i.c. X E RN*K" where K the order of the filter. For learning the filter coefficients we initialize the node embeddings with prior of the filter depending on the task. For an all-pass filter we could use vector of all ones as the initialization. This choice of prior is justified by property 4.1 (cf., Appendix
[.. for proof).
Property 4.1. The filter coefficients consisting of the vector of all ones is all-pass filter.
After the I-thh message passing, the vector obtained from Equation 9 is given to a readout function such global average pooling followed by simple feed forward network to obtain the final filter coefficients a", per attention head, as below:
N
a² MLP
(10)
where xf is the vector at node x; in the h-th attention head obtained from Equation 9 Dynamic Filtering Module: We use the filter coefficient a² to obtain the appropriate filter fre- quency response defined as:
K
G
(i)
(11)
where K is the filter order. The desired filter response H² at head h can then be obtained from G as observed E
Hh= G² -C -' Σ a (
The filter outputs from each head is concatenated to get the filtered output which is further concate- nated with the attention output X, followed by an MLP, with appropriate normalizations, for the output of the encoder layer:
Hh X MLP( X = Norm(M e H))
h
5

---

Under review as a conference paper at ICLR 2022
This could then be used in the upstream task of classification, regression, etc. In order to learn dis- tinctfiiter coefficients for each head we add a regularization term to the objective. The regularization tries to keep the coefficient vectors orthogonal to each other. It does so by taking the Frobenius norm (Horn & Johnson 1990) of the gram matrix of X whose columns consist of the coefficient vector of each head. Formally, define a² R and X [a', a² a.. of heads and k is the filter order. The regularization term is given by [[x x) @ (1 122, where I E Ra is the identity matrix and is the hadamard product. The below theorem (proof in Appendix A.1 justifies the proposed method.
Rexx where h is the number
Theorem 4.1. Assume the desired filter response G(x) has m + 1 continuous derivatives on the domain [-1, 1]. Let G(x) denote the nhth order approximation by the polynomiallchebysser filter and Sh G(z) denote the learned filter, C3 be the first absolute moment of the distribution of the fourier magnitudex of J (function learned by the network), h the number of hidden unity in the network and N the number of training samples. Then the error between the learned and desired frequency response is bounded by the below expression
(G(z)- S G(z)= 0( -
nC + N
hn² (og(()) + n -))
The above theorem argues that the Chebyshev polynomials are able to learn any smooth function. Using injective aggregators in GNNs and universal approximators in MLP, we can approximate these coefficients to the desired precision given by the bounds. The input to the GNNs could be divided into two parts: the input graph indicating the connectivity of nodes and the signals on the graph. In this work, aim to study if the spectral components could be identified by using the spatial connectivity pattern of the signals on the original graph obtained from the attention maps of the transformer. This justifies the proposed architecture, in which graph is constructed with the edge weights taken from the attention weights and fed to a GNN for learning the filter coefficients. These coefficients then used in a spectral GNN in which the input the original graph with node embeddings as learned from the transformer. The output of this is then fed to further transformer layers, and the process is repeated. The input to the first transformer is the node/edge attributes itself. We leave using the connectivity structure imposed by the original graph for future works.
4.2 POSITIONAL ENCODING SCHEMES
In SpecTRA, we learn the pairwise similarity between graph nodes inheriting the attention mecha- nism of vanilla transformer follows:
QKT Vdout.
Attention (Q, KVV) softmar
VV
(12)
Here = W K" -
Wh W E Rdooxxxiie are W and VT = W where Q: Ki the projection matrices for the query, key and values respectively for the head Following GraphiT (Mialon et al.) (02T), we share the weight matrices for the query and key matrices for learning positive semi-definite kernel. For the input features we use the node attributes, if provided, along in (Dwivedi & Bresson 2020). The static encoding
with the static laplacian position encoding, in the form of the laplacian eigen vectors is simply added to the node embeddings. For the relative positional encoding follow GraphiT and use the diffusion (Kn) and random walk (K kernels (cf., Equations and 3). The attention using the relative positional encoding schemes is now:
QQ"
Attention V) softmar(expl Vdout
K2)V
(13)
Here, Kp is the respective kernel being used i.c. K2 KD. Krw- We also borrow from the positional encoding scheme of SAN (Kreuzer et al.] 202I) that allow usage of the edge features F. E NNxNxdx xd,,, Formally, the attention weights wef between the nodes i and in the th layer and

---

Under review as a conference paper at ICLR 2022
th attention head is given by the below equations
With X(i] о Whth X + W. ]
if i and j are connected in sparse graph
ki oj
dout
Wakk X o Wa XLI O W E
otherwise
dout
so softmar
if and are connected in sparse graph
1 +
wi
fmmar
Way
otherwise
1+7
where Q Wkk W.i are the projection matrices corresponding to the query, key and edge vectors for the real edges and W W. W22k' are the projection matrices corresponding to E
Q the respective vectors for the added edges in the Ath head and n*h layer as in (Kreuzer et al. 2021
We further employ GCKN (Chen et al. 2020a) to encode graph's topological properties.
Limitations The space and time complexity of our method is O(N2) for full attention. This could be alleviated by using sparse attention (cf., Table 2). One may also use kernel methods as in (Choro- manski et al., (222I) to reduce the number of nodes in the graph and then apply the transformer on the reduced graph. Similar to vanilla Spensforerr,SpeTTR. cannot induce positional encoding on its own. It is yet to be explored if learning position encodings could be incorporated into the proposed method. We leave these directions of exploration to future works.
EXPERIMENT RESULTS
Can multi-headed attention combined with dynamic graph filtering improve SpecTRA's ability over base transformer for graph representation
We aim answer following research questions: RQI:
learning? RQ2: What is the impact of recently proposed position encoding schemes on Spec
RQ3: What is the efficacy of graph-specific filters on the performance of SpecTRA?
Datasets, Settings and Baselines: We use widely popular datasets (Kreuzer al., 2021 Mialon
et al., 2021 Hu et al. 2020): MUTAG, NCI1, and the AGBG-MolHIY for graph classification;
PATTERN and CLUSTER for node classification; and ZINC for graph regression task. Further de- tails are in the Appendix A.2 We borrow experiment settings from (Mialon et al. 2021
Kreuzer
al. 202T). The GNN and transformer baselines are listed in Table
TRe Contigurations: For fair and exhaustive comparison, we provide six variants of Spec-
TRA: 1) Spec Tra-Baee to compare against vanilla transformer without position encoding module
(cf., section 4.2 2) Lae contains static position encoding from Mialon al. (2021), ), 3) SpecTRA+3RW consists of position encoding based on 3tep RW kernel from Mialon et al. (2021), 4) SpecTRA +ETTTRAAGCK++++TT that uses GCKN (Chen et al. (020a) in addition with 3-step RW kernel to induce graph topology, 5) SpecTRA+LPE+Fiu with learnable position encoding (Kreuzer et al.) 202T) with full attention. 6) SpecTRA+LPPE. Sparse inheriting learnable position encoding from
Kreuzer et al. (202I). with sparse attention on the graphs
5.1 RESULTS
SpecTRA-Bass outperforms vanilla transformer (Table across all datasets establishing the positive impact of combining dynamic filtering with multi-headed attention into SpecTTRA architecture (suc- cessfully answering RQ1). We observe (Table 2 that for the smaller MUTAG and NCII datasets, SpecTRAA achieves the best results against baselines using the structural encoding of GCKN. It indi- cates that these datasets benefit more from structural information. The results of the other SpecTRA variants are comparable or better than the transformer-based (SAN, Graphi'T-Laph GraphiT-3RWV and GNN baselines. On OGBG-MolHIV and PATTERN/CLUSTER graph and node classifica- tion tasks, learnable position encoding has most positive impact on SpecTRR. Graphformer reports the highest value on MolHIV. However, its parameters are 47M compared to zs 500K from Spec- TRA+LPE, GCN-based models, and SAN. Notably, we see that SpecTRA performs exceptionally well on the graph regression task of ZINC with a relative decrease in the error of up to 50%. Po- tential reason could be SpecTRA' ability to learn diverse filters that are distinct for each graph (c.f,

---

Under review as a conference paper at ICLR 2022
Models
MUTAG
NCI1
ZINC
MolIIV
PATTERN
CLUSTER
Vanilla Transformer
82.2 = 6.3
70.0 = 4.5
0.696 = 0.007
65.22 5.52
75.77 = 0.4875
21.001 1.013
SpecTRA A-Aasese (ours)
73.7 1.4
0.412 0.004
65.77 3.838
78.65 2.509
30.351 2.669
Table 1: Results on graph/node classificaton//eerrssion Tasks (RQI). Higher (in green) value better (except for ZINC). Means and uncertainties are derived from four runs.
Models
MUTAG ACC
NCII
ZINC MAR
MolHIV % ROC-AUC
PATTERN ACC
CLUSTER ACC
ACC
GCN Kipf & Welling 2017
78.9
75.9 a 1.6
0.367 a 0.011
76.06 0.97
71,892 = 0.334
68.498 e: 0.976
Gatedlat Hrestmn & paaren 2017
0.282 + 0.015
85.568 0.088
73,840 + 0.326
GrapSSAGE
0.002
63.844 0.110
GAT
Velickon orale 4018
4.5
74.8 4.1
0.384 1 0.007
78.271 a 0.186
70.587 & 0.447
PNA
Cols0 ef 20100
0.142 0.000
79:05 + 1.33
GIN
2018
82.6 6.2
81.7
1.40
85,387
64,716 1,553
Grapbormer (ing ot al. 202]
0.122 0.006
80.51 1
-TT-se DWiveer & Bressen 2020
0.226 0.014
0.068 84,808
73, 73,169 O. 6.666
GiI-full Dirpali
0.049
56.482 3.549
27.121 8.477
SAN-Sparsc Kiezer K744
74.1 2.6
80.5 1.3
0.198 1 0.004
76.61 0.62
81,329 2.150
75.738 106
full
Krouze cru 2021
2.99
0.139 a 0.006
77.85 0.65
86.581 0.037
76.691 =: 0.247
Graphil-fapp:
2021
5.9
1.9
0.507 0.003
1.76
76.201
0.7
18.136 1,997*
GraphiT-3RW Miatonn sl
2011
83.3
3.66
0.244 0.011
64.22 4.94*
76,694 = 0.921
21.311 0.478*
GraphiT-3RW--. -RW-GCWN----G (Mtaion et 2021
90.5 7.0
81.4
0.211 a 0,010
2.73* 53.77
75.850 a 0.192*
69.658 a: 0.895*
SpecTWA Laph: (ours)
2..
2.6
DX077 0.00
66
78.800 78.808
19. 30,3666 3.818
SpecTRA + 3RW (ours)
8.60
78.5 1.3
0.104 1 0.005
59.95 3.91
77,285
1.146
68.572 +. 2.16
SpecTRA GCKN+ 3RW (ours)
92.9:::1.6
03.0
0:068 e 0.002
53.50 5.889
77.86 0.573
67.507 + 2,856
SpecTRA I.PE
1..2++1.6
738
0.1836
0.002
76.88 0.573
W6.52 0:013
76,750 0.296
SpecTRA + LPEASppure (ours)
7..2
81.0
0.1581 4 0.001
78.10 0.303
86.30 0.024
77,224 0.111
Table 2: Impact of external position encoding schemes (RQ2). For a dataset, Green and Grey cells represent the highest and the second best result, respectively. The baselines values are from (Kreuzer al. 2021 Mialon et al. 2021) and its additional values with * are calculated by us.
Appendix A.5 An important observation is that no position encoding scheme provides homoge- neous performance gain across all datasets for SpecTRA and it supports our choice to use them as a plug-in in (answering RQ2). Hence, it is still an open research question to propose a position encoding scheme that provides homogeneous performance gain across all tasks agnostic of the datasets.
Models
MUTAG
NCI1
ZINC
MolHiV
PATTERN
CLUSTER
SpecIRAA-Bsee
87.2 + 2.6
73.7
0.412 = 0.004
65.77 + 3.838
78.65 2,509
30.351 2.669
SpecTRA-ARMA
85.1 +1.3
7.12
0.355 0.007
65.45 + 4.237
76.93 0.279
20.390 + 2.859
SpecTRA-Static
83.3
7.8
0.470 # 0.002
67.10 3.647
76.03 0.861
20.995 0.005
Table 3: Comparing SpecTRA- against (RQ3): 1) SpecTRA-Static that uses static filter and 2) SpecTRA-ARMA which changes the filter in base configuration to ARMA.
Ablation Studies We created another SpecTRA configuration (SpecTRA-Statics where the filter is static per dataset based attention heads. Our idea here is to understand the impact of combin- ing multi-headed attentions with filter. From Table 3, we clearly observe the empirical advantage of SpecTRR SpecTRRA-Base More importantly, graph-specific filters aim for interpretability in spectral space per graph. Similar to attention weights, learning graph-specific filters facilitates the understanding of which nodes interact the spectral domain and which filter helpful for the task. In some cases, it may benefit from learning representations by aggregating from connected neigh- bors, which a low pass filter would do. Whereas in other cases, the task would benefit learning from unconnected distant nodes, which may be graph dependent. For instance, in Figure 3 we see that for sparse graphs (graph (a) (c)) the filter response has a prominent magnitude for the lower com- ponents of the spectrum along with some components in the middle regions of the spectrum. On the other hand, for relatively dense graphs, we see a relatively less prominent low frequency response and many heads learning to focus on the higher frequency components of the spectrum. In a sense, this enables aggregation of nodes that are distant in the graph and helps in providing interpretation as to which nodes interact in the spectral domain. Note that existing graph-specific attention mech- anisms, such as GAT, learn only low pass filters (Muhammet et al. 2020) and cannot perform such an aggregation. Also, the spectral GNNs (cf., section 2) that learn filters for the entire dataset
8

---

Under review as a conference paper at ICLR 2022
(a)
K
(c) =
(d) K
K
Figure 2: Aggregate Filter Frequency response (K is filter order). (a) (b) MUTAG and (c) (e) are on NCII. X axis shows the normalized frequency with magnitudes on the axis.
unable to perform similar aggregation in graph-specific manner which may be beneficial in some cases (cf., [A.4). Also, the learned filters have different frequency responses specific to the dataset as they are tuned to the data characteristics (cf., Figure 2). These observations justify our rationale filters and successfully answering RQ3. We note, equation represents
to propose
(b)
(c)
(d)
(c)
K
(b)
i
Figure 3: Filter Frequency response individual graphs. Graph (a) is from MUTAG and, (b)~ (c) are from the NCII dataset and Figures (f) ~ (j) are the corresponding frequency responses. X axis shows the normalized frequency with magnitudes the Y axis.
a polynomial filter using the Chebyshev polynomials (Defferrard et al. 2016). Polynomial filters (Hammond al., (01I) are smooth and have restrictions that they cannot model filter responses with sharp edges. Hence, we devise TRAAAAAA that uses rational filters such as ARMA (Isufi al. 2016). Our idea here is study the empirical efficacy of these filters. It can be observed from Table that SpecTRA-ARMA resulted in lower performance than SpecTRA-Bass
most of the datasets. However, on ZINC, there is an improvement using ARMA filters as compared to Chebyshev polynomial filters. Also CLUSTER, we observer sharp increase using SpecTRA- but not with SpecTRA-
Hence, we conclude that filter response and empirical predictive performance could be orthogonal objectives, and it becomes trade-off to decide which type of filter to apply for a given task.
Base as compared SpecTRA-S
CONCLUSION
In this work, we have introduced novel wransformer-based approach for graph representation learn- ing. Our model SpecTRA aims to effectively learn multiple filters per attention head to capture heterogeneous information spread over wider frequency domain. Furthermore, learning graph- specific filters provide interpretabilityy in spectral space per graph, which is not the case in a dataset- specific static filter. Experiments standard datasets of variety of tasks suggest clear empirical edge on vanilla transformer. Also, using recently proposed position encoding schemes as plug-ins in the flexible architecture of SpecTRA resulted in better comparable state-of-the-art performance.

---

Under review as a conference paper at ICLR 2022
7 ETHICS AND REPRODUCIBILITY STATEMENT
In this work, we present significant progress in graph representation learning using transformers. Knowledge representation from the data (mainly graphs) is important goal that human beings seek for reasoning along with the advancement of technology. Many recently proposed transformer approaches rely on static frequency filters (including one of our configuration Spec A-Statiic compared to our proposed dynamic filtering approach. Furthermore, we employ widely used public datasets for graphs. When it comes to who may be disadvantaged from this research, we do not think it is applicable since our study of addressing the dynamic filtering capabilities of the transformer, which still at an early stage. Additionally, there no concrete evidence in the literature that signals on the graphs causes bias or ethical concerns for effectively learning graph representations.
Having said so, we are fully supporting the development of ethical and responsible AI. The poten- tial bias in the standard public datasets that may lead to wrong knowledge needs to be cleaned or corrected with validation mechanisms. We are also aware of energy consumption of GPUs used in the empirical evaluations and support development of Green AI for sustainable development of ML research.
Regarding reproducibility: upon acceptance, we will publicly release code with detailed user instruc- tions to reproduce our empirical values. We have provided an additional appendix section including GPU size and all other hyper parameters needed reproduce this work. Also, have made sure that in methodology, all relevant equations are presented in the main section the paper to clarify our proposed approach.
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
A. Barron. Approximation and estimation bounds for artificial neural networks. Machine Learning, 14:115-133, 1991.
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. ICMI.2021, 2021.
Jonathan M. Blackledge. Chapter 2 2d fourier theory. In Digital Image Processing, Woodhead Publishing Series in Electronic and Optical Materials, pp. 30-49. Woodhead Publishing, 2005.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-freyyyncy information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 35, pp. 3950-3957, 2021.
Xavier Bresson and Thomas Laurent. arXiv:1711.07553, 2017.
Residual gated
graph convnets.
arXiv preprint
Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph- structured data. In International Conference on Machine Learning, pp. 1576-1586. PMLR, 2020a.
Fenxiao Chen, Yun-Cheng Wang, Bin Wang, and C-C Jay Kuo. Graph representation learning: A survey. APSIPA Transactions on Signal and Information Processing, 9, 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic, Adaptive universal generalized pagerank graph neural network. In nternational Conference Learning Representations, 2021.
Krzysztof Choromanski, Han Lin, Haoxian Chen, and Jack Parker-Holder. Graph kernel attention transformers, 2021.
F.R.K. Chung, F.C. Graham, CBMS Conference on Recent Advances in Spectral Graph Theory, Na- tional Science Foundation (U.S.), American Mathematical Society, and Conference Board of the Mathematical Sciences. Spectral Graph Theory. CBMS Regional Conference Series. Conference Board of the mathematical sciences, 1997.
10

---

Under review as a conference paper at ICLR 2022
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844-3855 2016.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 4171-4186, 2019.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks to graphs, 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.009k3 2020.
Xing Gao, Wenrui Dai, Chenglin Li, Junni Zou, Hongkai Xiong. and Pascal Frossard. Message passing in graph convolution networks via adaptive filter banks. arXiv preprint 2ww.:::::0.999900 2021.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volus Volume 70, pp. 1263-1272. JMLR. org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Roger A Horn and Charles R Johnson. Norms for vectors and matrices. Matrix analysis, pp. 313- 386, 1990.
Weihua Hu, Matthias Fey, Marinka Zitikk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In In Advances in Neural Information Processing Systems, 2020.
Elvin Isufi, Andreas Loukas, Andrea Simonetto, and Geert Leus. Autoregressive moving average graph filtering. IEEE Transactions on Signal Processing, 65(2))274-288, 2016.
Chaitanya Joshi. Transformers are graph neural networks. The Gradient, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference Learning Representations, ICLR 20/7, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létoureeu,, and Prudencio Tossou. Rethinking graph transformers with spectral attention. NeurlPS 2021 (to appear), abs/2106.03893, 2021.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions Signal Processing, 67(1)997-109, 2018.
Yuan Li, Xiaodan Liang, Zhiting Hu, Yinbo Chen, and Eric Xing. Graph transformer. 2018.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667, 2021.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion
Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
11

---

Under review as a conference paper at ICLR 2022
Balcilar Muhammet, Renton Guillaume, Héroux Pierre, Gaüzère Benoit, Adam Sébastien, and Paul Honeine. When spectral domain meets spatial domain in graph neural networks. In Thirty-seventh International Conference Machine Learning (ICML 2020)- Workshop Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5):808-828, 2018.
Giuseppe Peano. Resto nelle formule di quadratura espresso con un integrale definito. Tipografia della R. Accademia dei Lincei, 1913.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20( 20(1):61-80, 2008.
Yunsheng Shi, Zhengjie Huang, Wenjin Wang, Hui Zhong, Shikun Feng, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03500 03,5099,, 2020.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE signal processing magazine, 30(3):83-98, 2013.
Steven W Smith et al. The scientist and engineer's guide to digital signal processing. 1997.
Kiran K Thekumparampil. Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv:/803.03733 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008266. 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural net- works? In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2019b.
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? NeurlPS 202/ (to appear), arXiv preprint arXiv:2106.05234 2021.
Chulhee Yun. Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of eqquence-to-seqeene to-suue-eeeee functions? In International Con- ference Learning Representations, 2019.
Chulhee Yun, Yin- Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. O (n) connections are expressive enough: Universal approximability of sparse transformers. In NeurIPS, 2020.
Jiawei Zhang and Lin Meng. Gresnet: Graph residual network for reviving deep gnns from sus- pended animation. CoRR, abs/1909.05722, 2019.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint a0X1v:2001.05140, 2020.
12

---

Under review as a conference paper at ICLR 2022
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. A/ Open, 1:57-81, 2020.
A APPENDIX
A.I THEORETICAL JUSTIFICATION
Property A.1. The filter coefficients consisting of the vector of all ones is an all-pass filter
Proof. Consider the filter response given by the chebyshev coefficients T, of the first kind as below
G(x)= Σ T()))t"
==
where t' represent the coefficients for the 1th polynomial. It can be verified that the generating function for G above could be given by the below equation
1 lxt
G(z) = 1 2tx + 1
(14)
setting in this equation gives G(x) _ which does depend on æ. Thus G would behave as an all-pass filter.
Note that is also an alternative but this would cause a degenerate learning of the filter coefficients which may always remain 0 after aggregation and the MLP layers (in the absence of bias).
Theorem A.1. Assume the desired filter response G(z) has + 1 continuous derivatives on the domain [-1,1]. Let G(x) denote the nhth order approximation by the polymomial(heebysherr filter and ST. G(z) denote the learned filter, C₁ be the first absolute moment of the distribution of the fourier magnitudes of (function learned by the network), h the number of hidden units in the network and N the number of training samples. Then the error between the learned and desired frequency response is bounded by the below expression
hn² IG(z) - ST. G(z))= -( O NNN log(N) + +n +
nC
Proof. We begin by defining a bounded linear functional L on the space (mm-[[1111 with m + continuous derivatives below
LG = (=)= - G(x)
Since G(x) has 1 derivatives, it is approximated by polynomial function of degree n > By Peano's kernel theorem (Peano 1913), we can write LG as below
()) - -Gx)) / Gm+ (z), t)dt
(15)
where
(z)
5T (x - -t (x t)
(16)
m!!
The notation (. (.- f) indicates
(x - t)m if >
(xr 1)
otherwise
13

---

Under review as a conference paper at ICLR 2022
We note the thhh order approximation of the chebyshev expansion of the function Gr is given by
$ G = Σ (x())
k=0
where,
G(x)Ta(z)
dr
VI- x²
Thus we get S (x t) as
5 (x 1)
Σ
Ckar (x(
k=
where,
Ckm π (') (x ()))((()))
dx
V1 x
Graph Neural Network approximates Ckm in the proposed method, then we would have an error due to this approximation. We now find the bounds of this approximation. As the current method relies on the connectivity pattern due to the signals of the nodes of the graph, we desire different graph for different signal patterns and thus different filter coefficients. Assuming an injective function (Xu et al. 2019b) for aggregation, we can always find a unique map for a unique the frequency response. Now we need to learn function that maps the output of the previous network to the coefficients of the desired frequency response. A classical neural network with h hidden units could approximate this by the below bound (Barron [991)
graph corresponding
Ckm =0 G hd Iog(N))
Gem
where d = n as the input dimension is the filter order, N is the number of training samples. In- tuitively the first term of the expression states that increasing the number of nodes h decreases the error bounds and the second term acts as a regularizer to limit the increase in h by the number of samples. The latter term be thought of enforcing the bound obey the Occam's razor that parameters should not be increased beyond necessity.
C₁ C-=/ (==/WulFFid
FF is the Fourier magnitude distribution of f which is the function to be learned by the network. Thus get,
C2 hn O log(N))
(17)
N
We represent by S/." (xx t) the approximation obtained by the network of the nh order chebyshev polynomial. Thus
ST' (x
t)
km Tx(x)
k=
14

---

Under review as a conference paper at ICLR 2022
From equation 17 and the previous equation we get the below
S (x 1) (x-1))1
'km Tx(x) (xr - (1)
(ckm + +x) (x +)
k=0
Ckm Tx(x)) - (x- - t + Σ cT(())
0=0
k=0
Ckm Tx( - (xr - 1) +
(T((T)
Σ
Ckm Ta (x))
k=0
k=n+1
Σ TT(l)) - Σ
Ckm [x(x]
k=
Σ
Tkm2k(2)
k=0
k=
C2
Im
(0
+
(og(
Σ
Ckm Ta (z))
h
N
K=0
k=++1
nC
hn²
0
log (N))
Ckm Tu (z))
h
N
k=n+1
We now bound the expression
Ek=nt1 Ckm Tx(x)) We note that
(x - ())TT(())
Ckm
de
x2
Using cos & and cos & get
2 / (cos 1 - cos " cos k0d8
Cke
We now have to solve the integral parts
-o (cos 0 - cos TM cos k0d0 We do this by integrating by
[ccos 0 - cos 3) sin k0
10 / mncos 0 cos (oos)) sin 0) sin ko
I=
k d0
sin kD
m m 0 coo ))m m (- sin 0)
d0
k
m(cos cos 6) cos (k- 1)0 + cos (k + 1)0
d0
k
m(cos 0 cos () cos (k 1)0 d0 + 1//0 m(cos cos "m (Ic + 1)0 d0)
D
= =Tm + I12)
Continuing in this manner we get (2 integrals, one of which as below
m(m 1m - 2).....
Im1 k(k 1)(k 2) ... (k m)) (- sin 0) sin (k m)))
O(k-m)as - xc
15

---

Under review as a conference paper at ICLR 2022
Thus evaluates to O(k-m)) and Ckm
( m))
Thus we have,
Σ k=
Clem Ckm]T(()) = Σ 1kkml
k=++1
On m))
Using this result in the expression for 1S (x t) - (x +)
we get
1) 0 n
hn?
1S (x - t) (o
h +
log(N)) +1
Σ
Ckm Ckm (x)
N
k=n+1
= 0 nC²
hn? log(N)) - On
+
N
Finally using equations 16 and for S G we get
1 Gl= 0 nC?
+ hn? log(N) + n m-)
(18)
N
which concludes the proof.
The bound states that as the filter order n and the hidden dimension of the network h are increased (subject to C²Cy S hn² log condition can be thought to satisfy the statistical rule that the model parameters must less than the sample size. In the limit of N - do, h and n could be increased to as large values as desired subject to 2 (n).. which is the order parameters to be approximated. This is equivalent to say that do not consider the generalization error, with only the term containing the filter order i.e. the approximation error comes down to On "") expected. One point to note is that assume suitable coefficients Ckm. can be learned from the input graph. This assumption requires that the graph has the necessary information regarding spatial connectivity and signals. In the current implementation, we only use the information from the signals residing on the graph nodes in the attention heat map and discard the spatial connectivity. It a straightforward exercise extend this idea by using multi-relational graphs to include the graph signals and the spatial connectivity information which we leave for future works. Nevertheless, the current implementation does well empirically, as is evident from the results on the real world and synthetic A.4 datasets.
N ) the approximation will converge to the desired filter response. The
theoretically take large h. Then,
are left
A.1.1 TRANSFORMERS AND WL TEST
WL-test has been used as a standard measure to study the expressivity of GNNs. The k-WL test the variant of the WL test that works on k-tuples instead of one-hop node neighbors compared to the standard 1-WL. test. Recently, with the rapid adoption of transformers on graph tasks, the equivalence of transformer and WL test naturally arises. In the following section, we try to argue how transformer can approximate the WL test.
Given a sequence, recent works by (Yun et al. 2019 2020) have theoretically illustrated that Trans- formers are universal sequence-to-sequene former is a self-attention layer; the self-attention layers compute dynamic attention values between the query and key vectors by attending to all the sequences. This can be viewed as passing messages between all nodes, regardless of the input graph connectivity.
approximators. The core building block of the trans-
For position encoding, recently, many works have tried using eigenvectors and eigenvalues as PEs for GNNs (Dwivedi & Bresson 2020 Kreuzer et al., 2021). The recent work by DGN (Bainn et al., distinguish non-isomorphic graphs which WL test cannot.
2021 shows how using eigenvalues
Transformers are universal approximators coupled with eigenvalues and eigenvectors as position encodings powerful than the WI test given enough model parameters. However, they only
16

---

Under review as a conference paper at ICLR 2022
DATASET
GPU
Memory
TIME (see PER EPOCH)
MUTAG
Geforce P8
1.5
NCII
Geforce P8
37.8
Molhiv
Tesla V100
16
79.0
PATTERN
Tesla V100
16
104.2
CLUSTER
Testa V100
16
115.4
ZINC
Tesla V100
529.9
Table 4: Computational details used for the datasets on the SpecTTRA setting
Model
Dataset
PE
PE layers
PE dim
no, layers
hidden dim
Model Params
Heads
Filter Order
MUTAG
64
118074
4
NCII
122194
SpAcTRA- Base
Molhiv
129465
4
PATTERN
64
5468930
4
CLUSTER
5467726
ZINC
351537
MUTAG
119080
NCI1
64
107074
4
Vanilla-
Molhiv
127356
Transformer
PATTERN
5445389
CLUSTER
64
5447657
4
ZINC
64
340737
4
Table 5: Model architecture parameters of Spec and
approximate the solution to the graph isomorphism problem with specific error and not solve them fully which is also proven by Kreuzer al. (202T). The same holds for as we inherit the identical characteristics from SAN.
A.2 DATASET DETAILS
We benchmark the widely used datasets for graph classification, node classification, and graph gression. Namely for graph classification we use MUTAG (Morris et al., 2020),. NCII (Morris et al., 2020) and, the agbg-MolHIVv (Hu et al. (2020) dataset, for node classification use the PATTERN and CLUSTER datasets @wiieedi et al. 2020) and for graph regression we run our method on the
ZINC (Dwivedi al. 2020) dataset.
MUTAG is collection of nitroaromatic compounds. Here, the goal is to predict the mutagenicity of these compounds. Input graphs represent the compounds with atoms as the vertices and bonds as the edges. Similarly, in NCI1, the graphs represent chemical compounds with nodes representing the atoms and the edges indicating their bonds. The atoms are labeled as one-hot vectors as node features. Oglg-MolHIV is a molecular dataset in which each graph consists of molecule, and nodes have their features encoded as the atomic number, chirality, and other additional features. PATTERN and CLUSTER els. In PATTERN, the task is to identify subgraphs and CLUSTER aims at identifying clusters in sumi-super setting. ZINC is database of commercially available compounds. The task is to predict the solubility of the compound formulated as a graph regression problem. Fach molecule has the type of heavy atom as node features and the type of bond as edge features.
node classification datasets constructed using stochastic block mod-
A.3 EXPERIMENT SETTINGS
Table lists the hardware and the run time of the experiments on each dataset. Table ?? lists out the model architecture parameters for each configurations. For the configurations SSeecRRABaass Spec- we used the default hyper-parameters provided by GraphiT (Mialon et al. 2021 as we inherited position encodings from GraphiT. For and used the configurations from SAN (Kreuzer al. 2021). This is to sure same experiment settings which these encoding schemes have used while inducing position encodings in the vanilla transformer models. Means and uncertainties derived from four
LapE, SpecTRA+3RV and
instance, in ZINC, we don't t use edge features. In the configurations Spec/RA+LPE+Sppr SpecTRA+LPE+Fill
17

---

Under review as a conference paper at ICLR 2022
Model
Dataset
PE
PE layers
PE dim
no. layers
hidden dim
Model Params
Heads
Filter Order
MUTAG
LapE
2216402
NCTI
1 TapF:
64
64
2218322
SpecTRA LapE
LapE
129657
PATTERN
LapE
64
64
4414022
CLUSTER
LapE:
64
3
5468494
7INC
1 LapE:
64
3
483401 64
MUTAG
LapE
64
64
2T95467
NCII
LapE
2207266
GraphiT
Molhiv
LapE
64
64
127489
Lapl
PATTERN
LapE
CLUSTER
LapE
64
474456 64
5447384
ZINC
LapE
MUTAG
RW
3
64
T06694
NCTI
RW
3
10698
SpocTRA 3RW
Molhiv
RW
64
129465
4413258
CLUSTER
RW
5467726 64
ZINC
MUTAG
RW
64
104578
NCII
106498
GraphiT
Molhiv
RW
64
125745
+ 3RW
PATTERN
RW
64
4394786
CLUSTER
RW
5445478
ZINC
RW
338817 64
MUTAG
OCKN-RW
32
64
116783
SpecTRA
NCII
CCKN-RW
32
2228434
GCKN
Molhiv
GCKN-RW
32
64
5619529
PATTERN
CCKN-RW
32
37988386 64
3RW
CLUSTER
GCKN-RW
32
37990182
ZINC
GCKN-RW
32
499273 64
MUTAG
GraphiT GCKN
NCTI
GCKN-RW
32
3
64
2205672
Molhiv
GCKN-RW
32
5598726
3RW
PATTERN
RC
32
3
64
37889986
CLUSTER
GCKN-RW
32
37895163
ZINC
OCKN-RW
32
3
64
478645
Table Model architecture parameters of SpecTRA with position embedding from GraphiT and original Graphi'T model
Model
Dataset
PE
PE layers
dim
layers
hidden dim
Model Params
Heads
Filter Order
MUTAG
LPE
16
64
558322
SpecTRA
NCII
LPE
1
16
64
559762
8
Molhiv
LPE
2
96
LPPE
PATTERN
LPE
3
16
96
579013
10
Sparse
CLUSTER
LPE
1
16
16
56
412978
8
ZINC
LPE
3
96
364167
8
MUTAG
L.P
64
5420N2
NCII
LPE
16
64
543522
8
SAN
Molhiv
LPE
2
16
96
602672
IPE
PATTERN
LPE
96
570736
Sparse
CLUSTER
LPE
56
403783
ZINC
LPE
3
16
96
360617
8
MUTAG
LPE
64
640242
SpecTRA
NCII
LPE
16
64
641682
8
Molhiv
LPE
2
16
96
732984
LPE
PATTERN
LPE
96
Full
CLUSTER
LPE
16
16
56
867046
8
ZINC
LPE
3
16
96
458303
8
MUTAG
LPE
64
624002
NCII
LPE
64
625442
SAN
LPE
Molhiv
LPE
2
16
96
714769
Full
PATTERN
LPE
3
16
96
688534
10
CLUSTER
LPE
96
858538
ZINC
LPE
3
16
96
454753
8
Table Parameters of SRe with position embedding from SAN compared with original SAN
18

---

Under review as a conference paper at ICLR 2022
Method
MUTAG
NC11
ZINC
PATTERN
CLUSTER
ogbg-molhiv
Avg [V]
30.32
29.87
23.15
118.89
117.20
25.51
Avg [8]
32.13
32.30
24.90
3039.28
2,150.86
27.47
Node feature
L.
L
A
L
L
A
Dim(feat)
38
37
28
3
9
#Classes
2
2
NA
2
6
2
#Graphs
4,127
4,110
250,000
14,000
12,000
41,127
Table 8: Dataset statistics (L. indicates node categorical features and A denotes node attributes).
with different seeds, same as SAN. Additionally, with the final optimized parameters, we reran 10 experiments with identical seeds, which is same as SAN's/Mialon et al/Dwivedi al's experiment settings. Vanilla transformer implementation and values main paper is taken from Mialon et al. (202T.
A.4 SYNTHETIC DATASET
To show the benefit of graph-specific filtering compared to static filtering, we run experiments on synthetic datasets that have different spectral components for different graphs. We begin by noting a few basic properties of the Laplacian and its spectral decomposition before detailing the data generation process. The below equation gives the unnormalized Laplacian (L = A) of graph:
deg(i) -1
if
L(i,j)
if (
otherwise
where deg(i) the degree of the node and E is the set of edges in the graph. Multiplying L by vector gives the below expression
Lu
w(i) = Σ (o(1)- -())
iEEE
The expression v² Lo gives
v Lv
Σ 011) Σ (v(1) - v(i))
iEEB
Σ Σ ((i(((()) -(i))
WEE
Σ v(i((((i) v()) +0)0)()
(.,EEE
Σ
(u(1) - x())²
j>LEEEEE
Thus we can see that the expression - evaluates to the sum of squared distances between neigh- boring nodes the graph. We also note that due to this property, the laplacian definite matrix. If u were the eigenvector of the graph, we know that vf Lo would be the eigenvalue corresponding to that vector by the spectral decomposition theory. Thus all the eigenvalues of the laplacian are non-negative.
positive semi-
We now try to develop an intuition of the laplacian's 's lowest and largest eigenvalues/vectors. We see from the above equations that o' Ly is the sum of squared differences between values on the nodes. Thus the smallest eigenvalue would correspond to the eigenvector that assigns the same value to all the neighboring nodes, subject to ||u||= 1. The second eigenvalue would correspond to the orthonormal vector to the first vector and minimizes the sum squared differences of nodes within cluster. Thus the second eigenvector would try keep values of its components similar/closer for
19

---

Under review as a conference paper at ICLR 2022
100 1.N 3.0
(a)
(b)
(c)
Figure 4: Graphs and Filter Frequency response for the graphs on the Synthetic, dataset for the case with K = 4 and = 1. Figure (a) is graph that illustrates low frequency signals (here, we observe the neat clusters as expected for low frequency information). Figure (b) represents graph with a high frequency component (we observe the mixing of signals in nodes of the same cluster, i.e, different intra-cluster signal values). Finally, figure (c) is the aggregated frequency response across the dataset with the normalized frequency along the X-axis and associated magnitudes on the Y-axis. Here we note the filter has learned the two components of the graph spectrum: the low frequency and the high frequency components.
nodes that belong the same cluster. Similarly, the vector corresponding to the largest eigenvalue would try to maximize the sum of squared differences between neighboring nodes and have its nodes(components) belonging the same take different values subject to ||]||= while also being orthonormal to the other vectors.
With the above background, we generate synthetic datasets with node signals exhibiting different spectral components for different graphs. Consider L to be the graph laplacian with eigenvalues and eigenvectors V. We generate stochastic block matrices (SBMs) with B number of blocks and N number of nodes per block having an intracluster density of edges as pt and the inter-cluster edge density as Po- The signals are assigned to the graphs according to the eigenvectors of the selected components of the spectrum. To keep it simple, we use only single eigenvector (V/) to generate signals per graph. Specifically, out of the NG = E(N B) eigenvalues, we select one and take the components of the corresponding cigenvectors. The nodes are then clustered using standard clustering algorithms, such as K-means, into C' classes that we keep equal to the number of blocks. Each node is assigned one-hot vector at the position of the class it belongs then drop this attribute of 50% of the nodes i.e., these nodes are assigned 0 vector, and the task is to find the correct assignment for the unknown class based on the connectivity pattern and the spectrum of the known signals on the graph. Thus this task boils down to finding the suitable spectral component in the graph signal and using this information for classification. This should benefit from a graph-specific decomposition and filtering approach, which we confirm from the empirical results. We generate 3 datasets namely Synthetic Syntheticz, and Syntheticy using different values of N, B, Pis Po. V. Synthetic, has N = 10, B 2, Ps 0.9, Po = 0.05, (Vi i E (1,Nc)): with 1000, 100, 100 graphs the train, test and valid graphs respectively. Synthetic has N = 10, B 6, P: 0.9, Po 0.05, {V: i E {1, Na with 1000, 100, 100 graphs in the train, test and valid graphs respectively. Syntheticı has N = 10, 6, p. = 0.9, P. = 0.05. (V: i {1. 1, with 1000, 100, 100 graphs in the train, test and valid graphs respectively.
We
We train the synthetic datasets on the SpecTRA-Staree and SpecTRA-Bas models to study the effect of graph-specific dynamic filters the graph. For the Synthetic dataset, we use the hidden dimension as 16, and for Syntheticy and Syuthetica we keep it to 64. The number of layers is fixed to 1. The number of heads h and filter order K for SpecTRA-Static are kept at and 4 respectively and for varied for other settings as can be seen in table A.4 We can see from table A.4 that the performance on the synthetic datasets, using dynamic filters of SpecTRA-Base has increased by large margin as compared to the case of static dataset-specific filters in SpecTRA-Statee using the same model parameters. This justifies the benefit and necessity of graph-specific filter design in
20

---

Under review as a conference paper at ICLR 2022
Model
Synthetic
Synthetio
Syntheticy
#Param(dim=16)
#Param(dim==6))
SpecTRA-Statie
K
h
70.04 4.41
35.34 0.25
33.05 0.48
4122
62958
K
89.67 0.50
45.63 0.30
39.67 0.55
3582
54738
SpecTRA-Base
K h
92.15 + 0.20
46.32 0.42
40.22 + 0.61
4122
62958
K = 8
92.26 + 0.40
47.14 0.63
40.27 + 0.30
5250
79446
K = 2 K =
79.26 + 7.47
46.26
0.20
39.83 + 0.33
3090
47010
SpecTRA-Bar
91.54
46.59
0.34
39.42 0,30
3150
47550
K
92.35 0.37
0.56 46.24
40.74
0.35
3318
48678
K K h =
74.99 0.43
45.88 0.50
38.60 1.05
3064
46618
SpecTRA-Bas
91.32 + 0.43
45.77 0.73
38.86 + 0.17
3100
46774
K 8
91.60 + 0.30
45.75 0.73
39.71 + 0.50
3220
47134
Table 9: Study on the performance of SpecTRA- -ase vs SpecTRR--taate on the synthetic datasets. We study the effect the order K of filters and the number of heads for SpecTRA-
cases where the spectral information differs from graph graph. We also observe that as the filter order is increased for a given number heads, the performance improves.
On the other hand, lower filter order is detrimental to the task. The performance saturates if the filter order is increased beyond a specific limit, as is evident from the Synthetic, dataset. Also, we do not observe any improvement by increasing the number of heads, keeping the filter order fixed, in this case. This may be due to the nature of the dataset, where we have restricted each graph to contain single spectral component. We leave it to future studies determine the effect of number of heads on multiple spectral components in the signal.
A.5 FILTER FREQUENCY RESPONSE ON OTHER DATASETS
Here we provide the plots of the frequency response of the filters learned on the other datasets which has not been included in the main paper due to page limit.
The frequency response of the filters learned on ZINC with filter order four is given in figure Each curve is the frequency response of a filter learned for single head. We see various filters being learned, such few low pass, high pass, and band stop filters. Figure shows the frequency response for filters of order 8. Here we observe the high pass and multi-modal band pass responses being learned.
Filter Frequency response on ZINC:
Filter Frequency response on MolHIV:
Figure 7 illustrates the frequency response for filters learned on the MolHIV. Here, we observe the low pass and multi-modal band pass filter responses.
Filter Frequency response on PATTERN: Figure& shows the frequency response for filters learned on the PATTERN dataset. Here we observe the filters allowing signals in the low and high frequency regime along with some magnitude assigned to the mid- mid-frequency components. The filter order eight (the two right-most plots) shows a surprising result of visually indistinct filters being learned despite the regularization. This indicates the task has a high bias towards signals in the low- cow-freuuency region and some components in the middle and high frequency regime to an extent. This could be interpreted the model trying learn the components: the SBM, which corresponds to the low-frequency signal, and the underlying pattern itself, which may benefit from the middle and high frequency components in the spectrum.
Filter Frequency response on CLUSTER: Similar to PATTERN, the filter response plots for CLUSTER as in figure show low-frequency filters being learned along with bandpass filters. This is intuitive as the task of CLUSTER would indeed benefit by learning low-frequency signals for grouping nodes belonging to the same cluster. All these observations across all datasets validates our hypothesis studied in the scope of this paper.
A.6 INTERPRETABILIE IN SPECTRAL SPACE
In this section, we look at the interpretability aspect induced by SpecTTRA in the spectral space. the nodes corresponding to the
The figures 10 and [] show the graphs with the eigenvectors top eigenvalues selected by the filter. From both figures, we see that in the case the low pass filter (leftmost graph in sub-figure (a), (d) of figure and and subfigure (a)-(d) of figure [T), the nodes
21

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
(h) K
Figure 5: Filter Frequency response individual graphs the ZINC dataset for filter order of Figures (a) ~ (d) are the graphs from the dataset and Figures (e) ~ (g) are the corresponding frequency responses. axis shows the normalized frequency with magnitudes the Y axis
(a)
(b)
(c)
(d)
(h)
Figure 6: Filter Frequency response individual graphs the ZINC dataset for filter order of Figures (a) ~ (d) are the graphs from the dataset and Figures (e) ~ (g) are the corresponding frequency responses. X axis shows the normalized frequency with magnitudes the Y axis.
22

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
(h)
Figure 7: Filter Frequency response individual graphs the MolHIV dataset. Figures (a) (d) are the graphs from the dataset and Figures (e) ~ (h) are the corresponding frequency responses. X axis shows the normalized frequency with magnitudes the Y axis.
(a)
(b)
(c)
(d)
(h)
Figure 8: Filter Frequency response individual graphs the PATTERN dataset. Figures (a) (d) are the graphs from the dataset and Figures (e) ~ (h) are the corresponding frequency responses. X axis shows the normalized frequency with magnitudes the Y axis.
23

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h) K
Figure 9:
Filter Frequency response on individual graphs on the CLUSTER dataset. Figures (a) (d) are the graphs from the dataset and Figures (e) (g) are the corresponding frequency responses. X axis shows the normalized frequency with magnitudes on the Y axis.
(a)
(b)
(d)
Figure 10: Attention heat map spectral space of the sample graphs in ZINC dataset determined from the frequency response in Figure for its each sub-graph (a)-(d), Blue illustrates the lower end of the spectrum and red color shows the higher end the spectrum.
24

---

Under review as a conference paper at ICLR 2022
(b)
(d)
Figure 11: Attention heat map in spectral space of the sample graphs in MolHIV dataset determined from the frequency response in Figure for its each sub-graph (a)-(d), Blue illustrates the lower end of the spectrum and red color shows the higher end of the spectrum.
in the neighborhood forming a cluster have similar eigenvalues. Whereas in the highpass filter ( (rightmost graph in each subfigure (a)-(d)) the eigenvalues of the nodes alternate, with neighboring
nodes taking distinct values and far off nodes having similar values.
We could make two interpretations of this phenomenon. The first one is closely related to attention in the spatial space where SpecTTR attends to select input features. In this case, we can think the model learning to pay more attention to the nodes with higher eigenvalues and lesser attention the nodes with smaller eigenvalues in a graph and task-specific manner. The second interpretation is re- lated the interaction between the nodes, i.e., for given node which other nodes considered for aggregation. For example. in graph attention networks, the neighboring nodes are aggregated, and the values of nodes in the same cluster tend be closer to each other (homophily). This particu- lar case of the low pass filter in which we can see from the figures) and 11 that the nodes belonging the same cluster take on similar values. For example, consider the Figure (d)... (d). The leftmost graph has nodes in a particular cluster taking similar eigenvalues showing short-range dependencies (interactions).
the rightmost graph, nodes in the same clusters take on different eigenvalues, illus- trating the need for long-range interactions. However, depending also learns to aggregate (interact with) distant nodes, as seen the graph corresponding to the high pass filter (the rightmost graphs in each sub-figure 10 and IT]. Thus SpecTRA can be interpreted as generic(covering the entire spectrum frequencies) attention network in the spectral space.
the task and graph, the model
25


Reviews:
[{"review_id": "l97LjshnxTU", "reviewer": "Reviewer_iKKm", "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": "The paper discusses augmenting the Transformer structure to better suit the nature of graph data modeling. My main concern is that the paper itself does not compose a coherent story of why the GNN layer should be effective and makes a difference as a whole.\n\n## Pros\nThe paper provides a good way to interleave GNN and Attention layers. Compared to simply injecting graph structures into positional embeddings, this method gives a novel way to fuse benefits from both sides.\n\n## Cons\n* The descriptions and notations by the paper are preventing a coherent understanding. e.g. the superscript $h$ (e.g. $\\alpha^h$) is used to represent the corresponding head number while superscript $l$ is used to represent the layer number. When combined with the output representation $x$, it would be unclear for a first-time reader to notice the meanings of $x^h$ and $x^l$ are different.\n* The method itself is hard to be in the SOTA class. For example, in Table 1, even for SpecTRA+GCKN+3RW which is the best among 3/6 datasets, it can still not outperform the previous SAN-Sparse one on the remaining 3/6 datasets. Given its added complexity compared to SAN (they share most of the parts in the positional embedding scheme), it’s hard to justify its effectiveness.\n* A fair Transformer comparison is needed. It would be beneficial to state the added number of parameters compared to the baseline Transformer. As in most cases that would induce larger model capacity.\n* Minor:\n  * The current draft itself can be more polished to be a qualified submission. There are some typos and unclear statements:\n  * Equation (6) double `)` \n  * Equation (8) Missing $V$\n  * 2 lines above Equation (11)$h^{th}$ -> $h$-th\n  * Figure 3, it would be better to show unsmoothed filter frequencies for limited-point graphs (e.g. (a)).\n", "summary_of_the_paper": "This paper proposes a framework that adds in an extra GNN layer after the Attention layer of Transformer, which enables better quality modeling in graph data. In particular, the GNN layer learns a per-head transformation that imposes learnable filter coefficients, which demonstrates better performance than static filters coefficients.\n", "summary_of_the_review": "The proposed method gives a new way of enhancing Transformer models in the graph domain. However, the experiments are not sufficient to justify the efficacy of the new model given its added complexity.", "strength_and_weaknesses": "", "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": "iNBBXV8QtIa", "reviewer": "Reviewer_7T9R", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "+ The paper is well-structured.\n\n+ The paper lacks its motivation. I can understand the motivation for filtering graphs for GNNs (Gao et al., 2021), but adapting this existing motivation to argue that the transformer cannot effectively segregate the noise from the signal is not enough. Some recent models (Mialon et al., 2021; Kreuzer et al., 2021) and SpecTRA are only suitable for small-size graphs due to utilizing the self-attention networks on the whole input graph. However, it is worth noting that these recent models ignore Graph-BERT [1] and Graph-Transformer [2].  Both Graph-BERT and Graph-Transformer can work quite well for node and graph classification and can be adapted for large-size graphs as they employ the self-attention networks on neighbors to take the local structures into account, which the recent models (Mialon et al., 2021; Kreuzer et al., 2021) and SpecTRA are missed.\n\n+ Furthermore, it is straightforward to directly adapt Equation 6 for H^h with the learnable parameter \\alpha instead of computing \\alpha from the attention weights in Equation 9. Equation 9 is the main contribution in SpecTRA, but why does SpecTRA need it? What is the motivation behind it? What are the results of directly adapting Equation 6 with the learnable \\alpha?\n\n+ Regarding Equation 10, x^h_i is the vector at node x_i in the h-th attention head obtained from Equation 9. Is x^h_i actually from Equation 8? Because if it is from Equation 9, it means that SpecTRA constructs GCNs on top of the vanilla multi-head self-attention networks, followed by spectral filterings. This makes a confusion as if it is correct, SpecTRA is an extension of Graph-Transformer with additional using spectral filterings inspired from Gao et al., (2021).\n\n+ SpecTRA lacks novelty as it is incremental. The performance gains are marginal.\n\n+ The obtained results mainly come from the existing positional encoding schemes (Kreuzer et al., 2021). Without the existing positional encoding schemes, SpecTRA-Base is outperformed by other existing models such as GIN. Therefore, the main contribution shown in Equation 9 is incompetent.\n\n+ The paper misses the results of the closely related works Graph-BERT, Graph-Transformer.\n\n+ Why are the GIN and GCN results on MUTAG and NCI reported in Table 1 different from the original paper?\n\n[1] Graph-Bert: Only Attention is Needed for Learning Graph Representations. https://github.com/jwzhanggy/Graph-Bert\n\n[2] Universal Graph Transformer Self-Attention Networks. https://github.com/daiquocnguyen/Graph-Transformer\n", "summary_of_the_paper": "This paper proposes SpecTRA to construct spectral filterings on top of vanilla multi-head self-attention networks to have coefficients for each input graph. Specifically, SpecTRA computes the filter coefficients from the attention weights of vanilla multi-head self-attention networks by defining a mapping function (i.e., Equation 9) from the attention space to the filter coefficient space.", "summary_of_the_review": "The paper lacks the motivation and the proposed model SpecTRA is incremental.", "strength_and_weaknesses": "", "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": "O3x0o3-drei", "reviewer": "Reviewer_VYTd", "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": "Correctness: No correcteness concerns.\n\nTechnical novelty and significance: The idea that different filter shapes are necessary to discriminate the spectral components associated with different graphs makes sense, therefore, learning the filter coefficients of the GNN used to distinguish between these graphs is a compelling solution. However, other architectural choices are not as well motivated. For example, why do the authors learn the spectral GCN filter weights from the attention matrix of the transformer, which can have a completely different sparsity pattern than the input graph? Why not learn the filter weights from the graph itself, e.g., by using a GNN? What is the rationale behind this choice of architecture? \nAnother technical concern relates to Theorem 4.1. While the authors claim that this theorem justifies the proposed architecture, it is not clear how. That smooth functions can be approximated by Chebyshev polynomials is a well-known result. Can the authors clarifiy which aspects or parts of their method are justified by Theorem 4.1? I recommend adding a more detailed discussion of the theorem's implications to Section 4.1. \n\nEmpirical novelty and significance: One of the goals of the numerical results is to assess \"the impact of recently proposed position encoding schemes on SpecTra\". Yet, none of these position encoding schemes were proposed by the authors. Moreover, the numerical results are unconvincing. The proposed method achieves similar performance to the compared methods except for ZINC. Additionally, errors with three decimal digits are not statistically significant for averages over 4 runs.\n\nOther comments:\n- The abstract and the introduction are difficult to understand and do not give a clear picture of the paper's contributions.\n- In the beginning of Section 4.1, the authors should specify how the node feature embeddings fed to transformer are obtained from the graph.", "summary_of_the_paper": "This paper proposes a model for graph representation learning based on a transformer and on two GNNs: a message-passing neural network that learns graph filter coefficients from the transformer's attention weights, and a spectral GCN with parameters given by these filters coefficients. This choice of architecture is motivated by the assumption that different filter shapes are necessary to discriminate the specific spectral components associated with different graphs.", "summary_of_the_review": "The idea that different filter shapes are necessary to discriminate the spectral components associated with different graphs makes sense, therefore, learning the filter coefficients of the GNN used to distinguish between these graphs is a compelling solution. However, other architectural choices---such as learning the spectral GCN filter weights from the transformer's attention matrix---are not well motivated. Moreover, the numerical results are unconvincing. ", "strength_and_weaknesses": "", "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": "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": "-wYBYQZPBor", "reviewer": "Reviewer_5mRd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Strength:\n1. This paper has clear motivation and goal; that is since the transformer model naturally gives diverse attention sub-spaces, which correspond to the multiple filters covering the spectrum of the graph. Under these settings, the goal of the model is then to learn the filter coefficients; this process also naturally provides interpretability.\n2. This paper has solid theoretical proof.\n3. The experiment is pretty comprehensive; it includes many models from recent years as baselines and the comparison is done on six different datasets under three different tasks.\n4. Overall this paper is well organized where the authors clearly know what they are talking about.\n\nWeakness:\n1. From the experiment section we can see that the proposed model can do pretty well on some tasks while doing worse on other datasets. This variance in performance could suggest that the proposed model need certain prerequisite to be fully functional. More datasets are needed to fully test the functionality of this model.\n2. The proposed model is usually combined with other modules to achieve the best performance while the base version of it is definitely not the best in comparison to other models. More ablation studies might be necessary to justify the role that the proposed model plays in the system.", "summary_of_the_paper": "This paper proposes a novel model called SpecTRA to optimize the performance of the transformer model on the graphs. This proposed model induces a spectral module into the original transformer architecture to enable it to decomposite graph spectrum and filter the frequency domain and thus leading to more useful information.", "summary_of_the_review": "This paper proposes a model that tries to improve the performance on the transformer on graph structure data. The proposed model has pretty good motivation and reasonable theory support, with the performance being relatively good in comparison to other baselines on some tasks. Overall, this is a solid paper, but it might more experiments to justify the importance of the proposed model.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel approach to include graph information into Transformers. Reviewers expressed concerns on 2 main issues -

1) The exact architecture proposed in the paper is not well motivated. In words of one of the reviewers 'I still do not understand why the authors learn the spectral GCN filter weights from the attention matrix of the transformer, which can have a completely different sparsity pattern than the input graph, instead of learning the filter weights from the graph itself, e.g., by using a GNN. '. Authors tried to provide an explanation in the response however I think it needs to be made much more rigorous for it to be well motivated.

2) The interplay between existing position encoding schemes and the proposed method. This point also confused couple of reviewers as the empirical results seem to be strongly influenced by the choices of position encoding. Authors, I think did a great job in addressing this concern by providing additional results during the response period. 

Given the weak experimental results and lack of clear motivations I think the paper is not currently ready for acceptance.
Decision: Reject