Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework
Authors: Yujie Xing
Xiao Wang
Bin Wu
Hai Huang
Chuan Shi
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Graph Transformers
Graph Representation Learning
Primary area: deep_learning

Abstract: Graph Transformers (GTs) have emerged as a powerful paradigm for graph representation learning due to their ability to model diverse node interactions.
However, existing GTs often rely on intricate architectural designs tailored to specific interactions, limiting their flexibly.
To address this, we propose a unified hierarchical mask framework that reveals an underlying equivalence between model architecture and attention mask construction.
This framework enables a consistent modeling paradigm by capturing diverse interactions through carefully designed attention masks.
Theoretical analysis under this framework demonstrates that the probability of correct classification positively correlates with the receptive field size and label consistency, leading to a fundamental design principle:
An effective attention mask should ensure both a sufficiently large receptive field and a high level of label consistency.
While no single existing mask satisfies this principle across all scenarios, our analysis reveals that hierarchical masks offer complementary strengths—motivating their effective integration.
Then, we introduce M$^3$Dphormer, a Mixture-of-Experts based Graph Transformer with Multi-Level Masking and Dual Attention Computation.
M$^3$Dphormer incorporates three theoretically grounded hierarchical masks and employs a bi-level expert routing mechanism to adaptively integrate multi-level interaction information.
To ensure scalability, we further introduce a dual attention computation scheme that dynamically switches between dense and sparse modes based on local mask sparsity.
Extensive experiments across multiple benchmarks demonstrate that M$^3$Dphormer achieves state-of-the-art performance, 
validating the effectiveness of our unified framework and model design.

Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework
Yujie Xing', Xiao Wang?; Bin Wu', Hai Huang', Chuan Shi'
Beijing University of Posts and Telecommunications, China
BBeihang University, China
(yujie-xing, xb789, www.w,.huanggg.c.... shi chuan) @bupt. en, xiao haa__aangubua..c. edu.
Abstract
Graph Transformers (GTs) have emerged as powerful paradigm for graph repre- sentation learning due to their ability to model diverse node interactions. However, existing GTs often rely intricate architectural designs tailored to specific inter- actions, limiting their flexibly. To address this, we propose a unified hicrarchical mask framework that reveals an underlying equivalence between model architecture and attention mask construction. This framework enables a consistent modeling paradigm by capturing diverse interactions through carefully designed attention masks. Theoretical analysis under this framework demonstrates that the probability of correct classification positively correlates with the receptive field size and label consistency, leading to a fundamental design principle: An effective atlention mask should ensure both a sufficiently large receptive field and a high level of label consis- tency. While no single existing mask satisfies this principle across all scenarios, our analysis reveals that hierarchical masks offer complementary trrengths-motivene their effective integration. Then, we introduce M Dphormer, Mixture-of-Expeee -fxexesrss based Graph Transformer with Multi-Level Masking and Dual Attention Compu- tation. M Dphormer incorporates three theoretically grounded hierarchical masks and employs bi-level expert routing mechanism adaptively integrate multi- interaction information. To ensure scalability, we further introduce a dual attention computation scheme that dynamically switches between dense and sparse modes based on local mask sparsity. Extensive experiments across multiple benchmarks demonstrate that Dppporrrer achieves state-of-the- performance, validating the effeetiveness of our unified framework and model design. The source code is available for reproducibility at: https://gihub..co//mllyyyyy www.:////mmmmlyy/y//////ommam
Introduction
As a fundamental data structure, graphs have been widely used to model complex and diverse interactions in real-world systems, such as social networks and brain networks. To learn high-qualit node representations, variety of Graph Neural Networks (GNNs) have been proposed 23 38 [6]
However, their performance is inherently constrained by the pessaggeppasinng mechanism, which imposes strong locality inductive bias. Inspired by the success of Transformers (37] across various machine learning domains [22 [3], adapting Transformer architectures to graphs has emerged promising direction, owing to their strong capability to model interactions over broader range.
Graph Transformers (GTs) leverage the core component of the Transformer architecture, Multi-Head Attention (MHA), to adaptively model diverse node interactions and learn expressive representations. One prominent line of research treats the entire graph as fully connected and applies attention Another line constructs token
mechanisms to capture pairwise node dependencics [42
"Corresponding authors
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

sequence for each node, typically via node sampling or feature aggregation, and adopts Transformer to capture multi-scale interactions. [5] 4T]. Besides, several studies leverage graph partitioning to enable efficient interaction modeling and learn high-quality representations. [8] 20 44).
While many GT's have been proposed, they often rely on intricate architectural design tailored to specific types of node interactions, which limits their ability to model other important interactions. This raises a natural question: Does there exist a unified perspective of GTs that allows for flexible modeling of diverse node interactions? To address this question, we propose a unified hierarchical mask framework, developed through a thorough analysis of existing GTs. Our analysis reveals that various GT architectures inherently model interactions at different global corresponding to the hierarchical organization of relational patterns in graphs. Furthermore, we find that these hierarchical interactions can be uniformly modeled through the design of appropriate attention masks, and that many existing GT's can be interpreted as implicitly corresponding to specific masks. This unified perspective reveals an underlying equivalence between model architecture and mask construction, offering more flexible approach to GT design.
local, cluster, and
Under this unified framework, diverse node interactions can be modeled in a consistent manner through the construction of appropriate attention masks, avoiding the need to design intricate network architectures as in traditional methods. Moreover, it facilitates theoretical analysis, proving that both the lower and upper bounds of the probability of correct classification correlate positively with the size of the receptive field and the degree of label consistency. This leads to a fundamental design principle for attention masks: An effective attention mask should ensure a sufficiently large receptive field and a high level of label consistency. Further analysis of masks derived from existing GT's shows that no single mask consistently satisfies this principle across all scenarios. However, hierarchical masks exhibit complementary strengths in node classification, suggesting that integrating multi-level masks provides a natural and effective way to adhere to this principle.
Then, we conduct experiments on real-world datasets to investigate the effectiveness of combining masks across multiple levels. Specifically, we construct three GTs, each designed to capture single level of interaction local, cluster, or global using corresponding attention mask. We then apply three ensemble strategies to integrate their outputs: Mean, Max, and an idcalized Oracle. The node classification results show that: 1) The Oracle strategy significantly outperforms all other models, demonstrating the potential of comprehensively leveraging multi-level interactions. 2) Naive ensemble methods (Mean and Max) often underperform than the best individual-mast model, highlighting a core challenge in effectively integrating hierarchical information. In addition, the excessive memory usage medium-scale graphs further reveals key efficiency challenge in GTs.
In this paper, we propose MrDphormer, a novel Mixture-of-Experts based Graph Transformer with Multi-Level Masking and Dual Attention Computation. Specifically, M Dpphormer employs three theoretically grounded attention masks for comprehensive modeling of hicrarchical interactions, including local, cluster, and global associations. To effectively integrate information across these interaction levels, we design bi-level expert routing mechanism, where each expert a multi-heas attention module associated with specific mask. Furthermore, a dual attention computation strategy introduced to enhance scalability and computational efficiency.
Our main contributions are summarized as follows:
We propose a unified hierarchical mask framework that reveals an underlying equivalence be- tween model architecture and attention mask construction, enabling diverse node interactions to be consistently modeled through carefully designed masks.
Theoretical analysis within this framework reveals that the probability of correct classifica- tion is positively correlated with both the receptive field size and label consistency. This leads guiding principle for designing attention masks: an effective mask should ensure a sufficiently large receptive field and a high level of label consistency.
We propose M Dphormer, a novel Graph Transformer that captures hierarchical interactions comprehensively and efficiently through multi-level masking, bi-level expert routing, and dual attention computation, thereby adhering to the proposed design principle.
We perform extensive experiments on benchmark datasets, showing that M*Dphormer consistently outperforms 15 strong baselines, demonstrating its effectiveness.
2

---

