How Expressive are Transformers in Spectral Domain for Graphs?
Authors: Anson Bastos
Abhishek Nadgeri
Kuldeep Singh
Hiroki Kanezashi
Toyotaro Suzumura
Isaiah Onando Mulang'
Venue: Accepted by TMLR ()

Abstract: The recent works proposing transformer-based models for graphs have proven the inadequacy of Vanilla Transformer for graph representation learning. To understand this inadequacy, there is a need to investigate if spectral analysis of the transformer will reveal insights into its expressive power. Similar studies already established that spectral analysis of Graph neural networks (GNNs) provides extra perspectives on their expressiveness. 
In this work, we systematically study and establish the link between the spatial and spectral domain in the realm of the transformer. We further provide a theoretical analysis that the spatial attention mechanism in the transformer cannot effectively capture the desired frequency response, thus, inherently limiting its expressiveness in spectral space. Therefore, we propose FeTA, a framework that aims to perform attention over the entire graph spectrum (i.e. actual frequency components of the graph) analogous to the attention in spatial space. 
Empirical results suggest that FeTA provides homogeneous performance gain against vanilla transformer across all tasks on standard benchmarks and can easily be extended to GNN-based models with low-pass characteristics (e.g., GAT). 

Published in Transactions on Machine Learning Research (07/2022)
How Expressive are Transformers in Spectral Domain for Graphs?
Anson Bastos
ansombstos@gmail.com
Indian Institute of Technology Hyderabad, India
Abhishek Nadgeri
RWTH Aachen and Zerotha Research, Germany
Kuldeep Singh
Zerotha Research and Cerence GmbHl Aachen, Germany
Hiroki Kanczashi
The University of Tokyoo Tokyo, Jopan
Toyotaro Suzumura
The University of Tokyo Tokyo, Japan
Isaiah Onando Mulang'
IBM Research
Kenya, Africa
Reviewed on OpenReview: https: openreview. net/ forum? id= aRsLetuma!
Abstract
The recent works proposing transformer-basee models for graphs have proven the inadequacy of Vanilla. Transformer for graph represenlation learning. To understand this inadequacy, there is need to investigate if spectral analysis of the transformer will reveal insights into its expressive power. Similar studics already established that spectral analysis of Graph neural networks (GNNs) provides extra perspectives on their expressiveness. In this work, we systematically study and establish the link between the spatial and spectral domain in the realm of the transformer. We further provide a theoretical analysis and prove that the spatial attention mechanism in the transformer cannot effectively capture the desired frequency response, thus, inherently limiting its expressiveness in spectral space. Therefore, we propose FeTA, framework that aims to perform attention over the entire graph spectrum (i.e., actual frequency components of the graphs) analogous to the attention in spatial space. Empirical results suggest that FeTA provides homogeneous performance gain against vanilla transformer across all tasks on standard benchmarks and can casily be extended to GNN-based models with low-pass characteristies (e.g., GAT).
1 Introduction
Several graph neural network (GNN) approaches have been devised as generic and efficient framework to learn from graph-structured data for tasks such as graph classification, node classification, graph regression, and link property prediction (Zhou et al. 2020). Among them, message-passing GNNs (MPGNNs) have been prominently used to obtain latent encoding of graph structures, achieving good results related tasks

---

Published in Transactions on Machine Learning Research (07/2022)
Gilmer et al. 2017 Veličković et al.
2018 Xu et al. 2019a). Although effective, these methods suffer from
performance issues such as over-smootthng (Zhao & Akoglu 2020 suspended animation (Zhang & Meng
2019), and over-squashing (Alon & Yahav 2021). Recently, researchers (Li et al. 2018b) have attempted to use vanilla transformer (Vaswani et al., 2017) for graph representation learning without such issues. However, transformers are inherently incapable of graph representation learning (Dwivedi et al., 2020). Hence, more
recent works have added gamut of positional and structural encoding methods (Mialon et al. 2021 Kreuzer
et al. 2021 to alleviate limitation of transformers to learn topological information.
The research community has theoretically studied the expressive power of GNNs with two schools of thought: 1) by equating to Weisfeiler-Lehman (WL) test order for spatial domain (xu ct al. 2019b; Morris et al. 2019) 2) by spectral analysis of GNN models (Wu et al. 2019 Balcilar et al. 2020a). However, vanilla transformer based models (Vaswani et al., 2017) are only studied in the spatial domain by analyzing expressive power using WT.test (Ying et al. 2021; Kreuzer et al. 2021) for graphs. Furthermore, no prior work provides a theoretical understanding of the propertics and limitations of transformers in the spectral domain. This paper argues that analyzing transformers theoretically and experimentally in the spectral domain can bring a new perspective their expressive power. Unlike GNNs, where researchers have studied their spectral propertics (Wu et al. 2019 Nt & Machara 2019) and established an equivalence between corresponding spatial and spectral space [Balcilar et al. 2020a), to the best of our knowledge, there exists no study that establishes such uniformity for transformers. Moreover, if there exists an equivalence, there remains another open question: what is the expressive power of transformers in spectral space for graphs? Our work aims to explore these important open research questions.
Motivation:
Contributions: In this paper, our first contribution is to formally characterize an equivalence between transformers' spatial and spectral space. Based on this analysis, as second contribution, we study the expressive power of the transformer in the spectral domain and conclusively establish its limitation. As a third contribution, we propose FeTA, a framework that overcomes these limitations while also considering the fact that signals on a graph could contain heterogencous information spread over a wider frequency range (Bianchi et al. 2021 Gao et al. 2021). Therefore, it able to perform allention over the entire graph signals in spectral space analogous to the traditional transformers in spatial space. We further study the generalizability of FeTA by incorporating its ability to perform attention over the graph spectrum into low-pass filter GNN for empowering it to include the full graph spectrum, observing an empirical edge on base model. Our last contribution is to study the impact of recently proposed position encoding schemes on FeTA The main results of this work are summarized below:
We formally bridge the gap between spatial and spectral space for the vanilla transformer.
We theorctically establish that transformers are only effective in learning the class of filters containing the low-pass characteristic. This implies transformers are not able to selectively attend to certain frequencies using their inherent spatial attention mechanism.
Based on the observed limitation, we develop FeTA (Frequency Attention Transformer), a framework that performs attention over frequencics for the entire graph spectrum. We study the efficacy of FeTA with extensive experiments on standard benehmark datasets of graph classficatioon/reresse /regression and node classification resulting in superior performance compared to vanilla transformers.
FeTA's ability perform attention over the entire graph spectrum when induced into low-pass GNN filter models such as GAT (Veličković et al., 2018) has significantly improved GAT's performance.
Extensive experiments with position encodings (PE) show that none of the considered state-of-the-art PEs proposed for transformer work are agnostic to the graph dataset. However, replacing the vanilla transformer with FeTA in recently proposed transformer architectures that use PFs (Dwivedi et al. (2020): Krouzer et al. 20021:; Mialon et al. (2021)) improved the overall performance on most graph representation learning lasks. Observed behavior implies that our work provides complementary and orthogonal school of thought to position encodings developed for transformers in spatial space.
The remainder of the paper is organized as follows: we describe the related works in section 2 Section 3 provides the preliminaries and problem definition. Section provides theoretical foundations of our work. Tn
2

---

Published in Transactions on Machine Learning Research (07/2022)
we explain the proposed approach for graph-specific dynamic filtering. Dataset details, experimental results, and ablations are given in sections i Section 7 concludes the paper.
section 5
2 Related Work
GNNs and Graph Transformers: In this section, we stick to the work closely related to our approach (dctailed survey in (Chen et al. 2020b)). Since the carly 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 ncural networks for updating representation of neighboring nodes by exchanging messages between them. The use of transformer-style allention to GNNs for aggregating local information within the graphs is also an extensive research topic in recent literature (Thekumparampil et al. 2018 Shi et al. 2020
let al. 2018b Wu et al.] 2021). Dwivedi & Bresson (2020) use the eigenvectors of the graph laplacian to induce positional information into the graph. The SAN (Kreuzer et al.) 2021) model propose a learnable position encoding module that applies transformer
the eigenvectors and eigenvalues of the graph laplacian. SAN uses the eigenvectors as features(U|n,;)) :"? for nth node) for each node and applies attention over these frequency features, in contrast, FeTA does so over the actual frequency components residing on the graph(U" X, U-Eigenvector, X X-Graph signals). Hence, SAN's attention is over the components of the eigenvectors rather than on the frequency components in the spectral space. Also the vanilla transformer used in SAN would suffer from the issues of not being able to effectively learn the desired spectral response detailed in our theoretical analysis. (Ying al. (2021) 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, Mialon et al. (2021) induce relative position information in the form of diffusion and random walk kernels. Complementary to PE-based models, our idea is to provide alternative view on transformer's expressiveness in spectral space.
Filters on Graphs: 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 (Kipl & Welling, 2017] and variants such as (Zhang& & Meng, 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 figh-freeuency components (Gao et al.) 2021). Approaches in the spectral domain attempt to reduce the computationally complex eigen decompasition of the laplacian by adopting certain functions of the graph laplacian such as Chebyshev polynomials (Defferrard et al. 2016), Cayley polynomials (Levie et al., 2018), and aulo regressive moving average (ARMA) filters (Isufi et al. 2016). These approaches focus on designing specific filters with desirable characteristics such as bandpass and highpass, explaining advantages of spectral filtoring. Hence, at the implementation level, our work focuses on the design of graph-specific learnable filters for transformers, whose frequency response (akin to atlention in spectral space) can be represented in polynomial functions in multiple sub-spaces(i.e. attention heads) of the signal. [ao et al. (2021) is closely related to part of our work which designs filter banks for GNN, albeit task-specific, for heterogeneous and multi-channel signals on graphs.
3 Preliminaries and Problem Definition
We denote a graph as (V,E) where V is the set of N nodes and E 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)s,- The normalized laplacian L of the graph is defined as L = I D- 1 AD- eigenvectors and eigenvalues as: = AU*, where U is an N x N matrix; the columms of which are the eigenvectors corresponding to the eigenvalues .2..,.....AA AN and A = dia A,.).. Let X E R xd be the signal on the nodes of the graph. The Fourier Transform X of X is then given as: X U Similarly, the inverse Fourier Transform is defined as: X == UX. 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
Graph Fourier Transform:
à, The laplacian L can be decomposed into its
3

---

