Relieving the Over-Aggregating Effect in Graph Transformers
Authors: Junshu Sun
Wanxing Chang
Chenxue Yang
Qingming Huang
Shuhui Wang
Venue: NeurIPS 2025 poster ()
Keywords: graph transformers
message passing
graph neural networks
Primary area: deep_learning

Abstract: Graph attention has demonstrated superior performance in graph learning tasks. However, learning from global interactions can be challenging due to the large number of nodes. In this paper, we discover a new phenomenon termed over-aggregating. Over-aggregating arises when a large volume of messages is aggregated into a single node with less discrimination, leading to the dilution of the key messages and potential information loss. To address this, we propose Wideformer, a plug-and-play method for graph attention. Wideformer divides the aggregation of all nodes into parallel processes and guides the model to focus on specific subsets of these processes. The division can limit the input volume per aggregation, avoiding message dilution and reducing information loss. The guiding step sorts and weights the aggregation outputs, prioritizing the informative messages. Evaluations show that Wideformer can effectively mitigate over-aggregating. As a result, the backbone methods can focus on the informative messages, achieving superior performance compared to baseline methods.

Relieving the Over-Aggregating Effect in Graph Transformers
Junshu Sun
Wanxing Chang?
Chenxue Yang* Qingming Huang Shuhui Wang
Sttte Key Lab. of AI Safety, ICT, CAS
University of Chinese Academy of Sciences
DDMM Academy, Alibaba Group
*Agriculture Information Institute, CAAS
(sunjunshu21s, wangshuhuil ac. cn changwanxing wwxealibaba- com yangchenxue@cass. cn qmhuangOucas.acc ac.
Abstract
Graph attention has demonstrated superior performance in graph learning tasks. However, learning from global interactions can be challenging due to the large number of nodes. In this paper. we discover a new phenomenon termed over- aggregating. aggregggggg arises when a large volume of messages is aggre- gated into single node with less discrimination, leading to the dilution of the key messages and potential information loss. To address this, propose Wideformer, plug-and-pla method for graph attention. Wideformer divides the aggregation of all nodes into parallel processes and guides the model to focus specific subsets these processes. The division can limit the input volume per aggregation, avoid- ing message dilution and reducing information loss. The guiding step sorts and weights the aggregation outputs, prioritizing the informative messages. Evaluations show that Wideformer backbone methods can focus on the informative messages, achieving superior performance compared to bascline methods.
effectively mitigate aver-gggrgg As result, the
1 Introduction
Transformers have achieved remarkable success modeling duclidean-structuun data, including natural language processing [47, 26, 25], image understanding [27, 40, 38, 39], and video process- ing 5, 52]. Built on this success, significant efforts have been devoted to adapting transformers graph-structured data, giving rise various graph transformer models [23, 58, 55). Lever- aging the attention mechanism, graph transformers can learn from long-range dependencies and capture global features. These strengths provide effective solutions address the challenges of over-smoothing [30] and over-squahhin [1, 46], commonly encountered in traditional graph neural networks (GNNs) [17, 14, 48, 43, 13, 44, 45J. Evaluations across diverse downstream tasks highlight the promising performance of graph transformers [55, 42, 9].
Nevertheless, the dense global attention in graph transformers incurs space complexity of O(n²), where the memory consumption increases quadratically with the number of input nodes. This high complexity hinders graph transformers from sealing large datasets. To enhance the scalability of graph transformers, two primary approaches have been proposed, including sparse attention [19, 42] and linear global attention [50, 49, 9]. Sparse methods reduce the density of dense global attention, which, in its original form, corresponds to fully connected graph. The sparsified attention graph contains fewer edges, resulting reduced memory overhead but also smaller receptive fields for each node. In contrast, linear methods preserve pairwise interactions between nodes and reduce complexity by eliminating the need for explicitly computing the dense attention.
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Dip
Cas
02-
Coudiatt
306
Jecee
(a) Average Attention Entropy
(b) Entropy acToss Node Scales
(c) Entropy during Training
Figure I: Over-Aggregating in Graph Transformers. The entropy values normalized to [0, 1]. with higher entropy indicating a more uniform distribution attention scores. (b), we show the attention entropy with different numbers of nodes for Polynormer [9], typical linear attention method.
However, learning from pairwise interactions is challenging due to the large number graph nodes. Fig. 1 illustrates the average attention entropy different models. Attention entropy denotes the confidence the nodes in discriminating informative messages during aggregation. Higher entropy indicates more uniform distribution of attention scores and less confidence. From Fig. (a)), see that linear methods tend to aggregate messages from nodes with higher attention entropy and similar attention scores. When the number of nodes increases in Fig. 1(b), the attention scores become more and more similar. As a result, large volume of messages aggregated into single node with less discrimination, leading potential information loss. We name this uniform aggregation phenomenon as over-aggregating.
To tackle over-aggregating in graph transformers, propose Wideformer, a plug-and-play method for graph attention. Wideformer divides the aggregation of nodes into parallel processes and guides the model to focus specific subsets of these processes. Specifically, the aggregation inputs are divided into distinct clusters, with each cluster aggregated separately. Instead of compressing messages from all nodes into single target node, Wideformer limits the input volumes for each aggregation, thereby avoiding message dilution and reducing information loss. To ensure target nodes focus on the informative messages, the aggregation results sorted and weighed based on the attention scores between the clusters and the target nodes. In contrast to the sparse attention methods that reduce the number of inputs for each target node, Wideformer maintains the global receptive field and distributes the inputs into multiple aggregation processes. By integrating with three popular linear methods GraphGPS [34], SGFormer [51], and Polynormer [9], Wideformer demonstrates effectiveness in tackling over-aggregating. It can consistently benefit the backbones to achieve superior performance baselines. Codes available https: g thub. com/ sunjas/ wwwass//vveeeeeeeeeeeeeeeeeweeee htt///verrrrrrgeeee aeger-gggggtttnng
The contribution of this paper can be summarized as follows:
We discover new phenomenon in graph attention, termed over-aggregating, which aggregates a large volume of messages with less discrimination.
We propose a novel method to relieve vveraggregating, named Wideformer, which divides the aggregation process and guides the model focus on the informative messages.
We demonstrate the effectiveness of Wideformer on thirteen real-world datasets, which consis- tently relieves wver-aggregating and benefits backbones to achieve superior performance.
2
Related Work
GNNs perform message passing input graphs, enabling nodes to learn from their connected neighbors and capture topological features [61]. Among the different message passing methods, GAT [48] first adopts the attention mechanism to aggregate messages. It utilizes attention scores between connected nodes to help central nodes filter out noisy neighbors and focus on the most informative ones. Following GAT, subsequent methods further adopt dense global attention to graphs [23]. A primary challenge for these methods lies in how to effectively encode the graph structure, global attention performs message passing between all pairs of nodes while neglecting

---

