Restricted Global-Aware Graph Filters Bridging GNNs and Transformer for Node Classification
Authors: Jingyuan Zhang
Xin Wang
Lei Yu
Zhirong Huang
Li Yang
Fengjun Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Graph Transformer
Graph Neural Networks
Graph Filter
Node Classification
Primary area: deep_learning
TL;DR: Transformers fall short of surpassing the performance ceiling of GNNs, but introducing appropriate constraints can effectively enhance the generalization of GNNs.

Abstract: Transformers have been widely regarded as a promising direction for breaking through the performance bottlenecks of Graph Neural Networks (GNNs), primarily due to their global receptive fields. However, a recent empirical study suggests that tuned classical GNNs can match or even outperform state-of-the-art Graph Transformers (GTs) on standard node classification benchmarks. Motivated by this fact, we deconstruct several representative GTs to examine how global attention components influence node representations. We find that the global attention module does not provide significant performance gains and may even exacerbate test error oscillations. Consequently, we consider that the Transformer is barely able to learn connectivity patterns that meaningfully complement the original graph topology. Interestingly, we further observe that mitigating such oscillations enables the Transformer to improve generalization in GNNs. In a nutshell, we reinterpret the Transformer through the lens of graph spectrum and reformulate it as a global-aware graph filter with band-pass characteristics and linear complexity. This unique perspective introduces multi-channel filtering constraints that effectively suppress test error oscillations. Extensive experiments (17 homophilous, heterophilous graphs) provide comprehensive empirical evidence for our perspective. This work clarifies the role of Transformers in GNNs and suggests that advancing modern GNN research may still require a return to the graph itself.

