DUALFormer: Dual Graph Transformer
Authors: Jiaming Zhuo
Yuwei Liu
Yintong Lu
Ziyi Ma
Kun Fu
Chuan Wang
Yuanfang Guo
Zhen Wang
Xiaochun Cao
Liang Yang
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Transformers
Node Classification
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Transformers (GTs), adept at capturing the locality and globality of graphs, have shown promising potential in node classification tasks. Most state-of-the-art GTs succeed through integrating local Graph Neural Networks (GNNs) with their global Self-Attention (SA) modules to enhance structural awareness. Nonetheless, this architecture faces limitations arising from scalability challenges and the trade-off between capturing local and global information. On the one hand, the quadratic complexity associated with the SA modules poses a significant challenge for many GTs, particularly when scaling them to large-scale graphs. Numerous GTs necessitated a compromise, relinquishing certain aspects of their expressivity to garner computational efficiency. On the other hand, GTs face challenges in maintaining detailed local structural information while capturing long-range dependencies. As a result, they typically require significant computational costs to balance the local and global expressivity. To address these limitations, this paper introduces a novel GT architecture, dubbed DUALFormer, featuring a dual-dimensional design of its GNN and SA modules. Leveraging approximation theory from Linearized Transformers and treating the query as the surrogate representation of node features, DUALFormer \emph{efficiently} performs the computationally intensive global SA module on feature dimensions. Furthermore, by such a separation of local and global modules into dual dimensions, DUALFormer achieves a natural balance between local and global expressivity. In theory, DUALFormer can reduce intra-class variance, thereby enhancing the discriminability of node representations. Extensive experiments on eleven real-world datasets demonstrate its effectiveness and efficiency over existing state-of-the-art GTs.

Published as a conference paper at ICLR 2025
DUALFORMER: DUAL GRAPH TRANSFORMER
Jiaming Zhuo Yuwei Liu Yintong Lu Ziyi Ma¹
Kun Ful
Chuan Wang
Yuanfang Guo Zhen Wang' Xiaochun Cao Liang Yang!
Hebbe Province Key Laboratory of Big Data Calculation, School of Artificial Intelligence, Hebei University of Technology. Tianjin, China
"Shoool of Computer Science and Technology. Beijing JiaoTong University, Beijing, China
$ Schooo of Computer Science and Engineering, Beihang University, Beijing, China
"School of Artificial Intelligence, OPtics and ElectroNics (iOPEN).
School of Cybersecurity, Northwestern Polytechnical University, Xi d'an, China
"Scoool of Cyber Science and Technology.
Shenzhen Campus of Sun Yat-sen University, Shenzhen, China jiaming wutooouttoooo.oo.ooooooooooooooo com,
(2023328C3037, 202322802030) hebut. edutteedduccmm cn, zyma@hebut. cn, fukun@hebut. edu. cn, wangchuang www.eiieeac...oooo andyguo@bua..edu.comm en, t-zzhneewwu.eedu.. caoxiaochun@mail.c
wtwp://mmmmma............o. syw.. en, yangLiangerip.og.oo
ABSTRACT
Graph Transformers (GTs), adept at capturing the locality and globality graphs. have shown promising potential in node classification tasks. Most statc-of-the-art GTs succeed through integrating local Graph Neural Networks (GNNs) with their global Self- Self-Attention (SA) modules to enhance structural awareness. Nonetheless, this architecture faces limitations arising from scalability challenges and the trade- off between capturing local and global information. On the one hand, the quadratic complexity associated with the SA modules poses a significant challenge for many GT', particularly when scaling them to large-scale graphs. Numerous GTs neces- sitated a compromise, relinquishing certain aspects of their expressivity to garner computational efficiency. On the other hand, GTss face challenges in maintaining detailed local structural information while capturing long-range dependencies. As result, they typically require significant computational costs to balance the local and global expressivity. To address these limitations, this paper introduces a novel GT architecture, dubbed DUALFormer, featuring dual-dimensional design of its GNN and SA modules. Leveraging approximation theory from Linearized Trans- formers and treating the query as the surrogate representation of node features. DUALFormer efficiently performs the computationally intensive global SA mod- ule on feature dimensions. Furthermore, by such a separation of local and global modules into dual dimensions, DUALFormer achieves a natural balance between local and global expressivity. In theory, DUALFormer can reduce intra-class vari- ance, thereby enhancing the discriminability of node representations. Extensive experiments on eleven real-world datasets demonstrate its effectiveness and effi- ciency over existing state-of-the-art GTs.
INTRODUCTION
Node classification, aimed at accurately predicting the categories labels of individual nodes based on the graph topology and node attributes, is an essential task in social networks Bhagat et al. [201T), citation networks Ju et al. (2024). and biological sciences Yi et al. (2022). among other domains. Graph Neural Networks (GNNs) Kipf & Welling (2016) have emerged as a dominant architecture for this task due to their outstanding ability capture local neighborhood information. Most GNNs, such as the seminal GCN & Welling (2016), and subsequent innovations Klicpera et al. (201);;
Velickovic et al. (0077) follow graph-based message-passingg paradigm Gilmer al. (0017) where
corresponning author

---