the underlying graph structure. Several solutions have been proposed, including combining global attention with GNNs simultaneously encode global features and graph structures [62, 53, 29]. learning positional or structural encodings as node features [62, 11, 10, 19], and incorporating graph structures as an attention bias [55].
Another challenge arising from the dense global attention is a space complexity of On²²). Efforts to address this challenge can be broadly categorized into two approaches: sparse attention and linear global attention. Sparse attention stems from the Big Bird model [59], which utilizes random masks, sliding windows, and partial global masks achieve sparsification traditional transformer architec- tures. Built upon Big Bird, GraphGPS incorporates these sparse mechanisms into comprehensive framework for constructing graph transformers [34]. In addition to Big Bird, GAT. which employs input graphs as attention graphs, can also be considered form of sparse attention. Exphormer [42] and Spexphormer [41] further transform the input graphs into expander graphs, thus better approxi- mating the fully connected graph. However, all of these sparsification methods shrink the receptive fields of each node, leading to a trade-off between model complexity and the ability to capture global information. Different from sparse attentions, Wideformer maintains the global receptive field while requiring linear computing complexity.
In contrast to sparse attention, linear global attention focuses on directly simplifying the computation of dense attention. For example, GraphGPS [34] and Nodeformer [50] extend the linear attention method, Performer [8], from traditional transformer architectures to graph transformers. Performer enables nearly unbiased estimations of dense attention without explicitly computing the attention matrix. In addition to approximation methods, several models have been proposed to model pairwise relations linear time [51, 9]. However, as shown Fig. (a), the linear methods that maintain the global receptive field during aggregation encounter over-aggregating, leading to dilution of important messages and potential loss of information.
3 Over-Agggegg in Graph Transformers
Graph transformers facilitate global or approximated global message passing between nodes. How- ever, extracting informative features from these global interactions becomes challenging the number of graph nodes increases. investigate the behavior of global interactions in graph transformers, we utilize entropy measure of attention scores and examine how graph nodes distribute their attention in the receptive field.
3.1 Attention Entropy
In graph attention, input features are projected into query, key, and value features. The value features are aggregated based on the similarity between the query and key features. Let X E Raxd denote the input node features, where n denotes the number of nodes and d denotes the number of features. Node features are mapped to the query, key, and value features through Q = XW K XWK. K.
and V = XWv, respectively. Let R QK we now have graph attention as
exp (R.,)) Σn (R,,),
H Rijj = sof tmax taaxtmxx RR),,
Given the attention scores (a 1, ann) between the target node v; and all graph nodes, the attention entropy can be formulated as
H(v,) = Σ ois log Oi,j.
To ensure comparable results across different datasets, the entropy values are normalized by log to range [0. 1] for visualizations. Attention entropy measures the distribution of attention scores, indicating the confidence of the target nodes in diseriminating informative messages. Lower entropy indicates that each target node focuses on a subset of graph nodes with higher attention scores (confidence), while higher entropy reflects more uniformly distributed attention and lower confidence.
Fig. ((a) compares the attention entropy sparse attention and linear global attention methods, including linear methods GraphGPS with Performer [34], Polynormer [9], and SGFormer [51], as
3

---

well as sparse methods SAN [19] and Exphormer [42]. The entropy values are averaged over all graph nodes throughout the training process. As shown Fig. ((a), linear and sparse methods exhibit distinct attention distribution patterns. Specifically, sparse methods demonstrate low attention entropy, which can be attributed to their sparsification strategies that enable nodes to filter out noisy messages and focus on the most informative ones. Conversely, linear methods involve all the graph nodes for aggregation and tend to assign similar attention scores in the receptive field, resulting in higher entropy. The distinct distribution patterns of the sparse and linear methods indicate the relation between the number of nodes aggregation and the attention entropy.
Theorem 3.1 (Monotonic Lower Bond of Attention Entropy), Let ax,, E R" be the attention distribution of node v; over n nodes. The attention entropy H(vx) admits a lower bound that increases monotonically with n.
The proof is provided in Appendix A. Theorem 3.1 indicates that graph attention will be more likely to have higher attention entropy when aggregating more graph nodes, which is further demonstrated in Fig. 1(b).
3.2 Over-Aggregating
We refer to the aggregation process with high attention entropy over-aggregating, typically demonstrated as uniform and small attention scores, offering limited discrimination among nodes. As result, over-aggregating prevents graph nodes from prioritizing the informative messages, leading to message dilution and potential information loss.
To empirically evaluate the effect of over- aggeggggggg with high attention entropy, we add an entropy regular- ization term to the optimization loss for linear methods GraphGPS with Performer, SGFormer, and Polynormer. The best results among the three backbones are reported. Tab. shows that directly reducing the attention entropy during training gives rise to better model performance. This indicates that over-aggregating with high attention entropy does harm the model performance. However, although directly regularizing attention entropy during training can benefit model performance, this process re- quires the explicit computation of the whole attention matrix, making it inapplicable to large graphs. As result, remains an open problem to alleviate over-aggregating for learning on graphs.
Table 1: Effect of Over- Over-Aggregan ggregating by Attention Entropy Regularization (Mea- sured by accuracy except for ROC-AUC for minesweeper: %).
ORI
+REG
CORA CITESEER
86.03.0.54
86,23
77.96
78.19 10.39
AMZPHOTO
95.47 20.53
95.52..0.4
MSWEEPER
97.13
97.20 +0.32
Over- Over-aggres aerrgggggggtigggggg stems from the optimization of attention scores. As shown in Fig. ((c), models typically initialized with high attention entropy, which gradually decreases during training. Throughout this process, models update the parameters W Q and Wx with back pack-propagatton, and thus optimize the attention scores. Take Wo an example, the gradient of oi with respect Wa can be derived as
dos.j | = assi as. DWQ
X XX W
Cas X W
(3)
k=1
For more details, please refer to Appendix B. A higher initial attention entropy implies smaller attention scores, which in turn attenuate the signals to update these scores. As a result, models converge with persistently high attention entropy, reflecting suboptimal attention distributions. Eq. can also provide insights for the aggravated over-aggregating problem on large-scale graphs (indicated by Theorem 3.1 and Fig. (bb)
doij aWe
ans (go, Mothera Ciij (1 ai
W
X X WT
(4)
where Je, corresponds to the update signals based on the interaction between node v; and Vj. and Jothers corresponds to the cumulative impact of all other nodes. As the number of graph nodes grows, fothers increasingly incorporates more irrelevant signals, diluting the relative strength of the meaningful update signals in Ivy- This dilution hinders the optimization of or preventing the model from learning discriminative attention distributions and amplifying the over-aggregating issue on large-scale graphs.

---

Global Aggrespation
Divided Global Aggressation
1
2
2
3
4
Selection
Source Asdggnsinn
Contec- Divided Aggregation
Figure 2: Attention Comparison between Global Aggregation and Our Divided Global Ag- gregation. Global attention employs global aggregation to aggregate source messages into one- dimensional representation. To relieve the over-aggregatingg, we assign source nodes into distinct clusters and aggregate each cluster separately, giving rise to multiple aggregation results.
3.3 Discussion
Similar the occurrence of over-aggregating on the attention graphs, recent study highlights phenomenon known over-globalizing in graph transformers, where models struggle to learn from neighboring nodes in homophilic datasets [54]. While wer-globalizzig specifically concerns nodes at varying distances, agggrgggggg focuses on the discrimination of all nodes during aggregation.
In the context of message passing input graphs, over-dilution studies aggregation for both feature dimensions and neighboring nodes [21]. Specifically, intra-node dilution focuses on the volumes of the node features, while inter-node dilution focuses whether node's information is preserved during aggregation. Different from over-dilution, over-aggregating focuses on the volumes of the input nodes and emphasizes the preservation of messages from the informative nodes, regardless of whether that includes the node itself.
Besides over- over-dilution, over-smoothing occurs when node features become increasingly similar as the number of layers grows [30]. This results from the low-pass aggregation among connected nodes in the imput graph. In contrast, over vver-aggregating occurs the attention graph due to the large number nodes in the global receptive field. Designing high-pass aggregating functions can tackle over-smoothing. Conversely, for over-aggregating on graph transformers, behavior desired, the optimization of attention weights may still be hindered by the overwhelming number nodes involved in aggregation.
when high-pass
Another notable issue on input graphs is over-squashing, which occurs when message pathways include edges with negative curvatures. It leads to exponential expansion of the receptive field the message- -aaggggggaginggggg distance increases [1]. In consequence, a large volume of messages is compressed into nxed-dimensional representations, impeding the effective message exchange between long-rang, nodes. Unlike over-squashing that occurs during multi-step message passing, over-aggregating arises in one step. It aggregates large volume of messages into a single node with limited discrimination, leading to the loss of informative messages from one-hop neighbors.
4 Wideformer: Relieving the Over-Aggregating
Based on the analysis in Sec. 3, global attention, including both dense and linear methods, faces a critical trade-off between mitigating aggeegggggg and maintaining global receptive field. To address this challenge, we propose Wideformer, plug-and-play method designed to enhance graph transformer backbones. Unlike sparse attention methods that reduce the input volume, Wideformer maintains the total inputs and increases the output volume. Specifically, it partitions the inputs into distinct clusters, giving rise multiple aggregation results for each node and guiding the nodes to focus on the informative clusters. The following subsections detail the two key components of Wideformer: dividing the aggregation and guiding the attention.
4.1 Dividing the Aggregation
Message passing involves aggregating messages from source nodes target nodes. For each target node ;; global attention, treats all the input nodes {u;}. E {1,..., .n. as the source nodes, and aggregate messages V based on the attention scores between its query features Q, and the
5

---

source key features K,, As result, messages from all source nodes at each feature dimension are compressed into mnggl-dimmenional representation, leading to the potential dilution of the key messages.
To relieve the dilution, we propose divide the source nodes into different clusters based on their attention scores and aggregate each cluster separately. Therefore, source nodes with the highest level of attention can be ag- gregated together, excluding the other nodes and relieving the message dilution. However, explicitly computing the attention matrix re- quires a space complexity of O(?2). To ad- dress this issue, Wideformer approximates the division with attention scores by first selecting cluster centers among the query features, and then assigning the source nodes to the clusters based on the similarity between their key features and the centers.
Algorithm Center-sclection Function Cluster
Input: query Q _ number of clusters m Initialize center C = [0)mx)
C1, Qt... = arg max; Σ, Qu.
for to m
Compute distances: q = max, [QQC ).3]
Select next center indices: g arg mig
Update centers: Cr Qg.
end for Output: centers R2mx
Let m be the number of clusters, C = Cluster( (Q, m) E mR be the cluster centers. The center- implemented based on K-Means++ [3]. The query
selection function Cluter Algorithm of the source node with the largest summation across feature dimensions is selected as the initial cluster center. Notably, this initial center is solely used to initiate the selection process and does not participate in the aggregation. Cluter then select m centers sequentially, where the node that minimizes the maximum similarity to all previously selected centers is designated as a new cluster center.
The source nodes are assigned to the identified query clusters based on the similarity between and C. The assignment result k E R" can be formulated as
(KCT).. 1.j.
k;
arg max
(5)
By performing aggregation within distinct clusters, Wideformer produces multiple outputs for each target node. The aggregation result of the t-th cluster H(t) guxd can be formulated as
H
Σ
softmax roftmax(QK].))
(6)
=E()),=t
To illustrate the effect of aggregation, for each target node u; and the j-th feature dimension of the source message V. the original aggregation method in Eq. I compresses messages from all nodes into -in-dmmeniional representation H.g. which leads to the dilution of key messages and over- wve--aggregating contrast, Wideformer with Eq. increases the output volume, yielding a
m-dimensional representation ( H. (m),
j ). Only limited volume of messages is aggregated for each cluster, preventing the dilution the key messages. Even when the target nodes apply uniform attention scores to the source nodes, the messages in different clusters remain separate from being wer-agggeeated.
4.2 Guiding the Attention
The aggregation results (H()).... .......... (m)) are concatenated for the subsequent modules in backbones. During the concatenation, the current ordering of the aggregated results depends on the cluster- selection order. However, since each target node assigns different attention scores to the clusters, this order does reflect the importance of each cluster for the target node. To ensure consistent ordering and enable the target nodes to focus on the informative clusters, Wideformer sorts and weights the clusters for each target node based on the cluster attention score مر,ة E Raxm. These scores can be formulated as
ãi = sof tmax QK Jas.
K,,-
K,.,
Huilk = tH
kEU/k,=t)
where K E Rm denotes the average key features of the clusters. aggregation result A'()) E I is then obtained as
The sorted and weighted
A a.s. H. (S..)
S., arg sort, (ār,]
(8)

---

Table 2: Comparison Results Homophilic Datasets (Measured by accuracy: %). OOM indicates out-of out-of-memory under the experimental setups.
AMAZONCOMPUTERS
COAUTHORCS
AMAZONPHOTO
COAUTHORPHYSICS
#NODES
13,381
18,333
7,487
34,493
#FEATURES
767
6,805
745
8,415
#CLASSES
10
15
8
5
GCN
89.65
92.92
92.70-0.20
96.18
GRAPHSAGE
91.20 20:29
93.91 10:13
94.59_o0
96.49
GAT
90.78 10.13
93.61 10.14
93.87=0.0
96. 96.17=0.08
GPRGNN
89.32 +0.29
95.13 60009
94.49 -0.19
96.85=0..
NAGPHORMER
91.19 #0.14
95.75 +.0.09
95.49 =0.11
97.34-0.00
NODEFORMER
86.98 +0.62
95.64 +0.22
93.46=0.85
DIFFORMER
91.99
94.78 2:0.2
95.10
96.60
GOAT
90.96+0.90
94.21 +0.38
92.96
96.24_.o..
EXPHORMER
91.47
94.93 +0.01
95.35
96.89 -0.89
GRAPHGPS
90.62
95.44-20.05
94.98 -9.16
96.75 155_0.07
+ETROOP REG
90.68 20:37
95.50 20.19
95.28 25.28_0.22 20.2
OOM
WIDEFORMER
90.84 10.57
95.85 20.07
95.55 20.74
96.95 _0.00
SGFORMER
91.66:00.2
93.50 #0.32
95.47
96.87=o0
ENTROPY REG
91.78 20:37
93.59
95.51-0.49
96.88
WIDEFORMER
92.1910.17
93.8610.41
95.64_9..
97.39
POLYNORMER
91.98 60.09
94.53 #0.01
95.47 -0.65
96.67 =0.20
ENTROPY REG
92.08 20.07
94.57 40.44
95.52-0044
96.69 =0.31
92.39 10:07
94.60.0.0
95.64 -0.36
96. 79
where arg returns the indices of the sorted elements in ascending order. Eq. 7 and 8 inject the importance of each cluster into the aggregation, guiding the focus of the target nodes. The weighted results concatenated for the following computation.
5
Experiment
To evaluate the effectiveness of Wideformer, we conduct empirical evaluations on real-world datasets. The detailed setups are presented in Appendix D.
5.1 Effectiveness in tackling Over-Aggregating
Wideformer is evaluated three linear methods, including GraphGPS with Performer [34], SGFormer [51], and Poly- normer [9]. To ensure consistent comparison, these methods are implemented under the framework of GraphGPS. As pre- sented in Fig. (a)), Wideformer can effectively reduce the attention entropy of all backbone methods. This reduction allows target nodes focus on informative source nodes within the global receptive field, effectively preventing the dilution of key messages and mitigating vvrragggeg.
(a) Attention Entropy Comparison
0.17
However, Wideformer without the ineention-guddigg process still exhibits high attention entropy in Fig. 3(a). This partial method only avoids message dilution but fails to effectively guide the attention of the target nodes. To further investigate the attention-guiding process in Wideformer, we conduct an empirical analysis of cluster attention a. As shown in Fig. 3(b), Wideformer provides low cluster attention entropy for all three backbones, indicating that only subset of input messages is crucial for the target nodes. The attention- guiding process Wideformer allows backbone methods concentrate on these informative subsets, enhancing their ability to mitigate over-aggrogating. As the number of nodes increases, GraphGPS and SGFormer exhibit increasingly divergent attention scores across clusters, while Polynormer maintains much lower cluster attention entropy, albeit with slight upward trend. This indicates that Wideformer consistently supports different backbone methods in prioritizing informative messages, even when the graph size grows.
0.000
10
(b) Cluster Attention Entropy
Figure 3: Effectiveness Evaluation for Over-Aggregating, "+ Ours" de- notes using proposed Wideformer. "+ Ours w/o. Guide" employs Wide- former without attention guidance.
7

---

