A Closer Look at Graph Transformers: Cross-Aggregation and Beyond
Authors: Jiaming Zhuo
Ziyi Ma
Yintong Lu
Yuwei Liu
Kun Fu
Di Jin
Chuan Wang
Wenning Wu
Zhen Wang
Xiaochun Cao
Liang Yang
Venue: NeurIPS 2025 spotlight ()
Keywords: Node Classification
Graph Transformer
Cross-attention Mechanism
Primary area: deep_learning

Abstract: Graph Transformers (GTs), which effectively capture long-range dependencies and structural biases simultaneously, have recently emerged as promising alternatives to traditional Graph Neural Networks (GNNs). Advanced approaches for GTs to leverage topology information involve integrating GNN modules or modulating node attributes using positional encodings. Unfortunately, the underlying mechanism driving their effectiveness remains insufficiently understood. In this paper, we revisit these strategies and uncover a shared underlying mechanism—Cross Aggregation—that effectively captures the interaction between graph topology and node attributes. Building on this insight, we propose the Universal Graph Cross-attention Transformer (UGCFormer), a universal GT framework with linear computational complexity. The idea is to interactively learn the representations of graph topology and node attributes through a linearized Dual Cross-attention (DCA) module. In theory, this module can adaptively capture interactions between these two types of graph information, thereby achieving effective aggregation. To alleviate overfitting arising from the dual-channel design, we introduce a consistency constraint that enforces representational alignment. Extensive evaluations on multiple benchmark datasets demonstrate the effectiveness and efficiency of UGCFormer.