Published as a conference paper at ICLR 2025
the representations of each node are updated by aggregating the information from its neighboring
nodes. Although such localizing property has propelled notable success for GNNs, the other side is
that it creates a bottleneck for GNNs to obtain long -aagg dependencies Dwivedi et al. (2222) As
result, GNNs often encounter over-smoothing and over-squashing issues Alon & Yahav (2021)
Initially developed for NLP, Transformers Vaswani al. (2017), known for full-token connectivity enabled by the Self-Attention (SA) mechanism, have shown significant performance across vari- ous tasks Gilkioz al. (2020). Recently, Graph Transformers (GTs) with excellent expressivity have been presented and shown notable potential in addressing the above issues of GNNs Wu et al. (202T); Chen et al. (2022) 2024a b). The success of GTs lies in their ability to simultaneously capture long- range dependencies and structural bias from graph structure. Accordingly, GTs for node-level tasks can be broadly divided into four categories: 1) Node attribute extension using positional/strrutuuaal encoding, including NodeFormer Wu et al. (2022). NAGphormer CCen et al. (2023), Exphormer Shirzad et al. (2023). and GOAT Kong et al. (202);
; 2) Sampling context nodes based on graph, con- laining GOAT and NAGphormer; 3) GNN block integration, encompassing NAGphormer, GOAT, SGFormer Wu et al. (2024), Polynormer Deng et al. (2024), and CoBFormer Xing et al. (2024); and 4) Edge rewriting, represented by Exphormer. Their introduction signifies an initial stride.
Nonetheless, existing GT's typically encounter two primary challenges, as illustrated in Fig. [a). 1) Unscalability. In pursuit of global dependencies between nodes, GTs, particularly those built upon the vanilla SA mechanism Wu et al. (202T); Chen et al. (2022). tend to encounter scalability issues due to their quadratic time and space complexity, which prohibitive when dealing with large-scale graphs. To address this issue, existing approaches tend to compromise the global expressivity (c.g., NAGphormer and Exphormer) or increase model complexities (e.g.. GOAT, CoBFormer). This re- sults in models that may fail to generalize well. 2) Tradeoff dilemma of locality and globality. It noteworthy that several offte-of-the-art GTs (e.g., NAGphormer, GOAT, SGFormer, Polynormer, and CoBFormer), either explicitly or implicitly, still resort to the GNNs to learn local node repre- sentations; These representations are then incorporated with Self-Attention (SA) blocks to generate final node representations. Unfortunately, GTss demonstrate a certain level of information loss, stem- ming from the necessity to trade off the locality and globality. Specifically, they tend to encounter challenges in retaining the fine-graie fine-grained structural details while capturing long-range dependencies, which could lead to the loss of nuanced information crucial for accurate node classification.
This paper seeks to break the aforementioned limitations by devising novel GT architecture with (1) an efficient SA mechanism and (2) a comprehensive fusion mechanism of local and global infor- mation. To this end, the architectures of existing GT's are systemically investigated, and intuitive interpretation of these limitations from a decoupled perspective, as shown in Fig. aa). Specifically, the existing global SA mechanisms default the value as the agent representation of node features, essentially performing a global message passing between nodes to capture the global dependencies. Thus, the common fundamental factor in these two issues is an over-reliance on single dimension. Intuitively, through regarding the query as the agent representation and leveraging the established approximation between (Query x Key) x Value and Query x (Keyx Value), the aforementioned global message passing can be efficiently executed along the feature dimension. Inspired by these insights, this paper proposes DUALFormer, a simple yet effective GT architecture featuring a dual-dimension design, as depicted in Fig. [b). The idea of DUALFormer is to decouple the GNN and SA modules from the same dimension to separately model local and global information in the node dimension and feature dimension, respectively. Therefore. it achieves efficient global SA on the one hand, and on the other, it naturally integrates locality and globality without compromising the trade-off. The comparisons between GT's regarding performance, running time, and GPU memory usage demon- strate the effecttivness and efficiency of DUALFormer, as shown in Fig. 2
The contributions of this paper can be summarized as follows:
We investigate two drawbacks of existing Graph Transformers (GTss, that is, unscalability and tradeoff dilemma between local and global expressivity.
We introduce DUALFormer, simple yet comprehensive GT architecture featuring dual- dimensional design of its local and global modules.
Extensive experiments on public benchmark datasets demonstrate the superior performance and efficiency of DUALFormer over state-of-the-art GNNs and GTs.
2

---

Published as a conference paper at ICLR 2025
Local module
as the
as represeutations
Output
represeniationss
GNN
Tradeoff
Roch
Features
GNN Block
Output
Input
NxN
DHD
Moch Local
Features
Global
Block
Approsimate
Features
Allention Scoras
Attention: Seores
Global module
Input
(a) Existing GTT's with tradeoff' strategy for local and global modules.
(b) The proposed DUALFomer with simple yet comprehensive dual-dimensional architecture.
Figure The design motivation of the proposed DUALFormer and comparison with existing state-of-the-art GT architectures. (a) Existing GTs suffer from two primary challenges: 1) the scala- bility issue from Self-Attention (SA) mechanisms, and 2) the tradeoff dilemma of local and global in- formation. By default, global SA mechanisms serve the value V the agent representations of node features, so that by employing attention score matrix sim Q K) E IR X to capture global depen- dencies among nodes. Intuitively, by leveraging the approximation sim Q, K)V Qsim (K, V), and treating the query Q as the agent representations, the above global SA mechanism can be effi- ciently implemented in the feature dimension. (b) DUALFormer is dual-dimensional GT architec- ture that seamlessly integrates the local GNN block and global SA block on dual dimensions. Thus, DUALFormer effectively and comprehensively leverages the advantages of both dimensions.
PRELIMINARIES
This section starts with an overview of the notation used in this paper. It then provides an introduc- tion to the fundamental concepts of Graph Neural Networks (GNNs). Finally, it details the vanilla Transformer architecture and Graph Transformers (GTs) that extends upon GNNs.
2.1 NOTATIONS
Matrices (e.g.. W) are in bold capital letters, vectors (e.g.. Wi.,, which represents the i-th row vector of W), are in bold lowercase letters, scalars (e.g., Wiyj, which stands for the elements in the i-th row and j-th column of W), are in lowercase letters, and sets (e.g.. V) are in calligraphic letters.
For general-purpose description, this paper examines undirected attribute graph G(V,E). The node set V consists of n node instances ((x,,
where E Rnxf and Y R nxe represent the attributes and labels of node respectively, and f is the attribute dimension and c is the label dimension. E = { 2y stands for the edge set. Generally, the adjacency matrix E R= is utilized to describe the graph topology and 0t.j 1 only if there is the edge (v,, vi) &, otherwise as.j = Its forms Random- Walk (RW) normalization À D A and Laplacian normalization Á = D - AD- are commonly utilized, where D denotes the diagonal degree matrix. Morcover, the graph
be expressed in matrix form as (AA, X).. Besides, Y c E IR and Yu R xe stand for the labels of the labeled and unlabeled nodes, respectively.
2.2 GRAPH NEURAL NETWORKS
Propagation-baa based Graph Neural Networks (GNNs) typically follow the messaae-passsing paradigm Gilmer et al. (017) to harness structural biases in graphs. Within each layer, the representations of center nodes are updated by iteratively aggregating and combining the features from their adjacent nodes (i.e,, one-hop neighbors) in the graph. In specific, for node v in the 1-th layer, denoted by h the above representation update can be expressed as
hg A Aggregation' ((b"-"/u E W,)), h Combination ((h K.))
where Aggregation(-) and Combination(,) denote the aggregation and combination modules, re- spectively. A represents the neighbor set of node v. Typical GNNs detailed in Section B
Despite their localizing property, GNNs still struggle to effecttvely capture long-range dependencies Dwivedi al. 2022). A trivial approach is to broaden the receptive field of each node by stacking
3

---

Published as a conference paper at ICLR 2025
ACC Time Memory
ACC vs. Time Memory
ACC Time Memory
75.0
Fomeer
Cethurger
New
$4.0
Pedpwweer Saderhise
$3.0
Wiggtoreer
5
GAAT
12.0
Redellemer
73.5
79.0
Time/epochi(m))
Time/spuch(ms))
Timelrpoc((ms)))
(a) Corn
(b) CiteSeer
(c) PubMed
Figure 2: Comparisons between GTs regarding accuracy, running time, and GPU memory usage.
The size of circles signifies memory consumption. DUALFormer achieves superior performances in a shorter runtime (except simple SGFormer) over baselines, showing its effectiveness and efficiency.
multiple layers. However, this approach tends to lose discriminative information of representations due to over-smoothing and over-squashing Alon & Yahav (2021).
2.3 GRAPH TRANSFORMERS
Unlike the localized GNNs that restrict information aggregation to the neighborhood scope, Trans- formers facilitate a holistic aggregation across all token pairs through the self-attention mechanism. Intuitively, the above self-attention mechanism functions similarly to GNNs and can specifically be considered instances with the global receptive field of the message-pasiee paasiig paradigm.
Transformer Architecture. The vanilla Transformer Vaswani et al. (0117) consists of two essential components: Multi-Heads Self-Attention (MHSA) and Feed-Forward Network (FFN). The former enables the model to capture global dependencies between all tokens within the sequence, while the latter performs additional non-linear transformation. Given n tokens Z ?zll==0 E Faxd each head, the self-attention first maps the input features Z to query (Q), key (K), and value (V) vectors. Then, attention scores from query-key pairs are applied to weight aggregate the value vectors.
Specifically, general expression of Self- Delf-Attention (SA) module can be expressed as
Q = zzW K ZWK. V ZWv,
(2)
exp(sim((a:) (0, k.))
2. - Σ SQK Vu Σ
NEV Eusy exp(sim((x. k..))
Vu:
(3)
where We. WK. and Wv E Rdddd denotes trainable projection matrices. sim(,) ) terms the sim- ilarity function, which mainly adopts scaled dot dot-product attention, i.e., sim sim(Q, where d is the feature dimensions. Note that the attention score matrix SQK E x n is derived by
QKT/Vá
computing similarities of all query-key pairs, which leads the computation complexity of O(?)).
After obtaining the features for each head ()). MHSA derives the final features by concatenating the outputs from all t heads and then applying subsequent linear transformation, namely,
Ž final Concat (()) Z(n) ......... (()-)) W
(4)
where W Ridxd stands for trainable projection matrix.
Transformers on Graphs. To exploit the structural biases in graphs, current GTs have adopted four strategies integrate discriminative topology information into the vanilla Transformer, as outlined in Section I Among these, many SOTA GT's rely on the GNNs to create local representations, such as SGFormer Wu et al. (2024), Polynormer Deng et al. (2024), and CoBFormer Xing et al. (2024). The final node representations are typically derived via two schemes: ! local-and-globe fusion and 2 local-to-global fusion, as detailed Section B
METHODOLOGY
This section first highlights the significance of deploying self-attention in the feature dimension by examining its linear approximation. Then, it introduces a -ineenssoii GT architecture. Finally, it compares the proposed GT with existing GT's in terms of scalability, simplicity, and expressivity.
4

---

Published as a conference paper at ICLR 2025
3.1 ANALYSIS AND MOTIVATIONS
As previously discussed in the Introduction, existing GT' tend to encounter the scalability issue and the dilemma of trading off global and local information. To overcome the scalability issue, which arises from the need to compute pairwise similarities between queries and keys in Softmax attention, linearized attention mechanisms Katharopoulos et al. (2020); et al. (2023) have been introduced. These mechanisms approximate or replace the Softmax attention using separate kernel functions, allowing for changing computation order from the standard (Query Key) x Value, as formulated by to a more efficient Query x (Keyx Value) format.
Eq. B
Given a kernel function with representations (X),, Eq. can be rewritten as
2. ((q.) (Euev
(5)
((q.) E Euev (k,)T)
This equation becomes clearer when expressing the numerator in vectorized form, that
Ż = Sim Q K)V = =(Q) (o(K)
(6)
where the kernel function can be exponential linear unit d(X) clu(X) + 1. Notably, this mecha- nism reduces the computation complexity from (n)²) to (n)).
Upon reviewing the above two forms of self-attention mechanisms, two pivotal insights emerge.
The standard self-attention mechanism (Eq. encapsulates the global dependencies among samples. The formula leverages the value (V) surrogate representation of the input features Z, with the attention score matrix sim Q, K) functioning as the dependen- cies matrix between samples. Thus, this formula can be interpreted as a message-passing process that propagates the value features (Vi.) on the global dependencies matrix. Mean- while, this mechanism possesses global expressivity, ie.. capturing global dependencies.
The above linearized self-attention mechanism (Eq. 6 effectively captures the global correlations between features. From the message pessage-passing viewpoint, one can regard the query (Q)) as the representation of Z, and the product matrix (o(K)V V) as the correlation matrix between features. In contrast to the original attention (Eq. 3). the linearized attention can be interpreted as another message-passing process between features, which propagates the query features (o(q:.)) with the correlation matrix as the propagation matrix. As result, this mechanism can model the correlations between features.
According to the approximation between these two formulas, is natural to conclude that within the self-attention mechanism, characterizing the global dependencies between nodes is approximately equivalent to describing the global correlations between features. Thus, the self-attention mecha- nism can be implemented in the feature dimension.
3.2 DUALFORMER
Inspired by the analysis in the previous subsection, this subsection presents novel GT transformer, which is referred to as Dine-siiensional TransFormer (DUALFormer). Central to the design of DUALFormer is an efficient global attention module that captures the implicit dependencies between nodes from the dimension regarding features. DUALFormer includes three modules, each described below. Refer to Section for the pseudocode of these modules.
Input Projection Layer. Considering that the node attributes X in graph G(A, X) are unprocessed and high-dimensional, a Feed-Forward Network (FFN) f Raxf + Raxd is deployed to project these attributes into a low-dimensional hidden space, thus producing informative node features. By opting for Multi-Layer Perceptron (MLP) Rumelhart et al. (986) as the network architecture, these node features can be represented as
H MLP
The obtained feature H serves as the input to the subsequent SA and GNN modules.
To efficiently capture global dependencies between nodes while sidestepping the trade-off dilemma between local and global expressivity, DUAL.Formet introduces dual-ddieensoonll architecture, as
5

---