Published in Transactions on Machine Learning Research (07 (07/2022)
response G is given by (below, Um is the mh node in the graph, Up is the hth eigenvector):
(X + () Σ ((W
(1)
(X G)(
Σ (U (ULX)(A)GGA))UU
x= =GG=UXIAYU'X
Spectral GNN: Spectral GNNs rely on the spectral graph theory (Chung et al. 1997). Consider a graph
with U as its eigenvectors, À the eigenvalues, and L the laplacian. Considering spectral GNN at any layer having multiple(fi) sub-spaces, the graph convolution operation in the frequency domain can be obtained by adding these filtered signals followed by an activation function as in (Bruna et al. 2013
ft Udiog (Giss) UOH H!)
where H/ is the jth filtered signal in the +1++ 1)th layer, G.I,A 1 tt imput and jth filtered signal the 1 layer. This formulation non-transferable the learning problem over multiple graphs (Muhammet et al. 2020), ; where the number of nodes could be different and also in graphs with the same number of nodes but different cigenvalues. Thus defined in (Muhammet et al. 2020 G. is re-pa re-parametrized as: G2,51 B[W w "..... W/.S/T, where R is learnable function of the eigenvalues, 5' is the number of filters and Wi, is the learnable matrix for the sth filter in the /th layer. The Equation 2 depends on the computation of the eigenvectors graphs. In our work, we consider the polynomial approximations as proposed by Hammond al. (2011) Specifically, the frequency response of the desired filter is approximated as:
is the learnable filter response between the
L, which is computationally costly for large
K
a
(()
33)
k=
where Tk) is the polynomial basis such Chebyshev polynomials (Defferrard et al. 2016), = 24
Amez 1, Amar
is the maximum eigen value and a is the corresponding filter coefficients. recursive formulation could be used for the Chebyshev polynomials with basis To(x) 1, Ti (x) x and beyond that Th (xx) = 2x (x) - -he 2
Thus, the convolution operation in Equation can be approximated:
KJ
Rf
X+GRU
Σ kmD
U'x Σ a ('TT((
(4)
kf d'Tx
k=
This corresponds to an FIR filter of order K Smith et al. 1997 Setting a as a learnable parameter helps learn the filter for the downstream task.
Problem definition In this work, aim to learn the filter coesficients from the attention weights of the transformer. Formally, given the transformer attention for the head h at layer I as A RNN, aim to define a mapping M RNxN > R where KJ is the filter order. The mapping M would take us from the space in the attention weights to the filter coefficient space for defining corresponding attention in the spectral domain on graph frequencics.
4 Theoretical Foundations
Since GNNs have been well-studied in spectral space (Defferrard et al. 2016 Nt Machara 2019 Bianchi et al., 2021) with an already established link between its spatial and spectral domains (Balcilar 2020b), first. intend to draw equivalence between transformers and spatial GNNs (proofs are in appendix
4

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Lemma 4.1. The attention of the transformer is,
QK" Vooue
Attention" (Q, K,V) softmar
which is special case of the spatial COnvGNN defined
H E (CCHwwll)))
with the convolution kernel set to the transformer attention where W(l.)) the trainable matrir for the l-th layer's ' s-th convolution kernel(C*) ) and S the desired number of convolution kernels.
The lemma 4.1 brings the transformer attention into the space spatial Convolution GNN (ConvGNN). is worth noting that the convolutional support/kerne in the case of transformers is function of input node embeddings (which is not static). This is in accordance to the definition of convolution supports for other atlention based architectures such GAT in Balcilar et al. (2020b). This property, we argue could give the transformers the ability to learn dynamic filters for given graph, rather than rely on a fixed kernel. Further, Balcilar et al. (2020b) already prove that the spectral GNNs are a special case of spatial ConyGNN. We now study the relation between the transformer (altention) and spectral GNNs.
Megnitude
Magntude
Meggn
Egenduuss
Eigenvaluss
Elgenvatues
(a)
(b)
(d)
Figure 1: Aggregate Filter Frequency response on Zinc Regression datasct (section A.4 for (a) Vanilla Transformer (b) Transformer with learnable position encoding from SAN (Kreuzer et al. 2021 (c) FeTA (section 5), and (d) FeTA induced with laplacian position encoding. X axis shows the normalized frequency with mdgnitudes
the Y axis. Transformers approximately seem contain the low-pass filter response. However, FeTA shows considerable improvement in learning the desired filter responses.
We begin by defining measure of error between matrices in the two spaces. Consider C, to be the set of all possible attention maps of transformer. This is the subset of of nodes in the graph, such that the rows form a probability distribution i.c., each value is greater than equal to 0 and the rows sum to and is the row-wise softmax of the gram matrix. Thus C. is a subset of the space of all stochastic matrices size n. Consider F(A) or F to be the diagonal matrix containing the desired frequency response of the spectral GNN. A (iiag(A,,) A2, the desired filter response and we let A2.......u >n] E R i.e., we consider the entire vector space. We take U R=xn to be the eigenvectors of the laplacian of the graph. Thus, the convolutional support of the desired spectral GNN is C = UFUT, The error (E)) between an arbitrary attention map C₁ and filter F, for given graph is defined as the frobenius norm of the difference between C, and C as below:
matrices, with being the number
is the diagonal matrix containing
E(CG, Cy) = ||C₂ - Cyllr = |C. - -UFU
(5)
By definition, the error would be 2 0. We would like understand whether the error becomes precisely equal to 0 for given F. What the class of response functions where the error is 0 i.e. the transformer would be able to exactly learn the desired filter response, for some graph signal? In other words, is the transformer able to approximate any desired graph frequency response upto a desired precision to be fully expressive in spectral domain, similar to spectral approaches such as Isufi et al. (2016); He et al. (2021)? not, for the set of filter responses that the transformer is not capable of learning with 0 error, what are the bounds within which the transformer would approximate the filter response of the spectral GNN, for any given graph signal? The following theorems help understand the answer to these questions.
5

---

Published in Transactions on Machine Learning Research (07 (0222)
Theorem 4.1. The error function E, Cg) between the convolution supports of the transformer attention and that in the space of spectral GNNs has a minimum value of 0. Considering the case. of non-negolive weighted graphs, this minima oan be attained at only those frequency responses for which the magnitudes at all frequencies (c(Cg) I 1 and the low(0) frequency response Xn(Cg) =1.
In the above, expression Ax(Cg) is the ith diagonal entry of F used in eq Theorem 4.1 has an important implication that transformers can learn only a filter response having a the low(O) frequency component effectivcly i.c. with error. This is essentially the class of filters consisting of frequency responses such low pass, band reject etc. that have a maximum magnitude of 1 in the pass band in the Offrequency component). For any other filter response, the transformer attention map can at best only be an approximation to the desired frequency response with non error (cf., Figure Dp. The next theorem gives lower and upper bounds on the error, also summarizing inherently limited expressiveness of transformer in spectral domain.
Theorem 4.2. The minimam of the ervor given by E(Cr, Cg) over Ct, between the comvolution supports of the set of stochastic matrices (which is superset of the tronsformer attention map) and spectral GNN, for given filter response F, is bounded below and above by the inequalities
Damin S EEC, Cg) S [Amaxl
where Amin, Amaz are the minimam and mazimum of the absolute of the eigenvalues OFU(F-TJD TJUT respectively and Oj = arg min E(Cr, Cg),, For the set of transformer attention maps Ct the upper bound is relaxed as Ct
E A
Observed from the term (F- the error increases as the filter deviates from the identity all pass matrix. Thus the error is unbounded F - co, indicating that for certain choices of filters the transformer attention its own may be bad approximation.
5 FeTA: Frequency Attention Transformer
Derti Soins
Atartion
61)
Cookilents
Laper
OIN
INPUT
Spulini Aftention Transtorrar
2 From Spurial Spocrral Raaeo
37 Modale
DYNAIIC
GRAPH
Figure 2: FeTA Framework: The first step aims to capture the spatial connectivity of the input graph in the form of an attention map. The second step uses each attention head's weights and learns the multiple filter coefficients using the GNN. Finally, the third step employs a spectral GNN with filter coefficients as input capture the desired frequency response. Hence, the architecture allows us to learn spectral components using the spatial connectivity pattern of the signals the original graph obtained from the attention map.
5.1 FeTA Architecture
We aim to inherit the attention map and project it to desired filter frequency responses for given graph as our key architecture motivation. It is evident from the literature that spectral GNNs can learn static filter responses for given data distribution (Defferrard et al. 2016). Hence, we propose an architecture that augments spatial attention with a filtering module using spectral GNN. However, our architecture novelty is to use the transformer attention map to learn the filter cocfficient of spectral GNN dynamically. By doing so, we can learn the desired frequency response for given graph. Moreover, this can help capture the spectra's beneficial components (i.e., desired frequencies), which could be different per graph. Another benefit for

---

Published in Transactions on Machine Learning Research (07/2022)
adapting spatial attention of the transformer in architecture is that it addresses the performance issues of
GNNs such as over-smoothing (Zhao & Akoglu 2020; Oono & Suzuki, 2020 Li et al. 2018a). suspended
animation (Zhang & Meng 2019), and over-squashing (Alon & Yahav 2021 Topping et al. 2022). The
Figure 2 illustrates FeTA architecture with three steps:
1. Spatial Attention Transformer: we view the graph as set 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:
AllentionWeiguee eights"(Q, (Q, = softmaa
(6)
Viout
Here, Q= = X and K = X where Q' W E R are the projection matrices for the query and key respectively for the head h. The output X the head h can be obtained from eq 6 and node features V as:
QK?
x = Attention " (Q,K,V = softmar
V
(7)
douu
Next, we utilize the spatial information learned by the attention heads of the transformer to dynamically decide the filler coefficients (i.e., distinct filter coefficients for each head). The transformer naturally gives diverse attention sub-spaces, which are utilized by FeTA to design multiple filters covering broad spectrum of the graph. This enables interpreting the association between a particular frequency component with cach head for a given graph. Furthermore, it also helps select the useful range of information in the frequency domain for different sub-spaces (attention heads in FeTA). Our reasoning emerges from: 1) If the graph spectrum consists of several underlying components relevant for different sub-graphs, then it is paramount to dynamically learn the filter coefficients. 2) when certain classes are skewed, a task-spocific filter would learn generic coefficients for the majority class, when keeping limit on the number of filters.
2. Mapping from Spatial-Spectral Space: In order to obtain the filter coefficients from the weights of each attention head, we use a GNN layer. Our motivation to add a GNN layer in FeTA architecture (Figure 2 is that different filter shapes must discriminate the spectral components associated with distinct. graphs. Therefore, we first aim to utilize GNN's position invariant message passing ability for capturing the connectivity pattern in the spatial domain. Attention map provides inference to the connectivity of a graph implicitly, using which, we can deduce the frequency band to filter out the noise. If each node's signal øt is considered with its neighborhood ((xx) which represents the non-zero attention weights obtained from Equation 6 then the message passing is:
Uy(2,, Zim = Ar(2// E = (mm)
where of and zimm are the signals and the aggregated message at node x; in the layer I. Here, As and Uy are the aggregation and update functions respectively. This framework enables the usage of popular message passing schemes of GNN. For example, one the aggregation is a simple projection of the signals followed by a summation weighted by the normalized laplacian with self loops. Next, the update is an activation function such as RcLU, The final equation is now represented as below:
A141 =a
Σ (FE
(8)
where x. is the node embedding for the jth node in the I-th layer of the GNN learn coefficients) for
the h-th head of the transformer, L= I A is the normalized laplacian and W! is the learnable projection matrix at layer L. This GNN is common for all the heads and at all layers of the transformer. Here, the node embeddings reside in the coefficient space i.e. X E RNK where K is the order of the filter. For learning the filter coefficients we initialize the node embeddings with a 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 5.1 (cf., Appendix A.1 for proof).
p
Property 5.1. The filter coefficients consisting of the vector of all ones is an all-pass filter.
7

---

Published in Transactions on Machine Learning Research (07 (07/2022)
After the L-th message passing, the vector obtained from Equation is given to readout function such global average pooling followed by feed forward network to obtain the final filler coefficients a², per attention head:
g
N
a" = MLP
2
h.L
(9)
where nf is the vector at node 2; in the h-th attention head obtained from Equation 8 3. Filtering Module: We use the filter coefficient a² to obtain the appropriate filter frequency response
Kf
(10)
where K the filter order. The desired filter response Hh at head h can then be obtained from Gh
as
observed in Eq 4
H = x G = UŌ (L)x** K³
The filter outputs from each head is concatenated to get the filtered output which is further concatenated with the attention output X, followed by an MLP, with appropriate normalizations, for the output of the encoder layer:
= H X MLP((IX") X = -Morm + H))
here, denotes the concatenation operator. This could then be used in the downstream task of classification, regression, etc. In order to ensure learning of distinct filter coefficients for each head (i.e., dynamic filtering), we add regularization term to the objective. The regularization trics orthogonal to each other. It does 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' E R and X [a a² ..?.....) ] E Rexh where h is the number of heads and A is the filter order. The regularization term is given by [((*x) o (1@1-1
keep the cocfficient vectors
11l01-10 (0--)) 12222, where I E Rhxh is the identity matrix, O and @ are the hadamard and kronecker products. The below theorem (proof in Appendix A.2h bounds our proposed method.
Theorem 5.1. Assume the desired filter response G(x) has m + 1 continuous derivatives on the domain [1,,]]. Let ST, G(z) denote the K2 order approzimation by the polymomial chebyshev) pohmmomia((chebyshee) filter and ST G(x)
denote the learned filter, Cj be the first absolute moment of the distribution of the fourier magnitudes of f (function learned by the network), h the number of hidden unils the network and N, the number of training samples. Then the error between the learned and desired frequency response bounded by:
KgO h
hK3² N. log(No) + Ky -m
[G(z) G(x)==
+
The above theorem provides the bound between the desired frequency response and that learned by FeTA. It states that as the filter order Ky and the hidden dimonsion of the network are increased (subject to K2 K2² < hK2² S ,=) the approximation will converge the desired filter response. The condition h < Na of sample size. In the limit of N₂ > oc, h and Ky could be increased to as large values as desired subject to 2 O(y)), which the order of parameters to be approximated. This is equivalent to say that if we do not consider the generalization error, we can theoretically take a large h. Then, we are left with only the term containing the filter order i.e. the approximation error comes down to O(K,-m) as expected. One
K can be thought to satisfy the statistical rule that the model parameters must be less than the order
8

---

Published in Transactions on Machine Learning Research (07/2022)
point to note is that we assume suitable coefficients can be learned from the imput. This assumption requires that the graph has the necessary information regarding spatial connectivity and signals. The context. of assumption is that the filtering module which learns the filter coefficient needs distinct inputs for different graphs. And, if we could feed distinct representations for different graphs, the filtering modulc could learn the filter coefficient as desired. For vanilla transformers, this may not always hold true, for example, two graphs have different structures and the same signal values. It will result in a similar attention map and will learn same filter responses. We can resolve this issue by imposing structural encodings. In general, cases, if the representations have injective mapping then the filtering module will be able to learn desired response per graph (up to a certain precision). Theoretically, the assumption requires that we feed different. representation for distinct graphs to the filtering module. From the literature, we know that the K-WL test could be used to distinguish between non-isomorphic graphs and we also have GNNs that are as powerful as WL-Test. For future, modifying spatial attention of transformers to be able to learn injective representations is a promising direction to explore. Currently, we only use the information from the signals residing on the graph nodes in the altention heat map and discard the spatial connectivily. Nevertheless, the current implementation does well against vanilla transformer,
is evident from the results the real world (section ( and synthetic AA.7 datasets. We do attempt to model the filter coefficients using the connectivity structure imposed by the original graph as input, albeit with minimal empirical gains (Table 13). The potential reason for limited performance could be that frequencies on the graph cannot be deduce from the structure alone and we may need better approaches to combine the signals and graph structure for more precisely learning the optimal frequency response of the graph beneficial to the task.
The space and time complexity of our method is O(N2) for full attention. This could be alleviated by using sparse attention (cf., Table 3). One may also use kernel methods as in (Choromanski et al. 2021) to reduce the number of nodes in the graph and then apply the transformer on the reduced graph. Similar to a vanilla transformer, FeTA cannot induce positional encoding (PE) on its own, which also has implications for its empirical performance against vanilla GNNs. However, for the heterophilic setting, FeTA-base performs better than vanilla GNNs (cf., Table 6) 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. Theoretically, PE methods like GT (Dwivedi & Bresson 2020) or SAN (Kreuzer et al. 2001] use complete cigen decomposition constituting ((N)) complexity. However, such additional cost is added by few of the existing PE methods. Since our method is agnostic of the PE, with the development of computationally effective PEs, extra computational costs can be eliminated for FeTA.
Limitations
6 Experiment Results
We aim to answer following research questions: RQ1: Can dynamic graph filtering improve FeTA's ability over base transformer for graph representation lcarning? RQ2: What is the efficacy when a low-pass filter GNN induced with FeTA's 's ability to perform attention over entire graph spectrum? RQ3: What is the impact of recently proposed position encoding (PE) schemes on FeTA?
Datasets and Settings: We use widely popular datasets (Mialon et al 2021: Hu et al. 2020 MUTAG, ΝCI1, and the OGB-MolHTV for graph classification; PATTERN and CLUSTER for node classificat ion; and ZLNC for graph regression task (details in A.4]. We borrow experiment settings and baseline values from
Dwivedi & Bresson 2020: Mialon et al. 2021 Kreuzer et al. 2021
Baselines We first benchmark FeTA against vanilla transformer Vaswani et al. (0177 To study impact of
position encoding on FcTA, we compare against recent PE-induced vanilla transformer basod approaches, namely Graph-BERT Zhang et al. (2020), GT (Dwivedi et al. 2020), SAN (Kreuzer et al., 2021). GraphiT
MMialon et al.
2021 , and Graphormer (Ying et al.) 2021). along with other message passing GNN models
such as GCN Kipf & Welling, 2017). GIN (Xu et al. 2018). GAT (Veličković et al.] 2018), GatedGCN
Bresson & Laurent 2017), and PNA (Corso et al. 2020 also with spectral GNNs such as BankGCN
Gao
et al. 2021) and Chebnet (Defferrard et al. 2016).
FeTA Configurations: For a fair and exhaustive comparison, we provide seven variants of FeTA: 1) FeTA- -Bss to compare against vanilla transformer without position encoding module, 2) for generalizability study, FeTA-GAT replacing transformer attention in Step 1 of Figure 2 with GAT's attention. 3) Fe + LopF
9

---

Published in Transactions on Machine Learning Research (07/2022)
(2021) 4) F consists of position encoding 2021 5) Fe GCKN+3RW that uses GCKN (Chen et al. based on 3-step RW kernel from Mialon et. al.
contains static position encoding from Mialon et al.
2020ah in addition with 3-step RW kernel to induce graph topology, 6) FeTA+LPE+Pul with learnable inheriting learnable position encoding from Kreuzer et al. (2021) (cf., A.3 for implementation details). Using PE-induced Fe variants, in experiments, we aim to study if FeTA's 's ability to attend over graph spectrum complements the ability of position encodings in learning topologiall information, and is there any performance gain?
position encoding (Krouzer et al., 2021 with full attention. 7)
Models
MUTAG ACC
NCI % ACC
ZINC MAE
ogb-MOLHIV % ROC-AUC
PATTERN % ACC
CLUSTER % ACC
Vanilla Transformer
82.2 #6.3
70.0 + 4.5
0.696 0.007
65.22 + 5.52
75.77 + 0.4875 78.65 2.509
21.011 + L.013 30.351 2.669
FeTA-Base
87.22..8
73.7 + 1.4
0.412 - 0.004
67.59 + 1.83
Table 1: Results on graph/node classifcation Tasks (RQ1)). Higher (in red) value is better
(except for ZINC).
Models
MUTAG
NCI1
ZINC
ogb-MOLHIV
PATTERN
CLUSTER
GAT
80.3 8.5
74.8 4.1
0.384 0.007
71.18+0.27*
78,271 + 0.186
70.587 = 0.447
FeTA-GAT 85.18 2.8
78.67 + 1.2
0.279 + 0.008
76.69 + 0.17
84.756 + 0.128
71.848 + 0.448
Table 2: FeTA-GAT performance increases when FeTA's ability to perform attention over entire graph spectrum has been induced in GAT which a low-pass filter (RQ2), empowering GAT to attend to all frequencies. (red higher except for Zinc calculated by us.);
6.1 Results
FeTA-Base outperforms vanilla transformer (Table 1 across all datasets establishing the positive impact of combining dynamic filtering with spatial attention into FeTA.
Generalizabllity Study: For RQ2, we study FeTA's ability to learn dynamic filters for covering entire graph spectrum improves performance of a GNN. Hence, we chose GAT, that learns low-pass filters [Bacillar et al. (2020b). Table 2 illustrates that on similar parameters, FeTA-GAT outperforms GAT on all datasets concluding the generalizability of our approach to GNNs, also proving FeTA architecture works agnostic of specific form of attention mechanism and position encodings (PEs).
Effect of PE: To understand effect of PEs, we replace vanilla transformer with FeTA in original imple- mentation of Dwivedi & Bresson (2020); Mialon et al. (2021): Kreuzer et al. (2021). ). We keep nearly same parameters to understand fair impact. We observe (Table 3) that for the smaller MUTAG and NCI1 datasets, FeTA achieves the best results against baselines using the structural encoding of GCKN. It indicates that these datasets benefit more from structural information. Also, lower results of spectral GNN-based models (ChobNet and BankGCN) than FeTA configurations support our choice for combining both spatial and spectral properties in FeTA On OGB-MolHIV and PATTERN/ CLUSTERRs graph and node classification tasks, learnable position encoding has most positive impact on FeTA Graphformer reports the highest value on MolHIV. However, its parameters are 47M compared to & 500K from FeTA+LPE, GCN-based models, and SAN. Notably, we see that FeTA performs exceptionally well on the graph regression task ZINC with a relative decrease in the error of up to 50%. Potential reason could be FeTA's ability to learn diverse filters that are distinct for each graph (c.f, Appendix A.8 for frequency images). An important obscrvation is that PE scheme provides homogeneous performance gain across all datasets for FeTA (neither for vanilla transformers). Also, FeTA's ability complements PEs performance for further improving the overall performance (answering RQ3).
We created configuration (FeTA-Static) where the filter is static per dataset based on attention heads (i.e., directly adapt Equation for 4 with the learnable parameter a instead of computing a from the attention weights). Our idca here is understand the impact of combining multi-headed attentions with a graph-specific dynamic filter. From Table we clearly observe the empirical advantage of FeTA-Base. For second ablation, we note, equation 10 represents polynomial filter using the Chebyshev polynomials
Filter Ablations:
10

---

Published in Transactions on Machine Learning Research (07/ (07/2022)
Models
MUTAG
NCI
ZINC
ogb-MOLHIV
PATTERN
CLUSTER
GCN
18.9=10.1 NA
75,9 + 1.6
0.367 = 0.011
76.06 + 0.97
71.92 + 0.334
68.498 0.976
GatedGCN
NA
0.282 + 0.015
NA
85.568 + 0.088
73.840 + 0.326
GAT
80.3 + 8.5
74.8 + 4.1
0.384 + 0.007
0.278
78:271 + 0.186 NA
70.587 0.447 NA
PNA
NA
NA
0.142 = 0.010
79.05 + 1.32
GIN
82.6 + 6.2
81.7 + 1.7
0.526 = 0.051
75.58 + 1.40
85.387 + 0.136
64.716 + 1.553
ChebNet
82.5 + 1,58
81.8 2.35
NA
74.69 + 2.08
NA
NA
BankGCN
$2.89 + 1.61
82.06 + 1.75
NA
77.95 + 1.56
NA
NA
Graph- BERT
NA
NA
0.267 2 0.012
"NA"
75.459 & 0.216 NA
70.790 E 0.337 NA
Graphormer
NA
NA
0.122 # 0.00G
80.51 + 0.53
CT-sparse
NA
NA
0.226 + 0.014
NA
84.808 + 0.068
73.169 + 0.662
GT--Full
NA
0.598 + 0.049
NA
56.482 + 3.549
27.121 8.471
SAN-Sparse
78.8 2.9
80.5 1.3
0.198 = 0.004
76.61 + 0.62
81.329 + 2.150
75.738 0.106
SAN-Full
71.9 2.9
71.93 + 3.4"
0.139 + 0.006
77.85 + 0.65
86.581 0.037
76.691 0.247
CraphiT-LapE
8
74.6 + 1.9
0.507 = 0.003
65.10 1.76*
0,738* 76.701
18.136 = 1.997*
GraphiT-3RV
83.3
77.6
0.244 0.011
64,22 4.94
U.9211 76.694
21.311 + 0.478
GraphiT-3RW + GCKN
7.0
81.4 2.2
0,211 = 0.010
53.77
2.73
75.850
0.192
69.658 = 0.895*
FoTA LapÉ (ours]
2.6
75.4
0.077 + 0.001
06.80 2.18
78.808 + 1.662
19.306 3.818
FoTA 3RW (ours)
2.6
78.5
0.104 = 0,005
59.95 - 3.91
77.285 + 1.146
68.572 2.164
FoTA GCKN + 3RW (ours)
9.6
83.0 0.5
0.068 + 0.002
53.50 + 5.89
77.86 0.573
67.507 2,856
FeTA LPE + Full (ours)
72.2 +
72.99
0.5
0.1836 0.002
76.88 0.573
86.52 0.013
76.750 0,296
FeTA- LPE + Sparse (ours)
79.6
+ 2.6
$1.0 + 1.5
0,1581 0.001
78.10 + 0.303
86.30 + 0.024
77.224 + 0.111
Table 3: Impact of external position encoding (PE) schemes (RQ3). For dataset, red and blue colors
represent the highest and the second best result,, respectively. The baselines values are from Kreuzer et. al.) 2021 Mialon et al. 2021] and values with * are calculated by us. None of the PE method works agnostic of dataset neither for previous vanilla transformer-base able to complement the performance of various PEs, achieving best values on majority of datasets.
models, nor when induced FeTA. However, FeTA is
Modela
MUTAG
NCI1
ZINC
ogb-MOLHIV
PATTERN
CLUSTER
ReTA-Base
87.2 + 2.6
78.7
+ 1.4
0.004
87.59
1.88
78.65
2.509
80.851
2.669
ReTA-Static
83.3
= 1.3
70.4
- 3.8
0.470 = 0.002
67.10 + 3.647
76.03 = 0.861
20.995 4 0.005
ROTA-ARMA
85.1
1.3
+ 2.1
0.355
0.007
65.45
4.237
76.93
0.279
20.390
2.859
Table 4: For Ablation studies, comparing FeTA-Base against: 1) FeTA-Static that uses static filter and
2) ReTA-ARMA which changes the filter in base configuration to ARMA Tsufi et al. (2016), illustrating non-dependency architecture on particular type filter as Chebyshev filters are used in base configuration.
Defferrard et al. 2016). We used Chebyshev polynomials for spectral approximation as it has been defacto in the literature. Polynomial filters [Hammond et al.) 2011] are smooth and have restrictions that they cannot model filter responses with sharp edges. Hence, we devise FeTA-ARMA that uses rational filters such as ARMA (Isufi et al. 2016). It can be observed from Table 4 that FeTA-ARMA resulted in lower performance than FeTA-Base on most of the datasets. However, on ZINC, there is an improvement using ARMA compared to Chebyshev polynomial filters. Hence, we remark that filter response and empirical predictive performance could be orthogonal objectives, and it becomes tradc-off to decide which type of filter to apply for a given task.
Learnt Filter Frequency Response: In this section we analyze the frequency response of the filters learned on graphs of some of the datasets. Further plots and analysis on other datasets can be found in the appendix (cf. A.S).. In Figure g we see that for sparse graphs (graph (a) - (c)) the filter response has a prominent magnitude for the lower components of the spectrum along with some components in the middle regions of the spectrum. This could indicate that for smaller graphs (a) the immediate neighborhood signal benefits the task. For graphs with larger diameter (b,c) we may interpret that along with neighbor signals aggregating information from the nodes farther in the chain is important the model learns to focus on frequencies in the middle region. On the other hand, for denser graphs, we see a relatively less prominent low frequency response and many heads learning to focus on the higher frequency components of the spectrun. In a sense, this enables aggregation of nodes that are distant in the graph(eg. in different clusters) and helps in providing interpretation as which nodes interact the spectral domain. Note that existing graph-specific attention mechanisms, such as GAT, learn only low pass filters (Muhammet et al., 2020)) and cannot perform such aggregation. Our model aims to learn filters having different frequency responses specific to the data
11

