GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers
Authors: GuoguoAi
Guansong Pang
Hezhe Qiao
YuanGao
Hui Yan
Venue: ICML 2025 poster (2025)
Keywords: Graph Transformers
Kolmogorov-Arnold Networks
Fourier Series
Spectral Graph Neural Networks
Primary area: deep_learning->graph_neural_networks
TL;DR: GrokFormer is a novel Graph Transformer that learns expressive, adaptive spectral filters through order-K Fourier series modeling, overcoming the limitations of self-attention and improving graph representation learning performance.

Abstract: Graph Transformers (GTs) have demonstrated remarkable performance in graph representation learning over popular graph neural networks (GNNs). However, self-attention, the core module of GTs, preserves only low-frequency signals in graph features, leading to ineffectiveness in capturing other important signals like high-frequency ones. Some recent GT models help alleviate this issue, but their flexibility and expressiveness are still limited since the filters they learn are fixed on predefined graph spectrum or spectral order. To tackle this challenge, we propose a Graph Fourier Kolmogorov-Arnold Transformer (GrokFormer), a novel GT model that learns highly expressive spectral filters with adaptive graph spectrum and spectral order through a Fourier series modeling over learnable activation functions. We demonstrate theoretically and empirically that the proposed GrokFormer filter offers better expressiveness than other spectral methods. Comprehensive experiments on 10 real-world node classification datasets across various domains, scales, and graph properties, as well as 5 graph classification datasets, show that GrokFormer outperforms state-of-the-art GTs and GNNs. Our code is available at https://github.com/GGA23/GrokFormer.

GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers
Guoguo Ai! Guansong Pang?
Hezhe Qiao
Yuan Gao
Hui Yan
Abstract
ness, popular GNNs are often limited by issues like over- smoothing (Oono & Suzuki, 2020) and over-squashing (Top- ping et al., 2022). On the other hand, graph Transformers (GTs) use a Transformer-bast 2017) to learn graph representations. Due to its strong ca- pability in capturing long-range dependencies among graph nodes, it offers a potential solution to address the issues in popular GNNs.
Graph Transformers (GTs) have demonstrated re- markable performance in graph representation learning over popular graph neural networks (GNNs). However, self-attention, the core mod- ule of GTs, preserves only low-frequency sig- nals in graph features, leading to ineffecttvvnness in capturing other important signals like high- frequency ones. Some recent GT models help alleviate this issue, but their flexibility and expres- siveness are still limited since the filters they learn are fixed on predefined graph spectrum or spec- tral order. To tackle this challenge, we propose a Graph Fourier Kolmogorov-Amol Transformer (GrokFormer), a novel GT model that learns highly expressive spectral filters with adaptive graph spectrum and spectral order through a Fourier series modeling over learnable activa- tion functions. We demonstrate theoretically and empirically that the proposed GrokFormer fil- ter offers better expressiveness than other spec- tral methods. Comprehensive experiments on 11 real-world node classification datasets across various domains, scales, and graph properties, as well as 5 graph classification datasets, show that FrokFrrmer outperforms state-of-the-art GTss and GNNs. Our code is available at https: figtthub...
architecture (Vaswani et al.,
One key ingredient to successful GT's is effectively inte- grate topological structure information into the Transformer network. This may be achieved by various position encod- ing methods such as Laplacian vectors and random walks (Zhang et al., 2020; Dwivedi & Bresson, 2020; Kreuzer et al., 2021; Kim al., 2022; Wu et al., 2021). Other infor- mation such as graph distances and path embeddings can also be incorporated into GTs through their attention mech- anism to improve the performance (Maziarka et al., 2020; Ying et al., 2021; Chen et al., 2022; Choromanski et al., 2022; Wu et al., 2024). However, despite the remarkable success in graph representation learning, their performance can be severely limited by the inherent low-pass nature of the self-attention module, since it only preserves low- frequency signals that highlight similarity between nodes (Bastos et al., 2022: Wang et al., 2022: Shi al., 2022). This prevents GT's from capturing other important frequency sig- nals, egg., high-frequency signals that highlight difference between nodes, which can be crucial for learning complex relationships nodes in diverse graphs.
To address this issue, inspired by polynomial GNNs (e.g.. ChebyNet (Defferrard al., 2016), GPRGNN(Chien et al., 2021), BernNet(He et al., JacobJJan (Wang & Zhang, 2022)) and A2GCN (Ai et al., 2024), some recent methods are dedicated to capturing various frequency sig- nals by order-K polynomial approximation. For example, FeTA (Bastos et al., 2022) and PolyFormer (Ma et al., 2024) learn the coefficients for order-K polynomial bases (e.g.. Chebyshev, Monomial, Bernstein basis) through the self- attention mechanism. However, these polynomial filters are typically approximated via K predefined bases with specific frequency responses as illustrated in Figure 1(a), and thus, they have receptive field of size K in information passing, leading to a locality modeling and limited flexibility and expressivity. Consequently, they are often unable to fit com- plicated graph filters well, as shown by the failure of the
1. Introduction
Graph neural networks (GNNs), which jointly encode graph structures and node features, have been emerging as an ef- fective generic tool for graph-structured learning problems (Yi al. 2023; Qiao et al., 2024). Despite their effective-
'The work was partly done when Guoguo Ai visited Singapore Management University. 'School of Computer Science and Engi- neering. Nanjing University of Science and Technology. Nanjing, China "School of Computing and Information Systems, Singapore Management University, Singapore. Correspondence to: Hui Yan <yanhui @ wjwst.edu..n>>. edu.en
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

GrokFormer: Graph Fourier Kolmogorov-Armold Transformers
of Polynommah::
Table I: Our proposed filter vs. existing spectral filters.
ofDAtel (ruiFormerr
of Spectommnt
GrounTruth
BemNet
S Syeeforme
CroiForrerr
1b((A)
1.0
Models
Order-udaptive Specirum-adaptive
ChebyNet, GPRGNN,
GNNs
BernNet, JacobiConv
0.6
FeTA, PolyFormer
0.4
GTs
Spectormer
X
GrokFormer (Ours)
0.0
10
0.0
0.5
1.0
1:5
2.0
k
able activation functions modeled as Fourier series over K -order graph Laplacian spectrum, producing K adaptive filter bases. As shown in Figure ((a), these bases can capture any frequency response across the spectrum of both low and high orders (i.e., from 1st to Kthh orders). Furthermore, we devise learnable order coefficients to assign varying impor- tance to the K filter bases, enabling an adaptive adjustment in fitting the graph spectral order. The resulting filter in GrokFormer is adaptive/leamable in both graph spectrum and spectral order, having better adaptivity than existing pop- ular filters, as shown in Table In doing so, GrokFormer filter can more flexibly capture a broader range frequency responses, offering significantly better expressiveness than other filters (sce Figure 1(b)). The main contributions are as follows:
(a)
(b)
Figure 1: (a) The frequency response range of K filter bases {bi (A), (A).. b x (A) k E [1, K] for GrokFormer, Specformer, and polynomial filters at the spectrum w.r.t. spectral order k, where colors represent the varying fre- quency components of spectrum different orders. Polyno- mial filters typically have fixed bases, e.g., X, A?, A corresponding the K filter curves that capture the spe- cific curvilinear frequencies, whereas Specformer adaptively learns the filter bases at the first-order spectrum, enabling it to capture arbitrary frequency responses in the spectrum plane of 1. In contrast, our GrokFrrmer filter bases are capable of capturing arbitrary frequency responses across K different spectral planes. (b) Low-comb filter (ground truth) and the approximated filters generated by the filters of GorkFormer and Specformer, and the Bernstein polynomial filter in BernNet.
We propose novel GT model, GrokFormer, that can effectively capture a wide range of frequency signals in an order- and spectrum-adaptive manner. To the best of our knowledge, this is the first GT model that has a learnable filter in both graph spectrum and spectral order.
prevalent Bernstein polynomial in fitting a low-comb filter in Figure 1(b). To effectively encode such spectrum informa- tion and achieve a more global graph modeling, Specformer (Bo et al., 2023) performs self-attention over the N eigenval- ues after positional encoding to build learnable filter bases. As shown in Figure I(a), the frequency response of its filter bases can be arbitrary on the first-order graph Laplacian spectrum. Although it shows impressive effectiveness, its filter learning has a computational complexity of O(N2), making it difficult to simultaneously capture higher-order spectral information, and thus misses some important fre- quency components embedded in higher-order spectrum. Therefore, the learning capacity of the Specformer filter is limited to the specific first-order spectrum and thus it struggles to fit the complicated low-comb filter in Figure 1 (b). Accordingly, the key question we ask here is: can we have a GT that efficiently and flexibly extracts rich fre- quency signals across the multi-order spectrum of the gruph Laplacian?
We further introduce a graph filter lcarning approach, namely Graph Fourier KAN, that leverages learnable activation functions modeled Fourier series to learn a set of spectral filter bases. The learned filter enables GrokFormer to model diverse frequency signals from a broad graph spectrum of both low and high order.
We theoretically show that the GrokFormer filter of- fers better learning ability than state-of ofte--ofttheaar (SOTA) competing filters, and empirically demonstrate the su- periority of GrokFormer over SOTA GNNs and GT' on real-world node- and graph-level datasets.
2. Related Work
Graph Neural Networks. Existing GNNs are mainly di- vided into two main streams: spatial-based and spectral- based methods. Spatial-based GNNs, like GCN (Kipf & Welling, 2017), SGC (Wu et al., 2019) and GAT (Veličković et al., 2018), update node representations by aggregating information from neighbors. By stacking multiple layers, they may learn long-range dependencies but suffer from over-smoothing and uver-squashing. Some improved spa- tial methods, such as H2GCN (Zhu et al., 2020), HopGNN
To answer this question, propose novel GT model, called Graph Fourier Kolmogorov-Arool Transformers (GrokFormer), which provides an efficient approach for learning order- and spectrum-adaptive graph filter for GTs. In particular, motivated by Kolmogorov-Amon Networks (KANs) (Liu et al., 2024), GrokFormer leverages learn-
2

---

GrokFormer: Graph Fourier Kolmogorov-Armold Transformers
(Chen et al., 2023c) and SHGCN (Yan al., 2025) propose to combine first-hop and multi-hop neighborhood represen- tations. Other studies (Xu et al., 2019; Dong et al., 2021) point out from a spectral perspective that GCN only consid- ers the first-order Chebyshev polynomial, which acts as a low-pass filter. Subsequenlly, various spectral-based GNNs have been proposed, such as, GPRGNN (Chien et al., 2021), BerNNet (He et al., 2021) and JacobiConv (Wang Zhang, 2022) learn arbitrary graph spectral filters by order-K K poly- nomial approximation. HiGCN (Huang et al., 2024) uses Hloer-PPetas Laplacians in simplicial complexes to learn polynomial filters across varying topological scales. How- ever, the information passing in these polynomial models is local, and their filters with fixed bases have limited learning ability.
3.2. Graph Filter
L UAUT denotes the spectral decomposition of Lapla- cian matrix, where U (u, u2...... ................................ uN) is a complete set of orthonormal eigenvectors, also known graph Fourier modes, and A = diag {(r]]==] is diagonal matrix of the eigenvalues of L. The Fourier transform of a graph signal or E R is written as a U xc. The inverse transform is x = U (Shuman et al., 2013). Per convolution theorem, the convolution of the graph signal with a spectral filter G having its frequency response as h can be obtained by:
x G UU(A)U* x Udiaggh(A1)) ... A(A)) x,
(1)
where h(A) applies h element-wisely to the diagonal entries of A, i.e., [A{A)] = lxA)).. A powerful spectral filter can exploit useful frequency components in graphs.
Graph Transformers. Compared GNNs, the attention weights in Transformers can be viewed as weighted ad- jacency matrix of a fully connected graph, capturing long- range dependencies. Some GT's combine both and are pop- ular in graph representation learning, such as Graphormer (Ying et al., 2021), GraphGPS (RampáKek et al., 2022), GRIT (Ma et al., 2023), SAT (Chen al., 2022), Node- Former (Wu et al., 2022), NAGphormer (Chen al., 2023a), GCFormer (Chen et al., 2024b), and SGFormer (Wu al., 2024) are proposed by incorporating various graph struc- tural information into the Transformer architecture. How- ever, these GTs are limited by the inherent low-pass nature of the self-attention mechanism (Bastos et al., 2022). Ad- vanced GTss have increasingly focused on capturing various frequency signals tackle the issue. SignGT (Chen al., 2023b) designs a signed self-attention mechanism to capture low- and high-freyuency signals. FeTA (Bastos et al., 2022) and PolyFormer (Ma et al., 2024) extract various frequency information via polynomial approximation like polynomial GNNs. Specformer (Bo et al., 2023) develops learnable filter bases, offering greater spectral expressiveness compared to polynomials with fixed bases. However, such spectral filters still struggle achieve the desired frequency response due to their limited focus on the specific first-order spectrum.
3.3. Self-Attention
Multi-head self-attention is a key module of Transformers, having strong ability to capture interactions between any pair of input instances, e.g., graph nodes in GTs. Let X denote the input of self-attention, and for simplicity of il- lustration, we consider the single-head self-attention in the equation below. It first projects X into three subspaces query Q, key K, and value V through three projection matrices Wº, W WV. The self-attention is then calculated as:
QKT
Attetion (Q, K, V) = =oftmaa
VV,
(2)
Vd
where d is query dimension, Q = XWO, K = XW* and V = XWV.
3.4. Kolmogorov-Arnold Network
KAN is grounded in the Kolmogorov- Amolld representation theorem (Kolmogorov, 1957; Ismayilova & Ismailov, 2024),
which states that for a function f:
2n+1
f(11,...,I,,) =
(3)
3. Preliminaries
where 6g.p is trainable activation function, and By: [0.1] + R and 0n. : R + IR are univariate functions that map each imput variable xp. It create an arbitrary function at cach hidden neuron by overlaying multiple nonlinear functions onto the input features. For a single-layer KAN & with an input dimension of nin and the output dimension of nout!
3.1. Notations
An attributed graph is represented as G = (V,EX)) where V denotes the node set with i2 e V and |V] = N, E denotes of node attributes. Each e has F-dimensional feature representation z;- The topological structure of G is represented by an adjacency matrix A = [a:y] E NNN aij = ajf. if (v, vy) e E, and aij = ajs = 0 otherwise. D E N denotes a diagonal degree matrix with d = Σ; dzy- The normalized Laplacian matrix L is defined by = Iy A
the edge set, and X NxF is
out 2
Ois (4.").
(4)
where x; denotes the i-th dimension æ. and Φ represents a learnable nonlinear function, often parameterized as a linear combination of B-splines (Liu et al., 2024).
where I E R NxN denotes an identity matrix.
3

---

GrokFormer: Graph Fourier Kolmogorov-Amold Transformers
Prodktton Loyer
16
X
Add & Noen
10
Scl Attention
Graph Fouster KAN
Feitwckiing Layer
Rigenolie).
E
Node P X
Graph Tepology A
Figure 2: Overview of GrokFormer. In addition to the use of self-attention to capture global information in the spatial domain, novel Graph Fourier KAN proposed in GrokFormer the achieve global graph modeling in the spectral domain. This design enables strong adaptability in both spectral order and graph spectrum, offering superior expressive power in capturing diverse graph frequency signals. GrokFormer synthesizes the spatial and spectral representations by a standard summation and normalization layer, followed by Feed-Forward Network (FFN) layer for prediction.
4. Methodology
and both of which are hyperparameters; Okm and bem are trainable Fourier coefficients.
GrokFormer is novel GT framework empowered by Graph Fourier Kolmogorov-Armold Network (KAN)-based spectral graph convolutional filter, as shown in Figure 2. Graph Fourier KAN in GrokFormer devised in way that can adaptively learn diverse frequency signals from wide range of spectral order and graph spectrum, going beyond the self-attention mechanism in GTs.
Compared to existing popular graph filters, (A(A) has the following three advantages. (i) Effectiveness: The orthog- onality of polynomial bases is nice property in learning filters (Wang & Zhang, 2022; Bo et al., 2023). Sine and co- sine in the Fourier series are orthogonal, our graph Fourier KAN inherits this property, enabling effective learning of graph filters. Also, many sine and cosine terms with differ- ent frequency components can well support the modeling of rich frequency information our filter. (ii) Convergence guarantee: In approximation theory (Pinkus, 2000), the fact that the Fourier series attains the best convergence rate for function approximation supports the fast convergence for our method. (iii) Global graph modeling: The filter func- tion can effectively attend to all eigenvalues, allowing the learned graph Laplacian to construct a fully connected graph that captures global information (Bo al., 2023).
4.1. The Proposed GrokFormer Filter
The Formulation. To capture various frequencies in flexi- ble and efficient manner, design novel spectral graph convolution module, named Graph Fourier KAN. Motivated by KAN, which use Iearnable functions parameterized as splines instead of traditional weight parameters to achieve parameter-efffiienn learning, we devise learnable functions to learn iigenvaluesppecinn filter functions over the order- K spectrum of the graph Laplacian, thereby improving the expressiveness of the filters. However, the spline in KAN is piecewise and difficult to train (Xu et al., 2024), which does not meet our goal to develop an efficient filter learning method. To address this issue, we turn to finding multi- ple relatively simple nonlinear functions. To this end, we propose a novel approach that leverages Fourier series rep- resentation to parameterize each learnable function. The specific filter function can be accordingly defined follows:
Order and Spectrum Adaptability. The filter is aimed to adaptively consider variety of graph Laplacian spectrum from the 1st order up to the Kthh order (K-order graph spec- trum for short). To adaptively capture diverse frequency patterns across different orders, we rewrite Eq. (5) and de- fine of learnable bases at a specific order as follows:
(x) Σ (cos (md+) ) am + sin (md*) bm), (6)
K
M
(A)
Σ
Σ
(cos (mx*) atem + sin (ma+) bue))
1= m==
(5)
where K is the highest order the filter can model, M rep- resents the number of frequency components (or grid size),
where l: = [1,2...., K]. Subsequently, we introduce a learnable order coefficient og to adaptively synthesize the