A Closer Look at Graph Transformers: Cross-Agrregation and Beyond
Jiaming Zhuo', Ziyi Ma', Yintong Lu', Yuwei Liu', Kun Fu', Di Jin', Chuan Wang", Wenning Wu', Zhen Wang', Xiaochun Cao², Liang Yang Hebei Province Key Laboratory of Big Data Calculation, School of Artificial Intelligence, Hebei University of Technology, Tianjin, China "College of Intelligence and Computing. Tianjin University, Tianjin, China
Schooo of Computer Science and Technology, Beijing JiaoTTong University, Beijing, China SScoool of Artificial Intelligence, OPtics and ElectroNics (iOPEN),
School of Cybersecurity, Northwestern Polytechnical University, Xi'an, China SSchool of Cyber Science and Technology,
Shenzhen Campus of Sun Yat-sen University, Shenzhen, China
j jiaming zhuoeoutlokk com, zyma@hebut. edu.. cn,
(202332803037, 202322800030) hebut edu, cn, fukun@hebut. edu, cn, jindištju. edu. w-zhen@nwpu.co edu. en, caoxiaochunmaill sysu. edu. en, yangliangdvip.gg com com
edu cn, wangchuan@iie ac en, wusenning@nspu. edu en,
Abstract
Graph Transformers (GTs), which effectively capture long-range dependencies and structural biases simultaneously, have recently emerged as promising alternatives to traditional Graph Neural Networks (GNNs). Advanced approaches for GTss to leverage topology information involve integrating GNN modules or modulating node attributes using positional encodings. Unfortunately, the underlying mecha- nism driving their effectiveness remains insufficiently understood. In this paper, we revisit these strategies and uncover shared underlying mechanism Cross Aggre- gation- that effectively captures the interaction between graph topology and node attributes. Building this insight, propose the Universal Graph Eross-attention Transformer (UGCFormer). a universal GT framework with linear computational complexity. The idea is interactively learn the representations of graph topology and node attributes through a linearized Dual Cross-attention (DCA) module. theory, this module adaptively capture interactions between these types of graph information, thereby achieving effective aggregation. To alleviate overfitting arising from the dual-channel design, we introduce consistency constraint that enforces representational alignment. Extensive evaluations on multiple benchmark datasets demonstrate the effectiveness and efficiency of UGCFormer.
Introduction
Node classification, aimed at accurately predicting node categories based on the graph topology and node attributes, is fundamental task in identifying the properties of individual nodes [12
[8] 14 32
10
As a powerful class of models for fusing topology and attribute information graphs, Graph
Neural Networks (GNNs) have achieved initial successes in this task (29 5 12 24
22 25 In general,
(MP) paradigm [16]. While this paradigm endows GNNs with the localizing property, it also restricts their ability to capture long-ran long-range dependencies 9 resulting in well-known challenges such as mor-smotthin 6 59 and over-squashing [17].
they follow the graph-bound Message Passing
*Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Inspired by the remarkable success of Transformers in NLP [35.. Graph Transformers (GTs) have emerged as powerful architectures for node classification tasks. The core component Transformers is the Self-Attention (SA) module 46], which models full interactions among tokens within sequence, thereby endowing the Transformers with globalizing properties. The initial success of GTts can be attributed to the strategic integration of discriminative graph topology into Transformer architectures, enabling the simultaneous capture of structural biases and long-range dependencies.
To date, two primary strategies have achieved SOTA performance in existing GTs: (1) integrating GNN blocks [31 50 7 [T], and (2) modulating node attributes utilizing Positional Encodings (PEs) 44. However, both strategies face inherent limitations. The first tends to inherit drawbacks from GNNs due to its reliance on them, whereas the second introduces additional computational complexity due to the use of PEs, thereby restricting the models' universality and scalability.
2 40
This leads to a fundamental question:
What underlying mechanism drives the effectiveness of diverse Graph Transformers?
A thorough understanding of the underlying mechanisms can offer valuable insights for developing more advanced and efficient architectures. Following this line, this paper theoretically investigates the mechanism shared by the aforementioned types of GTs and, based this insight, proposes novel GT architecture. In particular, the unified cross- tross-aggregation mechanism (as formally defined in Definition D is explored by analytically decoupling topology and attribute representations from node representations. Specifically, the GNN block in GT's can be interpreted as aggregating topology representations into attribute representations (in Theorem I indicating that this category of GTTs inherently incorporates aggreeatgg, Furthermore, GT's employing PEs contain diverse forms of cross-agrregation between topology and attribute representations. Therefore, the shared underlying mechanism among these GTs is cross-aggregation between graph topology and node attributes.
This understanding naturally leads to key question:
How can we design an effective and efficient GT architecture grounded in cross-aggregation.
To this end, this paper proposes the Universal Graph Cross-attention Transformer ( (UGCFormer), which implements the cross- coossggggegntooon mechanism via cross-attention. To be specific, it separately encodes graph topology and node attributes to obtain their initial representations. At its core lies a linearized Dual Cross-Attention (DCA) module that updates the topology and attribute representations by computing cross-attention scores among nodes and utilizing them for weighted aggregation. In theory, the DCA module adaptively captures both correlation and exclusion relationships between graph topology and node attributes, making it simple yet effective. Finally, the two representations are integrated to yield a comprehensive node representation. To prevent representation distortion, a consistency constraint is introduced to enforce mutual alignment between them.
The main contributions of this work summarized as follows:
We theoretically reveal a unified mechanism across typical Graph Transformers, namely cross-aggregation between graph topology and node attributes.
Mechanism Revelation:
Model Innovation: We propose UGCFormer, a GT architecture equipping with linearized Dual Cross-Attente Attentionn (DCA) module that implements the cross-aggregation mechanism.
* Comprehensive Evaluation: Extensive evaluations conducted on sixteen homophilic, het-
erophilic, and large-scale graphs demonstrate the universality and scalability of UGCFormer.
2
Preliminaries
This section begins by presenting the notation used throughout this paper. Then, it introduces the concepts of Graph Neural Networks (GNNs) and Graph Transformers (GTs).
2.1 Notations
The subject of this paper is the widely-used undirected attribute graph, denoted as G(V,E), where V and È represent the node set and edge set. V consists of node instances {xx.. y w>)vev where
'The ability of models to handle both homophilic and heterophilic graphs.

---

X2 E R and Yv E R denote the node attribute and label of node v, respectively. f is the dimension of attributes and is the dimension of labels. & {(;; 22)} terms the edge set. Typically, graph topology is described by the adjacency matrix A E IR where d;,j
only if (vi, 02) E &, and di.j = otherwise. In formal terms, the graph 9 can redescribed as G ((A, X). In the context of semi-supervised learning, the node labels are segmented into two sets: Y L E I R for the labeled nodes and Yu E _ xc for the unlabeled nodes.
To verify the model's universality, this paper examines graphs with varying degrees of homophily. In homophilic graphs, edges are typically formed between nodes with similar labels. Conversely, in heterophilic graphs. edges tend to form between nodes with dissimilar labels 37 60 62
2.2 Graph Neural Networks
Message Passing (MP)-based Graph Neural Networks (GNNs) follow aggregation-coombination strategy. Specifically, the representation each node is iteratively updated by aggregating the features from its local neighbors and combining the aggregated features with its features, which is given by
h A COM (h,- AGG" (fb E ((()))))
(1)
where (v) denotes the set of neighboring nodes node v. For the functions AGG(.) and COM()), vanilla GNNs, e.g., GCN [29]. adopt the sum function to implement them, that is,
H))
H = (AH'W), = X,
(2)
where (.) stands for the nonlinear activation functions, and À = - is the normalized adjacency matrix with À A + W denotes the trainable projection parameters.
2.3 Transformers
Inspired by the success of Transformers in NLP 46 numerous variant models have been designed for multiple fields, including CV (21) and Graph Learning. They typically consist of four functional components: attention module, feed-forward network, residual connection, and normalization.
Self-attention Module. This is a core component of the vanilla Transformer to model intra-sequence relationships among all tokens [46]. Given a sequence containing n tokens H = [h=],-dd e R= the module first projects H into Query (H)), Key l(H)), and Value k(H). It then employs the attention scores calculated from all Query-Key pairs to perform a weighted sum of the Value vectors.
A general formulation of the Self-Attention (SA) module is given by
9 (H)))(H)
SA(H): ASA Soflmar
v(H)
Vd
where g(),, k()), and v(-) generate the Query, Key, and Value via MLPs with learnable parameters W. The attention score So (g T /vd)= E IR=xn is computed via the scaled dot product of full-token pairs, resulting in quadratic computational complexity.
Graph Transformers (GTs), Most existing models [5T I 39 36) 4 53
3 build upon the SA
module. GTs differ from traditional Transformers in how they leverage topology information to capture structural biases. As discussed in the Introduction, two main strategies for incorporating topology information have achieved SOTA performance on node-level tasks: (1) integrating GNN blocks, and (2) modulating node attributes utilizing Positional Encodings (PEs).
Cross-Attention Module. Unlike self-attention, which models the intra-source relationships, cross- attention captures the interactions between two distinct sources. For the features from two different sources H E R xd and Z E Rn2xd, the Cross-Attention (CA) module can be expressed as
(Z)k(H)
CA(Z, H) HC Softmar
(H).
(4)
Vd
After the representation Hc is obtained, it is typically used as the cross source representation to update Z. Due to its exceptional capacity for modeling inter-source relationships, this module has been applied in diverse domains, e.g., NIP [15 and CV (26). However, it has received little attention in Graph Learning, largely due to the lack of motivation and well def-ede applied target. Moreover, similar to the self-attention (Eq. 3), its computational complexity is quadratic, i.e.. ((112))
3

---

Topalogy Space
Residual cormectiin
Topology
embeddings
Oulpul
Baca
Graph topology
Crossattentionnaeeelne mechianism
Raaa
Artribute Space
Ra.
Doca
Comprehensive
Inpur graph
K
representations
K
Artribute emboddiags
Shared
Node attributes
Residual connection
Inputs and geod
The pipeline UGCFormer.
Lincar Attention Module.
Figure I: Overview of the proposed GT architecture UGCFormer and its linear attention module. (a) The pipeline of UGCFormer, which incorporates a dual cross-attention (DCA) module. First, two basic elements of graphs (i.e., graph topology and node attributes) are independently processed in their respective spaces utilizing distinct projection layers fa(-) and fx fx(-). Next, the dual cross- attention (DCA) module with residual connections operates across the topology and attribute spaces, updating each representation by integrating correlated features from the other space. Finally, the two representations are combined produce the final output representation. (b) Illustration of the proposed efficient cross-attention module, where parameters are shared between the query (Q) and key (K), and the representations are computed using linearized attention, given by Q(K QV.
3
Methodology
This section starts by theoretically exploring the functional mechanism shared by Graph Transformers (GTs) that use Graph Neural Network (GNN) blocks and GTs that utilize Positional Encodings (PEs). Inspired by this mechanism, it introduces UGCFormer, a simple yet universal graph cross cross-attention Transformer with linear complexity. Finally, it gives a comprehensive analysis of UGCFormer.
3.1 Motivations
As previously discussed, the underlying mechanism behind the effectiveness of typical GTs remains insufficiently explored. To address this issue, this subsection proposes cross-aggregation mechanism and theoretically examines how it is manifested in the two types of SOTA GT's.
The cross cooss-aggregation mechanism is formally defined as follows.
Definition (Cross-aggregation mechanism) Given two representations B FT Xd2 and Z gng xd2 from different modalities (sources), which share at least one same dimension, i.e., n2 = 122 or dj d2. general formula for two types of cross-aggregations can be expressed
Sim [Z, B)B, Si5S [B, Z), m1 = 112
d, d2.
2
(5)
where Sim B) denotes a similarity function between Z and B, such as cosine similarity.
The first case corresponds to sample (node)-level aggregation, e.g., cross-attention (Eq. 47. while
the second corresponds to dimension (feature)-lett -leeel aggregation [56] 57 61]. When =B,, Eq. 5
reduces to celf-aggregation (e.g., self-attention). Accordingly, two theorems are presented.
Theorem typical Graph Transformers, the diffusion matrix of GNN blocks can be expressed via eigendecompasition as S = UAU where U and A = (iag((>)....... >al)) represents eigenvectors and eigenvalues, respectively (in descending order). Accordingly, the GNN block can be viewed as cross-aggregation between attribute representations XW and topology representations U.A
Theorem Given the modulated node attributes using any PE, i.e., X X;P], where P E Ruxk represents the PE and [:] denotes concatenation operator. PE-based GTs (Eq. 3 inherently contain a cross-aggregatton between attribute representations X.W and topology representations PW.
The proofs for Theorems T and 2 are provided in Sections and respectively. short, the key mechanism of GTs using GNNs and PEs is Cross-Aggregatio between topology and attributes.

---

3.2 UGCFormer
Motivated by the cross- aggreggggnn mechanism explored in the previous subsection, this subsection introduces UGCFormer, a simple yet universal GT. At its core, UGCFormer employs a linearized cross-attention module that implements the cross-aggregation mechanism to capture interactions between graph topology and node attributes. UGCFormer consists of four modules, each of which is described below. The detailed implementation is provided in Algorithm [
Two different projection layers are utilized to independently generate initial representations for the two types of graph information. For simplicity, MLPs are used to process the adjacency matrix A E Ruxx and the attribute matrix X E Rnxx, producing the corresponding initial representations Z and B, that is,
Initial Representation Layer.
Z = MLPA(A), B MLPx E Rexd,
(6)
where MLPA(-) and ML term the MLPs for processing topology and attributes, respectively.
Dual Cruss-attention Module. As an implementation of the cross- aggsegggggo (in Definition I
this module is designed to capture the interactions between these two types of graph information.
However, directly employing the cross-attention (Eg. 4 may result in two issues: (I) unacceptable quadratic computational complexity due to the calculation of dot products for all node pairs, and (2) an increased number of parameters and overfitting risk due to the use of two separate channels.
To alleviate these drawbacks, the proposed Dual Cross-Attention (DCA) module adopts two strategies: (I) linearized attention computation [50] and (2) parameter sharing, as shown in Fig. [Tb). Firstly, through approximating or replacing the Softmax attention utilizing separate kernel functions, the computation order in the SA module can be reordered from the standard (Query x Key) x Value (Eqq. 3) to the more efficient Query x (Keyx x Value) format (28). However, this strategy unsuitable for the cross-atentioon module. Specifically, the attention score k(B) (( E Rd computes the similarity between features within the same space, rather than across different spaces. To ensure cross-space interaction, DCA sets the Key to originate from the same space as the Query. Moreover, DCA shares parameters between the Query and Key to reduce the number of parameters.
To streamline the description of the update process for topology representations and attribute rep- resentations, two abstract representations H, and H2 are introduced. For clarity, layer indices are omitted. The general formulation of the DCA module is given as follows:
DCA(H,, H2):
Q = (HH)
K = k H V ((H)),
(7)
Q Q
K
K
(8)
Q F
KK|FF
V 1
Q VO(KTV)). n
H D
(9)
where q()) and k(-) stand for the Query and Key functions, respectively, with q()) k(-). And (-) represents the Value function. These functions are implemented as MLPs. || - ||= denotes the
Frobenius norm. D Diag(1 + Q(K 1)) stands for a diagonal matrix and 1 is an all-one vector.
The topology-related attribute representations can be obtained BDCA DCA(B, Z). Then, the topology representations are updated via
Ż = (1- Á)ÁV ABDCA:
(10)
where À denotes the normalized adjacency matrix. The first term denotes the topology representation updated purely from the topology space, which can be viewed as being obtained via spectral clustering
48 (4] (see Theorem 3 Ā Tanh(A) stands for a scalar to balance these two terms, where is a
learnable parameter. Combining these two terms allows for the fusion of topological details alongside the topology-related attribute information into the final topology representations.
Similarly, the attribute representations are updated by incorporating relevant information from the topology space, that is, ZDCA DCA(Z, B), with their representations. This can be expressed as
B = (1 - B - 5ZDCA:
(11)
where 5 = Tanh(?)) denotes a scalar to trade off the two terms with y denotes a learnable parameter. Note that DCA requires two separate sets of network parameters to generate the attribute and topology
5

---

Algorithm 1: UGCFormer
Input:
Graph ((A, X) with labels Y. hyperparameters a, and T.
Output:
Trained network parameters O'.
Initialization: Network parameters O,
while not converged do
1. Generate two initial node representations Z and B via Eq. 6
2. Get two updated node representations Z and B via Eqs. 10 and
Obtain the final predictions Y via Eq. 12
4. Calculate the overall loss fiinal via Eqs. 13 and 14
5. Optimize the parameters via e* < Adam ( 9);
end
return Parameters θ*
representations, e.g., (-(.) and qx (+) represent the Query for graph topology and node attributes, respectively, as shown in Fig. !
Prediction Layer. After obtaining the topology representations Ž and attribute representations B through / layers, the final node representations can be generated by weight combining them. Next, the predictions are generated via an MLP network and nonlinearities (i.e., So Softmar())) that is,
Y Sofoomma (MLP ( (11-a)2 + +aB)
(12)
where ar denotes scalar that adjusts attention to topology and attribute representations. Y E Rnxe represents the predictions, indicating the estimated outcomes for each of the n nodes across e classes.
Objective Function. Note that the proposed DCA module, with large number of parameters across two distinct spaces, is susceptible representation distortion caused by overfitting [8, especially when the number of training nodes is limited. Thus, a consistency constraint is introduced to align the two representations Z and B. First, pseudo-labels are derived by averaging the two representations. For node its pscudo-label can be computed y. = =2, + b.). Next, low-entropy pseudo-labed are obtained through sharpening technique that controls the sharpness of the distribution. This can
be formulated as Øt.j / Ei= Bo.j. (0 S j S c 1). where (0, 1] denotes scaling factor that controls the sharpness of the distribution.
Once the pseudo-label is obtained, the next step is to calculate the squared Euclidean distance between and the two representations, which is given by
1 n-1
Loom (2, B) = 2 Σ (I.S:- - -111-2113:1 l1y: - (b:1))
(13)
The overall objective of UGCFormer is to minimize the weighted sum of the cross-entropy loss and the consistency loss, defined as follows:
Loverall Loe B.econ
(14)
where Lee = - Evev, yo log and 3 stands for a balance hyperparameter.
3.3
Model Analysis
This subsection provides comprehensive analysis of UGCFormer. First, the computational complex- ity of UGCFormer analyzed. Then, the simplicity of UGCFormer is examined through architectural comparison with existing GTs. Finally, the effectiveness of UGCFormer is theoretically justified.
Complexity Analysis. UGCFormer operates with linear time complexity. The time complexity for generating initial representations through the projection layer is (md nd?) as the adjacency matrix sparse, where mn represents the number of edges. Secondly, owing to the linearized cross-attention module, the aggregation operator incurs a computational overhead of O(nd²). Finally, obtaining the predictions involves feature mapping and element-wii wise operations, resulting a complexity of O(n)). UGCFormer operates with linear space complexity. The space required to store the input topology

---

Table 1: Accuracy (ACC) or ROC-AUC in percentage (mean over 10 trials of the node classifica- tion task on homophilic graphs. Best and runner-up models are in bold and underlined, respectively.
Model Metric
Cora ACC1
CiteSeer ACC
PubMed ACC
Photo ACC
Physies ACC t
Questions ROC-AUC
ACC f
Avg
Rank
GCN
81.6040.40
71.602a.40
78.80_0.00 22
92.92 92.92+0.12
96.18
76. 28.
84,30
13.29
GAT
83.00
12.10+1.10
79.00_0.40
93.87
93.61
96.17
74.0440:56
84.67
11.43
GraphSAGE
82.68+0.47
71.93+0.5
-9.41-0.33
94.59+0.14
93.11
46.49
76.4440.62
85.00 65.06
9.71
APPNP
83.3010.50 11.8010.50
80.10
94.3210.14
94.4910.07
16.54
15.23
85.15
8.14
GPR-GNN
84.20=0.50 71.60+0.80
80.07=0.02
94.4940.16
95.13+0.0
96.8520.08
67.15+1.92
84,21
8,71
LINKX
77.9540.12
68. 2.2
77.36-u.42
91.97
94.77
96, 20.2
75.71+1.40
83.19
13.14
GloGNN
00.17 71.74
80.37_u.95
95.
10
95.00+0.10
67. 67.15 96.97
1.22
84.07
8.43
GraphGPS
82.8441.0e .os
72.73
79.94_0.26
95.06
93.93+o.12
97. 19
71.73+1.44
84,76
8.29
NodeFormer
82.20
72.50+1.10
79.90-1.00
03.4620.a5
95.64+0.22
96.24=0.24
74.27+1.46
84.89
9.57
NAGphormer
82.1211.18
11.47:1.30
79.73
95.4910.11
95.75
27.34
14.98
85.27
7.71
Exphormer
82.77
11.6311.19
79.46
0.35
95.3510.22
94.9310.01
16.80
14.77
85.10
8,86
GOAT
83.18+1.27
11.99+1.20
19.13_0.38
92.96
94.38
96.45520.2
75.76+1.66
84.81
10.00
SGFormer
84.50
02.60
80.30=a.60
95. 10
94.78
96.60=a.18
12.15
85. 14
6.57
Polynormer
83.2510.03
72.31 7.
49.24_0.43
96.46
95.53
97.27
76.91
85.85
4.71
Gradformer
82.95
72.80 10.59
80.14
95.76
94.21 10.29
97 97.06
74.7111.07
85.38
6.14
UGCFormer
84.94
73.41 20.27
81.79
20.51
96.21 10.31 95.91 10,23
20.1
77.02.0.76
86.666
1.14
and attributes is O(m + rd), where m corresponds to the number of edges and ni accounts for the feature matrix. The aggregated and updated representations each require O(nd) space, since their dimensions do not exceed those of the input feature matrix. In the linearized attention computation (Fig. ()). the attention matrix contributes an additional (dd?) space overhead.
Components. To leverage discriminative graph topology and capture structural biases, existing GTs often resort to auxiliary components that compromise their efficiency and effectiveness. Specifically, the positional or structural encodings (e.g., Laplacian eigenvector encodings) used in GraphGPS (9), NAGphormer (2) Exphormer [4), and GOAT [1 as well as augmented training losses (e.g.. edge regularization loss) in NodeFormer, often necessitate cubic computational complexity and quadratic space consumption. Moreover, the GNN module tends to generate representations that are susceptible to issues caused by the limited message passing. In contrast, the proposed UGCFormer features a streamlined and efficient design that relies solely a linear cross-attention module.
Theoretical Justification. Though designed be simple and intuitive. the proposed UGCFormer is theoretically guaranteed to be effective from a graph optimization perspective [55 58
Theorem 3. Let Z and B denote the topology representations and attribute representations, respec- rively. The representation update in the dual gross-attention module DCA (Eq. 100 and Eq. 77) is equivalent to solving an optimization problem with the objective function:
arg min X Tr(Z Li) + - (B-MLP(X) - Z B Z,B
(15)
where L terms the Laplacian matrix of A. X and 17 are the scalars used to balance these three terms.
In Eq. 15 the first term stands for relaxed optimization problem widely used in spectral clustering 48). Thus, the DCA seeks to generate topology representations that capture mesoscopic community structures. The second term measures the distance between the attribute representation B and its initial representation M (X). The third term denotes the statistical dependence measure, approximated by the Hilbert-Schmidt Independence Criterion (HSIC) [9], that is, HSIC B) s Tr(zZ' BB T) ||Z BlI which reflects the dependence between topology and attribute representations. Therefore, the interaction, whether mutual correlation (positive weights) or exclusion (negative weights), can be modulated by the parameters. In summary, TheoremBjinde indicates that UGCFormer focuses on learning representations by mining the interactions of two basic graph information.
4 Experiments
This section evaluates the effectiveness and universality of the proposed UGCFormer by comparing its performances against various diverse graph learning models on the node classification task. Morcover,
7

---

Table 2: Accuracy (ACC) in percentage (mea over 10 trials of the node classification task on heterophilic graphs. Best and runner-up models are in bold and underlined, respectively.
Model Metric
Cornell ACC f
Texas ACC
Wisconsin ACC t
Actor ACC
Chameleon ACC
Squirrel ACC
Ratings ACC
Avg
Rank
GCN
28.41
65.6144.60
61.2825.87
30.63_0.62
13.43.1102
41.30.0..4
47.77
49.78
11.57
GAT
58.29-3.52
60.73+66.0
63.6446.18
30.36_0.94
40.1441.67
35. 35.09-0.70
47.95
48.03
14.57
GraphSAGR
75.95
62.4316.07
81.1814.56
34.23 1.07
39.11
36.4612.16
53. 10.54
57.50
11.00
APPNP
73.68=3.97
74.57
35.18 70.61
39.4213.87
38. 13.1322.67
49.78g0.72
54,49
12.71
GPR-GNN
78.11=6.55 81.35
82.55+622
35. 35.16-0.s5
39 39.93
38.95
43.90
57.14
11.86
LINKX
77.84 74.60 18.37
75.49
36, 16,10 1.55
40,0212.33
39.8 1..8812.8
51.36
10.47
56.47
11,00
GloGNN
83.51 84.32+4.15
87.06
37.35=1.30
38 18.443
30.30
37.28
56.89
8.14
GraphGPS
82.06=5.7a
82.21+6.14
85.36+4.24
36.18=1.27
40.7944.08
39.67
53.10.o.4z
59.91
7.29
NodeFormer
82.1516.72
81.68
13.41
36.28
43.0912.81
40.61
60.122..66
59.62
7.43
NAGphormer
79.97=0.07 80.18+4.57
82.97
34.36-0.75
44.61+3.10
41.27=1.00 .9
62.51
59.41
7.86
Exphormer
83.07=4.31 $2.81
83. 83.90+4.31
41.63+3311 36.82=1.95
40.32-11.0
52. 52.08
60.06
6.00
GOAT
83.18-1.27 71.99
79.1310.38
36.55_1.19
42 12.56113.17
40.81
19.68.0.50
$7.70
8,53
SGFormer
81.64_3.88
84.29+5.67
83.59
44.93.33.1 37.79+1.60
41.80_2.27
48.01 +0.40
60.29
4.86
Polynormer
81.90_4.17
82.17
83.95
17.01
41.97 13.18
40.87 1.96
53.29
10.23
60.22
5.14
Gradformer
83.06 16
12.19
84,2642.24
40.73 36.5820.71
60
40.29
53.
10.29
60.03
6.43
UGCFormer
85.14_5.83
44.59+4.69
87.36
37.41
L.79 0.79
43 43.2842.17
41.56 12.01 53.48
61.83
1.71
it provides additional analysis experiments to enhance the understanding of UGCFormer. Refer to Section E for details on the datasets, baselines, and experimental setups.
4.1 Experimental Results
Homophilic Graphs. The experiment results for node classification on homophilic graphs are shown in Tab. [ from which three key observations can be made. Firstly, the performance of the backbone GNNs (e.g.. GCN and GAT) lags behind that of GTs. To be specific, on six of the seven homophilic graphs, the models that rank in the top two positions are GTs. This is primarily because most GTs, such as NAGphormer, are built upon these backbone GNNs and specifically address the shortcomings of GNNs in capturing mange dependencies. Secondly, the proposed UGCFormer outperforms all baseline GTs across six of the seven datasets and achieves the optimal rank, demonstrating its consistent superior performance. In particular, on PubMed, UGCFormer achieves a performance that is 2.55% higher than the baseline Polynormer, which has an average rank of second, and its average rank is significantly lower. Thirdly, compared with the baseline LINKX, which also processes graph topology and node attributes separately and does not leverage message passing, UGCFormer consistently achieves better results across all datasets. This can be attributed to its ability to capture the interactions between these two types of graph information and alleviate the representation distortion, which LINKX does not account for. This highlights the rationality of UGCFormer's 's design.
Heterophilic Graphs. Tab. 2 shows the results of the node classification task on seven heterophilic graphs, highlighting three key observations. Firstly, the baseline GTs perform slightly better than the baseline GNNs, but the difference is not substantial. In specific, the baseline GNNs, particularly GloGNN on Cornell, Texas, and Wisconsin, and GraphSAGGE on the Ratings, achieve top-two results on five of the seven datasets. This can be attributed to the high complexity and large number of parameters in GTs, which make them prone to overfitting. Therefore, the baseline SGFormer, which linearly combines the local representation from the GNN module and the global representation from the GT module, achieves superior performance. This is evidenced by its ranking in the top two for three datasets. Secondly, the proposed UGCFormer outperforms the GT baselines on the majority of heterophilic graphs, proving its effectiiveness. For example, on Cornell, UGCFormer exceeds the second-ranked GT, i.e., GOAT, by significant margin of 1.96%. Thirdly, UGCFormer consistently outperforms the baseline LINKX on all heterophilic datasets, highlighting the significance of capturing the relevance between graph topology and node attributes. Overall, UGCFormer achieves performance improvements on both homophilic and heterophilic graphs, demonstrating its universality.
Scalability Study. To evaluate the scalability of the proposed UGCFormer, this experiment quantita- tively changes the network size and records the running time and GPU memory usage. Specifically, utilizes the ogbn-arxiv to randomly sample subsets of nodes, with the node numbers varying from 10K to 100K, As shown in Fig. 2 the running time and GPU memory usage of UGCFormer increase linearly with the size of the sampled graph. For example, the training time and memory usage with
8

---

100k nodes are approximately five times higher than with 20k nodes, This indicates that UGCFormer
exhibits linear time and space complexity, consistent with the conclusion in Section 3.3
Training time
GPU memory cost
200
Memory(GB) (GB))
Time(ms)
# nodes(10k)
nodes(10k)
Figure 2: Training time and GPU memory usage of UGCFormer.
Node Property Prediction.
This experiment seeks to eval-
Table 3: Node property prediction per-
uate the effectiveness and scalability of GTss by comparing them with GNNs on two large-scale benchmark datasets. Upon examining Tab. B which presents the results of the node property prediction task on these two datasets, two key conclusions can be drawn. Firstly, the backbone GTs generally outperform the backbone GNNs, which not only highlights the superiority of GTss but also underscores their scalability-a key challenge that GT's aim to address. This be attributed to the integration of the GNN blocks in GTs, exemplified by SGFormer. These GTs generate the fi- nal prediction by combining the local representations from the GNN module with the global representations from the GT module. Secondly, the proposed UGCFormer achieves optimal performance on these two datasets, indicating its effectiveness and scalability on large graphs.
formances on two large-scale graphs.
Model Metrie
oghn-proteins ROC-AUC
ogbn-arxiv
ACC
GCN
72.51
71.74.0.2
GAT
72.02.0.44
71.95
GPRGNN
71.10.0.12
71.1020.12
LINKX
66.1810.33
71.5910.71
GruphGPS
76.83 76.8320.26
20.47
NodeFormer
77.45+1.15
67 67.19+0.83
NAGphormer
73.61 20.33
70.13.0.50
Exphormer
74.5820.26
72.4420.22
GOAT
74.84
72.41
SCFormer
79.53
72.63
Polynomner
78.97
73 13.46...16
Gradformer
77.64
72.71
UGCTormer
79.95
74.02
4.2 Additional Analysis
Ablation Study. This experiment evaluates the contributions of the proposed gross-attention module and the consistency constraint by comparing UGCFormer with two variants lacking these components. Fig. 3 shows that these variants consistently underperform UGCFormer across the four datasets. This illustrates that the efficacy of UGCFormer stems from the collective contribution of all components. Besides, even without the consistency loss, the variant model (w/o Leon) still provides competitive performance compared the baseline GT's as seen in Table This highlights the effectiveness of the cross-attention module and thereby reaffirms the rationality of the UGCFormer architecture.
awo CA w L_con UGCFormer
UGCFormer
UGCFormer
Porformance
97.0
07.45
100
Accuracy(%)
90
Cara
80
CiteSeer PubMed
CiteSeer
20
PubMed
Photo
CS
Physics
Questions
70
Datasets
layers
dimensions
Figure 3: Impact of functional components (i.e., the CA and consistency constraint).
Figure 4: Performance variations for varying I. variations for varying d.
Figure 5:
Performance
Parameter Sensitivity Analysis. These experiments aim to provide an intuitive understanding for
the selection of hyperparameters. Performance changes due to varying the number of layers (1)
and layer dimensions (d) are shown in Figs. and 5 respectively. Number of Layers. Fig. 4
shows that UGCFormer achieves stable performance across various layer numbers (1, 2, 4, 5). Specifically, performance fluctuations are minimal, within 2.2% on the Cora, 1.4% on the CiteSeer, and 1.3% on PubMed. This indicates that UGCFormer is relatively insensitive the number of layers. Additionally, optimal performance is achieved with {3, 4}. likely due to the risk of wer-shmothing in

---

deeper models. Hidden Layer Dimension. As shown in Fig. 5 UGrmereer maintains consistent performance across the hidden dimension range {64, 128, 256, 512]. For example, on the Cora, which shows the most significant performance variation, the difference is less than 2%. This indicates that UGCFormer not sensitive to this parameter. Additionally, optimal performance on the three datasets corresponds to d E {128, 256). rather than the highest value of 512. This suggests that larger dimensions can lead to overfitting and distorted representations. Additional hyper-parameters (including and B) are analyzed in Section E,4
5 Conclusions
By revisiting two typical Graph Transformers (GTs), this study has uncovered a potential functional mechanism: cross-aggregation between graph topology and node attributes. To effectively implement this mechanism, this paper introduces UGCFormer, a linearized graph cross-attention Transformer. Extensive experiments on sixteen graph benchmarks demonstrate its effectiveness and efficiency.
Acknowledgements
This work was supported in part by the National Natural Science Foundation of China (No. 925701 18, U22B2036, 62376088, 62272020, 62025604, 923701 11, 62272340, Hebei Natural Science Foundation (No. F2024202047), in part by the National Science Fund for Distinguished Young Scholarship (No. 62025602), in part by the Hebei Yanzhao Golden Platform Talent Gathering Programme Core Talent Project (Education Platform) (HJZD202509), in part by the Post- graduaaas Innovation Fund Project of Hebei Province (CXZZBS2025036), in part by the Tencent Foundation, and in part by the XPLORER PRIZE.
136549), in part by the
References
[1] Dexiong Chen, Leslie O' O'Bray, and Karsten M. Borgwardt. Structure-aware transformer for graph representation learning. ICML, volume 162, pages 3469-3489, 2022.
[2] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification large graphs. In ICLR, 2023.
[3] Jinsong Chen, Chenyang Li, Gaichao Li, John Hopcroft, and Kun He. Rethinking tokenized graph transformers for node classification. CoRR, abs/2502.08101, 2025.
[4] Jinsong Chen, Hanpeng Liu, John E. Hopcroft, and Kun He. Leveraging contrastive learning for enhanced node representations in tokenized graph transformers. In NeurIPS, 2024.
[5] Zhaoliang Chen, Zhihao Wu, Ylli Sadikaj, Claudia Plant, Hong-Ning Dai, Shiping Wang, Yiu- Ming Cheung, and Wenzhong Guo. Adedgedrop: Adversarial edge dropping for robust graph neural networks. IEEE Transactions on Knowledge and Data Engineering. 37(9):4948-496 2025.
[6] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
[7] Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expresive graph transformer in linear time. In ICLR, 2024.
[8] Claudio Filipi Goncalves dos Santos and João Paulo Papa. Avoiding overfitting: A survey regularization methods for convolutional neural networks. ACM Comput. Surv., 54(10s):213:1- 213:25, 2022.
[9] Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In NeurIPS, 2022.
[10] Ruiyi Fang, Bingheng Li, Zhao Kang, Qiuhao Zeng, Nima Hosseini Dashtbayaz, Ruizhi Pu, Charles Ling, and Boyu Wang. On the benefits of attribute-driven graph domain adaptation. In ICLR, 2025.
10

---

[11] Ruiyi Fang. Bingheng Li, Jingyu Zhao, Ruizhi Pu, Qiuhao Zeng, Gezheng Xu, Charles Ling, and Boyu Wang. Homophily enhanced graph domain adaptation. In ICML. 2025.
[12] Ruiyi Fang, Liangjian Wen, Zhao Kang. and Jianzhuang Liu. Strueture-preseriing graph representation learning. In ICDM, pages 927-932. IEFE, 2022.
[13] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. 2019.
CoRR, abs//903.000000
[14] Chaofan Fu, Guanjie Zheng, Chao Huang, Yanwei Yu, and Junyu Dong. Multiplex hetero- geneous graph neural network with behavior pattern modeling. In SIGKDD, pages 482-494, 2023.
[15] Mozhdeh Gheini, Xiang Ren, and Jonathan May. Cross-attention is you need: Adapting pretrained transformers for machine translation. In EMNLP, pages 1754-1765, 2021.
[16] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. ICML, 2017.
[17] Francesco Di Giovanni, T. Konstantin Rusch, Michael M. Bronstein, Andreea Deac, Mare Lackenby, Siddhartha Mishra, and Petar Velickovic. How does over-squashing affect the power of gnns? Trans. Mach. Learn. Res., 2024.
[18] Maoguo Gong, Hui Zhou, A. K. Qin, Wenfeng Liu, and Zhongying Zhao. Self- Self-paced co-training of graph neural networks for sumi-super node classification. IEEE Transactions on Neural Networks and Learning Systems, (H(1)):9244 -9247, 2023.
[19] Arthur Gretton, Olivier Bousquet, Alexander J. Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-schmidt norms. In ALT, volume 3734, pages 63-77, 2005.
[20] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, pages 1024-1034 2017.
[21] Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey on vision transformer. IEEE transactions on pattern analysis and machine intelligence, 45(1):87-110, 2022.
[22] Dongxiao He, Yongqi Huang, Jitao Zhao, Xiaobao Wang, and Zhen Wang. Str-gel: Structural commonsense driven graph contrastive learning. In WWW, pages I 1129-1144 1141, 2025.
[23] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning on graphs. In NeurlPS, 2020.
[24] Yongqi Huang, Jitao Zhao, Dongxiao He, Di Jin, Yuxiao Huang, and Zhen Wang. Does gel need a large number of negative samples? enhancing graph contrastive learning with effective and efficient negative sampling. In AAAI, volume 39, pages 17511 1-15118, 2025.
[25] Yongqi Huang, Jitao Zhao, Dongxiao He, Xiaobao Wang, Yawen Li, Yuxiao Huang, Di Jin, and Zhiyong Feng. One prompt fits all: Universal graph adaptation for pretrained models. arXiv preprint arXiv:2509.2244
2025.
[26] Zilong Huang, Xinggang Wang, Yunchao Wei, Lichao Huang, Humphrey Shi, Wenyu Liu, and Thomas Huang. Cenet: Criss-cross attention for semantic segmentation. IEEE Trans. Pattern Anal. Mach. Intell,, (166))686666088 2023.
[27] Md. Shamim Hussain, Mohammed J. Zaki, and Dharmashankar Subramanian. Global self- attention as a replacement for graph convolution. In KDD. pages 655-665. ACM, 2022.
[28] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In ICML, volume 119, pages 5156-5165, 2020.
[29] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.

---

[30] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
[31] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A global transformer on large-scale graphs. In ICML, volume 202, pages 17375-17390, 2023.
[32] Xiang Li, Chaofan Fu, Zhongying Zhao, Guangjie Zheng, Chao Huang. Yanwei Yu, and Junyu Dong. Dual-channel multiplex graph neural networks for recommendation. JEEE Transactions on Knowledge and Data Engineering, 37(6)3337733341, 2025.
[33] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In ICML, volume 162, pages 13242-132562 2022.
[34] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on con-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, pages 20887-20902, 2021.
[35] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers. AI Open, 3:1 11-132, 2022.
[36] Chuang Liu, Zelin Yao, Yibing Zhan, Xueqi Ma, Shirui Pan, and Wenbin Hu. Gradformer:
Graph transformer with exponential decay. In UCAL, pages 2171-2179, 2024.
[37] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
[38] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmilaa Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In ICLR, 2023.
[39] Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. In NeurIPS. 2022.
[40] Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9(2), 2021.
[41] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6088):533-536 1986.
[42] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Collective classification in network data. AI Mag., 29(3):93-105 2008
[43] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski. and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, abs/1 18111111111 1.0566.... 2018.
[44] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In ICML, volume 202, pages 31613-31632. PMLR, 2023.
[45] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In SIGKDD, pages 807-816, 2009.
[46] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, pages 5998-6008, 2017.
[47] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. CoRR, abs/17110 10903, 2017.
[48] Ulrike von Luxburg. A tutorial on spectral clustering. Stat. Comput,, 17(4):395-416, 2007.
12

---

[49] Qitian Wu, Wentao Zhao, Zenan Li, David P. Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. NeurIPS, 2022.
[50] 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 NeurIPS, 2023.
[51] Zhanghao Wu, Paras Jain, Matthew A. Wright, Azalia Mirhoseini, Joseph E. Gonzalez, and lon Stoica. Representing long-range context for graph neural networks with global attention. In NeurIPS, pages 13266-13279, 2021.
[52] Zhihao Wu, Zhaoliang Chen, Shide Du, Sujia Huang, and Shiping Wang. Graph convolutional network with elastic topology. Pattern Recognition, 151:110364, 2024.
[53] Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is more: on the over- globalizing problem in graph transformers. In ICMI, 2024.
[54] Liang Yang, Zhenna Li, Jiaming Zhuo, Jing Liu, Ziyi Ma, Chuan Wang, Zhen Wang, and Xiaochun Cao. Graph contrastive learning with joint spectral augmentation of attribute and topology. In AAAL, pages 21983-21991, 2025.
[55] Liang Yang, Chuan Wang, Junhua Gu, Xiaochun Cao, and Bingxin Niu. Why do attributes propagate in graph convolutional neural networks? In AAAI, pages 4590-4598, 2021.
[56] Syed Waqas Zamir, Aditya Arora, Salman Khan, Munawar Hayat, Fahad Shahbaz Khan, and Ming-Hsuae Hsuan Yang. Restormer: Efficient transformer for high-resolution image restoration. In CVPR, pages 772999 2022.
[57] Zhongying Zhao, Zhan Yang, Chao Li, Qingtian Zeng, Weili Guan, and Mengchu Zhou. Dual feature interaction-based graph convolutional network. IEEE Transactions on Knowledge and Data Engineering. 35(9):9099-9030, 2023.
[58] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In WWW, pages 1215-1226, 2021.
(59] Jiaming Zhuo Can Cui, Kun Fu, Bingxin Niu, Dongxiao He, Yuanfang Guo, Zhen Wang, Chuan Wang, Xiaochun Cao, and Liang Yang. Propagation is all you need: A new framework for representation learning and classifier training on graphs. In MM, pages 481-489, 2023.
[60] Jiaming Zhuo Can Cui. Kun Fu, Bingxin Niu, Dongxiao He, Chuan Wang. Yuanfang Guo, Zhen Wang. Xiaochun Cao, and Liang Yang. Graph contrastive learning reimagined: Exploring universality. In WWW, pages 641-651, 2024.
[61] Jiaming Zhuo, Yuwei Liu, Yintong Lu, Ziyi Ma, Kun Fu, Chuan Wang. Yuanfang Guo, Zhen Wang, Xiaochun Cao, and Liang Yang. Dualformer: Dual graph transformer. In ICLR, 2025.
[62] Jiaming Zhuo Feiyang Qin, Can Cui, Kun Fu, Bingxin Niu, Mengzhu Wang, Yuanfang Guo, Chuan Wang, Zhen Wang, Xiaochun Cao, and Liang Yang. Improving graph contrastive learning via adaptive positive sampling. In CVPR, pages 23 23179-23187, 2024.
13

---

A Algorithm Description
layer of the proposed dual cross-attention module DCA is depicted Algorithm
Algorithm 2: PyTorch-style Code for DCA layer
N: instance number
D: hidden dimension
z: data embeddings sized [N, D]
b: data embeddings sized [N, D]
H: head number
Wq. Wk, Wv: parameter matrices for feature transformation
=
Wq(z) [N, H. D]
Wk(z) [N. H.
V= = Wv(b) # [N, D]
numerator
kv torch.einsum("lnng Ihd -> hmd", k, v) num = torch..insum("" nhm, hmd nhd", q. kv)
num += N v # [N, H, D]
denominator
all_ones = torch onesh)
k_sum = torcoooreiiie wwwrchhinnsmm"Ihnn 1 - hm", k, all_ones)
den = torch...eiie wrarccheinsummmniii
hm - nh", k_sum) # (N, H]
aggregated results
den += torch.ones like(den) N output num den.unsqucezee()) # [N, H. D]
head average
output (utput. [N, D]
B Proof for Theorem 1
Proof. The proof unfolds in three stages: firstly, concise description of the model to be validated is provided; subsequently, the model decomposed into its topology and attribute components; and finally, it is verified that this structure aligns with the cross-aggregation form.
For single-layer GNN block, such GCN can be expressed as
29 widely used in GTs [39 2
the feature update
H = o
(16)
where the diffusion matrix À denotes the normalized adjacency matrix.
By omitting the nonlinear activation function and performing eigendecomposition the adjacency matrix, the above equation can be reformulated as
H = AxW
UAU XW
(17)
UVAVAU XW.
Next, let B UVA and = XW. The similarity function Sim(-,-) is implemented matrix multiplication. With the definitions in Eq. 5 the GCN block can be interpreted as cross-aggregation from the attribute space to the topology space.
Extension to Multi-layer GNN Blocks. Following the discussion on single-layer GNNs, the solution for llyer GNNs is presented. Under the above assumptions, the node representations in the I-th layer can be formulated as
H'= = (A'A A.)(('/''''' w') =S
(18)
14

---

where A' and W denote the diffusion matrix and the parameter matrix, respectively, in the i-th layer. S = - S' and W = -T'= W stand for the product of the diffusson matrices and the projection matrices. Given the properties of the diffusion matrix, the product diffusion matrix can be cigen-decomposed as = UA UT, where A (1) represents the power of A. Therefore, the above conclusion still holds in the context of multi-layer GNNs.
Remark. This interpretation holds under the assumption that the diffusion operators across layers share common eigenspace (i.e. identical or mutually commutative Á across layers). Otherwise, the equivalence serves first-order approximation of the aggregation process.
C Proof for Theorem 2
Proof. This proof first expands the model based on the feature and parameter matrices. Then, identifies the representation updates of the topology and attributes within it. Finally, it establishes the relationship between these updated expressions and the cross-aggregation.
Firstly, the function Softmar()) can be approximated using Random Features mappings, that is, H = Softmar(44 QQT)VV x (Q))(K)) T V. Here, o(.) denotes kernel-based feature mapping that linearizes the attention computation. In practice, the learnable projection matrix W applied to X can be viewed as a parametric approximation to this mapping.
By expanding node attributes X
[X; PJ. where X E Rnx/ and P E Ba*k it can be obtained as
T P
DIX:PIWW
(X:))W(
(19)
Wy
Then, by expanding the Query (like W =
). and the Key and Value, it can be derived as
W
(XXY + PW ((W)) X + (W (PT)) (XWI + +WW)
= ((XY + PW (WW))
T X + (W2) PT)) XWI
(20)
(XWW) + PW?) ((W)) X + (Wh) TPT) PW
evident that the equation includes several terms that describe the self-aggregation of topol- ogy and attributes. For instance, PW3(PW5) PW; and XW((XW)) "XWi stand for the self-aggregation of topology and attributes, respectively. Furthermore, this equation contains sev- eral terms that include cross-aggregation across topology and attributes. Exampled by the term X (PW PWy, by setting
'WW
XW and B PW2, the cross-aggregation from the topology space to the attribute space can be obtained. Similarly, terms (e.g.. (PW)) XWW) describing cross-aggregation from the attribute space to the topology space can be found.
D Proof for Theorem 3
Proof. This proof includes two main steps. First, we plan to derive the closed-form solutions for Z
and B from the convex optimization objective (Eq. [5]. These solutions are denoted as Z and B respectively. Second, we aim establish the equivalence between these derived solutions Z and B*
and the feature updates in Eq. and Eq. 11 respectively.
Let us denote the objective function (Eq.
15) OZ,,B), that is
O B) = XTr Z LZ) + | MLP - - B
=XTr(Z (I- Á)Z)
(21)
Tr T - MLP((X)) TTCT))))BBBB MLP(X)))
Tr((Z B) (Z B))
Firstly, the partial derivatives of O B) with respect to Z can be calculated
()) 2A( Äjz (BB ZZ)
(22)
az
15

---

The closed-form solution z" for the objective function O can be derived by setting that is
a0(2.))
0,
82
2A(1 A)Z 2 BB Z 0
(23)
- = AZ + BB Zz
7
(24)
Then, by setting
7 X+j
we obtain
z' (1 w1 w AZ + w BB T
(25)
For the update of topology representations in the proposed DCA module, Le,, Eq. 10 the process can be rewritenn as
2 Á)ÁV Äsv,
(26)
at k.
where S E puxn stands for the cross coss-attention score matrix, with the scores 8t, n+ 2, 9:, k,
and
Si.j q.ckk. for i +
To demonstrate the equivalence between Eq. 25 and Eq. 26 the first step to set w1 = À. With this condition met, the required proof is to derive matrix B that satisfies the equation BB = S.
Let us denote the diagonal matrix as D, where d1, n4 q.
n=1
the construction of B DQ
ensures that the above equation holds.
For the diagonal elements of BB there
BBB
)r,
Σ 1=
(dr,
Ft 22 de
Pi
(27)
1=0
j=0
Given that the rows of Q are L2-normalized, we have Σ Ri.
2 1. Due to the same source and
parameter sharing, it follows that Q K. Thus, obtain (BB
),, dt,, nt 9..
a+1
which
matches the definition of the score Sa,v on the main diagonal.
For the off-diagonal elements of BB where u + u, there
d-1
(BB kkg =
bitt bij+ Σ
(dis (ue)) (dja qaa)
1=0
(28)
9..
di. dj
Σ
Σσ qi.
1=0
Since d,,, and djj are the square roots of the denominators in the formula for s,, and sj,j, respectively, and qr. q.. is the dot product of the i-th and j-th rows of Q, this matches the definition of st.- Therefore, the correct construction of B should be BDQQ
Similarly, the closed-form solution B" of the objective in Eq. 15 can be obtained by setting its derivative to 0 as
80 B)
²B MLP()) (z ( B)
(29)
= B = =MLP(X) + 7z
(30)
Then, by defining wa I+7" there is
B' -1 (1-w3)MLP(X) ZW BB
(31)
The proposed dual cross-attentian module for updating the attribute representations, i.e., Eq. I1 can be rephrased as
== (1 (L) SSV
(32)
Similarly, considering that matrix maintains the same structure as described in Eq. 26 the crucial step to ensure B is establish the parameter W2 = 5 and to set Z DQ. This approach guarantees that the necessary conditions for the equivalence are met.
16

---

E Experimental Details
E.1 Datasets and Splitting
Datasets. In the node classification experiments, sixteen publicly available benchmark datasets are utilized. These graphs can be classified into two categories based on whether their Edge Homophily
37] exceeds 0.5: seven graphs are tagged as homophilic graphs, including Cora [42) CiteSeer [42)
PubMed 42 Photo 4R CS 43 Physics [3] and Questions [38]. The remaining seven graphs are marked as heterophilic graphs, containing Cornell [37] Texas (37], Wisconsin [3]. Actor [45],
Chameleon 40 Squirrel [4], and Ratings [8]. It is worth noting that the original Chameleon and
Squirrel exhibit neighborhood overlap, and are thus filtered according to the study [88 Additionally,
two large-scale graph datasets, i.e., ogbn-arxiv [23 and ogbn- gebn-proteins [23] are employed for node property prediction experiment. Statistics are shown in Tab.
Table 4: Statistics of sixteen graph datasets, #h denotes the edge homophily shown in
37
Dataset
Nodes
Edges Features Classes #/
Cora
2,708
5,278
1,433
0.81
CiteSeer
3,327
4,552
3,703
0.74
PubMed
19,717
44,324
500
3
0.80
Photo
7,650
238,163
745
8
0,83
CS
18,333
81,894
6,805
15
0.81
Physics
34,493
247,962
8,415
5
0,93
Questions
48,921
153,540
301
0.84
Cornell
183
280
1,703
S
0.30
Texas
183
295
1,703
5
0.11
Wisconsin
251
466
1,703
0.21
Actor
7,600
33,544
0.22
Chamelcon
890
8,854
2,325
5
0.24
Squirrel
2,223
46,998
2,089
5
0,21
Ratings
24,492
93,050
300
5
0.38
ogbn-proteinn
132,534
39,561,252
8
2
00.38
oghn-arxiv
169,343
1,157,799
300
128
0.65
Dataset Splitting, To ensure that the experimental results are credible and reproducible, this paper follows well-established dataset splitting strategies. For the Cora, CiteSeer, and PubMed, the public standard splitting described in [29] is adopted, with 20 nodes per class for training. 500 for validation, and 1000 for testing. The Photo, CS, and Physics are randomly divided into training, validation, and testing sets in 60%, 20%, and 20% ratio, respectively. For the heterophilic datasets Cornell, Texas, Wisconsin, Actor, and Chameleon, this paper employ 10 standard train/valiin caiin/vlliation/tess splits with a division ratio of 48%, 32%, and 20%, respectively. Note that the Chameleon and Squirrel used here are pupliccaee-removee 50% 225% /25% train/validationftest random split pattern. For the two datasets from the OGB (23). i.e., ogbn-arxiv and
filtered versions as referenced in (38). The Ratings, and Questions follow a
the provided standard splits are utilized.
E.2 Introduction of Baselines
The comparative analysis in the experiments involves seven Graph Neural Networks (GNNs) as well as seven Graph Transformers (GT's) as the baseline models. To be specific, the GNNs include four standard GNNs, i.e., GCN [29, GAT [47) GraphS [20]. and APPNP [30] and two universal
GNNs for graphs with diverse homophily, i.e., GPR-GNN 6 and GloGNN 33 and a non-message-
passing GNN with a separate topology and attribute design, i.e., LINKX 32 Besides, the baseline
GTs encompass eight state-of-the art models, namely, GraphGPS [39], NAGphormer [2], Exphormer GOAT [31), NodeFormer [49]. SGFormer [50], Polynormer 77. and Gradformer [36]. These models are implemented following the released code the original paper.
E.2.1 Graph Neural Networks (GNNs)
The following specifies the GNN baselines employed in comparative analysis.
17

---

GCN [2] convolution.
A seminal GNN that integrates graph topology and node attributes via graph
GAT 47 A classic graph attention network that weights propagation using attention mechanism.
GraphSAGE 20 scalable variant of GCN that employs neighbor sampling and diverse
aggregation strategies.
APPNP :0 A variant of GCN that weights propagation based on personalized PageRank.
GPR-GNN 6 A universal variant of GCN that weights propagation using learnable layer coefficients.
LINKX +4 A cont-esssgee-assiinng GNN that directly combines representations of graph topology and node attributes.
GloGNN
B A universal variant of GCN that obtains the propagation matrix from an optimization objective describing node relationships.
E.2.2
Graph Transformers (GTss)
The following specifies the GT baselines utilized in our comparative analysis.
GraphGPS 39
general GT architecture incorporating positional encodings and lo-
cal/global modules.
NodeFormer [49]
scalable GT architecture that learns layer-specific graph structures via kernelized Gumbel-Softmn operator.
NAGphormer 2 A creative GT architecture constructing token vectors using neighborhood aggregation.
Exphormer 44 A general GT architecture combining local, extended, and virtual node- based global attention.
GOAT [31] comprehensive GT architecture linearizing computational complexity based on the k-means algorithm.
SGFormer [50]: A lightweight GT architecture featuring single-layer self-attention module.
Polynormer 7 polynomial-expressiee expressive GT architecture learning high-degree polynomials on input features.
Gradformer [3): An effective GT architecture dynamically modeling node relationships by exponentially diminishing values in the decay mask matrix.
For the four GNN baselines, including GCN, GAT, GraphSAGE, and APPNP, we utilize the public library, PoTorch Geometric (PyG) [13,, for their implementation. For the other three GNN baselines, we utilize their original code. The sources are outlined as
GPR-GNN: htw.a//wwww//////ooooo////////aa
LINKX: http:///giiiilloooo/////oooooooo GloGNN: http://ghhttt.omn/cccccssooonnnn
For the GT baselines, including GraphGPS, NodeFormer, NAGphormer, Exphormer, GOAT, SG- Former, Polynormer, and Gradformer, we utilize their source code. The sources are detailed
GraphGPS: ,
NodeFormer: http::/hhhhhia..om//aaaaaa////aa
GOAT: http::/gghhhbbccoomddvvvonngooo
SGFormer: http:://gghhbbbcoomggraaanu//Sna
Polynormer: http://gtiioccc///ommm////////nn
Gradformer: http://stthbbccoon/iiiinnnngghgu
18

---

E.3 Experimental Setups
Configurations. The experiment is performed on two Linux machines using single GeForce RTX4090 24 GB GPU and single NVIDIA A800 80GB GPU, respectively. The reported results are averaged over ten random trials. All models operate under supervipe learning paradigm. where the results on validation sets are referenced to fine-tune hyperparameters.
Table 5: Hyperparameters of UGCFormer per dataset.
Dataset
# layers I # dimensions
a
B
wd
Cora
256
0.001
0.5
1
5e-3
CiteSeer
256
0.001
0.6
0.1
5e-3
PubMed
128
0.001
0.5
0.1
le-2
Photo
512
0.001 0.3
0.1
5e-5
CS
512
0.001
0.6
0,1 5e-4
Physics
512
0.001 0.5
1
5e-4
Questions
2
256
0.005 0.3
0.1 5e-4
Cornell
256
0.001 0.9 0.001
1e-2
Texas
0.001 0.7 0.001
1e-2
Wisconsin
128
0.001 0.9 0.001
le-2
Actor
5
512
0.001 0.9 0.01
le-2
Chameleon
2
512
0.001 0.2 0.01
5e-3
Squirrel
4
512
0.001 0.2 0.01
Se-5
Ratings
2
64
0.001 0.3 0.001
0
ogbn-proteins
128
0.001 0.7
0.01
5e-4
ogbu-arxiv
2
512
0.01 0.3 0.01
5e-4
Hyper-parameters. The hyperparameters are selected via grid search strategy. In the node classification task, models are trained employing an Adam optimizer with the learning rate among {0.001, 0.005, 0.01} and the weight decay among (0, 1e 5e 1e 4, 5e 4, 3, 5e 1e - 2}. The number of layers is selected from {1, 2, 3, 5, and the dimension of hidden layers chosen from (64, 128, 256, 512], and their impacts on model performance are analyzed in Section
4.2 For the node property prediction task, the hyperparameter selection follows the baseline [50] For UGCFormer, a is chosen from range starting at 0.1 and increasing by increments of 0.1, up to 0.9, 3 is selected from {0.001, 0.01, 0.1, 1}, and 7 is fixed to 0.5. Refer Tab. for the chosen parameters that correspond the reported results.
the unique hyperparameters
Table 6: Training time and GPU memory usage on three graphs.
CiteSeer
PubMed
ogbn-arxiv
Method
Train/Fpoch (ms) Mem. (MB) Train/Fppcch (ms) Mem. (MB) Train/Fipoch (ms) Mem. (MB)
GraphGPS
16.82
140
46.99
470
166.10
8,102
NodeFormer
10.20
110
11.14
218
84.00
2,066
NAGphormer
10.81
166
17.65
352
760.50
1,962
Exphormer
14.20
159
25.00
696
145.70
6.758
SGFormer
5.80
84
6.07
142
36.90
1,024
Polynormer
9.20
174
15.20
307
170.07
4,729
UGCFormer
8,80
10.60
246
69.60
2,050
E.4
Additional experiment results
Rumning Time and Space Consumption. To further illustrate the efficiency and scalability of the proposed UGCFormer, this experiment compares it with other GTss in terms of runtime and GPU memory usage. Common hyperparameters are uniformly applied across all models to highlight the impact of their components, particularly the attention modules. As depicted in Table 6 UGCFormer consistently has the second-lowest running time and ranks among the top three in terms of lowest GPU memory usage across three datasets. Despite utilizing linearized attention mechanisms, most linearized GTs, including GraphGPS, NodeFormer, Exphormer, and Polynormer, perform worse than UGCFormer. This highlights the lightweight and efficient design of UGCFormer.
19

---

UGCFormer
UGCFarmer
UGCFarmer
UGCFarmer
89
Accuracy
Accurace (rss
12
Accuracy(55)
Accuracy(
03
75
65
Corel R0at WARWHA
Camdl
RubMed
-2
Rosa
53
PLEMO)
0.1 0.
0.3 0.4
0.
*
Figure 6: Performance variations for varying a.
Figure Performance variations for varying B.
Hyperparameter As depicted in the Fig. UGCFormer exhibits stable performance within specific parameter range for each dataset. For instance, on Cora, performance variation minimal within the set {0.3, 0.4, 0.5, 0.6), indicating that the model is robust to changes in hyperparameter Similar observations are made for heterophilic graphs.
Hyperparameter B. From the Fig. it can be observed that the performance remains stable across the selection range of f, demonstrating that the model is not sensitive to this parameter. Even the worst case of parameter selection, the model achieves performance that is comparable to the baseline.
F Discussion
Comparison with Edge-augmented Graph Transformer (EGT). The proposed UGCFormer shares conceptual connection with EGT [27]. yet their core mechanisms differ substantially. EGT augments pairwise attribute-based attention between nodes using graph topology, whereas UGCFormer captures the interaction between topology and attributes through cross-attention mechanism. Although EGT introduces an additional edge channel alongside the attribute channel, this design primarily aims to utilize edge features modulate the attention process (via addition gating) rather than explicitly model the interaction between the two channels. Moreover, EGT requires large-scale edge features of size (nn2d) d) (where denotes the number of nodes and d the feature dimension), which significantly increases computational complexity and limits scalability. In contrast, UGCFormer adopts linear cross-attention module that efficiently models topology-attribut interactions with linear time and space complexity.
Broader Relation to Other Categories of Graph Transformers. The proposed cross- agggggggg mechanism can also provide a unified interpretation for other two types of Graph Transformers, that is, those based context-node sampling or edge rewriting. Although both categories of GTs implemented in different ways, their essence is to determine the subgraph for each node to perform local message passing (via graph convolution self-attention). Thus, they be uniformly expressed by obtaining the graph structure. As result, the topology representation can be straightforwardly determined based the eigenvalue decomposition of the adjacency matrix, described in the manuscript. Ultimately, a formulation similar to that of cross-aggregation can be derived. Therefore, their underlying mechanism be attributed cross-aggregation between topology and attribute representations.
G Limitations
The proposed UGCFormer, like other Graph Transformers (GTs), relies on fixed set of hyperparam- eters, requiring significant tuning and prior knowledge optimize results. This not only limits their applicability but also increases computational costs. Future work should explore adaptive learning mechanisms to automate hyperparameter adjustment based on input data characteristics, reducing manual intervention and enhancing generalizability.
20

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly outline the contributions our paper, including the motivation and design of the proposed UGCFormer.
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 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 as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations in Section G particularly regarding the large number of hyperparameters commonly found in GTs. We have outlined potential directions for future research to address this concern.
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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in 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 prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
21

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have included complete and executable code within the supplemental material, ensuring the reproducibility of our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
aublic/guudees/Coeeetbbmsss wotpssiiinoollyyyy for more details.
While encourage the release of code and data, understand that this might not 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 run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccppppccggua.aeaeaeccuuea
Stteee///ooSSSeeissSioica www.ssssiicgcyy 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 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: We have provided detailed descriptions of our experimental setup in Section including data splits, hyperparameters, and optimizer, etc.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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 experimental results are presented as the mean and standard deviation over 10 runs, as shown Tabs. [ and 2 as well Figs. and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
23

---

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 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 error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided the computational resources used for all experiments in Section F.3
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research adheres to the NeurIPS Code of Ethics, and we have ensured that all aspects our work.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Due to the nature of this work, there may be no potential negative social impact that is easily predictable.
Guidelines:

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility 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: Our work does not involve releasing data or models that pose a high risk for misuse, so no specific safeguards are necessary.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have accurately credited the sources and provided URLs in Section E.2
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.
25

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, papprsaipphaeeeooccaaapppaapppse thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The supplemental material includes the file of our model's code
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing or research with human subjects, so this information not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of 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: This research does not involve human subjects, so IRB approvals or equivalent reviews are not required.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
26

---

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 this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httt:://meerrrss..ccoooorereer/p for what should or should not be described.
27


Reviews:
[{"review_id": "hl926MGD59", "reviewer": "Reviewer_izVd", "summary": "This paper reveals Cross Aggregation, a mechanism that effectively links graph topology and node attributes, by analyzing two main strategies utilizing by existing Graph Transformers. Based on this insight, UGCFormer is proposed, implementing the uncovered mechanism through a linearized Dual Cross-Attention module.\n\nThe key contributions of this paper include:\n\n1.   **Identification of Cross-Aggregation Mechanism**. The paper explores the effectiveness of typical Graph Transformers and formalizes the cross-aggregation mechanism as a central component in GTs.\n2.   **UGCFormer Architecture**. The paper proposes a linearized GT that utilizes the DCA module to aggregate graph topology and node attribute while maintaining linear time complexity.\n3.   **Theoretical Foundations**. The paper provide proofs showing that Corss-Aggregation between topology and attributes is the essential mechanism in typical GTs.\n4.   **Extensive Experiments**. The paper demonstrates the effectiveness of UGCFormer on multiple datasets, including both homophilic and heterophilic graphs, showing its effectiveness compared to existing models.", "questions": "1.   The paper explores its core mechanism by revisiting two main strategies used by existing Graph Transformers (GTs). Since this mechanism proves effective in this work, it suggests that a similar mechanism may also be playing a role in other GTs. However, the paper does not discuss the approaches of other related works. Could you provide specific methods from other related works and highlight how they differ from the approach in this paper?\n\n2.   The paper introduces a novel Dual Cross-Attention module, but the exact dynamics of how the model balances information from the topology and attributes could be explained more intuitively. Could you provide a more detailed, intuitive explanation of how the DCA module updates representations and how it compares to other attention mechanisms used in graph learning (e.g., self-attention or cross-attention in NLP)?\n\n3.   The paper briefly mentions that the consistency constraint helps mitigate overfitting. However, there is little discussion on how this mechanism performs under extreme cases, such as small datasets or highly noisy data. Have you conducted experiments where overfitting is more pronounced (e.g., using very small training sets or datasets with significant noise)?\n\n4.   While the paper compares *UGCFormer* to multiple GNNs and GTs, the comparisons seem mostly quantitative. Can you provide a more detailed qualitative analysis, such as analyzing the impact of the cross-attention mechanism on the learned representations or providing case studies where *UGCFormer* performs better than its competitors?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n1.   This paper provides a solid theoretical foundation by identifying and formalizing the concept of Cross-Aggregation between graph topology and node attributes. Such formal proofs strengthens the scientific rigor and ensures that the proposed method has a robust theoretical basis.\n2.   The paper provides a thorough account of experimental setups, datasets, hyperparameters, and evaluation metrics, ensuring that others can replicate the experiments.\n3.   *UGCFormer* introduces a practical solution that is likely to be valuable in various applications where scalability and efficiency are essential, by combining topology and attributes in a way that captures long-range dependencies without incurring high computational costs\n\n## Weaknesses\n\n1.   The core idea of combining graph topology and node attributes through attention module has been explored in other works, such as those involving GNNs with positional encodings or integrated GNN blocks. Therefore, while the specific design of UGCFormer is original, it is incremental innovation in attention mechanisms.\n2.   The model propoesd requires tuning multiple hyperparameters, which may limit its ease of use in real-world applications. A more adaptive method for hyperparameter selection could improve the accessibility and usability of the model.\n3.   While the experiments show impressive results on benchmark datasets, the paper could be improved by discussing potential applications in more depth. For example, how would *UGCFormer* perform on graph data with highly heterogeneous or noisy attributes? More concrete use cases or challenges faced when deploying the model in practical settings could be beneficial for demonstrating its significance.", "was_revised": true, "final_justification": "The authors have addressed all my concerns.", "rebuttal": ">W1. The core idea of combining graph topology and node attributes through an attention module has been explored in other works, such as those involving GNNs with positional encodings or integrated GNN blocks. Therefore, while the specific design of UGCFormer is original, it is an incremental innovation in attention mechanisms. \n\nR1. This may be a misunderstanding of our contribution. As we know, effectively integrating graph topology and node attributes has always been a key topic in graph learning models. However, they always do outside the attention module: Graph Neural Networks (GNNs) propagate attributes over the graph topology, and Graph Transformers concatenate positional encodings (topology representations) to node attributes. In contrast, this is the first work to explore and reveal that the essence of these two methods is to capture the interrelation between graph topology and node attributes through a common mechanism, and to design a simple yet effective cross-attention module accordingly. \n\nMoreover, unlike the attention module in existing GTs, which focuses on correlations within a single representation space, our proposed attention performs fusion between topology and attribute spaces. This represents a significant contribution that clearly distinguishes our attention mechanism from existing ones. We hope it addresses your concerns regarding design novelty. \n\n- - -\n\n>W2. The model proposed requires tuning multiple hyperparameters, which may limit its ease of use in real-world applications. A more adaptive method for hyperparameter selection could improve the accessibility and usability of the model. \n\nR2. Thank you for highlighting the importance of training efficiency—this is indeed a shared limitation of current GTs. We have already noted it in Section F and regard it as a priority for future work.\n\n- - -\n\n\n>W3. How would UGCFormer perform on graph data with highly heterogeneous or noisy attributes? More concrete use cases or challenges faced when deploying the model in practical settings could be beneficial for demonstrating its significance. \n\nR3. Thank you for your valuable feedback, which has guided us to reflect on the model's robustness and practical deployment. To verify the robustness of UGCFormer, we have conducted robustness experiments on two datasets (Cora and CiteSeer). We adopt two simple noise settings: \n(1) Randomly masking $p\\%$ of the attribute dimensions across all nodes;\n(2) Injecting Gaussian noise ($\\sigma = 0.1$) into the attributes of $p\\%$ of randomly chosen nodes. The results are as follows. \n\n| p | 0 | 20 | 40 | 60 | 80 |\n|:--------|:---------:|:--------:| :--------:| :--------:| :--------:|\n**Masking**\n| Cora | 84.9 | 81.3 | 78.3 | 73.7 | 67.1 |\n| CiteSeer | 73.4 | 65.5 | 62.6 | 59.7 | 55.9| \n**Injecting Noise**\n| Cora | 84.9 | 81.7 | 79.9 | 76.9 | 79.5 |\n| CiteSeer | 73.4 | 70.1 | 68.4 | 65.3 | 67.0 |\n\nAcross all cases, UGCFormer maintains stable performance, demonstrating its robustness to attribute noise. This stems from the dual-branch design between the topology and attribute spaces, which treats topology as a stabilizing prior: when attributes are noisy, cross-attention and the consistency loss use the topology to suppress attribute noise and guide the learning of attribute representations. \n\nFor highly heterogeneous attributes, UGCFormer can ingest multi-modal inputs through modality-specific encoders followed by a shared projection layer, allowing the cross-attention to fuse diverse signals without manual alignment. We plan to pursue this as future work.  \n\n- - -\n\n>Q1. The paper explores its core mechanism by revisiting two main strategies used by existing Graph Transformers (GTs). Since this mechanism proves effective in this work, it suggests that a similar mechanism may also be playing a role in other GTs. However, the paper does not discuss the approaches of other related works. Could you provide specific methods from other related works and highlight how they differ from the approach in this paper? \n\nR4. According to your suggestion, we have explored the relationship between the two other categories of GTs, namely, those involving sampling context nodes and those involving rewriting edges, and the cross-aggregation mechanism, as follows.\n\nAlthough both categories of GTs are implemented in different ways, their essence is to determine the subgraph for each node to perform local message passing (via graph convolution or self-attention). Thus, they can be uniformly expressed by obtaining the graph structure. As a result, the topology representation can be straightforwardly determined based on the eigenvalue decomposition of the adjacency matrix, as described in the manuscript. Ultimately, a formulation similar to that of cross-aggregation can be derived. Thus, their underlying mechanism can be attributed to a cross-aggregation between topology and attribute representations.\nThank you for guiding us to further discuss a broader category of GTs. We appreciate the opportunity to further enhance the comprehensiveness and generalizability of our theoretical contributions. We will add the above discussion to the revised manuscript. \n- - -\n\n>Q2. Could you provide a more detailed, intuitive explanation of how the DCA module updates representations and how it compares to other attention mechanisms used in graph learning (e.g., self-attention or cross-attention in NLP)?  \n\nR5. The DCA module intuitively balances information from topology and attributes through an optimization framework (in Theorem 3.4) that explicitly models their interrelations. Firstly, the third term, which uses the Hilbert-Schmidt Independence Criterion (HSIC), measures the dependence between topology representations (from the first term) and attribute representations (from the second term). This allows the model to learn whether to correlate or exclude certain aspects of topology and attributes, thus modulating their interrelation. Secondly, the balance between topology and attributes can be achieved by tuning the parameters $λ$ and $η$, which control the trade-off between these three terms. By minimizing the objective function, the DCA module learns to integrate topology and attributes in a way that best captures the underlying structure and semantics of the graph. \n\nThe DCA module is designed to update representations by capturing the interrelations between graph topology and node attributes. This dual attention process allows for a more nuanced integration of topology and attributes compared to traditional self-attention in graph learning, which is typically without explicit attribute-topology alignment. Moreover, unlike cross-attention in NLP, which handles sequences of tokens, DCA is tailored for graph-structured data, addressing the unique challenge of integrating topology and attributes. Thus, DCA enables learning more expressive representations suited for diverse graph learning tasks. \n\n- - -\n\n>Q3. There is little discussion on how this mechanism performs under extreme cases, such as small datasets or highly noisy data. Have you conducted experiments where overfitting is more pronounced (e.g., using very small training sets or datasets with significant noise)? \n\nR6. According to your suggestion, we have conducted an overfitting study to investigate the effect of the consistency constraint. We compared UGCFormer with a variant without the proposed consistency constraint, using only 1, 3, 5, 10, and 15 labeled nodes per class. We observe that the variant without the consistency term suffers a steep accuracy decline as fewer labels are provided, whereas UGCFormer’s performance degrades modestly. This confirms that the proposed constraint effectively curbs overfitting under extreme label scarcity. This gain is mainly due to the consistency loss, which causes the topology and attribute representations to supervise each other. Full results are reported in the following Table. \n\n| | 1 | 3 | 5 | 10 | 15 |\n|:--------|:---------:|:--------:| :--------:| :--------:| :--------:|\n**Cora**\n| w/o L_con | 41.7 | 62.4 | 70.1 |  75.4 | 79.9  |\n| UGCFormer | 50.9 | 70.5 | 76.4 | 78.7 | 81.2 | \n**CiteSeer** \n| w/o L_con | 36.8 | 48.2 |  59.1 | 66.3 | 69.8 |\n| UGCFormer | 45.1 | 53.7 | 65.2 |  69.0 | 72.2 | \n\n- - -\n\n>Q4. Can you provide a more detailed qualitative analysis, such as analyzing the impact of the cross-attention mechanism on the learned representations or providing case studies where UGCFormer performs better than its competitors?\n\nR7. To illustrate the impact of the cross-attention mechanism on learned representations, we have added the following qualitative study. Specifically, we use t-SNE to visualize the node embeddings generated by UGCFormer and by LINKX, which can be viewed as a UGCFormer's variant without cross-attention. \n\nCompared with LINKX, UGCFormer yields tighter intra-class clusters and larger inter-class margins, indicating that the cross-attention mechanism successfully disentangles topology and attribute and produces more discriminative representations. \n\nDue to constraints, we are unable to include external links or images here; the complete t-SNE visualizations will be provided in the revised manuscript. \n\n- - -\n\n> Paper Formatting Concerns: the extra year citation in the References [12] and the syntax error in Lines 228-229. \n\nR8. Thank you for your careful review. We have corrected the identified issues and conducted a thorough review of the entire manuscript."}, {"review_id": "4ytPsQlAG5", "reviewer": "Reviewer_3zmm", "summary": "The paper proposes UGCFormer, a simplified Transformer variant adapted for graph data that achieves universality by generalizing across various graph types (homogeneous, heterogeneous). The key idea is to use a type-aware linear projection strategy and to replace the traditional softmax-based attention with an attention-free module involving token-wise linear transformations and graph-specific interactions. Experiments across 13 datasets show competitive or superior performance against prior graph Transformers.", "questions": "1. The structural input is limited to a raw adjacency matrix, which may limit generalization to complex graphs. It's unclear whether UGCFormer can adapt to positional encodings or multi-hop connectivity representations.\n2. Over-smoothing is a common challenge in deep GNNs, where node features become indistinguishable across layers. Given that UGCFormer is based on Transformer-style cross-attention, does your model mitigate over-smoothing? Have you evaluated its performance or feature divergence at deeper depths (e.g., 128 layers)? If not, can you provide theoretical or empirical insights into whether your architecture avoids this issue?\n3. I have reviewed the released code and encountered an error during execution: UGCFormer.forward() got an unexpected keyword argument 'adj_normal'. This suggests a mismatch between the implementation and the interface defined in the main training script. I recommend the authors carefully verify and test the provided code to ensure reproducibility and consistency with the descriptions in the paper.", "limitations": "1. While the model is elegant, there is little formal discussion about its expressive power, e.g., whether it can capture structural inductive biases like WL-test expressivity, which many graph models target.\n2. All evaluations are limited to node classification tasks. Given the model is described as a \"universal\" graph framework, demonstrating generalization to other tasks (e.g., link prediction, graph-level classification) would substantially strengthen the claim.\n3. UGCFormer decouples topology and attribute inputs via separate linear projections. While simple and efficient, the choice lacks theoretical justification or ablation on its inductive bias.\n4. The model’s depth is restricted to just 1–5 layers in all experiments, which is relatively shallow for Transformer-based designs. This raises concerns about its scalability and representational power at deeper levels.\n5. While empirical comparisons with prior graph Transformers are included, there is no architectural analysis that clarifies why UGCFormer outperforms them. A discussion contrasting core design choices—such as attention mechanisms, position encoding, or expressivity—would improve the paper.\n6. The paper introduces Dual Cross-Attention to mitigate quadratic complexity, yet provides no runtime or memory benchmarks. An empirical analysis comparing efficiency with standard self-attention would better support this claim.\n7. The ablation in Figure 3 is limited to four datasets and two components. It would be helpful to analyze the component-wise impact on both homophilic and heterophilic graphs separately, or across varying graph sizes.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The authors make a convincing case that UGCFormer is applicable to a wide range of graph types, which is valuable in practice where heterogeneous and non-standard graph structures are common.\n2. By removing softmax attention and relying on fixed token-to-token interactions, UGCFormer is lightweight, faster to train, and memory efficient. This aligns with recent trends in efficient Transformer design.\n3. The model is evaluated across a variety of node classification benchmarks involving both homophilic and heterophilic graphs. \n4. The authors provide comprehensive ablations, runtime/memory analysis, and visualizations that clarify how each component contributes.\n\n**Weaknesses**\n1. While the model is elegant, there is little formal discussion about its expressive power, e.g., whether it can capture structural inductive biases like WL-test expressivity, which many graph models target.\n2. While UGCFormer achieves top performance on the majority of datasets, its accuracy lags behind other models on certain heterophilic graphs, such as Actor, Chameleon, and Texas. However, the paper does not discuss these underperformances or provide insights into potential causes. A deeper analysis of these failure cases would improve the completeness and credibility of the empirical evaluation.\n3. While the range of datasets is broad, the evaluation is limited to node-level prediction tasks.\n4. The model separately projects structural topology (adjacency) and node attributes using two independent MLPs. While this design effectively decouples two fundamental sources of graph information, it is somewhat heuristic and lacks analysis on how this separation impacts performance across different graph types.\n5. UGCFormer is only evaluated with shallow architectures (1–5 layers), which is considerably lower than standard Transformer-based baselines (often using 6–12+ layers). This limited depth range weakens claims about the model's scalability and expressiveness. Without testing deeper configurations, it remains unclear whether the architecture suffers from optimization issues, over-smoothing, or representational collapse at larger depths", "was_revised": true, "final_justification": "I appreciate the authors’ efforts in the rebuttal, and most of my concerns have been addressed. However, my main remaining concern is reproducibility. The provided code does not run as expected, which raises questions about the reliability of the reported results. If the authors can ensure the code is executable and fully replicates the experiments, I would be willing to support a weak accept.", "rebuttal": ">W1&L1. There is little formal discussion about its expressive power, e.g., WL-test expressivity.\n\nR1. Our primary contribution lies in unifying existing Graph Transformers (GTs) and designing a cross-attention-based GT for fusing topology and attributes, not in advancing structural expressivity. While the WL-test is a standard yardstick for message-passing Graph Neural Networks (GNNs), it is rarely applied to GTs, which typically adopt 1-WL GNNs such as GCN or GAT. We therefore do not pursue formal guarantees on WL-test equivalence; instead, we demonstrate empirical effectiveness across sixteen diverse datasets, leaving deeper theoretical analysis to future work. \n\n- - -\n\n> W2. The paper does not discuss these underperformances on certain heterophilic graphs, such as Actor, Chameleon, and Squirrel. \n\nR2. After a post-hoc analysis, we attribute the sub-optimal results on Actor, Chameleon, and Squirrel to the **abundance of noisy edges**. Since our model explicitly constructs the topology space based on the adjacency matrix, it captures rich topological information. This increased sensitivity to the topology space makes our model more susceptible to topology noise. \n\nIn sparsely connected heterophilic graphs such as Cornell, Texas, and Wisconsin (with approximately 3 average node degrees), the information from the attribute space can effectively mitigate the impact of topology noise. However, in densely connected heterophilic graphs like Actor, Chameleon, and Squirrel (with 8-42 average node degrees), the topology noise overwhelms the regulatory effect of the attribute space, leading to sub-optimal performance. \n\n\n>W3&L2. Given that the model is described as a \"universal\" graph framework, demonstrating generalization to other tasks (e.g., link prediction, graph-level classification) would substantially strengthen the claim.\n\n- - -\n\nR3. This might be a misunderstanding caused by the insufficiently detailed description. The phrase \"universal graph frameworks\" in this paper denotes models capable of handling both homophilic and heterophilic graphs. This is introduced in lines 67–68 and aligns with the terminology in classic works, e.g., [1]. In the revised manuscript, we will add clarifying footnotes at the first occurrence to eliminate any possible misunderstanding. \n\nExtending to link or graph-level tasks is valuable, yet these settings often introduce additional biases—such as subgraph sampling or graph-pooling choices—that can obscure the intrinsic topology–attribute fusion capability we study. We will leave broader evaluations to future work. \n\n[1] **Universal** Graph Convolutional Networks, NeurIPS 2021.\n\n- - - \n\n>W4&L3. While this design effectively decouples two fundamental sources of graph information, it is somewhat heuristic and lacks analysis on how this separation impacts performance across different graph types. \n\nR4. This design is mainly based on the theoretical insights from Theorems 3.2 and 3.3, which indicate that the potential mechanism of GTs is the cross-aggregation between topology and attributes. The implementation of cross-aggregation via cross-attention necessitates keeping topology and attribute representations separate before the cross-attention, i.e., at the beginning. Besides, this separating-then-combining scheme was validated in existing works, e.g., LINKX, which highlights the rationality of this design. \n\n- - -\n\n>W5&L4&Q2. UGCFormer is only evaluated with shallow architectures (1–5 layers), which is considerably lower than standard Transformer-based baselines (often using 6–12+ layers). Does your model mitigate over-smoothing?\n\nR5. Thanks for raising this important point. UGCFormer, like most node-level GTs (e.g., SGFormer and Polynormer), is evaluated with only a few layers (≤ 5) and exhibits a performance drop as depth increases (see the results below). Thus, UGCFormer does not benefit from deeper stacks. \n\n  - Cora: 84.9%→75.1%(16 L)→65.4%(32 L)→55.7% (64 L)\n  - CiteSeer: 73.4%→69.8%(16 L)→66.9%(32 L)→62.3% (64 L)  \n\nInterestingly, graph-level GTs typically benefit from much deeper stacks (> 5 layers), aligning with the mentioned Transformers. We attribute this discrepancy to the **differing supervisory granularities of node-level task versus graph-level task**. \n- Node-level tasks: each node has its label. After shallow layers, the representation already encodes sufficient neighborhood context; deeper stacks merely average in distant, label-irrelevant signals.\n- Graph-level tasks: the entire graph carries a single label. Since each layer’s softmax averages all N nodes, the model needs to repeatedly refine and concentrate distant information into a single readout token. \n\n\nWhile we believe the performance drop in the above results is due to over-smoothing, GTs differ from local GNNs in practice. Local GNNs, which rely on message passing within local neighborhoods, often require stacking many layers to capture long-range dependencies, which can lead to over-smoothing. In contrast, GTs, with their inherent global expressiveness, can capture long-range dependencies **without needing many layers**. \n\n- - - \n\n>Q1. It's unclear whether UGCFormer can adapt to positional encodings or multi-hop connectivity representations.\n\nR6. The adjacency matrix is only the default input; the architecture can seamlessly integrate richer structural encodings. Specifically, replacing the adjacency matrix with (i) a positional encoding matrix (LapPE, SignNet, etc.) or (ii) a multi-hop propagation matrix such as the Personalized PageRank (PPR) matrix only requires a one-line change. We adopt the raw adjacency matrix primarily for simplicity. More sophisticated encodings inevitably incur heavy preprocessing: computing Laplacian eigenvectors (LapPE) costs O(N^3) in dense form and O(kN^2) even with sparse Lanczos, where N denotes the number of nodes and k represents a hyperparameter, while PPR requires O(N^3) for dense matrix powers or O(kE) under sparse-iterative acceleration. By relying on the unprocessed adjacency, we avoid these upfront costs while still delivering strong empirical results. \n\n- - -\n\n>Q3. I recommend that the authors carefully verify and test the provided code to ensure reproducibility and consistency with the descriptions in the paper.\n\nR7. Thanks for pointing out this error. In the released version, UGCFormer.forward() lacked the keyword argument 'adj_normal' to receive 'data.adj_normal' and assign it to the variable 'topology_' used in get_TopoRepresentation(). We sincerely apologize for the confusion caused by the incorrect release. Due to rebuttal rules, we cannot update the demo at this stage; we will release the fully corrected and reproducible GitHub repository as soon as the paper is accepted. \n\n>L5. There is no architectural analysis that clarifies why UGCFormer outperforms them. A discussion contrasting core design choices—such as attention mechanisms, position encoding, or expressivity—would improve the paper.\n\nR8. UGCFormer outperforms prior works by achieving a tighter alignment of topology and attributes. Existing models entangle a large number of intermediate representations (in Eq. 20), e.g., topology–attribute–attribute and attribute–topology–topology, producing an over-mixed, noisy embedding that weakens the final alignment and degrades performance. UGCFormer introduces the cross-attention-based DCA module to align the topology and attribute space and make every node selectively focus on the most relevant topology and attribute representations. Moreover, UGCFormer further enforces distributional alignment via a consistency loss. Together, they deliver superior performance. \n\n\n\n- - -\n\n>L6. An empirical analysis comparing efficiency with standard self-attention.\n\nR9. We have measured training time (ms) and GPU memory (MB) of DCA and two baselines with standard self-attention, i.e., Graphormer [1] and GraphTrans [2]. As shown in the result, DCA significantly reduces both training time and memory usage compared to standard self-attention, confirming its practical advantage.\n\n| | CiteSeer | PubMed | ogbn-arxiv |\n|:--------:|:---------:|:--------:| :--------:|\n| | Time / Mem. | Time / Mem. | Time / Mem. |\n| Graphormer | 478.0 / 870 | 870.4 / 1,844 | - / OOM |\n| GraphTrans | 85.6 / 528 | 118.2 / 1,460 | - / OOM |\n| UGCFormer | 8.8 /106 | 10.6 / 246 | 69.6 / 2,050 |\n\n[1] Do Transformers Really Perform Bad for Graph Representation?, NeurIPS 2021.\n\n[2] Representing Long-Range Context for Graph Neural Networks with Global Attention, NeurIPS 2021.\n\n- - -\n\n>L7. It would be helpful to analyze the component-wise impact on both homophilic and heterophilic graphs separately, or across varying graph sizes. \n\nR10. According to your suggestion, we have extended the ablation study to cover both homophilic and heterophilic graphs and varying graph sizes:\n\n| | UGCFormer | w/o CA | w/o L_con | \n|:--------:|:---------:|:--------:| :--------:|\n| Cora | 84.94 | 79.88 | 82.29 |\n| CiteSeer | 73.41 | 70.60 | 71.83 |\n| PubMed | 81.79 | 79.71 | 80.29 |\n| Cornell | 85.14 | 80.11 | 83.27 |\n| Texas | 84.59 | 81.29 | 83.71|\n| Wisconsin | 87.36 | 80.84 | 86.59 | \n| Actor | 37.41 | 36.77 | 37.09|\n| ogbn-proteins | 79.95 | 72.29 | 78.33|\n| ogbn-arxiv | 74.02 | 72.21 | 73.40 |\n\nAcross all datasets, removing either component consistently hurts accuracy, confirming their necessity.\n- Cross-attention proves the most critical component: taking it away causes the steepest performance drops, in particular, the results on ogbn-proteins, and the heterophilic Cornell, Texas, and Wisconsin datasets, highlighting how well it learn distinctive node representations when the graph structure is noisy. \n- Consistency loss yields smaller but still clear gains, especially on smaller graphs (Cora, CiteSeer, PubMed), where it regularizes the dual-branch training; the gap shrinks on larger graphs (ogbn-arxiv, ogbn-proteins) yet remains positive."}, {"review_id": "EV2XgVR9cD", "reviewer": "Reviewer_KZXo", "summary": "This paper proposes UGCFormer, a novel Graph Transformer architecture that leverages a linearized cross-attention to capture the interrelations between graph topology and node attributes. The authors identify a common cross-aggregation mechanism in existing Graph Transformers and design UGCFormer to effectively implement this mechanism. Extensive experiments on various graph datasets demonstrate the effectiveness and efficiency of UGCFormer.", "questions": "1 What are the differences in the ability to capture the correlation between the two types of information for the two ways of cross-aggregation (across two dimensions)? Additionally, how do these differences impact the overall performance of the model?\n\n \n2 How does the optimization objective in Theorem 3.4 differ from commonly used graph optimization objectives? What properties does it aim to illustrate about the model? \n\n3 In the proposed model, the final representations are a combination of the topology and attribute representations. While this approach is intuitively sound, I am curious whether the authors have experimented with using the topology and attribute representations separately for node classification, rather than combining them. How would the results be? \n\n4 As the authors mentioned in Section 3.1, existing models, despite their different approaches, essentially also capture the correlation between topology and attributes. Why does the model designed in this paper achieve performance improvements?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Str.:\n\n1 The idea of unifying existing Graph Transformers is intresting and inspiring, demonstrating that the authors have a solid understanding of the current techniques.\n\n2 The article is well-written, making it readable.\n\n3 The organization of the experiments is commendable and comprehensive.\n\n\nWeak.: \n\n1 Some implementation details have not been clearly described. Firstly, it is unclear why the authors chose to use the adjacency matrix to generate initial structural features. Structural encodings based on the Laplacian, for instance, are often preferred due to their interpretability. Secondly, the explanations for Equations 8 and 9 are unclear and could benefit from further elaboration.\n\n2 The model introduces a number of hyperparameters that require careful tuning, which may complicate the optimization process and increase computational costs.\n\n3 The title seems not to fully reflect the contributions of the article. Although the contributions of this paper are rich, such a simple title cannot clearly describe all the key contributions. The authors might consider incorporating the contribution of unifying GTs into the title.", "was_revised": true, "final_justification": "I appreciate the thoughtful rebuttal, which addressed most of my concerns. I decided to raise my score.", "rebuttal": "> W1-1. It is unclear why the authors chose to use the adjacency matrix to generate initial structural features. Structural encodings based on the Laplacian, for instance, are often preferred due to their interpretability. \n\nR1. We adopt the raw adjacency matrix primarily for simplicity. The architecture can seamlessly integrate richer structural encodings. Specifically, replacing the adjacency matrix with (i) a positional encoding matrix (you mentioned LapPE, SignNet, etc.) or (ii) a multi-hop propagation matrix, such as the Personalized PageRank (PPR) matrix, only requires a one-line change. Unfortunately, these encodings inevitably incur heavy preprocessing: computing Laplacian eigenvectors (LapPE) costs O(N^3) in dense form and O(kN^2) even with sparse Lanczos, while PPR requires O(N^3) for dense matrix powers or O(kE) only under sparse-iterative acceleration. By relying on the unprocessed adjacency, we avoid these upfront costs while still delivering strong empirical results. \n\n---\n\n> W1-2. The explanations for Equations 8 and 9 are unclear and could benefit from further elaboration.\n\nR2. Equation 8 normalizes attention scores by taking the $l_2$-norms of the Query and Key vectors, ensuring numerical stability and scale-invariance. Equation 9 then averages the value vectors and rescales the output via the diagonal matrix $D$. \n\n---\n\n> W2. The model introduces a number of hyperparameters that require careful tuning, which may complicate the optimization process and increase computational costs.\n\nR3. Thank you for highlighting the importance of training efficiency—this is indeed a shared limitation of current GTs. We have already noted it in Section F and regard it as a priority for future work.\n\n---\n\n> W3. The title seems not to fully reflect the contributions of the article. Although the contributions of this paper are rich, such a simple title cannot clearly describe all the key contributions. The authors might consider incorporating the contribution of unifying GTs into the title. \n\n\nR4. Thank you for this insightful suggestion. We will revise the title to explicitly reflect the contribution to unify existing Graph Transformers. \n\n---\n\n> Q1. What are the differences in the ability to capture the correlation between the two types of information for the two ways of cross-aggregation (across two dimensions)? Additionally, how do these differences impact the overall performance of the model?\n\nR5. The two cross-aggregation ways are nearly equivalent in their capacity to capture the correlations between two types of information. Since kernelized attention modules in Transformers treat both dimensions symmetrically, the overall impact on final accuracy is comparable. However, the feature-level aggregation reduces the quadratic complexity down to linear, making training faster and memory lighter. \n\n---\n\n> Q2. How does the optimization objective in Theorem 3.4 differ from commonly used graph optimization objectives? What properties does it aim to illustrate about the model? \n\nR6. Traditional graph objectives optimize a single representation to satisfy smoothness or reconstruction loss, whereas the objective in Theorem 3.4 explicitly separates topology representations and attribute representations, and introduces a balancing term that drives the cross-attention to align the two. This design enables UGCFormer to learn expressive embeddings by jointly preserving community structure and attribute fidelity while discovering their mutual interrelation. \n\n---\n\n> Q3. In the proposed model, the final representations are a combination of the topology and attribute representations. While this approach is intuitively sound, I am curious whether the authors have experimented with using the topology and attribute representations separately for node classification, rather than combining them. How would the results be? \n\nR7. This design is mainly based on the theoretical insights from Theorems 3.2 and 3.3, which indicate that the potential mechanism of GTs is the cross-aggregation between topology and attributes. The implementation of cross-aggregation via cross-attention necessitates keeping topology and attribute representations separate before the cross-attention, i.e., at the beginning. Besides, this separating-then-combining scheme was validated in existing works, e.g., LINKX, which highlights the rationality of this design.\n\nTo address your question, we have compared five models: UGCFormer, Only Topology (UGCFormer with topology branch alone), Only Attribute (attribute branch alone), MLP_topo (MLP trained on raw topology), and MLP_attr (MLP trained on raw attributes). \n\n| | Cora | CiteSeer | PubMed | Texas | Wisconsin | Cornell |\n|:--------|:---------:|:--------:| :--------:| :--------:| :--------:| :--------:|\n| UGCFormer | 84.9 | 73.4 | 81.8 | 84.6 | 87.4 | 85.1 |\n| Only Topology | 76.1 | 52.5 | 74.0 | 64.9 | 60.1 | 64.8 |\n| MLP_topo | 60.6 | 42.2 | 68.9 | 58.1 | 52.0 | 50.5 |\n| Only Attribute | 64.9 | 60.2 | 75.5 | 82.9 | 86.8 | 84.6 |\n| MLP_attr | 55.1 | 46.5 | 71.4 | 80.8 | 85.3 | 81.9 |\n\nAs shown in the table, the single-branch topology and attribute models consistently outperform their MLP counterparts, thanks to the cross-attention module that aligns the topology with the attribute spaces. Yet both branches still lag behind the fused UGCFormer, which consistently tops the table, demonstrating that combining both sources is essential for distinctive node representations.  \n\n---\n\n> Q4. As the authors mentioned in Section 3.1, existing models, despite their different approaches, essentially also capture the correlation between topology and attributes. Why does the model designed in this paper achieve performance improvements?\n\nR8. The proposed model outperforms prior work by achieving a **tighter alignment of topology and attributes**. Although existing models also capture their correlation, they entangle a large number of intermediate representations (in Eq. 20), e.g., topology–attribute–attribute and attribute–topology–topology, producing **an over-mixed, noisy embedding** that weakens the final alignment and degrades performance. After identifying the essence of GTs, we first disentangle each node representation into separate topology and attribute components, then introduce cross-attention that allows every node to selectively focus on the most relevant topology and attribute representations and fuse them through weight combination. Moreover, the proposed model further enforces distributional alignment via a consistency loss. Together, they deliver superior performance."}, {"review_id": "vdFkiXwiN6", "reviewer": "Reviewer_SSak", "summary": "This paper aims to propose an efficient and effective graph transformer for node classification task. The authors first explore the potential cross-aggregation mechanism in various graph transformers. They then present UGCFormer, which incorporates a linearized cross-attention module to model the interrelations between graph topology and node attributes. Additionally, a consistency constraint is applied to enforce mutual supervision between these two information, effectively tackling the overfitting risks caused by the dual-channel design.", "questions": "1) Could the authors discuss the relevance of prior works on vanilla transformers, such as those exploring associative memory, energy perspectives, and Hopfield network, to provide a more comprehensive context?\n \n2) I suggest that the authors discuss the relationship between the proposed method and the recent method CoBFormer [1], which also utilizes a consistency loss for graph transformers.\n\n3) What was the rationale behind choosing squared Euclidean distance as the consistency loss instead of using KL divergence?\n\n[1] Less is More: on the Over-Globalizing Problem in Graph Transformers, in ICML 2024.", "limitations": "Please see weaknesses and questions.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths \n\n1) The theoretical contributions of the article are notable. The finding of the potiential cross-aggregation is supported by a theorem, making the arguments convincing. Moreover, the theoretical connection between cross-attention and the optimization framework is clearly verified by a theorem.\n\n2) The article is adequately structured and written.\n\n3) Some experimental results appear promising. \n\nWeaknesses\n\n1) The disscussion to related works is inadequate. The paper does not adequately distinguish the cross-attention from existing fusion methods, such as concatenation and weighted combination. Additionally, the presented method may overlap with those of the work [1].\n\n2) The performance gain is not very significant, however it is acceptable given these benchmarks have been well-explored.\n\n[1] Edge-augmented Graph Transformers: Global Self-attention is Enough for Graphs, in KDD 2022.", "was_revised": true, "final_justification": "After reading the author's response, my concerns have been resolved. Taking into account the opinions of other reviewers, I decide to increase my score.", "rebuttal": "> W1-1. The paper does not adequately distinguish the cross-attention from existing fusion methods, such as concatenation and weighted combination.  \n\nR1. Based on your reminder, we will add a dedicated paragraph that contrasts the two paradigms based on their **principles and mechanisms** in the revised manuscript:\n\nThe typical fusion paradigm, i.e., (1) concatenation ($H=[H_1||H_2]W$, where $H_1$ and $H_2$ denote two representations from two different modalities, respectively, and $W$ represents the projection weight), and (2) weighted combination ($H = a* H_1+b* H_2$, where $a$ and $b$ denote the weights), is grounded in the **linear mixing hypothesis**: the optimal fused representation is assumed to lie in the linear span of the two modalities. As exemplified by the baseline LINKX, it treats the topology representations and the attribute representations as **static channels** that are combined via a single linear projection.  \n\nCross-attention is grounded in the **selective refinement hypothesis**: each modality acts as a context that selectively refines the other via a learned compatibility function, allowing non-linear, high-order interactions. The proposed UGCFormer treats topology representations as Query-Key and attribute representations as Value, or conversely, dynamically computing attention scores that determine how much of its topology representations should attend to which attribute representations. \n\nBesides, the above conceptual differences are demonstrated by our experiments in Section 4: UGCFormer outperforms LINKX on all sixteen benchmark datasets, demonstrating that the performance gain stems from the proposed interactive cross-attention mechanism. \n\n- - -\n\n> W1-2. The presented method may overlap with those of the work [1]. \n\nR2. We have compared UGCFormer with the mentioned Edge-augmented Graph Transformer (EGT) [1], and listed the apparent differences between them:\n\nFirst and foremost, EGT follows the strategy widely used in GT of augmenting pairwise attribute-based attention between nodes with graph topology, while UGCFormer captures topology-attribute interaction with cross-attention. Although EGT adds an edge channel in addition to the attribute channel, its purpose is to employ the edge features to influence the attention process (via addition and gating) rather than capture the interaction between the two channels. Therefore, the proposed UGCFormer is novel, and there do NOT exist overlapping ideas between UGCFormer and EGT. Furthermore, EGT incorporates large-scale edge features of size $N^2 \\times D$ (where $N$ is the network size and $D$ is the feature dimension), which significantly increases the computational complexity and thereby hampers its scalability. In contrast, UGCFormer introduces a linear cross-attention mechanism that efficiently captures the interaction between topology and attributes. \n\nBy considering its importance in GT, we will cite [1] and compare it with UGCFormer in the revised manuscript. \n\n- - -\n\n\n\n\n> Q1. Could the authors discuss the relevance of prior works on vanilla transformers, such as those exploring associative memory, energy perspectives, and the Hopfield network, to provide a more comprehensive context?\n \nR3: According to your suggestion, we have strengthened the related work section of the revised manuscript to explicitly elucidate these connections, with key additions summarized below: \n\n(1) Associative Memory: The self-attention mechanism in Transformer implements content-addressable memory retrieval through query-key similarity matching, similar to associative memory architectures. This highlights its efficiency in extracting relevant information from large datasets. (2) Energy Perspective: The self-attention update rule is formalized as gradient descent on an energy landscape, highlighting the energy minimization interpretation of attention mechanisms. This aligns with energy-based models and deepens the theoretical understanding of Transformers' stability and convergence. (3) Hopfield Network: Transformer layers are reinterpreted as continuous modern Hopfield networks, with parallels such as exponential memory capacity from high-dimensional embeddings and softmax-attention dynamics mirroring Hopfield networks.\n\nThank you for highlighting the importance of connecting vanilla Transformers to foundational theoretical frameworks. This is crucial for developing advanced Graph Transformers. \n\n- - -\n\n> Q2. Suggest that the authors discuss the relationship between the proposed method and the recent method CoBFormer [1], which also utilizes a consistency loss for graph transformers.\n\n[1] Less is More: on the Over-Globalizing Problem in Graph Transformers, in ICML 2024. \n\n\nR4. We have compared the consistency losses in CoBFormer and UGCFormer. Both models use consistency losses to enforce mutual supervision between predictions from different channels. However, CoBFormer focuses on aligning local and global information, while UGCFormer emphasizes the topology-attribute interrelation.\n\n- - -\n\n> Q3. What was the rationale behind choosing squared Euclidean distance as the consistency loss instead of using the KL divergence?\n\nR5. We choose squared Euclidean distance mainly for its simplicity and computational efficiency, as it directly measures differences without requiring logarithmic operations. The ablation experiments demonstrate the effectiveness of the consistency loss, as illustrated in Figure 3. We are willing to leave the exploration of a consistency loss based on the KL divergence to future work."}]

Author rebuttal:

Meta-review: **Summary:** This paper proposes UGCFormer, a universal graph Transformer that formalizes the cross-aggregation mechanism as the key driver of existing Graph Transformers and implements it with a linearized Dual Cross-Attention (DCA) module. The model explicitly integrates graph topology and node attributes, with a consistency constraint to alleviate overfitting. The paper provides theoretical justification for the mechanism, comprehensive experiments across homophilic and heterophilic benchmarks, ablation studies, and efficiency analyses.

**Decision:** Reviewers found the work technically solid and the proposed architecture both effective and efficient. Some concerns were raised regarding novelty, the need for clearer distinction from related works, code reproducibility, and analysis of underperformance on certain datasets. The authors engaged actively during rebuttal, offering additional robustness experiments, qualitative analyses, and clarifications on theoretical and implementation aspects. These responses resolved most concerns, and reviewers updated their ratings accordingly. Overall, the paper makes a clear and valuable contribution to the development of graph Transformers. I therefore recommend acceptance.
Decision: Accept (spotlight)