2
Preliminary
We denote an attributed graph as (PE,,)), where V {0, 1,.,,.... ,N .N- 1} is the set of N nodes, is the set of E edges, and X [x] E R&xxd is the node feature matrix, with x, Rdd, representing the din-dimmnsi feature vector of node u. The adjacency matrix is denoted as A [ E [0,1) where Ouv if there exists an edge from node to node e, and Gus otherwise. For node classification, we define the set of labels as y and represent the node labels by Y= = [y] E {0, 1] x where Yu E {0, 1] is the one hot label of node u. The whole node set can be divided into the training set V Verain, the valid set Vnatid, and the test set Viest-
Graph transformers: The core component of GTs the MHA, formulated as follows:
head, (H, M) = Softmax (Mask (AC,,) VO0
i 1= H
A (9) Q (
HWO @
K HW (
VlO HW
dh
K
(I)
( ANn
if Mf =1 if MM, 0
Mask(A
M)
-00,
Here, H Nxd denotes the input representations, where N is the number of nodes and d is the representation dimension. w w w E &ddd,, are trainable projection matrices specific to the i-th head, and dy is the hidden dimension of each head. The attention score matrix A ( is masked by M E (0.1) where Mu, 1 indicates the validity of the attention from node u to node v. During masking, attention scores corresponding to invalid positions are set to -c, ensuring that their contribution becomes zero after the Softmax operation. The outputs of all heads are concatenated to produce the final output: MHA(H, M) = Concat(head hrad
Q
Revisiting GTs through a unified hierarchical mask framework
Interactions in graphs typically exhibit hierarchical organiza- tion, including local connectivity, cluster relations, and global associations. Each level provides essential information for ef- fective graph representation learning. An illustrative example for the importance of hierarchical interactions is provided in Figure T where node labels are indicated by different colors. Due local homophily, node 14 can be accurately classified, as most of its neighbors share the same label. However, such local interactions are insufficient for classifying nodes U2 and ug. By leveraging cluster interactions, node 122 can be correctly identified, as it lies within a coherent cluster (the blue region). Furthermore, assuming that nodes labeled green follow a representation distribution distinct from the blue and yellow ones, global iiccractions-repeseette by the dotted lines- can be adaptively learned to further enhance the classification ug. Here, we propose a unified hicrarchical mask framework that enables GTs to consistently model such multi-level interactions.
Figure 1: Hierarchical interactions.
3.1 The unified hierarchical mask framework for Graph Transformers
To formalize this framework, we categorize node interactions into three types: (1) N-N: interactions between individual nodes; (2) N-S: interactions between a node and a node set; and (3) S-S: inter- actions between node sets. For N-N, we directly set M,,, = to indicate a connection from node to For N-S and S-S, we treat each node set virtual super node v', and extend the node set as V = V (v'}. This allows both N-S and S-S to be equivalently modeled as N-N, enabling a unified and flexible mask design across different interaction levels. Based on this unified framework, we further illustrate how existing GTs implicitly design their attention masks to model hierarchical interactions across local, cluster, and global levels. A summary table is provided in Table
Local interactions: Modeling local interactions typically involves capturing information from K-hop neighborhoods. GOAT explicitly models N-N interactions between a target node and its K K-hop

---

neighbors, which corresponds to the mask M = A 24] ENN-Transformer hybrid architectures implicitly adopt the mask M through their GNN modules, and aggregating K -hop information Some tokenized GTss aggregate node features at multiple hops as input tokens of Transformer, effectively applying a set of masks {A*
recursively across layers 43
- K}
[ 1511 6
Cluster interactions: Several recent GTs have focused on capturing cluster-level interactions by partitioning the graph into disjoint clusters with METIS[22]. We define the partition function P(u) to denote the cluster index assigned to node u and the reverse partition function (p) {u: Cu.p 1} to denote the set of nodes belong to cluster p. By treating each cluster as virtual super node, we denote the set of such nodes as V Graph VIT [18] models interactions between clusters (S interactions), which corresponds to applying mask M where M 1 if u, VP, Cluster-GT (00 models more fine- linegraiied N-S interactions, where each cluster attends to all real nodes. This leads mask M defined as M
if E V" and e E V. To differentiate contributions from different clusters, attention scores are further modulated by the connectivity between clusters and refined via cluster attention implicitly induced by M CoBFormer 44 focuses on N-N interactions within each cluster by implicitly applying mask M where M if u, V E V and ((u) Pvv). It additionally applies M to capture inter-cluster interactions.
Global interactions: A common strategy for capturing global N-N interactions is to treat the entire graph as fully connected, corresponding to global mask M = 1 N 42 43 11 In contrast, Exphormer (34] approximates global dependencies through an N-S interaction scheme by introducing set of virtual super nodes V5, each connected bidirectionally to all real nodes. This yields global mask M where M
u, = 1 E and 19, or u E 19 and v V.
3.2 Theoretical analysis
To investigate the distinct contributions of hicrarchical masks to node classification, we develop theoretical framework based on a class-conditional representation model. Specifically, let 9 be a graph with label set V/ and assume uniform label distribution across nodes. The initial representation of node with label è is sampled from a d-dimensional Gaussian distribution: 2 ~ (1,,, I).,, where l = 1, and the class prototypes are assumed to be orthogonal, i.e., iid Me
for all *
Let node u have ground-trui truth label c. and its receptive field be specified by the mask vector M which contains & non-zero entries. Define Pe as the fraction of nodes labeled c' within this receptive field, and az as the average attention weight assigned to those nodes. Let 2, denote the attention- updated representation of node u. We consider similarity- correctly if & Me 2 des where ó, is a decision threshold implicitly learned by models.
classifier that predicts label c
Theorem 3.1. The updated representation of node u follows a Gaussian distribution:
[C]
ICI
2y N
kppaela
Assume the classifier is well-trained such that 8, kp S O, and the attention weights satisfy the constraint 0 S Ore' 5 S 0e S kpp Then, the probability that node is correctly classified by similarity-based classifier is bounded as:
1- ( de kpoac
8 kpeake
S P( 2 51 51-510
(3)
Vip.o2002 --
(kppa2o??
where (-)) denotes the cumulative distribution function (CDF) of the standard normal distribution, and o², maxiçe of is the maximum variance among non-target classes.
Both the lower and upper bounds are monotonically increasing with respect k, Pa. and ae and decreasing with respect to the set of class-wise variances {o, s - []']]-
The proof can be found in Appendix A Theorem 3. shows that the probability of correct classification primarily depends on the factors: k; Pe, Oke, and the set of variances (a; 1 < i < [D]]]. Since and as are affected by the training dynamics and input distribution, respectively, we focus our analysis on k and Pe: which are determined by the attention mask. Theorem 3.1 demonstrates that larger

---

values of k and Pe lead to higher lower and upper bounds on the probability of correct classification. This gives rise to fundamental principle for mask construction: An effective attention mask should ensure sufficiently large receptive field and high level of label consistency.
Building this theorem, we further analyze the applicabilitty of hierarchical masks derived from existing GTs under several representative scenarios: 1) For nodes with strong local homophily, using local masks (e.g.. M M is effective due their typically large Pe. 2) For nodes near cluster boundaries, local homophily weakens as some neighbors belong to other clusters. In such cases, cluster masks (e.g., M can yield higher Pe and larger k. potentially leading to improved classification performance, assuming the partitioning is accurate. 3) For heterophilic nodes with minority labels in their cluster, local or cluster masks may result in very small Pe. even below [
Here, the global mask M is preferable, as it ensures Pe [ and provides a large k N. By contrast, the use of M may be less effective, as the global virtual nodes lack explicit label semantics. 4) Some prior works approximate global interactions through inter-cluster attention (e.g., via M However, as shown in Equation cluster-level representations are dominated by the majority label. During inter-cluster aggregation, this bias is further amplified, increasing the risk of misclassifying minority-labe nodes as the dominant class. 5) For nodes belonging to classes with well-defined representation distributions (i.e., small variance σe), the attention weights a can be effectively learned to approximate kp. leading to higher probability of correct classification regardless of the specific mask employed.
_.
The above analysis suggests that no single mask consistently satisfies the proposed principle across all scenarios. However, hierarchical masks at different levels offer complementary strengths in node classification, and their integration provides natural means of aligning with the principle.
Table I: Accuracy comparison of individual masks, ensemble strategies, and the oracle case.
Dataset
Local
Cluster
Global
Mean
Max
Oracle
Cora
87.71
73.03 1.55
86.41
86.82+2.32
93.4/
Citeseer
27.02:2.110
71.43
72.94
76. 16.2112
75.73
84.32+2.10
Pubmed
89.77:0.46
87. 87.9620.35
20.41
8
89.1920.35
93.68
Photo
94.25=0.46
94.26.1106
85.61
95.14
94.7710.74
97.50+.040
Computer
91.57
89.33
1..7
91.41 +0.92
90.45
95.59
Squirrel
38.67 +1.72
38.03
38.6441.66
38.53
38.78+11.4
53.72
Chameleon
41.97
42.24
43.50 +2.97
42.96
42.60
64.57
3.3 Experimental analysis
To further investigate whether combining masks across multiple interaction levels yields benefits in real-world scenarios, we construct three GT's trained separately with the local mask M cluster mask M and global mask M on seven node classification datasets. Then we apply three ensemble strategies integrate their outputs: Mean: averaging the predicted probabilities; Max: selecting the maximum predicted probability; and Oracle: an idealized upper bound where the best prediction is always selected. The performance of individual models and ensemble methods is reported in Table [ with three key observations: 1) The strong performance of Oracle indicates that properly integrating complementary information from multiple interaction levels can yield substantial performance gains. 2) Naive ensemble methods, such as Mean and Max, underperform the best single-mask model on 5 out of 7 datasets, revealing key challenge for Graph Transformers: How to effectively integrate multi-level interaction information?
even 2-layer Transformer with 2 heads and a single mask, consumes 21 GB of GPU memory on the PubMed. Although several efficient Transformer variants
Moreover, our experiments reveal a significant efficiency issue:
as kernel-based linear attention methods 88 35) and FlashAttention 9 have been proposed to alleviate the O(N²) complexity, their applicability to graphs remains limited due to the irregular and diverse patterns of graph masks [39]. This leads to another key challenge: How to efficiently implement GTs with irregular masks on large-scale graphs?
4 Method
In this section, we propose M Drpporrer, a novel Mixture-of-Experts based Graph Transformer with Multi-Level Masking and Dual Attention Computation. The overall framework is illustrated
5

---

(b)
19)
Expert
BMS
Fasture
Liseor
Export
Sated
Reniial Trowformshio
Sparts
Danes
Figure 2: Overview of the M M Dphormer with Pre- Tre-RMMNorm [88 and ReLU[] a) The overall network architecture. b) The bi-level expert routing mechanism. c) The theorem-guidee hierarchical mask design strategy. Self seff-connections are added for nodes in local and cluster masks. Nodes 2, 4, and are included in the training set. d) The dual attention computation scheme.
in Figure Guided by theoretical analysis, we first design three hierarchical attention masks to comprchensively model multi-level interactions (part c). To adaptively integrate information across these interaction levels, we introduce bi-level attention expert routing mechanism, where each expert is MHA module associated with specific mask (part b). Additionally, dual attention computation scheme is incorporated to ensure computational efficiency (part d).
4.1 Overall architecture of M Dphormer
We first present the overall architecture of Dphoorrer. The initial representation is given by H XW... in. where Win IR xd learnable linear projection. The model then applies stacked DpDhhrrer layers, with the computation in the 1-th layer defined as:
H' ACT (BiMoE' (Norm'
+ H'-'W' rest
where H 1 is the input from the previous layer, W res is the residual projection matrix following (26.. Norm'() (-) is the normalization function, and ACT(-) is the activation function. The bi-level attention expert routing mechanism BiMoE' (-) integrates information from multiple interaction levels based on the hierarchical mask set M. After L layers, linear classifier is applied to obtain the final prediction: Y H ctas where W cta is the classifier weight matrix. The model is optimized using cross-entropy loss computed over both the training nodes Vinin and the label-specific global virtual nodes 19 which are introduced in the following subsection.
4.2 Theorem-guided hierarchical mask design strategy
To enable comprehensive modeling of multi-level node interactions, we propose a theoretically grounded design strategy for the hierarchical mask set M (M'2 M M
Local mask design: We adopt 2 = A as the local mask due to its several advantages over n A K; 1) As observed in CoBFormer[44), the homophily ratio pe tends to decline rapidly with increasing hop size K. A lower may lead to reduced classification probability, as indicated by Theorem 3.1 2) M ignores distance information between the target node and its K Khhopp neighbors, thus requiring explicit distance- aware position encoding (4]. In contrast, 2 can capture such distance implicitly through recursive aggregation across layers. 2 is sparser than M enabling more efficient computation under the dual attention scheme introduced later.
Cluster mask design: We first partition the graph into P disjoint clusters using METIS 22 and introduce a set of cluster-level virtual nodes YP = (N + i: S P). We then define a new (u,N+ (P()), (ii) D> and v E P-1 - N). The functions P(-) and p-1(-) denote the partition and reverse-partition function defined in Section 3.1 This formulation restricts attention to node-clusted pairs within the same partition. The feature of each virtual node in YP computed by averaging the features the real nodes in its corresponding cluster. Compared to 3 the proposed M significantly reduces the
cluster mask 4 where M if either (i) u E V and

---

non-zero ratio from 1 to PN+ since P < N. making it more efficient. Moreover, as demonstrated P in Proposition 4.1 the interactions captured by M can be effectively approximated using M Proposition 4.1. Cluster interactions modeled by a single Graph Transformer layer using M can be equivalently modeled by two consecutive layers using M
AN
The proof is given in Appendix A.4 Although this requires an additional layer, the reduction in sparsity still leads to substamtial computational savings by our dual attention computation scheme.
Global mask design: We introduce new global mask M which extends 2 by explicitly incorporating label semantics. Specifically, we add | global virtual nodes, indexed as 1 = {N P 0 < [}]]], each associated with distinct class label. The mask M is set to 1 if either: (i) V and v E 19, (ii) 1 and {I E Vinin Yr yu). This structure enables each real node to attend to all global nodes, while each global node aggregates information only from training nodes with a specific label. Similar to VP, the features of nodes in 1/9 are obtained by averaging the features of training nodes with the corresponding label. Let Jc denote the global virtual node for class c, and ne be the number of training nodes with label c. By Equation 2 the updated representation satisfies: 2g. ~ ( e'
The I), since P. = 1, P = 0 for d' * c, and ag 1 The reduced variance e² indicates that it is more concentrated around the class mean. According to Theorem 3.1 this leads to improved bounds for the probability of correct classification.
4.3 Bi-level attention expert routing mechanism
To adaptively integrate information from different interaction levels, we propose the bi-level attention expert routing mechanism the core component of M Dpphormer. Each expert corresponds to an MHA module equipped with a specific attention mask. Motivated by the observation in Table that the local mask yields the best performance in most cases, we prioritize the local expert the first routing level. The second level then refines the selection among the cluster and global experts. The bi-level routing mechanism formally defined as:
BiMoE(H, .M g1 .HH D (H, 2
) + g2 MHA D ( + g3 MHA M
g1 = B1, g2 = (1 31) B2, g3 = (1 31) (1 - 32)
(5)
3 = SHW
B2 Sigmoid HW?)
Here, M denotes the hierarchical mask set. M denotes our proposed dual attention computation scheme. W W E [Rdx1 are learnable gating parameters for the first- and second- level expert selection. The sigmoid function constrains the gating values G1 and Bg within [o, 1]. To emphasize the empirical importance of local interactions, both W and W are initialized as zero vectors, yielding initial routing weights of [0.5, 0.25, 0.25) for each node, which prioritizes local attention in the early training stage. Inspired by the observation in Table I that all interaction levels contribute significantly to the classification, we aggregate outputs from all experts using the learned routing weights gi, g2, and g3, without applying top-k selection.
4.4 Dual attention computation scheme
Finally, we introduce the dual attention computation scheme to enhance computational efficiency. While the irregularity of graph masks hinders the application of efficient attention variants g, 9 39
their inherent sparsity enables new optimization route sparse attention computation 34 Unlike standard dense attention (Equation]) D. which constructs the full attention matrix Á before applying the binary mask M. sparse attention computes attention scores only for valid node pairs (u, v) where
M. = 1. A detailed analysis of the sparse attention implementation in Algorithm reveals space complexity of (6m (6mm/d)) da). where m is the number of non-zero entries in M, H is the number of attention heads, and d, is hidden dimension of each head. Although this method significantly reduces the complexity from O(N2) to (m)) the constant factor 6H remains non non- non-negligible practice.
To further improve efficiency, we propose dual attention computation scheme that dynamically switches between dense and sparse computation based on the local sparsity of the attention mask. Specifically, we partition the attention mask M into K disjoint regions R. K each R, is
defined by a query set Q and the corresponding key set KG = Uneo, (u MG, = 1]. For each
region, the optimal computation mode is selected according to Proposition 4.2
7

---

Table Node classification results (%+o). ROC-AUC for Minesweeper; accuracy for the rest.
Datasets
Models
Cora
Citeseer
Pubmed
Computer
Photo
Squirrel
Chameleon
Minesweeper
Arxiv
GCN
16.53 75.97
28.51
89.83
93.07.20.48
42.19
42.8722.76
93.4720.47
22.55
GAT
16.53
14.31
87.4210.4 43
20.45
93.7920.25
36.59
41.5224.75
93.25 20.42
12.10go. as
SAGE
17.62
14.79
89.20 53
20.14
94.27
20.61
36.1611.40
42.06g0.01
23.64
72.3220.18
GCN
87.74
76.83
09.48
91.70g0.53
95.10.0.00
42.5922.14
43.7722.47
97.39
73. 18.122
GAT
87.59 7..42
89.1240.47
91.70
95.7340.03
38,3841.25
42.69.2.111
41.35
72.67
SAGE"
17.7 15.99
89.4910
91.5220.00
95.3740.89
39.28
43.23
97.39
72.75
GPRGNN
18
1..0221.81
88.4910.44
90.70
94.8010.37
16.80
41.2622422
89.05
68.44.0.21
FAGON
18.36+1.80
76.78
89.31
90.07
95.23
40.90
42.7823.a1
89.95
66.83
NAGihoomer
87.68+1.60
76.21+2.72
+9.35+
91.22+0.05
95.12+0.5e
38.67+1.47
41.61+2.64
90.08+00.46
71.38+0.20
Exphormer
87.03
1..
88.55
90.76+0.s0
95.1940.40
37.2042.56
40.27=1.63
95.32
72.24
SGFommer
87.8621.12
2..85
88.7540.41
91.52
95.10.0.52
38.60
43.77=3.02
20.28
72.44:20.26
CoBIarmer
18.15
77.05
.e
88.5010.59
59
91.64
95.58g0.55
39.03
43.50
95.63 go.52
73.17
PolyNormer
87.83+1.04
76.93+2.10
49.48+0.48
91.85
95.4440.11
19.32+1.46
44.30=2.04
96.98
73.27+0.88
Mowst
87.92
1..52
28
90.32
93.70.0.32
41.72
44.30g2.57
93.00.0.es
73.03
GCN-MoB
86.17.1.11
15.20
88.80
24
88.75
93.1920.32
43.02
44.5722.00
22.6320.4m 40
73.16 21
M Dphhoreer
1..4 77.53
89.96
40.09 40.91 44.341..04
47.09
20.27
73.54.0.30
Proposition 4.2. Let KR, denote the non-zero rate within region R2, The sparse attention scheme is more efficient than the dense scheme when KR. <
3dh
The proof is provided in Appendix A.5 This result guides the selection of sparse computation when local sparsity high and dense computation when the region becomes sufficiently dense. Based on this guidance, we formulate the dual attention computation scheme as:
MHA (H, M) Comb. (SelectMode (R,) R.))
Here, SelectMode(R.)) denotes the selection between sparse and dense computation modes for region RR, and Comb (.) aggregates the attention outputs from all K partitioned regions.
5 Experiments
Experiment setups. We evaluate M Dphormer on nine datasets, including six homophilic graphs
(Cora, CiteSeer, Pubmed [45). Computer. Photo [33, and Ogbn-Arxiv (19] and three heterophilic
graphs (Squirrel, Chameleon, and Minesweeper 31 Dataset statistics and splitting protocols are
detailed in Appendix(] [ We select 15 baselines spanning five categories: 1) Classic GNNs: GCN (3)
GAT (38), and GraphSAGE [16]. 2) Enhanced Classic GNNs: GCN*, GAT*, and SAGE* 3)
Advanced CNNs: GPRGNN 7 and FAGCN B] 4) SOTA Graph Transformers: NAGphormer [3].
Exphormer (34, SGFormer 43
CoBFormer [44), and PolyNormer [I]: 5) MoE-based GNNs:
Mowst 47 and GCN-MoE 40
Descriptions of the baselines are provided in Appendix E and
implementation details can be found in Appendix F
Node classification results. Table 2 presents the node classification results. Key observations include: 1) Dpphormer consistently outperforms all baselines across 9 datasets, highlighting its superior interaction modeling capacity. 2) Compared to traditional and MoE-based GNNs, D'Dporrrer demonstrates clear advantages by comprehensively capturing hierarchical interactions. 3) Compared to GT baselines, DPDphorner shows notable improvements, verifying both the benefit of comprehensive interaction modeling and the effectiveness of the bi-level attention expert routing mechanism in adaptively integrating multi-level information.
Ablation studies. We perform ablation studies to evaluate Dphoorrer in terms of effectiveness and efficiency. Firstly, construct five ablated variants by: 1) Removing individual experts; 2) Disabling
8