---

Published in Transactions on Machine Learning Research (07/2022)
distribution per graph and they tuned to be beneficial to the downstream task. These observations justify our rationale to propose groph-specifie filters.
(a)
(b)
(c)
(d)
(o)
(1)
K
(h)
(i) K
( K
Figure 3: Filter Frequency response of FeTA on individual graphs. Graph (a) is from MUTAG and, (b)~ (e) are from the NCI1 dataset and Figures (f) (i) are the corresponding frequency responses. X axis shows the normalized frequency with magnitudes on the axis.
Extended Experiments: Considering RQ2 focuses on under- standing FeTA's 's ability to improve the performance of GAT, we further extend our empirical study to analyze the behavior of FeTA induced in the recently proposed attention mechanism of GATv2 (Brody et al. 2022). GATv2 aims to strengthen attention interesting (dynamie) filter-
Datasets
GATv2
FeTA-GATv2
Mutag NCI1
83.33 + 0.001
85.18 + 0.032
75.75 + 0.012
77.29 + 0.006
mechanisms GNNs and have ing. In Table 5] see that the empirical results align with FeTA results GAT. This empirically verifies that FeTA could work for other attention mechanisms besides transformers. Despite our empirical ovaluations partly focusing on improving general attention mechanisms,, future works could theoretically study the expressive limitations of the general class of attention-baat based models in the spectral domain (if it exists).
Table 5: Table shows the results by induc- ing FeTA in GATv2.
Method
Accuracy
GCN
33.65 + 1.68
GAT
30.16 1.32
GATv2
25.06 3.13
MLP
72.75 +: 1.51
Furthermore, to strengthen the paper's choice of Chebyshev filtering in the face of non-homophilous data, extend our empirical evaluation to heterophilous datasets. We we borrow experimental scttings from Tailoor et al. 2022). Specifically, we run experiments on the pure heterophilous setting the syn-cora dataset. The results are reported in Table 0 Here, FeTa- Base is comparable to models performing well in this setting, which indicates that FeTA can learn heterophilous information well and verifies that it is to capture broader range of the graph spectrum.
MixHop
62.50 - 1.16
FeTA Base
65.55 + 3.15
Table 6: Accuracy on the pure heterophilic setting of syn-cora dataset. On the top we methods that fail work well in this setting whereas the bottom we report methods that work relatively better.
7 Future Directions and Conclusion
This work primirily focuses on the understanding of transformers from the spectral perspective and establishes the theoretical evidence on its limitations. Hence, our work opens up a new direction to study transformers more rigorously in spectral domain unveiling several new insights. Our proposed FeTA framework effectively learns multiple filters per attention head to capture heterogeneous information spread wider frequency
12

---