Published as a conference paper at ICLR 2025
shown in Fig. Unlike existing GTs, which typically integrate local and global interactions between nodes only in the node dimension, DUALFormer designs an innovative approach by modeling these interactions across two distinct dimensions. The details are follows.
Global Attention Module. This attention module is designed to efficiently capture global depen- dencies between nodes. It accomplishes this by introducing computation unit that captures full-pair correlations among features, thereby enabling the implicit capture of global node interactions. More- over, the module leverages a comprehensive Value computations (Eq. 2 the residual connections He al. (2016), and the scaled dot-product attention (Eq. B).
of established techniques from the Transformers for
each layer, which include the Beeer-KKe-Vee
Given the initial node features (
H this module can be expressed as
Q n 2(-11) w!!! Q K (011) vO ww
T V v (Q4) K(
vn
0 o + (1 (11111))
where Q, K. and V denote the query, key, and value, respectively, and (-)) represents the nonlinear activation functions, such as softmax(-), and M terms the attention score matrix, which character- izes the feature-to- to-feature correlations. a denotes a hyper-parameter to balance the representations derived from attention and those from the previous layers. Moreover, to augment the representation capabilities of DUAL Former, this module can incorporate the Multi-Head Self Self-Attention (in Eq. 4 and layer normalization Lei Ba et al. (2016). For clarity, is still used as the agent representation, with the order modified accordingly.
Local Graph Convolution Module. After the global representations from the attention module are obtained, diverse graph convolution blocks from GNNs can be incorporated to further integrate local information into the learned representations. Thus, an expression for this module
(k) A GNN (A,H(((-))
where (0) 20, and L represents the number of the attention layers. GNN(,) denotes the GNN layers. In DUALFormer, SGC (Eq. [T] is opted for GNN(,) ). capitalizing on its streamlined design and effectiveness. Furthermore, the impact of various GNN layers is analyzed in Section 4.2 Once the node representations from K layers of graph convolutions are obtained, prediction layer is used to yield the final predictions, that is, Y (L)(H(())
The proposed DUALFormer, although simple in design, possesses three attractive characteristics:
Efficiency and scalability. The above architecture, leveraging the sparse diffusion matrix (e.g., adjacency matrices) and low-dimensional attention score matrix M e Rdxd operates with complexity that is linearly related to the scale of the graph. Therefore, DUALFormer is computationally efficient and potentially scalable to large-scale graphs.
Comprehensiveness. The above architecture thoroughly accounts for the local inter-node dependencies and the global inter-feature correlations, which can be regarded as an approx- imation of the global inter-node dependencies. Furthermore, owing to the dual-dimensional design, it achieves a natural tradeoff between local and global expressivity. The detailed explanations of the localizing and globalizing properties of DUALFormer are presented in Section[E.4] Thus, DUALFormer is an informative and comprehensive GT architecture.
Theorem 1. (Discriminability Improvement.) Global attention module (Eq. g reduces the intra- class variance while keeping inter-class variance unchanged.
Theorem I indicates that DUALFormer is capable of diminishing class overlap, thus improving the effectiveness of representation learning. The proof of this theorem can be found in Section C
To sum up, this innovative dual- dinenssinnii design enables DUALFormer to efficiently and compre- hensively harness the strengths of both dimensions of the feature matrix within a unified framework. This emphasizes the simplicity and efficiency of DUALFormer..

---

Published as a conference paper at ICLR 2025
Table 1: Comparison between GTs in terms of three aspects: Time Complexity, Required Compo-
nents, including Positional Encodings (PE), Augmented Training Loss (ATL), Edge Features (EF), and Additional Parameters (AP), and Global Expressivity. Here, n represents the size of the graphs. stands for the number of edges. The notation Appr. represents approximate.
Time Complexity
Components
Global
Model
Pre-processing Training
PE
ATL
EF
AP
Expressivity
GraphTrans (NeurIPS 202/)
Oín e) O(n²
YES
SAT (ICML 2022)
O(n
YES
GraphGPS (NeurIPS 2022)
O(n²)
O
7
YES
NodeFormer (NeurIPS 2022)
/
YES
NAGphormer (ICLR 2023)
O(n)) O +e)
O(n)
V
NO
Exphormer (ICML 2023)
Appr.
GOAT (ICML 2023)
(nlog(n)
O
V
Appe
SGFormer (NeurIPS 2023)
O
YES
Polynormer (ICLR 2024)
O(n+e)
YES
GoBFormer (/CMI. 2024)
O(nlog(n))
O(+++e)
Appr.
DUALFormer (Ours)
O(++c)
YES
3.3
COMPARISON WITH OTHER GTs.
This subsection presents a comparison between the proposed DUALFormer and some state-of-the- art GT's, aiming demonstrate the advantages of DUALFormer. As shown in Table DUALFormer has more streamlined and efficient architectural design compared to the baselines. Taking this into account across three aspects, the detailed explanation as follows.
Scalability. GraphTrans Wu et al. (2021) and She et al. (2022) have a complexity of O ((n2++p +e) due to the computational demands the self-attention mechanism, which calculates the full-pair tention scores between nodes, and the message message-passing mechanism (in Eq. []. This computational intensity becomes bottleneck for scaling large-scall graphs. contrast, the proposed DUAL- Former offloads such computationally intensive self-attention mechanism to the low-dimensional feature dimension, thus achieving linear time complexity. Besides, the absence of additional param- eter requirements precludes increase in spatial complexity. Both aspects ensure its scalability.
Components. To integrate the discriminative information of graph structure into their architectures, existing GT's often resort to the additional components: positional/structural encoding (e.g.. random- walk structural encoding and Laplacian eigenvectors encodings Rampásek et al. (2022)), augmented training loss (e.g., edge regularization loss in NodeFormer), and the local GNNs, which necessitates additional parameters to control its effect (e.g.. a hyper-parameter in SGFormer and learnable param- eters in Polynormer). Compared them, Formmer features a more streamlined and efficient architectural design, requiring neither positional/struccurra encoding, augmented loss, nor additional parameters, and utilizes only simple local graph convolution and global attention.
Expressivity. Due to the limited receptive field of nodes, many existing GTs lack global expressiv- ity. For example, NAGphormer achieves linear complexity through k-hop neighborhood sampling. yet this approach, while enhancing computation efficiency, leads to a compromise in the global ex- pressivity. Additionally, several GTs (e.g., Exphormer, GOAT, GoBFormer) attain linear complexity through clustering-like techniques; yet, this approach offers only an approximate global expressiv- ity due it equips nodes with an indirect global receptive field. In contrast, DUAL.Former stands out by delivering both global expressivity and linear complexity. Section E.4 provides analysis that demonstrates the superiority of the proposed self-attention module between features over the traditional elffatttetion module between nodes.
EXPERIMENTS
This section first evaluates the effectiveness and efficiency of the proposed DUALFormer by com- paring its performance against various graph representation learning models on tasks of node classi- fication and property prediction. Subsequently, it performs several additional experiments to provide a comprehensive understanding of DUALFormer. For details on the utilized benchmark datasets, the compared baselines, the experimental setups, and the tuned hyperparameters, refer Section D

---

Published as a conference paper at ICLR 2025
Table 2: Accuracy in percentage (sta over 10 trials of the node classification task across seven graphs. Best and runner-up models are bolded and underlined, respectively.
Model
Cora
CiteSeer
PubMed
Computers
Photo
CS
Physics
GCN
$1.60
71. 21.60ga.40
28.80
89.65
92.70 20.20
92.92
96.18 96.18
GAT
83.00
10
79.00
90.78 90.78
03.6112.14
96.17 96.1740.08
GraphSAGE
82. #2.68
71.93+a.85
79. 2 +0.0a
91.20=
94. 04.59:0.14 #d.14
93.91 =3.91=0.18
40.40
APPNP
83.30
71. 50
80. 10.10+a.uu 20
90.18 =0.17
94. 04.32++0.14
94. 49.0007
96.5 96.54+0.07
SGC
80.10
71.90=0.14
78.70 70
90.11
91.97 20.19
93. 93.41=0.22
96.35 96.35+40007
GraphGPS
82.84 .13
72. 1.
79. 79.94420.2
91.1942..4
95.06
93.93
97. 97.124u.19
NodeFormer
82.20
12.50
79.90+1.00
86,98 20.60
93.46
95.64
96. 96.2440024
NAGphormer
82.12
11.0
79.73
01.22.10.1
95.49 10.11
95.75 10009
97. 97.34100.0
Exphormer
82.77
11.63
79.4610.35
91.47 10.17
35.35
94.93_0.00
96.89.10.0
GOAT
83.18 1.22
1.
79.13
90.96.0..0
92.96
94.21
96,45
SGFormer
84.50
72.60
80.30 $00.00
91.99
95. 20.47
96.60.0.18 94.78
Polynormer
83. 83.25
72.31
29.24
23.6
96.46 20.26
95.53=0.16
97.27 97.27-+0.08
CoBFormer
94.71.0:70 73
74.29 20.51
81.42 +0.53
92. 92.21=0.41
95.46+0.49
04.91=0.07
97. 97.33+4022
DUAL.ormer
74.45 85.88+0.100
83.97
93. 18.16
96.7440.08
05.62_0.00
97.42
Datasets. In the node classification experiments, seven benchmark datasets are employed, including
Cora Sen et al. 2008), CiteSeer Sen al. (2008), PubMed [Sen al. (2008), Computers Shhchu
et al. (2018), Photo Shehur et al. 2018). CS Shchur et al. (2018), and Physics Shehur et al. (0018).
For the node property prediction. four benchmark datasets are utilized. including ogbn-proteins Hu
et al. (2020), ogbn-arxiv Hu et al. (2020), ogbn-products Hu et al. (2020), and pokec Jure 2014).
For details on the utilized datasets, refer to Section D.I]
Baselines. The baseline models include five typical GNNs; GCN Kipf & Welling (2016), Graph- SAGE Hamilton et al. (2017), | Velickovic et al. (2017). APPNP Klicpera et al. (2019), and SGC Wu et al. (2019), and eight GTss that represent the cutting-edge in this field: (GraphGPS Rampásek et al. (2022), NodeFormer Wu et al. (2022), NAGphormer Chen et al. (2023), Exphormer Shirzad ct al. 2023). GGAT|Konee et al. (2023), SGFormer Wu et al. (2024). Polynormer Deng et al. (2024),
CoBFormer Xing et al.al.2222)) (2024). Section D.2 offers an introduction to the compared models.
4.1 EXPERIMENTAL RESULTT
Node Classification. The results of the models on the node classification task are presented in Tab. and Fig. 2 Two observations can be drawn from Tab. [ The first point is that the proposed DUAL- Former outperforms the baseline models on five of the seven datasets and delivers near-optimal per- formances on the remaining two. This demonstrates the superiority of second point is that the proposed DUALFormer demonstrates significant performance advantages on Cora and PubMed datasets, exceeding all baselines by a wide margin. Specifically, the accuracies of DUALFormer exceed those of the runner-up model (CoBFormer) by 1.17% and 2.55%, on these two datasets, respectively. Note that some of state-of of-te----hhearrr baselines, e.g., SGFormer, Polynormer, and CoBFormer, either explicitly or implicitly, incorporate GNNs, similar to DUALFormer. Thus, the performance advantages can be attributed to the fact that the proposed dual-dimennionaal architec- ture efficiently reduces information redundancy between the GNN and Self-Attentio (SA) blocks, achieving collaborative propagation of local and global information. Furthermore, as depicted in Fig. 2 the proposed DUALFormer not only achieves superior performance but also consumes less computation time compared to the GT baselines except SGFormer. To be specific, the red circles, representing the proposed DUALFormer, are superior left and above most other circles in the fig- ure. This implies DUALFormer is lightweight, aligning with conclusions in Section 3.3 Besides, DUALFormer introduces modest memory usage, which indicates its potential for scalability.
Moreover, the
This experiment is designed to evaluate the scalability and effectiveness of the models by testing them on four large-scale graph datasets. The experiment results for the node property prediction task on these datasets are presented in Tab. 3 Upon observing this table, two key conclusions can be drawn. (1) Most GTs consistently show superior performance over the backbone GNNs across all datasets. This is because most GTs incorporate GNNs as their local module in architecture. Based performance that is at least on par with its individual components. (2) Compared to the baselines, the proposed Former achieves superior performances across three of the four datasets. These
Node Property Prediction.
the concept of feature fusion, the integrated architecture typically achieves
8

---

Published as a conference paper at ICLR 2025
Table 3: Results (ROC-AUC for the ogbn-proteins and Accuracy for the others) in percentage (mean over 10 trials of node property prediction across four large-scale graphs. Best and runner- up models are bolded and underlined, respectively. # #OOM means out of memory.
Model
ogbn-proteins
ogbn-arxiv
rebnnproddcct
pokec
GCN
71.74 20.51
25.6440.21
75.4
GAT
72.02
21.95
79.45
12.23
GraphSAGE
77.68
21.49
18.50
75.6320.38
GraphGPS
76.83
20.97
75.39
74.42
NodeFormer
77.45.1.15
67.19
72.9340.18
71. 71.00
NAGphormer
73.61
70.13
73.55+0.21
20.25
Exphormer
74.58
72.44
76.9640.05
a0.40
SGFormer
79.53.10.58
72.63
74. 14.101
73. 06.224
Polynormer
78.97
73.46
83.82
86.10+0.00
CoBFer
48.59
73.17
78. 78.1540.07
79.82+0.29
DUALFrrmer
82.98
73.71
83.91
82.97
results demonstrate, on one hand, that DUALFormer is scalable to large-scale graphs and, on the other, illustrate its effectiveness. Notably, DUALFormer achieves 3.45% higher ROC-AUC over the second-ranking model SGFormer on the ogbn-proteins dataset, which highlights its superiority.
4.2 ADDITIONAL EXPERIMENTS
Scalability Study. This experiment aims to thoroughly examine the scalability of DUALFormer. It achieves this by randomly sampling nodes for the training set, gradually increasing the sample size from 10K to 100K nodes, and monitoring both training time and GPU memory usage as the dataset size varies. The variations in terms of running time and GPU memory consumption obg-products dataset are reported in Fig. Beefft and (right), respectively. It is evident that both the running time and memory consumption of Dormerrmer increase linearly with the size of the graph, indicating that QUALFormes possesses linear time and space complexity. This is consistent with the conclusion presented in Section 3.3 thereby demonstrating the scalability of DUALFormer.
the
Training time
GPU memory cost
Timelmal
Memory
0.5
300
02
nodes(10k)
nodes(10k)
Figure 3: Training time and GPU memory usage of DUALFormer on the
dataset.
Backbone Performance Evaluation. This experiment is designed to evaluate the impact of differ- ent backbone GNNs (including GCN, APPNP, and SGC) on model performances. Fig. 4 provides the experiment results, from which one can draw three conclusions. Firstly, all variants of DUAL- Former perform consistently across three datasets, suggesting that the performance of DUALFormer is not sensitive to different backbones. In particular, the most significant performance difference is observed on the CiteSeer dataset, with the original DUALFormer that equips SGC showing just 1. 1.29% improvement over its variant that employs GCN. Secondly, DUAL and its vari- ants achieve significantly improved performance over the baseline GNNs. For example, on the Cora dataset, the DUALFormer enhances the performance of GCN by 3.89%, and the variant with APPNP boosts the performance of APPNP by 2.83%. This underscores the effectiveness of DUALFormer's design. Finally, the performance of variants that pair with perperrfonnng GNNs is generally high, indicating the potential for further improvements through integration with advanced GNNs.
Parameter Sensitivity Analysis. These experiments performed provide an intuitive under- standing of hyperparameter selection. Firstly, as depicted in Fig. [ which reports the performance variance for varying the dimension d,
achieve consistently stable performances across

---

Published as a conference paper at ICLR 2025
D GCC
DUAL w/ GCN
APPNP
DUALFormer w/ APPNP
DI SGC
DUALFooms
Accuracy
85
86.13
$4.52
24.55
Cora
CiteSeer
PubMed
Figure 4: Comparison DUAL Former with the employed backbone GNNs and the impact of dif- ferent backbone GNNs on the model performances. The legend DUALFormer w/ GCN represents the variant of DUALFormer that incorporates GCN as its GNN block.
{32, 64, 128, 256). In specific, the performance variation these datasets remains minimal, staying within a 2.5% margin. Therefore, DUALFormer has low sensitivity to the parameter d. In addition, DUALFormer does not always necessitate high value for the parameter d to function optimally; even a value as low as 64 is sufficient. Secondly, it can be observed from Fig. [6] that DUALFormer exhibits moderate sensitivity the number of layers for both GNN and SA. To be specific, within the range of {1, 2, 3, 4, 5, 6, 7), its performance tends to decline when the numher of layers exceeds 3. However, the Citeseer dataset, where this effect is most pronounced, the performance decrease did not exceed 3.1%. This illustrates the stability of DUALFormer.
85
Accuracy (%)
Accuracy(
Accuracy(%%
Cora CiteSeer PubMed
Cora
Cora
CiteSeer
PubMed
PubMed
75
32
# dimensions
64
128
256
#
layers
70
1
# layers
Figure 5: Performance varia- tions for varying dimension d.
(a) Depth of local GNN layers
(b) Depth of global SA layer
Figure 6: Impact of local GNN and global SA layer depths
5 CONCLUSIONS
This paper presents DUALFormer, straightforward and lightweight Graph Transformer (GT) archi- tecture that utilizes a muul-dimensional design to enable efficient and effective learning of graph rep- resentations. DUALFormer addresses two key issues in existing GTs: the scalability issue on large- scale graphs and the tradeoff dilemma between local and global information. Extensive experiments across eleven graph benchmark datasets demonstrate the superiority of DUALFormer compared to existing Graph Neural Networks (GNNs) and GTs. Nonetheless, still has scope for improvement. For example, 1) the universal GT architecture for homophilic and heterophilic graphs. Despite their global expressivity, GTs do not outperform well-designed GNNs on heterophilic graphs. Therefore, this is research- worthy topic. 2) designing edge-level GT architecture for edge-level tasks. Cur- rently, GT's focus on graph-level and node-level tasks, with limited exploration in edge-level tasks. This is open research question that merits further exploration.
ACKNOWLEDGMENTS
This work is supported in part by the National Natural Science Foundation of China (No. U22B2036, 62376088, 62276187, 62102413, 62272020). part by the Hebei Natural Science Foundation (No. F2024202047, F2024202068), in part by the National Science Fund for Distinguished Young Schol- arship (No. 62025602), in part by the Science Research Project of Hebei Education Department (BJK2024172), in part by the Guangxi Key Laboratory of Machine Vision and Intelligent Control (2023B03), in part by the Hebei Yanzhao Golden Platform Talent Gathering Programme Core Talent Project (Education Platform) (HJZD202509), in part by the Post Post-graduate's Innovation Fund Project of Hebei Province (CXZZBS2025036), in part by the XPLORER PRIZE, and in part by the Open Topics from the Lion Rock Labs of Cyberspace Security (under the project #LR..224 IRI.2409).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Smriti Bhagat. Graham Cormode, and S Muthukrishnan. Node classification in social networks. Social network data analytics, pp. 1 115-148, 2011.
Dexiong Chen, Leslie O' O'Bray, and Karsten M. Borgwardt. Structure-aware transformer for graph representation learning. ICML, volume 162, pp. 3469-3489, 2022.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs. In ICLR, 2023.
Jinsong Chen, Chang Liu, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormert: A tokenized graph transformer with neighborhood augmentation for node classification in large graphs. IEEE Transactions on Big Data, 2024a.
Jinsong Chen, Hanpeng Liu, John Hopcroft, and Kun He. Leveraging contrastive learning for enhanced node representations in tokenized graph transformers. In NeurlPS, 2024b.
Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expressivee graph trans- former linear time. In ICLR, 2024.
Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In NewrIPS, 2022.
Wenzheng Feng. Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs In NeurlPS, 2020.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. CoRR, abs/1903.02422 2019.
Anthony Gillioz, Jacky Casas, Elena Mugellini, and Omar Abou Khaled. Overview of the transformer- based models for nlp tasks. In FedCSIS, pp. 179-183. IEEE, 2020.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomás Mikolov. Learning word vectors for 157 languages. In LREC, 2018.
Yuhe Guo and Zhewei Wei. Graph neural networks with Icarnable and optimal polynomial bases. In ICML,, volume 202, pp. 12077-12097, 2023.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, pp. 1024-1034, 2017.
Dongchen Han, Xuran Pan, Yizeng Han, Shiji Song, and Gao Huang. Flatten transformer: Vision transformer using focused linear attention. In ICCV, pp. $938-5948, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, pp. 770-778. IEEE Computer Society, 2016.
Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks on graphs with cheby- shev approximation, revisited. In NeurlPS, 2022.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. NeurIPS, 2020.
Wei Ju, Zheng Fang, Yiyang Gu, Zequn Liu, Qingqing Long, Ziyue Qiao, Yifang Qin, Jianhao Shen, Fang Sun, Zhiping Xiao, et al. A comprehensive survey on deep graph representation learning. Neural Networks, pp. 106207, 2024.
11

---

Published as a conference paper at ICLR 2025
Leskovec Jure. Snap datasets: Stanford large network dataset collection. Retrieved December 2021 from http://ssap.. stanford. edu/data, 2014.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In ICML, volume 119, pp. 5156- 5165, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv, 2016.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
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, pp. 17375-17390, 2023.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. ArXiv e-prints, pp- a60iv-1607, 2016.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In ICLR, 2023.
Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In NeurIPS, 2022.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back- propagating errors. nature, 323(6088):533-5233 1986.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. A/ Mag., 29(3):93- 106, 2008.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, abs/18 1.05868, 2018.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In ICML,, volume 202, pp. 31613-31632, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. NIPS, pp. 5998-600 2008-608, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. CoRR, abs//110. 2017.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quant. Sei. Stud., 1(1):396 413, 2020.
Felix Wu, Amauri Souza, Tianyi Zhang. Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In ICML., pp. 6861-6871. PMLR, 2019.
Qitian WU, Wentao Zhao, Zenan Li, David P. Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. NeurIPS, 2022.
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. NeurIPS, 36, 2024.
Zhanghao Wu, Paras Jain, Matthew A. Wright, Azalia Mirhoseini, Joseph E. Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. In NeurIPS, pp. 13266-132777 2021.
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.
12

---

Published as a conference paper at ICLR 2025
Liang Yang, Chuan Wang, Junhua Gu, Xiaochun Cao, and Bingxin Niu. Why do attributes propagate in graph convolutional neural networks? In AAAI, pp. 1590-4598, 2021.
Hai-Cheng Yi, Zhu-Hong You, De-Shuang Huang, and Chee Keong Kwoh. Graph representation learning in bioinformatics: trends, methods and applications. Briefings in Bioinformatics, 23(1):
bbab340, 2022.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework, In WWW, pp. 1215-1226, 2021.
13

---

Published as a conference paper at ICLR 2025
A ALGORITHM DESCRIPTION
The specifics of the DUALFormer architecture are presented in Algorithm global attention module is elaborated in Algorithm
I whereas the innovative
Algorithm 1: PyTorch-style Code for DUAmerrmer
n: the number of nodes
m: the number edges
# f: the dimension of node attributes
# d: the dimension of hidden layers
111: the number of local graph convolution layers
1.2: the number of global attention layers
# x: input node attribute matrix with shape [n, f] edge_index: input graph structure with shape [2, m]
# alpha: combine rate of residual and output of each trans layer
convs: local graph convolution layers (e.g., SGConv from PyG)
# global trans: global attention layers (implemented in Code
residual Jist = -1
input projection layer x intput project(x) residual trans list.append(x)
global attention module
for transllaed in enumerate(global.tran trann):
trans layer(x)
X alpha * x + (1-alpha) * residual trans list[-1]
residual trans list.append(x)
local graph convolution module
residual_come _ostsslist residual.convs. convs wtt.sssss..pppped.....
for conv layer in enumerate(local.come
x convs(x. edge index)
residual conv list[-1]
residual cocituaaloooo__sssss_lee list..pdds))p))))
output output_project(x)
# negative log-likelihood loss calculation
y y-pred F.log softmax(output,, dim=l)
loss criterion(y preddtrainnnmante _ww.mmmak..i.. idx], ytttuetttain_mmat satpsaaaskiice idx))
B ADDITIONAL PRELIMINARIES
Typical Graph Neural Networks (GNNs). From the mentioned message-passiieee pasgiing-annnggggg paradigm, typical GNNs such as GCN Kipf & Welling (006)), SGC Wu et al. (2019) APPNP Klicpera al. (2019) employ the average function to implement the operations AGG(.) and COM(, ). that is,
GCN H H a (AH'W"),
(10)
SGC(A, H'):
H = -
(11)
APPNP(A. H H = AH' + H
(12)
14

---

Published as a conference paper at ICLR 2025
where a denotes the non- non-linear activation function (e.g., ReLU(-)). A
Im) represents the normalized adjcency matrix, where D is the diagonal degree matrix with d,, Σj D.j. These GNNs are employed in the proposed framework to capture the structure biases.
Graph Transformers (GTss. Given the node representations from the GNN, denoted as H, and the SA module, denoted Z, the final representations P produced according two strategies: (T) local-and-glote fusion and ( local-to-global fusion. These can be formulated as
! P å Combination (H, Z),
(13)
2 P A (H) H GNN(A,
(14)
where Combination(,) represents a combination function, such as P HH + (1 X)Z (i.e., the linear weighting in SGFormer, and À is parameter to balance these two terms).
C THEORETICAL PROOFS
To facilitate the proof, the node feature x. R is handled column vector. Assume that the node feature and label are the observations of random variables X Xx,.... x and Y respectively. The node features are assumed be mean-centered, namely, [X = O. Note that the variance of random vector is the sum of the variance of each dimension, which can be represented as the trace its covariance matrix. According to the law of total variance, the variance X can be decomposed into intra-class and inter-class variances, that is,
Var [X]
E [[V
[ar[
(15)
Intra class Variance
Inter class Variance
where Var[x|Y kt] stands for the variance of class i and E kj denotes the center of class k. The conditional expectation of node feature Xj w.r.t. the K classes can be represented as
cj [E ,E,,, K]} E R
(16)
The key component of the Global Attention (GA) Module (in Eq.
8) is XM, where the attention
matrix between features, i.e., M [m.y] softmax (Q) K
learnalee stochastic matrix.
vn
The node feature after GA is M x, R/, and thus the corresponding random variable is M X. Then, the conditional expectation of node feature after GA is é, = E; mije, The quality this attention score matrix between features M impacts this conditional expectation. Intuitively, good attention score matrix should contain large elements, whose indices correspond to attributes with similar conditional expectations, i.e., l|e, e,ll2
Theorem can be divided into the following two lemmas.
Lemma 1, The intra-class variance of M X is less than or equal to that of X. that is,
Va M X||| < X|]]]
(17)
Lemma 2. the learned attention score matrix good enough that cyllc S for any mij + 0, then the distance of conditional expectations before and after GA is also less than or equal to i.e
lēe -ell22 Se
(18)
and can be arbitrarily small with a proper M.
The proofs for these lemmas refer Sections
C.1 and C.2 respectively.
15

---

Published as a conference paper at ICLR 2025
C.I PROOF FOR LEMMA
1
Proof. By denoting a E I ;0; _ /Var [ = kj as the vector of intra-class variances, it can be
proved that Var M X|V = k] S Var[x| = k] as follows.
Var(M X = k]
(19)
TTrCCov(M (M T X k))
(20)
=Tr(M Cor(X|X K)M)
(21)
= =Ir(Cov(X] = })MM)
(22)
= - X, (MMM)) Dyy
(23)
Σ
VarlXX,| = kI Var[x = (MM)) D8s
(24)
(25)
'M σ
(26)
S 1
(27)
Σ Var[X, k]
(28)
Var X Y = k..
(29)
Note that the second inequality holds since the eigenvalues of M are no more than 1. According to this, Lemma I can be obtained as follows.
[[[ar [M X X|]
(30)
Σ
Pr(Y = Var = k]
(31)
Pr(Y = Var R.
(32)
E [Xr
(33)
L
C.2
PROOF FOR LEMMA 2
Proof.
1 - --1112 = e, Σ mijei
(34)
2
Σ mis miyles - ei)
(35)
S Σ m - -ill2
(36)
Σ mie= =E
(37)
The second inequality holds due to the Cauchy-Schward inequality. To show that there exists matrix M such that can be equal to 0, it need that M satisfying Σ, m,je; = ey. Given that the number of features significantly exceeds the number of classes, the number of variables in the linear system is larger than that of equations. Thus, there exists an infinite number of solutions. Therefore, e can be arbitrarily small with proper M.
16

---

Published as a conference paper at ICLR 2025
Algorithm 2: PyTorch--tyyle Code for Global Attention Layer
n: the number of nodes
# m: the number of edges
the dimension of node features
# x: node features matrix with dimension [n, d] the number of head
linear transformations
q = q. lins(x).reshaee(-1,, d. h)
[n, d, h] [n, d, h]
= Iiinssx).eshhapee-ll.. d. h)
v_.inns())reshaaee(1..dd h) [n, d, h]
calculate attention score matrix with size [d, d]
qk prrch.einsum""Img Idh + mdh", q. k)
qk torch. srrh..softmax(qk, dim=0)
trans_outha output = torch. wethheeennmmmmnni mdh - Idh", qk)
# take average of all heads
outpst = trans
[n, d]
D EXPERIMENTAL DETAILS
D.1 INTRODUCTION OF DATASETS
Table Statistics for the eleven graph benchmark datasets used in Section with seven employed for node classification tasks and the remaining four utilized for node property prediction tasks. For clarity, the "ogbn-" " prefix omitted for datasets including proteins, arxiv, and products.
Node Classification
Node Property Prediction
Cora CiteSeer PubMed Computers
Photo
CS Physies]
proteins
arxiv
products
pokec
# Nodes
2,708
3,327
19,717
13,752
7,650
18,333
34,493
132,534
169,343
2,449,029 1,632,803
# Edges
5,278
4,522
44,324
245,861
119,081
81,894
247.962
39,561,252
1,166,245 61,559,440 30,622,564
# Features
1,433
3,703
500
767
745
6,805
8,415
8
128
100
65
# Classes
7
6
3
10
15
2
40
47
2
# Metric
ACC1
ACC1
ACC ACC ACC1 ACC1 ACC ROC-AUCT
ACC1
ACC1
ACC
Tab. presents a compilation of statistical information for the eleven graph datasets (including Cora, CiteSeer, PubMed, Computers, Photo, CS, Physics, ogbn-proo proteppsoeins,, ogbn-arxiv, ogbn- ggbn-proddcts, and pokec). Moreover, Tab. 7 offers statistical data for three graph datasets (including Roman-Empire, Question, and bogg-pappers1000 10M). These datasets are described as follows:
Datasets for Node Classification.
Cora, CiteSeer, and PubMed Sen et al. (2008): They three citation networks. The nodes signify scientific publications, characterized by attributes such as abstracts, keywords, full- text content, and derived features like 0/1-valued word vector and TF/DD weighted word vector. The edges represent citation relationships. The node labels correspond to research areas topics.
CS and Physics Shchur et al. (2018): They are two co-author networks. The nodes represent authors, with edges representing oo-authorship relationships. The node attributes and labels indicate the keywords of the papers and the most active fields of study, respectively, for each author.
Computers and Photo Shchur et al, (2018): They are two co-purchase networks from Ama- zon. The nodes represent products available for sale, which characterized by attributes extracted from product reviews. The edges signify the co co-purchase relationships. The node labels denote product categories brands.
17

---

Published as a conference paper at ICLR 2025
Roman- Caanaa--mmpieelee Platonov et al. (2023): It is network constructed from the Roman Empire article on English Wikipedia. The nodes denote words in the article, with edges connect- ing sequential words those with syntactic dependencies. The node attributes stand for FastText word embeddings Grave et al. (2018), and the node labels indicate syntactic roles.
Platonov D et al. (2023): This is a question-and answering network. The nodes represent users, and the edges represent answer interactions between them. The node attributes the average FastText embeddings Grave et (2018) of the user's description, plus a binary feature for users without descriptions. The node labels denote whether users are active.
Datasets for Node Property Prediction.
gebn-proteins, ogbn-arxiv, boon-ppoouuts, and par-pppppesOMM... The are four large-scale graphs released recently by the Open Graph Benchmark (OGB) Hu et al. (2020). For the ogbn-produce dataset, nodes represent products available for sale on Amazon; edges sig- nify that the products are purchased together; node attributes are generated by extracting lag-of-words features from the product descriptions followed by the Principal Component Analysis (PCA) to reduce the dimension to 100. For the ogbn-proteins dataset, nodes denote individual proteins, and edges represent variety of biologically significant inter- actions, including physical associations and co-expression patterns. For the ogbn-arxiv dataset, nodes represent papers on arXiv; edges stand for those papers cite other papers; the attributes of each node represent 128-dimensional vector derived from averaging the embeddings of the words in the title and abstract of each paper. These word embeddings are generated using the skip-gram model over the MAG corpus Wang et al. (2020). For the ogbn-papers 100M dataset, nodes correspond to academic papers from arXiv, charac- terized by 128- 228-dimensional word embeddings as node attributes. Edges represent citation relationships between papers, and labels indicate the subject areas of the papers.
pokec Jure (2014): This is an online social network in Slovakia. The nodes stand for users, with edges indicating friendships between users. The node attributes represent personal information, such as gender, age, hobbies, interests, and education. The node labels denote the attribute labels of the nodes, such as gender or age.
Dataset Splitting, To ensure the credibility and reproducibility of the experiment, the dataset split- tings follow widely accepted schemes. To be specific, the split for the Cora, CiteSeer, and PubMed datasets follows the standard public strategies referenced in Kipf & Welling (2016), which allocate 20 nodes per class for training, 500 nodes for validation, and 1000 nodes for testing purposes. For the Computers, Photo, CS, and Physics datasets, the training. validation, and testing sets constitute 60%, 20%, and 20% of the data, respectively. For the four datasets sourced from OGB (i.e., ogbn- arxiv, ggonuproducts, ogbn-proteins, and ogbn-papers Coppers100M 100M), their standard public splits are utilized as referenced in Hu et al. (2020). For the pokec dataset, the partitioning follows Deng et al. (0024), with the training, validation, and testing sets distributed 50%, 25%, and 25% respectively. For the Bomann-Emiin and Questions datasets, the partitioning follows the scheme from Platonov et al. 2023), specifically, 50%/25%/22 /25% split for training, validation, and testing.
D.2 INTRODUCTION OF BASELINES
Graph Neural Networks (GNNs). The following outlines the GNN baselines used for comparison.
GCN & Welling 2016); This is a seminal graph convolution network that integrates node attributes with topology structure through localized, diffusion- based convolutions.
GAT Velickovic al. (2017): This is a groundbreaking graph attention network that incor- porates the popular attention mechanism into the graph convolution networks.
GraphSAGE Hamilton Hamiitoo et al. (2017): : This is a scalable variant of GCN, which updates node features by sampling neighbor nodes and applying learnable aggregation function.
APPNP Kliepera et al. (2019): : This is variant of GCN that mitigates over-smoothing by aggregating node features based on personalized PageRank.
SGC|Wu et al. (2019): This is a simplified version of GCN that iteratively applies multiple feature aggregations to learn node embeddings.
18

---

Published as a conference paper at ICLR 2025
ChebNetll He et al. (2022): This is spectral graph convolution network that enhances graph convolution through Chebyshev polynomial interpolation.
OptBasisGNN Guo Wei (2023): This spectral graph convolution network that com- putes the optimal polynomial basis for a given graph structure and graph signal.
Graph Transformers (GTs), The description of the GT baseline model is as follows.
GraphGPS Rampásek et al. 2022): This versatile GT architecture, which encompasses position encoding, local message passing mechanism, and self-attention mechanism.
:
NodeFormer Wu et al. (2022): This is a scalable GT architecture that utilizes kernelized
Gumbee--softmax operator for efficient and differentiable learning of graph structures.
NAGphormer Chen et al. (2023): This is scalable GT architecture, which utilizes multi- hop neighborhood aggregation to construct the token vectors for input sequences.
Exphormer Shirzad al. (2023): This sparse GT architecture that incorporates local attention, extended attention, and global attention through virtual nodes.
GOAT Kong et al. (2023): This is general GT architecture that utilizes the k-means-based dimensionality reduction linearize computational complexity and tackles the challenges of both homophilic and heterophilic graphs.
SGFormer Wu et al. (2024): This is a streamlined GT architecture that enables efficient information aggregation by only utilizing single-layer global attention and GNN network.
(024): This is polynomial expressive GT model with linear com- plexity, which leverages oocl-to-global attention scheme learn node representations.
Polynormer[ Deng et al.
CoBFormer Xing al. (2024): This is novel GT architecture that employs self-attention mechanisms within and across clusters to address the Ever-globalizing problem.
For the seven GNN baselines, i.e. GCN, GAT, GraphSAGE, APPNP. SGC, ChebNetII, and OptBa- sisGNN, we use the public library PyTorch Geometric (PyG) Fey & Lenssen (2019) and source code for their implementation. For the eight GT baselines, iee, GraphGPSS Nodmer NAGphormer, Exphormer, GOAT, SGFormer, Polynormer, and CoBFormer, we leverage their source codes. The sources are outlined as
GNNs: http:///hhhhhhcn.ooceoe/e/eereer
GraphGPS: http::///siiilooco//////ass///ss
NodeFormer: http://gthhu..commaiaaaaaaooooee
NAGphormer: h http://gtttiiiooomm//ttisssSS/SS
GOAT: http:///ggiiibbcco/////ooo/oooo
SGFormer:
Polynormer: http://gttaaaccommooo//////////a
CoBFormer:
https///gthhubccommmmmixx////f/f
D.3 EXPERIMENTAL SETUP
Hyper-parameters. The model employs semi-supervised learning framework, in which the model performances the validation set are leveraged to tune the hyperparameter selection. By default, the hyper-parameter are meticulously selected via a grid search strategy. For the node classification task, DUALFormer is trained utilizing Adam optimizer with the learning rate from {le-3, le 1e= and the weight decay rate from [1e-5,11
le -3) The number of the local graph convolution layers and global attention layers chosen from {1, 2, 3, 4, 5, 6, 7), and the optimal results corre- sponding to these selections are depicted in Fig. 6 The dimensions of hidden layers are selected from {32, 64, 128, 256) and the impacts are analyzed in Section 4.2 For each layer, the dropout
19

---

Published as a conference paper at ICLR 2025
rate is among the set {0.1, 0.5}. For the parameters unique to the attention layer: the number of heads is chosen from {2,4], 4), and a residual connection selected from {0.1, 0.3, 0.5}. In addition, Batch Normalization and Layer Normalization property prediction task on four large-scale graphs, a mini-batch training strategy is adopted. The value of for the residual connection is chosen from the set {0.1, 0.2, 0.3, 0.4, 0.5). The selection of whype--paaameteere follows the compared baselines CheeeinneeChennece et al. (2022); 22024. Refer to Tab. for the parameter selections associated with the respective outcomes.
utilized as appropriate. For the node
; Wu et al. (2024); Deng et al.
Table 5: Selected hyperparameters for DUALFormer.
Dataset
GNN Layers
SA Layers
INNGN
Ir
Hidden Dim
a
Cora
0.001
0.001
256
CiteSeer
3
0.001
0.01
256
0.1
PubMed
3
0,001
0.001
256
0.1
Computers
0.001
0.01
64
0.5
Photo
0.01
0.001
64
0.1
CS
0.001
0.001
256
0.1
Physics
0.001
0.001
256
0.3
ogbn pprotennss
1
0.001
0.001
32
0.5
oghn-arxiv
0.001
0.001
256
0.2
oghn-products
0.001
0.001
256
pokec
1
0.0005
0.0005
512
0.1
Configurations. All experiments are conducted on two Linux machines as below.
Table 6: Servers and environment.
Server
Server 2
Linux 5.15.0-82-
Linux 5.15.0-78-gemat
CPU
Intel(R) Core(TM) 17-1270011 CPU @ 3.6GHz
Intel(R) Xeon(R) Platinum 8360Y CPU @ 2.40GHz
GeForce RTX 4090
NVIDIA A800 80GB PCIe
ADDITIONAL EXPERIMENT RESULTS
E. FURTHER COMPARATIVE PERFORMANCE ANALYSIS
This subsection aims to evaluate the universality and scalability of the proposed DUALFormer. To this end, we compare DUALFormer with the latest state-of-the-ar GNN baselines, including Cheb- Netll and OptBasisGNN, and GT's with linear complexity, including NodeFormer, NAGphormer, and SGFormer, graphs (i.e., ogbn-papers papers I 100M, ogbn-arxiv, and pokec). The baselines are configured as per their original descriptions, and DUALFormer settings are consistent with those mentioned Section D.3 The experiment results are shown in Tab.
heterophilic graphs (i.e., Roman-Empire and Question) and three large-scale
Observing Tab. results in the following two conclusions. Firstly, compared the state-of-the-art GNNs, Le., ChebNetll, and OptBasisGNN, the baseline GTs perform worse in most datasets. This primarily attributed the inadequate integration of the GNN module with the SA module in these baselines. Secondly, in comparison to these baselines, the proposed DUALFormed achieves consis- tent performance advantages across all datasets, which demonstrates its universality and scalability. The performance boost stems from avoiding information redundancy between the two modules and effectively extracting discriminative information.
E.2 FURTHER ASSESSMENT EFFICIENCY SCALABILITY.
The running time and GPU memory usage for the three large-scale graphs detailed in Tab. To demonstrate the impact components in their architectures, particularly their self-attention mecha- nisms, on the scalability, the common hyper-parameters remain uniform across all models. It can be
20

---

Published as a conference paper at ICLR 2025
Table Accuracy in percentage (sda of node classification property prediction het- erophilic graphs and three large-scale graphs. Best and runner-up models are bolded and underlined, respectively. means out of memory or failing be finished within an acceptable time budget.
Roman- -amaree-
Question
ogbn- panp--ppessOOMM
ogbu-arxiv
pokec
# Nodes
22,662
48.921
111,059.956 1,615,685,872
169,343
1,632,803
Edges
32,927
153,540
1,166,243
30,622,564
# Attributes
300
301
128
128
65
# Classes
18
2
172
40
2
ChebNedI
74.6/40.a9
74.41
67.18 20.32
72.32
82.33
OptBasisGNN
73.82
67.22
72.27 #0.15
82.83
NodeFormer
20.79
74.48+1.88
67. 67.19
+1.00+1.00
NAGphormer
74.45=0.48
75.13
76,59+0.25 70. 00.55
SCFormer
70.91
77.06
77.00
66.01
72. 63
73.76
DUALFormer
+0.17
78.62=0.56
27.5920.28
82.97 73.21
+0.22
Table 8: Training time and GPU memory usage three large graphs. The best model is bolded and the runner-up underlined, respectively.
ogbn-arxiv
ogbn-products
pokec
Method
Time/Epoch(s)
MCm.(GB) Time/Epoch(s) Mem
Time/Epoch(s) Mem
GraphGPS
0.114
8.43
8.13
2.56
NodeFormer
0.089
2.88
4.43
0.76
1.46
0.75
NAGphormer
0,349
6.02
13.98
4.13
3.59
1.20
Exphormer
0,123
6,76
7.64
2.27
2.17
2.11
GOAT
2.021
1.42
17.33
1.18
6.76
1.12
SGFormer
0.033
0.98
3.70
0.50
1.25
0.44
Polynormer
0.047
4.08
4.17
1.36
I.54
1.22
CoBFermer 0.103
6.46
5.62
9.28
2.44
3.70
DUALFormer
0.034
1.17
3.03
0.54
1.06
0.46
observed that DUALFormer exhibits the shortest runtime and has the top-2 smallest memory usage compared to the other GTs. The result highlights the efficiency and scalability of DUALFormer.
In addition to the aforementioned results, we conduct specific comparison of the proposed DU- ALFormer with NAGphormer, which boasts the lowest training complexity of O(n). detailed in Tab. Note that while the preprocessing steps of NAGphormer, which involve obtaining structural encodings, computationally intensive, this cost be amortized over multiple training epochs. Therefore, justifies a comprehensive comparison of overall run times. Specifically, the experiment in Tab. 19] compares DUALFormer with NAGphormer in terms of performance, total running time, and GPU usage on three datasets: AMiner-CS Feng et al.] (2020), Reddit Hamilton et al. (2017), and Amazon2M. To ensure fair comparison, this experiment follows the setup of NAGphormer, with the exception that the data is divided into the commonly accepted ratio of 50% 23% 25% for training, validation, and testing, respectively.
Table 9: Accuracy (%), running time (s), and GPU memory usage (MB) on three large graphs. The best model is highlighted in bolded.
AMiner-CS
Reddit
Amazon2M
Acc(%) Time(s)
Mcm.(MB)
Acc(%)
Time(s) Mcm.(MB)
Acc(%)
Time(s)
Mcm.(MB)
NAGphormer 19.141...1 491.70
1672
95.9610.02
437.85
1710
90.7310.24
2, 629.466
1786
DUALFormer 69.30 10.27 223.43
1347
95.7
05.71.0.07
328.71
1364
91.17 19.15
11, 772.03
1380
From this table, the following three results can be observed. Firstly, on these three large-scale graphs, the proposed DUALFormer achieves comparable performance to the baseline NAGphormer, which emphasizes the scalability and effectiveness of DUALFormer. Secondly, the proposed DUALFormer has short total running times on these datasets except for Amazon2M and less GPU usage on three datasets compared NAGpormer. The advantage of DUAL.Foree primarily stems from its elimi-
21