---

Table 3: Node classification results of various Dphormerr variants
Cora
Citeseer
Puhmed
Computer
Photo
Squirre
Chameleon Minesweeper Ogbn-Arxiv
Full Model
88.484
17.53
89.9620.4u
92.09.0.48
90.9
44.34
47.09
=8.2700220 23.54
W/O Local
82.84+2.16
74.09+1.46
88.75+0.4s
88.99.0.94
93.83-0.44
+1.61 42.60+4.441
57.55+a.78
67.24
WVO Cluster
17.8341.43
76.7342
19.6910.16
91.5920.70
95.2220.53
42.48
44.9313.21
98.0310.44
73.4010.23
W/O Global
87.95
76.33
89.76ga.34
91.8920.00
95.6220.39
41.58
45.47
98.02:0.24
73.41
W/O Route
47.65
46.25
49.44
91.76+0.71
95.59 =0.57
42.05
41.21
43.95
97.72+0.17
40.11
W/O Bi-Level
27
77.124
91.622037
95.70
42.41
44.3914.44
97.8410.30
73.50
Memory Usage Across Datasets with Different Computation Schemes
Dasl
Sparso (ODM) Dense (DOM)
207
Minsstepper
Figure 3: Memory usage of different schemes.
the attention expert routing mechanism; 3) Replacing the bi-level attention routing mechanism with a single-level gating scheme. Results in Table show that: 1) Removing any individual expert consistently degrades performance, underscoring the necessity of comprehensively modeling hierarchical interactions. 2) Disabling the routing mechanism leads substantial degradation, suggesting that simple aggregation is insufficient for effectively integrating multi-level interactions. 3) The performance gap between the single-Ievel routing variant and Dpphorreer demonstrates the advantage of the proposed bi-level attention expert routing mechanism. Then, we report the GPU memory usage of M Dphormer and its two variants employing sparse and dense computation schemes in Figure 3 As shown, the dense scheme incurs the highest memory consumption and leads to off-oo-memory (OOM) errors on four datasets. While the sparse scheme substantially reduces memory usage, it still fails to run Ogbn-Arxiv In contrast, our dual attention scheme achieves superior memory efficiency and successfully scales to all evaluated graphs.
Cora
Citeseer
squirre!
Minesweeper
71.
BOC-AIC
27.0
075
37.5
45.0
120
-28
Computer
20.0
95.01
Rocusscy
20.5
45.5
26.0
122
zic
252
zic
Figure 4: Test accuracy vs.
Parameter analysis. The only key hyperparameter in M Dphormer is the number of clusters P. which affects the quality of the cluster mask M For each dataset, we select appropriate range of P values according to its size. Figure presents the model's performance under varying P. Overall, M Dphormeer demonstrates strong robustness to the choice of P on most datasets. An exception is variations P substantially impact the quality of partitioning, resulting in more significant performance fluctuations.
Chameleon-a small graph with only 890

---