Published in Transactions on Machine Learning Research (07 (07/2022)
domain. Experiments standard datasets of various tasks suggest clear empirical edge vanilla transformers. Results in Table 2 provide critical finding that GAT, when induced with the ability to attend to the entire graph spectrum, shows significant performance jump across tasks. Additionally, our work provides a conclusive statement on the limitations of position encodings. Considoring graphs have also been viewed literature from signal processing side, hence, the need for signal processing(fleerig noise removal etc.) orthogonal to the need for position encodings (inducing relative node positions). Hence, our work provides the first step toward studying transformers orthogonal to the popular position encoding based school of thought.
What's Next: We leave readers with the following open research directions emerged based on our work: 1) How can the ability to learn topological information be inherently induced in FeTA? 2) Is it possible to develop universal position encoding (initial works such as Luo et al. (2022)) ) that provides a consistent performance agnostic of dataset? As our work provides findings on limitations of the existing PEs and paves way for universal PEs for transformer which is a future direction. 3) Is it possible
learn the desired filter response with better precision using an iterative algorithm?? 4) Can the method be scaled to large graphs by making the computational complexity (sub)linear? 5) Can the self-attention of the transformer be altered to fix the transformer's limitation in expressing arbitrary spectral filters? 6) Can universal approximators such as GATv2 and other families of attention models be studied theoretically in the spectral domain to study their expressive power (i.e., generalizing our theoretical analysis to larger group of attention models)?
Acknowledgment: This work was partly supported by Japan Society for the Promotion of Science (JSPS) Kakenhi Grant Numbers 21K21280 and 21K17749. Additionally, thank anonymous reviewers of TMLR for detailed constructive discussion work.
References
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In Ith International Conference on Learning Representations, ICLR 2021, Virtual Evenl, Austria, May 3-7, 2021. OpenReview.net, 2021.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference on Learning Representations, 2020a.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Bridging the gap between spectral and spatial domains in graph neural networks. CoRR, abs/ abs/2003. 1100, 2020b.
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ò. Dircctional graph networks. ICML2201, 2021.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 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.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv: 2017.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2022.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs, 2013. URL http:::/aaaxv..or///aaaaaa 1312//233......
13

---

Published in Transactions on Machine Learning Research (07/2022)
Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph-struchured data. In International Conference on Machine Learning, pp.
PMLR, 2020a.
Fenxiao Chen, Yun-Cheng Wang, Bin Wang, and C-C Jay Kuo. Graph representation learning: survey. APSIPA Transactions on Signal and Information Processing, 9, 2020b.
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, National Science Foundation (U.S.), American Mathematical Society, and Conference Board of the Mathematical Sci- ences. Spectral Graph Theory. CBMS Regional Conference Series. Conference Board of the mathematical sciences, 1997.
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 works graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844 3852, 2016.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs 2020.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks. arXie preprint arXiv:2003. 0098,, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. ICLR, 2022.
Xing Gao, Wenrui Dai, Chenglin Li, Junni Zou, Hongkai Xiong, and Pascal Frossard. Mcssage passing in graph convolution networks via adaptive filter banks. arXiv preprint arXiv:2106.09910 2021.
Saul I. Gass and Michael C. Fu (eds.). KaersshKKhhn--- Kuhn--uccer (KKT) Conditions, pp. 833 23-834..4 Springer US, Boston, MA, 2013. ISBN 978-1-4419-1153-7.
S. Gerschgorin. Uber die Abgrenzung der Eigenwerte einer Matriz, Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nouk (in German), pp. 749-754
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1263-1272. JMLR. org, 2017.
Geoff Gordon and Ryan Tibshirani. Karush-kuunn-tucke conditions. Optimization, 10(725/36):725 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Tn Advances in 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.
Mingguo Hc, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 2021.
Roger A Horn and Charles R Johnson. Norms for vectors and matrices. Matriz analysis, pp. 313-386, 1990.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In In Advances in Neural Information Processing Systems, 2020.
Elvin Isufi, Andreas Loukas, Andrea Simonetto, and Geert Leus. Autoregressive moving average graph filtering. IFF.F Transactions Signal Processing, (6(2):274-288) 2016.
14

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, TCLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourncau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. NewrlPS 2021, abs/2106.03893, 2021.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1): 97-109, 2018.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Thirly-Second AAAT conference artificial intelligence, 2018a.
Yuan Li, Xiaodan Liang, Zhiting Hu, Yinbo Chen, and Eric P Xing. Graph transformer. 2018b.
Shengjie Luo, Shanda Li, Shuxin Zheng, Tie-Yan Liu, Liwei Wang, and Di He. Your transformer may not be 2022.
as powerful as you expoct. arXiv preprint
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.0566 05667,, 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go ncural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 33, pp. 4602 4609, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. Tn ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Balcilar Muhammet, Renton Guillaune, Héroux Pierre, Gaüzère Benoit, Adam Sébastien, and Paul Honeine. When spectral domain meets spatial domain in graph neural networks. In Pherty-seventie International Conference on Machine Learning (ICML 2020)- Workshop Graph Representation Learning and Beyond
(GRL+ 2020), 2020.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. ar preprint ar Xr::;:1905 09550, 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 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 828, 2018.
Namuk Park and Songkuk Kim. How do vision transformers work? arXiv preprint arXiw:2202.06700 2022.
Giuseppe Peano. Resto nelle formale di quadratura espresso con 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(1):61-80, 2008.
J. Schur. Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen. Journal für die reine wnd angewandte Mathemattkk (Crelles Journal), 1911(140):1 28, July 1911. ISSN 0075-4102, 1435-5345.
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 Xiv:20000 Xix:2009.00300, 2020.
15

---

Published in Transactions on Machine Learning Research (07 (07/2022)
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 networks 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.
Shyam Tailor, Felix Opolka, Pietro Lio, and Nicholas Donald Lane. Do we need anisotropic graph neural networks? In International Conference on Learning Representations, 2022.
Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv:1803.00 03795, 2018.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference Learning Represenlations, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz, Kaiser, and Illia Polosukhin. Attention is all you need. In 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.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Hsien-Chung Wu. The karush kuhn tucker optimality conditions in an optimization problem with interval- valued objective function. European Journal of operational research, 176(1):46-5)) 59, 2007.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and lon Stoica. Repre- senting long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266 13279, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arxiv: 1810. 00826, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net 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 2021, arXiv preprint arXiv:2106.0522 05523444, 2021.
Chulhce Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators sequence-to- to-sequence functions? International Conference on Learning Representations, 2019.
Chulhee Yun, Yin- Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. O (n) connections are expressive enough: Universal approximability of sparse transformers. In NewrIPS, 2020.
Jiawei Zhang and Lin Meng. Gresnet: Graph residual network for reviving deep gnns from suspended animation. CoRR, abs/ Aos/1999,,5729, 2019.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention needed for learning graph representations. arxio preprint arXim:2001.051.0 2020.
16

---

Published in Transactions on Machine Learning Research (07/2022)
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In 8th International Conference on Learning Representations, TCLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nec, 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 applications. AT Open, 1:57-8 -1, 2020.
A Appendix
A.1 Extended Architecture Motivation
In the previous section, we have established the conclusive limitations of transformers in the spectral domain. Specifically, the transformer attention map, which acts as convolution support, learns a family of functions containing low-pass responses. We aim to inherit the attention map and project it to desired filter frequency responses for given graph as our key architecture motivation. It is evident from the literature that spectral GNNs can learn static filter responses for given data distribution (Defferrard et al. 2016). Hence, propose an architecture that augments spatial attention with filtering module using spectral GNN. However, our architecture novelty is to use the transformer attention map to learn the filter coefficient of spectral GNN dynamically. By doing so, we can learn the desired frequency response for a given graph. Moreover, this can help capture the spectra's 's beneficial components, which could be different per graph. Another benefit. for adapting spatial attention of the transformer in our architecture is that it addresses the performance issues of GNNs such over-smoothing (Zhao & Akoglu. 2020), suspended animation (Zhang & Meng 2019), and over-squashing (Alon & Yahav 2021). An additional motivation for our architccture is the necessity of filtering over graphs. A graph is a structured data with signals residing on it and as with any signal processing system, filtering is beneficial in applications such as increasing the signal-to-noise ratio, performing sampling over graph nodes, etc. Further motivation and applications of filtering could be found in Ortega eet al. (2018) and SShuman et al. (2013). Please note that alternative archilecture designs, such as improving the vanilla transformer's 's limitation in expressing arbitrary spectral filters (e.g., by modifying self-attention), could be explored as future research and are out of the scope of this work.
A.1.1 Preliminaries for Architecture Design
As explained in the previous subsection, our architecture builds upon spatial attention as input. We aim to design architecture that creates an effective mapping between transformer attention map to spectral space. For simplicity, consider an arbitrary graph with two nodes. The transformer attention on nodes gives a 2 x 2 attention map (Figure illustrating the space mapping). We consider each position of map as a basis spanning a 4D vector space. For plotting in 3D, we squish the matrix into a 4D vector, and consider the 3D slice fixing the third dimension at zero. The set of matrices having low pass characteristics (all-pass identity matrix E in the figure) will lie in the spectral space. The other points (point D in figure) have a non-zero error between the transformer attention space and the space of the filter response.
A.2 Theoretical Motivations and Justification of the approach
In the following result we intend to draw an equivalence between transformers and spatial GNNs as defined in Balcilar et al.] (2020b). Taking inspiration from previous works Balcilar et al. (2020b ab we define the convolution support as the matrix C* that performs the desired transformation (such as convolution operation or filtering in the spectral space). Consider U as the matrix whose columns are the cigenvoctors of the graph laplacian and F the diagonal impulse response of the filter. Let G be the convolution matrix that performs the desired filtering. Then we have for input X (which could be transformed using projection matrix W
17

---

Published in Transactions on Machine Learning Research (07/202) 2022)
Input Graphs
Attention
Space of Spectral Filters
E
Figure 4: Figure indicating the set of the transformer attention maps (points D and E) and the sub-space of filter response of spectral GNNs (plane). The sub-space/sen are a slice of 2 x matrices belonging to the respective spaces with the (1, position fixed at 0. Point G the projection of the point D in the space of transformer attention onto the spectral space, where the segment DG represents the residuc(minimum error between point and the subspace). Point E is the identity matrix (one of the points with 0 error). However, in general, the error could be any arbitrary non-negative value. Point H represents the desired filter response to be learnt for the task.
X - WX),
G G*X
=
-UFU
=Cx
where C* UFUT in this case of spectral filters.
Lemma A.1. The attention mechanism of the transformer defined as below,
QKT
Attention"(Q. K,V) = softrar( Vamu V
is a special case of the spalial ConvGNN defined as
H' -
with the convolution kernel set to the transformer attention where W(..)) the trainable matriz for the l-th layer's s-th convolution kernel and is the desired number of convolution kernels.
Proof. Consider the vanilla transformer (Vaswani al. 2017 that learns the pairwise similarity between the graph nodes using its attention mechanism as follows:
AttentionW wights (Q, = sof softmax( QKT
(11)
doont
18

---

Published in Transactions on Machine Learning Research (07/2022)
Here, Q" = WXX" and K" = x query, key and Value respectively for the head h. The output at the head h can be obtained from:
x" where W Wk. W E Rdoux are the projection matrices for the
QKT W
Attention"(Q... (Q,K, V) so softmar
Vontt QKT
so soflmar
(XW?")
doutt
= =c
Thus from the above equation each head can be viewed convolution kernel acting the input graph with the support defined as below
C = softmax QK
(12)
Vout
This is the spatial ConyGNN defined in Balcilar et al. (2020b) as
H = a Σ C* H''ill))))
with the number of convolution supports per head 1 and as the concatenation followed by the projection layer of the multi headed attention module.
The lemma A.1 brings the transformer attention into the space of spatial ConvGNN, Balcilar al. (2020b) also shows that the spectral GNNs special case of spatial ConvGNN. We can now study the relation between the transformer (attention) and spectral GNNs and see if there exists equivalence between them.
We now attempt to characterize an equivalence between the transformer attention and spectral GNNs. To do so we begin by defining a measure of error between matrices in the two spaces. Consider C2 to be the space of all transformer attention maps possible. This is the set of n X n matrices with n being the number of nodes in the graph, such that the rows form a probability distribution i.e. each value greater than or equal to 0 and the rows sum to and is the row wise softmax of the gram matrix. Thus C. subset of the space of all stochastic matrices of size Consider F(A) F to be the diagonal matrix containing the desired frequency response of the spectral GNN. A (itag(1,, (2,,,2,......... .2....,,, Xn) the desired filter response and we let A2, Am] ] R i.c. we consider the entire vector space. We take U E Rax= to be the eigenvectors of the laplacian of the graph. Thus the convolutional support of the desired spectral GNN is Cg = UFUT. We define the error(E) between an arbitrary attention map C2 and filter F, for given graph, as the frobenius norm of the difference between C₁ and C, as below
) is the diagonal matrix containing
E(C,, Cy)) = I|C2 - Cyll = -UFU-
(13)
Next. we define and prove a few lemmas that give some auxillary results some of which would be helpful in the following proofs. The next result is for the case when the attention kernel is positive semi definite with Q = K as defined in Mialon et al. (2021).
Lemma A.2. The function E as defined in 13 over F with C, fixed is a conver function.
Note: This Lemma is standalone case to illustrate a property in a particular case proposed by GraphiT Mialon et al. (021) that contributes a kernel-based position encoding for transformers. Considering this case, unveil the convex properties of the objective for future work. In this particular case, GraphiT authors assume Q == K for transformers. Neither the theoretical results presented in main paper nor in next section are affected by this assumption of the Lemma. Our rationale is also to cover exceptional cases such as GraphiT besides the general proof proposed by where we have not assumed Q = K.
Proof. For simplicity of the proof let's consider the square of the error function i.c. f= E.. If we show that f is convex we can say that is convex since square root is convex and monotonically increasing in the domain of the function( (R+)).
19

---

Published in Transactions on Machine Learning Research (07/2022)
We proceed by finding the gradient of f (Vf) wrt the frequency responses X. By definition the frobenius norm squared is the sum of squares of the entries in the matrix.
Vx.f 22
C.u; Cuu; xx)
where us is the ith column of U and X, is the ith diagonal entry of F. The Hessian would then be obtained from the above expression as
2( Cru,), i-
ViA
(14)
0.
otherwise
(15)
We now show that C is positive semi-definite. We begin by noting that in the case of Q= K, C. sof coftmar(( (TTQ). QTQ is gram matrix which is positive definite (z 0). Also we have by the Schur Product Theorem Schur 1911 that if A, B 2 0, then Ao B ž O, where is the Hadamard product.
Now we can verify that softmar M) = Dog(M) where ( = MM) which is the element wise exponential of the matrix and D = [e1, 62 eal [ 1.......11 1], where e; = E, ((M())))) 2 O. By the Taylor's expansion of
the exponential function we can write f(M) = Ek=o c where M & is element wise and C₁ = मे 2 0. Thus
we have g(M) ž 0 [cite polya szego] M 2 0. Now we show that is positive semi-definite. We consider the mathematical program below
P min T Dx
EER
We can check the hessian of TT Dx is
ii=
2 3,
(x Dz)
0,
otherwise
which positive semidefinite and the optimal solution is 0 i.e. the minimum is obtained when 31 = 22 =.... vn = 0. Thus the value of is :. x² Dr 2 and thus z Finally using the Schur Product Theorem we have softmar(Q"
D fMM ビ O.
Thus, from 14 have V Via, 2 and f is convex which implics E is convex.
-UFl Fr we wish to find an which minimizes E. Now, consider the optimization problem p Intuitively it may seem that F = (aag(UTT,U)) The next result proves this.
FFUT
Lemma A.3. The function E as defined in 13 over F with Ct fixed has an optimal solution at F = - C.U) and the optimal value of the function is VtracelCTCC. D2), where D diag(diag C.U)).
Proof. Consider the optimization problem
Pelt" p= min |C,- UF)
min Felt"
- - diaggF))ls
The second equality follows from the fact that the frobenius norm docsn't change by multiplying with orthogonal matrices. Since the domain of the objective f ||C, Uddaa(()) [| is open, we could obtain the optimal F by setting the gradient to 0. (Also for the special that K in Mialon et al. (001))
20