---

Published as a conference paper at ICLR 2025
nation of the need for preprocessing to acquire structural encoding and storage, unlike NAGphormer, which requires such steps. The reason for the failure of DUALFormer on the Amazon2M is that this graph has the highest number of edges compared to the other two graphs, leading to extended com- putation times for the GNN module. Thus, this results in a longer overall processing time compared to NAGphormer without the GNN module, aligning with the results of the complexity analysis.
E.3 ADDITIONAL PARAMETER ANALYSIS
This experiment is conducted analyze the parameter sensitivity of the proposed DUALFormer hyperparameter a. The search range of this parameter is detailed in Section D.3] The experimental
results for seven small-scale and four large-scale graphs are shown in Tab. 10 and Tab. [I respec- tively. Firstly, from Tab. [0] it can be observed that DUALFormer is not sensitive to this parameter. Specifically, within the search range, the variation of classification accuracy does not exceed 0.8%. Furthermore, the same conclusion is supported by the data in Tab. 11 as the performance variations do not exceed 1%. Thus, there no need to concentrate excessively on the precise value.
Table 10: Performance variations for varying parameter a on six small-scale graphs.
Cora
CiteSeer
PubMed
Computers
Photo
CS
Physics
0.1
85 $5.88_0.1
74, 74.45.0.39
83.97 :0
23.09
96. 06.7440.09
95.62
97.37
0.3
85.20 25.20_o.12
73.6940.08
83.91 +0.07
93.1 93.14
95.38+0.00 43.00
97. 97.12=0003
0.5
85.35_0.05
74.06
83.89
96.39 13.16
95.52
97.39_0.02
Table 11: Performance variations for varying parameter a on four large-scale graphs
ogbn-proteins
ogbn-arxiv
ogbn-products
pokec
0.1
82.25
73.30
83.1940.77
82.97 10.43
82.26 22.26420.31
73.71
82.9940.81
82.50.0.46
0.3
82. 20.30
73.4920.13
83.7940.64
82.68
0.4
82.3240.67
73.4420.17
83.07
82.81
0.5
82.98
73.5220.22
83.91 1..11:0.20 23
81.9840.70
E.4 LOCAL AND GLOBAL EXPRESSIVITY
Localizing Property. The following theoretical analysis elucidates that in the proposed DUAL- Former, although the GNN module is set after the global attention module, it is capable of capturing the locality of the graph. Firstly, from the perspective of graph learning, many classical GNNs (e.g.. GCN and SGC) can be induced by optimizing the objective function Yang et al. 2021 ; Zhu et al. 22021. namely
1 Σ āe h. h arg min tr (H LH) H
(38)
2
where denotes the Laplacian matrix of the normalized adjacent matrix A, and H stands for the node features such as H = XW in GCN and H = X in SGC. This indicates that GNNs essentially learn local information through feature updates that are constrained by the graph topology.
From the above perspective, the GNN module in the proposed DUALFormer is equivalent to solving the above objective function with H Z, where Z denotes the node features obtained from the self- attention on the dimension regarding features. Thus, even as a post-processing technique, the GNN module can ensure localizing property by leveraging graph topology to constrain the feature updates.
Globalizing Property. The capability of capturing global information stems from the approximate T V. Note that the global information can be captured by the attention between nodes, i.e., softmax QK" ), in the previous GTs. Thus, ac- cording to the combination law for matrix multiplication, holds that (QK = Q(K V) and baftmax((Q' Q ((()) V). Therefore, this paper tends approximate the pensive node attention (QK" ) via efficient feature attention (K V) since softmax QK V ss éi (O()T V). Therefore, the proposed DUAL can capture global information.
equivalence between softmax QKT)) V and (Q))(K)
22