Restricted Global-Aware Graph Filters Bridging GNNs and Transformer for Node Classification
Jingyuan Zhang!2 Xin Wang Lei Yu
Zhirong Huang
Li Yang!." Fengjun Zhang
Institute of Software, Chinese Academy of Sciences
University of Chinese Academy Sciences
{zhangj ingyuan2023, wangxin, yulei2022, toangzhhirong2222)diicco {yangli2017, @iscas. ac.
Abstract
Transformers have been widely regarded as promising direction for breaking through the performance bottlenecks Graph Neural Networks (GNNs), primarily due to their global receptive fields. However, recent empirical study suggests that tuned classical GNNs can match or even outperform state-of-the-ar Graph Transformers (GTs) standard node classification benchmarks. Motivated by this fact, deconstruct several representative GTs to examine how global attention components influence node representations. We find that the global attention module does not provide significant performance gains and may even exacerbate test error oscillations. Consequently, we consider that the Transformer is barely able to learn connectivity patterns that meaningfully complement the original graph topolegy. Interestingly, we further observe that mitigating such oscillations enables the Transformer to improve generalization in GNNs. a nutshell, we reinterpret the Transformer through the lens of graph spectrum and reformulate it global- aware graph filter with band-pass characteristics and linear complexity. This unique perspective introduces multi-channel filtering constraints that effectively suppress test error oscillations. Extensive experiments (17 homophilous, heterophilous graphs) provide comprehensive empirical evidence for our perspective. This work clarifies the role of Transformers GNNs and suggests that advancing modern GNN research may still require return to the graph itself.
Introduction
Graph Neural Networks (GNNs) 20 26 57
64 67 have demonstrated powerful modeling capabilities on graph-structured data and have been widely applied various tasks [6
such node classification. Most existing GNNs follow a message-passing paradigm [18] where messages are exchanged between a target node and its neighbors integrate node features with graph topology, exhibiting strong spatial locality. Naturally, this local message exchange has raised concerns about the lack of global awareness, which often viewed as a performance bottleneck for GNNs. To address this limitation, some studies [42 40 have explored incorporating Transformers into graph learning, giving rise Graph Transformers (GTs). However, it is unclear what extent. Transformers enhance GNNs.
60 44
In the literature, research on GTs has evolved through three distinct stages: (i) Expressive Power: In the early stage, GT's primarily leveraged the attention mechanism in Transformers [56) to establish global receptive fields, alleviating the limitations on expressive power caused by over wer-shoothing [0
[] and over-squashing [4]. To enhance model expressiveness, various forms of positional encoding
CCorresoonding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(PE, including Laplacian spectral encoding 4 28
learnable spectral encoding [13]. and both global or structural encoding (SE, including node degree centrality [66].
and local positional encoding
node subgraph representations 6 pairwise distance and path encoding [70], and random walk-hased
encoding (37].) were introduced, (ii) Scalability. GTs have shown promising encoding capabilities in comparison to GNNs. However, the computational complexity of GNNs typically scales linearly
with the number of edges (O))E)), whereas GT's generally incur a quadratic complexity (O(V))) due to the computation of attention score matrices. This prompted the development of linear or sparse GTs [TO 699 27 61]. Recent advances have shown that state-of-the-ar GT's can strike balance between expressivity and efficiency. For example, [63] achieves competitive performance with a single-layer global attention network of linear complexity. [3] combines high-order polynomial expressiveness with linear computational complexity.
S3 adopts a two-stage process to further sparsify the attention mechanism, thereby reducing memory overhead. (iii) Effectiveness (Actual Gains), At this stage, GTs appear to be relatively mature. However, a recent empirical study [36] cast doubt on their actual benefits, showing that fine-tuned classical GNNs can perform on par with or even surpass the SOTA GTs. This finding challenges the fundamental premise of GT's research: Does the Transformer truly enhance the performance of GNNs? As there currently no definitive answer, the field faces significant challenges that warrant deeper reflection.
In this work, we argue that Transformers may empirically boost the performance upper bound of GNNs, but they can serve as regularization components to enhance generalization of GNNs. This conclusion stems from a unique perspective on understanding Transformers. Prior efforts largely inherit the standard Transformer framework (i.e., the QK V paradigm), employing attention either as a supplement graph topology or as a downstream encoder following GNNs. However, based on our experimental observations (as shown in Figure T.. the former often introduces substantial topological noise, where redundant global signals contribute little to optimization or generalization. As for the latter, building upon the upstream GNN results, the Transformer merely re-encodes already- captured information, limiting its effectiveness. From the lens of GNNs, Transformer can be seen as learning a new shift operator over complete graph (i.e.. the attention matrix) and applying it for low-pass filtering (i.e., neighbor aggregation). If key inductive biases lie in localized structures, this relaxed low-pass channel setting may lead to a form of representational "laziness" in the attention mechanism. Enforcing sparsity attention to contain such locality theoretically appealing, but computing the full QK remains costly. Therefore, our focus naturally shifts to diversifying the filtering channels, offering a new path for bridging GNNs and Transformers.
Based on the above analysis, we innovatively extend the Transformer into a band-pass global-aware graph filter Elter--oe Former, departing from the conventional cascade fashion. The band-pass property allows the Transformer to adaptively learn graph spectrum determined by the graph topology under different channels. This channel diversity encourages the attention mechanism to move beyond pure similarity modeling between node pairs, thus exerting a certain regularization to facilitate better generalization for GNNs. The details are as follows:
Rather than advocating naive combination of GNNs and Transformers, we propose Former, structurally extended architecture from the perspective of graph signal processing. Under multi- channels, G*Former induces Transformers to generate guided noise that enhances node features, thereby benefiting the inference of downstream GNNs. This constitutes a novel global-to-loce framework that effectively addresses the aforementioned "laziness" issue. GoFormer theoretically supports band-pass filtering at arbitrary frequency bands, thereby satisfying constraint requirements and adapting to diverse graph structures. Attention mechanism enables a node feature- driven and learnable graph spectrum, challenging the traditional view of topology as a fixed prior in graph filtering. We design and discuss two channel initialization strategies to highlight the importance of channel constraints. And G2 Former retains linear computational complexity.
Extensive experiments on 17 datasets of real-world node classification covering homophilous, heterophilous, and large-scale graphs with millions of nodes demonstrate our claims. We hope this work helps break the current dilemma in GT's research and revisit the positioning of Transformers for the field. Our code is available at htttps://ggthuu: com wtmm/hhansstarr/// F-22orrree
2 Background
This section presents preliminaries in two relevant areas: Transformers and graph filtering.
2

---

30.
25-
Saferar Text
Faysmer
SOPA Tuln
Nypammuu Tul
SoPertitonn Tran
Felrermetin Trsh
115
10-
50
300
100
100
360
650
502
de
25
50
180
125
154
25
10c
(a)
(b)
(c)
(d)
2.5
Saliomar- Trai
Kcheaman Tean
scieeer Schemer- Tei
Folyererr Fan
2.04
MAW
Polrermer Ted
on
Sau Text
Sofereeso -To
5
Pavrermtion
303
230
502
265 $000
500
230
420
900
(e)
(f)
(h)
volureer Tel
Poynoree ne Tran
voburver lad
32famiran Trih
Fely soriiiee Iran
aoformtan Trsh
Fubyromation Than
8
104
203
690
sio
1050
520
1033
1570
2030
100
260
303 41c
269
650
803
1902
(i)
(i)
(k)
(I)
Figure 1: SGFormer [63] and Polynormer [13] correspond to two distinct GT architectures: local-and- global and local-to-llobl,, respectively. We report their training and test cross-entropy losses across various datasets. SGFormer.ONN retains only the fine-tuned GCN backbone, while Polynormer.oww keeps only its local attention mechanism (which is GNN-like), (a)-(f) correspond to homophilous graphs, and (I)-() to heterophilous graphs. These two GT's fail to provide significant test improve- ments for their GNNs and even underperform compared to standalone GNNs on some datasets.
Transformers. For general self-attention Transformer architecture [56], each layer computes attention scores between every pair of samples, yielding an attention coefficient matrix. This matrix then used to linearly reconstruct the sample features and update the representation the current layer. For example, given a sample feature matrix X E RRn the self-attention can be computed in the following two ways:
QKT
V X' (Q)))()) (Q(((()
X' soflmax(
Vd
where Q = XWQ, K = XW = XWy v are the query, key and value matrices. We E Raxd", Wx E Raddd, Wv E Rdxd' are trainable matrices, 1 E Raxi is an all-one vector, and the sigmoid function. The first equation is the commonly used explicit computation of the self-attention coefficient matrix, but it is computationally expensive, requiring ((n2) operations. The second equation is a lincar attention (25) formulation. which leverages simple kernel trick to reorder the computation and reduce the complexity to (n)). Division by o (() ensures that each row of the attention matrix sums to I. GTs typically integrate the graph adjacency matrix with the attention matrix, or apply graph convolution before feeding the features into the Transformer.
Graph Filtering. For an undirected attributed graph 9 = V, X), V. are the sets of edges and nodes, X is the node attribute matrix. Let A be the adjacency matrix of G, the symmetric normalized Laplacian L D 1/2 (D- A)D - 1/2, , D is the degree matrix of A. Perform the eigenvalue decomposition on L, i.e. L = UAU - U is the eigenvector matrix, A diag([)ı, X2, .... An]). A; is i-th eigenvalue of L. 0 λ1 < A2 < An < 2. Assume that x E xx is signal of G, g(A) is the frequency response function, the graph filtering can be formulated as:
F(L)x = F[()x-U((AJU',
UTx. A; indicates the frequency magnitude of the graph Fourier basis U, designed g( A) is applied to amplify or suppress corresponding frequency components, and the signal is then mapped back to
First, transform x into the spectral domain via the graph Fourier transform 49 x
3

---

the spatial domain via the inverse graph Fourier transform UX to complete the filtering process. F(L) is referred to as the graph filter 45]. Combining multiple distinct designed F(L) enables filterin..
multi-channel 54 or mixed-channel
3 Methodology
In this section, we provide detailed explanation of the proposed method. In Section 3.1 we describe how Transformer is extended into a global-aware graph filter with band-pass characteristics, along with two different strategies for channel initialization. In Section 3.2 present the method for generating guided noisy samples from multiple channels and performing graph-guided filtering to enhance node features for downstream GNN training or inference. Finally, we introduce the GoFormer framework, its optimization objective, and provide theoretical analysis (including the computational complexity) in Section 3.3
an3 and 3.4
3.1 Global-Aware Graph Filters
As shown Equation I self-attention can be viewed form of topology reconstruction (graph structure learning) followed by message passing over the updated topology. From the perspective of GNNs, the behaviors of both are highly similar. To address the "laziness" that arises when combining it with GNNs and to fully leverage their global receptive field, we develop the band-pass property
of the Transformer. We follow the common setting of Section that denote Q¹
|[a()).ll, K
a(Q),
(K)) I. Q' E mand K' E Baxd' a is the sigmoid function. Let As Q'K if Q' and K' 20
do not share parameters, As 1 QQ'" K'Q" ensuring that Ag is symmetric matrix.
Similarly, Ls D
s 1/2 (Ds As) 1/2 Ds is the degree matrix of As. We define a band-pass
global-aware graph filter as follows:
F(Ls;a,3,0) = (21) Ls)
(2I) Lg)
So (A)dA
S (2 -)
where θ (WQ: Wk]. I is the identity matrix, (s()) is the frequeney response function of ( Lg) a, 3 E N are the band control coefficients. θ enables the filter to adaptively learn the graph topology, thereby adjusting the graph spectrum. f gs (A)dA represents the area under the curve of (>),,, acting as normalization term for F(Ls; a. B, θ) to prevent numerical explosion due to over-amplification, it can be written as:
S [xx12-x)axx da 2 2 1 (
2 X dd. )a
(4)
2
Let A/2 = t, can be rewritten as:
sdd 2 2a+s+1 / f
2
2a 28
(1-1 ttt
-
(5)
Note that fo (a(1 dt at is the Beta function B(a + 1, + 1). According to the relationship 12 between the Beta function and the Gamma function I, we can get:
2 S.' E - = = 20+ T(a + 1)r(3 + +1) I(a + 3 2)
(6)
Hence, the final expression of the filter is:
a,0)) I 3 () (( Ls)
I(a + 1)l(3 + 1)2
where T(a 11 a!.
As is well known, Ls, 21- Ls correspond to high-pass and low-pass channels, respectively. Therefore, when B, F(Ls; a, B, θ) focus certain low- frequeeqencc range; conversely, it passes signals

---

X
A
A
GNN
X
FEN&
Projectors
Hapal
X
Greph-Gudkel Filtering
K
V
Projectors
K
X'
3
e S0oftmar(QK"" (QK
AH @ V.
Q'K
GNN
Q'KK" V)
(as) (12
H
H
Local-to-Global
Global-to Local (Ours)
(b)
Figure 2: The architecture of G2 Former and its comparison with previous works. The modules marked in orange contain learnable parameters. @ denotes the fusion of topological information with the self-attention mechanism. Att: self-attention computation. & represents the computation of Ls as described in Section 3.1 and C' corresponds to Equation 6
in certain high-frequency band. We can adjust the frequency band that the filter emphasizes by tuning a, B. For F(Lg; > 0, 0, θ) and F(Ls: 0, 8 > 0, θ), they are also high-pass and low-pass channels, respectively. In our implementation, two feedforward networks (FFNs), So, and Jag. are initialized. Specifically, fo, serves as a replacement for [Wo Q. Wx) } (Q = K So, (X)), while foz maps X into a latent space prior to filtering, and = {01, 02) now.
Channel Initialization. We introduce two channel initialization strategies: full-spectrum and low-spectrum (in Figure 3. We use
Prequency Response Function
Å to denote the pass-bant of a specific channel, and ( repre- sents the average frequency response within that channel. Assuming Athre = as the threshold, [o. 1] corresponds to the low-frequency band, while (1, represents the high-frequency band. The full- spectrum filter bank is denoted as (F(Ls; a + B - i, E (0....++333 and low-spectrum filter bank is i, θ) i E (0,.., a + }-}- In general, node classification tasks primar- ily rely low-frequency components, which may make the low- spectrum initialization sufficient without the need to incorporate high-frequency signals. However, such compromise can be detri- mental to attention mechanisms. Focusing solely on low-frequency signals may still lead to underconstrained behavior, whereas full- spectrum coverage provides a more principled solution. A detailed discussion can be found in Section 4.33
2-0.8-4
2.5
== 3,5
(a) full-spectrum Frequency Response Function
0=
2
g=4,0=4
3.2 Graph-Guided Filtering
(b) low-spectrum
Inspired by guided filtering 21, we attempt to use the graph filter introduced in Section 3.1 to generate guided noisy samples that en- hance the original node features and facilitate downstream GNNs training and inference. By adjusting a, 3, the guided noise en- compasses features from various channels (low-pass, high- or band-pass) and retains global perspective. This design aims to cir- cumvent model overfitting caused by a single relaxation channel. In the field of image processing, the guided filter is defined follows:
Figure 3: Frequency response
functions of the two channel initialization strategies (with max(a, 8)
as an exam- ple). The pass-band Ā of each channel is indicated by dashed lines and marked with penta- grams in corresponding col- ors.
/: a4 + bg, Vi E Wk-
(8)
This means that the filtered image q is linear transformation of the guidance (or guided noise) within a local window Wi. With reference to the above equation, we define graph filtering kernel as follows:
X = N, +
a, X,)X,, E [0, i 0, I,
(9)
5

---

where a, is the weight. In this case, the filtered attribute X' is the linearly weighted sum of the original attribute and the guided noise N. braph-guides filtering not determined solely by the guided noise; the incorporation of original features serves as a residual connection, which facilitates more effective model training. When a, 8 are fixed, the guided noise under different channel initialization strategies can be computed as follows:
at F(Ls; + (X) F(Lg;,, B,
N
(10)
The weight Rex1 in Equation 9 is provided by the model and is updated at each iteration. To obtain the wights, we initialize a predictor fo,, parameterized as a fully connected layer, a, = max(fe, (N,)) fa, is optimized by computing the loss with respect to the training labels, which differs from the way it is derived in Equation While traditional guided filtering minimizes the enror between the filtered and original images, our graph-guided filtering adaptively assigns weights based on the confidence of the guided noise. This filtering approach injects the guidance into X, balancing the correlation of the filtered result with both the original features and the guidance.
3.3 The G Former Architecture
This section presents the architecture followed by GoFormer and highlights its differences from previous works. Subsequently, we introduce the optimization objective of the model.
Global-to-Local Scheme. Previous GT architectures can be mainly categorized into two classes: Local-and-Global and Local-to-Global. As analyzed in Section [ propose Global-to-Lan
scheme. The "Global" component is placed upfront to generate guidance via the global graph filter bank, enabling graph-guided filtering. This is then followed by downstream "Local" encoding. Our design is orthogonal to the choice of downstream GNNs, allowing users to flexibly plug in various customized GNNs. At this stage, the Transformer generates guidance under the constraints of multiple channels, which distinguishes it from the conventional stacked or cascade encoding approach with GNNs. This design effectively improves the coordination between the two components. The detailed architecture is illustrated in Figure
Optimization Objective. In general, the optimization objective of typical GTs only involves the cross-entropy loss between the predicted probabilities and the ground-truth labels. In contrast, Former introduces additional cross-entropy loss term. As shown in Equation 9 obtaining the weight a for generating the guidance also requires supervision from the labels. We initialize separate predictor fe, (as mentioned in Section 3.2) for the final encoded representation GNN(X') and the guided noise N, respectively, to compute their corresponding loss terms. Let P = (GNN(X")) P' So, (N) the overall loss can be expressed as:
6- Σ Σ
Σ
Σ
Yo[k] In P((k),
(11)
VEVeracn
vEVerase
where Verain is the set of training nodes, Y E gaak is the ground truth label matrix, K denotes the number classes.
3.4 Theoretical Analysis
This section provides theoretical analysis of GrFormer, focusing on the filtering properties of the global-aware graph filter and the time complexity.
Theorem 3.1. Consider a > 0, 3 > O, when + cc, (F(Ls; a+3-i,, i (0..., +3} and [FLss; within the range (0, 2) and (0, 1), respectively.
i, a + 8, θ) i {0, a }}} are capable of covering any specific frequency band
The proof can be found in the Appendix A Theorem 3.1 highlights the strong capability of global- aware graph filters and underscores the importance of the hyperparameter a 3. An increase in a leads to greater diversity among filtering channels, which improves the quality of the guidance signals. Additionally, the shared use of the FFNs (i.e., for Sog) across more channels imposes stronger regularization on the Transformer and effectively prevents it from overfitting to limited number

---

Table 1: Comparison between our model and the baselines over homophilous graphs (%). The reported metric is Accuracy.
Cora
CiteSeer
PubMed
Computer
Photo
CS
Physies
WikiCS
GraphiGSS
83. 13.12
12.7
79.96.u.15
91.80
94.83
94,00
96.51 10:00
78.63
NAGphormer
80.35
70.12-150
80.02
91.65_015
12.12
95.81 19
97.33 10.11
77.95
EXphormer
83.22+1.55
71.88-1.1
+9.65
91.55=0m2
95.62+0.22
96.00
96.90
79. 79.26+000
GOAT
83,20
72.02
79.601061
92.32_042 0.42
94,43
93.72_ox
96.37
77.97
NodeFrrmer
82. 12.122200
72.27
80. 20.10
87. 47.12-048
93. 93,40
95.71=029
96.45
75. 15.15
SGFormer
84.72.0.7
72.70
80.6310.4
92.42_007
95.6010.35
95.75
96,701023
80. 80.10
Polynormer
83.33+0.89
72.20
79.12+n251
93.76-015
96.60+0.2
95.30-a20
97 97.20
80. 80.12+0.85
Spexphormer
83. 10
71.86_a86
79.33
91.12_0.1
95.35
94,90
96.71 1.030
78. 2.0777
GCN
84.564071
72.28
81.16
93.95-a15
96. 16.1220.50
96. 12
97.4444012
80.33
GraphSAGE
83,68 83,68+0.5
72.21
79.70
93.22-017
96.71
96,33-a15
97. 97.10
80,61
GAT
84,22
72.22
80.12
94.01 2011
96.6310.44
96.20
97.26
81.07 10.57
G.Former
83.72
72.62 003
79.30
94.29_aa
97.0610.10
96.53
97.60
g1.14
of channels. Nevertheless,
should not be excessively large. Beyond the risk of performance degradation due to over-regularization, redundant channels just incur additional computational cost. In line with Occam's Razor [2) the number of channels should be kept minimal yet sufficient. We
further discuss it in Appendix B.
Time Complexity. The main computational cost of Forrreer lies in the Transformer-based global graph filtering (i.e., Equation [0) and the downstream GNN encoding. is important to note that the computation must follow the linear attention computation order described in Equation T otherwise, its complexity would increase to ()D))). For example, Lsfe, (X) is equal to:
fe.(X) - D5 AsD5 1/2 fe, (X) = (X) - 1/2 (Q'("" (D5 fa, (X)))),
1/2
(12)
where Ds diag(Q) Q'K" 1)). So global graph filtering only needs O((a + BB V d) The complexity of the GNN is O(EE)). and with the additional cost of the feed-forward network (FNN) being ( dd'), the overall complexity of Foromeer is O(V) ((a + 3)dd² dd') + |ε]. Hence, Former still has linear complexity with respect to the number of nodes and edges.
Experiments
We conducted extensive evaluation experiments three types different real-world graph datasets (including homophilous, heterophilous and large graphs) to verify the effectiveness of G2 Former. Specifically, first evaluate the performance of Former these node classification datasets, addressing the question of whether Transformers can benefil GNNs. We conducted ablation studies on two types of channel initialization strategies and global attention module (including test error and visualization). In addition, we perform sensitivity analysis on the number of filtering channels in Appendix B.1 Finally, we report the training and inference cost of Fororrrr to demonstrate its scalability in Appendix B.2
Experimental Setup. Appendix C.I provides detailed statistics and splitting of the 17 standard datasets (8 homophilous, heterophilous and 3 large graphs). Note that for heterophilous datasets, the new version [46] of Chameleon and Squirrel, which removes overlapped nodes. The baselines mainly include 8 state-of-the-art GTs (GraphGPS [47), NAGphormer [7], EXphormer [52]
GOAT (27, NodeFormer (62). SGFormer 663 Polynormer
[3] and Spexphormer (53) and the
three well-tumed classic GNNs: GCN (26). GraphSAGE (0 and GAT [57]. Detailed descriptions
and hyperparameter configurations can be found in the Appendix C.
We use the official
implementations or public benchmarks (36) of baselines whenever possible. We follow (36) or their configurations tune the hyperparameters for better performance. We report the mean and standard deviation over five independent runs. The experimental environment details and the specific hyperparameter settings for G Former are also provided in the Appendix C.3 and Appendix
4.1 Performance on Diverse Graphs
Performance comparisons on homophilous, heterophilous, and large-scale graphs are presented in Tables I 2 and 3 respectively. The best and second-best results are highlighted in bold
7

---

Table 2: Comparison between our model and the baselines over heterophilous graphs (%). The reported metric is ROC-AUC for the Minesweeper and Questions and Accuracy for all others.
Squirrel
Chameleon
Amazon-Ratimn Ratings
Homann-Empite
Minesweeper
Questions
GraphGiPS
39.68420
41. 41.234339
53.33
82.45
90.66_0.8
72.33
NAGphormer
1..3
41.722461
51,42+0x8
74,49
85,03
68 11.45
EXphormer
39,80
39.13
53.34
89.13
90.38
74.01
GOAT
35.05
35.0615.77
45.1 10.59
71.88
81.88
75.80
NodeFormer
38.77
36.33
43.80
74.90_m.85
87.73
14.98
SGFormer
42.60.2240
44.3243911
54.04
80.10
91.43
73.83 0.069
Polynormer
42.05
41.88
54,96
92.5660.35
97.50
78.91 #0000
Spexphormer
40.33
40.30
10.77
83.03 00.69
90.73
73.02:10.76
GCN
4..03
44.91
53.82
91.23 _0,22
97.79
78.92
GraphSAGE
1..2
44.804453
55.14
91.02=00.1
97.73
77.20
GAT
41.81
44.221449
55.164021
90.41 10.17
97.75
77.90
Former
4..53
44,34
55.86
93.03
99,45
79.55
and underlined, respectively. On homophilous graphs, GoFormer improves the generalization performance of the best-performing GNNs by 0.16%-0.36%, and that of the best-performing Graph Transformers by 0.28%-1.27%. GNNs generally perform well on homophilous graphs, which can be attributed to the compatibility between their low-pass filtering nature and ho- mophily. Notably, SGFormer achieves the best performance on Cora, Citeseer, and PubMed, but performs poorly other real-world datasets. In contrast, Polynormer does not overfit to these three toy datasets and demonstrates relatively strong applicability among existing GTs. On heterophilous graphs, Former yields generalization improvements ranging from 0.51% to 1.7% over the best-performing GNNs, and from 0.51% to 6.88% over the best-performing GTss The advantage of Former particularly evident in heterophile graphs, which typically exhibit more complex connectivity patterns where the labels of neighboring nodes often differ from those of the cen- tral node. The global graph filter in Forormer exhibits band-pass characteristics, enabling it to capture both low and feggufre components on heterophilous graphs. In contrast, both GNNs and existing GTts are single-channel (i.e., low-pass only) and thus inca- pable of effectively capturing high-freen gighffreueecc signals. For large graphs, Fororeer provides generalization improvements ranging from 0.2% to 0.6% over the best-performing GNNs, and from 0.04% to 0.9% over the best-performing GT'. Its advantage remains more pronounced on heterophilous graphs. As the scale of heterophilous graphs increases, the performance gap among GTs also widens, which is closely related to the design of their attention modules. In such scenar- ios, the introduction of overly complex mechanisms may limit its applicability. Overall, G Former contributes better generalization in GNNs, yet it falls short of surpassing the inherent performance ceiling imposed by GNNs.
Table Comparison between our model and the basclines over large graphs (%). The reported metric is Accuracy. OOM means out of memory.
ogbn-ursiv
ogha-products
pokec
Type
Homophilous
Homophilous
Heterophiloes
GraphGPS
71.10a030
OOM
OOM
NAGphormer
70.90
74.33-025
76.10.2065
EXphormer
72.11 72.11
0OM
ODM
GOAT
12.81
82.29
72.50
67.66
74.10
71 21.00...30
SGFermer
72.42a042
81.66-1544
82 22.33
Polynormer Spexphormer
73.33
83.61
86.01
70.84
82. 82:10=as0
74.80
GCN
73.3 23.31
82.35=020
86 86:31
GraphSAGE GAT
73.05 1035.
Lives
85.90 pnz
g0.0
86. 12
Former
73.634025
83.98
86.81
4.2 Test-time Behavior of Attention Mechanism
This section investigates the encoding capacity of attention modules within GTs, this aspect that has been largely overlooked in prior work. To reveal the inherent differences, we remove the GNN component and train only the attention module for encoding. We compare the attention mechanisms of two top-performing GTS-SGFormer and Polynormer-and report their test errors after training, as shown in Figure In Figure abland and Figure/4d the regularization effect of Formerr's attention evident, effectively suppressing test error oscillations. Even more stable cases, Formerr'ss attention consistently maintains the lowest loss levels. This experiment demonstrates that under
8

---

Attention
Attertton "esting Loss over Wales
Alteriinn Testing Laso ondt atgrppoddzts
Vetire Roiigs
SGZ ormer
Safamee Pelytermer OPhommr
Sahoreer
2.2
3.-
Polynommr d'fermer
OPforner
Lo5e
2.4
206
416
100
2000
300
tio
260
Alo
1056
232
430
902
1392
1030 Epoch
1306
Epoch
Epoch
Epoch
(a)
(b)
(c)
Figure 4: A comparison of the test error behavior of the attention mechanism in G² Former versus those in the other two GT's.
Gramanoo
45
4000
Figure 5: Visualization of the attention mechanisms of the G2 Former,, SGFormer, and Polynormer, along with Polynormer-GNN and the corresponding label matrix.
multi-channel constraints, Formerr's attention can adapt to various types and scales of graphs, effectively avoiding the introduction of excessive detrimental topological noise into the GNN.
4.3 Channel Initialization Strategies
This section investigates the differences between the channel initialization strategies (full-spectrum and low- spectrum) described in Section 3.1 with the results pre-
Computer
Plol
C5
sented in Figure 6 The dashed line indicates the perfor- mance of the best-performing GNN. Performance degra- dation is observed on 11 out of the 12 datasets, with the exception of ogbn-arxiv. Moreover, on four homophilous graphs CS, Physics and WikiCS - the results are even worse than those of the best-performing GNN, This pro- vides strong evidence for the necessity of high-frequent channel constraints. If the attention module only covers the low-frequency band, it may still exhibit "laziness" in learning. The inclusion of high-frequency components helps to capture edge patterns (i.e., heterophilous con- nections), thereby mitigating the influence of trivial or spurious connections learned by the module. For het- crophilous graphs, the target signal is relatively dispersed across the frequency spectrum and less concentrated in the cow-frequency band [ 9 This spectral dispersion makes the low-spectrum filter bank less prone to overfitting, but the inability capture components that reside in the high-frequency range still limits its performance.
Vikes
Toman-Erphs
Figure 6: Performance under different channel initialization strategies.
4.4 Visualization
To further investigate the role of attention mechanisms in GT', we randomly sample 100 nodes on Minesweeper to visualize them in Figure Compared to the label matrix, the node representation similarity produced by Dolynormer-GNi aligns closely with the ground truth. Despite the inclusion of an attention module downstream, no performance gain over the GNN observed. And the close resemblance between Polynormer-Attn and Polynormer-GNY further indicates that its attention layer mainly repeats the already captured features. contrast, SGFormer introduces substantial topological noise through its attention mechanism. In Former, the multi-channel constraint plays crucial role:

---

spurious connections are effectively suppressed, while falsely missing edges still receive relatively high attention scores. As observed in the highlighted regions, this sparsity effect reminiscent of Lasso Regression [55]. Former tends to emphasize the intersection of above different attention mechanisms, thereby guiding the downstream GNN to focus more on essential features.
Conclusions
This paper clarifies that Transformers do not empirically provide universal performance boost for Graph Neural Networks, but better suited as a form of data augmentation enhance generalization. We introduce a global-aware graph filtering framework with multi-channel constraints that stabilizes attention, promotes feature focus, and reduces overfitting. Our findings highlight the value of revisiting the intrinsic structure of graphs over increasingly complex network architectures.
Acknowledgments and Disclosure of Funding
This work was supported by the National Key Research and Development Program of China (No.2023YFB3307203))
References
[1] Alon, U. & Yahav E. (2020) On the bottleneck of graph neural networks and its practical implications. In International Conference Learning Representations
[2] Blumer A., Ehrenfeucht, A., Haussler, D., & Warmuth M. K. (1987) Occam's razor. Information processing letters 24(6):377-380.
[3] Bo D., Wang X., Shi, C., & Shen, H. (2021) Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI conference artificial intelligence 35, pp. 3950-3957.
[4] Bo D., Shi C., Wang L., & Liao R. (2023) Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations
[5] Chen, Lin, Li, W., Li. P., Zhou, J., Sun X. (2020.) Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence 34, pp. 1438-3445.
[6] Chen, D., O' O'Bray I.., Borgwardt, K. (2022.) ) Structure-aware transformer for graph representation learning. In International conference on machine learning pages 3469-3489. PMLR.
[7] Chen J., Gao, K., Li, G., classification in large graphs. The Eleventh International Conference on Learning Representations
K. (2022. Nagphormer: A tokenized graph transformer for node
Chen, M., Wei, Z., Huang. Z., Ding B.. & Li, (2020. Simple and deep graph convolutional networks. In International conference on machine learning pages 1725- 1735. PMLR.
[9] Chien, F., Peng J., Li, P., & Milenkovie, O. (2021) Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations
[10] Choromanski, K., Lin, H., Chen H., Zhang T., Sehanobish A., Likhosherstov V., Parker-Holder J.. Sarlos, T., Weller A., & Weingarten, T. (2022) From block-toeplitz matrices to differential equations on graphs: towards general theory for scalable masked transformers. In International Conference on Machine Learning pages 3962-3983. PMI.R
[11] Cui, G., Zhou J., Yang C., & Liu Z. (2020) Adaptive graph encoder for attributed graph embedding. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery data mining pages 976-985.
[12] Davis J. (1959) Leonhard euler's integral: A historical profile of the gamma function: In memoriam: Milton abramowitz. The American Mathematical Monthly 66(10);49 869.
[13] Deng. C., Yuc, 7.,6 & Zhang Z. (2024) Polynormer: Polynomialeexpressive graph transformer in linear time. In The Twelfth International Conference Learning Representations
[14] Di Giovanni, F. Rusch, T. K., Bronstein M. M., Deac. A., Lackenby M., Mishra S., & Veličković P. (2023) How does squa-ing affect the power of gans? arXiv preprint ar06v: 03589
10

---

[15] Dwivedi, V. P., Luu A. T., Laurent, T., Bengio. Y., & Bresson, X. (2021) Graph neural networks with learnable structural and positional representations. arXiv preprini 17X0::21
[16] Dwivedi, V. P., Joshi, C. Luu A. T., Laurent, T., Bengio. Y., & Bresson, X. (2023) Benchmarking graph neural networks, Journal of Machine Learning Research 24(43): 48.
[17] Fey, M. & Lenssen J. E. (2019) Fast graph representation lcarning with pytorch geometric. arXiv preprint arXiv: OrXiv:7903.000 1903.02428
[18] Gilmer, J., Schoenholz, S., Riley P. F., Vinyals. O., & Dahl, G. E. (2017) Neural message passing for quantum chemistry. In International conference on machine learning pages 1263-1272. PMLR.
[19] Guo Y. & Wei, Z. (2023) Graph neural networks with learnable and optimal polynomial bases. In International conference muchine learning pages 12077-12097. PMLR.
[20] Hamilton, W., Ying Z. & Leskovec J. (2017) Inductive representation learning on large graphs. Advances in neural information processing systems 30.
[21] He K., Sun J.& & Tang. X. (2012) Guided image filtering, IEEE transactions on pattern analysis and machine intelligence 1997-1939.
[22] He, M., Wei, Z.,, Xu, H., & others (2021) Bernet:: Learning arbitrary graph spectral filters via bernstein approximation. Advances neural information processing systems 34:142: 14:19229-14 14251..
[23] W., Fey, M.. Zitnik, M.. Dong Y., Ren H., Liu B., Catasta M., & Leskovec J. (2020) Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33:22118 8- 8-2213..
[24] Huang, K., Wang, Y. G., Li, M., & Lio, P. (2024) How universal polynomial bases enhance spectral graph neural networks: Heterophily, ovoo-smn, and over-squashing In International Conference on Machine Learning pages 203 10-3033.. PMIR.
[25] Katharopoulos A., Vyas, A., Pappas, , N., & Fleuret, F. (2020) Transformers rans: Fast autoregressive transformers with linear attention. In International conference on machine learning pages 5156-5165.
PMLR.
[26] Kipf, N. & Welling, M. (2017) Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations
[27] Kong K., Chen J., Kirchenbauer J., Ni, R., Bruss C. B., & Goldstein, T. (2023) Goat: A global transformer large-scale graphs. In International Conference on Machine Learning pages 17375-17390. PMLR.
[28] Kreuzer. D., Beaini, D., Hamilton, W.. Létourneau V.. & Tossou, P. (2021) Rethinking graph transformers with spectral attention. Advances Neural Information Processing Systems 34:21618-21629,
[29] Leskovee J. & Sosič, R. (2016) Snap: A general-purpose purpose network analysis and graph-minigg library. ACM Transactions on Intelligent Systems and Technology (TIST) 8():1-20)
[30] Li Q., Han Z., & Wu X.-M. (2018) Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI conference on artificial intelligence 32,
[31] Li, X., Zhu, R., Cheng, Y., Shan C., Luo, S., Li, D., & Qian, W. (2022) Finding global homophily in graph neural networks when meeting heterophily. In International conference on machine learning pages 13242 13256. PMLR.
[32] Lim, D., Hohne F, Li, X., Huang, S. L., Gupta, V., Bhalcrao, O., & Lim S. N. (2021) Large scale learning on conhoooppiiooss graphs: New benchmarks and strong simple methods. Advances in neural information processing systems 34:20887-2090
[33] I. & Zhou, T. (201 1) Link prediction in complex networks: survey. Physica A: statistical mechanics and its applications 390(6):1 (0006)115000000 150-1170.
[34] Luan, S., Hua, C. Lu, Q. Zhu J., Zhao M., Zhang S., Chang X.W.,, & Precup. D. (2022) Revisiting heterophily for graph neural networks. Advances in neural information processing systems 35:1362-1373 1375.
[35] Luo, Y., Shi L.. & Thost, V. (2023) Improving self-supervise molecular representation learning using persistent homology. Advances in Neural Information Processing Systems 36:34043-3400
11

---

[36] Luo Y.. Shi. L.,, & Wu, X.-M. (2024) Classic gnns are strong baselines: Reassessing gnns for node classification. In Advances in Neural Information Processing Systems 37, pp. 97650-97669. Curran Associates, Inc.
[37] Ma. L.. Lin, C.. Lim. D., Soriiao-Soriano.... A., Dokania P. K., Coates M.. Torr P., & Lim S.-N. (2023) Graph inductive biases in transformers without message passing. In International Conference on Machine Learning pages 23321- 233337. PMLR.
[38] Maurya, S. K., Liu, X., Murata T. (2022) Simplifying approach to node classification in graph neural networks. Journal of Computational Science 62:101695.
[39] Mernyei. P. & Cangea C. (2020) Wiki-es: wikipedia- based benchmark for graph neural networks. arXiv preprint arXiv:2007.02901
[40] Min E., Chen, R., Bian Y., Xu, T., Zhao K., Huang W. Zhao P., Huang J., Ananiadou S., Rong. Y. (2022) Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.08455
[41] Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen J. E., Rattan G., & Grohe M. (2019) Weisfeiler and leman go neural: Higher-order neural networks. In Proceedings of the AAAI conference artificial intelligence 33, pp.
[42] Müller, L.. Galkin, M.. Morri C., & Rampášek, L. (2024) Attending to graph transformers. Transactions Machine Learning Rexearch
[43] Nikolentzos. G. & Vazirgiannis, M. (2020) Random walk graph neural networks. Advances in Neural Information Processing Systems 33:16211-16222
[44] Oono K. & Suzuki T. (2021) Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations
[45] Ortega A., Frossard, P., Kovačević J., Moura J. M., & Vandergheynst, P. (2018) Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE 106(5):808-88 828.
[46] Platonov. O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova L. (2023) A critical look at evaluation of gnns under heterophily: Are really making progress?. In The Eleventh International Conference on Learning Representations
[47] Rampášek, L., Galkin, M., Dwivedi P., Luu, A. T., Wolf, G., & Beaini, D. (2022) Recipe for a general, powerful, scalable graph transformer. Advances Neural Information Processing Systems 35: 14501-14515.
[48] Rozemherezki, B., Allen, C., Sarkar, R. (2021) Multi-scale attributed node embedding. Journal of Complex Networks 9(2)ccabb14.
[49] Sandryhaila A. & Moura J. M. (2013) Discrete signal processing on graphs: Graph fourier transform. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing pages 6167-6170, IEEE.
[50] Sen P., Namata G., Bilgic, M., Getoor L.,, Galligher, B., & Eliassi-Rad T. (2008) Collective classification in network data. Al magazine 29(3)933993
[51] Shchur, O., Mumme, M., Bojchevski A., & Günnemann, S. (2018) Pitfalls of graph neural network evaluation, arXiv preprint 1xXiv1811.0558
[52] Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland D. J., & Sinop A. K. (2023) Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning pages 31613-31632. PMLR.
[53] Shirzad, H., Lin, H., Venkatachalam, B., Velingker, A., Woodruff, D. P., & Sutherland, (2024)
Even sparser graph transformers. Advances in Neural Information Processing Systems 37:71277-71305.
[54] Tang J., Li J., Gao, Z., & Li J. (2022) Rethinking graph neural networks for anomaly detection. In International conference machine learning pages 21076-21089, PMLR.
[55] Tibshirani, R. (1996) Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology 58(1):267-28
[56] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit J., Jones L., Gomez, A. N., Kaiser L., & Polosukhin I. (2017) Attention is all you need. Advances in neural information processing systems 30.
12

---

[57] Veličković, P., Cucurull, G., Casanova, A., Romero, A.. Lid, P., & Bengio, Y. (2018) Graph attention networks. In International Conference Learning Reprexenlations
[58] Wang. M., Zheng, D., Ye, Z., Gan Q. Li M., Song, X., Zhou J., Ma, C., Yu L.., Gai Y., & others (2019) Deep graph library: A graph-centric, highly-performen package for graph neural networks. arXiv preprint arXiv:1909.01315
[59] Wang X. & Zhang M. (2022) How powerful spectral graph neural networks. In International conference on machine learning pages 23341 23362. PMLR.
[60] Wang Y., Wang. W., Liang Y., Cai, Y., & Hooi, B. (2021) Mixup for node and graph classification. In Proceedings of Web Conference 2021 pages 3663-3674.
[61] Wu Q. Yang. C., Zhao W., He Y., Wipf D., & Yan J. (2022. Difformer: Scalable (graph) transformers induced by energy constrained diffusion. The Eleventh International Conference on Learning Representations
[62] Wu, Q. Zhao , W., Li, Z., Wipf, P., Yan (2022. ) Nodeformer: scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems 35: 27387-3 27401.
[63] Wu Q. Zhao W., Yang. C., Zhang H., Nie F., Jiang H., Bian Y., & Yan J. (2023) Sgformer: Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems 36:64753-641 64773.
[64] Xu K., Hu, W., Leskovec J., & Jegelka. S. (2018) How powerful are graph neural networks?. In International Conference Learning Representations
[65] Yang. C.. Wu. Q.. Wang J.. & Yan J. (2023) Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. In The Eleventh International Conference on Learning Representations
[66] Ying. C., Cai, T., Luo S.. Zheng S., Ke G., He D., Shen Y., & Liu T.-Y. (2021) Do transformers really perform badly for graph representation? Advances in neural information processing xystems 34: 28877-28858
[67] You J., Ying R., & Leskovec J. (2019) Position aware graph neural networks. In International conference on machine learning pages 7134-7143, PMLR.
[68] Zhang M. & Chen, Y. (2018) Link prediction based on graph neural networks. Advances in neural information processing systems 31.
[69] Zhang. Z., Liu Q. Hu, Q.. & Lee, C.-K. (2022) Hierarchical graph transformer with adaptive node sampling. Advances in Neural Information Processing Systems 35:21171-21183.
[70] Zhao H., Ma S., Zhang D., Deng Z.H.,, & Wei, F. (2023) Are more layers beneficial graph transformers?. The Eleventh International Conference on Learning Representations
[71] Zhu J.. Yan, Y., Zhao L., Heimann, M., Akoglu L., & Koutra, D. (2020) Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems 33:7793-7804.
[72] Zhu, J., Rossi, R. A., Rao, A., Mai T., Lipka, N., Ahmed, N. K., Koutra D. (2021) Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence 35, pp. 1168-11176.
13

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.cc/pullc//uuuii wwwiiicgguie//eeeeeeeeeic CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This work is not expected to pose any specific societal impacts beyond those associated with existing graph neural network models.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our model does not fit in high-risk or misusable models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

A The Proof of Theorem 3.1
Proof. In the following content, we abbreviate the two channel initialization strategies {F(Ls; 8 - i, 0, E {O,.., a + }}} and {F(Ls;i, + 0, E (0,-., + 8}} as F and Flow: respectively. Each filter F(Ls; B, )) among them, its frequency response function is (As( = (2 - 2) C corresponds to Equation Consider > 0, > 0, À E [0. (A), we use the mean Á E(A) to represent the band-pass frequency of gs(A) like Figure
For Fulls E(A) is written as:
B(A) /-- (ssdA ( x 1 (2 -2 d)
?
(13)
2
catt(2 (2 dd
c
According to Equation 6
we can get:
1 с / x (2- dA
((A)
I(a + () + 1)2a+344 22+8+42 I(a + (3
T(a +
(14)
I'a + 3 - 3)
a a 9
Similarly, the mean E[A?) can be written as:
E(A²) = с / 1 (2
T(a + 3+2)
T(a + 3)T(3 +1)
(15)
I(a+ (3 + 1)2a+B+I
I(a + B +4)
4(a ()(a 2)
aa + + (a + 3 3)
The variance Var(A) can be written
Var(A) E(A2) - (E()
4(a + () + 2)
2(a +1 2
(a + 33+ () + (+
a a 3+2
(16)
4(a + 1)(3 +1)
(a 34 () +)3)*
If a + 8 + 0o, Var(A) = 1(a+1)(--1) + O, E(A) 10+042)(a++43
2(a+11
2a
3+1. Let
x+3+2
I = E (0, +oo), E(A) + It means that Fyult concentrate any B(A) (0,2), which
completes the proof of the frequency band coverage property of Fyau-
For Flow, its coverage within the interval (0, 1) be referred to Frun- For the last filter (F(Ls;; 3,a + 3, θ) in Fisw, where x = 1, we have (E(A) = 1, the band-pass frequency of Flow reaches its maximum. Hence, the frequency band coverage range of Flow is (0, 1].
B Additional Experiments
B.1 Sensitivity
21

---

Compute
Physkos
28.0
3110
(a) Homophilous Graphs
3.500
Amazon Retings
5940
Jeraan-Empr
Minesweeper
080
Questions
1.000
0.90
2.54
0.79
(b) Heterophilous Graphs
Figure 7: Effect of varying on model performance, = ++++++ 3.
T=1, avg Soore=0.9693555
T=8, avg 0.99550
Ground-truth Label
1.00
0.98
0.98
0.96
0.6
0.94
0.94
0.92
0.0
Figure 8: Visualization of the attention mechanisms of the G2 Formerr, SGFormer, and Polynormer, along with Polynormer-GNN and the corresponding label matrix.
As a critical hyperparameter in G*Foreer T= a + 3 directly controls the extent to which the attention mecha- nism is constrained. To assess its impact, we performed sensitivity analysis, with the experimental results shown in Figure 7 In conjunction with Table T2 the optimal number of filters tends concentrate between and 4 across both homophilous and heterophilous graphs. The maximum number of filters is used in homophilous graphs (c.g., Wikics, 7'=7), while the minimum appears in het- erophilous ones (e.g., Amazon- Amazon-Ratings. T=1). possible explanation is that, in homophilous graphs, due to the abundance of homophilous connections, kingle-channe attention mechanisms (i.e., low-pass filters) tend to in- duce nearly fully connected graphs, introducing substan- tial topological noise particularly when the number of classes large. Larger T impose stronger constraints, which help suppress spurious connections. Heterophilous graphs present more complex challenges, often requiring manual tuning to apply appropriate levels of constraint. For more difficult datasets (e.g., Amazon- Ratinng,,, overly strong constraints may hinder the downstream GNN from effectively focusing on the most relevant features.
Trainin and Testing Lass over Arazzan-Rttnngs
T= 1 Train
T-
Test
T= 8 Train
T-8 B Test
Loss
2
GCN Train
GCN Test
1
200
400
600
800
1000
Epoch
Figure Training and Testing Loss over Amazon-Ratings under different T.
Taking Amazon- Amazon-Ratings as an example, Figure g illustrates that increasing from minimal changes in the attention module, indicating the presence of redundant channels. Figure 9 presents the training and testing losses of FoFormer under T=1 and 7-8. As shown, while 7=8 achieves the most stable test loss, the performance begins to fluctuate (see Figure 7b), suggesting that the constraint may overly strong. Specifically, when becomes too large, Jo, also must update parameters across greater number of channels, thus increasing the optimization difficulty. In
leads to
22

---

Table 4: Runtime/Epoch (including training, validation, and testing) on large graphs (s).
Dataset ogbn-arxiv ogbn-products
pokec
SGFormer 0.33
11.13
7.43
Polynormer 1.33
15.06
7.24
Former 1.39
10.63
6.04
Table 5: Performance of band-pass filters under different heterophilous levels.
Dataset
Photo
ogbn-products
pokec
Minesweeper
Hete.
0.1674
0.1887
0,5552
0.2815
X
0.5466(0.07/0.06)
(3044337.80/37.116
0.5299(27.56/24.45)
0.5544(0.97/0.77
Fo
0.6835(3.27/1.522
0.4895(0.58/0.60)
0.5311(1.02/0.90)
0.5855(0. 25/0 18)
Fi
0.683566.5533.33
0.4892(1.72/14
0.5310(3.02/2.67)
0.5855(0. (5855(0,96/0068)
F2
0.6835(..27/1.52)
0.4891(1.72/1.. 180)
0.5310(2.98/2.644
0.5864(1 (0000.998
Fo
0.4889(0.57/0.60)
0.5309(0.9810.87))
0.5873(0.90/0.63
F1
0.5882(0.22/0.155
X
0.6698(12.36/6.09)
0.50(25.82/25.82)
0.5288(14.69113009)
0.5835(2.94/.10))
contrast, with T=1, the test loss lies between that of T=8 and tuned-GCN, indicating a more suitable level of regularization.
B.2 Scalability
Table reports the runtime per epoch (including training, validation, and testing) of Gorormer and the other two SOTA linear GTs. Note that full-batch training is used for ogbn-arxiv, while the remaining two datasets share the same batch size setting. The results indicate that GD Former incurs computational overhead comparable to linear GTs, which is consistent with the complexity analysis in Section 3.4 The GNN backbone of G2Former relies solely on efficient operations supported by modern graph learning frameworks (c.g., PyG, DGL), while the mobal-aware filter consists only of linear matrix multiplications. Therefore, we believe Former to highly efficient.
B.3 Effect of Graph-Guided Filtering
In T we present the response of different spectral channels under varying levels of heterophily, where heterophily (Hete.) is defined as the proportion of heterophilous edges among all edges. The table reports the Dis Dis Dishomoo) for X and X', representing the features before and after graph-guided filtering, respectively. F, denotes the filter associated with the i-th channel, where larger i corresponds to higher-frequency bands. As shown in the table, for smaller-scale graphs such as Photo and Minesweeper, graph-guided filtering tends to enhance the distinction between heterophilous node pairs, resulting in increased Dis scores in X' In contrast, for large-scus srrge-scale graphs such as ogbn-products and pokec, the filtering operation exhibits a compressive effect on node attributes, reducing both Dis_hee hete and Dis homoo Nevertheless, the overall feature distribution remains close to the original, as reflected by similar Dis scores before and after filtering. These findings highlight the adaptive role of graph-guides filtering: enhancing local discriminability in smaller graphs, while promoting feature compactness in larger graphs without significantly distorting the global structure.
B.4 Results in Comparison with Heterophilous and Spectral GNNs
In addition to H2GCN 71 and FAGCN 3], we also provide experimental results (In Table our method consistently demonstrates superior performance across various benchmarks.) of CPGNN 72.
GPRGNN 9. FSGNN 38), and GloGNN (1. We also provide a comparison between our method and these spectral GNNs (BernNet (22) JacobiConv [59] OptBasisGNN [99 and UniFilter 24 ) as shown Table 7 below. The best performance highlighted bold. Our method still demonstrates superior performance.
23

---

Table 6: Comparison of model performance on heterophilous graphs.
Dataset
Squirrel
Chameleon
Amazon Ratings
Coman-Empire
Minesweeper
Questions
Metric
Accuracy
Accuracy
Accuracy
Accuracy
ROC-AUC
ROC-AUC
H2GCN
34.75=0.97
27.80=3.87
36.40.0029
60.01 18
88.65 =0.37
62.37=1.15
FAGCN
36.33=1.62
34.67
40.28 68
=2.89
50.19+1.34
67.99=1.51
CPGNN
30.01=2.11
32.75=3.79
38.66 38.6641066
62.37
50.01
65.97=1.67
GPRGNN
39.01=2.00
39.64
45,02
65.13
85.26
54.38
FSGNN
34.99=1.27
40.33
51.87
79.65
90.11
78.85
GloGNN
35.36=2.14
23.99
36.97
60.21
51.26
65.32
Ours
45.53=1.70
44.34 44.3
55.86
93.03 20.33
99.45 10.12
79.55 20.31
Table 7: Comparison of model performance on homophilous graphs.
Computer
Photo
physics
wikies
BernNet 92.63+0.33
94.65+1..2
94.77=0.3
96.54+0.1
75.29=
JacobiConv
92.32=+0.2
93.7610.1
94.21=0.5
96.17#0.1
75.47=1.1
OptBasisCiNN
91.04-+0.4
95.31++.3
95.66++0.6
96.81+0.1
77.63+00.9
UniFilter
93.20++0.3
93.98++0.4
93.22++0.1
96.77+00.
78.82+0.7
G Forrmer
94.29.10.1
97.06:10.1
96.53+1.11
97.60
81.14:0.2
B.5
Comparison of Generalization Gap
We report the model's generalization gap (65 in Table T0 classical GNN that achieves the highest performance score the corresponding dataset. Our method consistently achieves the lowest generalization gap.
below. The tuned GNN refers to the
C Dataset and Baselines Details
C.1
Dataset
Table presents detailed statistics of the 17 datasets used our experiments. For the train-
ing/validation/test splits, directly adopt the splits from [36] (0.6/0.2/0.2) for Computer, Photo, CS, and Physics. Squirrel and Chameleon follow the version of [46), which removes duplicate nodes.
The remaining datasets use the official splits 32 23 39).
Specifically, Cora, CiteSeer, and PubMed (50) are widely used toy citation networks. Computer and Photo [51] are co-purchase networks where nodes represent products and edges indicate frequently co-purchased items. and Physics [5T] are co-authorship networks, with nodes denoting authors
and edges representing collaborations, WikiCS [3] is citation network of computer science papers.
Squirrel and Chameleon 48 are two widely studied Wikipedia page networks centered around specific topical domains. Other 4 heterophilous datasets [66]: Roman-Empire is word-level graph constructed from the Roman Empire Wikipedia article, where nodes represent individual words and edges link words that are either sequential or syntactically related. Amazon-Rating represents product co-purchasing network, with nodes as products and edges connecting items frequently bought
Table 8: Comparison of model performance on heterophilous graphs
mmazon_ratinge
roman ioman_empire
minesweeper
questions
BernNet
50.70+10.6
88.71+0.7
89.76++0.5
76.04++0.7
JacobiCony
52.39-10.4
89.32.00.3
91.62-10.3
76.11+1.00
OptBasisGNN
52.1111.4
88.9410.6
93.50
77.23
UniFilter
53.66:10.7
91.32210.6
92.38.10.7
77.564+0.9
Former
55.8611011
93.03110.3
99.45-10.1
79.5540.3
24

---

Table Generalization gap on homophilous graphs.
Computer
Photo
physics
wikics
SGFormer
0,2650
0.1356
0.0963
0.0719
0.9439
Polynormer
0. 1414
0,1622
0.0574
0.0911
0.8236
tuned GNN
0.0893(GAT)
(Grap((G))
0.087A(GraphAAGB)
0.0089(GCN)
0,4402(GAT)
Former
0.0686,,
0.00534
0.01964.
0.00514
0.36574
Table 10: Generalization gap on heterophilous graphs.
amazon ratings
roman empire
minesweeper
questions
SGFormer
8.2326
0.8225
0.3561
1.7627
Polynormer
3.3355
0.6561
0,3393
0.7404
tuned GNN
4.0T64(GAT)
0.6327(GCN)
0,3475(GCN)
0.3036(GCN)
Fororeer
2.08374
0.4242
0.0900
0.24114
together. Minesweeper is a synthetic dataset, modeling 100 100 grid where nodes are grid cells and edges connect adjacent cells. Questions is user interaction graph derived from the Yandex Q question-answering platform, where nodes denote users and edges indicate interactions via answered questions.
ogbn-arxiv and ugbn-products [23 are datasets released by the Open Graph Benchmark (OGB), rep- resenting citation network of academic papers and an Amazon co-purchasing network, respectively,
Pokec 29 a large-scale social network dataset.
C.2 Baselines
For all datasets, our baselines fall into two main categories: Graph Transformers and well-tuned classical GNNs (GCN, GraphSAGE, and GAT), The Graph Transformer group includes eight models: GraphGPS, NAGphormer, EXphormer. GOAT, NodeFormer, SGFormer, Polynormer, and Spex- phormer.
Table 11: Summary of Dataset Statistics for Node Classification.
Dataset
Type
# Nodes
# Edges
# Feature
Classes
Cora
Homophilous
2.708
5,278
1,433
7
Citeseer
Homophilous
3,327
4,522
3,703
6
Pubmed
Homophilous
19,717
44,324
500
Computer
Homophilous
13,752
245,861
767
10
Photo
Homophilous
7,650
119,081
745
CS
Homophilous
18,333
81.894
6,805
15
Physies
Homophilous
34,493
247,962
8,415
Wikies
Homophilous
11,701
216,123
300
10
Squirrel
Heterophilous
2,223
46,998
2,089
5
Chameleon
Heterophilous
890
8,854
2,325
5
Noman-Empire
Heterophilous
22,662
32,927
300
18
Amazon- -atings
Heterophilous
24,492
93,050
300
5
Minesweeper
Heterophilous
10,000
39,402
7
2
Questions
Heterophilous
48,921
153,540
301
2
ogbn-arxiv ogbn-products
Homophilous
169,343
1,166,243
128
40
Homophilous
2,449.029
61,859,
100
47
Pokec
Heterophilous
1,632,803
30,622,564
65
2
25

---

For GCN, GraphSAGE, and GAT, we directly use the implementation from [3],, where the key hyperparameters for these classical GNNs are already properly configured. For the 8 Graph Trans- formers, we use their official implementations and tune the critical hyperparameters according to the following configuration:
GraphGPS F We perform hyperparameter tuning on the dropout rate from {0.1, 0.3, 0.5, 0.7]. MPNN layer type within {GCN, GraphS GAT), hidden size from (64, 128, 256). the number of layer from {1, 2, 3, 4, 4, 6, 7,8,9 9, 10} and attention heads from {1, 2, 4}. We set the learning rate 0.001 and Performer as the global attention layer type.
NAGphormerr fl We set the learning rate to 0.001 and the hidden size to 512. And We perform hyperparameter tuning the number of global layers from f1,2, 3, 4,5, 5, 6, 8,8,9 9, 10), the number of hops from {3, 7, 10), dropout rate from {0.1, 0.3, 0.5, 0.7} and epochs from {1000, 1500, 2500).
as the local model and Exphormer as the global model. We set the learning rate to 0.001. We perform hyperparameter tuning on the hidden size from {64, 256, 512]. the dropout rate from {0.1, 0.3, 0.5, 0.7}. the number of layers from {1, 2, 4,5, 6, 7, 8, 9, 103 and the heads of attention from {1, and the epochs from {1500, 2500].
EXphormer We choose (GCN,GGaapSAAGE..AAT
GOAT We set the "conv type" to "full", the learning rate 0.001 and the epochs to 2000. We perform hyperparameter tuning on the number of centroids from {1024, 2048, 4096], dropout rate from 0.3,, 0.5, 0.7), the hidden size from (64, 256, 512), the heads of attention from (1,2,4) and the number of layers from {1, 4, 5, 6, 7, 8, 9, 10).
NodeFormer We set the learning rate to 0.001. We perform hyperparameter tuning on dropout rate from {0.1, 0.3, 0.5, 0.7}. the hidden size from {64, 256, 512]. the heads of attention from {1, 4). M. from {30, 50}. K from (5, 10), rb order from {1, 2] and the number of layers from (1, 4, 5, 6, 7, 8, 9, 103.
SGFormer We set the learning rate to 0.001, the number of global layer to 1 and 0.5. We perform hyperparameter tuning on dropout rate from {0.1, 0.3, 0.5, 0.7]. the hidden size from {64, 256, 512]. the heads of attention from {1, 2, 4]. graph weight from {0.5, 0.8). and the number of local layers from {1, 2, 3, 4, 5)
37 Polynormer. For Cora, Citeseer, Pubmed, Squirrel and Chameleon, we set the learning rate to 0.001. We perform hyperparameter tuning on dropout/indropout rate from {0.1, 0.3, 0.5, 0.7]. the hidden size from {64, 256, 512]. the heads of attention from {4, 6, 8). weight decay from {0.005, 0.0005, 0.00005), and the number of local/global layers from {1, 2, 3, 4, 5, 6, 7, 8, 9, 10). For the remaining datasets, we use the officially provided hyperparameters without further modification.
Spexphormer T0 For Cora, Citeseer, Pubmed, Wikies, Squirrel, Chameleon, Amazon Amazon-Ratings. Roman-Empire, Empire, Questions and ogbn-products, we perform hyperparameter tuning on the learning rate (0.001, 0.005). , the number of GNN/GT layers from {1, 2, 3, 4, 5). dropout rate from 10.1, 1,.,, 0.5), the hidden size from (64, 256, 512), weight decay from (0.005, 0.0005, 0.00005) and the heads of at- tention from {2, 4, 6). For the remaining datasets, we also use the officially provided hyperparameters without further modification.
C.3 Computing Environment
Our implementation is based on PyG 17 and DGL [58]. The experiments are conducted on Python 3.8. Intel(R) Core(TM) i7-6700 CPU 3.40GHZ 3.41 GHz, 24GB and Ubuntu 20.04 with Intel(R) Xeon(R) Platinum 8480+ CPU and 8 NVIDIA H800 GPUs.
26

---

Table 12: Dptaset-specific hyperparameter settings of GeFormer. "BN" and "LN" denote batch
normalization and layer normalization, respectively.
Dataset
ResNet
Normalization
Dropout
GNNs layer
Hidden size
GNN backbonc
Cora
False
False
0.9
0.001
GCN
Citeseer
False
False
0,5
2
512
0.001
GCN
Pubmed
False
False
0.7
GCN
Computer
False
LN
GCN
Photo
True
IN
0.5
0.001
GAT
CS
True
LN
0.4
256
0.001
GAT
Physics
True
LN
0.6
256
0.001
GCN
Wikies
False
LN
0.7
128
0.001
GAT
Squirrel
True
0.7
GCN
Chameleon
False
False
0.7
GAT
Roman- Roman-Empire
True
GCN
amazon-Rating
True
BN
0.5
512
0.001
GAT
Minesweeper
True
BN
0.1
64
0.01
GAT
Questions
True
False
0.3
13
512
3e-5
GCN
oghn-arxiv
True
0.5
0.0005
GCN
ogbn-products
False
GraphSAGE
Pokec
True
BN
0.2
0.0005
GCN
D Hyperparameters and Reproducibility
Since our GNN backbone is based the three classical architectures, Forrmrrr's hyperparameter settings primarily follow [36), with minor modifications depending on the specific dataset. We also follow prior works regarding the use of mini-batch full-batch training: except for ogbn-products and pokec, all datasets are trained full-batch mode. For GFForeer-ppccific hyperparameters. such the number of channels T
8, manual tuning is required. Detailed configurations for
reproducibility are provided Table 12
Limitations
This study is based node classification benchmark and focuses solely node-level tasks, lacking exploration of link prediction or graph classification. Establishing edge-level and graph-level evaluation benchmarks and further investigating the potential of GTs in supporting such tasks would be a valuable direction for future research.
27


Reviews:
[{"review_id": "SN3U51M9fh", "reviewer": "Reviewer_ieX9", "summary": "This paper presents G2Former, a graph transformer architecture that integrates global self-attention with local GNN in a **global-to-local** manner. The key idea is to treat the transformer as a band-pass graph filter that injects guided noise into node features across multiple frequency channels, which a downstream GNN then aggregates. The authors hypothesize that while pure transformers may not exceed the inherent performance of GNNs, a restricted multi-channel transformer can improve GNN generalization by capturing both low and high-frequency graph signals that classic GNNs (mostly low-pass) might miss. They support this claim with theoretical analysis and extensive node classification experiments on diverse graph datasets.", "questions": "Had fun reading the paper! Thanks to the authors for their clear language and apt amount of rigor. I have a few questions that I think would help clarify the contributions and applicability of G2Former.\n1. Performance vs simplicity: Given that G2Former's accuracy improvements over well-tuned GNNs are quite small (often < 0.5%), can the authors elaborate on when using G2Former is most justified? For what types of graphs or scenarios would the added complexity pay off most? It would help to know if there are specific regimes (e.g., strong heterophily, extremely large and sparse graphs, etc.) where G2Former yields a clear advantage, as opposed to cases where a simple GNN is \"good enough\".\n2. Channel initialization and sensitivity: The paper mentions two channel initialization strategies and provides a sensitivity analysis on the number of channels in Appendix B.1. Could the authors clarify the following: (a) what are these two strategies in intuitive terms? and which one was ultimately used for the main results? (b) How sensitive is G2Former to the choice of the total number of channels $(\\alpha + \\beta)$ or the distribution of those channels between low vs high frequency? For instance, if one uses too few channels or suboptimal $(\\alpha,\\beta)$ combinations, does performance degrade notably?\n3. Understanding \"guided noise\": The concept of guided noise is intriguing. Could the authors provide more intuition or examples of what the transformer-generated noise looks like in practice? For example, do the attention-based features highlight anomalous or hard-to-predict nodes, or do they act as a form of dropout/regularization on the feature space? Any qualitative or quantitative insight into what the multi-channel attention is learning (perhaps via attention weights or frequency response curves) would help justify why this \"noise\" improves generalization.\n4. Limits of the transformer component: The authors conclude that G2Former \"falls short of surpassing the performance ceiling of GNNs\". What do the authors see as the fundamental limitation that prevents the transformer from exceeding GNN performance? Is it because the transformer's global attention, even when band-limited, cannot add new information beyond what multi-hop message passing provides? Or could it be an optimization issue (e.g., harder to train the attention fully)? Understanding this would be valuable for future research – for instance, if the issue is optimization, maybe different training schemes could help, whereas if it's an inherent limitation of global filters, then the community might better focus elsewhere.\n5. Attention sparsity and interpretability: G2Former currently constructs a dense attention graph (complete graph) but leverages a low-rank factorization to apply it efficiently. Do the authors have a sense of whether the learned attention matrix is sparse or diffuse? For example, do nodes attend strongly only to a limited set of other nodes (implying a sparser effective structure), or is the attention more spread out? Any information on this would help interpret how the model is functioning. Additionally, can any of the learned global connections be interpreted as meaningful (e.g., connecting nodes of the same class across clusters, which a local GNN might not connect)? Providing a bit of interpretation could strengthen the argument that the global filter is doing something non-trivial and useful (again, not expecting too much work here, please feel free to tell me if this is too much work and is out of scope of the current project, it will not affect my rating/view of this work).", "limitations": "Limitations have been addressed adequately.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Global-to-local design: G2Former integrates a global transformer as a band-pass filter feeding into a GNN, which avoids redundancy and leverages complementary spectral information.\n- Theoretical grounding: The model is formally shown to act as a multi-channel polynomial filter over a learned Laplacian, with provable ability to span arbitrary frequency bands via $(\\alpha, \\beta)$ (Theorem 3.1).\n- Scalability: The architecture maintains linear complexity in $|V| + |E|$ using low-rank attention and polynomial filtering, and runs efficiently on large-scale graphs like ogbn-products etc.\n- Strong experiments: Evaluated on 17 diverse graphs, the model shows consistent improvements over both classical GNNs and graph transformers, with well-tuned baselines and rigorous ablations.\n- Regularization effect: The multi-channel setup stabilizes learning and improves test generalization, as shown via controlled attention-only ablations and loss curves.\n\nWeaknesses\n- Marginal gains on homophilic graphs: Improvements over strong GNN baselines are often under 0.5%, and in some cases, negligible or absent. It would be interesting to address why the method is not more effective on these kinds of datasets.\n- Added complexity: The multi-channel design, spectral filtering, and channel hyperparameters introduce non-trivial implementation and tuning overhead for modest gains. Is there a simpler alternative that could achieve similar results? I would expect a simpler model to mimic these effects without the spectral complexity.\n- Guided noise concept lacks clarity: The role and behavior of transformer-injected \"noise\" are not fully explained or visualized, which makes interpretation more challenging.\n- Limited task diversity: Evaluation is restricted to node classification; it's unclear if the method generalizes to link prediction or graph-level tasks. The nature of the global-to-local design could be more thoroughly explored across different graph learning tasks. Of course, this would be a separate paper, but it would be interesting to comment on it a little if you have some thoughts. (Not expecting any analysis or results here, so feel free to ignore this comment.)", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**. Thank you for this thoughtful question. We agree that G2Former does not always outperform well-tuned GNNs by large margins, especially on simple or homophilous graphs. This observation aligns with our central motivation: To examine whether and when global attention mechanisms truly help GNNs generalize — not just whether they boost accuracy in absolute terms. Our experiments (Table 1-3, Figure 4) show that G2Former tends to offer the most tangible benefits in the following regimes:Heterophilous graphs, where spatial domain neighborhood are noisy or conflicting; Large and sparsely connected graphs, where global signal propagation improves convergence and stability. G2Former offers a principled framework for interpreting and refining Graph Transformers through spectral constraints. The following presents the link discriminability under homophilous settings, computed as $Dis=Dis_{hete}/(Dis_{hete}+Dis_{homo})$. $Dis_{hete}, Dis_{homo}$ denote the average Euclidean distances between node pairs connected by heterophilous and homophilous edges, respectively. The dataset with the smallest performance improvement exhibits the highest $Dis$ score, indicating lower similarity among node pairs connected by heterophilous edges, and consequently, a higher degree of homophily in the graph structure. This is in line with your judgment.\n\n**Table: Link discrimination ($Dis$) on homophilous graphs.**\n\n| Dataset   | Cora    | Citeseer | PubMed  | Computer | Photo   | cs      | Physics | WikiCS  |\n|-----------|---------|----------|---------|----------|---------|---------|---------|---------|\n| $Dis$    | **0.5749** | **0.6060** | **0.5742** | 0.4811   | 0.4501  | 0.5156  | 0.5154  | 0.5281  |\n\n\n**Q2**. Thank you for raising this important and thoughtful question. We are happy to clarify the two initialization strategies and the robustness of channel design. (a) Initialization strategies: As described in Figure 3, we consider two initialization strategies for the learnable spectral filters: Full-spectrum initialization: channels are initialized to evenly cover the full frequency domain (from low to high); Low-spectrum initialization: all channels are initialized within the low-frequency range. The full-spectrum initialization is used in all main experiments (Tables 1-3), as it consistently outperforms the low-spectrum alternative across both homophilous and heterophilous graphs (Figure 6).\n(b) Sensitivity to the total number of channels $T = \\alpha + \\beta$: As shown in Figure 7 and discussed in Appendix B.1, G$^2$Former exhibits dataset-specific preferences for $T$, but overall demonstrates robustness to its precise value: On homophilous graphs, larger $T$ (e.g., $T = 7$ on WikiCS) help suppress spurious attention due to oversmoothing, effectively regulating the attention spectrum; On heterophilous graphs, smaller $T$ (e.g., $T = 1$ on Amazon-Ratings) are preferred, avoiding over-constraining the attention module, which could otherwise limit expressiveness. We also show in Figures 8 and 9 that larger $T$ values may introduce redundant channels and optimization challenges, but even suboptimal choices of $T$ still yield test performance comparable to or better than strong GNN baselines.\n\n**Q3**. We thank the reviewer for their insightful interest in the concept of guided noise, which indeed plays a central role in our interpretation of G$^2$Former's generalization behavior. At a high level, we use “guided noise” to refer to structured spectral perturbations introduced by multi-channel attention filters — which differ from random noise in that they are constrained to lie within specific frequency bands (e.g., low-pass, high-pass). We present the response of different spectral channels under varying levels of heterophily, where heterophily (**Hete.**) is defined as the proportion of heterophilous edges among all edges. The table reports the $Dis(Dis_{hete}/Dis_{homo})$, for $\\mathbf{X}$ and $\\mathbf{X'}$, representing the features before and after graph-guided filtering, respectively. $\\mathcal{F}_i$ denotes the filter associated with the $i-$th channel, where a larger $i$ corresponds to higher-frequency bands. As shown in the table, for smaller-scale graphs such as Photo and Minesweeper, graph-guided filtering tends to enhance the distinction between heterophilous node pairs, resulting in increased $Dis$ scores in $\\mathbf{X'}$ . In contrast, for large-scale graphs such as ogbn-products and pokec, the filtering operation exhibits a compressive effect on node attributes, reducing both $Dis\\_{hete}$ and $Dis\\_{homo}$. \nNevertheless, the overall feature distribution remains close to the original, as reflected by similar $Dis$ scores before and after filtering. These findings highlight the adaptive role of graph-guided filtering: enhancing local discriminability in smaller graphs, while promoting feature compactness in larger graphs without significantly distorting the global structure.\n\n**Table:Response results of each channel on graphs with different heterophily.**\n\n| **Dataset**  | **Photo** | **ogbn-products** | **pokec** | **Minesweeper** |\n|--------------|-----------|-------------------|-----------|-----------------|\n| **Hete.**    | **0.1674** | **0.1887** | **0.5552** | **0.2815** |\n| **$\\mathbf{X}$**         | **0.5466 (0.07/0.06)**  | **0.5043 (37.80/37.16)** | **0.5299 (27.56/24.45)** | **0.5544 (0.97/0.78)** |\n| **$\\mathcal{F}_0$**      | **0.6835 (3.27/1.52)**  | **0.4895 (0.58/0.60)**   | **0.5311 (1.02/0.90)**   | **0.5855 (0.25/0.18)** |\n| **$\\mathcal{F}_1$**      | **0.6835 (6.55/3.03)**  | **0.4892 (1.72/1.80)**   | **0.5310 (3.02/2.67)**   | **0.5855 (0.96/0.68)** |\n| **$\\mathcal{F}_2$**      | **0.6835 (3.27/1.52)**  | **0.4891 (1.72/1.80)**   | **0.5310 (2.98/2.64)**   | **0.5864 (1.40/0.98)** |\n| **$\\mathcal{F}_3$**      | **-**                  | **0.4889 (0.57/0.60)**   | **0.5309 (0.98/0.87)**   | **0.5873 (0.90/0.63)** |\n| **$\\mathcal{F}_4$**      | **-**                  | **-**                    | **-**                    | **0.5882 (0.22/0.15)** |\n| **$\\mathbf{X'}$**        | **0.6698 (12.36/6.09)** | **0.5000 (25.82/25.82)** | **0.5288 (14.69/13.09)** | **0.5835 (2.94/2.10)** |\n\n**Q4.** We deeply appreciate this question, as it aligns closely with the central motivation of our study. Based on extensive empirical exploration, we believe that the inability of global attention mechanisms to surpass well-tuned GNNs stems primarily from their inherent limitations in modeling graph inductive bias, rather than optimization difficulties. Specifically, our findings suggest that attention-based modules struggle to capture the complex, often irregular topological priors inherent in real-world graphs. Unlike Euclidean domains (e.g., images or text), graph connectivity does not necessarily follow intuitive patterns like “similar nodes are more likely to be connected.” Moreover, a recent empirical study **[1]** also shows that graph Transformers exhibit no significant advantage over classical GNNs on graph-level tasks, further reinforcing our conclusion. This raises fundamental concerns about the assumption that global attention can automatically discover useful relational structure. Our results suggest that global attention, even when spectrally constrained, cannot reliably introduce valuable new connections beyond what multi-hop GNNs already aggregate. Therefore, we share the reviewer’s view that this may reflect a fundamental limitation of current global filtering approaches. Rather than solely developing more complex architectures, we advocate for a shift in focus back to the analysis and modeling of graph topology itself, which may offer more fruitful directions for advancing the field.\n\n**Q5.** We appreciate the reviewer’s thoughtful comments regarding the sparsity and interpretability of the attention matrix. As in prior works such as SGFormer and Polynormer, G$^2$Former employs a dense attention mechanism. This design ensures scalability and fairness in comparisons, especially on large graphs where explicit sparsification would incur high computational cost. While the learned attention matrix is mathematically dense, we observe that the effective attention tends to be soft-sparse, i.e., each node often focuses more strongly on a subset of other nodes (Figure 5).  Regarding interpretability, we do not rule out the possibility that G$^2$Former captures semantically meaningful global connections, such as linking same-class nodes across clusters. However, our primary conclusion is based on entire performance trends: these potential benefits are often offset by the topological noise introduced by dense global attention, especially on homophilous graphs. Moreover, such connections may be  due to the fact that the node pair is a training sample, and their generalization to unseen test pairs remains uncertain. While a detailed interpretability analysis is beyond the current paper’s scope, we agree that exploring this further would be a promising direction for future work. In ongoing work, we are exploring relaxed message-passing schemes that aim to combine the strengths of local GNN modeling and global perception, seeking to expand the receptive field while mitigating the topological noise introduced by dense attention. Thank you very much for your support.\n\n[1] Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence. ICML 2025."}, {"review_id": "85M0oPTv32", "reviewer": "Reviewer_3Sa7", "summary": "The paper examines the efficacy of Graph Transformers (GT) in graph learning and proposes a new framework called G2Former, which redesign GT as band-pass global-aware graph filters. From the emprical study, the author shows that GT’s global attention does not significantly improve node classification performance and may introduce topological noise. Instead of using GT in traditional parallel or stacking fashions with GNNs, G2Former places the global attention module upfront, using it to generate band-pass filtered guidance signals which are then injected into downstream GNNs via a graph-guided filtering mechanism. Extensive experiments on 17 graph datasets (homophilous, heterophilous, large-scale) show improved performance.", "questions": "I have listed a few questions in the weakness part.", "limitations": "yes.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper provided clear motivation and insightful empirical observations, like the (e.g., loss plots and visualizations) that GT often fail to significantly improve GNNs and may even degrade performance.\n2. The paper introduce a theoretically grounded G2Former, which treats GT as band-pass graph filters. The mathematical formulation of band-pass filters with learnable graph spectra is well done and connects the model to spectral theory.\n3. Extensive experiments span homophilous, heterophilous, and large graphs, and compare against a wide range of classical GNNs and SOTA graph Transformers.\n\nWeakness:\n1. Clarity of the methods can be improved. The method section is dense, with heavy reliance on mathematical notation; Some design choices suddenly appear without intuitive justification. For instance: \n- the use of two FFNs (fθ1 and fθ2) is introduced abruptly without justification. What is the reason for using FFN instead of simple projection matrix? Will these increased parameters and enhanced representation power works as confounding factor and increase the performance?\n- The graph-guided filtering mechanism is mathematically sound but lacks a clear conceptual description. Why this approach helps, what type of features it enhances, and how it interacts with heterophily? Some figures showing how the spectral response of your filter under different heterophily might help justify its usage.\n- The paper can benefit from clearer section transitions, perhaps starting each technical section with a “motivation paragraph” that ties back to observed problems, then leads to your design choices..\n\n2. The paper introduces three paradigms: local-to-global, local-and-global, and global-to-local. But the conceptual framing is underdeveloped, and not well described. Specifically, the authors do not clearly define or survey prior work falling into the first two categories, but only provide the framing in Figure 2, and leave the reader to figure it out. For example, SGFormer and Polynormer are mentioned as representatives, but there’s no summary of their architectural roles or design philosophies. A taxonomy of existing GT architectures with citations would make the novelty of G2Former’s global-to-local scheme more understandable and grounded. In its current form, the distinction feels more like a post-hoc categorization rather than a well-established analytical framework.\n\n3. I notice that some newer or more tuned heterophily-centered GNN baselines (e.g., H2GCN, FAGCN) that perform well on heterophilous graphs were not included in the tables. Besides, the G2Former results are strong but not always dominant over GNNs on homophilous datasets, limiting claims of universal superiority.", "was_revised": true, "final_justification": "After considering all aspects of the paper, including the paper's clarity, method's adaptability across homophily, I’ve decided to keep my score unchanged.", "rebuttal": "**W1.** We thank the reviewer for this important comment and the opportunity to clarify our design choices. The use of two FFNs follows the standard design in Transformer architectures **[1]**, where each attention layer is followed by a FFN. In our case, since the model is not designed as a stacked encoder, we directly apply FFNs to the node features. $f_{\\theta _1}$ maps node features into the latent space for constructing the attention matrix; $f\\_{\\theta\\_2}$ transforms features before graph spectral filtering, which is a standard preprocessing step for graph signal processing **[2][3]** and also adopted in some graph Transformers (e.g. SGFormer). **In fact, this common setting is rarely mentioned in previous papers. It is clarified in this paper for the sake of detail and reproducibility.**\nThis separation allows us to independently control topology construction and feature adaptation under the filtering view. We provide a comparison of parameter size between our method and the best-performing graph Transformer baseline, Polynormer, as shown in two tables below. **Across all datasets, our approach consistently requires fewer parameters than Polynormer.** This efficiency primarily stems from the design where all spectral channels share the same pair of FFNs. Therefore, model complexity is well controlled. We sincerely thank the reviewer for the careful and responsible concern regarding this aspect.\nHope these could address your concerns.\n\n**Table: Comparison of model parameter scales on homophilous graphs.**\n\n|  | **Computer** | **Photo**     | **CS**        | **Physics**   | **WikiCS**|\n|---------------|--------------|---------------|---------------|---------------|--------------|\n| **Polynormer**| 81,387,540   | 119,132,176 | 106,377,246 | 134,823,946 | 7,537,172 |\n| **G$^2$Former (Ours)** | 2,115,337 | 415,408 | 10,860,034 | 10,860,034 | 249,448 |\n\n**Table: Comparison of model parameter scales on heterophilous graphs.**\n\n| | **amazon\\_ratings** | **roman\\_empire** | **minesweeper** | **questions** |\n|----------------|---------------------|-------------------|-----------------|-----------------|\n| **Polynormer**| 9,112,586 | 156,053,540 | 167,983,108 | 105,619,460 |\n| **G$^2$Former (Ours)**| 2,777,122 | 5,958,692 | 213,141 | 8,029,700 |\n\n**W2.** We thank the reviewer for highlighting the need for a clearer conceptual description of our graph-guided filtering module. This undoubtedly strengthens the elaboration and demonstration of the method. The underlying intuition is as follows: The global-aware graph filter acts as a feature perturbation mechanism that introduces structured noise, guided by multi-channel spectral constraints. This“guided noise”is then injected into the node features via a residual-style update, similar in spirit to data augmentation or feature sharpening.\n\nIt encourages the model to focus on features that are consistently highlighted across multiple frequency channels. This reduces over-reliance on spurious local signals and helps the model generalize better across different graph structures.\n\nWe present the response of different spectral channels under varying levels of heterophily, where heterophily (**Hete.**) is defined as the proportion of heterophilous edges among all edges. The table below reports the $Dis(Dis_{hete}/Dis_{homo})$. $\\mathbf{X}$ and $\\mathbf{X'}$ represent the features before and after graph-guided filtering, respectively. $Dis_{hete}, Dis_{homo}$ denote the average Euclidean distances between node pairs connected by heterophilous and homophilous edges, $Dis=Dis_{hete}/(Dis_{hete}+Dis_{homo})$. $\\mathcal{F}_i$ denotes the filter associated with the $i-$th channel, where a larger $i$ corresponds to higher-frequency bands. As shown in the table, for smaller graphs (Photo and Minesweeper), graph-guided filtering tends to enhance the distinction between heterophilous node pairs, resulting in increased $Dis$ scores in $\\mathbf{X'}$ (feature sharpening). In contrast, for large-scale graphs (ogbn-products and pokec), the filtering operation exhibits a compressive effect on node attributes while preserving the original feature distribution, as evidenced by the simultaneous decrease in both $Dis\\_{hete}$ and $Dis\\_{homo}$ (data augmentation), with the overall $Dis$ score remaining largely unchanged. The model effectively adapts to both enhancement effects under varying levels of heterophily and graph scales. We sincerely thank you again for your meticulous and rigorous feedback.\n\n**Table:Response results of each channel on graphs with different heterophily.**\n\n| Dataset| **Photo** | **ogbn-products** | **pokec** | **Minesweeper** |\n|--------------|-----------|-------------------|-----------|-----------------|\n| Hete.| **0.1674** | **0.1887** | **0.5552** | **0.2815** |\n| **$\\mathbf{X}$** | **0.5466 (0.07/0.06)**  | **0.5043 (37.80/37.16)** | **0.5299 (27.56/24.45)** | **0.5544 (0.97/0.78)** |\n| **$\\mathcal{F}_0$** | **0.6835 (3.27/1.52)**  | **0.4895 (0.58/0.60)** | **0.5311 (1.02/0.90)** | **0.5855 (0.25/0.18)** |\n| **$\\mathcal{F}_1$** | **0.6835 (6.55/3.03)**  | **0.4892 (1.72/1.80)** | **0.5310 (3.02/2.67)** | **0.5855 (0.96/0.68)** |\n| **$\\mathcal{F}_2$**  | **0.6835 (3.27/1.52)**  | **0.4891 (1.72/1.80)** | **0.5310 (2.98/2.64)** | **0.5864 (1.40/0.98)** |\n| **$\\mathcal{F}_3$**  | **-** | **0.4889 (0.57/0.60)**   | **0.5309 (0.98/0.87)**   | **0.5873 (0.90/0.63)** |\n| **$\\mathcal{F}_4$**  | **-** | **-** | **-** | **0.5882 (0.22/0.15)** |\n| **$\\mathbf{X'}$** | **0.6698 (12.36/6.09)** | **0.5000 (25.82/25.82)** | **0.5288 (14.69/13.09)** | **0.5835 (2.94/2.10)** |\n\n**W3.** We thank the reviewer for this valuable suggestion regarding section transitions and structural clarity. In the final version, we will add brief motivation paragraphs at the beginning of each major subsection. \nWe believe these additions will significantly improve the readability and conceptual accessibility of the paper.\n\n**W4.** We appreciate the reviewer’s suggestion and understand the need for clearer framing. In fact, we would like to clarify that our categorization of Graph Transformer architectures is not introduced post-hoc, but rather follows the taxonomy established in Polynormer **[4]**. In other words, we followed the published work precisely to avoid unnecessary controversy. \nSpecifically, as stated in lines 54–56 and illustrated in Figure 1, we describe SGFormer as a representative of the local-and-global paradigm, and Polynormer as a local-to-global model. We adopt this framing as a basis to highlight the novelty of our global-to-local design. Thank you again for your valuable suggestion.\n\n**W5.** We thank the reviewer for raising this important point.Regarding the selection of baselines, our primary goal was to benchmark G2Former against a wide range of state-of-the-art Graph Transformers and classical GNNs, rather than exhaustively cover all heterophily-specialized GNNs. In addition to H2GCN and FAGCN, we also provide experimental results (In the table below, our method consistently demonstrates superior performance across various benchmarks.) of CPGNN, GPRGNN, FSGNN, and GloGNN to address your concerns. \n\nWe appreciate the reviewer’s observation, and we agree that G2Former does not achieve the best results on small citation networks such as Cora, Citeseer, and PubMed. This is not an oversight, but rather an expected and honest outcome — and reflects the underlying inductive bias of classical GNNs. The high homophily of these graphs aligns well with the low-pass filtering nature of GNNs. In the R1 of Reviewer ieX9, their homophily ranks among the top three under the homophilous benchmark. It is not surprising that G2Former — which incorporates high-frequency information — does not always outperform them on these tasks. However, this also reflects a broader issue in GNN benchmarking.  As observed in our experiments, many Graph Transformers perform well only on these small, homophilous datasets, but suffer from poor generalization on larger, more heterophilous graphs, which are in line with the conclusions of **[5]**. We hope this work provides useful insights and a reproducible benchmark for the community to better understand the true utility and limitations of Transformers in graph learning.\n\n**Table : Comparison of performance on heterophilous graphs. The best results are highlighted in bold.**\n\n|  | **Squirrel** | **Chameleon** | **Amazon-Ratings** | **Roman-Empire** | **Minesweeper** | **Questions** |\n|----------|--------------|---------------|---------------------|------------------|------------------|---------------|\n| Metric| Accuracy | Accuracy | Accuracy | Accuracy | ROC-AUC | ROC-AUC |\n| **H2GCN** | 34.75${\\pm}$0.9 | 27.80${\\pm}$3.8 | 36.40${\\pm}$0.3 | 60.01${\\pm}$0.4 | 88.65${\\pm}$0.3 | 62.37${\\pm}$1.3 |\n| **FAGCN** | 36.33${\\pm}$1.6 | 34.67${\\pm}$3.9 | 40.28${\\pm}$0.6 | 62.89${\\pm}$0.7 | 50.19${\\pm}$1.3 | 67.99${\\pm}$1.5 |\n| **CPGNN** | 30.01${\\pm}$2.1 | 32.75${\\pm}$3.7 | 38.66${\\pm}$0.6 | 62.37${\\pm}$0.4 | 52.01${\\pm}$0.7 | 65.97${\\pm}$1.6 |\n| **GPRGNN**| 39.01${\\pm}$2.6 | 39.64${\\pm}$3.8 | 45.02${\\pm}$0.3 | 65.13${\\pm}$0.7 | 85.26${\\pm}$0.5 | 54.38${\\pm}$1.4 |\n| **FSGNN** | 34.99${\\pm}$1.2 | 40.33${\\pm}$3.5 | 51.87${\\pm}$0.8 | 79.65${\\pm}$0.4 | 90.11${\\pm}$0.7 | 78.85${\\pm}$0.9 |\n| **GloGNN** | 35.36${\\pm}$2.1 | 23.99${\\pm}$4.3 | 36.97${\\pm}$0.1 | 60.21${\\pm}$0.6 | 51.26${\\pm}$1.2 | 65.32${\\pm}$1.2 |\n| **Ours**  | **45.53**${\\pm}$1.7 | **44.34**${\\pm}$4.3 | **55.86**${\\pm}$0.3 | **93.03**${\\pm}$0.3 | **99.45**${\\pm}$0.2 | **79.55**${\\pm}$0.1 |\n\n[1]  Attention is all you need. NeurIPS 2017.\n\n[2] Adaptive universal generalized pagerank graph neural network. ICLR 2020.\n\n[3] Rethinking graph neural networks for anomaly detection. ICML 2022.\n\n[4] Polynormer: Polynomial-Expressive Graph Transformer in Linear Time The Twelfth International Conference on Learning Representations. ICLR 2024.\n\n[5] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks. ICML 2025."}, {"review_id": "4WuiSF22zI", "reviewer": "Reviewer_g3CZ", "summary": "This paper explores the global attention mechanism in Graph Transformers in terms of node representation. The authors identify the test error oscillation phenomenon led by the global attention component and point out that mitigating such oscillation improves the generalization in GNNs. Those insights are evaluated in comprehensive experimental evaluations.", "questions": "1.\tThe rationale of global-to-local design is not fully elaborated. In the spectral design, G2Former utilizes the global attention matrix in place of the adjacency matrix. I understand that the filtered signals are fed into GNNs as inputs. However, the original graph structure is not considered at this spectral filtering stage. The authors should justify the rationale for this design.\n\n2.\tThe theoretical analysis or conclusion on the generalization in GNNs is missing. The ability of the Transformer to improve the generalization in GNNs claimed in the paper, is critical. I suggest the authors provide the necessary theoretical analysis.\n\n3.  It lacks necessary explanations of G2Former’s inferior performance on homophily graphs compared with other graph-transformer-based models. G2Former does not perform well on the three homophily datasets. Please justify this phenomenon.\n\n4.\tSome relevant spectral GNN models are not discussed or compared. Spectral GNNs acting as spectral graph filters on graph signals are closely relevant to the scope of this paper. However, they are not mentioned or compared in the experiments. For example, for example [1][2][3][4]. \n\n[1] BernNet: Learning arbitrary graph spectral filters via Bernstein approximation. NeurIPS 2021\n\n[2] How powerful are spectral graph neural networks? ICML 2022\n\n[3] Graph neural networks with learnable and optimal polynomial bases, ICML, 2023\n\n[4] How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing. ICML 2024", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. This paper proposed an interesting idea of incorporating global attention in the Transformer into the design of spectral GNN.\n\n2. Theoretical analyses on the spectral properties of G2Former and its time complexity are provided, which provide some insights into the research of graph transformers.\n\n3. Extensive evaluation of G2Former is conducted against both graph transformer baselines and GNNs on homophily and heterophily datasets. \n\n\nWeakness:\n\n1. The rationale of global-to-local design is not fully elaborated.\n\n2. The theoretical analysis or conclusion on the generalization in GNNs is missing.\n\n3. It lacks necessary explanations of G2Former’s inferior performance on homophily graphs compared with other graph-transformer-based models.\n\n4. Some relevant spectral GNN models are not discussed or compared.", "was_revised": true, "final_justification": "My major concerns have been cleared.", "rebuttal": "**Q1.** We thank the reviewer for the insightful question regarding the use of the global attention matrix in place of the original adjacency matrix during the spectral filtering stage. First, **we would like to clarify that this design follows a well-established paradigm in Graph Transformers, where the attention matrix is commonly used as the graph structure within attention-based message passing or implicit filtering modules.**\nOur contribution lies not in the replacement itself, but in providing a novel spectral interpretation of this process:\nWe reinterpret the attention matrix as a learnable graph filter, allowing us to impose explicit frequency constraints (e.g., multi-band-pass filtering), and use it to inject generalization-enhancing signals into the node features prior to GNN layers.\nThe learned global matrix replaces the adjacency only within the auxiliary filtering step. The original graph structure is fully preserved in downstream message-passing, so our method can still leverage its topological priors.\nThis decoupling enables the model to build a complementary structural view that enhances generalization, especially under structural noise or heterophily. We will clarify this distinction and its motivation in the revised version to prevent confusion.\n\n**Q2.** We appreciate the reviewer’s suggestion, and agree that theoretical analysis of generalization remains an important and open challenge in the GNN community.\nAt the same time, we would like to highlight a long-standing gap between theoretical predictions and empirical performance in this field.\nFor instance, **[1] provides theoretical justification that self-attention improves the generalization ability of Graph Transformers over GCNs. However, this conclusion is not always supported in practice. This is due to the fact that this generalization analyses focus on a narrow class of simplified Transformer architectures, without considering key components used in actual models (e.g., common tricks such as residual connections, layernorm/batchnorm, dropout, etc.). These components have been demonstrated in **[3,5]** to play a critical role in unlocking the full potential of GNNs.**\nGiven this gap, our work focuses on practical indicators of generalization, such as:\nGeneralization across diverse datasets (Tables 1–3);\nStability in test loss dynamics (Figure 4);\nVisualization of the Attention Matrix under Regularization Constraints (Figure 5).\nAdditionally, **to alleviate your concerns, we report the model's generalization gap **[4]** in the table below. Our method consistently achieves the lowest generalization gap.**\nRather than proposing abstract theoretical bounds, we provide empirical and spectral perspectives on how Transformer modules interact with graph inductive biases — offering a mechanism-level understanding that complements existing theoretical views.\nWe respectfully invite the community to revisit the reliability and applicability of current theoretical frameworks, with the goal of more effectively advancing modern GNN research.\n\n**Table: Generalization gap on homophilous graphs.**\n\n| **Model**     | **Computer** | **Photo** | **CS** | **Physics** | **WikiCS** |\n|---------------|--------------|-----------|--------|-------------|------------|\n| **SGFormer**  | 0.2650       | 0.1356    | 0.0963 | 0.0719      | 0.9439     |\n| **Polynormer**| 0.1454       | 0.1622    | 0.0574 | 0.0911      | 0.8236     |\n| **tuned GNN** | 0.0893 (GAT) | 0.2341 (GraphSAGE) | 0.0874 (GraphSAGE) | 0.0089 (GCN) | 0.4402 (GAT) |\n| **G$^2$Former (Ours)** | 0.0686$\\downarrow$ | 0.0053$\\downarrow$ | 0.0196$\\downarrow$ | 0.0051$\\downarrow$ | 0.3657$\\downarrow$ |\n\n**Table: Generalization gap on heterophilous graphs.**\n\n| **Model**      | **amazon\\_ratings** | **roman\\_empire** | **minesweeper** | **questions**      |\n|----------------|---------------------|-------------------|-----------------|--------------------|\n| **SGFormer**   | 8.2326              | 0.8225            | 0.3561          | 1.7627             |\n| **Polynormer** | 3.3355              | 0.6561            | 0.3393          | 0.7404             |\n| **tuned GNN**  | 4.0764 (GAT)        | 0.6327 (GCN)      | 0.3475 (GCN)    | 0.3036 (GCN)       |\n| **G$^2$Former (Ours)** | 2.0837$\\downarrow$  | 0.4242$\\downarrow$| 0.0900$\\downarrow$ | 0.2411$\\downarrow$ |\n\n**Q3.** We appreciate the reviewer's question. Indeed, G2Former does not outperform all baselines on the three old toy homophily-dominated datasets (Cora, Citeseer, PubMed), and we think this is an expected and informative result, rather than a shortcoming.\nThese datasets are known for their high homophily, which align closely with the inductive bias of classical GNNs — and also favor Transformer models that preserve this local bias.\nOur architecture includes graph-guided filtering (low and high frequency component) — which may not provide additional benefit (and could introduce unnecessary flexibility) on highly smooth graphs.\nAdditionally, we intentionally avoid overfitting to citation benchmarks through extensive per-dataset hyperparameter tuning, which has been criticized in **[2]** as a source of misleading claims. This is the case for most GTs (except for Polynormer, whose sourse paper avoided referring to these three homophilous datasets). In our response to R1of Reviewer ieX9, we presented the homophily rankings of these three graphs within homophilous datasets, where they ranked among the top three.\nWe will clarify this observation in the final version and emphasize that G2Former is not optimized for a single data regime, but rather for broader generalization across graph types. We believe this reflects an important tradeoff in model design: performance consistency vs task-specific overfitting.\n\n**Q4.** We thank the reviewer for pointing out the connection to spectral GNNs, such as BernNet, JacobiConv, OptBasisGNN, UniFilter. While our method is indeed inspired by graph signal processing, we would like to clarify that our setting and objectives differ significantly from conventional spectral GNNs.\nClassical spectral GNNs typically rely on static graph filters derived from the input Laplacian or pre-defined polynomial bases, and assume a relatively stable global frequency profile.\nIn contrast, G2Former uses a learned attention-based Laplacian to construct adaptive, input-dependent graph filters, enabling more flexible and localized frequency manipulation.\nFurthermore, our work focuses on providing a spectral interpretation of the attention mechanism in graph Transformers, aiming to address the effectiveness dilemma currently faced by such models. We also provide a comparison between our method and these spectral GNNs, as shown in the table below. The best performance is highlighted in bold. Our method still demonstrates superior performance. We hope these will address your concerns.\n\n**Table: Comparison of model performance on homophilous graphs.**\n\n| **Model**      | **Computer**         | **Photo**            | **cs**               | **physics**          | **wikics**           |\n|----------------|----------------------|-----------------------|-----------------------|-----------------------|-----------------------|\n| **BernNet**     | 92.63$_{\\pm 0.5}$     | 94.65$_{\\pm 0.2}$      | 94.77$_{\\pm 0.3}$      | 96.54$_{\\pm 0.1}$      | 75.29$_{\\pm 0.5}$      |\n| **JacobiConv**  | 92.32$_{\\pm 0.2}$     | 93.76$_{\\pm 0.1}$      | 94.21$_{\\pm 0.5}$      | 96.17$_{\\pm 0.1}$      | 75.47$_{\\pm 1.1}$      |\n| **OptBasisGNN** | 91.04$_{\\pm 0.4}$     | 95.31$_{\\pm 0.3}$      | 95.66$_{\\pm 0.6}$      | 96.81$_{\\pm 0.1}$      | 77.63$_{\\pm 0.9}$      |\n| **UniFilter**   | 93.20$_{\\pm 0.3}$     | 93.98$_{\\pm 0.4}$      | 93.22$_{\\pm 0.1}$      | 96.77$_{\\pm 0.3}$      | 78.82$_{\\pm 0.7}$      |\n| **G$^2$Former** | **94.29**$_{\\pm 0.1}$ | **97.06**$_{\\pm 0.1}$  | **96.53**$_{\\pm 0.1}$  | **97.60**$_{\\pm 0.1}$  | **81.14**$_{\\pm 0.2}$  |\n\n**Table: Comparison of model performance on heterophilous graphs.**\n\n| **Model**      | **amazon_ratings**      | **roman_empire**       | **minesweeper**         | **questions**           |\n|----------------|--------------------------|--------------------------|--------------------------|--------------------------|\n| **BernNet**     | 50.70$_{\\pm 0.6}$         | 88.71$_{\\pm 0.7}$         | 89.76$_{\\pm 0.5}$         | 76.04$_{\\pm 0.7}$         |\n| **JacobiConv**  | 52.39$_{\\pm 0.4}$         | 89.32$_{\\pm 0.3}$         | 91.62$_{\\pm 0.3}$         | 76.11$_{\\pm 1.0}$         |\n| **OptBasisGNN** | 52.11$_{\\pm 0.4}$         | 88.94$_{\\pm 0.6}$         | 93.50$_{\\pm 1.2}$         | 77.23$_{\\pm 0.8}$         |\n| **UniFilter**   | 53.66$_{\\pm 0.7}$         | 91.32$_{\\pm 0.6}$         | 92.38$_{\\pm 0.7}$         | 77.56$_{\\pm 0.9}$         |\n| **G$^2$Former** | **55.86**$_{\\pm 0.1}$     | **93.03**$_{\\pm 0.3}$     | **99.45**$_{\\pm 0.1}$     | **79.55**$_{\\pm 0.3}$     |\n\n[1] What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding. ICML 2024.\n\n[2] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks. ICML 2025.\n\n[3] Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence. ICML 2025.\n\n[4] Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. ICLR 2023.\n\n[5]  Classic gnns are strong baselines: Reassessing gnns for node classification. NeurIPS 2024."}, {"review_id": "xRPr6cAjRn", "reviewer": "Reviewer_gika", "summary": "This paper proposes G2Former, a novel framework that integrates graph spectral filtering with Transformers to improve node classification performance. The method introduces multi-channel band-pass filters to enhance feature representation and reduce topological noise in attention mechanisms. Extensive experiments on 17 diverse datasets demonstrate the effectiveness and generalization ability of the approach.", "questions": "see in the weaknesses", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper conducts experiments on 17 datasets, including homophilous, heterophilous, and large-scale graphs, which demonstrates the broad applicability and robustness of the proposed method.\n\nBy introducing multi-channel graph filters with band-pass properties, the method effectively reduces topological noise in attention and enhances the generalization ability of GNNs.\n\nWeaknesses：\n\nLine 37：\n\nThere is an obvious grammatical error: the phrase \"have have\" is duplicated.\n\nLine 8：\n\nThe claim that \"the global attention module does not provide significant performance gains\" is overly strong and lacks sufficient theoretical or empirical support. Many existing works (e.g., Graphormer, GTN) have shown the effectiveness of global attention in complex graph structures. Moreover, the proposed method itself incorporates global attention, which contradicts the claim.\n\nLine 12：\n\nThe paper asserts that \"the Transformer improves generalization in GNNs\" as a core contribution, but no experiments are designed to directly measure generalization. Therefore, the claim is unsubstantiated.\n\nLine 130：\n\nThe symmetric attention matrix \nA_s is not truncated or sparsified.If all attention values are non-zero and the graph is fully connected, does the degree matrix D_S result in all nodes having the same degree equal to the number of nodes?\n\nNecessity of Attention Mechanism Unclear:\n\nThe proposed G2Former effectively implements a learnable multi-channel graph filter. This could potentially be achieved using parametric spectral filters directly. Whether the attention mechanism is necessary for constructing the adjacency matrix is not discussed. If attention is only used to derive a spectral filter, there might be more direct and efficient alternatives, which should be addressed.", "was_revised": true, "final_justification": "It has addressed the issues I raised. There are minor flaws in the writing.", "rebuttal": "**Weakness 1.** Thank you for catching the typo. We will correct the duplicated phrase \"have have\" at line 37 in the final version.\n\n**Weakness 2.** We appreciate the reviewer’s concern, and we would like to clarify a potential misunderstanding.\nThe statement that “global attention modules do not provide significant performance gains” is in fact well-supported by existing empirical evidence.\nFirst, as cited in the Introduction (Line 56), prior work **[1]** has shown that many Graph Transformer models fail to outperform carefully tuned GNNs across datasets with diverse properties — including homophily, heterophily, and large-scale graphs.\nSecond, our own empirical study (Section 5), which includes comprehensive benchmarks across 17 datasets as well as training and test loss curves, further reinforces this observation.\nAdditionally, while Graphormer(NeurIPS 2021) and GTN(NeurIPS 2019) were not included in the original version due to their earlier publication dates, we have now added their results for comparison.\nThe experimental results are shown in the table below, where the performance of Graphormer and GTN remains inferior to that of the fine-tuned GNNs and our proposed method.\n**Most importantly, we would like to reiterate the core goal of our work:\nTo investigate whether the Transformer architecture — and specifically the global attention module — provides substantial performance improvements in GNNs. This is a problem that the GNN community must face and respond to.**\nOur key finding is nuanced:\n**Global attention alone does not reliably improve GNN performance. However, when constrained through a frequency-aware design, it can significantly support generalization.**\nThis challenges prevailing assumptions in the community, and highlights the need to revisit the role of attention mechanisms in GNNs.\n**Therefore, we emphasize that our inclusion of a global attention module is intentional and essential for our analysis, not contradictory.**\nIt allows us to reinterpret attention as a spectral operator and to examine when and why it may help GNNs generalize — under controlled conditions.\n\n**Table: Performance comparison with Graphormer and GTN.**  \nThe best performance is **bolded**, and the suboptimal performance is marked in *italics*. The tuned GNN uses the best-performing classic GNN, as indicated in parentheses.\n\n| **Model**     | **Cora**                    | **Citeseer**               | **Photo**                        | **Squirrel**                  | **Chameleon**                 |\n|---------------|-----------------------------|----------------------------|----------------------------------|-------------------------------|-------------------------------|\n| **Metric**    | Accuracy                    | Accuracy                   | Accuracy                         | Accuracy                      | Accuracy                      |\n| **Type**      | Homophilous                | Homophilous               | Homophilous                     | Heterophilous                | Heterophilous                |\n| **GTN**        | 80.36${\\pm}$0.9            | 68.76${\\pm}$1.5           | 89.93${\\pm}$0.6                 | 38.42${\\pm}$2.6             | 36.37${\\pm}$3.1             |\n| **Graphormer** | 83.15${\\pm}$0.7            | 72.11${\\pm}$0.8           | 92.70${\\pm}$0.4                 | 35.33${\\pm}$2.3             | 37.81${\\pm}$3.6             |\n| **tuned GNN**  | **84.56**${\\pm}$0.7(GCN)   | 72.28${\\pm}$0.5(GCN)      | 96.71${\\pm}$0.30(GraphSAGE)  | 45.03${\\pm}$1.7(GCN)        | **44.91**${\\pm}$4.6(GCN)    |\n| **Ours**       | *83.72* ${\\pm}$0.6     | **72.62**${\\pm}$0.6       | **97.06**${\\pm}$0.1             | **45.53**${\\pm}$1.8         | *44.34* ${\\pm}$4.4       |\n\n\n**Weakness 3.** Thank you for pointing out this important issue. \nWe believe there may be a misunderstanding regarding how we evaluate generalization. While we understand the concern, we interpret generalization in an empirical context, as is standard in GNN evaluation. The current challenges faced by Graph Transformer are based on an empirical research[1], so this approach will be a direct and powerful response.\nIn fact, we explicitly analyze generalization behavior in Section 4 through the following means:\n\n**The gap between test losses of different models.**\n\n**The stability of test-time performance across datasets with varying graph structures (homophily, heterophily, scale).**\n\n**Visualization of the attention matrix under multi-channels constraints.**\n\nThese evaluation strategies are consistent with prior empirical studies in the community. **In response to your concerns, we further provide the generalization gap **[2]** of the model as shown below.** Our method consistently achieves the lowest generalization gap. Therefore,  we believe our current experiments sufficiently and appropriately capture the generalization behavior of both GNNs and Transformer-based models in practice.\n\n**Table: Generalization gap on homophilous graphs.**\n\n| **Model**     | **Computer** | **Photo** | **CS** | **Physics** | **WikiCS** |\n|---------------|--------------|-----------|--------|-------------|------------|\n| **SGFormer**  | 0.2650       | 0.1356    | 0.0963 | 0.0719      | 0.9439     |\n| **Polynormer**| 0.1454       | 0.1622    | 0.0574 | 0.0911      | 0.8236     |\n| **tuned GNN** | 0.0893 (GAT) | 0.2341 (GraphSAGE) | 0.0874 (GraphSAGE) | 0.0089 (GCN) | 0.4402 (GAT) |\n| **G$^2$Former (Ours)** | 0.0686$\\downarrow$ | 0.0053$\\downarrow$ | 0.0196$\\downarrow$ | 0.0051$\\downarrow$ | 0.3657$\\downarrow$ |\n\n**Table: Generalization gap on heterophilous graphs.**\n\n| **Model**      | **amazon\\_ratings** | **roman\\_empire** | **minesweeper** | **questions**      |\n|----------------|---------------------|-------------------|-----------------|--------------------|\n| **SGFormer**   | 8.2326              | 0.8225            | 0.3561          | 1.7627             |\n| **Polynormer** | 3.3355              | 0.6561            | 0.3393          | 0.7404             |\n| **tuned GNN**  | 4.0764 (GAT)        | 0.6327 (GCN)      | 0.3475 (GCN)    | 0.3036 (GCN)       |\n| **G$^2$Former (Ours)** | 2.0837$\\downarrow$  | 0.4242$\\downarrow$| 0.0900$\\downarrow$ | 0.2411$\\downarrow$ |\n\n**Weakness 4.** We thank the reviewer for this insightful observation, which touches on a fundamental challenge in the design of Graph Transformers.\nIndeed, $\\mathbf{A}\\_s$ is not explicitly truncated or sparsified in our implementation — and this is by design.\nFirst, although $\\mathbf{A}\\_s$ is dense, the attention weights are derived from softmax-normalized scores, which typically concentrate on a few dominant entries. This results in a non-uniform degree matrix $\\mathbf{D}\\_s$ and a meaningful spectrum for $\\mathbf{L}\\_s$.\nEnforcing sparsity would require explicit construction and thresholding of $\\mathbf{A}\\_s$, incurring $\\mathcal{O}(n^2)$ complexity — which we intentionally avoid for scalability.\n\nSecond, we appreciate the reviewer’s sharp insight, **which touches on a subtle but critical issue also raised in our Introduction — namely, the “representation laziness” of dense, unconstrained attention.**\nPrior models such as SGFormer and Polynormer allow the attention module to freely learn graph inductive biases, but in practice this often leads to overly smooth or structure-agnostic behavior.\nOur work directly addresses this challenge by reinterpreting the attention matrix as a spectral operator, and constraining its response to enhance generalization of GNN rather than relying on unstructured learning alone.\n\nIn this light, we view $\\mathbf{A}\\_s$ as a frequency modulation tool — and preserving its dense form is essential for analyzing its behavior.\n\n**Weakness 5.** We sincerely thank the reviewer for raising this thoughtful question.\nWe believe this point touches on a deeper misunderstanding about the goal of our paper.\n\nThis work is not primarily intended to introduce a novel method that achieves state-of-the-art performance, but rather to address a critical open question in the community:\n\n**Can Transformer architectures truly help GNNs break through existing performance ceilings?** This was challenged by an empirical study **[1]**.\n\nTo answer this, we design G2Former as a controlled analytical framework, where we reinterpret the attention matrix not as a learned graph structure, but as a spectral filter — and systematically study its effect under frequency constraints.\n\n**We emphasize that this design is not about replacing the adjacency matrix with a better one, but about exposing and understanding the actual role of global attention in generalization of GNN, which has often been regarded as having broken through the performance bottleneck of GNNs in prior works.**\n\nAs we note in the Introduction, many existing Graph Transformers rely on unconstrained attention modules to \"implicitly learn\" the topology.\nHowever, this often results in representation laziness, as also observed in SGFormer and Polynormer.\nOur work critically examines this phenomenon and shows that without proper spectral constraints, attention alone provides limited benefit.\n\n**Therefore, we intentionally retain the attention module — not because it is the most efficient or direct way to build a graph filter, but because it is the object of our study.**\nWe hope this clarifies that our paper is driven by scientific inquiry into an open and impactful question, rather than by methodological novelty alone. Thank you again for your comment and we sincerely hope you can refer to our reply.\n\n[1] Classic gnns are strong baselines: Reassessing gnns for node classification. NeurIPS 2024.\n\n[2] Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. ICLR 2023."}]

Author rebuttal:

Meta-review: This paper investigates the fundamental question of whether Transformers can help Graph Neural Networks overcome their performance bottlenecks by proposing G2Former, which reinterprets global attention as band-pass graph filters with multi-channel spectral constraints. The work addresses a timely and important challenge in the graph learning community, motivated by recent empirical evidence questioning the effectiveness of Graph Transformers. The four reviewers provided scores of 5, 3, 4, and 5, with generally positive feedback on the experimental comprehensiveness but concerns about clarity and theoretical depth. Key strengths include: (1) Comprehensive empirical investigation - The evaluation spans 17 diverse datasets across homophilous, heterophilous, and large-scale graphs, providing robust evidence for the proposed approach's broad applicability; (2) Novel theoretical perspective - The reinterpretation of attention mechanisms as learnable spectral filters with band-pass characteristics offers a principled framework for understanding and constraining global attention in GNNs; (3) Honest and nuanced findings - The authors candidly report that G2Former does not always outperform baselines, particularly on highly homophilous datasets, while demonstrating clear benefits on heterophilous and large-scale graphs; (4) Important research question - The work tackles the fundamental question of whether attention mechanisms truly enhance GNN performance, providing empirical evidence that challenges prevailing assumptions in the field. Limitations acknowledged: (1) Modest performance improvements - The gains are often marginal (< 0.5%), though the authors argue their focus is on understanding the role of attention rather than achieving state-of-the-art results; (2) Presentation challenges - Multiple reviewers noted clarity issues and dense mathematical exposition, though the authors committed to improving section transitions and motivation; (3) Limited theoretical depth - While the spectral interpretation is novel, the theoretical understanding of generalization mechanisms remains primarily empirical. The authors demonstrated strong engagement during the review process, addressing technical concerns and providing additional experiments including comparisons with heterophily-focused baselines and generalization gap analyses. The work makes a valuable contribution to the graph learning community by providing a principled framework for understanding attention mechanisms and offering insights into when and why global attention may benefit GNN generalization, particularly under structural noise or heterophily.
Decision: Accept (poster)