---

Published in Transactions on Machine Learning Research (07 (072))
the objective is convex from lemma A.2 with respect to F and again can obtain the optimal solution by setting the gradient to 0.)
The gradient of the function with respect to F(A) is given as below
Vx.. - C.u: X:)
Thus we get a system of n equations and solving gives
F diag Saiagg~U'' (UT C,U)
(16)
where (.) is the vector formed by picking the diagonal elements of the input matrix. We can check at this point the objective is minimized as V = 21 2 0.
Now the optimal value of the objective attained at this optimal solution in 16 Substituting gives
P |c, ('dia(("))U"
, diog(F
1UTOU diag(diag -U C.U))l
1U -IGUU-DIE -DIE
IUTCUUIE= trace D2)
IracelCTCC, C+) trace D2)
tracelCC C T22
The above result gives some insight into the error between the convolution support of the transformer (attention map) and that of the desired filter, when the convolution support C, is fixed. The form of the minima tells us that there exists an error(2 0) between the two spaces when trying to bring matrix (U diag diag(F)UU))
the spectral space closer to C.. But when is the error exactly equal for a given F and what are the class of response functions where the error is 0 ie. the transformer would be able exactly learn the desired filter response?
For the set of filter responses that the transformer is not capable of learning with O error, what are the bounds with which the transformer would approximate the filter response of the spectral GNN for any given graph. The next theorems help us understand the answer to these questions.
Theorem A.1. The error function E(Cr, Cg) between the convolution supports of the transformer atlention and that in the space of spectral GNNs has minimum value of 0. Considering the case of non-negative weighted graphs, this minima can be attained at only those frequency responses for which the magnitudes at all frequencies (C,C)) < 1 and the low(0) frequency response >o(C')) =
Proof. From the definition of F(C1,, Cg) = ||C, - Cylle = =||C, - UFUT F we can see E 2 0. If we take C==C C, we can readily see that E(C,, C₂)) = which is the minimum value. Thus a minima of the Tunction both the spaces.
We now have to show that if E(Cr, C.) ||C, Cyll = ||C-UFUT|| = 0 then we must have An 1 and x < 1 for the desired frequency response. Consider the optimization problem below
P min Cr.F
C. - UFUT|
min min| UFU Ci
F
min CC Udiag (UT [U)))"
C,
min Ci
| CTU (U
21

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Let Cf be point where the abobe optimization problem is The third equality is obtained using lemma 16 optimized. In this case we have
min
U C.U diag(diag ( =0
"(U*
C
min
C,U =0
67
C =
where D the diagonal matrix diag(dion - (U CUU)). Now we know by the definition of the transformer attention map C₁
c11=1
:1'11==
1 PUDDV")1=
1 1
Σ
111 us
Σ
A7( Vn
W4 3 = n
T
Σ
x vn
uz)²
Thus we have the equation,
1 T
Σ
( 1
u,)² =1
(17)
Vn
Also we have,
Σ A
1
uz)² < Xmax Σ
vn u;)
1 T
Vn
=Xiax
< X
The last equality follows as the sum of squares of the projections of a unit vector on an orthonormal basis is 1. Since u,8 are the eigenvectors of the graph laplacian which by definition form orthogonal basis and Vn is by definition orthonormal, we have E, V u,)² - 1. By the Gerschgorin circle theorem (Gerschgorin), we know that Amar (C;) < 1. Thus, from this and above inequality 1 1 Amaz (Cf), we have that for the optimal solution Xmaz (Ct) = 1 and so for any frequency component. i, A,(C)) 1.
1 T
Next we consider the case of non-negative weighted graphs, as with negative weights the laplacian may have negative eigenvalues may not be diagonalizable all and in which case may have to resort to singular values for the frequencies which we leave for future works. We note the variational form of the laplacian L is x
Lx = E(i Wzy(2; -x,)2, where can be considered the vector of signals on the graph, E is the set of edges, Wij are the corresponding edge weights. Since we consider Wij 2 we can be sure that L is diagonalizable and so the eigenvectors (basis frequency vectors) are well defined for the graph. Let ug. u1, U2... un represent these basis vectors corresponding to the sigonvaluesfroqueniiic co, C1 62 en-1 in increasing order of magnitudes. We know that for connected graph eo = 0, for graph with disjoint components 6o eι and Let C be the number of components in the graph. The eigenvector
22

---

Published in Transactions on Machine Learning Research (07/2022)
corresponding to the ith component(0 eigenvalue, i < C) S is given by,
S
if jth node belongs to the ith component
uz
0,
otherwise
Due to the orthogonality of the cigenvoctors we have ue, Uj >= Ovi F
Thus for 2 C, < C' we have,
Σ 1
u4 uy >
[ uy [k]
S
0
v
|
k
where 4 is the indicator variable such that
1,
if kth node belongs the ith component
[[]]-
0, otherwise
Thus we have for the ith component,
Σ
LKkkuy]k]] = 0
(18)
Summing equation 18 over all components,
<<hu ΣΣ
E 4 [(]]uu[[
" To(a)) [M]
0 = Σ [A]
where e(k) represents the component that the kth node belongs to. The second equality as the components are mutually exclusive and exhaustive in the vertex domain. Thus we have for j > C,
[uykk =0 0
(19)
Also for < C' the square of the inner product with vector 1 vn gives,
1
1
(<
>)²
[SS]
vn
S
23

---

Published in Transactions on Machine Learning Research (07 (07/2022 /022)
Also since E n,
Σ
1 vn
>)²
|5:|
Ui
nh
i<C
K<C
1
11
i<C
n1
n
EK-
>)
(20)
iCC
Now from the square of the inner product with vector
1 for j 2 C is,
(< U
1
,,
Σ
vn U 12]12)2
1
vn
1
ng [R:))
Using this result and from equation 17
we have,
T
Σ
A
Us}
2
Vn
Σ M vn
u,)²
KC
We have shown that the response for the ith frequency component X (Cf) S 1 and the maximum value of
Enso
Xi( va T "z,² is attained when X are maximized. Thus from 20 we can show that if X₂(C;) < 1, then
Eieo Mi vy u, <1. We must have for optimal solution of P that Ae(C)) = 1, Vi < C. This completes
Tu,)
the proof.
Theorem A. has an important implication that the set of filter functions the transformer can learn effectively i.e., with error, subset of the filter responses having a in the low-frequency component (maximum magnitude of any component & 1). This is essentially the class of filters consisting of frequency responses such as low pass, band reject etc., that have maximum magnitude of in the pass- aass-ban((ann 1 in the O-frequency component). For other filters such as high pass, band pass, etc., the transformer attention map can at best, only be an approximation to the desired frequency response with a non-zero error. Note that due to the condition that the magnitude of the response at any given frequency component A S 1, there may still be some error even in cases where the desired frequency response contains the frequency component. Please note that our results are line with the empirical observation made by Park & Kim 2022) for vision transformers. However, our proof and theoretical foundations are for the more general domain of non-euclidean data.
In the remaining section, we intend to provide the lower and upper bounds on the error of objective. The theorem A.2 explains the error bound.
24

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Theorem A.2. The minimam of the error given by E Cÿ) over Ct, between the convolution supports of the set of stochastic matrices (which is supersel of the transformer atlention map) ond spectral GNN, for given filter response F, is bounded below and above by the inequalities
Aminl S E Cg) S [Amaa
where Amin, Amaz are the minimum and marimum of the absolute of the eigenvalues (F)F respectively and C = org min F. Cg)- For the set of transformer atdention maps Ct this bound is relazed as, C₁
Dmminl S SECC S |
where D are the eigenvalues of of UF - I)U
Proof. Consider the optimization problem below
P = min
| - UFU?
(21)
s.t. c,111
0>0 0
Now,
min ||c, - UFUT C
min -
Taking the gradient of the objective we get
Vc.(IG--FUU'l
= Vc,trace(CC C. - 20, (UFU") +UF²U) 2C, - 2UFUT
and for the hessian we squish the n x n gradient matrix above into an n² vector to get
( Vo, (22C,-2UFU))
21,2xn²
Thus the hossian of the objective is positive semi-definite and the function is convex. Also check the condition C,1 is affine and the domain as defined in 21 is convex.
Thus we can apply the Karush-Kuhn-Tln Tucker (KKT) Gass & Fu 2013 Gordon & Tibshirani 2012 Wu (2007) conditions to get the optimal solution.
We introduce the slack variable E R² such that 87 (T,C 1) 0. From the KKT conditions for optimality
we have,
C,1
C 0
25

---

Published in Transactions on Machine Learning Research (07 (07/2022)
which are the feasibility conditions. For the complementary slackness conditions introduce R and E R as the slack variables.
$20
120
(C 1) =0
A
C.
-: 4 C.
From the above we have t 0. Also we have the gradient conditions as below,
-FlIG-UUU7i (c -0 20, 2UF + =0 C = UFUT 1"
where @ is the kronecker product.
Also from the conditions,
C11
$ (UFUT 811=1 2
UFU a 2
2 (UFUTI-)
n
Substituting we get the optimal solution C as,
C UPU" _ 1
1
26

---

Published in Transactions on Machine Learning Research (07/202) 2002)
and the optimal value of the error as,
min ||0 UFU
||; - -UFU 1/
- ( 8 17
F
1 $ n
n
n²
n²
- ())"
12
1 traeeU(F-1))'1180)
n
1 trace (1= UFU(FFI)UU")
n
1 -race(17
f ) 1)
1 - -trace(
A7. (1" ))
1=1
n
T 3z)3)
Thus we have the below lower bound,
min ||c,- - UFU 2 C.
u
T
X2
u
min
x2
Imin"
{As sum of squares of projection of unit vector on an orthonormal basis is 1}
and the upper bound as,
min C - UFU C.
1=1
1 T
< X²
u,)
Vn
X2
maa
Thus we have the bounds for the mathematical program in 21 as
X2 S 1|0
UFU 112 < 22
27

---

Published in Transactions on Machine Learning Research (07 (0722)
Since square is monotonically increasing function in the non-negative domain and E 2 0,
min ||c, UFUTI 1 F (min |C,, - UFU 1r)
(I|C; -UFU"11P)) (E(C), c2))
Thus we have,
2nn I E(C Cg)² S Xmaa
Amin S E(C; Cg) Ammal
This concludes the proof for the minimum of the function over the set of stochastic matrices.
In the above optimization problem we have (aken the domain as the set of all stochastic matrices. But the set of transformer attention maps is a subset of the set of stochastic matrices and is not convex. However the lower bound still holds as the objective is convex and in the subset of the domain the values must be greater than or equal the optimal value. For the upper bound we simply compute the value of the function C. 1, which is point in the set of convolution supports obtained from the transformer attention. Then the minimum value of the error must be greater than equal to this value.
E(C,, Co) = |C: - CgllF
1 - 1-UFU
|00- -UFU
| - -UFU
| F)
| - 1
II(F - 1)
Σ X2
where A; are the eigenvalues of F - I. Thus we have for Cr, Of belonging to the set of transformer attention maps,
Dmmal EECCi Cy) S
Σ X2
The above result gives us a lower and upper bounds to the error. From the term (F - 1) in the proof we can see that the error increases as the filter deviates from the identity all pass matrix. This indicates that the error is unbounded F co. We leave the task of obtaining better bounds for the set of transformer attention maps future works.
Next we characterize the properties of the filters in the proposed architecture and provide the precision upto which the filter responses could be learnt.
Property A.1. The filter coefficients consisting of the vector of all ones is all-pass filter
28

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Proof. Consider the filter response given by the chebyshev coefficients Tn of the first kind as below
G(z) = - Tx)))t"
where t' represent the coefficients for the tt polynomial. It can be verified that the generating function for G above could be given by the below equation
1 la
G(x)
(22)
2t. + t2
setting in this equation gives G(x) which does not depend æ. Thus G would behave all-pass filter.
Note that is also an alternative but this would cause a degenerate learning of the filter coefficients which may always remain O after aggregation and the MLP layers (in the absence of bias).
Theorem A.3. Assume the desired filter response G(x) has m continuous derivatives on the domain [_1.]] Let 5k, G(z) denote the K3hh order approzimation by the polgnomial(chcbyshee denole the learned filler, Cj be the first absolule moment of the distribution of the fourier magniludes of f (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
filter and Sk, G(x))
K2C? hK? (og(NN) + K7"))
-
- G(=) 0 00 +
N,
Proof. Note for notational simplicity in this proof we represent the mumber of samples N, as N and the filter order K by n.
We begin by defining a bounded linear functional on the space (m++[(-1,1] 1] with m ++ continuous derivalives as below
LG ()) G(x)
Since G(x:) has m derivatives, it is approximated by polynomial function of degree n >> m. By Peano's write LG below
kernel theorem Peaan 1913).
(x) = / (m (t, t)dt
(23)
where
1 (x 1)
S (x 1) (x 1)
(24)
m!!
The notation (. - t) indicates
(x ()= t)mh if>
(x - 1)
0
otherwise
We note the th order approximation of the chebyshev expansion of the function Gr is given by
5h (x))
K=
where,
G(z)Tx(z))
dx C₁
v1 - x
29

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Thus get S f)
S (2 - t)
Ckm (x)
where,
2 { (x - Tx(a) do
Ckm
v1 xx
a Graph Neural Network approximates Ckm. in the proposed method, then we would have an error due this approximation. We now find the bounds of this approximation. As the current method relies the connectivity pattern due to the signals of the nodes of the graph, desire a different graph for different signal patterns and thus different filter cocfficients. Assuming an injective function (Xu et al.) 2019b) for aggregation, we can always find a unique map for a unique graph corresponding to the frequency response. Now we need to learn a function that maps the output of the previous network to the coefficients of the desired frequency responsc. classical neural network with h hidden units could approximate this by the below bound (Barron 1991
C2 hd Ckm = =0(- + llg(NN)
6 Ckm
where d = the imput dimension is the filter order, N is the number of training samples. Intuitively the first term of the expression states that increasing the number of nodes h decreases the error bounds and the second term acts as regularizer to limit the increase in h by the number of samples. The latter term can be thought of as enforcing the bound to obey the Occam's 's razor that paramoters should not be increased beyond necessity.
C₁ -JallFide
F is the Fourier magnitude distribution of which is the function to be learned by the network. Thus we get,
C2 0
hn
log( N))
(25)
h N
We represent by Sh (x-1) the approximation obtained by the network of the th order chebyshev polynomial. Thus
ST (x t)
km Tx(x))
k=
30

---

Published in Transactions on Machine Learning Research (07 (07/2022)
From equation 25 and the previous equation we get the below
ST n
(x 1)+ - (x - 1)
ckm (x) (x t)
Σ
(ckm +c]T((2) - (x - +)
Clem (x) - -(x - - +
(x(2))
k=
k=
Clem Th (x) - (I - -) +
(T)(
Σ
Cka (x)
k=U
k=n+1
(1) -
Chm Torr)
k=
(x(+)++
Σ
Okm Tx(2)
k=0
km++1
C h
+ hm
10
(o)(N)))TA(O)++
Σ
Ckm (e())
N
K=
k=n+1
nC?
hn?
0
+
log logggg())))) N)) +
Σ
Ckm (x())
h
N
k=n+1
We now bound the expression
Σ 00
E1 Ckm [z(z)). We note that
2 (' (x ())))(())
Ckm
V1 dx
Using x cos and cos & we get
2 1 (cos 1 - cos T cos k0d8
Ckm
We now have to solve the integral = J0 (cos 0 - cos 6m cos k0d0 We do this by integrating by parts
I = [[cos 0 cos 3) sin k0
Jo
k
sin k0
m(cos cos 3)
1 mn
sin 8)
k d0
sin kt
m(cos 0 - cos -os c) m) (- sin 0)
d0
m(cos 0 cos (ross)mm- m- cos (k 1)0 + cos (A: + 1)0
d0
k
1 mm(cos 0 cos m cos (A: 1)0
h: d0
mncoss 0 cos m- cos (k 1)0 d0)
k
(111 112)
31

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Contimuing in this manner we get O(2T)) integrals, one of which is as below
m(m- 1m 2) ....
Im
(- sin 0) sin (A- m)0)
k(k - 1)(k - 2) ... (I m)) 0(m"k
O )a h: + 00
Thus I evaluates to O(k and Ckm O(k ))
Thus we have,
D0
Ckm Tx(xx)
Σ
1km
k=++1
k=n+1
= (n (m)
Using this result in the expression for 1S (x - -) - (x - f
we get
1
(x
l)
(x 1 1)
nC
hn²
00
logg(N)))))))
Ckm Tu (z)
h
N
k=
nC²
hn?
0
log IN)(N)) + On m)
h
N
Finally using equations 24 and
23 for
ST' G we get
n0
hn² log(N) --)
S G o
+
(26)
N
which concludes the proof.
The bound states that as the filter order K, and the hidden dimension of the network h are increased (subject to K3C9 I hK3 < i, the approximation will converge to the desired filter response. The condition N, h h K can be thought to satisfy the statistical rule that the model parameters must be less than the sample size. In the limit of N, + co, h and Ky could be increased to as large values as desired subject to h 2 O(K) f), which is the order of paramoters to be approximated. This is equivalent to say that if we do not consider the generalization error, we can theoretically take a large h. Then, we are left with only the term containing the filter order i.e. the approximation error comes down to OKF"") as expected. One point to note is that we assume suitable coefficients Cke 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 the graph nodes in the atlention heat. map and discard the spatial connectivity. It is a straightforward exercise to 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 evident from the results on the real world and synthetic A.7 datasets.
A.2.1 Transformers and WL test for Spatial Domain
WI-test has been used as a standard measure to study the expressivity of GNNs. The k-WL test is 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 oquivalence of transformer and WL test naturally arises. In the following section, we try to argue how a transformer can approximate the WT. test.
32