Visualization. We plot the accuracy and loss curves of M Dphormer and GCN 26 in Figure Across the training, validation, and test sets, M Dphormer consistently achieves faster convergence and higher accuracy than GCN during the training process, demonstrating the effectiveness of our method. A similar trend is also observed in the comparison with PolyNormer in Appendix G.4 A visualization of the learned gate weights is provided in Appendix G.5
Less Curves
Accuracy Curves Curves
1.2
0.78
0.0
0.7
Ufteiamet vale non
0.74
0.72
BEV jod)
250
750
1.000
1250
1500
3750
2300
5.00
3000
1250
1300
2000
Epochs
Epochs
Figure 5: Comparison of accuracy and loss curves between DF and GCN* on Ogbn-Arxiv.
6
Related Work
Graph neural networks. Classic GNNs, such as GCN (23 SAGE [16.. and GAT 38 rely on message-passing mechanisms that recursively aggregate information from local neighbors at each layer. To move beyond the widely adopted homophily assumption- -that nodes of the same class more likely to be connected [28] advanced GNNs such GPRGNN 77 and FAGCN [3] have been proposed to improve performance on heterophilic graphs. More recently, a benchmark study demonstrated that carefully tuning the hyperparameters of classic GNNs and enhancing them with advanced training techniques-such as residual connections [ and normalization methods 48 21 can lead to substantial improvements in node classification performance. While GNNs have proven effective in many scenarios, they still suffer from a fundamental limitation: message passing primarily captures local interactions, often neglecting informative signals from broader, long-range dependencies.
Graph transformers. graph representation learning. By leveraging the multi-head self-attention mechanism originally introduced in Transformer (37), they aim to adaptively model diverse and complex interactions from a broader perspective. primary line of research treats the entire graph as fully connected and computes attention scores between all node pairs [46 32 11). However, a recent study has revealed the over-globalizing problem in such methods, which may lead to a significant decrease in performance [44] Another line of work constructs token sequence for each node based the graph structure and feeds these sequences into a Transformer to learn node representations [49] 5
Recently, Graph Transformers have emerged promising paradigm for
15 6 41).
These methods often rely on desern-de tokenization strategies, which tend capture local information while overlooking larger-scale interactions. In addition, several recent approaches focus on modeling cluster-level interactions, which have shown promising results in capturing mid-level
structural patterns for graph representation learning [18 20 44).
7 Conclusion
In this paper, we propose unified hicrarchical mask framework for Graph Transformers. A fun- damental design principle and two core challenges identified under this framework. We then introduce M Dphhrrmer, a novel ofaturreof-Experrt based Graph Transformer with Multi-Level Masking and Dual Attention Computation, designed to efficiently, comprchensively and adaptively capture hierarchical interactions. Extensive experiments demonstrate its effectiveness.
Limitations and broader impacts. In this paper, we focus our theoretical and empirical analyses on the node classification task under the proposed unified hierarchical mask framework, as it is fundamental and extensively studied problem in the graph learning community. Extending our theoretical insights to graph-level and edge-level tasks represents promising direction for future work. Apart from this, we do not expect any direct negative societal impacts.
10

---

Acknowledgments and Disclosure of Funding
This work is supported in part by the National Natural Science Foundation of China (No. U20B2045. 62322203, 62172052, 62192784, U22B2038).
References
[1] Abien Fred Agarap. Deep learning using rectified linear units (relu). arXiv preprint arXiv:1803.08375. 2018.
[2] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. urXiv:1607006455 2016.
arXiv preprint
[3] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 195003957,2000
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXiv preprint arXiv:2 14491, 2021.
[5] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification large graphs In The Eleventh International Conference Learning Representations, 2022.
[6] Jinsong Chen, Hanpeng Liu, John Hopcroft, and Kun He. Leveraging contrastive learning for enhaneed node representations in tokenized graph transformers. Advances in Neural Information Processing Systems, 37:85824-85845, 2024.
[7] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations, 2021.
[8] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint 20x:9 14794, 2020.
[9] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in neural information processing systems, 35: 35:16444-16359 2022.
[10] Andreea Deac, Marc Lackenby, and Petar Veličković. Expander graph propagation. In Learning on Graphs Conference, pages 38-1. PMLR, 2022.
[11] Chenhui Deng, Zichao Yuc, and Zhiru Zhang. Polynormer: Aalynomial-xxpressitii graph transformer in linear time. In The Twelfth International Conference on Learning Representations, 2024.
[12] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pro-training of deep bidirec- tional transformers for language understanding. arXiv preprint arXiv: 1810.04805, 2018
[13] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghami. Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[14] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint ar Xiv: 0ttp::9933.2222. 2019.
[15] Dongqi Fu, Zhigang Hua. Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jingrui He, and Bo Long. Ver-graphormer: A mini-bated graph transformer virtual connections. In The Twelfth International Conference on Learning Representations, 2024.
[16] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 2017.
[17] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[18] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generaliza- tion of vit/mlp-mine mixer to graphs. In International conference on machine learning, pages PMLR, 2023.

---

[19] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 13:22118-22133, 2020.
[20] Siyuan Huang. Yunchong Song, Jiayue Zhou, and Zhouhan Lin. Cluster-wise graph transtormer with dual- granularity kernelized attention. Advances Neural Information Processing Systems, 37:33376-33401, 2024.
[21] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448 456. pmir, 2015.
[22] George Karypis and Vipin Kumar. A fast and high quality multilovel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing. 20( 0:359-392, 1998.
[23] Thomas N. Kipf Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[24] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, Bayan Bruss, and Tom Goldstein. Goat: A global transformer on large-scale graphs. In International Conference on Machine Learning, pages 17375-17390. PMLR, 2023.
[25] Qimai Li, Zhichao Han, and Xiao-Ming Wu, Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[26] Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Classic gnns are strong haselines: Reassessing gnns for node classification. arXiv preprint 089993, 2024.
[27] Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Can classic gnns be strong baselines for graph-level tasks? simple architectures meet excellence. In Forty-second International Conference on Machine Learning. 2025.
[28] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27:415-444, 2001.
[29] Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 1905:1905.099 2019.
[30] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference Learning Representations, 2020.
[31] Oleg Platonov. Denis Kuznedelev. Michael Diskin. Artem Babenko, and Liudmilaa Prokhorenkova. A critical look the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023.
[32] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalahle graph transformer. Advances in Neural Information Processing Systems, 35: 45011115554 2022.
[33] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /81 1508668, 2018
[34] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pages 31613-31632. PMLR, 2023.
[35] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 368:127063, 2024.
[36] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint 2021.
[37] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[38] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018
12

---

[39] Guoxia Wang, Jinle Zeng. Xiyuan Xiao, Siming Wu. Jiabin Yang, Lujing Zheng, Zeyu Chen, Jiang Bian, Dianhai Yu, and Haifeng Wang. Flashmask: Efficient and rich mask extension of flashattention. arXiv preprint 4rX1vv2410001359 2024.
[40] Haotao Wang. Ziyu Jiang. Yuning You. Yan Han, Gaowen Liu, Jayanth Srinivasa, Ramana Kompella. Zhangyang Wang, et al. Graph mixture experts: Learning on large-scale graphs with explicit diversity modeling, Advances in Neural Information Processing Systems, 36:50825-508855 2023.
[41] Limei Wang. Kaveh Hassani, Si Zhang, Dongqi Fu, Baichuan Yuan, Weilin Cong. Zhigang Hua, Hao Wu, Ning Yao, and Bo Long. Learning graph quantized tokenizers for transformers. arXiv preprint arXiv:2410.13798, 2024.
[42] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 0127337-227401 2022.
[43] Qitian Wu, Wentao Zhao, Chenxiao Yang. Hengrui Zhang, Fan Nie. Haitian Jiang. Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. In Shirry- Conference on Neural Information Processing Systems, 2023.
[44] Yujie Xing, Xiao Wang. Yibo Li, Hai Huang, and Chuan Shi. Less is more: the over-globalizing problem graph transformers. International Conference on Machine Learning, pages 54656 54672. PMIR, 2024.
[45] Zhilin Yang, William Cohen, and Ruslan Salakhudinov, Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48 48. PMLR, 2016.
[46] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng. Guolin Ke, He, Yanming Shen, Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28888, 2021.
[47] Hanqing Zeng, Hanjia Lyu, Diyi Hu, Yinglong Xia, and Jiebo Luo. Mixture weak and strong experts on graphs. In The Twelfth International Conference on Learning Representations, 2024.
[48] Biao Zhang and Rico Sennrich. Root mean square layer normalization. Advances in Neural Information Processing Systems, 32, 2019.
[49] Wenhao Zhu, Tianyu Wen, Guojie Song. Xiaojun Ma. and Liang Wang. Hierarchical transformer for scalable graph learning. In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference Artificial Intelligence, IJCAI-23, pages 4702-4710, International Joint Conferences on Artificial Intelligence Organization, 2023. Main Track.
13

---

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 abstract and introduction, we highlight that existing Graph Transformers can be unified under hierarchical masking framework. which simplifies model design the construction of appropriate masks and offers a principled foundation grounded in theoretical analysis. Building this framework, we further propose novel Graph Transformer that achieves state ofate-of-the-art performance on node classification tasks.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not 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. It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In Section 7
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best 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.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide full assumptions in Section 3.2 and proof' in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: In Section 5 and Appendix F
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS 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) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: The access details of the datasets are provided in Appendix D and the GitHub repositories of baselines are listed in Appendix Partial implementation of our method is included in the supplemental materials.
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/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nipscc. tttpcc//pbbbc mubllc//guddee httgg//ddd//oeeuubmimis www.//ooieeessiiieeoea wommiissiooiiicy for more details.
The authors should provide instructions on 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, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Section Appendix D and Appendix
F
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: The mean and standard deviation across five independent runs with different seeds are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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 or the standard error of the mean.
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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix F All experiments are conducted on single NVIDIA GPU with 24 GB memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 or failed experiments that didn't make 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 httppp///eaaappp...ppppitttttttt
Answer: [Yes]
Justification: have reviewed the NeurIPS Code of Ethics and believe that the research presented in this paper fully complies with it all respects.
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., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
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 a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The 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 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: [No]
We have cited the original papers in Section Appendix provided URLs of the baselines in Appendix However, we were unable to locate the license information for the assets used.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
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: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor 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 to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if 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.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurips hett:s///eerrrpp.ccc//oofrrrerre /c////ooeeeeeecs///2/////.. for what should or should not be described.
20

---

A Theorem Proofs
We begin by decomposing Theorem 3.1 into two theorems and one proposition, and then prove them individually.
Theorem A.1. The updated representation of node follows a Gaussian distribution:
Le1
[CI
Ln ~ N
kppae
kpaa
1=1
Accordingly, the probability that node u is correctly classified by similarity-based classifier is:
P Me 2 d6) = -1- 6.
kppac
(8)
1= k
where (-)) denotes the cumulative distribution function (CDF) of the standard normal distribution.
Theorem A.2. Assuming the classifier is well trained, i.e., 6 kp. S and the attention weights satisfy 0 S ac I I ac S 1 then the classification probability is bounded as:
kpp
1-4 se kpoac
6 kpeake
S PP 2 66) S -1-6 Φ
(9)
kppaaoo + 1-ps o
Vkp.a20?
where oh maxe ffe o². is the largest representation variance among non-target classes. Proposition A.3, In Equation 9 both the lower and upper bounds are monotonically increasing with respect to k. Pe. and ac. and decreasing with respect the set of variances (o, i [/]]]
A.1 Proof of Theorem A.1
Proof. Let node u have ground-truth label c, and denote its receptive field by the mask vector M..;, which includes nodes in total. Let p; be the proportion of class-í nodes in the receptive field, and let as denote the average attention weight assigned to these nodes.
The updated representation of node is given by:
k
2.
a;
(10)
Each node representation 2, with class label e' generated using the reparameterization trick:
pd + de E. where E, N(,
(11)
Regrouping the neighbors by class, rewrite the update
D
kp:
y
kps
2u
kp +
Σ
o > E
(12)
Since the sum of i.i.d. standard Gaussian vectors satisfies:
E, (,0,
(13)
j=1
we have:
kpc
0700
E,
N'O, o0
(14)
j=1
21

---

Hence, the updated representation 2n follows multivariate Gaussian distribution:
D
Zu ~ N
k
(15)
Define the total variance scalar:
Su
(16)
Using the reparameterization trick again, we can rewrite En as:
D
kp + Su é. where ~ N0,
(17)
Now consider the inner product with the class prototype Mei
D
z Me
Σ
kproatts
Met + (Su E) He
(18)
By orthogonality of class means (H. Me = 1 if and O otherwise), the first term simplifies to kpe Since & (O, I), the second term becomes linear combination of i.i.d standard Gaussians:
= Me kppae + Su Σ Hers. ~0,11)
(19)
Because || 1, the sum Σlm Me, is distributed as (0, 1). Thus:
2 Me N(ksaaee S.:)
(20)
To compute the classification probability, we consider a similarity-based classifier that predicts correctly if:
(21)
Since 2 Me Gaussian distributed, we apply the cumulative distribution function of the normal distribution. For X ~ (N,,, we have:
P(X 2 a) 1-
a
(22)
Applying this to our case:
P P(2 u. 2 6z) =1 $ (5c ---kppcke
5. kpeaa
=1
(23)
Su
V Σ 1 opo?kp,
which concludes the proof.
A.2
Proof of Theorem
Proof. From Theorem A. we know:
& Me N
kpa
Σ kp.aço?
(24)
1
22

---

and the classification probability is:
P 2 2 Me 2 26:) =1- =6)=110
de ke
(25)
Σ kppazo?
Let us denote the variance as:
D
Var = Σ k = kppa +
> op
(26)
ifc
Let ot == m of. Since S for + we have af S 1 R
and hence:
Σ isc
kp.afo? S Σ
kpi
0
Σ
Pc
(27)
k
k
ipc
ifc
Therefore:
Var S 2p.
- Pe k
om
(28)
We now use the fact that the Gaussian CDF (=) is strictly increasing. Under the assumption that d. - kp 0, the numerator is negative. In this case, increasing the denominator (i.e., the variance) reduces the absolute value of z, making less negative. As a result, ((2) increases, and the
classification probability 1 (=) decreases.
This gives the lower bound:
8. kpp
c Me 2 66) 21-11-
(29)
kppazoo 1-p= o
To obtain the upper bound, we lower bound the total variance by dropping the non-negative cross- class terms:
Σ iff
kprafo 20
(30)
which leads to:
Var 2 kp.
(31)
Since the CDF ((=) is increasing and the numerator is negative, smaller denominator results in more negative standardized score, and hence a larger classification probability 4(2). Therefore, this yields the following upper bound:
55 kpoac
P( u. 51
(32)
Vkp.ogo2
Combining both bounds gives the result.
A.3 Proof of Proposition A.3
Proof. We analyze the monotonicity of both the upper and lower bounds Equation 9 by taking partial derivatives of the normalized score with respect to each variable. Let the standardized score be denoted as f()).
Upper bound:
Supper(x:) 8, kpo.e
Vkp.az0?
(1) With respect k: Let C₁ 5cs C2 = Palles C3 = 2. Then:
C1 kC2
(upper()) (k) -kO2Os C.Cs
(k)
2(kCg)3/2 <
(33)
VkC2
23

---

(2) With respect to Pe: Let C2 = kac. C3 ka?o Then:
C1 PoC2
PpoC203 CiC3
Supper (Pc)
(upperle))
0
(34)
V3
2(pcCa)3/2
(3) With respect to aci Let C2 kpc. C3 k.p Then:
C1 C20ke
-C1 =
Supper
Supper
<0
(35)
02vC3
Lower bound:
6. -kppac
flower()) =
kpp + 1-ps 02
(1) With respect to k:
Let C1 de. C2 Polkes C3 poa and C4 = (1 Po)om.
Then the lower bound becomes:
flower (1) C1 kC2
(36)
kO3
Let D(k) kk00+ + C. Then, using the quotient and chain rule, we obtain:
-2C2D2(k) (Cs
( (Ci kC2)
Fawer (k)
(37)
(k)
Now we simplify the numerator:
C4
-2C2D2(1))
C3
(C1 kC2)
C4
C1
2C2 KKCss +
C3
(C1 - kk22)
b
12
3C2C4
-Cyss + C₁
--CCO33
k
Ci(C, -3kC2)
=- - C.Cs+
(38)
Under the assumption that the classifier is well-trained, we have:
C C-3kC²²
3ksp < 8 kpoae <
Hence, each term in Equation 38 is negative, and the overall numerator is negative. Since the denominator (k) O, we conclude:
flowrr (k) < 0
(39)
which means the normalized score decreases with k. and thus the classification probability increases.
(2) With respect to Pa:
Let C1 de. C2 kaa, C3 kazog, and C4 - Then the lower bound becomes:
C1 C2pc
Rower(po)
(40)
VCspe + Ca(1-pc) b
Let D(p.) Vspe + Cal1-pe). b
Then using the chain rule, the derivative is:
-20gD2(pc) (Ca Ca (C, C2pc)
flower (p.)
(41)
2D3
24

---

We now simplify the numerator:
-2C2D (C3-
C4 k
(C1 C2pc)
=C2 2C3 Cap. Ca(l-Pa)
(cs C1
(Ci -2pp))
k.
2C2C4(1- Po)
C4C1
C2paC4
-CC2O3pe
-OyC1 +
+ +C2peC's
k
k
k
202Cs
CapaCa
k + CiC₁
C2Cape - -
+
(42)
k
Hence the full numerator is:
CcCape-CCCs Ca(C2pe + C1 222))
(43)
We now verify its sign. Under the assumption that the classifier is well-trained, i.c.
C1 C2pe = -ppcc < O
C1 < C2pc
which implies:
C1 C2pe 20pp 20 C1 C2pe - 202
Thus the entire numerator is negative, and since D(p.) > 0, conclude:
Koweer (Pe)
(44)
That is, the normalized score decreases Pe increases, and hence the classification probability increases.
(3) With respect to azt
Let C1 &c, C2 = kpec C3 = kp.o2 and C4 1-pe o
Then the lower bound becomes:
k
(a:) C1 C2ac VCaag + C4
(45)
Let D(ae) == /Cza + C₁. Applying the quotient and chain rule, we obtain:
flower (ac) -C2 C3ac((1 C2ac)
(46)
D3
We now expand the numerator:
-2C2 C4) C3a C2ac)
2C2Csa3 - 20201 C.C3a. C2Cza
- C2C3o 2C2C4 - CiCza
(47)
All three terms in the numerator negative, and the denominator is strictly positive. Therefore:
(a.) <0
(48)
This implies that the normalized score decreases as ae increases, and hence the classification probability increases.
(4) With respect to variances a. and om:
In both bounds, de and om appear only in the denominator. Increasing either of them increases the total variance, which increases the normalized score f(z) (i.e., makes it less negative), and hence decreases the classification probability (ff()))
Conclusion: In both upper and lower bounds, the classification probability is monotonically increas- ing with respect to k. Pe. and ac. and monotonically decreasing with respect to {o, {or)!
25

---

A.4 Proof of Proposition 4.1
Proof. Let u, v E V belong to the same cluster, i.c., P(u) = P(v) = p. the dense attention setting defined by mask M the attention weight from to is given by:
exp( k.))
(c3)
EVEP ((p) (u, k,)))
Now consider the two-layer attention structure using mask M In the second layer, node attends to:
Itself, with attention score (2)
Its virtual cluster node p, with attention score Cup
(2)
The virtual node p in the first layer aggregates from all nodes in cluster including with attention (1)
score Opp--
Therefore, the total contribution of node to node through the two-layer structure can be approxi- mated as:
(c3)
(2)
arp (1)
(2)
if
Owv
Crup
(2)
uf
This formulation shows that the dense cluster-wise attention score can be decomposed into a mixture of self-attention and two-hop attention via the cluster-level virtual node. This completes the proof. D
A.5 Proof of Propostion 4.2
Proof. As detailed in Appendix B the space complexity of the dense attention computation is O22hN²), while that of the sparse computation (6hmdd)). By comparing the two, we conclude that the sparse scheme is more memory-efficient when:
m
N
3d
KR.
3dh,
where KR.
denotes the relative sparsity of the receptive field. This completes the proof.
N
B Efficiency Comparison of Attention Computation Schemes
We provide the pseudocode for masked multi-head attention with dense computation scheme in Algorithm T As illustrated, the primary memory overhead stems from storing the raw attention scores S and the normalized attention weights A, both which have space complexity of O In total, the algorithm requires 0(2hN²) memory. In terms of time complexity. the main cost comes from three parts: (1) the linear transformations for generating the QKV matrices, which require O33Nd): (2) the computation of the attention matrix, O(N2d); and (3) the multiplication between the attention matrix and the value matrix, O(Nd)). Summing up, the total time complexity of standard MHA is O(3.Vd &e 2N2d).
26