---

Published as a conference paper at ICLR 2025
F DISCUSSION ON ATTENTION BETWEEN FEATURES
Feature Attention vs. Node Attention. From the experiment results in Section 4 the proposed feature attention can lead to better efficiency and performance compared to node attention. This subsection seeks to offer insights into the efficiency and effectiveness of feature attention by com- paring with typical node attention.
Firstly, the high efficiency of the feature attention stems from the fact that the dimension of feature vectors significantly smaller than the number of nodes. This has been justified through complexity analysis in Section 3.3 Secondly, the proposed feature attention can result in better model perfor- mance than the node attention. This is because alleviates the conflict between limited training data and the need to model large-scale, complex relations between entries (nodes). On the one hand, the node attention in the previous GTs needs the model parameters to accurately trained to model the relations of n²² pairs. Unfortunately, the training data on graphs is often too limited to train them accurately. On the other hand, the feature attention in the proposed DUALFormer only requires to model the relations of f² pairs, which is much less than n pairs. Hence, the training requirement of the model parameters is not to be as high as in the node attention, and the training data with the same scale is sufficient. Therefore, the performance can be improved by easing the conflict between limited training data and modeling relations.
A specific case. Let consider specific case where the feature is one-dimensional. In this sce- nario, neither the node attention nor the proposed feature attention can gather information. Firstly, in the case of one-dimensional feature, Vo in Eq. simplifie V.a, aa where is scalar and V E R". Thus, the proposed feature attention is unable to gather information. Furthermore, for the one-dimensional feature, ((Q))(() in the node attention module reduces to rank-1 ma- trix, whose rows only differ from each other by scalar factor since Φ(Q) is column vector and <(K)T is row vector. Thus, the aggregation patternsscooffccients for different nodes, represented by the rows of 6(Q))(K) only differ by the scalar factor. As result, (KQ)((K) V degrades to the same aggregation pattern/coefficient for different nodes. Since the essence of aggregation is the different aggregation patterns/coeffciients for different nodes, the node attention loses this char- acteristic for one-dimensional feature. Therefore, in this special case, neither the node attention gathers information, like the feature attention. This case demonstrates the importance of multiple is further justified by exploring the
features for the transformer. Thus, the proposed correlation among multiple features with additional transformer.
23