---

GrokFormer: Graph Fourier Kolmogorov-Armold Transformers
filter bases from wide range of orders as follows:
the EMHA module and the proposed Graph Fourier KAN module through summation generate informative node representations. We formally characterize the GrokFormer layer as follows:
K
I(AA)
Σ (x)
(7)
X EMHA(LN(X + +X + X
Therefore, the corresponding spectral graph convolution in GrokFormer is defined as follows,
(10)
X 1 = (F ()) +
x F
(dia "
(8)
In the final layer of GrokFormer, we calculate the prediction scores of the nodes from class This score is given by:
where d-ag(-) creates a diagonal matrix, x = (X)), and fa is two-layer MLP (embedding layer).
= (ttfftaa(X()))
(11)
Theoretical Analysis. Below we show theoretically that our proposed filter can flexibly fit graph patterns of any spectral order K and graph spectrum.
where ( is the output of the final layer, and Y is the predicted class label.
Then, GrokFormer can be trained by minimizing the cross
Proposition 4.1. Our graph filter h(A) is learnable in both spectral order and graph spectrum:
entropy between the predicted and the ground-true truth labels:
= Σ Vic Y.E.
(12)
A(A)
OK
(cos (m2*) Okm. + sin (mx+) bkm)
iEVL
where C' is the number of classes, y is the real labels, and V, is the training set.
(9)
where the spectral order k is adaptively determined by co- efficient og while the spectrum X at the specific order ls is adaptively determined by coefficients dgm and bym-
4.3. Complexity and Scalability Analysis
Complexity. Firstly, like previous methods (Bo et al.. 2023; 2024), GrokFormer also needs spectral decompo- sition, which is done offline in the preprocessing step and has the complexity of O(N3). Secondly, GrokFormer's forward process involves an embedding layer with the complexity of O(Nd². efficient self-attention with com- plexity of O(Nd)), filter base learning with complexity of O(KN N MM). and graph convolution with complexity of (N"d)) Note that explicitly constructing the spectral filter matrix Udiag (h( (h(A))U in Eq. (8) incurs high computa- tional cost of O(N3). To address this, we leverage matrix associativity and compute U X first, which reduce the com- plexity to (NNd)). As result, the overall forward pass complexity GrokFormer is O(Nd(N + 2d) + MN).
Due to this adaptability, existing advanced filters are special cases of GrokFormer filter, showing its better universal- ity and flexibility in graph pattern modeling.
Proposition 4.2. Existing polynomial filters that can be = formulated as ((A) = Ek ax are a simplified variant of our graph filter.
Proposition 4.3. The filter in Specformer a simpli- fied variant of our graph filter.
We further show below in Proposition 4.4 that GrokFormer filter has strong expressiveness and can learn permutation- equivariant node representations.
Proposition 4.4. Our filter lxA) can approximate any con- tinuous function and constructs a permulation-eqiivaiant spectral graph convolution.
Scalability, In large graphs, GrokFormer can use Sparse Generalized Eigenvalue (SGE) algorithms, as outlined in earlier studies (Cai et al., 2021; Bo et al., 2023; 2024), to compute q eigenvalues and corresponding eigenvectors, in which case the decomposition complexity and the for- ward complexity will reduce to O(N2g) (g < N) and (2 + KqM + Ngd), respectively. Empirical results for computational cost can be found in Section 5.5.
All proofs are provided in Appendix
4.2. Network Architecture GrokFormer
GrokFormer built upon the original implementation a classic Transformer encoder. Specifically, we apply layer normalization (LN) on the representations before feeding them into other sub-layers, i.e., the multi- head self-attention (MHA) and the an efficient MHA (EMHA) that switches the order from (QKT) to Q(K of Eq. (2) (Shen et al., 2021), which helps reduce the complexity without affecting per- formance. We synthesize the representations from both
5. Experiments
blocks (FFN). Here, we use
In this section, we conduct comprehensive experiments on both synthetic and real-world datasets to verify the effec- tiveness of our GrokFormer. More experiments can be seen in Appendix B.
5

---

GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers
Table 2: Node classification results on five homophilic and five heterophilic datasets: mean accuracy (%) + std. results are in bold, while the recond-best ones are underlined. 'OOM' means out of memory
The best
Homophilic Datasets
Heterophilic Datasets
Cora
Citeseer
Pubmed
Photo
WikICS
Physics Spatial-basen
Penn94
Chameleon
Squirel
Actor
Texas
GNNs
GCN
87.14+tm
79.86=us>
86.74
88, 26,26
82,32+am
82,47 97.74zuus
59.61
46.78
33.23+116
77.38
GAT
88.03
10.5
87.04
90. 10w
83.221a74
97.82 juzs
81.53 jurs
13.s
44,491
33.93
80.82.21
H2GCN
87.961am
10.90
18
95.451mm
83.45
17.19
g1.31
61.20
39.53
36.3123.
91.891191
HopGNN
88 18.68
80.38
19.
24.49
84.73
97. 97.86
00M
65.25
57.83
39.33
15.15
Spectral-basce based GNNs
ChehyNet
86.6/1ax
19.11
87.95 joas
93.77
82.951am
97.25_.n7
81.09 2oos
19,28
40.551o.m
37.61
86.22_..4
GPRÖNN
88. 38.57
80. 12
88.46ge1
93
82.58
97.25gmm
67.28 81.38
m
50.15
39.922n07
22.95
BernNet
88. 52522
80.09
88 28.4
93.63-203
83.56=261
97.36=030
=2.47
68.29
51.35=a75
41.79=110
93.12=a0s
JacobiConv
88. 28.49
80.78=0x
89. 62.441
95.43++023
84.13+34
97.56 97.56-025
83.35=am
74.20+1m0
$7.38+1.2
41.17=054
93,44=2.11
HiGCN
81.12+00s 89.23+
89.95 sous
95.33++037
83,14
97.65=mas
OOM
68,47-+04
51.86+042
41.81
92.15
Graph Trans
Transformer
70.55 11
86.661ex 1050
89.58.1
77.361125
OOM
OOM
45.21
33.17
39.95..oa
88.75 16.70
GraphGPS
83.42+112
-5.87=u31
86.62+aas
+4,35+02s
79.26+037
97.60-was
OOM
46.07+151
34.14+aam
37.68-w94
83.71
NodeFormer
87.32
79.56
89. 89124:uus
95.27 10::
81.03
26.45
69,662us
56.34.tm
43,42
34.62
84.63:s4r
SGFormer
79.6211a1 87.87
89.07
94.34
82.71
76.65
61.44
45.82
41.69
92.461144
NAGphormer
88. 15
80. 12
89.70
95.49
83.41gam
97.85gmm
73.98
54.92
48.55ga.
40.08
91.80
Specformer
88 88.57=1m
81 2.49
90.61 2023
95.48
85.15
97.7 97.75=053
84.32
74.72
64.64
41.93=a144
88 38,223
PolyFomner
87.67+121
81.80=ars
90.68=031
94.08+13r
83.62+au7
98.08=021
79.27=026
60.17++1.9
44.98
41.51=0m
89.02=344
GrokFormer
19.57
91.39 81.92.1a 12s
Jun
15.52
1MAs
98.31 Lass
83.59 1uize
75.5% 11.3
65.12
42.98 1.44
94.59 2.00
5.1. Performance for Node Classification
Table 3: Graph classification results.
Dataset Description. We conduct node classification ex- periments on 11 widely used datasets in previous graph spectral models (Bo al.. 2023; He et al., 2021; Deng et al., 2024), including six homophilic datasets, i.e., Cora, Cite- seer, Pubmed, the Amazon co-purchase graph Photo (He et al., 2021), an extracted subset of Wikipedia's 's Computer Science articles-WikiCS (Dwivedi et al., 2023), and a co- authorship network Physics (Shchur et al., 2018; Chen et al., 2024a). We also evaluate on five heterophilic datasets, i.e., Wikipedia graphs Chameleon and Squirrel, the Actor co- occurrence graph (Pei et al., 2020), webpage graphs Texas from WebKB, and Penn94, large-scale friendship network from the Facebook 100 (Lim et al., 2021). A more detailed description can be found in Appendix A.1.
PROTEINS MUTAG PTC-MR IMDB-B IMDB-M
Kereel methods
GK
71,420
81.712
55.3114
65.91m
43,9
WI. kernel
75.0_m1
90.41s7 59.914s
73.8119
50.9
DGK
71.7=as
82,7+14
57.3+11
67,0+ea
44.6=as
GNN methods
DGCNN
75.52n
85.8214
S8.6235
70.0
47.8gm
GCN
75.2=as
85.1
63.1
73.8234
55.2203
GIN
76.2::x
89.4134
64.62m
75.1
52.3
GDN
81.3
97.4
75.6176
79.3113
55.2143
HiGCN
77.0-42
91.3+54
66.2+G9
76.2+5.
52.7=35
Graph Transformers
Transformer
66.3_x1
81.9197
57.3
71.1
45.8g1
Graphormer
68.52n3
82.523a
59.2246
73.52s8
48.9231
SGFormer
74.6=30
88.6+5a
65.2+44
74.7+4u
56.4::4
NAGphormer
22.5
89.9
66.5256
75.1
51.7=35
Specformer
70,9
96.3asa
82,9249
86,6437
58.5=39
PolyForner 70.1
91.01sa
78.61s*
76.7
16.
Baselines and Settings. We compare GrokFormer with sixteen competitive baselines, including four spatial-based GNNs, five spectral-based GNNs and seven GTs. Note that PolyFormer has multiple variants, and use the Poly- Former(Cheb) the baseline. Following the previous works (He et al., 2021; Huang et al., 2024; Bo et al., 2023), we randomly split the node set into train/validation/tet set with ratio 60%%20%%/20% and generate 10 random splits to evalu- ate all models on the same splits. We report the average clas- sification accuracy and standard deviation for each model. For polynomial GNNs, we set the order of polynomials K 10, consistent with their original setting. For the baseline models, we adopt the hyperparameters provided by the au- thors. In the large-scale datasets Physics and Penn94, we implement truncated spectral decomposition for both Grok- Former and Specformer to enhance scalability, selecting the 3,000 eigenvectors associated with the smallest (low-
GrokFormer 78.2.44 99.5
94.8
88,5
62.2:43
frequency) and largest (high-frequency) eigenvalues. More detailed settings can be found in Appendix A.2.
The results are reported in Table 2, which shows the superiority of GrokFormer over state-of-the-arr baselines in both homophilic and heterophilic datasets.
Results.
Both spatial- based and spectral- based models perform well on the homophilic networks as they can easily capture the similarity information between neighbors, and the low-pass filter is easy to fit in the homophilic networks. Although some GT-based methods, like GraphGPS, also capture the similarity information between neighbors by integrating GNNs with Transformers, resulting in certain performance improvement compared to vanilla Transformer, their heavy
6

---

GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers
Table 4: Filter fitting results in the form of SSE + (IP² score 1). Lower SSE (higher Rt²) indicates better performance.
Low-pass
High-pass
Band-pass
Band-rejection
Comb
Low-comb
Models
exp(-10X-)
I-exp(-10X²)
exp(-10(A-
1)9
1-exp(-10(A 1)2
[))n
GCN
3.5149(98872)
68.6770(2400)
26.2434( 1074)
21.0127(9440)
49. (9.023(3303)
(1.1371(9158)
GAT
2.6883(9888)
21.5288(.7447)
13.8871(-4987
12.9724
22.0646(.690
29.2842(.9277)
ChebyNet
0.8284(.9973)
0.7796(.990)
2.3071((910))
2.5455((9934)
(.0355(99455)
5.0966(_9866
GPRGNN
0.4378(99883)
0.1046(.9985
2.1593(.8952
4.2977(.9894)
4,9416(
8.6554(
BerNNet
0.0319(9999)
0.01466 9998)
0.0388( (9984)
0.9419(9973)
(.1073(9853)
4.5643(9878)
Specformer
0.0015(:9999)
0.0029(
0.0010(.9999)
0.0027(.999)
0.0062(
0.0283(.9998)
GrokFormer
0.0011(:9999)
0.0012(9999)
0.0004(.9999)
0.0024(9999)
0.0021(9999)
0.0029(9999)
emphasis on global information and dependence on a freely learned attention matrix often make them susceptible to overfitting.
addition, compared to the kernel-based models, our ap- proaches achieve greater improvement, with a maximum improvement of 34.9% in PTC-MR. GNNs and GT's gen- erally perform better than traditional kernel methods. Re- markably, due to its more expressive power, GrokFormer shows consistent superiority over the strongest baseline, Specformer, achieving an average improvement of 5.6% across all datasets.
Heterophilic networks usually require complicated filters that have their spectrum adaptive over all cigenvalues to perform well. Thus, only Specformer and our GrokFormer can learn and fit such complex filters; the other methods fail to perform satisfactorily. Compared to Specformer, our GrokFormer performs better because our filter lever- ages both order- and spectral-adaptics learning power, while Specformer ignores the order-adaptive. In addition, Spec- former learns node representations solely from the spectral domain, whereas our GrokFormer takes into account both spectral and spatial information simultancously. Besides, GrokFormer can scale up in large graphs via the use of efficient self-attention and truncated decomposition.
5.3. Effectiveness of GrokFormer in Learning Pre-defined and Unknown Filter Patterns
5. PRE-DEFINED FILTERS IN SYNTHETIC DATASETS
Following prior work (Bo et al., 2023), we generate datasets with six filter patterns of various levels of difficulty. Specifi- cally, images with a resolution of 100 x 100 from the Image Processing in Matlab library' are taken, with the image rep- resented as a 2D regular grid graph with 4-neighborhood connectivity. The pixel values serve as node signals ranging from O to 1. These image share the same adjacency ma- trix A E R 110000010000 and the m-th image has its graph signal Z'm. E 100000 We apply six different predefined filters the spectral domain of its signal, with each filter detailed in Table 4, where (A) of Low-comb is defined as 1o,005; (A) + [sin(TTA] ((....)) + [2in( [1.2). with In = 1 when À E Ω, La = 0 otherwise.
5.2. Performance for Graph Classification
Dataset. We also conduct graph classification experiments on five TU benchmarks from diverse domains. They in- clude three bioinformatics graph datasets, i.e., PROTEINS (Borgwardt et al., 2005), PTC-MR (Toivonen et al., 2003), and MUTAG (Debnath et al., 1991) and two social net- work datasets, i.e., IMDB-BINARY and IMDB-MULTI (Yanardag & Vishwanathan, 2015) (see Appendix A.1 for more details).
We compare the capability of our GrokFormer filter with six baselines, including GCN, GAT, ChebyNet, GPRGNN, BernNet, and Specformer, in fitting these pre-defined fil- ter patterns through node regression task. The hy- perparameters for our model were probed in M (16, 32, 64, 128, 256), K E (1,2, 10). For baselines, we set the hyper-parameters suggested by their authors and tune the hidden dimensions to maintain a consistent param- eter scale. Two popular evaluation criteria - the sum of squared errors and the R² score are used.
Baselines and Settings. We compare GrokFormer with diverse comepting models, including kernel-based methods: GK (Shervashidze al., 2009), WL kernel (Shervashidze et al., 2011) 1) and DGK (Yanardag & Vishwanathan, 2015), popular GNN-based models: DGCNN (Zhang et al., 2018), GCN, GIN (Xu et al., 2018), GDN (Zhao et al., 2020), and HiGCN, as well as GTs. We follow the same evaluation protocol of InfoGraph (Sun al., 2020) to conduct 10-fold cross-validation scheme and report the maximum average validation accuracy across folds (see Appendix A.2).
The fitting results are reported in Table 4. We can observe that (1) Our GrokFormer filter consistently achieve the best performance in both metrics. For complex graph filters, such
Results. The performance of graph classification is pre- sented in Table 3. We find that the proposed GrokFormer outperform state-of-the-art baselines on 4 out of 5 datasets and achieve 11.9 1. relative improvement in PTC-MR. In
7

---

GrokFormer: Graph Fourier Kolmogorov-Amold Transformers
99
Accunscy
Accestaccy
87
85
0.0
0.5
1.5
2.0
1.0
2.5
5
A
lndex of max de
k
fndet k of max de
2
(a) Cora
(b) Citeseer
(a) Cora
(b) Pubmed
1.2
0.9
78
0.66
Acontr Nobtraay
0.3
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
(c) Squirrel
(d) Texas
2 A Index of max
K
3 4 Index of max
K
Figure 3: Filters learned by our GrokFormer on Cora and Citeseer (homophilic graphs), and Squirrel and Texas (het- erophilic graphs). See Appendix B.2 for the other datasets.
(c) Squirrel
(d) Chameleon
Figure 4: Order adaptivity analysis results on two ho- mophilic graphs, including Cora and Pubmed, and two het- erophilic graphs including Squirrel and Chameleon. See Appendix B.3 for the other datasets.
as Comb and Low-comb, our filter can also perform very well, demonstrating its strong expressivity in fitting the com- plex filters. (2) GCN and GAT can only learn low-pass filter well, which is not effective in heterophilic graph learning. (3) Polynomial-basee spectral GNNs, ChebyNet, GPRGNN, and BernNet perform better than GCN by approximating graph filtering using order-adaptive polynomials. However, their expressiveness is still limited in learning complex fil- ters due to fixed filter bases. (4) Specformer learns filters through spectrum adaptation, possessing stronger expres- sive ability than polynomial filters, but still weaker than filter in fitting higher-order patterns it is pre-fixed to 1st order spectrum, leading to less effective performance in fitting Comb and Low-comb. Visualization of the filter fitting results is provided in Appendix B.1.
heterophily, GrokFormer adaptively learns a high-pass filter to capture the differential information between nodes. On Squirrel, which has dense and mostly heterophilic edges, GrokFormer also effectively learns the heterophily, result- ing in comb-alike filter. Importantly, GrokFormer does not require prior knowledge to manually tune the spectrum hyperparameters to achieve this; it learns to adaptively fit dif- ferent filters hidden in the graphs with different homophilic and heterophilic properties. Similar results can be found for the other datasets in Appendix B.2.
Adaptability in Graph Spectral Order. Similarly, we also analyze the order adaptability of GrokFormer on Cora, Pubmed, Squirrel and Chameleon. To this end, we evaluate the accuracy performance of GrokFormer with all other settings fixed except that we increase the order K from one to six, from which we observe the relation of k and K w.r.t the best accuracy. The results are shown in Figure 4. Cora and Pubmed are strong homophilic network that expect the low-pass filter, and such filter is easy to learn, on which GrokFormer fits the graph adaptively with a small K (i.e., K < 3) rather than overfitting it with a large K. Squirrel and Chameleon have large number of heterophilic edges, requiring more complex frequency response (see Figure 3), on which GrokFormer learns to adaptively use large K (i.e., K 3) for capturing rich frequency components instead of restricting in using small K values. Additionally, we can observe that the maximum order coefficient ag is distributed within the K < 3 order filter basis on Cora and Pubmed, while on Squirrel and Chameleon, as the order K increases, the largest order coefficient og extends to
5.3.2. UNKNOWN FILTERS IN REAL-WORLD HOMOPHILIC AND HETEROPHILIC DATASETS
We investigate the filters learned by GrokFormer on real- world homophilic and heterophilic datasets used in Table 2. Note that no exact ground truth filter patterns are known these real-world datasets, but the visualization of the learned spectrum offers important insights into how the spectrum and order adaptability in Fromer enables the learning of complex homophilyyhhterophiiy relations.
Adaptability in Graph Spectrum. To analyze the impor- tance of spectrum adaptability, we plot the filters learned by GrokFormer on two typical homophilic datasets, Cora and Citeseer, and two heterophilic datasets, Squirrel and Texas, in Figure& 3. We observe that GrokFormer learns a low- pass filter on Cora and Citeseer, aligning with their strong homophily. In contrast, on Texas, which exhibits strong
8

---

GrokFormer: Graph Fourier Kolmogorov-Armold Transformers
Table 5: Ablation studies on node- and graph-level tasks
Table 6: The training cost in terms of GPU memory (MB)
and running time (s).
Method
Node-level
Graph-level
Cora
Penn94
Texas
PROTEINS
IMDB-B
Dataset
Method
Memory (MI3
Time (s)
SE
77.42-13 76,29+035 90.33+236
71,4+37
74,9+3a
PolyFormer
1836
13.58
GFKAN
88.98 25 21 to
93.62210
16.
87.3ass
Cora
Specformer
1509
4.35
Full Model
89,57_14 83 94,59
78.2244
88.525
GrokFormer
1267
3.23
PolyHormer
14113
121.78
Penn94
Specformer
5053
9.39
GrokFormer
4647
8.13
the higher-order filter basis. This shows that our method can learn to adaptively assign a large weight the most suitable filter bases, thereby achieving synthesized filter specifically for the training graph. More results can be found for the other datasets in Appendix B.3.
for polynomial bases of PolyFormer. The pre-processing of all models is not included in the training time. The results are shown in Table 6.
Results. From Table 6, we can find that our GrokFormer shows high efficiency. Compared with Specformer that performs self-attention on N eigenvalues with O(N2) com- plexity, Fourier series representation in our GrokFormer of- fers lower training complexity, scaling linearly with (NV). PolyFormer needs to calculate the self-attention weights of K polynomial bases for N times, which requires lot of computations, but Specformer and our GrokFormer only need to calculate Udiag(A)UT once for non-local infor- mation passing. Besides, Specformer and our GrokFormer utilize 2-layer MLP (embedding layer) on the feature ma- trix X to reduce the feature dimension F to number of classes C (C < F) before information passing, but Poly- Former does not have this embedding layer, so it consumes more computation. In the large graph Penn94, Specformer and our GrokFormer use truncated spectral decomposition to reduce the forward complexity, so it is more efficient than PolyFormer.
5.4. Ablation Study
The ablation study is performed to analyze the performance of GrokFormer (Full Model) compared to its two variants: i) Self-attention-E (SE), which contains only efficient self- attention mechanism in GrokFormer, with the proposed spectral graph convolution module removed; ii) Graph Fourier KAN (GFKAN) that keeps the spectral graph con- volution module only. The results on three node classi- fication datasets and two graph classification datasets are reported in Table 5. It can be observed that Self-attention-E shows good performance in some datasets such as Texas, outperforming most spatial methods in Table 2, due to its ability to capture the feature similarity of the global node. However, it struggles to perform well on the other graph datasets due to its limitation in capturing non-low frequency graph information. The proposed Graph Fourier KAN sig- nificantly enhances the performance, showing competitive performance against the state-of-the-an competing methods in Table 2. This superiority benefits from its order and spec- trum adaptability that enables expressive graph representa- tion learning without using self-attention. However, on the large-scale dataset penn94, which exhibits low level of ho- mophily, relying solely on spectral information from Graph Fourier KAN proves insufficient. GrokFormer achieves consistently improved performance only when both Graph Fourier KAN and self-attention are integrated, demonstrat- ing its ability to effectively synthesize the strengths of both modules and outperform its individual variants.
6. Conclusion and Future Work
This paper presents GrokFormer, a novel GT model that learns expressive, adaptive spectral filters through order-K K Fourier series modeling, overcoming the limitations of self- attention to effectively capture rich frequency signals in a broad range of graph spectrum and order. Experiments on the synthetic dataset show that the proposed Gromer filter is more expressive than SOTA graph filters used in GNNs and GTs. Comprehensive experiments on real-world datasets also demonstrate that the superiority of GrokFormer over SOTA GNNs an GTs. A promising future direction is to learn graph filters with strong expressiveness more efficiently, without the need for spectral decomposition.
5.5. Empirical Time and Space Complexities
In this section, we apply Cora and Penn94 to verify the effi- ciency of GrokFormer. We test the time and space overheads of GrokFormer and two spectral GTs, i.e., PolyFormer and Specformer.
A Acknowledgments
Setup. To perform fair comparison, we run each model for 1,000 epochs and report the total time and space costs. We set the hidden dimension = 64 for all methods. For Spec- former and our GrokFormer, we use use full eigenvectors for Cora and 6,000 eigenvectors for Penn94. We set K = 10
This research is supported in part by A under its MTC YIRG Grant (No. M24N8c0103), the Ministry of Education of Singapore under its Tier-1 Academic Research Fund (No. 24-SIS SIS-SMU-008), and the Lee Kong Chian Fellowship.

---

GrokFormer: Graph Fourier Kolmogorov-Armol Transformers
Impact Statement
Chen, J., Li, Z., Zhu, Y., Zhang, J., and Pu, J. From node interaction hop interaction: New effective and scal- able graph learning paradigm. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7876-7885, 2023c.
This paper presents work whose goal to advance the field of graph machine learning. There are many potential soci- etal consequences our work, none of which we feel must be specifically highlighted here.
Chen, J., Liu, C.,, Gao, K.. Li, G., and He, K. Nagphormert: A tokenized graph transformer with neighhorhood aug- mentation for node classification in large graphs. IEEE Transactions on Big Data, 2024a.
References
Ai, G., Yan, H., Wang, H.,, and Li, X. A2gen: Graph convo- lutional networks with adaptive frequency and arbitrary order. Pattern Recognition, 156:110764, 2024.
Chen, J., Liu, H., Hopcroft, J., and He, K. Leveraging contrastive learning for enhanced node representations in tokenized graph transformers. Advances in Neural Infor- mation Processing Systems, 37:85824-85845 2024b.
Bastos, A., Nadgeri, A., Singh, K., Kanezashi, H., Suzu- mura, T., and Mulang, O. How expressive are trans- formers in spectral domain for graphs? Transactions Machine Learning Research, 2022.
Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive uni- versal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, ICLR 2021, 2021.
Bo, D., Wang, X., Shi, C., and Shen, H. Beyond low- frequency information in graph convolutional networks. In Proceedings of the AAAI conference artificial intel- ligence, volume 35, pp. 3950-39577 2021.
Choromanski, K., Lin, H., Chen. H., Zhang, T., Schanobish, A., Likhosherstov, V., Marker-Holled J., Sarlos, T., Weller, A., and Weingarten, T. From block-toeplitz matrices differrntial equations on graphs: towards a general theory for scalable masked transformers. In International Conference on Machine Learning, pp.
Bo, D., Shi, C., Wang, L., and Liao, R. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations, 2023.
2022,
Bo, D., Fang, Y., Liu, Y., and Shi, C. Graph contrastive learning with stable and scalable spectral encoding. Ad- vances in Neural Information Processing Systems, 36, 2024.
Debnath, A. K., Lopez de Compadre, R. L.., Debnath, G., Shusterman, A. J., and Hansch, C. Structure-activity rela- tionship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S., Smola, A. J., and Kriegel, H.-P Protein function prediction via graph kernels. Bioinformatics, (suuppl_ i47-i56, 2005.
Defferrard, M., Bresson, X., and Vandergheynst, P. Con- volutional neural networks on graphs with fast localized spectral filtering. Advances in neural information pro- cessing systems, 29, 2016.
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.075:: 2017.
Deng, C., Yue, Z., and Zhang, Z. Polynormer: Polynomial- expressive graph transformer in linear time. In The Twelfth International Conference on Learning Represen- tations, 2024.
Cai, Y., Fang, G., and Li, A note on sparse generalized eigenvalue problem. Advances in Neural Information Processing Systems, 34:23036-23044 2021.
Chen, D., O' O'Bay, L., and Borgwardt, K. Structure-aware transformer for graph representation learning. In Interna- tional Conference on Machine Learning, pp. 3469-3489, 2022.
Diederik, P. K. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations (Poster), 2015.
Dong, Y., Ding, K., Jalaian, B., Ji, S., and Li, J. Adagnn: Graph neural networks with adaptive frequency response filter. In Proceedings of the 30th ACM international conference on information knowledge management, pp. 392 401, 2021.
Chen, J., Gao, K., Li, G., and He, K. Nagphormer: A tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference Learning Representations, 2023a.
Chen, J., Li, G., Hopcroft, J. E., and He, K. Signgt: Signed attention-base graph transformer for graph representa- tion learning. arXiv preprint arXiv:2310. /025, 2023b.
Dwivedi, V. P. and Bresson, X. transformer networks to graphs. arXiv preprint arXiv22012.09699, 2020.
generalization
10

---

GrokFormer: Graph Fourier Kolmogorov-Armold Transformers
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T. and Beaini, D. Long range graph bench- mark. Advances in Neural Information Processing Sys- tems, 25:22326-22340, 2022.
Ma, J., He, M., and Wei, Z. Polyformer: Scalable node-wise filters via polynomial graph transformer. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp. 2118 2129, 2024.
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Ben- gio, Y.. and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Ma, L., Lin, C., Lim, D., Comero-Soriang A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph in- ductive biases in transformers without message passing. International Conference on Machine Learning, pp. 23321 23321-23337. PMLR, 2023.
He, M., Wei, Z., Xu, H., et al. Bemnet: Learning arbitrary graph spectral filters via bernstein approximation. Ad- vances in Neural Information Processing Systems, 34: 14239-14251, 2021.
Maziarka, E.., Danel, T., Mucha, S., Rataj, K., Tabor, J., and Jastrzebski, Molecule attention transformer. arXiv preprint arXiv:2002.08264 2020.
Huang, Y., Zeng. Y., Wu, Q.. and Lü, L. Higher-order graph convolutional network with flower-petals laplacians simplicial complexes. In Proceedings of the AAAI Con- ference Artificial Intelligence, volume 38, pp. 12653- 12661, 2024.
Oono, K. and Suzuki, Graph neural networks exponen- tially lose expressive power for node classification, In International Conference Learning Representations, 2020.
Irwin, J. J., Sterling, T., Mysinger, M. M., Bolstad, E. S., and Coleman, R. G. Zinc: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7):1557-1768 2012.
Pei. H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representa- tions, 2020.
Ismayilova, A. and Ismailov, V. E. On the kolmogorov neural networks. Neural Networks, 176: 106333, 2024.
Pinkus, A. Weierstrass and approximation theory. Journal of Approximation Theory, 107(1); 2000.
Kim, J., Nguyen, D., Min, S., Cho, S., Lee, M., Lee, H., and Hong, S. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35: 14582-14595, 2022.
Qiao, H., Wen, Q. Li, X., Lim, E.-P., and Pang, G. Gener- ative semi- semi-supervised graph anomaly detection. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, pp. 10-15, 2024.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017.
Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, seal- able graph transformer. Advances Neural Information 2022.
Kolmogorov, A. N. On the representation of continuous functions of many variables by superposition of contin- uous functions of one variable and addition. In Dok- lady Akademii Nauk, volume 1 14, pp. 953-956. Russian Academy of Sciences, 1957.
Processing Systems, 35:
Shehur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 181.05668, 2018.
Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and Tossou, Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618 8-66999 2021.
Shen, Z., Zhang, M., Zhao, H., Yi, S., and Li, Efficient attention: Attention with linear complexities. In Proceed- ings of the IEEE/CVF winter conference applications 2021.
of computer vision, pp.
Lim, D., Hohne, F., Li, X., Huang. S. L., Gupta, V., Bhalerao, O., and Lim, S. N. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Pro- cessing Systems, 34:20887-20902, 2021.
Shervashidze, N., Vishwanathan, S., Petri, T., Mchlhorn, K., and Borgwardt, K. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pp. 488-495, 2009.
Liu, Z. Wang, Y., Vaidya, S., Ruchle, F. Halver- son, J., Soljačić, M., Hou, T. Y. and Tegmark, M. Kan: Kolmogorov-arnol networks. arXiv preprint arXiv:2404. 19756, 2024.
Shervashidze, N. Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.

---

GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers
Shi, H., GAO, J., Xu, H., Liang, X., Li, Z., Kong, L., Lee, S. M., and Kwok, J. Revisiting over-smoothing in bert from the perspective of graph. In International Confer- ence on Learning Representations, 2022.
Wu, Q. Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., and Yan, J. Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36, 2024.
Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and Vandergheynst, P. 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.
Wu, Z., Jain, P., Wright, M., Mirhoseini, A., Gonzalez, J. E., and Stoica, Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 13279, 2021.
Stein, E. M. and Shakarchi, R. Fourier analysis: an intro- duction, volume 1. Princeton University Press, 2011.
Xu, B., Shen, H., Cao. Q.. Cen, K., and Cheng, X. Graph convolutional networks using heat kernel for semi- supervised learning. In Proceedings of the 28th Inter- national Joint Conference on Artificial Intelligence, pp. 1928-1934, 2019.
Sun, F.-Y., Hoffman, J., Verma, V., and Tang, J. Infograph: Unsupervised and remi-supervised graph-level represen- tation learning via mutual information maximization. In International Conference Learning Representations, 2020.
Xu, J., Chen, Z., Li, J., Yang, S., Wang, W., Hu, X., and Ngai, E. C.-H. Fourierkan-gef: Fourier kolmogorov- aroold network-an an effective and efficient feature transfor- mation for graph collaborative filtering. arXiv preprint arXiv:2406.0100 2024.
Toivonen, H., Srinivasan, A., King, R. D., Kramer, S., and Helma, C. Statistical evaluation of the predictive tox- icology challenge 2000-2001. Bioinformatics, 19(10):
1183-1193, 2003.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding oqur-squa and bottlenecks graphs via curvature. In International Conference on Learning Representations, 2022.
Yan, H., Ai, G., and Li, X. Selective-hop graph neural networks for semi-supervised node classification. Neuro- computing, 61 128812, 2025.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Atten- tion is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Yanardag, and Vishwanathan. Deep graph kernels. In Proceedings of the 2 ACM SIGKDD international conference knowledge discovery and data mining, pp. 1365-1374, 2015.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Yi, K., Zhang, Q., Fan, W., He, H., Hu, L., Wang, P., An, N., Cao, L.,, and Niu, Z. Fouriergnn: Rethinking multivariate time series forecasting from a pure graph perspective. Advances in neural information processing systems, 36: 2023.
Wang, P., Zheng, W., Chen, T., and Wang, Z. Anti- oversmoothing deep vision transformers via the fourier domain analysis: From theory practice. In Interna- tional Conference on Learning Representations, 2022.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888
Wang, X. and Zhang, M. How powerful are spectral graph neural networks. In International conference on machine learning, pp. 11341223362, 2022.
2021.
Zhang, J., Zhang, H., Xia, C., and Sun, L. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001. 051440, 2020.
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Wein- berger, K. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861- 2019.
Zhang, M., Cui, Z.,, Neumann, M., and Chen, Y. An end-to- end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 32, 2018.
Wu, Q. Zhao, W., Li, Z., Wipf, D. P., and Yan, J. Node- former: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27401, 2022.
Zhao, W., Fang, Y., Cui, Z., Zhang. T., Yang, J., and Liu, W. Graph deformer network. In Proceedings of the Thirtieth
12

---

GrokFormer: Graph Fourier Kolmogorov-Armol Transformers
International Joint Conference on Artificial Intelligence, pp. 1646-1652, 2020.
Zhu, J., Yan, Y. Zhao, L., Heimann, M., Akoglu, L., and Koutra, Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
13

---

GrokFormer: Graph Fourier Kolmogorov-Armol Transformers
A. EXPERIMENTAL DETAILS
A.1. DATASETS
Table Statisties of node classification datasets.
Datasets
Cora
Citeseer
Pubmed
Photo
WikiCS
Physics
Penn94
Chameleon
Squirrel
Actor
Texas
#Nodes
2,708
3,327
19,717
7.650
11701
34,493
41,554
2,277
5,201
7,600
183
#Edges
5,429
4,732
44,338
238,163
216,123
247.962
1.362,229
36.101
217,073
33,544
295
#Features
1,433
3,703
500
745
300
500
4,814
2,325
2,089
931
1,703
#Classes
7
10
2
5
5
H
0.81
0.74
0,80
0.83
0.57
0.91
0.47
0.23
0.22
0.22
0.06
The homophily ratio H. in Table as measure of the graph homophily level is used to define graphs with strong homophily/hhterophily.. The homophily ratio is defined H [((,,,, (. DeA.n=s (Zhu al., 2020), which the [E]
fraction of edges graph which connect nodes that have the same class label. Homophily ratio + represents the graph exhibit strong homophily, while the graph with strong heterophily (or low/weak homophily) have small homophily ratio H. + O.
Table 8: Statistics of graph classification datasets
Datasets
PROTEINS
MUTAG
PTC-MR
IMDB-B
IMDB-M
#Graphs
1113
188
344
1000
1500
#Classes
2
2
2
3
#Nodes (Max)
620
28
109
136
89
#Nodes (Avg.)
39.06
17.93
14.29
19.77
13.00
#Edges (Avg.)
72.82
19.79
14.69
13.06
65.93
A.2. DETAILED EXPERIMENTAL SETUP
1. OPERATING ENVIRONMENT
For the implementation, we utilize NetworkX, Pytorch, and Pytorch Geometric for model construction. All experiments are conducted on NVIDIA GeForce RTX 3090 GPUs with 24 GB memory, TITAN Xp GPU machines equipped with 12 GB memory.
A.2.2. NODE CLASSIFICATION
We train all models with the Adam optimizer (Diederik & Ba. 2015) following previous works (Bo et al., 2021; 2023). We run the experiments with 2,000 epochs and stop the training in advance the validation loss does not continuously decrease for 200 epochs. Classification accuracy is used as metric to evaluate the performance of all models (Kipf & Welling, 2017; Veličković et al., 2018). For the large-scale dataset Penn94, (Lim et al., 2021) provides five official splits, so we run it five times to report the mean accuracy. For other datasets, we run the experiments ten times, each with a different random split. Moreover, due to the increased number of nodes and edges, we set K 10 for Penn94.
The hyper-parameter ranges used for tuning each dataset follows:
Number of layers: {1, 2, 3):
Number of Fourier series expansion terms: {16, 32, 64);
Number of heads: 2, 4, 5);
Hidden dimension: {64, 128);
Learning rate: {0.01, 0.005):
Number of K: (1, 2, 3, 4, 6, 10):
14

---

GrokFormer: Graph Fourier Kolmogorov-Armol Transformers
1.0
GoradTukk
1.0
1.0
GouadTauk
Socciam:
Speoome
GoneFomer
0.8
GulFara
h0)
0.6
GoandTuuk
Specfermt
0.6
0.4
0.4
Goofertazz
Bernher
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.5
1.0
1,5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Low-pass
(b) High-pass
(c) Band-pass
1.2
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.4
Goazdd
0.2
SpecGence:
GriiFomme
GrokFumnt
Speelinne
0.2
GridForme
Specfam
Bunehki
0.0
Ban8ia
1,0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.5
(d) Band-rejection
Comb
(f) Low-comb
Figure 5: Illustrations six filters and their approximations learned by our GrokFormer filter, BernNet, and Specformer.
Weight decays: (5e-3, 5c-4, 5e-5);
Dropout rates: {0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.7.
A.2.3. GRAPH CLASSIFICATION
We use the Adam optimizer train all models. Following (Sun et al., 2020), we perform 10-fold cross validation. We report the average and standard deviation of validation accuracies across the 10 folds within the cross-validation. We implement readout operations by conducting max pooling to obtain a global embedding for each graph. Since the computational complexity of vanilla self-attention in graph classification task can be alleviated by tuning batch size, we employ the vanilla self-attention mechanism in the graph-level representation learning. Hyperparameter selection range as follows:
Number layers: {1, 2):
Epoch: {100, 200, 300]:
Learning rates: (0.01, 0.005, 0.001):
Weight decay: (0.0, 0.0005, 0.00005):
Dropout rate: (0.0, 0.05, 0.1};
Number of Fourier series expansion terms: (16, 32, 64);
Hidden dim: (32, 64, 128);
Number of K: (1. 2, 3, 4, 6):
Batch size: (128}:
15

---

GrokFormer: Graph Fourier Kolmogorov-Armol Transformers
h22
hP) 12
1.0
0.5
0.0
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1,0
2,0
0
0.0
0.5
1.0
1.5
2.0
(a) Pubmed
(b) Photo
(c) WikiCS
(d) Physics
2.0
hgg
1.3
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.0
0.5
1.0
1.5
2.0
h.
A
(e) Penn94
(f) Chameleon
(g) Actor
Figure 6: Filters learned from real-world datasets with varying graph properties by our GrokFormer.
B. MORE EXPERIMENTAL RESULTS
B.1. VISUALIZATION OF LEARNED FILTERS ON SYNTHETIC DATASETS
Here we illustrate six filters and their approximations learned by our GrokFormer filter, BernNet, and Specformer in Figure 5. In general, GrokFormer filter can learn a precise approximation of these filters. However, polynomial filter of BernNet is difficult to these filters, especially other complex filters beyond low-pass and high pass filters. Although Specformer has been well fitted, our proposed filter can perform much better, especially on filters with more complex patterns, such as Comb and Low-comb.
B.2. VISUALIZATION OF LEARNED FILTERS ON REAL-WORLD DATASETS
In this section, we visualize more filter results learned by our GrokFormer on real-world datasets. From Figure 6, we find that (I) on homophilic graphs, our proposed filter learns low-pass filters with different amplitude and frequency responses for them, which is consistent with the homophily property, i.e., the low-frequenge information is important in the homophilic scenario. (2) Edges in Chameleon and Penn94 datasets dense and mostly heterophilic, comb-alike filters with complex frequency components for them. (3) our GrokFormer filter learns an all-pass filter on the Actor dataset protecting its raw features, which is consistent with the fact that its raw features are associated with labels (He et al., 2021).
proposed filter learns
B.3. ADAPTIVITY IN GRAPH SPECTRAL ORDER
Figure 7 shows additional results on order adaptivity. We observe that GrokFormer achieves the best performance when K small on all homophilic datasets. This because the low-pass filters desired by homophilic networks (see Figure 6) are easy to learn. GrokFormer fits the graph adaptively with a small K rather than overfitting with a large K. In addition, as shown in Figure 3 and Figure 6, a high-pass filter required by the strong heterophilic network Texas, and an all-pass filter desired by the Actor are also easy learn, so GrokFormer fits them adaptively with a small K. However, for Penn94, which have dense edges and predominantly heterophilie, complex comb-like mikb filters (see Figure 6) are required. As result, Fromerrmer learns to adaptively use larger K to capture broader range of frequency components, rather than restricting itself to a small K. Moreover, we can find that GrokFormer filter assign the largest order coefficient to K < 3 order filter basis on these datasets that expect simple filters (low-pass, all-pass, high-pass), while on Penn94, the largest order coefficient ag extends to the higher-order filter basis. This demonstrates that our method can effectively learn order-adaptive filters for datasets with varying properties.
B.4. GRAPH CLASSIFICATION AND REGRESSION
In this section, we conducts experiments on additional graph-level datasets, including subset (12K) of ZINC molecular graphs (250K) dataset (Irwin al., 2012), the super-pixels dataset CIFARTO (Dwivedi al., 2023), and a long-range graph
16

---

GrokFormer: Graph Fourier Kolmogorov-Arood Transformers
85
86
96
2 5 Acoieaa
81
94
Index of max
2
Index max O2
Index of inax
Index of de
2
5
6
(a) Citeseer
(h) WikiCS
(c) Photo
(d) Physics
84
45
Acsuracy
Accurdey
7 1
4 K
6 Index of mon dz
3
Index k
3 A
Inder of mox dx
k
5
5
Og
(c) Penn94
(f) Actor
(g)
Texas
Figure 7: Order adaptivity analysis results.
Table 9: Detailed information of additional graph-level datasets.
#Graphs
Avg. #nodes
Avg. #edges
Node feat. (dim)
Edge feat. (dim)
Tasks
Metric
ZINC
12,000
23.2
24.9
Atom Type (28)
Bond Type (4)
Regression
MAE
CIFAR10
60,000
117.6
941.1
Pixel[RGB]+Coord (5)
Node Dist (1)
Classification
ACC
Peptides-fune
15,535
150.9
307.3
Atom Encoder (9)
Bond Encoder (3)
Classification
AP
benchmark Peptides-func (Dwivedi et al., 2022). We choose graph Transformers with positional or structural embedding (Graphormer, GraphGPS and GRIT) as the baselines. All experiments are conducted on the standard train/validation/test
splits of the evaluated benchmarks. We use the hyperparameter for the basclines as suggested their respective papers. Our
hyper-parameterr and ranges follows:
Dropout: {0.0, 0.05, 0.1):
Number of layers: {4, 6, 8);
Number of Fourier series expansion terms: (16, 32, 64);
Number of heads: 21, 2, 3, 53:
Learning rate: {0.001, 0.0001, 0.0005);
Number of K: (1, 2, 4, 5, 6);
Weight decays: (5c-4, 5e-5}:
Table 10: Results on additional graph-leved datasets. **" means edge feature encoded.
ZINC (MAE.)
CIFARIO (ACC1)
Peptides-fund (APt)
Peptides-fune"
Graphormer
0.122
GraphGPS
0.070
72.31
0.6535
0.6257
GRIT
0.060
75.67
0.6988
0.6458
Gromerrmer
0.076
74.26
0.6415
0.5987
17

---

GrokFormer: Graph Fourier Kolmogorov-AAmold Transformers
Internal MPGNN: {GCN, GatedGCN(Bresson & Laurent, 2017));
From the results, we observe that GrokFormer achieves better performance than Graphormer and performs comparably well to GraphGPS. GrokFormer slightly underperforms GRIT ZINC and CIFARIO, while the performance margin Peptides-func is relatively large. GRIT is designed to improve GT's expressiveness in large datasets by incorporating graph inductive biases, so it shows an advantage on long-range graph dataset. Although GraphGPS achieves better performance on ZINC and Peptides-func, it exhibits suboptimal results on CIFARIO and the node-level datasets due to overfitting. In GrokFomer, we aim to enhance the GT's capability to capture various frequency information on graphs by designing an expressive filter. It achieves a relatively better balance between the generalization ability and the expressiveness, leading to a robust performance on both node-level and graph-level datasets.
C. THEORETICAL PROOFS
In the following, we present the proof for Proposition 4.1.
Proof. For the spectrum of graph Laplacian X, the corresponding arbitrary order is given by : = When processed by the order-wise MI.P with the trainable weight w = [Wo, "1,""" [uk] E R RIXK the new spectrum Xacio is
updated as Anew = wo + wi\² + w2\² + + + wx
In Eq. (9), we eliminate the learnable nonlinear function over the spectrum and define our GrokFormer filter function as follows:
K
M(A) Σ a
(13)
k=
where og learned based on the k-order spectrum x This value serves as order-adaptive weight for the polynomial filter similar wn of MLP. Therefore, the designed GrokFormer filter function is learnable in terms of the spectral order.
Secondly, GrokFormer filter function can be reduced into simpler form follows, when removing the order adaptivity term and the higher-order term:
M
A(A) Σ
(cos (mA) am + sin (mA) .mn)
(14)
Here, sin(mA) and cos(m)) with m E [0, M] scale the spectrum with different frequency components. Therefore, different scales of the spectrum are adjustable due the presence of learnable coefficient am and bm They serves as the spectrum-adapted weights for the filter. Therefore, GrokFormer filter function is also learnable in terms of the graph spectrum.
In the following, present the proof for Proposition 4.2.
Table 11: The filter form of polynomial GNNs
Model
Filter
APPNP
h(A)
Σ k
k=0 1-
X)*
GPR-GNN
h(A)
2k=0 (1 A)*
BernNet
h(A)= = k=u ag ( >) ( 4k
EK
K
JacobiConv
A(A) = Σk D Dalkkta-illbbtte
(k+a) 2) (2- X)
Proof. Polynomial filters are popular in graph representation learning. We show below that the state-of-the-ar (SOTA) polynomial filters listed Table 11 is a simplified form of our proposed filter, some of which are utilized by SOTA methods such FeTA (Bastos et al., 2022) and PolyFormer (Ma et al., 2024).
18

---

GrokFormer: Graph Fourier Kolmogorov-Armod Transformers
First of all, the polynomial filter functions in Table 11 can be uniformly written follows:
h(A) = ao + 01d + oz)² Ox Σ East..
(15)
where a is a learnable parameter. These polynomial functions have fixed filter bases (i.e., X, X2, .... A²), which approximate arbitrary spectral filters an order-adaptive manner. According to the above Proof for Proposition 4.1, our proposed filter can be simplified to:
A.......
K
h(A) Σ agd.
(16)
k=
Therefore, these polynomial filters are the case of a simplified variant of our GrokFormer filter.
Below, we present the proof for Proposition 4.3.
Proof. The very recent model Specformer (Bo et al., 2023) learns graph filters hg (A) via eigenvalue encoding, which can be treated as a linear combination of position encoding in graph Transformer when the self-attention matrix is the identity matrix:
4/2
4/2
c
(A) aud +
Σ sisin i=1
10000
+
Σ
bccos
1000025/a)
(17)
==1
where is hyperparameter and d is the dimension. a; and b; are learnable parameters. If M = d/2 and used, Eq. (17) can be rewritten as follows:
10000 are
(A) = aod + Σ (sin(mA) a; cos(mA) b.).
(18)
Therefore, the Specformer filter learns over the specific first-order spectrum of graph Laplacian.
In Eq. (18), the term A can be combined into sine and cosine terms in an approximate manner. Suppose that constants and @ can be found such that:
ag R sinnnnn + +).
(19)
We can approximate a as a linear combination of Rsnn(A + d). Given that the sine function has the linear combination form sin(x <) = sin(a) cos(Ø) cos(x) sin()), we can get the following:
agd = R(sin(A) ()) cos(o) + cos(A) sin),
(20)
where R, cos( (ò) are constants. Therefore, Eq. (18) can be rewrite as follows,
M
(A) = 0, sin(A) 02 cos(() Σ (sin(mA) + cos(mA) bi).
(21)
where 0, R cos(d)a) and 02 (o))b))
According to the above Proof for Proposition 4.1, our GrokFormer filter can be written as follows:
M
A(A) = Σ
(sin (mA) am cos (mA) - bmn)
(22)
m==
We can further write the Eq. (22) in the following form:
M
Λ(A) = + sin(A) + b cos(A) + Σ (sin (iX) a, + cos (iX) b1).
(23)
Comparing Eq. (21) and Eq. (23), it is clear that the Specformer filter is simplified variant of our GrokFormer filter.
19

---

GrokFormer: Graph Fourier Kolmogorov-Arool Transformers
Next, we provide the proof for Proposition 4.4.
Proof. According to the uniform convergence of Fourier series (Stein Shakarchi, 2011), for any continuous real-valued function (a) [a.b] and I' (x) is piece-wise continuous on [a.b] and any 0, there exists Fourier series P(x)
converges to f(x) uniformly such that
max S
P(x) f(x) <.
(24)
Since the eigenvalues fall in the range [0, 2] and GrokFormer filter is constructed from Fourier series representation, filter can approximate any continuous function in the interval [0, 2] based on the uniform convergence of Fourier series above.
Secondly, the spectral graph convolution in Eq. (8) based on the learnable filter is permutation equivariant because [[IPAP)(PUP) = P(UAUT)P given an arbitrary permutation matrix
20


Reviews:
[{"review_id": "ZSGG0eXR2e", "reviewer": "Reviewer_axD1", "summary": "This paper proposes GrokFormer, a novel graph transformer (GT), with superior capability in modelling complex spectral filters. The filter design is both order and spectrum adaptive and is implemented using a specific instantiation of Kolmogorov-Arnold Network in the spectral domain. Results on several node and graph level tasks demonstrate its effectiveness. The visualizations show the expressive modelling of the designed filters. Specifically, comparison with Specformer for modelling complex, comb-like frequency patterns shows the superiority of this novel parameterization of the filter.\n\n**Update**: I have carefully read the other reviews and the authors' rebuttals. Overall, the new results presented during the rebuttal period improve the paper greatly. Please revise the paper by including these new results and discussions if accepted. I am happy to raise the score to 4 to indicate an accept recommendation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive and positive comments on the presentation, visualization, and experiment design. Please see our response to your comments one by one below.\n\n>**Weaknesses #1 and #2**  Lack of a few challenging benchmark GNN datasets (datasets in [Ref1] and LRGB datasets [Ref2])  and two recent baseline methods (GraphGRS [Ref3] and GRIT [Ref4]).\n\nFollowing your suggestion, we conducted the experiments on the two representative datasets, WikiCS and Peptides-func, obtained from [Ref1] and [Ref2] respectively, to further demonstrate the expressiveness of GrokFormer.  Additionally, we also added the two new expressive GTs, GraphGPS and GRIT, as our competing methods. The experimental results are shown in Tables A1 and A2.\n\n```\nTable A1. Classification accuracy (in percent) on the WikiCS and Test AP on Peptides-func.\n```\n| |WikiCS|Peptides-func|\n| --- | --- |---| \n|Specformer|82.37|0.5771|\n|Polyformer|80.19|0.5319|\n|GraphGPS|78.66|0.6257|\n|GRIT|77.21|0.6458|\n|GrokFormer|83.11|0.5987|\n\n```\nTable A2. Classification accuracy comparison of GRIT, GraphGPS, and GrokFormer.\n```\n||Pubmed|Squirrel|Actor|\n| --- | --- |---|---|\n|GraphGPS|86.94|35.58|36.01|\n|GRIT|87.62|37.68|37.51|\n|GrokFormer|91.39|65.12|42.98|\n\nThe experimental results show that GrokFormer consistently outperforms all competing methods, including the newly added expressive GTs, in Table A2 and on WikiCS of Table A1. This is primarily because expressive GTs like GraphGPS and GRIT struggle to capture the underlying label patterns due to the Transformer's low-pass nature, resulting in suboptimal performance. Note that the spectral-based methods slightly underperform the expressive GTs that are specifically designed to capture the major spatial structure information in Peptides-func, which is not modeled by these general spectral methods.  Thus, we believe that this suboptimal performance does not diminish our contribution in the proposed expressive spectral graph filters, considering its ability in enhancing the Transformer's capability to capture frequency signals beyond low-pass on graphs.\n\n- [Ref1] Benchmarking Graph Neural Networks. JMLR, 2022.\n\n- [Ref2] Long Range Graph Benchmark.  NeurIPS, 2022.\n\n- [Ref3] Recipe for a general, powerful, scalable graph transformer. NeurIPS, 2022.\n\n- [Ref4] Graph Inductive Biases in Transformers without Message Passing. ICML, 2023.\n\n>**Weakness #3**  The theoretical expressivity discussion in terms of WL, and compare and contrast it with existing GTs, e.g.  GRIT.\n\nWe would like to clarify that the spectral graph filter designed in GrokFormer is not based on the spatial-domain WL test. The GrokFormer is a spectral GT operating in the spectral domain while 1-WL or GD-WL algorithms are essentially spatial methods based on the graph structure. Therefore, GRIT exhibits better localization spatially, while our GrokFormer achieves better localization on frequencies. Although our work lacks a formal theoretical analysis in the spatial domain to discuss strong expressivity like the WL test, we provide theoretical analysis in the spectral domain to justify its advantages over existing advanced filters and show that our filter possesses better universality and flexibility. Moreover, the filter fitting experiment on synthetic datasets and comprehensive empirical comparison on real-world datasets demonstrate the stronger expressivity of our GrokFormer filter.\n\n>**Weakness #4** Lack of numerical results for the filter design in Eq. (5). What other alternatives were considered? How were those results compared to this version of the filter?\n\nWe would like to clarify that we have pre-defined six different filters on the synthetic dataset in Section 5.3.1 to verify the fitting capability of the filter design in Eq.(5) compared to alternative methods. Here we present partial results in Table A3 as follows, \n \n```\nTable A3. Node regression results on two difficult synthetic datasets. \n```\n| |High-pass|Comb|\n| --- | --- |---|\n|GPRGNN|0.1046(.9985)|4.9416(.9283) |\n|Specformer|0.0029(.9999) |0.0083(.9998)|\n|PolyFormer|0.0482(0.9993)|0.2868(0.9945)|\n|GrokFormer|0.0012(.9999)|0.0021(.9999)|\n\nNote that we use two metrics to evaluate each method: sum of squared error ($R^2$ score). Lower SSE (higher $R^2$) indicates better performance. The effectiveness of joint filter order-adaptive and spectrum-adaptive properties in Eq.(5) is empirically confirmed through its much better performance on such difficult synthetic datasets. Meanwhile, two simplified alternative cases (a) spectrum-only adaptation without high-order filter terms and (b) filter order-only adaptation are considered in the comparison above.  Per Propositions 4.2 and 4.3, the filter variant in case (a) can be regarded as the Specformer filter, while the variant in case (b) corresponds to the GPRGNN filter. The results show that heir fitting ability of the GrokFormer filter is much stronger than the two alternatives.", "claims_and_evidence": "Theoretical claims: (proofs are in Appendix C)\n\n1) $h(\\lambda)$ is learnable in both polynomial order and graph spectrum.\n\n2) Existing spectral GNNs' filters can be represented by this approach.\n\n3) The graph filter in Specformer is a simplified variant of proposed filter\n\n4) $h(\\lambda)$ can approximate any continuous function and constructs a permutation-equivariant spectral graph convolution (similar proof as in Specformer).\n\nEmpirical claims:\n\n1) Better benchmarking results on both real and synthetic data: Table 2-4\n\n2) More flexible modelling of the frequency spectrum: Figures 1, 5", "methods_and_evaluation_criteria": "The numerical evaluation is  generally comprehensive (specific questions/comments in later sections). In addition to standard transductive node classification benchmarks (both homophilic and heterophilic graphs), several small-scale TU benchmarks for graph classification is also considered. Experiment on the synthetic dataset in Section 5.3 (also studied in Specformer) also shows the impressive modelling capability of GrocFormer.", "theoretical_claims": "The proofs are written clearly, relatively simple to follow and are correct to the best of of my knowledge.", "experimental_designs_or_analyses": "Please see the comments on the experimental evaluation below.", "relation_to_broader_scientific_literature": "This work improves upon Specformer by proposing a more flexible KAN-based parameterization of the filter in the spectral domain, which has superior capability of modelling complicated spectral characteristics.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1) The paper is well-written, easy to read. The visualizations on both synthetic and real data are intriguing.\n\n2) The experiments are thorough and substantiates the main idea clearly for the chosen benchmarks.\n\nWeaknesses:\n\n1) There is no experiments on the popular Benchmarking GNN datasets [1], which are the de-facto benchmarks in recent graph transformers, e.g., GRIT [2]. It is well-known that those benchmarks are more difficult and requires higher expressivity compared to the datasets considered in this paper. For example, the node classification is experimentally studied entirely in the transductive setting in this work, whereas [1] contains inductive node classification benchmarks.\n\n2) Similarly, it would strengthen the paper if the authors include some results on the long range graph benchmark (LRGB) [3] datasets. \n\n3) It would be helpful to characterize the theoretical expressivity of GrocFormer in terms of GD-WL [4], and compare and contrast it with existing GTs, e.g. GRIT [2].  \n\n4) While the authors cite (Xu et al., 2024) for motivating the specific design of the filter in eq. 5, it would be more convincing if some numerical results are presented (even on the synthetic dataset) to showcase why this specific parameterization is chosen. What other alternatives were considered? How were those results compared to this version of the filter?\n\n\nReferences:\n[1] Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking Graph Neural Networks. J. Mach. Learn. Res., December 2022a.\n\n[2]  Ma, L., Lin, C., Lim, D., Romero-Soriano, A., K. Dokania, P., Coates, M., H.S. Torr, P., and Lim, S.-N. Graph Inductive Biases in Transformers without Message Passing. In Proc. Int. Conf. Mach. Learn., 2023.\n\n[3] Dwivedi, V. P., Rampa´sek, L., Galkin, M., Parviz, A., Wolf, ˇG., Luu, A. T., and Beaini, D. Long Range Graph Benchmark. In Adv. Neural Inf. Process. Syst., December 2022b.\n\n[4] Zhang, B., Luo, S., Wang, L., and He, D. Rethinking the Expressive Power of GNNs via Graph Biconnectivity. In Proc. Int. Conf. Learn. Represent., 2023.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please address the questions/comments in the preceding sections.", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "HcEoMXP6A9", "reviewer": "Reviewer_Cg7z", "summary": "The paper introduces GrokFormer, a novel Graph Transformer (GT) model that addresses limitations in existing graph learning methods, particularly in capturing diverse frequency signals in graph data. GrokFormer incorporates a Graph Fourier Kolmogorov-Arnold Network (KAN) to design spectral filters that are both spectrum- and order-adaptive. Unlike prior models with fixed or limited adaptability, GrokFormer uses Fourier series-based learnable activation functions to flexibly model graph Laplacian spectra across multiple orders. The model demonstrates superior expressiveness and adaptability compared to state-of-the-art (SOTA) Graph Neural Networks (GNNs) and GTs. Extensive experiments on node classification and graph classification tasks across various datasets validate its effectiveness, showing consistent improvements over baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive and positive comments on methodology design and theoretical analysis. Please see our response to your comments one by one below.\n\n> **Weakness #1** Limited discussion on potential limitations or failure cases.\n\nThank you very much for the suggestion and question. We will provide a more comprehensive discussion of GrokFormer's potential limitations. One limitation is that when learning optimal spectral filters that requires the complete spectrum, the full spectral decomposition may lead to a huge computational cost on very large datasets, but this limitation do not affect the detection effectiveness of GrokFormer on a variety of real-world graph datasets. Please also find another limitation in our response to Reviewer axD1's Weakness #1 and #2, where we discuss that our spectral graph filter may miss some spatial structure information in some datasets.\n\n> **Weakness #2, Question #2, and Suggestion #2** Can the model's efficiency be improved further by avoiding spectral decomposition entirely? Include runtime comparisons on larger-scale graphs beyond Penn94 for broader scalability insights.\n\nThank you for your insightful suggestion. Avoiding spectral decomposition entirely can further enhance the model's efficiency. To reduce computational costs, we can employ truncated spectral decomposition to compute only the top-$p$ eigenvalues in large-scale graphs.  As shown in Table A1, we provide runtime comparisons on the arXiv dataset, which contains 169,343 nodes (larger than Penn94). By considering only the smallest 5,000 eigenvalues, our model remains computationally efficient even on large-scale datasets.\n\n```\nTable A1. The training cost in terms of GPU memory (MB) and running time (in seconds) on arXiv. \n```\n| |Memory (MB)|Times (s)|\n| --- | --- |---|\n|PolyFormer|4019| 296.53 |\n|Specformer|5565 |6.58|\n|GrokFormer|5491|6.37|\n\n> **Suggestion #1 and Questions #3** Clarify how hyperparameters like $K$ (order) affect performance across different datasets. How sensitive is the performance to hyperparameters like $K$ or the number of Fourier terms ($M$)?\n\nThank you for the valuable comments. In our model, both filter order $K \\in [1,6]$ and Fourier terms $M \\in [32,64]$ can empower the filter to include richer frequency components and enhance the fitting capability of filter.  From the datasets description in Table 6 and the experimental results regarding the filter order $K$ in Figures 3 and 7, we can observe that (1) A smaller $K$ value is suitable for homophilic datasets and small-scale heterophilic datasets with sparse edges; (2) A larger $K$ value is suitable for large-scale heterophilic datasets and heterophilic datasets with dense edges. Similar observations can be obtained for Fourier terms ($M$), too.\n\n> **Questions #1** How does GrokFormer handle dynamic graphs where the topology changes over time?\n\nLike most competing methods, GrokFormer is designed for static graphs. Dynamic graphs, where the topology evolves over time, are not applicable in the current setting of these methods. We plan to extend GrokFormer to dynamic graphs in our future work.", "claims_and_evidence": "The paper makes several claims:\n\nExpressiveness of GrokFormer Filters: The authors claim that GrokFormer filters are more expressive than existing spectral methods due to their spectrum- and order-adaptive capabilities. This is supported by theoretical proofs (e.g., Propositions 4.1–4.4) and empirical results on synthetic datasets, where GrokFormer outperforms others in fitting complex filters like comb and low-comb patterns.\n\nSuperiority in Real-World Tasks: GrokFormer achieves state-of-the-art performance on 10 node classification datasets and 5 graph classification datasets, outperforming both GNNs and GTs. For example, it achieves the highest accuracy on heterophilic datasets like Squirrel, where complex frequency responses are crucial.\n\nEfficiency: The model is computationally efficient compared to alternatives like Specformer, as demonstrated by empirical time and memory complexity analyses.", "methods_and_evaluation_criteria": "The methods proposed align well with the problem of capturing diverse frequency signals in graphs:\n\nThe use of Fourier series for filter modeling ensures flexibility across spectral frequencies.\n\nThe evaluation includes a wide range of datasets with varying properties (homophilic and heterophilic), ensuring robustness.\n\nBaselines include both spatial-based GNNs (e.g., GCN, GAT) and spectral-based GTs (e.g., Specformer), providing a comprehensive comparison.", "theoretical_claims": "The theoretical claims are supported by detailed proofs:\n\nProposition 4.1 shows the learnability of GrokFormer filters in both polynomial order and spectrum.\n\nProposition 4.2 demonstrates that polynomial filters used in existing methods are special cases of GrokFormer filters.\n\nProposition 4.3 establishes that Specformer is a simplified variant of GrokFormer.\n\nProposition 4.4 proves the universal approximation capability of GrokFormer filters using Fourier series.", "experimental_designs_or_analyses": "The experimental design is sound:\n\nExperiments cover diverse datasets with varying scales, homophily levels, and graph properties.\n\nAblation studies isolate the contributions of key components (e.g., self-attention vs. Graph Fourier KAN).\n\nScalability tests demonstrate the model's efficiency on large graphs.\n\nHowever, further exploration of hyperparameter sensitivity could enhance the robustness of conclusions.", "relation_to_broader_scientific_literature": "The paper builds on prior work in GNNs (e.g., ChebyNet, GPRGNN) and GTs (e.g., Specformer). It advances the field by addressing limitations in spectrum adaptability (Specformer) and order adaptability (polynomial GNNs). The use of Fourier series aligns with established theories in approximation and signal processing.", "essential_references_not_discussed": "The paper appears comprehensive in its citations but could benefit from discussing recent advancements in scalable spectral methods or alternative transformer architectures that address similar challenges.", "other_strengths_and_weaknesses": "Strengths:\n\nOriginal combination of Fourier series modeling with Transformer architecture.\n\nComprehensive theoretical analysis supporting empirical findings.\n\nStrong performance across diverse datasets.\n\nWeaknesses:\n\nLimited discussion on potential limitations or failure cases.\n\nScalability could be further improved by avoiding spectral decomposition altogether.", "other_comments_or_suggestions": "Clarify how hyperparameters like K (order) affect performance across different datasets.\n\nInclude runtime comparisons on larger-scale graphs beyond Penn94 for broader scalability insights.", "questions_for_authors": "How does GrokFormer handle dynamic graphs where the topology changes over time?\n\nCan the model's efficiency be improved further by avoiding spectral decomposition entirely?\n\nHow sensitive is the performance to hyperparameters like K or the number of Fourier terms (M)?", "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": "", "extra_scores": {}}, {"review_id": "MNbDUY3AUh", "reviewer": "Reviewer_n2Go", "summary": "This paper proposes GrokFormer, a Transformer-based graph spectral model that introduces the expressive graph filter to the Transformer architecture, effectively capturing a wide range of frequency signals in an order- and spectrum-adaptive manner. Experiments on synthetic and real-world datasets show the effectiveness of the proposed method.\n\n## update after rebuttal\n\nThe authors' responses have addressed my concerns. Hence, I'd like to keep my original score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive and positive comments on methodology and experiment designs. Please see our response to your comments one by one below.\n\n>**Weakness #1** The time consumption of preprocessing should be included in Table 8, and whether the proposed method achieves a trade-off between computational cost and expressiveness.\n\nThanks for your valuable suggestion. Following your suggestions, we measured the computational overhead (including preprocessing) on the small-scale dataset Squirrel and the large-scale dataset Penn94, with the results summarized in Table A1 below.\n\n```\nTable A1. The computational cost in terms of GPU memory required in MB, training runtime, and pre-processing time (s) on two datasets.\n```\n| Dataset|Methods |Memory (MB)|Forward Times (s)|  Decomposition Time (s)|\n| --- | --- | --- | --- |---|\n|Squirrel|PolyFormer| 8678|42.38|/|\n||Specformer| 1951|6.45|3.26|\n||GrokFormer|1424|6.12|3.26|\n|Penn94|PolyFormer| 14113|121.78|33.14|\n||Specformer| 5053|9.39|746.32|\n||GrokFormer|4647|8.13|746.32|\n\nIt is clear that our GrokFormer and Specformer are comparably fast, both of which requires much less computational cost than PolyFormer. Additionally, accuracy results of node classification on Squirrel show that spectral decomposition methods, such as GrokFormer and SpecFormer, achieve approximately a 20\\% improvement over the polynomial filtering model PolyFormer. On the large-scale graph dataset Penn94, while preprocessing takes some time, the forward-pass complexity can be reduced using truncated spectral decomposition. Moreover, since spectral decomposition is computed only once and reused during training, its cost becomes a minor one compared to the forward-pass cost when training for many iterations.\n\n>**Weakness #2 and Question #1** Clarification from the authors about some guidelines to selecting order $K$ could be helpful.\n\nPlease see our detailed response to ***Reviewer Cg7z’s Suggestion #1 and Question #3***, where we clarified the concern regarding the selection about filter order $K$.\n\n>**Weakness #3**  A deeper discussion between GrokFormer, PolyFormer, and Specformer should be included.\n\nSpecformer designs a learnable filter by performing self-attention on each eigenvalue (spectrum), which is a spectrum-adaptive spectral method. PolyFormer designs an adaptive filter by performing self-attention on $K$ bases with fixed filter order. Different from these two methods, GrokFormer meticulously designs a universal order- and spectrum-adaptive filter within a Transformer architecture to capture diverse frequency components in graphs. We will add this comparison in the related work section.\n\n>**Question #2** How to understand the benefits of the higher-order filter base?\n\nHigher-order filter bases can result in the following two benefits: (1) enrich the spectral representation through additional frequency components, and (2) strengthen the approximation power. These advantages facilitate more accurate signal distribution modeling in diverse graphs of various complexities. Our method leverages these advantages through an adaptive order selection mechanism that dynamically optimizes filter orders for datasets with varying properties, achieving large performance improvement over existing SOTA filters, e.g., achieving 21\\% improvement over the baseline PolyFormer with fixed-order filter bases on the Squirrel dataset.", "claims_and_evidence": "Yes. The authors conduct extensive experiments on synthetic and real-world datasets. And the experimental results demonstrate that GrokFormer can learn an expressive filter and outperform baselines on node-level and graph-level tasks.", "methods_and_evaluation_criteria": "Yes. The evaluation criteria in this paper follows the same setting in previous methods.", "theoretical_claims": "The authors provide theoretical analysis and empirical evidence, showing the improved flexibility and expressivity of the GrokFormer filter over Specformer and Polynomial filters, which seems sound to me.", "experimental_designs_or_analyses": "I think the designs of experiments are reasonable.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. The motivation is reasonable and the idea is easy-to-follow.\n\n2. The paper develops a new graph Transformer that introduces a novel graph spectral filter learning approach in the Transformer architecture, which effectively capture a wide range of frequency signals in an order- and spectrum-adaptive manner.\n\n3. Comprehensive experiments are convincing in my opinion.\n\n4. The paper is clearly organized and well-written. \n\nWeaknesses：\n\n1.\tThe eigenvalue decomposition brings significant computational costs compared to polynomial paradigm. The authors are suggested to include the time consumption of preprocessing in Table 8, and demonstrate whether the proposed method achieves a trade-off between computational cost and expressiveness.\n\n2.\tClarification from the authors about some guidelines to selecting order K could be helpful.\n\n3.\tThe authors are encouraged to include a deeper discussion between GrokFormer, PolyFormer and Specformer,  as they are all spectral graph transformer methods.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. In Figures 4 and 7, as the order K increases, the performance on some datasets appears to change only marginally. Alternatively, clarification from the authors about some guidelines to selecting order K could be helpful.\n\n2. How to understand the benifits of higher-order filter bases in Eq. (6) ?", "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": "", "extra_scores": {}}, {"review_id": "ChTzeUlYh6", "reviewer": "Reviewer_tPj2", "summary": "This paper propose to introduce a novel Kolmogorov-Arnold networks (KAN) based spectral filters to graph Transformer framework to enhance the flexibility to perform low/high/band-pass filtering.\nCompared to the previous polynomial spectral graph neural networks (GNNs) as well as the proposed graph KAN spectral filter has orthogonal polynomial bases, better convergence as well as global graph modeling.\nCompared to the non-polynomial spectral GNNs, Specformer, the proposed spectral filter can consider the higher-order of the eigenvalues in an explicit manner, leading to more flexible construction.\nThe authors also show empirically that adding an linear-attention module to the spectral filters can lead to better empirical performance.\n\n\n## update after rebuttal\n\nI have updated the scores according to the rebuttal of the authors. Details please see the rebuttal comments", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your constructive and positive comments on the filter design. Please see our response to your comments one by one below.\n\n>**Question #1** In Specformer, MLP applied to each eigenvalue $\\lambda$, which can learn to output for $\\lambda^k$ theoretically.\n\nWe appreciate your insightful comment. While applying MLP to $\\lambda$ in Specformer can help theoretically capture frequency information about $\\lambda^k$, it does not necessarily enable the MLP in Specformer to effectively model spectral information across arbitrary filter orders $k$ due to its limited parameters and the lack of explicit learning for unknown $\\lambda^k$. In contrast, our GrokFormer explicitly captures a diverse range of frequencies across different filter orders, ensuring a more expressive representation in the spectral domain.\n\n>**Question #2** In multi-head attention, the residual connection might generate band/high-pass filters.\n\nWe really appreciate your comments. We'd like to clarify that [Ref1] has shown that *although multi-head, FFN, and skip connection all help preserve the high-frequency signals, none would change the fact that MSA block as a whole only possesses the representational power of low-pass filters* (see page 5 of [Ref1]).  The theory is further supported by the experiments on the ZINC dataset in [Ref2]. These findings confirm that Transformer is essentially a low-pass filter, motivating our development of expressive spectral filters for graph Transformers.\n\n- [Ref1] Anti-Oversmoothing in Deep Vision Transformers via the Fourier Domain Analysis: From Theory to Practice. ICLR, 2022.\n\n- [Ref2] How Expressive are Transformers in Spectral Domain for Graphs?  TMLR, 2022\n\n>**Question #3** How necessary for the attention modules in the work? (Lack of statistical analysis from t-test).  \n\nIn Table A1, we include a new dataset, Penn94 in ablation study and report the $p$-Value using t-tests on all datasets.\n\n```\nTable A1. Additional ablation study on Penn94.\n```\n| |Penn94|$p$-Value|\n| --- | --- | --- |\n|Self-attention-E|76.29|0.001|\n|Graph Fourier KAN|81.36|0.002|\n|GrokFormer|83.59|-|\n\nSelf-attention-E can generally capture global spatial relationships, preserving the similarity of node features.  However, on the large-scale dataset penn94 with a low homophily level, relying solely on spectral information from Graph Fourier KAN may not be sufficient.  Only when both Graph Fourier KAN and self-attention are integrated, GrokFormer can achieve consistently improved performance, with statistically significant differences ($p$ < 0.05) on the ablated GrokFormer models. This demonstrates that our GrokFormer is more than just a simple combination of self-attention and Graph Fourier KAN.\n\n>**Question #4** The theoretical discussion of strong expressivity on WL test.\n\nPlease see our detailed response to Reviewer axD1's Weakness #3.\n\n>**Question #5** and **Question #6** Some expressive graph Transformers like GraphGPS and GRIT are overlooked in comparisons.\n\nPlease see our detailed response to Reviewer axD1's Weakness #1 and #2.\n\n>**Question #7** The filter fitting experiments do not include graph Transformers in comparisons.\n\nBoth Polyformer and Specformer design filter functions h($\\lambda$) in the spectral domain, which can be regarded as spectral graph Transformers based on a Transformer architecture. Besides Specformer, we added the Polyformer in filter fitting experiments to further verify the learning capability of our filter.  Please refer to Table A3 in our response to Reviewer axD1's Weakness #4.\n\n>**Question #8**  'order-adaptive' and 'spectrum-adaptive' are vague. The term 'graph order' is used mistakenly.\n\nWe would like to clarify the \"order-adaptive\" in this paper is actually 'filter order-adaptive' in the spectral domain, rather than the spatial-domain order or 'graph order'.  It refers to using the $k$-power of eigenvalues to approximate filters, analogous to polynomial filter approximation in the spectral domain. 'spectrum-adaptive' indicates that a full (or subset of) spectrum (eigenvalues) is used to approximate spectral filters, similar to the ability of the filter in Specformer. We will give a clear description to avoid the misunderstanding in our final version.\n\n>**Question #9**  Complexity claim\n\nThe overall forward complexity of GrokFormer is $O(N(Nq+d^2)+KqM)$, where we have $q=N$ on small-scale datasets. It is lower than that of related methods, e.g., Specformer with a complexity of $O(N^2(q+d)+Nd^2)$.\n\n>**Question #10** Why not use full (regular) self-attention?\n\nWe replaced linear self-attention with regular attention (G-Reg) and conducted experiments, which show that both achieve comparable performance (Table A2), as they both capture non-local spatial features. We chose linear attention for its better efficiency.\n\n```\nTable A2. Accuracy comparison on attention type.\n```\n| | Cora |Squirrel |Actor| \n| --- | --- | --- | --- | \n|G-Reg|89.43| 65.32|42.75|\n|GrokFormer |89.57| 65.12|42.98|", "claims_and_evidence": "1. The authors claim that Specformer cannot consider spectrum at different orders while the proposed method can.\n- This is not well justified since in Specformer, there are MLP applied to each eigenvalue $\\lambda_i$ which can learn to output $\\lambda_i^k$ for $k>0$ theoretically, given by the universality of MLP. Therefore, this claim is problematic.\n\n\n2. The authors claim that self-attention preserves only low-frequency signals in graph features in abstract. \n- This is not well supported. It is true that each attention map is equivalent to a low-pass filter. However, in multi-head attentions, a linear combinations of different low-pass filters and all-pass filters (i.e., residual connection) might generate band/high-pass filters. \n\n\n3. The authors claim to propose a novel graph Transformers, which is more flexible and expressive.\n- First, the proposed networks is more like a spectral GNNs plus a linear-attention. The \"transformer\" component is not well justified. (The differences with/without attention in the ablation studies are not even staistically significant from T-test).\n- There is no theoretical and empirical support that the proposed model is more expressive than the recent graph Transformers such as GraphGPS (Rampasek et al., 2022), GD-Graphormer (Zhang et al., 2023), GRIT (Ma et al., 2023).\n- In the baselines, there are some graph Transformers known for better scalability but not on top of the expressivity. The comparison to them cannot support the claim on stronger expressivity.\n- Stronger ability to generate filters of different frequencies does not necessary lead to stronger expressivity on distinguish different graph-structure. Wang et al., (2022) shows that the expressivity of polynomial spectral GNNs are not more expressive than 1-WL. CKGConv (Ma et al., 2024), shows that applying non-linearity transformation on the polynomial bases can lead to stronger expressivity beyond 1-WL. There are no similar discussion in the paper to support the statement of \"more expressive\"\n\n\n\n-------------- \n> only the references not included in the paper are listed\n\n\n- Zhang, Bohang, et al. \"Rethinking the Expressive Power of GNNs via Graph Biconnectivity.\" The Eleventh International Conference on Learning Representations.\n- Ma, Liheng, et al. \"Graph inductive biases in transformers without message passing.\" International Conference on Machine Learning. PMLR, 2023.\n- Wang, Xiyuan, and Muhan Zhang. \"How powerful are spectral graph neural networks.\" International conference on machine learning. PMLR, 2022.\n- Ma, Liheng, et al. \"CKGConv: General Graph Convolution with Continuous Kernels.\" International Conference on Machine Learning. PMLR, 2024.", "methods_and_evaluation_criteria": "1. The datasets utilized are known for the lack of training examples, which are less suitable to evaluate the capacity of complicated models such as graph Transformers. The overfitting issues might dominate the performance improvements. These datasets can justify that the proposed method introduce better inductive bias. However, using these datasets only cannot well support the capacity statement of the proposed GrokFormer.\n\n2. In the literature of graph Transformers, the datasets from BenchmarkingGNNs (Dwivedi et al., 2023) and Long Range Graph Benchmarks (Dwivedi et al., 2022) are more widely used to evaulate the capacity and expressivity of the graph models. (They have been shown more effeictive to evaluate the ability of modeling graph-structure compared to TU datasets). However, the paper does not utilize those datasets and weaken the experimental conclusions.\n\n3. The proposed method claims that the proposed spectral filter can introduce the stronger capacity to graph Transformers.\nHowever, the compared graph Transformers are more known for better scalability instead of stronger expressivity.\n Most existing expressive graph Transformers are ignored in the comparison, including but limited to GraphGPS (Rampasek et al., 2022), GD-Graphormer (Zhang et al., 2023), GRIT (Ma et al., 2023).  (listed in previous section) Epesicallly for GraphGPS and GRIT, the former one is also hybrid Transformer architecture (MPNN+self-attention) and the latter one reach SOTA performance on various datasets with pure Transformer architecture.\n\n4. The filter fitting experiments does not include graph Transformers in comparisons.", "theoretical_claims": "1. Listed in the (1) of **Claims And Evidence**\n2. The Complexity claim has some issues.\n- When consider the full spectrum ($N$ eigenvalues/eigenvectors), the forward pass of the proposed method is actually $O(N^3)$ ($O(N^2 M)$ with $M=N$) on eq. (8), which is missed in the calculation of the overall forward complexity.\n3. In table 1, there are two properties 'order-adaptive' and 'spectrum-adaptive'. These properties are actually vague. They are viewed as positive feature of the work without clear definition and support.\n- In Polynomial Spectral GNNs, the *order-adaptive* is referred to the polynomial approximation to the full spectrum, which is an approximation from the spatial domain. This is a trade-off between the flexibility and the computational cost.\n- In Specformer, the *spectrum-adaptive* is referred to the usage of a subset of spectrums (eigenvalues), which is an approximation from the spectral domain. \n- In Graph KAN spectral filter, *order-adaptive* is referred to the usage of the $k$-power of eigenvalues. However, this is different from the *order-adaptive* in Polynomial Spectral GNNs and can neither lead to better computational cost nor leading to a tighter approximation.\n- In fact, it is arguably that the proposed KAN-based spectral filter can be well approximated by the transformer-based spectral filter in the specformer due to the universal approximation. (However, the performance might be different in practical training).", "experimental_designs_or_analyses": "1. The ablation study cannot well justify the necessary of the efficient self-attention. \n- the performance difference between the graph Fourier KAN and Full model is not statisically significant, indiciating that the efficient-self-attention is not necessary. \n- consider using other datasets with stronger distinguishability on the model capacity.", "relation_to_broader_scientific_literature": "1. The proposed method does not provide key contribution to the literature of graph Transformers as well as Transformers. This unmatch the main statement of the paper.\n2. The key contribution of the proposed method is proposing a novel parameterization of the graph spectral filters and spectral GNNs, which endows with several desired properties.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Weaknesses**\n\n1. The proposal of the graph Fourier KAN spectral filters are novel and interesting. However, the injection of efficient self-attention is not well supported, which in fact weaken the paper. A simple A+B technique combination without good motivation and theoretical/empirical support  lead to a negative viewpoint.\n\n2. No expressivity discussion on the proposed method.", "other_comments_or_suggestions": "1. In graph theory, the term ``graph order'' is widely used, which stands for the number of nodes in a graph. This work uses this term mistakenly.\n\n2. Arguably speaking, Specformer (Bo et al., 2023) shall be considered as a spectral GNNs with Transformer/self-attention encoders rather than graph Transformers, which are supposed to learn graph-structure data directly with Transformer architecture (self-attention + FFN).", "questions_for_authors": "1. The method seems to focus on the capacity and expressivity of the model. Why not use full self-attention? What is the main goal of using the linear-attention which is theoretically weaker than the regular self-attention.\n2. How necessary for the attention modules in the work?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents GrokFormer, a novel Graph Transformer that leverages adaptive spectral filters via Fourier series modeling to address limitations in capturing diverse frequency signals in graph data. The reviewers highlight its theoretical contributions, including proofs of expressiveness and flexibility, as well as strong empirical performance across 10 node and 5 graph classification datasets. While some reviewers initially raised concerns about comparisons with expressive graph Transformers (e.g., GRIT, GraphGPS) and the clarity of "adaptivity," the authors' rebuttal addressed these issues by adding experiments on challenging benchmarks (e.g., ZINC, SP-CIFAR) and clarifying terminology. The method's ability to balance generalization and expressiveness, particularly on heterophilic graphs, was noted as a strength. Although scalability and dynamic graph handling remain future work, the consensus leans toward acceptance due to the paper's solid theoretical grounding, comprehensive evaluations, and rebuttal improvements. Given its contributions to spectral graph learning and Transformer architectures, we recommend acceptance with the expectation that the authors incorporate the suggested revisions (e.g., expanded discussions on expressivity and dataset comparisons) in the final version.
Decision: Accept (poster)