---

Published in Transactions on Machine Learning Research (07/2022)
Given sequence, recent works by (Yun et al. 2019 2020 have theoretically illustrated that Transformers are universal sequence-to-sequuens approximators. The core building block of the transformer 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.
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 (Beaini et al. 2021) shows how using eigenvalues distinguish non-isomorppic graphs which WL test cannot.
Transformers are universal approximators coupled with eigenvalues and eigenvectors as position encodings are powerful than the WL lest given enough model parameters. However, they can only approxinale the solution to the graph isomorphism problem with a specific error and not solve them fully which also proven by Kreuzer ct al. (2021). The same holds for us in spatial domain as we inherit the identical charactcristics from SAN.
A.3 Positional encoding schemes
In FeTA, we learn the pairwise similarity between graph nodes inheriting the attention mechanism of vanilla transformer as follows:
Attention" Attention((Q,K,V) (Q,K,V) softmar( QKT W Vand
(27)
Here Q²= = KT = and VT = W where W W W E R.dout are the projection matrices for the qucry, key and values respectively for the head h. Following GraphiT (Mialon et al., 2021).
share the weight matrices for the query and key matrices for learning a positive semi-delinite kernel i.e.
Q K. For the imput features use the node attributes, if provided, along with the static laplacian position encoding, in (Dwivedi & Bresson 2020). The static encoding in the form of the laplacian eigenvectors is simply added to the node embeddings. For the relative positional encoding we follow Mialon et al. (2021
and use the diffusion (Kp) and random walk (K,.) kernels (cf., Equations and 30p. The attention using the relative positional encoding schemes now:
QQT
Attention(Qu. V) = softmar(exp
K2)
(28)
doout
Here, Kp is the respective kernel being used i.c. K₂ KD, Krw. The diffusion kernel Kp for graph with laplacian L. is given by the equation below,
KD -BL lim (I -_1 L) iinl
(29)
For physical interpretation, diffusion kernels be interpreted the amount of substance that accumulates at 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. It. is described by the equation below,
Kno -1-
(30)
We can see that above equation becomes the diffusion kernel if y = 8 and p - cc. However, the difference with respect to the diffusion kernel that the random walk kernel is sparsc. We also borrow from the positional encoding scheme of SAN (Kreuzer et al.) (202)) that allow usage of the edge features E E N Formally, the attention weights w/f between the nodes and j in the 1sh layer and t attention head is given
33

---

Published in Transactions on Machine Learning Research (07/2022)
DATASET
GPU
Memory
TIME
MUTAG
Geforce P8
8
1.5
NCI1
Geforce P8
8
37.8
Molhiv
Tesla V100
16
79.0
PATTERN
Tesla V100
16
104.2
CLUSTER
Tesla V100
16
115.4
ZINC
Tesla V100
16
529.9
Table Computational details used for the datasets on the FeTA-Base setting. Time is in seconds per epoch.
by the below equations
With x O " Wiikd E(i
dout
if and j are connected in sparse graph
X O o 2
X W B
dont
otherwise
1+7 softmax
du if and j are connected in sparse graph
kll Wij
7 s0f softmar
1+7
otherwise
where w.l.k.l Wilki, w.I.k. are the projection matrices corresponding to the query, key and edge vectors for Q the real edges and w.kkk, w2 w.2.k. are the projection matrices corresponding to the respective vectors for the added edges in the 4thh head and 1th layer as in (Kreuzer et al. 2021 We further employ GCKN (Chen et al. 2020a) to encode graph's topological properties.
A.4 Dataset Details
We benchmark the widely used datasets for graph classification, node classification, and graph regression. Namely for graph classification we use MUTAG (Morris et al. 2020). NCT1 (Morris et al. 2020) and, the ogbg-MolHIV {Hu et al. 2020) dataset, for node classification we use the PATTERN and CLUSTER datasets
Dwivedi et al. 2020) and for graph regression we run our method on the ZINC (Diieedi et al. 2020 dataset.
MUTAG collection of nitroaromatic compounds. Here, the goal is to predict the mutagenicity these compounds. Input graphs represent the compounds with atoms as the vertices and bonds the edges. Similarly, in NCII, the graphs represent chemical compounds with nodes representing the atoms and the edges indicating their bonds. The atoms are labeled one-hot vectors node features. Ogbg-MolHIV is molecular datasct in which each graph consists of molccule, and the nodes have their fcatures encoded as the alomic number, chirality, and other additional features. PATTERN and CLUSTER are node dlassification datasets constructed using stochastic block models. In PATTERN, the task is to identify subgraphs and CLUSTER aims at identifying clusters in semi-supervised sctting. ZINC available compounds. The task is to predict the solubility of the compound formulated as graph regression problem. Each molecule has the type of heavy atom node features and the type of bond as edge features.
database of commercially
34

---

Published in Transactions on Machine Learning Research (07 (022)
Model
Dataset
PE
PE layers
PE dim
layers
hidden dim
Model Params
Heads
Filter Order
MUTAG
3
64
118074
8
NCI
3
64
122194
8
FeTA-
Molhiv
129465
8
Base
PATTERN
5465930
CLUSTER
3
5467726
8
ZINC
3
64
351537
8
MUTAG
119080
NCH
3
107074
8
Vanilla-
Molhiv
3
64
127356
8
Transformer
PATTERN
64
5445389
8
CLUUTTER
5447657
ZINC
3
340737
8
Table 8: Model architecture parameters of FeTA-BBas and Vamilla-Transfrmi Transformer
Model
Dataset
PE
PE layers
PE dim
no. layers
hidden dim
Model Params
Heads
Filter Order
MUTAG
LapE
64
64
2216-102
4
NCI1
LapE
64
64
2218322
4
FeTA LapE
Molhiv
LapE
64
61
129657
4
PATTERN
LapE
64
64
4414026
4
CLUSTER
LapE
G4
64
54684494
4
ZINC
LapE
64
483401
4
MUTAG
LapE
2195-167
NCIL
LapE
2207266
GraphiT LapE
Molhiv
LapE
127489
PATTERN
LapE
4395278
CLUSTER
LapE
5447384
ZINC
LapE
474456
MUTAG
RW
106694
NCII
RW
110698
FeTA
Molhiv
RW
129465
3RW
PATTERN
RW
4413258
CLUSTER
RW
5467726
ZINC
RW
482825
MUTAG
NCI
106498
CraphiT + 3RW
Molhiv
125745
PATTERN
4394786
CLUSTER
5445478
ZINC
338817
MUTAG
GCKN+ RW
110783
NCII
GCKN+RW
2228-434
FeTA GCKN +
Molhiv
GCKN+RW
5619529
PATTERN
GC
37988386
3RW
CLUSTER
GC RW
ZINC
GCKN+RR
499273
MUTAG
GCKN+
114882
GraphiT
NCIL
CCKN + RW
32
64
2205672
4
8
GCKN
Molhiv
GCKN RW
32
64
5598726
4
PATTERN
GCKN RW
32
64
37880986
4
3RW
CLUSTER
CCKN+RW
32
64
37895163
4
ZINC
GCWN+RW
32
64
478645
4
Table Model architecture parameters FeTA with position embedding from GraphiT and original GraphiT model
35

---

Published in Transactions on Machine Learning Research (07 (07/202) 2022)
Model
Dataset
layers
dim
no. layers
hidden dim
Model Params
Heads
Filter Order
MUTAG
LPE
16
6
64
558322
4
8
NCI1
LPE
16
6
64
559762
8
8
+
Mulhiv
LPE
16
6
96
608129
LPE + Sparsc
PATTERN
LPE
16
579013
10
CLUSTER
LPE
16
16
56
412978
ZINC
LPE
3
16
6
96
364167
8
8
MUTAG
LPE
16
6
64
542082
NCII
LPE
64
343522
SAN
Molhiv
LPE
6
96
602672
LPE
PATTERN
LPE
3
16
6
96
570736
10
8
Sparse
CLUSTER
LPE
16
16
56
403783
8
ZINC
LPE
16
96
360617
MUTAG
LPE
16
6
64
640242
NCI
641682
FeTA +
Molhiv
LPE
2
16
6
96
732984
4
LPE Full
PATTERN
LPE
3
16
6
96
697003
10
8
CLUSTER
LPE
16
16
56
867046
ZINC
LPE.
96
458303
MUTAG
LPE
6
64
624002
8
NCTI
LPE
16
6
64
625442
8
8
SAN +
Molhiv
LPE
2
16
6
96
714769
LPE
PATTERN
LPE
688534
10
Full
CLUSTER
LPE
16
16
96
858538
ZINC
LPE
16
6
96
454753
8
8
Table 10: Parameters of FeTA with position embodding from SAN compared with original SAN
Method
MUTAG
NCI1
ZINC
PATTERN
CLUSTER
ogbg-molhin molhiv
Avg [V]
30.32
29.87
23.15
118.89
117.20
25.51
Avg [3]
32.13
32.30
24.90
3039.28
2,150.86
27. .7.47
Node feature
L
L
A
L
L
A
Dim(feat)
38
37
28
3
9
# Classes
NA
2
# #Gapphs
4,127
4,110
250,000
14,000
12,000
41,127
Table 11: Dataset statistics (L indicates node categorical features and A denotes node attributes).
36

---

Published in Transactions on Machine Learning Research (07/ (07/2022)
A.5
Experiment Settings
Table 7 lists the hardware and the run time of the experiments on each dataset. Tables g 9 10 lists out the model architecture parameters for each configurations. For the configurations PeTA-Base FeTA + LapE, FeTA+ +3RW and F we used the default syper-parameten provided by GraphiT MMillnn 2 as inherited position encodings from GraphiT. For instance, in ZINC, we don't use edge
et al. fcatures. In the configurations FeTA + and + we used the configurations from SAN (Kreuzer el al., 2021). This is to ensure same experiment settings which these encoding schemes have used while inducing position encodings in the vanilla transformer models. Means and uncertainties are derived from four runs with different sceds, same as SAN. Additionally, with the final optimized parameters, we reran 10 experiments with identical seeds, which is same as SAN's MAN's/Mialon 3/Mialon et al al/Dwivedi et al's experiment settings. Vanilla transformer implementation and its values main paper is taken from Mialon et al. (2021).
A.6 Additional Experiments
In order to further assess the impact of position encodings the performance of FeTA we conduct additional experiments by inducing the recently proposed learnable structural positional encoding (LSPE) Dwivedi et al. (2022) in FeTA The results are in table 12 We can see that adding the new position encoding in FeTA improves the values over the original basolinc on all the datascts. This further strengthens the argument that the ability of FeTA to selectively learn the graph spectrum complements the position encoding schernes and the various position encodings could be used as a plug-in along with FeTA to improve the performance on a task.
We also study the effect of inducing the inpul graph along with the transformer atlention map to learn the filter coefficients in FeTAA Here the input graph is taken as is with the node embeddings replaced by the all one vector. A Graph neural network followed by a pooling layer is then used to Iearn the filter coefficients as in the original configuration. This is then concatenated with the coefficients obtained from the transformer attention map and given to feed forward networks followed by a non linearity to obtaín the final filter coefficients. The results are given in table [3 We see a consistent drop in performance with respect to FeTA-Base indicating that the proposed method to learn the filter coefficients from the graph and attention map is inefficient and better method is needed. However, configuration (FeTA with i/p graph) outperforms the vanilla transformer reaffirming the benefits of inducing the transformer with the ability to selectively attend to the graph spectrum. It should be possible to learn better graph specific filters using the structure of the input graph and the spatial attention of the transformer, which we leave to future works.
observe that on 4 out of 6 tasks this new
Models
MUTAG % ACC
NCI1 % ACC
ZINC MAE
ogb-MOLHIV % ROC-AUC
Vanilla, Transformer LSPE FeTA= + LSPE
83.33 + 4.5
82.16 1'2 0.6
0.106 + 0.002
76.35 1 0.2
88.89 + 4.5
83.29 + 0.5
0.0998 + 0.004
77.17 + 0.9
Tasks using Vanilla Transformer and FeTA induced with learnable structural position encoding (LSPE). Higher (in red) value is better (except for ZINC). We see performance increase across all datasets when LSPE is induced with FeTA
Table 12: Results on graph/node dassifiiationn/egreee
Models
MUTAG
NCI1
ZINC
ogb-MOLHIV
PATTERN
CLUSTER
Vanilla Transformer
82.2 + 6.3
70.0 + 4.5
0.696 + 0.007
65.22 + 5.52
75.77 + 0.4875 78.66 + 2.509
21.001 1.013
FeTA-Bace
87.2
+ 2.8
78.7 = 1.4
0.412 4 0.004
65.77 - 8.888
80.851 - 2.689
PeTA (with 1/p graph)
77.78 + 4.5
70.0 + 2.3
0.470 + 0.002
03.01 + 5.3
76.85 1.1
28.25 + 4.02
Table 13: Results on graph/node /node classification/ ceefffaatioo/regeesssion /regreesionn Tasks using Vanilla Transformer, FeTA-Base and FeTA (with i/p graph) in which the input graph also used to learn the spectral filter coefficients. Higher (in red) value is better (except for ZICC). We see a performance drop compared to FeTA-Base when we use the input graph to learn the filter.
37

---

Published in Transactions on Machine Learning Research (07 (222)
A.7 Synthetic Dataset
To show the benefit of graph-specilic filtering compared to static filtering, we run experiments synthetic datasets that have different spectral components for different graphs. We begin by noting 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 a graph:
(ig(1) ifi=j
L(i,)) = -1
if (1,))
otherwise
where deg(i) is the degree of the node and E is the set of edges in the graph. Multiplying by a vector e gives the below expression
w = Lu
w(1) Σ
(n(1) - x())
iEEE
The expression 8 Lo gives
8 Lu Σ (11) Σ
(v(1) v(i))
TEE
Σ Σ ((i((v(i)
v(i)
WER
Σ v(i((u(t) v()) + +00)((()))
Σ -())-
jiLEEEEE
Thus we can see that the expression xd Lo evaluates to the sum of squared distances between neighboring nodes in the graph. We also note that due to this property, the laplacian is positive semi-definite matrix. If u were the cigenvector of the graph, know that v" Lu would be the cigenvalue corresponding to that vector by the spectral decomposition theory. Thus all the eigenvalues of the laplacian are non-negative.
We now try to develop an intuition of the laplacian's lowest and largest sigenvalues/vectorn above equations that oT Lu is the sum of squared differences between values on the nodes. Thus the smallest eigenvalue would correspond subject to ||=||= 1. The second eigenvalue would correspond to the orthonormal vector the first vector and minimizes the sum of squared differences of nodes within cluster. Thus the second cigenvector would try to keep values of its components similar/close /closer for nodes that belong to 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 modesccomponents. belonging to the same take different values subject to ||]|== 1 while also being orthonormal to the other vectors.
We see from the
the eigenvector that assigns the same value to all the neighboring nodes,
With the above background, we generate synthetic datasets with node signals exhibiting different spectral components for different graphs. Consider L 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 Pt and the inter-cluster edge density as Po. The signals are assigned to the graphs according to the cigenvectors of the selected components of the spectrum. To keep it simple, we use only a single eigenvector (V:) to generate signals per graph. Specifically, out of the NG = B) eigenvalues, we select one and take the components of the corresponding eigenvectors. The nodes are then clustered using standard clustering algorithms, such as K-means, into C classes that we keep equal the number of blocks. Each node assigned a one-hot vector the position of the class belongs to. We then drop this attribute of 50% of the nodes ie., these nodes are assigned 0 vector, and the task is
38

---

Published in Transactions on Machine Learning Research (07/202) 2022)
(a)
(b)
(c)
Figure 5: Graphs and Filter Frequency response for the graphs on the Synthetic, dataset for the case with K = and = Figure (a) 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 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 note the filter has learned the two components of the graph spectrum: the low frequency and the high frequency components.
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 finding the suitable spectral component in the graph signal and using this information for classification. This should benefit from graph-specifie decomposition and filtering approach, which we confirm from the empirical results. We generate 3 datasets namely Synthetici, Syntheticz, and Synthetica using different values of N, B, Pi, Po, V,. Synthetic, has 10, = 2, Pt = 0.9, Po = 0.05, {V; i {1, with 1000, 100, 100 graphs in the train, test and valid graphs respectively. Syntheticz has N 10, 6, p: 0.9, P. = 0.05, {V; E (1, N. with 1000, 100, 100 graphs in the train, test and valid graphs respectively. Synthetic, has N 10, B pi 0.9, p. 0.05, {V, i E {1, [ Nc)), with 1000, 100, 100 graphs in the train, test and valid graphs respectively.
We train the synthetic datasets on the FeTA-Static and FeTA-Base models to study the effect of graph-specific dynamic filters on the graph. For the Symthetic, dataset, we use the hidden dimension as 16, and for Synthelicz and Synthelicy we keep it to 64. The number of layers is fixed to 1. The number of heads h and filter order K for PeTA-Static are kept at 1 and respectively and for varied for other settings as can be seen in table A.7 We can see from table A.7 that the performance on the synthetic datasots, using dynamic filters of PeTA-Base, has increased by a large margin as compared to the case of static datasel-specifie filters in FeTA-Static using the same model parameters. This justifies the benefit and necessity of graph-specific filter design in cases where the spectral information differs from graph to graph. We also observe that as the filter order is increased for a given number of 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 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 studics to determine the effect of mumber of heads multiple spectral components in the signal.
A.8 Filter Frequency Response on 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.
39

---

Published in Transactions on Machine Learning Research (07 (2222)
Model
Synthetic
Syatheticz
Synthetics
#Param(din=16)
(Prram(dim=64)
FeTA-Static
K 4
h =
70.04 = 4.41
35.34 + 0.25
33.05 + 0.48
4122
62958
89.67 0.50
45.63 + 0.30
39.67 = 0.55
3582
54738
FeTA-Bass
K 4
92.15 = 0.20
46.32 + 0.42
40.22 + 0.61
4122
62958
92.26 0.40
47.14 + 0.63
40.27 = 0.30
5250
79446
K
79.26 7.47
46.26
0.20
39.83 + 0.33
3090
47010
FeTA-Base
K 4
h = 4
91.54 = 0.56
46.59 + 0.34
39.42 + 0.30
3150
47550
K 8
92.35 0.37
46.24 + 0.56
40.74 = 0.35
3318
48678
K 2
74.99 = 0.43
45.88 + 0.50
38,60 + 1.05
3064
46618
FeTA-Base
=
91.32 0.43
45.77 0.73
38.86 0.17
3100
46774
K ==8 8
91.60 = 0.30
45.75 + 0.73
39.71 + 0.50
3220
47134
Table 14: Study on the performance of FeTA-Base vs FeTA-Static on the synthetic datasets. We study the effect of the order K of filters and the mumber of heads h for FcTA-Basc.
The frequency response of the filters learned on ZINC with filter order four is given in figure 0 Each curve is the frequency response of a filter learned for a single head. We see various filters being learned, such as few low pass, high pass, and band stop filters. Figure 7 shows the frequency response for filters of order Here we observe the high pass and multi-modal band pass responses being Icarnod.
Filter Frequency response on ZINC:
Filter Frequency response MolHIV: Figure 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 9 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-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 high bias towards signals in the low-frequency region and some components in the middle and high frequency regime to extent. This could be interpreted the model trying to learn the two 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 10 show low-frequency filters being learned aloug with bandpass filters. This intuitive as the task of CLUSTER would indeed benefit by learning low- uww-freuency signals for grouping nodes belonging the same cluster. All these observations across all datasets validates our hypothesis studied in the scope of this paper.
A.9 Interpretability in Spectral Space
In this section, we look at the interpretability aspect induced by FeTA in the spectral space. The figures 11 and 12 show the graphs with the eigenvectors on the nodes corresponding to the top eigenvalues selected by the filter. From both figures, we see that in the case of the low pass filter (leftmost graph in sub-figure (a), (d) of figure 11 and subfigure (a)-(d) of figure 12), the nodes in the neighborhood forming a cluster have similar cigenvalues. Whercas 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 FeTA attends to select input features. In this case, we can think of the model learning to pay more atlention to the nodes with higher eigenvalues and lesser allention to the nodes with smaller eigenvalues in a graph and task-specific manner. The second interpretation is related to the interaction between the nodes, i.c., for given node which other nodes are considered for aggregation. For example, graph attention networks, the neighboring nodes are aggregated, and the values of nodes in the same cluster tend to be closer to each other (homophily). This is particular case of the low pass filter in which see
40

---

Published in Transactions on Machine Learning Research (07/202) /222))
(a)
(b)
(c)
(d)
25
19 Ho. 19 10 19 10
I5 30
16
(e)
g
(h) K
Figure 6: Filter Frequency response on individual graphs on the ZINC dataset for filter order of 4. Figures (a) (d) are the graphs from the dataset and Figures (e) (g) the corresponding frequency responses. X axis shows the normalized frequency with magnitudes on the Y axis.
(a)
(c)
(e)
(g)
(h)
K
Figure 7: Filter Frequency response on individual graphs on the ZINC dataset for filter order of 8. Figures (a) (d) 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.
41

---

Published in Transactions on Machine Learning Research (07/202) 2022)
(b)
(c)
(d)
10 100
(c)
(g)
(h) K
Figure 8: Filter Frequency response on individual graphs on the MolHIV dataset. Figures (a) (d) are the graphs from the dataset and Figures (e) (h) are the corresponding frequency responses. axis shows the normalized frequency with magnitudes on the Y axis.
(a)
(b)
(c)
(d)
K
(h)
Figure 9: Filter Frequency response on individual graphs on 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.
42

---

Published in Transactions on Machine Learning Research (07/202) 2022)
(a)
(b)
(c)
(d)
P
(c) K
(f) K -4
(g)
(h) K
Figure 10: Filter Frequency response on individual graphs on the CLUSTER dataset. Figures (a) ~ (d) are the graphs from the dataset and Figures (c) ~ (g) are the corresponding froquency responses. X axis shows the normalized frequency with magnitudes on the Y axis.
(a)
(b)
(d)
Figure 11: Attention heat map in spectral space of the sample graphs in ZINC datasct determined from the frequency response in Figure 7 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.
43

---

Published in Transactions on Machine Learning Research (07/202) 2022)
(8)
(b)
(d)
Figure 12: 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 the spectrum.
from the figures and 12 that the nodes belonging to the same cluster take on similar values. For example, consider the Figure showing short-range dependencies (interactions). In the rightmost graph, nodes in the same clusters take on different eigenvalues, ralust the need for long-range interactions. However, depending on the task and graph, the model also learns to aggregate (interact with) distant nodes, as seen in the graph corresponding the high pass filter (the rightmost graphs in each sub-figure of [1 and 12h. Thus FeTA can be interpreted generic(covering the entire spectrum of frequencies) allention network in the specival space.
The leftmost graph has nodes in a particular cluster taking similar eigenvalues
44


Reviews:
[{"review_id": "sTIMQNKpdb", "reviewer": "Reviewer_Ne6P", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I find the analysis presented by the authors to be timely and important, given not only the prevalence of Transformers, but also their growing usage on graph datasets. In my opinion, the key strength of the paper is its theoretical analysis, and it appears to be executed well, with actionable insight for future work. I also appreciated the extent of the quantitative and qualitative analysis of the proposed model.\n\nHowever, regarding the model proposal itself, I am unsure whether it is the most suitable response to the theoretical issues identified in the paper. The equations of the model seem to rely on the success of many variables. I will enumerate a few below:\n\n* We require the Transformer attention to be meaningful enough to provide a computational graph for the spatial GNN.\n* The GNN itself is a simple spatial GCN-like model (Equation 8), and it is unclear whether the authors attempted to improve its expressive power.\n* Lastly, it appears (Equation 10 onwards) that the only way the original graph's structure is used is to support a Chebyshev network-style rule with learnable filtering coefficients. But these coefficients only control the importance of various hop-level representations, while the actual Laplacian used is left unchanged from the original graph. I am unconvinced that this will be the most effective approach for heterophilous datasets.\n\nThe final two points are somewhat compounded by this passage in the authors' theoretical analysis: _\"One point to note is that we assume suitable coefficients can be learned from the input.\"_ I believe this point is somewhat handwaved in he paper, and potentially deserves a more thorough formal treatment, given that the success or failure of the final layers may rest on the quality of the coefficients.\n\nAll of these issues, compounded with the fact the proposal requires a quadratic space complexity, and the fact that simpler proposals have surfaced in recent times, make me think that somewhat more discussion and experimentation is needed in the paper's current form. I will detail proposed modifications in the \"Requested Changes\" section.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors offer a spectral-domain study of what Transformer attention coefficients can capture on a graph. From a theoretical standpoint, they demonstrate that attention coefficients could in principle have unbounded error in fitting the graph Fourier transform.\n\nAs a remedy to this approach, the authors propose FeTA: an approach that maps the Transformer's attention coefficients from the spatial into the spectral domain (using a spatial GNN encoder over the non-zero attention coefficients). The computed spectral coefficients are then used as a standard graph convolutional filter (akin to the Chebyshev network), and a regularisation term is applied to ensure that these coefficients learn distinct behaviours.\n\nTheoretically, the authors demonstrate that their model has a more favourable approximation error, and empirically, they are able to outperform relevant baselines (e.g. GAT) in a direct head-to-head setting. The paper also features very interesting qualitative results on the actual learnt frequency responses, highlighting that these results cannot be achieved from existing positional embedding approaches alone.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "To preface my suggestions for improvement, I should highlight that I am not disputing the presented quantitative and qualitative results; the proposed method genuinely feels empirically strong, and the qualitative results of learning the frequency responses appear convincing.\n\nWith that in mind, I would appreciate in the very least a response from the authors on the following:\n\n* I would appreciate a more careful (theoretical or qualitative) treatment of the claim that _\"we assume suitable coefficients can be learned from the input\"_. Anything that can give a more proper insight into how achievable this assumption is in general, or even over noisy graphs, would be invaluable to stimulate future research in the area.\n* A clarification on whether stronger spatial models than GCN were attempted in Equation 8 would be insightful.\n* I would recommend adding results on some of the established heterophilous datasets; for example the ones in \"Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs\" (Wu et al., NeurIPS'21). Many of these datasets are small, so the training on at least a few of them should not take a lot of time, and they would strengthen the paper's choice of Chebyshev filtering in the face of non-homophilous data.\n* My major concern with the utility of the proposed method is the fact that several other approaches have been proposed recently, both for strengthening attentional mechanisms in GNNs, and having more interesting (static) filtering. I would single out EGC (Tailor et al., ICLR'22) and GATv2 (Brody et al., ICLR'22) in this regard. Both of these methods are _subquadratic_ but perform remarkably well, and the authors should compare and contrast with them (ideally empirically). Especially, GATv2 is a quite important reference for this work (currently not cited): they identify limitations in both the original linear attention mechanism from GAT, _and_ the Transformer attention, and propose replacing the attention mechanism with a universal approximator (2-layer MLP). Would GATv2 have a favourable theoretical treatment in the authors' framework? How would its results compare to FeTA? Could FeTA improve its performance? All of these questions would be very important to answer in my opinion, to properly ground the contribution in prior work.\n\nLastly, a few minor concerns that are less significant, but a discussion on them could be useful:\n\n* The proposed method (FeTA) combines spatial and Transformer models in an interesting way: the Transformer is applied first. It would be useful to the reader, to also reference and compare with methods that choose to instead apply a spatial method first, and then follow-up with a fully-connected model: e.g. GraphTrans (Wu, Jain et al., NeurIPS'21), and the +FA method in the oversquashing paper of Alon and Yahav (already cited).\n* Quoting the paper: _“Another benefit for adapting spatial attention of the transformer in our architecture is that it addresses the performance issues of GNNs such as over-smoothing (Zhao & Akoglu, 2020), suspended animation (Zhang & Meng, 2019), and over-squashing (Alon & Yahav, 2021)”_. Would it be possible to add some citation / deeper discussion of this benefit? I feel like it is an important point.\n* In Figure 2, it is somewhat implied that the graph structure would be used by the Transformer, but in reality it appears to operate over the fully connected graph. Amending the figure somewhat could avoid this confusion.\n* Minor nit: The equations in the current form of the paper are not very pleasing to parse, because the authors do not expand the size of the parentheses. Adding a simple `\\left` and `\\right` to the parentheses could go a long way to improving this!\n\nIt is not necessarily a requirement that all of my suggestions are addressed in the paper, but given the abundance of interesting related proposals, it is in my opinion important to frame the paper's contributions properly with respect to them (regardless of which way the needle goes). \n\nOnce again, the paper's theoretical contribution could be strong enough to warrant acceptance even in absence of the strongest proposal immediately coming out of the theory.", "broader_impact_concerns": "No concerns. The paper is primarily an algorithmic contribution to graph representation learning.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ELKHSIXkpd", "reviewer": "Reviewer_vNWf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- The theoretical analysis of vanilla Transformer in the spectral domain\n- The extensive experiments\n\nCons:\n- In theoretical analysis, I notice the proof is based on Q == K. I think this assumption is too strong.\n- The C_t in equation 5 only considers Q \\dot K. The pair-wise relative positional embedding (like the shortest path used in graphormer) is ignored in the theoretical analysis. I believe considering it will come up with totally different theoretical results. \n- There are too many variations of FeTA (5+), and I am not sure which one of them is better. \n- FeTA is like a hot-fix. Although vanilla Transformer may not be powerful in the spectral domain, I expect the authors to propose a better attention method that performs better in spectral, rather than mixing GNN into Transformer. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to analyze the expressive power of the vanilla Transformer in the spectral domain. The theoretical result shows the vanilla Transformer is only effective in learning the low-pass filters. Based on the analysis results, the authors propose a variation of the Transformer framework, called FeTA, which adds an additional spectral GNN branch to the model. The authors conduct several experiments to demonstrate the ability of FeTA. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. the font-size in figure 1and figure 4 is too small\n2. Consider relative positional encoding in theoretical analysis. \n", "broader_impact_concerns": "no", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "n7uzQFnYUF", "reviewer": "Reviewer_h47B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n1. The paper studies an interesting research question about transformers and what benefits they bring compared to typical GNNs in graph machine learning problems. \nGiven the immense interest that transformers have generated in the AI community for different data modalities, this is an important question to explore. The authors show that, in the vanilla configuration, transformers have important limitations in modelling a large set of graph filters.\n\n2. The mathematical analysis is sufficiently thorough and does not leave questions unanswered. I have not checked the proofs in detail, but the results appear to be reasonable and intuitive to understand. \n\n# Weaknesses\n\n## On positional encodings and experimental results\n\nThe experimental results are presented in a misleading way. Comparing Tables 1 and 3 we see that FeTA does not outperform the standard GNNs unless equipped with positional encodings.\n\nThe relevant comparison is: \n\n| Dataset | FeTA-Base | Best method w/o PEs |\n|---------|-----------|---------------------|\n|Mutag|**87.2**|82.9|\n|NCI1|73.7|**82.0**|\n|Zinc|0.41|**0.14**|\n|MOLHIV|67.6|**79.0**|\n|Pattern|78.7|**85.4**|\n|Cluster|30.4|**73.8**|\n\nAdditionally, we see that among the methods that use positional encodings, the differences between FeTA and previous methods are not that impressive: on MUTAG, NCII, and PATTERN the results are too close and too uncertain to be statistically significant and on MOLHIV the best FeTA variant is comparable to BankGCN and outperformed by Graphformer, meaning that FeTA provides a clear improvement only on Zinc and Cluster (2/6 datasets). \n\nIn Section 5.3 the authors state:\n\n> One point to note is that we assume suitable coefficients can be learned from the input. 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. Nevertheless, the current implementation does well, as is evident from the results on the real world (section 6) and synthetic (A.6) datasets.\n\nThis statement is in contradiction with the results, and highlights a crucial limitation of the method: it needs positional encodings to be competitive with vanilla GNNs. \nFirst, this brings the \"practical\" complexity of FeTA to $O(n^3)$. Second, a fair comparison should consider vanilla GNNs augmented with the same positional encodings. As it is, the vanilla GNNs used in the comparisons could have a limited view of the graphs if their number of layers is less than the graph diameter, while also having fewer parameters than FeTA and a computational complexity of $O(|\\mathcal{E}|)$.\n\nIt is a very strong assumption that node features alone would be enough to provide all the structural information necessary to predict the filter coefficients, and these results confirm that the assumption is unlikely to hold. \n\n## On the use of transformers\n\nOne of the main results of the paper is that FeTA can implement any desired frequency response as the order of the filter grows (Thm. 5.1).\n\nThis result, however, hinges on the Chebnet architecture and not on the transformer. This makes the contributions of the paper less interesting because it doesn't show a way of improving the attention maps computed by transformer, but only that the attention maps can be used as surrogate for the structure operator in a typical Chebnet model. \nWe could remove the transformer from the equation and the results would still be trivially true: an order-1 Chebnet implements a low-pass filter, and higher powers of the structure operator are needed to implement more complex frequency responses.\n\nThe use of dynamical coefficients is nice, but also something that could have been included in any other model and does not say much about the ability of transformers for graph data. \n\n## Minor issues\n\n- In Section 5.3, the message passing is expressed as a function of the non-zero elements of the attention matrix. However, being the output of a softmax, the attention matrix will only have non-zero elements. This means that there is no real difference between Eq. 8 and Eq. 7.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the expressivity of graph transformers and proposes a new architecture designed to overcome their limitations in learning particular classes of spectral graph filters. \n\nThe paper begins with an analysis of the classes of filters that the transformer can learn, showing that they can only perfectly learn low-pass filters. \nThen, they propose the FeTA architecture to overcome this limitation. The FeTA model uses a transformer combined with a message-passing GNN to dynamically output the filter coefficients of a Chebyshev GNN.\nThe Chebyshev GNN uses the attentional map of the transformer as a structure operator to convolve the input signal. \n\nThe new architecture is shown to be capable of approximating an arbitrary frequency response in the limit of the number of filters and training samples. \n\nExperiments show that \n- the FeTA architecture can improve the performance of the vanilla graph transformer\n- when augmented with suitable graph positional encodings, the FeTA architecture outperforms many kinds of GNNs and graph transformers\n- the FeTA model can be used in conjunction with typical low-pass GNNs to improve their performance, using the true adjacency matrix to mask the attention map (similar to GAT)", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "None of the following suggestions is critical to my final judgment of the paper, but I think they would significantly improve the work.\n\n## Notation\nThe mathematical notation needs to be fixed. There is a lot of ambiguity, missing definitions, and notation reuse throughout the paper. A few issues (in no particular order): \n\n- $n$ is used for the number of nodes and the order of the filter\n- $N$ is used for the number of nodes and the number of samples\n- $U$ is used for the eigenvector matrix and the update function\n- $A$ is used for the adjacency matrix and the aggregation function\n- $G$ indicates both a matrix and a 3D tensor\n- $K$ is used for the order of the FIR filter and the keys matrix\n- In Section 3, $f_l$ is not defined\n- In Lemma 4.1, $C^s$ is not defined\n- In Equation 8, $V$ is not defined\n- In Theorem 4.1, it is unclear if $\\lambda_i(C_g)$ indicates the filtered frequencies and, in that case, if it could be more clearly indicated as $F(\\lambda_i)$ to match the notation above.\n- $C^t$ is not a \"space\", but an arbitrary matrix (as indicated later in the text)\n- In Section 5.3, why not write the definition of $Q$ and $K$ as $Q = XW_Q^h$ without the transpose?\n- The use of a sigma-like-notation for concatenation ($\\lVert_h X^h$) in the second unnumbered equation on Page 8 is a non-standard notation that should be introduced. \n\n## Typos\n- \"incapable graph representation learning\" -> \"incapable of graph representation learning\"\n- \"where researchers have studied its spectral properties\" -> \"where researchers have studied their spectral properties\"\n- \"low-pass filter GNN for empowering\" -> \"a low-pass filter GNN for empowering\"\n- \"U is the N × N matrix\" -> \"U is an N × N matrix\"\n- \"eigen vectors\" -> \"eigenvectors\"\n- \"eigen values\" -> \"eigenvalues\"\n- In Lemma 4.1, the repetition of \"is\" is ungrammatical: \"the attention of the transformer is X, is a special case of Y\" -> \"the attention of the transformer is X, which is a special case of Y\" or \"the attention of the transformer, X, is a special case of Y.\"\n- \"updation\" -> \"update\"\n- \"in graphs with same nodes the eigenvalues may differ\" -> \"in graphs with the same number of nodes but different eigenvalues\"\n- \"containing low-pass response\" -> \"containing low-pass responses\"\n\n## Miscellaneous issues\n- The meaning of the acronym FeTA is never given.\n- In Section 2, \"features of the graph spectra\" is an unclear expression to indicate the eigenvectors/positional encodings.\n- In Section 2, \"actual graph spectra\" is denoted as $U^\\top X$ although this is the Fourier transform, not the spectrum (which would be the eigenvalues).\n- In Section 3, the term \"multigraph\" is used in an ambiguous way since it usually indicates a graph with multiple edges between nodes.\n- In Section 4, the output of a softmax (especially of typical gram matrices with finite elements) is strictly greater than 0, not \"greater than or equal\".\n- The expression \"beneficial components [of the spectra]\" is unclear and could be rephrased.\n- Personal comment (feel free to ignore): the node set is in calligraphic font $\\mathcal{V}$ but the edge set is a lowercase Greek letter $\\epsilon$: why not $\\mathcal{E}$?", "broader_impact_concerns": "This work presents basic research with no immediate ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes the FeTA architecture that enhances the set of classes of filters that the transformer can learn. After the discussion, in which the authors participated diligently, and the author provided a proposed revision of their submission, all reviewers recommended acceptance.
Decision: Accept (poster)