Reviews:
[{"review_id": "EKcOPCg0ZX", "reviewer": "Reviewer_YCph", "summary": "This paper introduces DUALFormer, a novel Graph Transformer model designed to address scalability challenges and improve local-global information fusion. The approach is both simple and theoretically grounded. Extensive experiments demonstrate DUALFormer’s effectiveness, scalability, and robustness.", "questions": "N.A.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper is well-motivated.\n2. The proposed method is simple and effective.\n3. The inclusion of theoretical analysis strengthens the work.\n4. Extensive experiments show the effectiveness, scalability and robustness.\n5. This paper is easy to follow.", "weaknesses": "1. The proposed method can be interpreted as \"attention on attributes\". I wonder how is it different from the standard self attention. Especially why it can perform better on node classification? And when it is expected to perform better and when not?\n2. Can you provide further analysis, such as case studies, to further explain the semantic meanings of the \"attention on attributes\"?\n3. Can you provide further analysis and empirical studies to show that the GNNs after the graph Transform can indeed learn the localities in graphs?\n\nI will raise my score if my concerns are properly addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yAoYb2dig7", "reviewer": "Reviewer_CPJ4", "summary": "To address the scalability limitations of graph transformers (GTs) and the challenge of balancing local and global information, this paper introduces DualFormer, a novel GT architecture. DualFormer calculates global attention along the feature dimension, enabling the model to perform effectively and efficiently on large graphs while maintaining strong performance.", "questions": "- The first question concerns the reasonableness of applying softmax to the global correlations between features.\n\n  - In standard self-attention, $ \\mathbf{O} = \\exp(\\text{sim}(\\mathbf{Q}, \\mathbf{K}))\\mathbf{V} $ (Eq. 6).\n  - Through linearized attention, $ \\mathbf{O} = \\phi(\\mathbf{Q}) \\phi(\\mathbf{K})^\\top \\mathbf{V} $ (Eq. 11), where each element in $ \\phi(\\mathbf{Q}) \\phi(\\mathbf{K})^\\top $ is non-negative, representing attention weights (global dependencies between nodes).\n  - By the commutative property of matrix multiplication, $ \\mathbf{O} = \\phi(\\mathbf{Q}) (\\phi(\\mathbf{K})^\\top \\mathbf{V}) $, so we can interpret $ (\\phi(\\mathbf{K})^\\top \\mathbf{V}) $ as a correlation matrix (with elements that can be positive or negative).\n\n  However, in Eq. 13, $ \\mathbf{V} \\text{softmax}(\\mathbf{Q}^\\top \\mathbf{K}) $, i.e., $ \\mathbf{Q} \\text{softmax}(\\mathbf{K}^\\top \\mathbf{V}) $, differs from $ \\phi(\\mathbf{Q}) (\\phi(\\mathbf{K})^\\top \\mathbf{V}) $ because elements in $\\text{softmax}(\\mathbf{K}^\\top \\mathbf{V}) $ are all non-negative, unlike those in $ (\\phi(\\mathbf{K})^\\top \\mathbf{V})$. Could you clarify these differences and explain why it is reasonable to replace $ \\phi(\\mathbf{Q}) (\\phi(\\mathbf{K})^\\top \\mathbf{V}) $ with $ \\mathbf{Q} \\text{softmax}(\\mathbf{K}^\\top \\mathbf{V}) $?\n\n- The second question pertains to the interpretation of the proposed global attention. The method appears to aggregate information along the feature dimension, unlike previous approaches that gather global information across all or most nodes in a graph. For a one-dimensional feature, $ \\mathbf{V}  \\text{softmax}(\\mathbf{Q} \\mathbf{K}^T) $ in Eq. 13 reduces to $ \\mathbf{V} \\cdot \\alpha $, where $ \\alpha $ is a scalar and $ \\mathbf{V} \\in \\mathbb{R}^{n} $. How can this be understood as gathering information from a global perspective?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The writing is generally clear and accessible, making the paper readable and easy to follow.\n- The proposed method is both understandable and implementable, yet effective. It performs well on several datasets.\n- The paper includes diverse experimental analyses, such as node classification, node property prediction, ablation studies, and parameter sensitivity analyses. Furthermore, the authors offer theoretical guarantees to support the method.", "weaknesses": "- The motivation for the study is not fully convincing. Further details are provided in the questions below.\n- Since the paper emphasizes the method’s scalability, additional experiments on larger graphs would reinforce this claim. Suggested datasets include *Roman-Empire*, *Question[1]*, *Wiki*, and *ogbn-papers100M*. Moreover, the GNN baselines in Tables 2 and 3 are outdated, which may reduce the persuasiveness of the results. For instance, the statement, “Most GTs consistently show superior performance over GNNs across all datasets” (line 451), would be more convincing if compared with recent GNN baselines, such as *ChebNetII[2]* and *OptBasis[3]*, to present a more comprehensive evaluation.\n- Minor Issues: There are a few typographical errors, such as \"abov\" (line 182). Consistent notation throughout the paper is also preferable. For instance, in line 168, there is a \"$\\times$\" symbol between a scalar and a matrix, but not in line 216. Additionally, line 191 includes a \"$\\cdot$\" between matrices, whereas line 167 does not.\n\n[1] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In ICLR 2023.\n\n[2] Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited. In NeurIPS 2022.\n\n[3] Graph Neural Networks with Learnable and Optimal Polynomial Bases. In ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rTOIrA7lD9", "reviewer": "Reviewer_Q319", "summary": "This paper introduces DUALFormer, a graph transformer that tackles the challenges of the scalability and trade-off between local and global expressivity faced by current models. The motivation is to model the global dependencies among nodes by approximately characterizing the correlations between features. DUALFormer adopts a simple, intuitive design that includes local graph convolutional networks operating on the node dimension and a global self-attention mechanism operating on the feature dimension. The effectiveness and efficiency of the proposed DUALFormer are demonstrated in experimental evaluations across node classification and node property prediction tasks.", "questions": "Update after carefully reviewing the authors' responses: no further concerns", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1) The motivation for the dual design of local and global modules in this paper is clear and interesting.\n2) The model DUALFormer is simple and efficient with a solid theoretical foundation. \n3) The paper offers extensive experimental validation across various datasets. \n4) The paper is well-organized and easy to read.", "weaknesses": "1) The paper has some minor errors that need fixing. For example, Table 2 misses the mean value for the GraphGPS model on the Citeseer dataset. \n2) To enhance readability, Equation 13 should be split into two or three equations. \n3) The model DUALFormer places the GNN layers, such as the SGC layers, after the attention layers. What is the rationale behind this design? Is it possible to reverse this order? \n4) Figure 4 shows that the model utilizing APPNP outperforms the one using SGC in the Cora and Pubmed datasets. What accounts for this performance difference?\n5) The effect of certain hyper-parameters, such as the parameter $\\alpha$ in Equation 13, on performance has yet to be unverified. \n6) The paper does not mention any plans to open-source the code.\n\n* Update after carefully reviewing the authors' responses: The authors have provided detailed and thoughtful replies that effectively address most of my concerns. At this stage, I am pleased to increase my evaluation of the paper to '8: accept, good paper'.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Cv07xJPvIa", "reviewer": "Reviewer_GjDD", "summary": "This paper develop a new architecture based on GNNs and modified Transformers. The authors conduct expensive experiments as well as theoretical analysis to show the effectiveness of the proposed method.", "questions": "I have the following questions:\n1.  As the authors claim in Eq. 13, the proposed method only captures the feature-to-feature correlations. In my opinion, it is not the global information on the graph since it is unable to capture the relations between nodes. Why do authors claim the proposed method can capture the global information on the graph?\n2.  According to the paper, the efficiency is the most important contribution of the proposed method. I think the authors express this point in a wrong way. Firstly, the authors claim that the computational complexity of the proposed method is $O(n)$ which is obviously wrong. Based on Eq. 14, the calculation involves the adjacency matrix. Hence, the computational complexity of this part is $O(E)$ and it is cannot be ignored since $|E|>|N|$ （even $|E|>>|N|$ on some graphs). Then, the authors only compare the time cost of each epoch to demonstrate the efficiency which is not reasonable. I think the total training time cost is the most important metric to demonstrate the efficiency of a method. So, the authors should report the overall training cost of each method for efficiency study, especially on large-scale graphs.  Maybe authors can refer to the settings in NAGphormer. For instance, can the proposed method achieve more efficient and more powerful performance than NAGphormer on Aminer, Reddit and Amazon2M?\n3.  As shown in Section 4.2,  DUALFormer relies on the sampling strategy to perform on large-scale graphs, just like advanced linear graph Transformers. Hence, I think the GPU memory comparison is questionable since it is largely related to the batchsize. Do authors set the same batch for each method?\n4.  The analysis of the $\\alpha$ is missing. According to Table 5, the performance of DUALFormer could be sensitive to the value of $\\alpha$. So, the parameter analysis of $\\alpha$ should be added into the experiment section.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.  This paper is easy to follow.\n2.  The authors provide the theoretical analysis.\n3.  The results on various datasets seem to be promising.", "weaknesses": "1.  The comparison of efficiency study seems to be not reasonable.\n2.  The key contributions of the proposed method are not clear.\n3.  The complexity analysis of the proposed method seems to be wrong.&#x20;", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)