Table 3: Comparison Results Heterophilic Datasets (Measured by ROC-AUC except for accuracy for amazon-ratings and roman-empire: %). OOM indicates out- -ut-of-memory under the experimental setups.
AMAZON-RATINN
MINESWEEPER
QUESTIONS
TOLOKERS
#NODES
24,492
10,000
48,921
22,662
11,758
#FEATURES
300
301
300
SCLASSES
18
GCN
48.70
89.75.00552
76.09
73.69.0.74
83.64:0.07
GRAPHSAGE
53.63
93.51 20.07
76. 26.44.0.02
85.74 85.74=0.07
82.43
GAT
52.70=0.62
90.91
76.79=0.77
88.75+0.41
83.78 +0.43
GPRGNN
44.88
86.24
55.48 10.91
64
72.94.000
NAGPHORMER
51.26::072
84.19.go.0
68.17 21133
24.34.0.11
78.32
NODEFORMER
43.86
86.7 #0.88
74.27 :::46
64,49 o0.7a
78.10=1.00
DIFFORMER
47.84.0.65
90.89 0.89%.0.58
72.15 11:31
79.10
83.57 #.066
GOAT
44.61 +0.50
81.09=1.00
75.76=1.00
71.59
83. #:104
EXPRORMER
53.51
84.19.
73.94
89.03
83.77 +0.75
GRAPHGPS
49.73
93.26
75.48 20..0
81.46:0.c0
83.95 :.0.81
+ENTROPY REG
0OM
93,35 0.35==0.20
OOM
OOM
84.23 =0.51
WIDEFORMER
49,96.0.44
93.52
75.69 =1.17
82.12=0.30
84.67 #0006
SGFORMER
52.38
88.60
76.81 20.00
25.20
82.24
-ENRROPY REG
52.86
88.87 20.33
76.83 20.18
75.84
82.39 #0.19
WIDEFORMER
53.47..0.14
89.02.20.2
26.94.0.05
77.03
82.55 10000
POLYNORMER
54.71 10.17
97.13
78.66 20.50
11
85.09 g0.21
-NTROPY REG
54.79.9.03
97.20
78.69 20:24
91.94
85.21 10:30
WIDEFORMER
55.05 50.08
97.26 :0.01
79.00 -0.20
92.16 :0.24
85.33 60.28
Table 4: Comparison Results on Datasets with Broader Scales (Measured by accuracy: %). OOM indicates
out-of-memory under the experimental setups.
DGB-ARXIV
CrrnSena
CORA
TWIFCH-GAMER
WNODES
169,343
3,327
2,708
168,114
NFEATURES
126
3,703
1.435
#CLASSES
7
GCN
71.74_009
71.60.0.0
81 (M to
62.18
GRAMISAGE
71.49 71.49-007
71.93.0.5
82.68 82.68.0.47
64,37 64.37.10.0
72.10-1.0
83
EXPRORMER
71.63.1119
21.77
64.30
GRAPIGPS
70.47 1.55
77.96
86.03
64,98 10:20
Sumder Ogf
-ENTROP REG
OOM
78.19
86.23
0OM
Figure 4: Time Cost on GraphGPS. The point shape "" denotes the whole model and "*" denotes the Wideformer part. The color of the points indicates the number of the clusters m.
WIDEFORMER
70.66.1.89
10.35
86.70_o.55 20.55
65.46.0.00
SGFORMER
72.23.6.73
69.93
80.83 10.52
65,85 10.02
*ENTROPY REG
ODM
70.12
81 01,044..1
0OM
WIDEFORMER
72.58
70.63
81.20
66.34
POLYNORMER
70.77
66.43
78. 78.70.... 20.9
67.15
-ENTROPY ReG
0DM
67.21
79. 28 20.0
0OM
-WIDFFORMER
70.85
68.10..0.4
79.90
67.33
5.2 Model Comparison
Experimental Setup. We adopt thirteen real-world datasets, including both heterophilic and homophilic graphs. For baseline methods, both GNNs and graph transformers are adopted. Please refer to Appendix D.2 for detailed experimental setups. To address the out-of-memory issue associated with the entropy regularization bascline, we divide the target nodes into mini-batches. Each batch is sequentially processed to compute attention scores with all source nodes. The results of the backbone methods GraphGPS with Performer, SGFormer, and Polynormer are reproduced under the framework of GraphGPS.
Performance. We present the comparison results on datasets where the number of nodes is around 10k in Tab, 2 and Tab. 3. Wideformer consistently enhances the performance of all backbone models across various datasets. Specifically, backbones integrated with Wideformer achieve superior perfor- mance compared to baseline methods. For instance, in Tab. 2, Wideformer enables backbone methods to outperform the previous perforrnn baselines, including DIFFormer on AmazonComputers and NAGphormer on CoauthorsCS, CoauthorPhysies, and AmazonPhoto Compared to the entropy regularization method, we can see that regularizing entropy results in inferior performance to Wide- former and even marginal gains on larger graphs. This is consistent with our analysis in Sec. 3.2. Entropy regularization does not divide the aggregation process, and thus suffers from optimization challenges when aggregating over a large number of source nodes. In contrast, Wideformer separates
8

---

the aggregation into parallel processes. Each process only involves small ratio of the source nodes to be aggregated, preventing the dilution of the key messages. We also compare the gains with zero to evaluate the statistical significance of the performance gains. Paired t-tests on all backbones consistently give rise to p-values smaller than 0.05, and the confidence interval results do not contain 0, validating the statistical significance of the performance gains with Wideformer. These results demonstrate that relieving over-aggregating improves the effectiveness of graph attention.
To further verify Wideformer's ability to mitigate over-aggregating, we extend our experiments to datasets with broader node scales, including 1k and 0.1M nodes. Results in Tab. 4 show that Wideformer can benefit backbones with different scales of nodes, Among the three backbones, SGFormer achieves better results on large-scale graphs ogb-arxiv and twitch- twitch-gamer, but inferior results on small-scale graphs CiteSeer and Cora. This is due to the trade-off between noise filtering and information loss in SGFormer, which is further investigated in Sec. 5.3.1.
5.3 Model Analysis
0.4
Graphaha
033
5.3.1 Informative Source Nodes
Wideformer empowers backbone methods to focus on informative source nodes within the global receptive field. To investigate the attention mechanism in Wideformer, we conduct additional experiments on source nodes assigned to the cluster with the highest attention score, analyzing both their volumes and their relations with the target nodes.
Number of kode
Figure 5: Informative Source Node Ra- tio. The ratio is the number of nodes assigned to the cluster with the highest attention score relative to the total num- ber of graph nodes.
Node Ratio. To analyze the node volume, we calculate the ratio of nodes assigned to the cluster with the high- attention score relative the total number of graph nodes. As shown in Fig. 5, the node ratio decreases as the total number of nodes increases. This suggests that the proportion of informative nodes diminishes in larger graphs, leading noisier source messages. Wideformer addresses this by assigning smaller ratio of nodes to the cluster with the highest attention score, guiding the back- bones to focus on the most informative nodes. Among the three backbones, SGFormer focuses on fewer source nodes than GraphGPS and Polynormer. This results in a trade-off between noise filtering and information loss, where SGFormer performs better on large-scale graphs (ogb-arxiv and twitch-gamen but lags behind on smaller graphs (CiteSeer and Cora).
335
Datavea
Figure 6: Node Relations. Label/Edge denotes the ratio of source nodes sharing the same label/connected with the target nodes.
Node Relations. To analyze the relations between target and source nodes in the cluster with the highest attention score, we compute the ratio of the source nodes (1) that have the same label as the target nodes, and (2) that are connected with the target nodes, both relative to the total number of source nodes in the cluster. The results with GraphGPS are presented in Fig. 6. For the other two backbones, please refer to Appendix E. As shown in Fig. 6, we can that approximately 10% of source nodes are connected with their target nodes. The label distribution diverges between heterophilic graphs and homophilic graphs, where target nodes assign larger attention scores to the same-class source nodes on heterophilic graphs.
5.3.2 Complexity Analysis
The time and space complexity of Wideformer is 0(mm), where n and m denote the number of nodes and clusters, respectively. In practice, m is chosen from [2...., 8}, which ensures the model's s scalability to large graphs. We provide a time cost study regarding the number of nodes (n) and clusters (m), comparing the whole model with the part of Wideformer. The results on GraphGPS are presented in Fig. 4, where the time cost of Wideformer scales linearly to n and remains a small ratio of the total cost. For detailed experimental setup and full results, please refer to Appendix F.

---

5.3.3 Model Ablation
To evaluate the contribution of the aggregation-dividing and attention-guiding process in Wideformer, we conduct an ablation study on the three backbone methods.
Cluster Ablation. Wideformer partitions the source nodes into distinct clusters. To examine the impact of this division, we perform an ablation study on the number of clusters m regarding performance gains. The gain is
Scforar
0.1
defined as Pm-Pi, where and Pm denote the perfor- Pl mance with a single cluster and m clusters, respectively. The average performance gains across various datasets for all three backbones are shown in Fig. 7. We can see that increasing the number of clusters initially increases the performance gain. However, when m exceeds 6, the performance gain starts to decline. This because rel- atively larger number of clusters can effectively reduce the input message volume, mitigating the dilution of key information. Nevertheless, excessively partitioning the source nodes disperses critical information into multiple clusters. This leads to the distracted attention of the target nodes, reducing the values of attention scores and increasing attention entropy. In practice, the optimal number of clusters is around 3 ~ 5.
0.1
0.1
Number Clsters Ind
Figure 7: Comparison with Different Numbers of Clusters.
Center Selection. To ensure computing efficiency, Wideformer employs non-iterative strategy for cen- ter selection. We now compare this simple choice with (1) multi-step iterative clustering and (2) param- eterized centers, to shed light on the future direc- tions. Tab. 5 shows that applying iterative clustering can achieve better results, indicating the efficiency- performance trade-offs. Further modeling centers parameters can address this trade-off, which does not require iterations and achieves the best results.
Table 5: Comparison the Center Se- lection Methods. Results are averaged on amaazon-ratnngs, questions, CoauthorCS, and AmazonPhoto.
GRAPEGPS
SGFORMER
POLYNORMER
ORIGINAL
78.01.0.34
$.44...
20.45
WIIDEFORMER
79.26.n.19
9.. 99.98_..20
81.07anaa
+ITER=2
79.93 45
80.5 20.58_..01
81 1..44..m
+ITER-4
79.95.0.17
80 80.42:00.7
$1.43
+
79.85
80.55
81.52
50.60_0.30
81.54gm
Module Ablation. Tab. 6 shows that combining divided aggregation and attention guidance gener- ally achieves better performance. However, using only divided aggregation can also benefit the back- bones, such as on CoauthorCS and AmazonPhoto with Polynormer. This likely due to the simple attention-guiding strategy, which directly determines the importance of each cluster as a whole. Under circumstances where fewer source nodes contain in- formative messages, this simple strategy leads to lim- ited benefit capability. Exploring alternative guiding strategies will be the focus of our future work.
Table 6: Module Ablation Results (Mea- sured by accuracy: %). "Div."/'ll" de- notes the divided aggregation without/with ditention-guidance
AMAZON RATINUS
COAUTHOR CS
AMIAZON
BOSSAN
Pistro
GRAPHIGPS
49.75ana1
9E.9%
81.46gr.00
+IIIV
19.58
98.
81 ....
c.:11
95.65
19:24
10.00
SOPORMER
03.50
$2.42.0.5
93.53....1
10.34
93.86 c0.4
POLYNOEMER
34.712017
94.352044
54.82
96.60...2
6 Conclusion
In this paper, we discovered phenomenon in graph attention, termed over-aggregating, Attention with over-aggregating assigns uniformly distributed attention scores to the messages. As result, the key messages are diluted during aggregation, leading to potential information loss. To relieve this problem, we proposed a novel alug-and-plan method, Wideformer. Wideformer divides the source nodes for aggregation into distinct clusters and aggregates each cluster separately. To ensure focus on the informative source nodes, Wideformer applies attention guidance to sort and weight the clusters. Experiments on thirteen datasets show that Wideformer can consistently enhance the performance of backbones and effectively relieve over-aggregating. Please refer to Appendix. for the limitation discussion.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Key R&D Program of China under Grant 2023YFC2508704, in part by the National Natural Science Foundation of China 62236008, and in part by the Fundamental Research Funds for the Central Universities. The authors would like thank the anonymous reviewers for their helpful comments and suggestions that improved this manuscript.
References
[1] Uri Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications. In International Conference on Learning Representations, Virtual Only, 2021.
[2] Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid. ViViT: A Video Vision Transformer. In IEEE/CVF International Conference on Computer Vision, pages
2021.
[3] David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. In ACM-SIAM Symposium on Discrete Algorithms, pages 1027-1035, USA, 2007. Society for Industrial and Applied Mathematics.
[4] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: Tokenized Graph Transformer for Node Classification in Large Graphs. In International Conference for Learning Representations, 2023.
[5] Junxi Chen, Liang Li, Yunbin Tu, Li Su, Zhe Xue, and Qingming Huang. Generalizing single- frame supervision to event-level understanding for video anomaly detection. The Thirty-ninth Annual Conference on Neural Information Processing Systems.
[6] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster- GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Anchorage AK USA, 2019. ACM.
Data Mining, pages 257-266
[7] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. International Conference on Learning Representations, virtual, 2022.
[8] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking Attention with Performers. In International Conference on Learning Representations, 2020.
[9] Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-Exppesssiee Graph Transformer Linear Time. International Conference on Learning Representations, 2023.
[10] Vijay Prakash Dwivedi and Xavier Bresson. A Generalization of Transformer Networks to Graphs. In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
[11] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph Neural Networks with Learnable Structural and Positional Representations. 2021.
[12] Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with PyTorch Geo- metric. In International Conference on Learning Representations Workshop on Graphs and Manifolds, 2019.
[13] Benjamin Gutteridge, Xiaowen Dong, Michael M. Bronstein, and Francesco Di Giovanni. DRew: Dynamically Rewired Message Passing with Delay. In International Conference on Machine Learning, pages 12252-12267. PMLR, 2023.
[14] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In International Conference on Neural Information Processing Systems, pages 1025-1035, Red Hook, USA. 2017. Curran Associates Inc.
11

---

[15] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems, volume 33, pages 22118-2218 Curran Associates, Inc., 2020.
[16] Nam Hyeon-Woo, Kim Yu-Ji, Byeongho Heo, Dongyoon Han, Seong Joon Oh, and Tae-Hyun Oh. Scratching Visual Transformer's ' Back with Uniform Attention. In 2023 IEEE/CVF International Conference on Computer Vision (ICCV), pages 5784-5795, 2023.
[17] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations, Toulon, France, 2017.
[18] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A Global Transformer on Large-scale Graphs. In Proceedings of the 40th International Conference on Machine Learning, pages 17375-17390. PMLR, 2023.
[19] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létoureau, and Prudencio Tossou. Rethinking Graph Transformers with Spectral Attention. In Advances in Neural Information Processing Systems, volume 34, pages 11618-21629 Curran Associates, Inc., 2021.
[20] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-Attention Graph Pooling, In International Conference on Machine Learning, pages 3734-3743, Long Beach, California, USA, 2019, PMLR.
[21] Junhyun Lee, Veronika Thost, Bumsoo Kim, Jaewoo Kang, and Tengfei Ma. Understanding and Tackling Over-Dilution in Graph Neural Networks. In Proceedings of the 31 ACM SIGKDD Conference Knowledge Discovery and Data Mining V.2, pages 1253- 1261, New York, NY, USA, 2025. Association for Computing Machinery.
[22] Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. attp://snaee http://aap...aafffeeeee/eeaaaaas stanf data, 2014.
[23] Yuan Li, Xiaodan Liang, Zhiting Hu, Yinbo Chen, and Eric P. Xing. Graph Transformer. 2018.
[24] Derek Lim, Felix Hohne. Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large Scale Learning on Hommoooophilos Graphs: New Benchmarks and Strong Simple Methods. In Advances in Neural Information Processing Systems, volume 34, pages 20887-20902. Curran Associates, Inc., 2021.
[25] Jinzhe Liu, Junshu Sun, Shufan Shen, Chenxue Yang, and Shuhui Wang. Edit Less, Achieve More: Dynamic Sparse Neuron Masking for Lifelong Knowledge Editing in LLMs, 2025.
[26] Shih-yang Liu, Chien-Yr Yi Wang, Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang, Kwang-Ting Cheng, and Min-Hung Chen. DoRA: Weight-Decomposed Low-Rank Adaptation. In Forty-First International Conference on Machine Learning, 2024.
[27] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin Transformer: Hierarchical Vision Transformer using Shifted Windows. In JEEF/CVF International Conference on Computer Vision, pages 9992-10002, 2021.
[28] Diego Mesquita, Amauri H. Souza, and Samuel Kaski. Rethinking pooling in graph neural networks. arXiv:2010.1144 [cs), 2020.
[29] Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding Graph Structure in Transformers. arXiv:2106.05667 [cs], 2021.
[30] Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference for Learning Representations, 2021.
[31] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach Viti Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In International Conference on Neural Information Processing Systems, pages 8026-8037 Red Hook, NY, USA, 2019. Curran Associates Inc
12

---

[32] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look the evaluation of GNNs under heterophily: Are we re- ally making progress? In The Eleventh International Conference on Learning Representations, Kigali, Rwanda, 2023.
[33] Saeed Rahmani, Asiye Baghbani, Nizar Bouguila, and Zachary Patterson. Graph Neural Networks for Intelligent Transportation Systems: A Survey. IEEE Transactions on Intelligent Transportation Systems, 24(8):8846-8885, 2023.
[34] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. In Advances Neural Information Processing Systems, volume 35, pages 14501-14515 New Orleans, USA, 2022.
[35] Giorgos Savathrakis and Antonis Argyros. Enact: Entropy-Band Basped Clustering of Attention Input for Reducing the Computational Needs of Object Detection Transformers. In 2025 IEEE International Conference on Image Processing (ICIP), pages 295-300, 2025.
[36] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective Classification in Network Data. Al Magazine, 29(3);93, 2008.
[37] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation. arXiv: I. 1.05868 [cs, star], 2019.
[38] Shufan Shen, Zhaobo Qi, Junshu Sun, Qingming Huang, Qi Tian, and Shuhui Wang. Enhancing Pre-trained Representation Classifiability can Boost its Interpretability. In The Thirteenth International Conference on Learning Representations, 2024.
[39] Shufan Shen, Junshu Sun, Qingming Huang, and Shuhui Wang. VL-SAE: Interpreting and Enhancing Vision-Language Aligmment with a Unified Concept Set, 2025.
[40] Shufan Shen, Junshu Sun, Xiangyang Ji, Qingming Huang, and Shuhui Wang. Expanding Sparse Tuning for Low Memory Usage. In Advances in Neural Information Processing Systems, volume 37, pages 76616-76642, 2024.
[41] Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff, and Danica Sutherland. Even Sparser Graph Transformers. In Advances in Neural Information Processing Systems, volume 37, pages 71277-71305, 2024.
[42] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica Sutherland, and Ali Kemal Sinop. Exphormer: Sparse Transformers for Graphs. In International Conference on Machine Learning, volume 202, Honolulu, USA, 2023. PMLR.
[43] Junshu Sun, Shuhui Wang, Xinzhe Han, Zhe Xue, and Qingming Huang. All in a row: Compressed convolution networks for graphs. In International Conference on Machine Learning, volume 202, pages 33061-33076, Honolulu, USA, 2023. PMLR.
[44] Junshu Sun, Shuhui Wang, Chenxue Yang, and Qingming Huang. Scalable Graph Compressed Convolutions, October 2024.
[45] Junshu Sun, Chenxue Yang. Xiangyang Ji, Qingming Huang, and Shuhui Wang. Towards Dynamic Message Passing on Graphs. In Conference on Neural Information Processing Systems, December 2024.
[46] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference for Learning Representations, 2021.
[47] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In International Conference on Neural Information Processing Systems, pages 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc
13

---

[48] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liō, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations. Vancouver, Canada, 2018.
[49] Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion. In The Eleventh International Conference Learning Representations, 2023.
[50] Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. NodeFormer: A Scal- able Graph Structure Learning Transformer for Node Classification. In Advances in Neural Information Processing Systems, 2022.
[51] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations. In Conference on Neural Information Processing Systems, 2023.
[52] Yue Wu, Zhaobo Qi, Junshu Sun, Yaowei Wang, Qingming Huang, and Shuhui Wang. Video Language Model Pretraining with Spatio-temporal Masking. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8557-8567, 2025.
[53] Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph Gonzalez, and Ion Stoica. Representing Long-Range Context for Graph Neural Networks with Global Attention. In Advances in Neural Information Processing Systems, volume 34, pages 13266-13279. Curran Associates, Inc., 2021.
[54] Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is More: On the Over- Globalizing Problem in Graph Transformers. In International Conference on Machine Learning, pages 54656-54672. PMLR, 2024.
[55] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do Transformers Really Perform Bad for Graph Representation? In Advances Neural Information Processing Systems, volume 34, pages 28877-28888. Curran Associates, Inc., 2021.
[56] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical Graph Representation Learning with Diffcrentiable Pooling. Advances in Neural Information Processing Systems, volume 31, pages Associates, Inc.
Montréal, Canada, 2018. Curran
[57] Hao Yuan and Shuiwang Ji. StructPool: Structured Graph Pooling via Conditional Random Fields. In International Conference on Learning Representations, Addis Ababa, Ethiopia, 2020.
[58] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph Transformer Networks. In Advunces in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[59] Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Trans- formers for longer sequences. In International Conference on Neural Information Processing Systems, pages 17297, Red Hook, NY, USA, 2020. Curran Associates Inc.
[60] Sheheryar Zaidi, Michael Schaarschmidt, James Martens, Hyunjik Kim, Yee Whye Teh, Alvaro Sanchez-Gonzalez, Peter Battaglia, Razvan Pascanu, and Jonathan Godwin. Pre-training via Denoising for Molecular Property Prediction. In The Eleventh International Conference on Learning Representationss 2023.
[61] Bohang Zhang, Guhao Feng. Yiheng Du, Di He, and Liwei Wang. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehmaa Tests, In Proceedings of the 40th International Conference Machine Learning, pages 41019-41077. PMLR, 2023.
[62] Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-Bert: Only Attention is Needed for Learning Graph Representations. arXiv:2001.05) 05140 [cs, stat), 2020.
14

---

A Proof for Monotonic Lower Bound of Attention Entropy
Lemma A.I (Lower Bound of Attention Entropy). Let cii,- E "R. be the attention distribution of node Vi over n. nodes. Suppose each entry satisfies Cz 2 < Then the attention entropy H(e.)
admits the following strict lower bound:
H(u)) 2
1)c] (n 1)c] (n log
Proof. Assume e > O is lower bound for all elements of og,.. The minimum entropy under this constraint is attained when entry takes the maximum possible weight and the remaining (n 1) entries equal e, i.e.
a, (1
E..,,)...
The attention entropy of this distribution
(1:)(()) - [1 - (n - 1)e] log -1- (n 1)e] - (n 1)e log
Since the Shannon entropy strictly concave, any deviation from this distribution increases entropy. Therefore, for any valid distribution a,,, with elements bounded below by e, it holds that
H(v)) 2 (vs)
We now provide the proof for Theorem 3.1 based on Lemma A.1.
Theorem 3.1 (Monotonic Lower Bound of Attention Entropy). Let ai., E IR be the attention distribution of node v, over n nodes. The attention entropy H(v;) admits a lower bound that increases monotonically with n.
Proof. To show that Hmain increases monotonically with n, compute its derivative with respect to
(7Hmia(e)) = é log [1
(n 1)c] + (n 1)c]
log 6
dn
[1 (n 1)c
é log [1
(n 1)(] + 6 logge
clog 1 (n 1)e
+
Since o;, (1 (n 1)c,e,... c,.. denoting the most non-uniform distribution a,, requires 0 << e < i/n, follows that - (n - 1)e 2 and thus
d'Hmin (v:) O. dn
This confirms that Hmin (w:) increases monotonically with
B Detailed Derivation
In this section, we provide a detailed derivation for Eq. 3. Let R = QK Given the attention scores formulated in Eq. 1. the gradient of as with respect to We be derived
dai, aWQ
0as.j ÜR,
2R We
k=/
Oij (6i. (.jik) OW Q
x,
Wo
k=1
Σ Oii (dijk - -Gi X X W
k=
X X,,,,,, W - E X WT)
=0i
1=1
where 65,4 is sign function. When k = j. 8g otherwise 89 0.
15

---

Table S7: Comparison Results with Entropy Regulation the Cluster Attention (Measure by accuracy: %). "Reg." denotes employing the attention entropy of the cluster attention scores as part of the optimization target.
ROMAN-EMPIRE
COAUTHORCS
GRAPHGPS
81.46
95.44
+ WIIDEFORMER
82.12
95.85
+ WIDEFFOMMRR W/ REG.
82.23
96.14
SGFORMER
75.20
93.50
+ WIDEFORMER
77.03
93.86
+ WIDEFORMER w/ REG.
77.83
94.16
POLYNORMER
91.83
94.53
WIDEFORMER
92.16
94.60
WIDEFORMER W/ REG.
92.36
95.42
C Over-Aggregating Measurement
In this paper, we propose employ entropy quantify over-aggregating. This stems from the observation that the attention scores distribute uniformly among different source nodes. To quantify the uniformity of the distribution,
adopt entropy the measure following the common practice in the community [56, 6, 32]. Except for entropy, other potential metrics include standard deviation (STD). Kullback-Leiin Leibler divergence (KLD), and Jensen- -haennnn divergence (JSD). STD focuses on the dispersion of values. When the total number of values is large, but the number of dispersed values small, the STD may remain small despite the distribution being uneven. Therefore, using STD to assess uniformity is not an accurate approach. KLD and JSD are used to assess the similarity between two distributions. can measure the uniformity of distribution by setting the reference distribution to be uniform. However, when the reference distribution is uniform, KLD equals the difference between the maximum entropy and the entropy of the given distribution, while JSD can be viewed as combination of entropy and KLD. Therefore, we opted for the simpler and more commonly used entropy to directly measure the uniformity.
Entropy also demonstrates effectiveness in benefiting model performance. In addition to the entropy regularization method on the whole attention matrix (Tab. 1), we compute the entropy of the cluster attention scores in Wideformer and employ the results part of the optimization target. Results on roman-empire and CoauthorCS in Tab. S7 show that optimizing the cluster attention entropy for backbones with Wideformer can also benefit the model performance. This also indicates that the value of the attention entropy properly quantifies over-aggregating.
In Fig. 3(a), more significant entropy reduction occurs on Polynormer, but its associated performance gains superior to those of the other backbone architectures. This is due the distinct architectural design of the backbones. Different architectures inherently prioritize different attention patterns for optimal representation learning. While high attention entropy consistently indicates aver-gggrg the optimal entropy level varies across models. Thus, although Polynormer exhibits the most significant entropy reduction, this may still fall short of what is needed for its optimal performance.
D Details Experiments
D.1 Datasets
We adopt thirteen real-world datasets, including heterophilic graphs (amazon-ratings, minesweeper, questions, roman-empire, tolokers [32], and twitch-gamer [24]) and homophilic graphs (Cora, CiteSeer [36], CoauthorCS, CoauthorPhysics, AmazonComputers,, AmazonPhoto [37]. and ogb- arxiv [15]).
Questions is derived from Yandex Q, spanning user activity from September 2021 to August 2022. Nodes represent users interested in "medicine" and edges indicate answers to others' questions. The binary classification task predicts whether users remained active without account deletion or blocking. Node features are averaged FastText embeddings of profile descriptions.
16

---

Amazon-ratings is based on the Amazon product co-purchase network from the SNAP Datasets [22]. Nodes represent products, and edges capture frequent co-purchase relationships The task predict the average reviewer rating for each product, grouped into five ordinal classes. Node features are the average FastTText embeddings of product descriptions.
Tolokers represents crowdsoureing participation data from the Toloka platform. Nodes correspond contributors ("tolokers") active at least one of 13 projects, with edges connecting those who completed the same tasks. The binary classification task predicts whether tolokers were banned from projects. Node features include profile attributes and task performance statistics.
Minesweeper is a synthetic 100x 100 grid graph where nodes represent grid cells, with 20% randomly assigned as mines. The task is to classify nodes mines non-minn non-mines. Node features one-hot vectors encoding the count of neighboring mines, but 50% of nodes have their features reset to unknown values, marked by binary indicator.
twitch-gamer collected from the Twitch website with nodes representing users. Only users with mutual relations are incorporated in the dataset. The task is to predict whether the user accounts contain explicit content.
Cora and CiteSeer are citation graphs. In the Cora dataset, machine learning papers are grouped into seven distinet classes, while the CiteSeer dataset categorizes papers into six classes. Node features are derived from
words appearing in the content of the papers.
CoauthorCS and CoauthorPhysies derived from the Microsoft Academic Graph. These datasets represent co-authorship networks, where nodes correspond to researchers, and edges signify their collaborative relationships. The features of each node reflect the frequency of keywords extracted from the publications of the respective authors. Graph labels identify the primary research domain of each author, distinguishing between computer science and physics.
Amazon Computers and AmazonPhoto are co-purchase networks constructed from Amazon. In these graphs, nodes represent products, while edges indicate co-purchase relationships between item pairs. Node features are derived from encoded customer review texts associated with each product, and graph labels classify the products into specific categories.
OGB-ar Xiv citation graph composed of Computer Science papers from arXiv. In this dataset, nodes correspond to individual articles, and directed edges represent citation relationships. Node features are computed as the average of 128-dimensional word embeddings extracted from the title and abstract of each paper. The task involves predicting the primary category of arXiv articles among 40 possible classes.
D.2 Experimental Setup
The attention entropy experiments in Fig. 1, Fig. 3, and Fig. 5 are conducted on Cora, Amazon- Photo, AmazonComputers, CoauthorCS, CoauthorPhysics, tolokers, amazon-ratings minesweeper, and ogb-arxiv. The cluster ablation study Fig. is conducted and averaged on all the datasets included in this paper. The number of clusters is 4 in Fig. 3, Fig. 5-6, Fig. S8, and Tab. 5-6. Other experiments choose m from (2. ..... 8). For baseline methods, both GNNs (GCN [17], Graph- SAGE [14), GAT [48], GPRGNN [7]) and graph transformers (NAGphormer [4]. NodeFormer [50]. DIFFormer [49], GOAT [18)) are included. The results of the backbone methods, including GraphGPS with Performer, SGFormer, and Polynormer, are reproduced under the framework of GraphGPS.
The framework implemented with Py Torch [31] and Py Torch Geometric [12], and trained on
single NVIDIA A100. We perform grid search based on the validation performance of the models as follows:
GraphGPS. We search the number of graph transformer layers in (1..... 6). the number of hidden dimensions in {64, 80, 128, 256), the number of heads in {1, 2, 4). dropout in {0.1, 0.2, 0.3, 0.5). and learning rate in {5e - 4, le 3, le 2}. The rest hyperparameters are fixed as in the original implementation.
SGFormer. The GNN backbone implemented as GCN [17]. The number of GCN layers is searched in the number of hidden dimensions in {64, 80, 128, 256). the number of
17

---

heads in (1, dropout in {0.1, 0.2, 0.5), and learning rate in {lc 3, 5e 3, le 2}. The rest hyperparameters are fixed as in the original implementation.
Polynormer. The GNN backbone is implemented as GAT [48]. We search the number of graph
transformer layers {1,... .1, 6). the number of GAT layers in (1.... 10), the number of hidden dimensions in {64, 80, 128, 256}, the number of heads in {1, 2, 4, 8), dropout in {0.1, 0.2, 0.3, 0.5),
and learning rate in {5e le 3}. The rest hyperparameters are fixed following the original implementation.
029
113
0.0
(a) SGFormer
(b) GraphGPS
(c) Polynormer
Figure S8: Full Results for Relations between Source and Target Nodes.
E Full Results for Informative Source Nodes
To analyze the relations between target and source nodes in the cluster with the highest attention score, compute the ratio of the source nodes (1) that have the same label the target nodes, and (2) that are connected with the target nodes, both relative to the total number of source nodes in the cluster. The results for all three backbones are presented in Fig. S8. The ratio of source nodes that are connected to their target nodes varies across the different backbones. Among the backbones, SGFormer assigns more attention source nodes connected with the target nodes than Polynormer and GraphGPS. The label distribution differs between heterophilic and homophilic graphs, yet remains consistent across the backbones. On heterophilic graphs, target nodes assign higher attention scores to source nodes that have the same label as them. This stems from the heterophily of these graphs, where connected nodes often have different labels. Therefore, models only aggregate messages from nodes with different labels via local message passing and turn to global attention collect messages from nodes with the same label the target nodes.
Batter #fonte do
Salora Nows
(a) SGFormer
(b) GraphGPS
(c) Polynormer
Figure S9: Time Cost. Different colors of the points denote the number of clusters m. The point shape denotes the whole model with Wideformer. "*" denotes the Wideformer part.
F Complexity Analysis
We construct synthetic graphs to test the time cost across different graph scales. The average degree is set to 8, with maximum number of edges equals 100, 000. The number of classes is set to 10. Both the number of input features and hidden dimensions are set 64. Following the common configuration of the backbones, we set the number of local layers and global layers as (3, 1), (3, 3),
18

---

Table S8: Average Cost Increase Ratio. Comparing the time and memory cost of 4 clusters against 1 cluster. m denotes the number of clusters. The results are averaged across datasets with different numbers of graph nodes.
TIME (S)
MEMORY (MB)
GRAPHGPS
0.0973
13,870
4
0. 0.140830.9338
15,54610.r88
SGFORMER
0.0258
50,206
1.041137.5666
51.332 19%6
POLYNORMER
0. 0,1042
29,338
4 0. 0.1435
30, 20,1880.7799
Table S9: Comparison Results with ENACT (Measure by accuracy except for ROC-AUC for
questions: %). The bold values denote the best results among comparisons with the same backbone.
AMAZON-RATIEN
COAUTHORCS
AMAZONPHOTO
QUESTIONS
GRAPHGPS
49.73
95.44
94.98
75.48
+ENACT
48.52
95.16
94.76
75.74
+ WIDEFORMER
49.96
95.85
95.55
75.69
SGFORMER
52.38
93,50
95.47
76.81
+ENACT
53.32
93.21
95.53
76.53
WIDEFORMER
53.47
93.86
95.64
76.94
POLYNORMER
54.71
94.53
95.47
78.66
+ ENACT
54.94
94.60
95.55
78.78
WIDEFORMER
55.05
94.94
95.64
79.00
and (6, 3) for SGFormer, GraphGPS, and Polynormer, respectively. All models have attention heads. that the time cost of Wideformer scales linearly with the
From the results in Fig. S9, we number nodes and remains a small ratio the total time cost as the number clusters increases.
In Sec 5.3.3, we show that increasing the number of clusters m can benefit the model performance, while the optimal value of m is around 3 In practice, is chosen from (2.... 8) to remain small value. Therefore, although larger increases the memory and runtime cost linearly, the additional cost is minor. We further present the average cost increase ratio (calculated as (0stmmm4)-osmmmmmm
across different numbers of graph nodes Tab. S8. We can see that the
cost(m==)
additional costs relatively minor, amounting only 30% of the original time cost and less than 11% of the memory cost.
G Broader Related Work
Our study is also related other works beyond graph transformers. Wideformer employs the center selection method to assign source nodes to different clusters. Traditional cluster pooling methods focus on learning hierarchical features of input graphs [56, 20, 57, 28]. They can collect global information by stacking multiple layers. In contrast, Wideformer and other graph transformer models can collect global information in a single layer, giving rise to shallow architectures large graphs.
To better optimize the learning process of the attention matrix with dense interactions, previous study proposes inject uniform attention to vision transformers [16]. However, this solution cannot be directly adopted for graph transformers. It requires explicitly computing the whole attention matrix, which demands space complexity O(n²) and is not scalable large graphs. Moreover, different from the occasional observation of the uniform attention [16], we discover that uniform attention with high attention entropy consistently exists across different global graph attention methods on different datasets. To further reduce the computing complexity, ENACT proposes to cluster source nodes during attention-based aggregation for vision transformers [35]. However, ENACT cannot effectively alleviate over-aggregating. Specifically, their clustering process is based on the features of each individual node, while Wideformer clusters nodes based on the source-target relation, which better enables the selection of the informative sources for the targets. ENACT also applies attention
19

---

aggregation at the cluster level, while Wideformer applies attention aggregation at the node level within each cluster. Node-Ievel aggregation allows the model to adjust attention scores a finer level and capture the node feature distribution within each cluster. To further compare Wideformer against ENACT for tackling over-aggregating. we implement ENACT graph transformers by directly clustering source nodes based on their own features, and only applying cluster-level attention aggregation. Results Tab. S9 show that ENACT cannot effectively tackle over-aggregating and gains worse performance than Wideformer. This demonstrates the effectiveness of our method in tackling over-aggregating and benefiting backbone performance.
H
Societal Impact
This paper presents work whose goal is to advance the field of graph representation learning by proposing a plug-and-play method to tackle over-aggregating problem in graph transformers. The proposed method remains independent of specific downstream applications and can potentially benefit a wide range of domains, such as computational biology [60, 55] and intelligent transportation [33]. At present, we do not anticipate any evident ethical concerns or foreseeable adverse societal impacts.
I Limitation
This paper discovers the over-aggregating phenomenon in graph attention and proposes plug-and- play method to tackle over-aggregating. To keep the simplicity of our proposed method, we only explore a simple division method based on KMeans++ [3] and an attention- -oriiiiinnnniiiggggggg method with cluster weighting. Sec. 5.3.3, the center selection study primarily shows that a lcarnable center selection strategy solve the trade-off' between efficiency and model performance. The module ablation study demonstrates that the simple weighting method may fail to benefit backbones under certain circumstances. All these ablation results and the informative source node study in Sec. 5.3. indicates that it lacks further exploration of a learnable division strategy and adaptive weighting method.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer Appendix I.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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 sell-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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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]
21

---

Justification:
Theoretical proof is provided for Theorem 3.1 in Appendix A. Detailed derivation is provided for Eq. in Appendix B.
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 or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Please refer to Appendix D.2.
Code is provided in
https//ggiibb.oommmuss/vveeggggp
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others 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 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 reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be 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 deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Code
with instructions for reproduction is
provided in
http:://gthub..oommmssss/vrveee agggoggggn......ggggig.nn..gg
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
cormiiissssooooiiooooooo oolicyyyyyy for more details.
While encourage the release of code and data, 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 open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/
for more details.
The authors should provide instructions data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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:
Detailed experimental setups provided in Appendix D.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, 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: Please refer to Tab. 2-Tab.
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, least for the experiments that support the 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, or overall with given experimental conditions).
23

---

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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Appendix D.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 htwp:iiieehhhssciieeeeeeeeee
didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics stctps//neurips
Answer: [Yes]
Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics in every respect.
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).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer to Appendix H.
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 unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no 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 to 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. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Please refer to Appendix D.I.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi wwwode. com condaatasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
25

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Please refer http:://sihbbbbooommmuuss//reegr
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include 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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 in the main paper.
According the NeurIPS Code of Bthies, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
26

---

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


Reviews:
[{"review_id": "8PIuznAurv", "reviewer": "Reviewer_6GqH", "summary": "This paper presents Wideformer, a plug-and-play enhancement to graph attention mechanisms designed to address a newly identified challenge in graph transformers: over-aggregating. The authors observe that as the number of nodes increases, attention scores tend to become uniformly distributed, leading to diminished discriminatory power during message aggregation. Wideformer mitigates this issue by employing a divide-and-conquer strategy, in which parallel aggregation modules each focus on restricted subsets of nodes. This design reduces the information burden per aggregation unit and alleviates message dilution, thereby enhancing the model’s ability to capture salient information in large graphs.", "questions": "My major concerns are written in the weakness section above.", "limitations": "No. Refer to my weaknesses please.", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 1, "strengths_and_weaknesses": "[Strengths]\n\n1. I personally enjoyed Wideformer’s design—partitioning attention aggregation and enforcing selective focus—which mirrors established strategies in managing information overload in attention-based models (e.g., mixture-of-experts). The method is described clearly with intuitive steps: parallel aggregation, cluster-wise processing, and attention-guided selection.\n\n2. The paper is built upon a solid motivation which effectively situates Wideformer among two dominant solution categories for attention scalability: sparse attention and linear attention. It convincingly argues that while these approaches reduce complexity, they may exacerbate over-aggregation under large node counts.\n\n3. The paper is based on strong experimental results which validates that Wideformer achieves state-of-the-art performance across 13 well-known benchmarks in Graph Processing.\n\n[Weaknesses]\n\n1. Although \"over-aggregating\" is introduced as a distinct problem, its symptoms resemble aspects of over-squashing, over-smoothing, and over-dilution (where important messages are lost due to limited representation capacity). I have not been convinced that \"over-aggregating\" is a distinct and unique problem that requires special solution sets.\n\n2. Wideformer mitigates over-aggregation by increasing the number of parallel aggregation units. But I would have enjoyed a more thorough analysis on the computational overhead or memory cost. How does it compare in runtime efficiency after its \"late-aggregation\" style where it runs at subsets first and aggregated later. A brief discussion or analysis of efficiency vs. accuracy trade-offs is necessary, especially since scalability is a key motivation.\n\n3. The most major concern is that while the problem is introduced in Graph Neural Network, this is a central issue in both Graph-based [1] and Transformer-based methods that could be considered as fully connected graphs. In this aspect, I personally do not think that Wideformer is either unique nor novel, since simply restricting the attention scope into a subset of the input token has been presented in multiple previous works in Transformer attention [2,3,4].\n\n[1] Even Sparser Graph Transformers (NeurIPS 25, https://neurips.cc/virtual/2024/poster/95681)\n[2] Stabilizing Transformer Training by Preventing Attention Entropy Collapse (ICML'23, https://proceedings.mlr.press/v202/zhai23a/zhai23a.pdf)\n[3] Attention is not all you need: pure attention loses rank doubly exponentially with depth (ICML'21, https://arxiv.org/pdf/2103.03404)\n[4] In-Context Learning with Transformers: Softmax Attention Adapts to Function Lipschitzness\n[5] ENACT: Entropy-based Clustering of Attention Input for Reducing the Computational Needs of Object Detection Transformers (https://arxiv.org/abs/2409.07541)\n[6] Scratching Visual Transformer's Back with Uniform Attention (ICCV'23, https://arxiv.org/pdf/2210.08457)", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your valuable suggestions that help us revise our manuscript, and hope our response can adequately address your concerns. The discussion will be added to the revision.\n\n**W1**: Differences between over-aggregating and over-squashing/smoothing/dilution.\n\n**Response**: Thank you for bringing over-dilution to our attention. We would like to confirm that our understanding is correct, that the reviewer is referring to the over-dilution discussed in [R1]. If this is not the case, we kindly ask the reviewer to clarify. We have added the differences between over-dilution and over-aggregating to the existing discussion in sec 3.3.\n- Over-smoothing\n    - `Different graph structures`: Over-smoothing occurs on the input graph structures, while over-aggregating occurs on the attention graph. \n    - `Different causes`: Over-smoothing stems from the low-pass filtering of the aggregation function, while over-aggregating is caused by the attention optimization issue when the number of source nodes becomes large. \n    - `Different solution`: Designing high-pass filters can tackle over-smoothing. Conversely, even when a high-pass behavior is desired during over-aggregating, the optimization of attention weights may still be hindered by the overwhelming number of source nodes. One must tackle this issue regarding the input node volumes.\n- Over-squashing\n    - `Different causes`: Over-squashing stems from the imbalance between the volumes of a node’s input and output messages, whereas over-aggregating is only associated with its input volume.\n    - For instance, consider an attention matrix where edge weights are uniformly distributed across the fully-connected attention graph. \n        - This case reflects the most severe form of over-aggregating, where the attention entropy reaches its maximum (i.e., logn). \n        - Over-squashing does not arise where each node in such a graph has perfectly balanced input and output volumes.\n- Over-dilution\n    - Intra-node dilution focuses on the volumes of the `node features`, while over-aggregating focuses on the volumes of the `input nodes`.\n    - Inter-node dilution focuses on whether `a node's own information` is preserved during aggregation, whereas over-aggregating emphasizes the preservation of `messages from the informative nodes`, regardless of whether that includes the node itself.\n\n**W2**: Runtime and memory cost.\n\n**Response**: Thank you for your suggestion. Based on our analysis of model complexity (sec 5.3.2) and cluster ablation (sec 5.3.3), Wideformer results in \n- `Efficiency-accuracy trade-off` regarding the number of clusters $m$. \n    - Wideformer time/space complexity: T+$O(nm)$. T is the complexity of the backbone, and $n$ is the number of graph nodes. \n    - A larger $m$ value ($m\\le8$) gives rise to higher accuracy, but increases the memory and runtime costs linearly.\n- `Affordable increase in time and memory cost`: Fig. 7 shows that Wideformer achieves the largest gains with a small number of clusters $m$ in \\{3, 4, 5\\}. The average cost increase ratio (calculated as [cost(m=4)-cost(m=1)]/cost(m=1)) across different numbers of graph nodes is presented in Tab.R1. We can see that `the additional costs are relatively minor`, amounting to only ~30\\% of the original time cost and less than 11\\% of the memory cost.\n\n| Table R1. Cost Increase Ratio| | Time (s)  | Memory (MB) |\n| :-- | --: | --: | --: |\n| GraphGPS   | m=1   | 0.0973 | 13870 |\n| | m=4   | 0.1408 | 15546 |\n| | increase ratio | 30.93\\% | 10.78\\% |\n| SGFormer   | m=1  | 0.0258  | 50206  |\n| | m=4  | 0.0413 | 51332 |\n| | increase ratio | 37.56\\%   | 2.19\\% |\n| Polynormer | m=1  | 0.1043 | 29338 |\n|  | m=4 | 0.1435  | 30180 |\n|  | increase ratio | 27.37\\%  | 2.78\\% |\n\n**W3**: Differences with previous works.\n\n**Response**: Thank you very much for bringing these interesting works to us. The major differences between our work and previous works are that, \n- `Novel phenomenon`: We discovered the novel over-aggregating phenomenon as a common issue across different global graph attention methods in different datasets, and systematically studied its root cause and influence with different numbers of nodes.\n- `Novel solution`: To specifically mitigate over-aggregating, we propose Wideformer as a plug-and-play solution, including\n    - Node division tailored for message dilution in over-aggregating: \n        - Tackling over-aggregating requires distinguishing informative source nodes from less informative ones.\n        - Selecting the truly informative sources for the targets requires the `modeling of the source-target relations`.\n            - `Previous methods fail` by focusing solely on either target nodes (query) or source nodes (key).\n            - `We learn` from the relation by selecting cluster centers among the targets and assigning source nodes based on their similarity to the target centers. This strategy enables effective discrimination of informative nodes while avoiding excessive computational overhead.\n    - Attention guiding tailored for uniform attention in over-aggregating: To `enable target nodes focusing` on the informative clusters, cluster aggregation results are further weighted with cluster attention. \n- `Effective solution`: Wideformer can effectively tackle the over-aggregating effect, while previous work cannot. (Indicated in Tab. R1 and R2)\n\nSpecifically to the works you mentioned in the review, the differences can be summarized as:\n- [1][4] validate the prerequisite of our work: These works and other sparse attention methods prove the prerequisite of our work, that not all source nodes are informative to the target nodes. As a result, large attention entropy in graph transformers leads to indiscriminate aggregation and information loss.\n    - Why not sparse attention? Wideformer maintains the global receptive field for target nodes, while sparse attention shrinks the receptive fields, leading to sub-optimal message pathways for downstream tasks. This is supported by the results in Tab.1-3, where global attentions with Wideformer give rise to better performances than sparse attentions.\n- [2][3] study other issues in attention: [2] reformulates the weight matrix to tackle the training instability of transformers with lower attention entropy, and [3] decomposes the transformer forward pass into an ensemble of successive attention heads to tackle the attention collapsing.\n- [6] cannot be applied to graph transformers: [6] requires explicitly computing the whole attention matrix, which demands a space complexity of $O(n^2)$ and is not scalable to large graphs.\n- [5] cannot effectively address over-aggregating:\n    - Methodology:\n        - Awareness of source-target relation: [5] clusters the source nodes based on `their own features`, while Wideformer clusters nodes based on `the source-target relation`, which better enables the selection of the informative sources for the targets.\n        - Finer-level aggregation: [5] only applies attention aggregation at the `cluster level`, while Wideformer also applies attention aggregation at the `node level` within each cluster. Node-level aggregation allows the model to adjust the attention scores at a finer level and capture the node feature distribution within each cluster.\n    - Experiment: \n        - We implemented ENACT [5] in graph transformers by directly clustering source nodes based on their own features, and only applying cluster-level attention aggregation. \n        - By comparing Wideformer with ENACT in terms of the resulting attention entropy (Tab.R2) and node classification performance (Tab.R3), we can see that `ENACT cannot effectively tackle over-aggregating and gains worse performance than Wideformer`. This demonstrates the effectiveness of our method in tackling over-aggregating and benefiting backbone performance.\n\n| Table R2. Attention Entropy | GraphGPS | SGFormer | Polynormer |\n| :-- | :--: | :--: | :--: |\n| Original | 0.9846  | 0.9743  | 0.8138 |\n| ENACT | 0.9673  | 0.9619  | 0.8125 |\n| Wideformer | 0.2863  | 0.1352  | 0.6529 |\n\n| Table R3. Classification Results| amz-ratings | cs | photo  | questions |\n| :-- | :--: | :--: | :--: | :--: |\n| GCN  | 48.70 | 92.92 | 92.70 | 76.09  |\n| Exphormer | 53.51 | 94.93 | 95.35 | 73.94  |\n| GraphGPS  | 49.73 | 95.44 | 94.98 | 75.48 |\n| +ENACT | 48.52 | 95.16 | 94.76 | **75.74**    |\n| +Wideformer | **49.96** | **95.85** | **95.55** | 75.69 |\n| SGFormer  | 52.38 | 93.50 | 95.47 | 76.81 |\n| +ENACT | 53.32 | 93.21 | 95.53 | 76.53    |\n| +Wideformer | **53.47** | **93.86** | **95.64** | **76.94** |\n| Polynormer  | 54.71 | 94.53 | 95.47 | 78.66 |\n| +ENACT | 54.75 | 94.60 | 95.55 | 78.78 |\n| +Wideformer | **55.05** | **94.94** | **95.64** | **79.00**  |\n        \n[R1] Understanding and Tackling Over-Dilution in Graph Neural Networks. KDD'25"}, {"review_id": "0UkVteA4Jo", "reviewer": "Reviewer_j4ry", "summary": "The paper identifies over-aggregating, a tendency of graph-transformer attention to assign nearly uniform weights when many nodes are present, which “dilutes” salient messages. It measures the effect with attention-entropy and shows that the entropy lower-bound grows with graph size. To counter this, the authors introduce Wideformer, a plug-and-play module that divides the global receptive field into m query-based clusters using a K-means++ seeding routine (Alg. 1) and aggregates each cluster independently. It guides attention by re-weighting and sorting the cluster outputs with a second soft-max so each node can focus on informative clusters. Wideformer is inserted atop three linear graph-transformer backbones (GraphGPS, SGFormer, Polynormer) and evaluated on 13 node-classification datasets spanning 1 K – 170 K nodes. It consistently lowers attention-entropy and yields accuracy or ROC-AUC gains of ~(0.2–1.2) pp on most benchmarks, with linear time/space O(n m) and modest wall-time overhead. An ablation shows both division and guidance are needed for peak gains. Limitations and societal impact are discussed.", "questions": "The work is technically sound, addresses a practical issue, and shows consistent improvements with minimal cost. Expansion to broader tasks and deeper statistical analysis would elevate its impact. \n\nGenerality beyond node classification. Evaluate on graph-level tasks or link prediction.\n\nStatistical robustness. Add paired-t tests or confidence intervals; some gains lie within one standard deviation.\nFigure interpretability. Revise Figure 4 (requires description) and Figure 6 lacks a informative legend explaining that numeric labels denote clusters: similar plots, enlarge fonts. \n\nProofreading. Fix spelling errors (\"Cluter\", \"compexity\", \"Targe\") and standardize “Wideformer” capitalization.\n\nThe brief description of over-smoothing in §3.3 is hard to follow. Please consider rewriting this paragraph with a concise definition, one illustrative example", "limitations": "Authors explicitly acknowledge that (i) the current division and guidance strategies are simple and may fail in some regimes and (ii) only a limited search over clustering and weighting strategies is explored. I concur and suggest emphasizing scalability to million-node graphs and tasks beyond classification. Yes, limitations are adequately discussed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality\t\nStrengths: Solid empirical study on 13 datasets; ablations and complexity analysis support claims; open-sourced code and reproducibility checklist.\nWeaknesses: Experiments focus only on node classification; no link-prediction or graph-level tasks; statistical significance of gains not reported. Limitation of K-means++ choice. The divide step uses K-means++, which may be suboptimal due to its assumptions. Have the authors considered differentiable clustering or adaptive-k strategies? An ablation comparing clustering algorithms or at least discussing these trade-offs would strengthen the paper.\n\nClarity\t\nStrengths: Motivation, method and equations are easy to follow; limitations clearly stated.\nWeaknesses: (i) Several figures are hard to interpret: e.g., in Figure 6 the numbers actually label clusters, but this is never explained in the caption or legend, so a reader cannot tell what they mean without digging into the text. More descriptive legends or color-coding would help. (ii) Fonts in many plots are tiny. (iii) Multiple spelling glitches (“Cluter”, “Large”, “compexity”) and inconsistent capitalization of “Wideformer.”\n\nSignificance\nStrengths: Tackles a practical performance bottleneck in linear graph transformers and can be adopted by many models; modest but consistent gains on real data.\t\nWeaknesses: Incremental relative to existing sparse-attention or cluster pooling work; gains may be negligible in applications where entropy is already low.\n\nOriginality\nStrengths: Introduces the specific notion of over-aggregating and couples a two-step divide-and-guide scheme not present in prior work.\nWeaknesses: Concept overlaps with known uniform-attention phenomena; division uses standard K-means++ rather than a novel algorithm.", "was_revised": true, "final_justification": "The authors have cleared my concerns with additional experiments. They have promised to update the paper accordingly. As such I have raised my score from borderline accept to accept.", "rebuttal": "Thank you very much for your support and valuable suggestions that further broaden the potential application of our method to other tasks. We hope our response can adequately address your concerns. The discussion will be added to the revision.\n\n**Quality 1&Q1&Q2**: More results for different tasks.\n\n**Response**: We further evaluate backbones with Wideformer for graph classification on peptides-func [R1] and CIFAR10 [R2], and for graph regression on peptides-struct [R1] in Tab.R1. Results show that Wideformer can `consistently benefit backbones on these tasks`.\n\n| Table R1. Comparison on Graph-level Tasks | peptides-func $\\uparrow$ | peptides-struct $\\downarrow$ | CIFAR10 $\\uparrow$ |\n| :-- | :--: | :--: | :--: |\n| GCN  | 59.30 | 0.3496  | 55.71 |\n| GraphGPS    | 63.77 | 0.2615  | 71.63 |\n| +Wideformer | **64.02** | **0.2530**  | **73.40** |\n| SGFormer    | 60.14 | 0.2796  | 55.93 |\n| +Wideformer | **60.53** | **0.2687**  | **56.51** |\n| Polynormer  | 61.39 | 0.3089  | 65.34 |\n| +Wideformer | **61.95** | **0.3002**  | **66.11** |\n\n**Quality 2&Q3-1**: Statistical significance of gains.\n\n**Response**: Thank you for your suggestion, which enables us to prove the significance of our performance gains statistically. We compute the performance gains between backbones with Wideformer and backbones only, and then compare the gains with zero. Paired t-tests on all backbones consistently give rise to `p-values smaller than 0.05`, and the `confidence interval results do not contain 0`, demonstrating the `statistical significance` of our gains.\n\n**Quality 3&Originality 2**: Ablation on center selection methods.\n\n**Response**: Thank you very much for enlightening us to discover a better center selection method! \n- `Setting`: Following your suggestions, we studied the trade-off between computing efficiency and model performance. In the manuscript, to ensure computing efficiency, *we did not apply the iterative clustering process* in the Wideformer but only initiated the centers via a K-means++-like algorithm. Therefore, we only evaluated whether applying clustering iterations results in better performance during the rebuttal, instead of considering more complex clustering strategies. Specifically, we compare the simple initiating choice with (1) Multi-step iteration clustering and (2) directly modeling centers as parameters. The results are averaged on amazon-ratings, questions, CoauthorCS, and AmazonPhoto.\n- `Results` in Tab.R2 show that further `applying clustering iterations can achieve better results`, indicating the efficiency-performance trade-offs. We also discovered that `directly modeling centers as parameters can address this trade-off`, which does not require clustering iterations and achieves the best results.\n\n| Table R2. Clustering Method Comparison | GraphGPS | SGFormer | Polynormer |\n| :-- | :--: | :--: | :--: |\n| Original | 78.91 | 79.54 | 80.84 |\n| +Wideformer | 79.26 | 79.98 | 81.07 |\n| +iter=2 | 79.93 | 80.58 | 81.44 |\n| +iter=4 | 79.95 | 80.42 | 81.43 |\n| +iter=6 | 79.85 | 80.55 | 81.52 |\n| +learnable  | **80.05** | **80.60** | **81.54** |\n\n**Clarity&Q3-2&Q4**: Legend description, tiny fonts, and typos.\n\n**Response**: Thank you for your suggestions. We fixed these problems in the revision by increasing the font size, correcting the typos, adding legend description to Fig.6 (The shape of the points indicates the model types, where '.' denotes the whole model and '*' denotes the Wideformer part. The color of the points indicates the number of the clusters $m$), and adding descriptions to Fig.4 (The informative source node ratio denotes the ratio of nodes assigned to the cluster with the highest attention score relative to the total number of graph nodes).\n\n**Significance 1**: Comparison with sparse attention and cluster pooling.\n\n**Response**: Thank you for your suggestions. We have added the discussion to the revision.\n- `Sparse attentions` approximate fully-connected message passing via sparse connections. These methods shrink the receptive fields of the target nodes, which leads to sub-optimal message pathways for downstream tasks. In contrast, Wideformer maintains the global receptive field for target nodes. The importance of maintaining a global receptive field can be supported by the results in Tab.1-3, where combining global attentions with Wideformer gives rise to better performances than sparse attentions.\n- `Cluster pooling` methods focus on learning hierarchical features of input graphs. They can collect global information by stacking multiple layers. In contrast, Wideformer can collect global information in a single layer, giving rise to shallow architectures for large graphs.\n\n**Significance 2**: Performance on low-entropy scenario.\n\n**Response**: Wideformer can also achieve statistically significant gains on small-scale graphs (Cora and Citeseer in Tab.3 in the original manuscript), which typically have lower attention entropy. This demonstrates the effectiveness of Wideformer across different node scales.\n\n**Originality 1**: Comparison with uniform-attention phenomena.\n\n**Response**: Our work differs from previous uniform-attention phenomena by providing\n- `Proof as a common issue`: Different from the occasional observation of the uniform attention in previous works [R3], we discovered that uniform attention with high attention entropy consistently exists across different global graph attention methods in different datasets. \n- `Systematical study`: We termed this phenomenon as over-aggregating, providing quantitative, theoretical root-cause, and influence analysis systematically.\n- `Effective solution`: We also proposed Wideformer to tackle over-aggregating, which is tailored for large-scale graphs and achieves consistent performance gains for different backbones on different datasets.\n\n**Q5**: Definition and example for over-smoothing.\n\n**Response**: Thank you for your suggestion. We will rewrite this part with a concise definition and examples. \n- `Cause`: Over-smoothing occurs when applying low-pass filtering to aggregate messages on the input graphs, such as the adjacent matrix with self-loops. In contrast, over-aggregating is caused by the large number of nodes blocking the optimization of the attention scores. \n- `Solution`: Designing high-pass aggregating functions can tackle over-smoothing. Conversely, for over-aggregating on graph transformers, even when a high-pass behavior is desired, the optimization of attention weights may still be hindered by the overwhelming number of source nodes involved in aggregation. One must tackle this issue regarding the input node volumes.\n\n[R1] Long Range Graph Benchmark. NeurIPS'22\n\n[R2] Benchmarking Graph Neural Networks. JMLR'23\n\n[R3] Scratching Visual Transformer's Back with Uniform Attention. ICCV'23"}, {"review_id": "au9SQun0hh", "reviewer": "Reviewer_SCEQ", "summary": "The paper defines the concept of attention entropy, proposes a new algorithm that divides global aggregation by clusters and guides the aggregation by the significance of the clusters, which is supposed to reduce the attention entropy. Experiments show that the algorithm is effective in improving the performance of several graph transformers on various datasets.", "questions": "1. Is there a possibility that over-aggregation is not a significant factor for the generalization of graph transformer models, or, on the contrary, why is it a significant one?\n2. Can you find an approach to demonstrate that reducing the attention entropy deterministically improves the generalization of the model?\n3. In your abstract, you mentioned that your method reduces information loss. Can you be more specific about the information loss in the original transformer structures? How do you measure the information loss? To what extent does your algorithm help reduce it?", "limitations": "There is no negative societal impact of the work.  \nThe limitations of the paper: See the questions and weaknesses", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: Define the concept of attention entropy; propose a new algorithm that divides global aggregation by clusters and guides the aggregation by the significance of the clusters. It is written in plain language and has a handful of plots that attempt to corroborate the effectiveness of its method.\n\nWeaknesses: \n1. Theorem 3.1 (at line 122) is a correct but not meaningful statement. You can always show that entropy is lower bounded by 0, which is obtained when $\\alpha$ has a point mass distribution. This statement does not suffice to support the exact claim (at line 126) \"graph attention will have higher attention entropy when aggregating more graph nodes\", and fig.1(b) does not conform to the monotonicity in the Theorem when the # of nodes increases from 1e+4 to 1e+6.\n2. The paper does not show a clear causal relation (or correlation) between reduction of attention entropy and better generalization. Empirically, the algorithm reduces the attention entropy of all three architectures significantly, but the test accuracy is improved marginally. Moreover, the most severe reduction occurs on polynormer, but the improvement of polynormer is not superior to that of the other two architectures.\n3. The idea of using cluster information in the network data is not unique, even in my package of reviewed assignments.", "was_revised": true, "final_justification": "Questions are resolved.", "rebuttal": "Thank you very much for your valuable suggestions that help us improve our paper. We hope our response can adequately address your concerns. The discussion will be added to the revision.\n\n**W1**: Lower bound of the attention entropy.\n\n**Response**: \n- `Tight lower bound of Theorem 3.1`: We would like to clarify that Theorem 3.1 is not based on the trivial lower bound of 0, but a non-trivial, tighter lower bound derived in Appendix A. This bound increases with the number of aggregated nodes.\n- `Lower bound monotonicity`: Theorem 3.1 characterizes the monotonicity of the attention entropy lower bound to the number of nodes, rather than the monotonicity of the actual learned attention entropy.\n    - Regarding Fig.1(b): The overall trend of Fig.1(b) aligns with the theoretical prediction, where a higher lower bound makes it more likely for the learned attention scores to exhibit higher entropy given more aggregated nodes.\n    - Regarding Line 126: We agree that the original phrasing may be misleading. We will revise the statement to “more likely to have higher entropy” to better reflect the theoretical prediction.\n\n**W2&Q1&Q2**: Relation between attention entropy and model generalizability.\n\n**Response**: Thank you for your suggestions, which help us to better understand the working mechanics of Wideformer.\n- `Reduction of attention entropy relates to better generalization`\n    - `Regularizing entropy improves model performance`: In Tab.S5 in the manuscript, we show that directly reducing the attention entropy during training can achieve better model performance. \n    - `Reduced entropy results in smaller generalization gap`: We further analyze the performance gap between the training set and the test set with different weights on the entropy regularization term. Results are averaged on GraphGPS, SGFormer, and Polynormer across amazon-ratings, questions, AmazonPhoto, and CoauthorCS. Tab.R1 shows that *reduced entropy can reduce the performance gap between training and inference*. This confirms the positive relation between the reduction of attention entropy and better generalizability.\n    - `Attention entropy should be compared within the same architecture`: Due to distinct design principles, different architectures inherently prioritize different attention patterns for optimal representation learning. While high attention entropy consistently indicates over-aggregating, the optimal entropy level varies across models. Thus, although Polynormer exhibits the most severe entropy reduction, this may still fall short of what is needed for its optimal performance, explaining why its gain is not superior to the other two.\n- `Statistical analysis demonstrates the significance of performance gains`: Following the suggestions of reviewer j4ry, we compute the performance gains between backbones with Wideformer and backbones only, and then compare the gains with zero. Paired t-tests on all backbones consistently give rise to p-values smaller than 0.05, and the confidence interval results do not contain 0, demonstrating the statistical significance of our gains.\n\n| Table R1. Relation between Entropy and Generalizability | | | | |\n| :-- | --: | --: | --: | --: |\n| Reg weight  | 0  | 0.01 | 0.05 | 0.1  |\n| Cluster attention entropy | 0.1837 | 0.0921 | 0.0812 | 0.0509 |\n| Test-Train loss | 0.1235 | 0.1065 | 0.0892 | **0.0225** |\n| Train-Test acc | 10.27  | 3.34   | 2.55   | **0.69**   |\n\n**W3**: Differences between Wideformer and previous clustering-based methods.\n\n**Response**: The main difference between Wideformer and previous clustering-based methods is that Wideformer is tailored to tackle over-aggregating. \n- Node division tailored for message dilution in over-aggregating: \n    - Tackling over-aggregating requires distinguishing informative source nodes from less informative ones.\n    - Selecting the truly informative sources for the targets requires the `modeling of the source-target relations`.\n        - `Previous methods fail` by focusing solely on either target nodes (query) or source nodes (key).\n        - `We learn` from the relation by selecting cluster centers among the targets and assigning source nodes based on their similarity to the target centers. This strategy enables effective discrimination of informative nodes while avoiding excessive computational overhead.\n- Attention guiding tailored for uniform attention in over-aggregating: To `enable target nodes focusing` on the informative clusters, cluster aggregation results are further weighted with cluster attention. \n\n> Except for these model-level differences, we also showed in the manuscript that over-aggregating is a common issue across different global graph attention methods in different datasets, and systematically studied its root cause and influence with different numbers of nodes.\n\n**Q3**: Information loss during the over-aggregating.\n\n**Response**: The information loss refers to message dilution in over-aggregated attention, where signals from informative nodes are overwhelmed by noisy or irrelevant inputs.\n- `Quantitative measure`: We can measure this loss by summing the attention scores assigned to informative nodes. Ideally, if all attention is allocated to the informative nodes, the sum equals 1. A sum < 1 indicates message dilution, i.e., some attention is \"wasted\" on uninformative nodes, leading to loss of useful information.\n- `Wideformer reduces information loss via aggregation division`  \n    - Dividing the aggregation reduces the total number of nodes being aggregated. \n    - Fewer nodes, better optimization: Based on the derivation in sec 3.2, fewer source nodes benefit the optimization of the attention scores.\n    - Better optimization, more focused attention: The optimization empowers the target nodes to focus on the informative nodes, where informative nodes get larger attention scores and thereby reduce information loss.\n- `Reduced attention entropy demonstrates the reduced information loss`: Reduced attention indicates that target nodes successfully select their informative source nodes and assign large attention scores to these nodes. Therefore, the sum of the attention scores assigned to informative nodes becomes large, demonstrating less information loss."}, {"review_id": "oeGAl1l6jQ", "reviewer": "Reviewer_FdpH", "summary": "This paper discovers a new concept, over-aggregating, which aggregates a large volume of messages with less discrimination.\nTo address it, the authors propose Wideformer, a plug-and-play method for graph attention. Wideformer divides the aggregation of all nodes into parallel processes and guides the model to focus on specific subsets of these processes.", "questions": "Above.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "* Strengths\n1. The paper identifies a novel phenomenon called \"over-aggregating\" in graph transformers, where a large volume of messages is aggregated into a single node with less discrimination, leading to potential information loss. This insight is important for understanding and improving graph transformer models.\n‌Proposed Wideformer Method‌:\n2. The Wideformer method is an effective approach to relieve the over-aggregating effect. By dividing the aggregation of all nodes into parallel processes and guiding the model to focus on informative subsets, Wideformer can maintain the global receptive field while reducing information loss.\n3. The paper provides a theoretical analysis to justify the over-aggregating effect and the effectiveness of the proposed Wideformer method. This enhances the credibility of the claims.\n\n* Weaknesses & Questions\n1. In Sec. 3.3, I noticed that over-smoothing and over-aggregating have different definitions. The first concern: Is their influence on graph learning different?  I also noticed sentences in P4.L156-157. Since the authors think higher entropy suggests similar attention scores, I believe that for each node/token whose representation seems to be similar after this layer. Isn't it a low-pass filtering effect?\n2. When and how do the authors use Algorithm 1? Before training or during training? Are centers in different layers different?\n3. The paper uses a simplistic KMeans++ clustering method to divide the nodes into clusters. A more sophisticated clustering approach based on learned node representations may lead to better performance.\n4. While the experiments cover a diverse set of datasets, the evaluation on large-scale graphs is limited. Evaluating Wideformer on graphs with millions of nodes would provide insights into its scalability.\n5. Question about algorithm 1. In the loop, $\\\\mathbf{C}$ becomes a matrix, not a vector anymore. I'm confused about it.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your support and insightful suggestions that improved our manuscript. We hope our response can adequately address your concerns. The discussion will be added to the revision.\n\n**W1**: Differences between over-smoothing and over-aggregating.\n\n**Response**: \n- Over-smoothing and over-aggregating have `different` influences on graph learning.\n    - Over-smoothing indicates low-pass filtering among the `locally connected nodes`. \n    - Over-aggregating indicates low-pass filtering among the `query-key similar nodes`. \n    - For instance, consider a high-entropy case where a subset of nodes (set a) receives zero attention, and the rest (set b) are assigned uniform attention weights. In this case, the node representations are averaged over set b, leading to feature smoothing. However, if the nodes in set b are not adjacent in the input graph, the actual locally connected nodes will not be smoothed, and there will not be a low-pass filtering effect on the input graph.\n- `Solutions for over-smoothing cannot tackle over-aggregating`. Designing high-pass filters can tackle over-smoothing. Conversely, even when a high-pass behavior is desired during over-aggregating, the optimization of attention weights may still be hindered by the overwhelming number of source nodes. One must tackle this issue regarding the input node volumes.\n- `L156-157`. Thank you for pointing this out. The low-pass filtering in L157 refers to the local smoothing effect on the input graphs. To avoid confusion, we revised L157 as 'does not necessarily imply a low-pass filtering effect among the locally connected nodes as over-smoothing.'\n\n**W2&W3**: The use of Algorithm 1 and ablation on the center selection methods.\n\n**Response**: Thank you very much for enlightening us to discover a better center selection method! \n- Algorithm 1 is applied to the target nodes before each attention-based aggregation during training, and thus, `there will be different centers in different layers`.\n- To ensure computing efficiency, we did not apply the iterative clustering process in the Wideformer but only initiated the centers based on query features via a K-means++-like algorithm. `The selection process is based on the node representations`.\n- Following your suggestions, we study whether applying clustering iterations will improve the performance. \n    - `Setting`: We compare the simple initiating choice with (1) Multi-step iteration clustering and (2) directly modeling centers as parameters. The results are averaged on amazon-ratings, questions, CoauthorCS, and AmazonPhoto.\n    - `Results` in Tab.R1 show that further applying clustering iterations can achieve better results, indicating the efficiency-performance trade-offs. We also discovered that directly modeling centers as parameters can address this trade-off, which does not require clustering iterations and achieves the best results.\n\n| Table R1. Clustering Method Comparison | GraphGPS | SGFormer | Polynormer |\n| :-- | :--: | :--: | :--: |\n| Original | 78.91 | 79.54 | 80.84 |\n| +Wideformer | 79.26 | 79.98 | 81.07 |\n| +iter=2 | 79.93 | 80.58 | 81.44 |\n| +iter=4 | 79.95 | 80.42 | 81.43 |\n| +iter=6 | 79.85 | 80.55 | 81.52 |\n| +as parameters  | **80.05** | **80.60** | **81.54** |\n\n**W4**: Results on larger graphs.\n\n**Response**: Following your suggestion, we conducted experiments on ogbn-products and ogbn-proteins [R1] in Tab.R2. Results show that Wideformer can constantly benefit the backbones on these larger datasets (with more nodes or edges), further demonstrating its effectiveness.\n\n| Table R2. Comparison on Large-scale datasets | ogbn-products | ogbn-proteins |\n| :-- | :--: | :--: |\n| #nodes | 2,449,029 | 132,534 |\n| #edges | 61,859,140 | 39,561,252 |\n| GCN  | 72.80 | 72.51 |\n| GraphGPS    | 74.90 | 71.69 |\n| +Wideformer | **76.03** | **72.67** |\n| SGFormer    | 74.47 | 73.53 |\n| +Wideformer | **75.32** | **75.44** |\n| Polynormer  | 77.21 | 73.18 |\n| +Wideformer | **78.89** | **73.97** |\n\n**W5 (Q)**: The use of $C$ in Alg.1.\n\n**Response**: Thank you for bringing this to our attention. \n- The 'update centers' step in algorithm 1 is a concatenation operation. Therefore, after the first concatenation, $C$ becomes a matrix. \n- To avoid potential confusion, we revise the description of the algorithm by initiating $C$ as an all-zero $m\\times d$ matrix and updating centers by assigning the $t$-th center to the $t$-th row. This ensures that $C$ is a matrix of the same shape throughout the algorithm.\n\n[R1] Open Graph Benchmark: Datasets for Machine Learning on Graphs."}]

Author rebuttal:

Meta-review: This paper identifies the novel problem of "over-aggregating" in graph transformers and proposes an effective plug-and-play solution, Wideformer. The method demonstrates consistent performance gains across numerous benchmarks, and the authors' comprehensive rebuttal successfully resolved most reviewers' concerns. Given the strong empirical validation and the overall positive consensus, the paper is a good contribution and warrants acceptance.
Decision: Accept (poster)