---

Algorithm Masked Multi-Head Attention
Require: Input Z R-Nxd number of heads h, projection matrices Wo. WK. Wv, binary attention mask M E N
Ensure: Output Y RR-xduui
1: Project imput to queries, keys, values:
Q.K, - ZWo, ZWK, ZWv E R R-Nxdoo
2: Reshape and split into h heads:
Q.K. V E RhxNxdd where dn. = dmmodde/ h
3: Compute raw attention scores (per head):
= QKT ddn
E RANNNN
4: Apply attention mask:
Si.j. -oo (or a large negative constant),
if M.; = if M = 0
S.j
5: Normalize via Softmax:
A softmax (S) E RXNNNN
6: Apply attention weights:
H AV hxNxd.
7: Concatenate heads as the final output:
Y Concathend (H) E N Nxdmati
8: return Y
The sparse attention computation for head i can be formulated as:
W (H, exp W(
head, (H, Σ
H. (
(49)
veM. ElEm, exp )
where M, (v Mu, 1} denote the key of node u, H. H. E Rlxd denote the repre- sentations of node u, and (( w(i)
w( K V E Rdxda are the projection matrices for the i-th head. The outputs of all heads are concatenated to produce the final output: MHA S H, =
Concat(head,, headyy)
Next, we present the pseudocode for Sparse Multi-Head Attention in Algorithm 2 The dominant memory consumption arises from storing intermediate variables Q', K', S', V and H', each contributing to space complexity of ((mhdy), resulting total of (55hhdn). Additionally, computing the output H involves a Scatter.um() operation, which requires an auxiliary buffer of size O(mhd)). ). Therefore, the overall space complexity Sparse Multi-Heal Attention (66mhd)). Regarding time complexity, sparse MHA consists of three main parts: (1) feature transformations. (f (2) sparse attention score computation (Step 4), ((2m)); and (3) output computation (Step 6), O(2md). Therefore, the total time complexity is O33Nd + Ammd). A direct comparison indicates that sparse MHA outperforms standard MHA when
N2 < 2"
m
we apply sparse attention computation most regions, except for attention from global nodes the origin node, which involves dense attention region (where N = 1, as shown in Figure 2). This hybrid design allows our method achieve lower overall time complexity than both standard and sparse MHA, i... miN(O + +NN2
According to our "Dual Attention Computation Scheme" in Section 4.4 and Proposition 42
O(3Nd de + 4md)).
27

---

Algorithm 2 Sparse Multi-Head Attention
Require: Input representation matrix Z R Xxdumal, sparse index mask M E Z2xm, where m is the number of non-zero entries; projection matrices We: WK, Wy E gdumenddnnss number of heads h
Ensure: Output Y N Xdmaki
1: Linear projections:
Q -WW, K= ZWW, V ZWv IR
2: Reshape for multi-head:
Q. V Re
dn = =
3: Index via sparse mask:
Q' = Q
E Rmmxxxds K' = =[[]]
4: Sparse attention score computation:
S' Q' K' E mx
S = SUM(S', dim -1) E mx
5: Apply softmax normalization:
exp((() E R
S sum
Scatter (S, Mo. dim = NRA
S/S.um [Mo] E R
6: Aggregate weighted values:
V V/Mj E mxxxxds
H A V mxxxdd.
H Scattersum (H', Mo, dim 0) E xxhxda
7: Concatenate heads as the final output:
Y Concathend HH) E TR Xddmall
8: return Y
C The Summary Table of GTs and Hierarchical Attention Masks
We summarize many Graph Transformers and their corresponding hierarchical attention masks mentioned in Section i Table
Table Summary of Graph Transformers and their corresponding hierarchical attention mask.
Mask Type
Mask Notation
Representative Graph Transformers
n
GOAT 24] NAGphormer (5), VCR- VCR- Graphormer 15
GCFormer 6
Local Masks
NodeFormer 42 SGFormer 43 PolyNormer I1] CoBFormer 44
2
NAGphormer SS
VCR-Graphormer[[ (15), and GCFormer
M
Graph VTT Cluster-GT 20 CoBFormer
Cluster Masks
2
Cluster-GT[20
CoBFormer
1
NodeFormer SGFormer
Poly Normer
Global Masks
Exphormer 34
28

---

D
Dataset
Table 5: The detailed dataset statistics.
Dataset
#Nodes
#Edges
#Feats
Edge hom
#Classes
Cora
2,708
5,429
1,433
0.83
7
CiteSeer
3,327
4,732
3,703
0.72
PubMed
19,717
44,338
500
0.79
Photo
7,650
119,081
745
0.83
Computer
13,752
245,861
767
0.78
10
Squirrel
2,223
46,998
2,089
0.21
5
Chameleon
890
8,854
2,325
0.24
Minesweeper
10,000
39,402
0.68
Ogbn-Arxiv
169.343
1,166,343
128
0.63
40
D.1 Dataset Statistics
The detailed dataset statisties are listed Table [ The edge homophily is defined as:
u. Yol
E
The Cora, CiteSeer, PubMed [45). Photo, and Computer [33 datasets are available through PyG [4], while Ogbn-Arxiv can be accessed via the OGB platform [9]
Minesweeper datasets are provided in the official repository of The Chameleon, Squirrel, and
D.2 Dataset Splitting Protocol
randomly dividing nodes into training, validation, and test sets with 60%:20%:20% ratio over five runs. For Ogbn-Arxiv, adopt the official split provided in [19]. The remaining datasets are split into 50%:25%:255%
For Computer and Photo, we follow the splitting protocol in 11 15
train/validation/test sets, repeated five times following 442 31).
E Baselines
We compare Dphoomeer against 15 baselines spanning multiple model families:
1) Classic GNNs:
GCN 23 adopts spectral- based convolution that aggregates and transforms features from immediate neighbors using a normalized adjacency matrix. can be interpreted as form of Laplacian smoothing.
GAT 38 introduces self-attention mechanism to assign learnable weights to different neighbors, enabling adaptive and context-aware feature aggregation.
SAGE [66 is inductive framework that samples fixed-size neighborhood and aggregates features through functions such as mean, LSTM, or pooling, allowing generalization to unseen nodes and efficient training on large graphs.
2) Enhanced Classic GNNs: GCN*, GAT* and SAGE* are strong baselines proposed in [26], benchmark study showing that classic GNNs can achieve significantly better performance on node classification tasks by careful hyperparameter tuning and the incorporation of advanced training
techniques, such as residual connections [17] and normalization methods [48] 2 21
3) Advanced GNNs:
To move beyond the widely adopted homophily assumption that nodes of
the same class are more likely be connected (28 -davvanedd GNNs such as GPRGNN 7 and FAGCN [3] have been proposed to improve performance on heterophilic graphs.
. GPRGNN 7 employs generalized PageRank (GPR) propagation scheme, which allows flexible and learnable weighting over multi-hop neighborhood information. This design enables the model to adapt both homophilic and heterophilic graph structures.
29

---

FAGCN [3] introduces frequency adaptive mechanism that modulates the importance of low- and high-freeet -requencyy components the spectral domain. By learning task-specific filter, FAGCN effectively balances local smoothness and discriminative power, making it suitable for graphs with varying levels of heterophily.
4) SOTA Graph Transformers:
NAGphormer 3 tokenizes multi-hop neighborhoods into fixed-length sequences using
Hop2Token module, enabling scalable and efficient node classification on large graphs.
designs a sparse Transformer using expander graphs and virtual global nodes, achieving linear complexity and strong performance large-scale graphs.
Exphormer +d
SGFormer
simplifies the Transformer architecture by adopting shallow attentive propagation without positional encodings, ensuring efficient all -al-pair interactions.
43
CoBFormer mitigates globballaiiiiionn by combining coarse coarse-grained and fine- fine-grained paths, improving the model's balance between global and local information.
44
PolyNormer captures complex structures using polynomial-expreseee attention with linear time complexity, and performs well on both homophilic and heterophilic graphs.
5) MoE-based GNNs:
Mowst 47 introduces a Mixture of Experts (MoE) framework that combines a weak expert (MLP) and a strong expert (GNN). confidence-bant gating mechanism determines whether to activate the strong expert for each node, enabling adaptive computation and improved performance across diverse graph structures.
GCN-MoE 40 applies the MoE paradigm GCNs by incorporating multiple experts with varying neighborhood aggregation ranges. gating function dynamically selects the appropriate expert for each node, enhancing the model's capacity to handle graphs with diverse structural patterns.
Experimental Details
This section provides the detailed experimental setup corresponding the results reported in the main paper.
F1 Training Strategy
We follow the training protocol used in the official implementation of NAGphormer and train it using a mini-batch strategy on all datasets, For all other baselines and our proposed DPDphereer, we adopt full-batch training scheme. The Adam Optimizer is used for optimization.
F.2
M Dphormer Configuration
We implement M Dphormer by stacking multiple D'Dporreer layers. All hyperparameters are selected via grid search over the following search space:
Learning rate: (5 x 10-1, 10 10-3, x 10-3)
Number of M Dphoorrr layers:
Cora, Citeseer, Pubmed, Chameleon, Photo: {2, 3, 4}
Squirrel, Computer, Ogbn-Arxiv: (5, 6, 7)
Minesweeper: {10, 12, 15)
Number of attention heads: {1, 2, 4, 8)
Hidden dimension: {64, 128, 256}
Weight decay: {0, 10 4, x 10 10-3, 5 x 10 10-3)
Dropout rate: {0.3, 0.5, 0.7)
Attention dropout rate: (0.1, 0.3, 0.5)
30

---

Number of clusters:
Cora, Citeseer, Squirrll, Minesweeper: {96, 128, 160, ]92]
Pubmed, Photo, Computer: {160, 192, 224, 256}
Ogbn-Arxiv: {2048}
Chamelcon: {32, 64, 96, 128}
We apply Pre- Fre-RMSNorm 48 before the bi-level expert routing mechanism in each Dphhorrmer layer for most datasets. For Ogbn-Arxiv, however, we adopt BasthBatthNomm due its superior convergence behavior. We adopt GAT-style attention for the local expert due to its computational efficieney, and standard multi-head attention (MHA) for the cluster and global experts. This choice is motivated by the observation in 4 that GAT-style attention suffers from a static attention problem, which can significantly degrade the performance of cluster and global experts.
F.3 Baselines
We implement GCN, SAGE, GAT, GPRGNN, and FAGCN using PyG [14]. For all other baselines, we use the official implementations. The corresponding repositories are listed below:
GCN* GAT* SAGE* http:///ghhhhacoooo//////1/////0
NAGphormer: http:://gggauuooo///////////A//a
Exphormer:
SGFormer: S http://hhaabb.o///t/a//////////0
CoBFormer: http:////////////ooooo//o//////a
Mowst: htwp://ppp.gs.tttooo////////ooss
GCN-MOE: http://////ggggooooooooooo/ooaaa
of Experts
We follow the official training protocols and perform hyperparameter tuning for each model every dataset. The search space is defined as follows:
Learning rate: (5 10-A 10-3 x 10-3)
Hidden dimension: {64, 128, 256}
Dropout rate: {0.3, 0.5, 0.7)
Weight decay: {0, 10-4, 44 5 x 10-4, 10-3, 5 10-3
For models with additional key hyperparameters, we further tune them as follows:
Attention-based models: number of heads {1, 2, 4, 8)
NAGphormer: number of hops E (3, 5, 7, 10, 15)
SGFormer: (0.5, 0.8}
CoBFormer: E {0.9, 0.8, 0.7}; {0.9, 0.7, 0.5, 0.3)
GCN-MOE: number of experts E (3, 4, 5}
FAGCN: {0.3, 0.5, 0.7)
GPRGNN: E {0.1, 0.3, 0.5)
All models are trained on single NVIDIA GPU with 24GB memory. We run each method times and report the mean and standard deviation of the results.
31

---

Table 6: Performance and runtime comparison across datasets.
Cora
Citeseer
Pubmed
Photo
Computer
Chameleon
Squirrel
Dual
5.62s
4.92s
6.41s
5.34s
10.86s
5.58s
12.29s
Dense
6.69s
7.28s
0OM
7.25s
OOM
6.28s
16.45s
Sparse
6,28s
5.67s
7.16s
6.01s
15.56s
7.60s
14.38s
Polynormer
3.59s
2.76s
3.60s
6.02s
4.16s
3.88s
5.53s
G More Experimental Results
G.1 Runtime Comparison
We report the training time of our method over 200 epochs, and compare it against its sparse and dense variants as well PolyNormer [Τ]] The results are summarized in Table We observe that the proposed "Dual Attention Computation Scheme" achieves faster training than both sparse and dense MHA variants. Although it is marginally slower than PolyNormer, the additional cost arises from employing three MHA experts, which are crucial for attaining higher accuracy. Furthermore, our model converges within 200 epochs on most datasets, rendering the time overhead acceptable.
G.2 Graph Classification Performance
We extend our method to graph-level tasks by incorporating edge features and Laplacian positional encodings. To assess the effectiveness this extension, we conduct experiments on two graph classification datasets: OGBG-MOLBACE and OGBG-MOLBBBR, We compare our approach with three widely-used GNN basclines GCN, GAT, and HeNE-which are recognized as strong performers graph-level benchmarks 27
The results are summarized in Table
Table 7: Graph classification performance(% + σ), measured by ROC-AUC.
Method
ogbg-bace
ogbg-bbbp
M Dphormeer
0.80432+0.01040
0.68232:10.00632
GCN *
0.75680=0.01676
0.65146#0.01184
GAT*
0.70199=0..1900 0.65175+00.0121
GINE*
0.0111
0.65095=0000113
As shown in the Table 7 our extended model outperforms the baselines on both datasets, demonstrat- ing its strong potential for graph-level tasks.
G.3 Ablation Study on FFN Variants
In our method, the standard Transformer Feed-Forwart Network (FFN) module is replaced with single linear layer followed by an activation function, such as ReLU M. To investigate the impact of the FFN module node classification performance, we compare MPDphorme with its FFN variants. The results are summarized in Table
Table 8: Node classification results of M3Dphormer and its FFN variant.
Cor
Citeseer
Pubmed
Photo
Computer
Chameleon
Squirre
M3Dphormer
88.48 1.94 77.53 1,56 89.96 95.91 1:0.68
92.09-0..46
47.09 44.34
+FEN
16.50.11.77
29 89.28.10.30
95.37.10.5 91.78.10.72
44.22.12.81 1..36.1182
As observed, incorporating the FFN module often results in a noticeable performance drop, particu- larly on datasets such as Cora, Citeseer, Chameleon, and Squirrel. We attribute this to the relatively simple and easily learnable node features in these datasets. such cases, capturing complex node interactions becomes more critical, task that is more effectively handled by the Multi-Head Attention
32

---

(MHA) module. While MHA is commonly regarded as the core of Transformer architectures, it important note that the standard FFN module typically contains twice as many parameters as MHA (e.g., with a projection of d + 4d - d). Since meaningful structural interactions are primarily modeled through attention, it natural allocate greater capacity to the MHA module.
In addition to the observed performance improvement, reducing or simplifying the FFN module can significantly enhance computational and memory efficiency, making the model more lightweight and scalable.
G.4 Loss and Accuracy Curves For PolyNormer
We plot the accuracy and loss curves of Dphooreer and PolyNormer[11 11 in Figure 6 Across the training, validation, and test sets, M Dphormer consistently achieves faster convergence and higher accuracy than PolyNormer during the training process, demonstrating the effectiveness of our method.
Loss Curves
Accuracy Curves
#'Dohormz
In Jort
0.85
0.78
#FDohorme Deat
14 DoDhor mor vell bus
0.80
Accuracy
Pul, wwy.seL..o
0.75
0.70
0.74
0.70
230
500
250
Epachs
Epochs
Figure 6: Comparison of accuracy and loss curves between DF and PolyNormer on Arxiv.
G.5 More Visualization Results
We visualize the distribution of learned gate weights across node degree bins on Ogbn-Arxiv in Figure 7 Several observations be made: 1) In the first layer, the gate weights remain close the initialization [0.5, 0.25, 0.25]. suggesting that all types of interactions are considered at the early stage. 2) In the second layer, the weights for local and cluster experts increase, indicating a shift in focus toward capturing structural information at local and mid-range levels. 3) In the third and fourth layers, local experts consistently dominate across degree bins. Meanwhile, the gate weights for cluster and global experts exhibit decreasing trend with increasing node degree, reflecting the tendency of low-degree nodes-ofe located near cluster boundaries with low local homophily to rely more broader contextual information. 4) In the final layer, we observe notable shift: the weights assigned local experts decrease as node degree increases, while those for global experts increase. This trend may be attributed to the fact that high-degree nodes have already aggregated sufficient local information, and further local aggregation may lead over-smoothing [25] 29 30 or over-squashing [36] [0].
33

---

Gate Weight vs Node Degree Layer 0
Mean Gate Wetghh
glodal experts
0.2
3.0
20-27
27-34
26-40
40-7
47.84
5441
Node Degree
(a) Layer O
Gate Weight vs Node Degree Layer
0.7
expers dhster experts
gooa) exports
0.5
Gate
2.44
02-
Node Degree
(b) Layer
Gate Weight Node
local expers
chater ecperts glooal exports
Weight
3.6
0.4
(c) Layer 2
Weight
Degree Layer
local expers
clater experts
Weight
0.8
0.2
13-20
20-27
27-34
36-40
40-17
4744
5141
63
(d) Layer 3
Gate Weight vs Node Degree Layer
lutal
cluster
Rean Weightt
2-5
5-13
13-20
20-27
27-54
36-40
40-7
47.34
5441
63-4
Degree
Layer 4
Figure 7: Gate weight distribution across node degree bins for different layers.
34


Reviews:
[{"review_id": "mfKtTAl4W1", "reviewer": "Reviewer_zo8h", "summary": "This paper proposes a unified framework that reconceptualizes various Graph Transformer architectures as the design of hierarchical attention masks, leading to a key design principle: an effective mask must balance a large receptive field with high label consistency. Guided by this theory, the authors introduce M³I, a novel Mixture-of-Experts-based model that adaptively combines local, cluster, and global interaction masks to achieve state-of-the-art results on multiple node classification benchmarks.", "questions": "See Weaknesses. If the more convincing experimental results can be provided, I might consider increasing the score.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. This paper is well-organized.\n2. There is comprehensive theoretical analysis.\n3. The performance is great.\n\nWeaknesses:\n1. The proposed method does not truly achieve state-of-the-art performance. The results reported in papers such as https://arxiv.org/pdf/2410.02296 and https://arxiv.org/pdf/2410.13798 are competitive. More baselines should be included for comparison.\n2. The experimental evaluation is insufficient. Additional experiments, such as analyses of time and space complexity, should be conducted.\n3. The paper claims that the code is publicly available, but the code for the proposed method has not been released.\n4 .The authors only evaluate performance on node classification tasks, which limits the persuasiveness of the proposed method.", "was_revised": true, "final_justification": "The author addressed most concerns", "rebuttal": "We are truly grateful to the reviewer for the constructive comments and valuable feedback regarding our paper. To thoroughly address all the concerns raised, we will provide detailed responses to each question sequentially.\n\n**Compare with recent works**\n\nWe sincerely thank the reviewer for highlighting these recent works. We have carefully reviewed both papers and acknowledge that they are high-quality contributions to the field.\n\nThe first paper[1] proposes a novel approach that integrates large language models (LLMs) with graph neural networks (GNNs) to achieve impressive node classification performance. While the results are indeed strong, we believe this method is not a suitable baseline for our comparison. The approach leverages pre-trained LLMs, which inherently encode extensive world knowledge, and utilizes textual attributes as input features. These text-based features are significantly more informative than the original node features (which are typically simple bag-of-words or structural encodings) used in our setting. Therefore, the problem formulation and input assumptions differ substantially from ours, making a direct comparison less meaningful.\n\nThe second paper [2] proposes a compelling approach that leverages Residual VQ-VAE to learn expressive token representations and employs node sampling strategies to generate transformer-compatible sequences. We have acknowledged this work in the Introduction, highlighting it as a representative method of the second line of Graph Transformer research. During the rebuttal phase, we conducted a comprehensive comparison with GQT on seven node classification benchmarks. Our model consistently outperforms GQT across all datasets, as summarized below:\n\n|      | cora       | citeseer   | pubmed     | photo      | computer   | chameleon  | squirrel   |\n| ---- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| our  | 88.48±1.94 | 77.53±1.56 | 89.96±0.49 | 95.91±0.68 | 92.09±0.46 | 47.09±4.05 | 44.34±1.94 |\n| GQT  | 86.68±1.96 | 75.63±1.87 | 86.51±0.18 | 94.39±0.68 | 90.12±0.06 | 41.26±3.25 | 36.37±2.43 |\n\n**Note:** Although the authors have released their code on GitHub, we found the implementation to be incomplete and containing several bugs. We made our best effort to complete the missing parts and fix the bugs. However, their paper does not provide detailed hyperparameter settings per dataset. Given the time constraints, we conducted a reasonable grid search to tune hyperparameters, but were unable to fully reproduce the performance reported in their paper. We plan to contact the authors for further clarification and will update our comparison accordingly in a future version of the manuscript.\n\n**Time and space complexity**\n\nThanks for your valuable suggestions. We have conducted comprehensive space complexity analysis for standard MHA and sparse MHA in Appendix B. The conclusion is that the total space complexity of standard MHA is $O(2hN^2)$, where $h$ is the number of heads and $N$ is the number of nodes, and the overall space complexity of sparse MHA is $O(6mhd_h)$, where $m$ is the number of non-zero elements in the mask matrix and $d_h$ is the hidden size of each head. According to our proposed \"Dual Attention Computation Scheme\" and Proposition 4.2, the space complexity of our method is the lower bound of standard MHA and sparse MHA, i.e., $\\min(O(2hN^2), O(6mhd_h))$. We have plotted the memory usage of our method and its variants in Figure 3 and Appendix H. The numerical comparison is as follows:\n\n|        | cora    | citeseer | pubmed  | computer | photo   | squirrel | chameleon | minesweeper | arxiv   |\n| ------ | ------- | -------- | ------- | -------- | ------- | -------- | --------- | ----------- | ------- |\n| Dual   | 516 MB  | 552 MB   | 1298 MB | 1986 MB  | 794 MB  | 556 MB   | 1760 MB   | 1700 MB     | 18.9 GB |\n| Sparse | 610 MB  | 648 MB   | 1580 MB | 2364 MB  | 874 MB  | 1980 MB  | 590 MB    | 1900 MB     | OOM     |\n| Dense  | 2108 MB | 3944 MB  | OOM     | OOM      | 5062 MB | 5476 MB  | 618 MB    | OOM         | OOM     |\n\nWe find that our \"Dual Attention Computation Scheme\" is more memory-efficient than both the Sparse MHA variant and the Dense MHA variant, demonstrating the effectiveness of our design.\n\nNow, we analyze the time complexity. For the standard MHA, the time complexity mainly comes from the feature transformations of the QKV matrices ($O(3Nd^2)$), the computation of the attention matrix ($O(N^2d)$), and the matrix multiplication between the attention matrix and the value matrix ($O(N^2d)$). Therefore, the total time complexity of standard MHA is $O(3Nd^2 + 2N^2d)$. For sparse MHA, the time complexity includes the feature transformations ($O(3Nd^2)$), the sparse attention score computation ($O(2md)$, step 4 of Algorithm 2), and the output computation ($O(2md)$, step 6 of Algorithm 2), resulting in a total of $O(3Nd^2 + 4md)$. A straightforward calculation shows that sparse MHA is more efficient than standard MHA when $\\frac{m}{N^2} < \\frac{1}{2}$. \n\nAccording to our \"Dual Attention Computation Scheme\" and Proposition 4.2, we apply sparse attention computation in most regions, except for attention from global nodes to the origin node, which involves a dense attention region (where $\\frac{m}{N^2} = 1$, as shown in Figure 1). This hybrid design allows our method to achieve lower overall time complexity than both standard and sparse MHA, i.e., $\\min(O(3Nd^2 + 2N^2d), O(3Nd^2 + 4md))$.\n\nWe compare the training time (200 epochs) of our method with its variants and PolyNormer[3]. The results are as follows:\n\n|                       | cora       | citeseer   | pubmed     | photo      | computer   | chameleon  | squirrel   |\n| --------------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| base                  | 88.48±1.94 | 77.53±1.56 | 89.96±0.49 | 95.91±0.68 | 92.09±0.46 | 47.09±4.05 | 44.34±1.94 |\n| base_time_200_epoch   | 5.62s      | 4.92s      | 6.41s      | 5.34s      | 10.86s     | 5.58s      | 12.29s     |\n| dense_time_200_epoch  | 6.69s      | 7.28s      | OOM        | 7.25s      | OOM        | 6.28s      | 16.45s     |\n| sparse_time_200_epoch | 6.28s      | 5.67s      | 7.16s      | 6.01s      | 15.56s     | 7.60s      | 14.38s     |\n| polynormer            | 3.59s      | 2.76s      | 3.60s      | 6.02s      | 4.16s      | 3.88s      | 5.53s      |\n\nWe observe that our \"Dual Attention Computation Scheme\" achieves better training speed than both its sparse and dense MHA variants. Although it is slightly slower than PolyNormer, the extra computation stems from the use of three MHA experts, which are essential for achieving superior accuracy. Moreover, 200 epochs are sufficient for convergence on most datasets, making the time overhead acceptable.\n\n**Code**\n\nWe have included an anonymous ZIP archive of our code in the Supplementary Material. The results can be reproduced by running the provided runs.sh script. Upon acceptance of the paper, we will make the complete codebase publicly available on GitHub.\n\n**Performance on graph-level tasks**\n\nWe extend our method to support graph-level tasks by incorporating edge features and Laplacian positional encodings. To evaluate the effectiveness of this extension, we conduct experiments on two graph classification datasets: OGBG-MOLBACE and OGBG-MOLBBBP. Due to time constraints, we compare our method against three widely-recognized GNN baselines—GCN, GAT, and GINE—which have been shown to be strong baselines on graph-level benchmarks [4]. The results are summarized in the following table:\n\n|       | ogbg-bace(ROC-AUC) | ogbg-bbbp(ROC-AUC) |\n| ----- | ------------------ | ------------------ |\n| our   | 0.80432±0.010395   | 0.68232±0.006317   |\n| gcn*  | 0.75680±0.016756   | 0.65146±0.011839   |\n| gat*  | 0.78149±0.01900    | 0.65175±0.012214   |\n| gine* | 0.74799±0.010136   | 0.65095±0.011434   |\n\nAs shown in the table, our extended model outperforms the baselines on both datasets, demonstrating its strong potential for graph-level tasks. \n\n[1] Xu, Zhe, et al. \"How to make LLMs strong node classifiers?.\" *arXiv preprint arXiv:2410.02296* (2024).\n\n[2] Wang, Limei, et al. \"Learning graph quantized tokenizers.\" *arXiv preprint arXiv:2410.13798* (2024).\n\n[3] Deng, Chenhui, et al. \"Polynormer: Polynomial-expressive graph transformer in linear time.\" *arXiv preprint arXiv:2403.01232* (2024).\n\n[4] Luo, Yuankai, et al. \"Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence.\" *arXiv preprint arXiv:2502.09263* (2025)."}, {"review_id": "g5v7VUIkG7", "reviewer": "Reviewer_Exu6", "summary": "This paper introduces M3Dphormer, a graph Transformer architecture, and a framework for modeling graph interactions at multiple levels (local, cluster, global) through hierarchical attention masks. The central premise is that various Graph Transformer (GT) designs can be interpreted as applying different attention mask patterns. The authors unify these under a single masking framework and provide a theoretical analysis suggesting that classification accuracy correlates with a node’s receptive field size and the label consistency of its neighborhood. This leads to the design principle that an effective attention mask should cover a large, label-homogeneous neighborhood. Arguing that no single mask type is optimal across all nodes and graphs, the authors propose combining hierarchical masks.\n \nThe paper then presents M3Dphormer, a Mixture-of-Experts (MoE) based graph Transformer that integrates three mask types (local, cluster, global). The model uses a bi-level gating mechanism to weight expert modules, each associated with a specific mask type. To manage computational costs on large graphs, it employs a dual-mode attention computation that switches between dense and sparse implementations based on mask sparsity. The authors report experimental results on nine benchmark datasets, comparing M3Dphormer against 15 baselines. The model is shown to achieve strong performance across these datasets.\n \nThe main contributions are: first, a unified hierarchical mask framework that categorizes existing GT architectures; second, a theoretical analysis linking receptive field size and neighborhood label consistency to classification accuracy; third, the M3Dphormer model, which features multi-level masks, a bi-level MoE routing mechanism, and a dual-mode attention for scalability; and fourth, an empirical evaluation demonstrating performance gains over baseline models.", "questions": "Ablation on Global Nodes: An ablation study comparing the label-informed global nodes to generic, unlabeled global tokens (as in Exphormer) would be valuable. This would quantify the benefit of injecting supervised signals into the global attention mechanism.\n \nRuntime Performance: Including training time or throughput metrics would provide a more complete picture of the model's practical efficiency alongside pre existing memory usage analysis.", "limitations": "Scope of Evaluation: The evaluation is confined to node classification. While the results are strong, this narrow focus leaves open questions about the framework's generalizability. The performance gains on standard homophilic benchmarks (e.g., Pubmed, Ogbn-Arxiv) are modest, suggesting the model's complexity may not be justified in all scenarios. It would also be informative to compare against a simpler integration of the masks, such as concatenating them and allowing a standard attention mechanism to learn the weights, to better isolate the benefit of the explicit bi-level gating.\n\nLimited Novelty of Components: The novelty is somewhat limited, as individual components are adapted from prior work. The use of virtual nodes for clusters and global tokens has appeared in models like GraphViT, Cluster-GT, and Exphormer. The Mixture-of-Experts (MoE) gating mechanism is also an established technique in GNNs (e.g., GCN-MoE, MOWST). While the specific combination of three expert types within a bi-level gating framework for GTs appears new, the main contribution lies in the integration and empirical validation of these components rather than a fundamentally new algorithmic paradigm.\n\n\nWeaknesses related to component-level novelty and a narrow task focus still remain.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\nModel Design (M3Dphormer): The model architecture directly addresses the issues identified in the analysis. By using separate attention \"experts\" for local, cluster, and global interactions, combined with a bi-level gating mechanism to weight them on a per-node basis, M3Dphormer can adaptively combine information from different scales. The hierarchical nature of the gating—first deciding between local and non-local, then between cluster and global—is a reasonable approach to prioritize local signals while incorporating broader context.\n \nScalability via Dual-Mode Attention: The introduction of a dual-mode attention computation is a practical component for scalability. Since graph attention masks often have irregular sparsity, standard dense attention can be inefficient. The model switches between sparse and dense attention based on a derived criterion (Proposition 4.2) to optimize computation. This results in a significant reduction in memory usage.\n \nEmpirical Performance: M3Dphormer achieves strong empirical results on a range of benchmarks, including both homophilic and heterophilic graphs. The performance improvements are most notable on heterophilic datasets, where multi-scale information is often critical. The model is benchmarked against a comprehensive set of baselines, including recent GTs and tuned GNNs, which strengthens the empirical claims. Ablation studies in Table 3 demonstrate the contribution of each component of the proposed model.\n \nClarity and Organization: The paper is generally well-structured and clearly written. The hierarchical mask framework is introduced with helpful examples (Figure 1) and a clear mapping to prior work (Table 4), which contextualizes the contributions.\n\nWeaknesses\n  \nTheoretical Assumptions and Generality: The analysis is based on a simplified generative model. The class-conditional Gaussian assumption, with orthogonal mean vectors and isotropic variance for each class, is a strong simplification of real-world feature distributions. Furthermore, the model design, particularly the global mask, injects label information from the training set by creating global virtual nodes for each class. This tailors the model to semi-supervised node classification, and its applicability to other tasks (e.g., graph classification, link prediction, or settings with unseen classes) is not demonstrated.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the precious time spent reading through the paper and giving constructive suggestions. Below, we address the reviewer's concerns one by one, hoping that a better understanding of every point can be delivered.\n\n**Theoretical assumptions and generality**\n\nWe thank the reviewer for the insightful comment regarding the assumptions in our theoretical analysis. We acknowledge that the use of class-conditional isotropic Gaussian distributions with orthogonal class means is a simplification and may not fully capture the complexity of real-world feature distributions. However, such assumptions are widely adopted in theoretical studies of machine learning and representation learning [1,2], as they enable analytically tractable results and offer conceptual clarity. Our goal is not to precisely mimic empirical data distributions, but to distill key factors that influence node classification and to provide theoretical grounding for the design of Graph Transformers.\n\nImportantly, our analysis is conducted under the proposed unified hierarchical mask framework, which offers a feasible way for analyzing multi-level interactions. We believe this framework lays the foundation for more refined theoretical studies in the future, potentially under more relaxed or realistic distributional assumptions.\n\n**Extension of our method to graph-level task**\n\nThe label-related global mask in our model is derived from theoretical analysis tailored for node classification. To extend our method to other tasks, we replace this mask with a general global mask, similar to that used in Exphormer[3]. Specifically, we adapt our model for graph-level tasks by incorporating edge features and Laplacian positional encodings, along with the general global mask.\n\nWe evaluate this extension on two graph classification datasets: OGBG-MOLBACE and OGBG-MOLBBBP. Due to time constraints, we compare our method with three widely recognized GNN baselines—GCN, GAT, and GINE—known for their strong performance on graph-level benchmarks [4]. The results are presented below:\n\n|       | ogbg-bace(ROC-AUC) | ogbg-bbbp(ROC-AUC) |\n| ----- | ------------------ | ------------------ |\n| our   | 0.80432±0.010395   | 0.68232±0.006317   |\n| gcn*  | 0.75680±0.016756   | 0.65146±0.011839   |\n| gat*  | 0.78149±0.01900    | 0.65175±0.012214   |\n| gine* | 0.74799±0.010136   | 0.65095±0.011434   |\n\nThese results demonstrate that our method generalizes well to graph-level tasks and outperforms strong baselines, highlighting its flexibility and effectiveness beyond node classification.\n\n**More ablation studies**\n\nWe thank the reviewer for the constructive suggestions. To further validate our design choices, we conducted two additional ablation studies: (1) replacing label-informed global nodes with generic, unlabeled ones, and (2) simplifying the hierarchical mask integration by directly concatenating the three masks and applying standard attention. The results are summarized below:\n\n|                      | cora       | citeseer   | pubmed     | photo      | computer   | chameleon  | squirrel   |\n| -------------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| our                  | 88.48±1.94 | 77.53±1.56 | 89.96±0.49 | 95.91±0.68 | 92.09±0.46 | 47.09±4.05 | 44.34±1.94 |\n| generic global nodes | 88.24±1.70 | 75.80±1.33 | 89.67±0.30 | 95.49±0.43 | 91.76±0.47 | 43.68±4.73 | 42.26±1.91 |\n| mask_concat          | 84.05±1.71 | 75.58±1.68 | 89.22±0.36 | 94.55±0.96 | 91.35±0.77 | 44.13±2.30 | 40.18±2.05 |\n\nWe observe that both variants lead to consistent performance drops, particularly on heterophilic benchmarks (e.g., chameleon and squirrel). For the global nodes, this degradation aligns with our theoretical analysis: generic global masks lack class-specific semantics, limiting their ability to guide meaningful aggregation. In contrast, label-informed global nodes can better capture class-dependent representations and facilitate more targeted global interactions (see Section 4.2). \n\nSimilarly, the mask concatenation variant suffers due to semantic ambiguity—once the masks are merged, the model can no longer distinguish whether an edge reflects local, cluster-level, or global structure. As discussed in Section 3, these interaction levels play distinct roles depending on the graph topology. This highlights the importance of disentangled hierarchical modeling and our bi-level attention MoE, which explicitly separates and selectively leverages structural signals at different scales. Simpler alternatives fail to retain this structural granularity, resulting in reduced effectiveness.\n\n**Run time performance**\n\nWe are pleased to provide a detailed time complexity analysis. For standard multi-head attention (MHA), the computational cost primarily arises from: (1) feature transformations of the QKV matrices ($O(3Nd^2)$), (2) computation of the attention matrix ($O(N^2d)$), and (3) multiplication between the attention matrix and the value matrix ($O(N^2d)$). Thus, the overall time complexity is $O(3Nd^2 + 2N^2d)$. For sparse MHA, the complexity includes: (1) QKV transformations ($O(3Nd^2)$), (2) sparse attention score computation ($O(2md)$, step 4 of Algorithm 2), and (3) output aggregation ($O(2md)$, step 6 of Algorithm 2), leading to a total complexity of $O(3Nd^2 + 4md)$. A direct comparison reveals that sparse MHA is more efficient than standard MHA when $\\frac{m}{N^2} < \\frac{1}{2}$. \n\nIn our \"Dual Attention Computation Scheme\" (Section 4.2), we apply sparse attention in most regions, except for the attention from global nodes to the origin node, which uses a dense pattern (where $\\frac{m}{N^2} = 1$; see Figure 1). This hybrid design enables our method to achieve lower overall time complexity than both standard and sparse MHA, i.e., $\\min(O(3Nd^2 + 2N^2d), O(3Nd^2 + 4md))$. To empirically validate efficiency, we report training times (over 200 epochs) on seven datasets, comparing our method, its sparse/dense variants, and PolyNormer [5]:\n\n|                       | cora       | citeseer   | pubmed     | photo      | computer   | chameleon  | squirrel   |\n| --------------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| base                  | 88.48±1.94 | 77.53±1.56 | 89.96±0.49 | 95.91±0.68 | 92.09±0.46 | 47.09±4.05 | 44.34±1.94 |\n| base_time_200_epoch   | 5.62s      | 4.92s      | 6.41s      | 5.34s      | 10.86s     | 5.58s      | 12.29s     |\n| dense_time_200_epoch  | 6.69s      | 7.28s      | OOM        | 7.25s      | OOM        | 6.28s      | 16.45s     |\n| sparse_time_200_epoch | 6.28s      | 5.67s      | 7.16s      | 6.01s      | 15.56s     | 7.60s      | 14.38s     |\n| polynormer            | 3.59s      | 2.76s      | 3.60s      | 6.02s      | 4.16s      | 3.88s      | 5.53s      |\n\nOur method consistently outperforms its dense and sparse MHA variants in training efficiency.  Although slightly slower than Polyformer, the use of three MHA experts leads to faster and more stable convergence, ultimately resulting in higher accuracy. Furthermore, since the model converges within 200 epochs on most datasets, the additional overhead is acceptable in practice.\n\n**Clarifying the limitations**\n\nWe acknowledge that the performance gains on standard homophilic benchmarks (e.g., Pubmed, ogbn-arxiv) are relatively modest. This is consistent with our theoretical analysis: in highly homophilic graphs, local neighborhood information already provides strong predictive signals, making complex hierarchical modeling less critical. Nonetheless, our method still consistently outperforms strong baselines across all nine datasets and exhibits stable training behavior (see Figure 5 and Appendix H.3). More importantly, our framework is designed to address the challenges of heterophilic or structurally diverse graphs, where multi-level dependencies are essential. On such datasets (e.g., Chameleon, Squirrel, Minesweeper), our model shows substantial improvements, highlighting its strength in capturing complex structural signals.\n\nRegarding novelty, we emphasize that our key contribution lies not only in the specific model, but in the unified hierarchical mask framework. This framework provides a principled and general perspective to reinterpret GTs and enables theoretical analysis of node classification. It also facilitates a extensible way to incorporate hierarchical interactions via mask design, avoiding ad hoc architecture engineering. Our method is a natural instantiation of this framework, guided by both theory and empirical findings. In addition, to the best of our knowledge, this is the first work to integrate the MoE paradigm into Graph Transformers. Unlike prior approaches in NLP and GNNs that define experts as distinct parameter sets or layers, we treat each MHA module—coupled with a specific hierarchical mask—as a relational expert. This introduces a new form of structure-aware specialization, representing a conceptual shift in how MoE mechanisms can be utilized in graph representation learning.\n\n[1] Shen, Ruoqi, et al. \"Data augmentation as feature manipulation.\" *International conference on machine learning*. PMLR, 2022.\n\n[2] Li, Yibo, et al. \"Graph fairness learning under distribution shifts.\" *Proceedings of the ACM Web Conference 2024*. 2024.\n\n[3] Shirzad, Hamed, et al. \"Exphormer: Sparse transformers for graphs.\" *International Conference on Machine Learning*. PMLR, 2023.\n\n[4] Luo, Yuankai, et al. \"Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence.\" *arXiv preprint arXiv:2502.09263* (2025).\n\n[5] Deng, Chenhui, et al. \"Polynormer: Polynomial-expressive graph transformer in linear time.\" *arXiv preprint arXiv:2403.01232* (2024)."}, {"review_id": "r9Bowl0bMf", "reviewer": "Reviewer_BBQq", "summary": "The authors propose a unified framework based on hierarchical masks, demonstrating that existing Graph Transformers are implicitly designed to model hierarchical interactions, and that various interaction types can be effectively captured through the design of appropriate attention masks. Under this framework, they conduct a theoretical analysis of the node classification task and identify a core design principle for Graph Transformers. Guided by this principle, the authors develop M$^3$DPhormer, which integrates theoretically grounded mask designs, a bi-level attention Mixture-of-Experts mechanism, and a dual attention computation scheme. Extensive experiments are conducted to validate the effectiveness of the proposed method.", "questions": "In the standard Transformer architecture, the FFN module is essential for enhancing representational capacity. However, the proposed method seems to omit this component. What is the motivation of this modification?", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The authors propose a unified framework from the perspective of hierarchical masks, which reduces the design space to the construction of attention masks, avoiding reliance on intricate architectural designs. \n2. The authors develop a novel theoretical framework to analyze the distinct roles of various types of interactions and establish a theoretically grounded design principle that can guide future research in the field. The theoretical analysis is comprehensive, and the proofs are rigorous and well-founded.\n3. The proposed method M$^3$DPhormer is novel. Based on theoretical insights, the authors design three hierarchical attention masks and introduce a bi-level expert attention routing mechanism, where each MHA module with a distinct attention mask is treated as an expert. This allows the model to adaptively select the most informative interaction for each node. Additionally, a novel dual attention computation scheme is presented to improve computational efficiency.\n4. Comprehensive experiments are conducted to validate the effectiveness of the proposed approach, demonstrating its advantages over existing methods.\nWeaknesses:\nOverall, the paper is strong. One minor drawback is the lack of discussion on graph-level tasks, which could further demonstrate the generality of the proposed framework.", "was_revised": true, "final_justification": "After reviewing the authors’ response and the discussions among other reviewers, all of my questions is resolved. I will maintain my score.", "rebuttal": "Thank you for your valuable and positive feedback on our work. I’m glad to share our observations regarding the role of the Feed-Forward Network (FFN) module in node classification tasks. \n\n**The impact of  FFN module**\n\nOur experiments reveal that, unlike in NLP and CV domains, the commonly used FFN module does not contribute positively to performance in node classification. The following table presents comparative results across seven benchmark datasets:\n\n|      | cora       | citeseer   | pubmed     | photo      | computer   | chameleon  | squirrel   |\n| ---- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| our  | 88.48±1.94 | 77.53±1.56 | 89.96±0.49 | 95.91±0.68 | 92.09±0.46 | 47.09±4.05 | 44.34±1.94 |\n| +ffn | 86.50±1.87 | 75.53±2.19 | 89.28±0.3  | 95.37±0.54 | 91.28±0.72 | 44.22±2.81 | 41.36±1.82 |\n\nAs shown, adding the FFN module often leads to a noticeable performance drop—especially on datasets such as cora, citeseer, chameleon, and squirrel. We speculate that this is due to the nature of node features in these datasets, which are generally simple and easy to learn. In such cases, capturing complex node interactions becomes more crucial, a task better handled by the Multi-Head Attention (MHA) module. While the MHA is often regarded as the core of Transformer architectures, it is worth noting that the standard FFN module typically contains twice as many parameters as the MHA (e.g., with a projection from dimension $d \\rightarrow 4d \\rightarrow d$). Since meaningful structural interactions are primarily modeled through attention, a natural design choice is to allocate more capacity to the MHA module instead.\n\nIn addition to the observed performance improvement, reducing or simplifying the FFN module can significantly enhance computational and memory efficiency, making the model more lightweight and scalable."}, {"review_id": "QhwIEi68n4", "reviewer": "Reviewer_rvAf", "summary": "This paper revisits Graph Transformers through the lens of hierarchical interactions and proposes a unified hierarchical mask framework, which models different interaction levels via attention masks rather than architectural modifications. This design simplifies the model space and promotes structural consistency. Theoretical analysis under this framework identifies two key factors affecting node classification — receptive field size and label consistency — and argues that no single interaction level suffices across all scenarios. This motivates the integration of multiple levels of interaction. To address this, the authors propose M$^3$DPhormer, which uses three hierarchical masks, a bi-level expert routing mechanism for adaptive fusion, and a dual attention computation scheme for scalability. Experimental results across benchmarks demonstrate the effectiveness of both the framework and the proposed model.", "questions": "1.\tGiven that the main difference between experts lies in their attention masks, have the authors considered sharing parameters across the MHA modules to improve parameter efficiency?\n2.\tThe authors state that node classification performance is positively correlated with label consistency. Could the authors clarify how label consistency differs from the homophily rate?", "limitations": "YES", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: \n1. The paper is well-organized. It starts with a solid review of existing Graph Transformers and introduces a unified hierarchical mask framework. Both the theory and experiments are well-aligned, clearly identifying core challenges in modeling hierarchical interactions and proposing targeted solutions through M$^3$DPhormer. \n2. The framework is valuable in that it shifts focus away from complex architectures, showing that diverse interactions can be captured more cleanly via attention mask design. This abstraction also makes the theoretical analysis more tractable and informative for future model design.\n 3. M$^3$DPhormer is a thoughtful and well-motivated model. The bi-level expert routing supports adaptive multi-level fusion, while the dual attention scheme improves scalability. Experimental results are strong and provide convincing support for the proposed method.\n\nWeaknesses: \n1. More details about the proposed method should be clarified. In particular, it would be helpful to explain how the number of clusters is determined when constructing the cluster-level mask, and how the appropriate computation scheme is selected for different regions within the masks.", "was_revised": true, "final_justification": "The authors' rebuttal has address my concern. Based on the comments of all reviewers, I'd like to keep my score.", "rebuttal": "We are immensely grateful for the reviewer's constructive and valuable feedback. We are dedicated to thoroughly examining each issue raised and providing detailed responses to enhance our paper.\n\n**More Details**\n\nWe have provided detailed experimental settings in Appendix G, and an anonymous ZIP archive containing our code is included in the Supplementary Material. You may refer to Appendix G for specific experimental configurations, and reproduce our results by running the `runs.sh` script included in the provided code.\n\nRegarding the selection of the number of clusters, we preset a range based on the total number of nodes in each dataset to ensure that the cluster sizes remain appropriate. The selected cluster numbers are then treated as a tunable hyperparameter. The specific candidate cluster numbers for each dataset are listed in Appendix G.2. As shown in the parameter analysis in Figure 4 and Appendix H.2, the model’s performance is generally robust with respect to the number of clusters in most scenarios.\n\nFor the design of computation schemes in different regions, we follow the theoretical guidance provided by Proposition 4.2. Specifically, we use sparse attention for the local (local masks), intra-cluster (cluster masks), and node-to-global (global mask) regions, where the low density of non-zero entries makes sparse computation more efficient. In contrast, we use dense attention for the global-to-node region (also in the global mask), as this region is fully connected (all ones), making dense computation more efficient in practice. Experimental results in Figure 3 and Appendix H.1 empirically confirm the efficiency benefits of this design.\n\n**Sharing parameters across experts**\n\nWe conducted an experiment where the parameters of the three attention experts were shared. The results are presented in the table below:\n\n|                  | cora       | citeseer   | pubmed     | photo      | computer   | chameleon  | squirrel   |\n| ---------------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- |\n| our              | 88.48±1.94 | 77.53±1.56 | 89.96±0.49 | 95.91±0.68 | 92.09±0.46 | 47.09±4.05 | 44.34±1.94 |\n| share parameters | 87.06±1.93 | 76.69±1.62 | 89.14±0.48 | 95.24±0.57 | 91.77±0.37 | 43.68±3.79 | 40.50±1.51 |\n\nThese results show that sharing parameters among the three experts leads to a noticeable drop in performance across most datasets. We believe this is because each expert is designed to capture interaction information at a different level. When the same parameters are shared among them, each expert is forced to handle multi-level information simultaneously, which may cause conflicts in the learning process and hinder effective representation learning.\n\n**Homophily rate and label consistency**\n\nWhile the homophily rate captures label agreement among immediate neighbors, our definition of label consistency is more general. It measures label agreement among structurally related nodes across multiple levels—including multi-hop neighborhoods, clusters, and global contexts—rather than being limited to local connections. This broader perspective enables a better understanding of complex interaction patterns beyond simple homophily."}]

Author rebuttal:

Meta-review: This paper proposes a unified hierarchical mask framework for Graph Transformers and introduces a Mixture-of-Experts-based model that adaptively integrates local, cluster, and global attention masks for node classification. The method is theoretically well-motivated, clearly written, and demonstrates strong empirical performance across multiple benchmark datasets, particularly on heterophilic graphs. Most reviewers acknowledged the contributions in terms of methodological novelty, theoretical analysis, and adaptive multi-level fusion, as well as the practical scalability achieved via dual-mode attention computation. At the same time, several reviewers suggested improvements regarding generalizability and reproducibility, including comparisons with more recent baselines, evaluation beyond node classification, analysis of computational cost, and release of code. In response to these comments, the authors provided clarifications on the model design, detailed the cluster-level mask construction and gating mechanism, and highlighted plans for code release and extended experiments. Considering its theoretical contribution, strong empirical results, and responsive discussion of reviewer concerns, I recommend accepting this paper, with potential for broader application in future work.
Decision: Accept (poster)