Primphormer: Efficient Graph Transformers with Primal Representations
Authors: Mingzhen He
Ruikai Yang
Hanling Tian
Youmei Qiu
Xiaolin Huang
Venue: ICML 2025 poster (2025)
Keywords: Efficient graph Transformer
self-attention mechanisms
primal representation
asymmetry
kernel methods.
Primary area: deep_learning->attention_mechanisms
TL;DR: We propose a primal-dual framework for efficient graph Transformers which reduces the quadratic complexity.

Abstract: Graph Transformers (GTs) have emerged as a promising approach for graph representation learning. Despite their successes, the quadratic complexity of GTs limits scalability on large graphs due to their pair-wise computations. To fundamentally reduce the computational burden of GTs, we propose a primal-dual framework that interprets the self-attention mechanism on graphs as a dual representation. Based on this framework, we develop Primphormer, an efficient GT that leverages a primal representation with linear complexity. 
Theoretical analysis reveals that Primphormer serves as a universal approximator for functions on both sequences and graphs, while also retaining its expressive power for distinguishing non-isomorphic graphs.
Extensive experiments on various graph benchmarks demonstrate that Primphormer achieves competitive empirical results while maintaining a more user-friendly memory and computational costs.

Primphormer: Efficient Graph Transformers with Primal Representations
Mingzhen He! Ruikai Yang'
Hanling Tian
Youmei Qiu Xiaolin Huang'
Abstract
which allow each node globally attend all other nodes is proposed to enable the learning of long-rann raage dependen- cies within the graph (Rampasek et al.) [0022 Chen et al.] 2022). While GTs are promising approach, they suffer from a significant drawhack: their quadratic complexity caused by pair-wise computations in self-attention mech- anisms, which limits their practical applicability.
Graph Transformers (GTs) have emerged as promising approach for graph representation learning. Despite their successes, the quadratic complexity of GTs limits scalability on large graphs due to their pair-wise computations. To fundamentally reduce the computational burden of GT's, we propose primal-dual framework that interprets the self-attention mechanism on graphs as dual representation. Based on this frame- work, we develop Primphormer, an efficient GT that leverages a primal representation with lin- ear complexity. Theoretical analysis reveals that Primphormer serves as a universal approxima- tor for functions on both sequences and graphs, while also retaining its expressive power for distinguishing non-isomorphic graphs. Exten- sive experiments on various graph benchmarks demonstrate that Primphormer achieves compet- itive empirical results while maintaining a more user-friendly memory and computational costs.
The key to reducing the quadratic complexity is to com- putationally efficient attention mechanisms. Linear atten- tions like Performer (Choromanski et al. 2021) and Big- Bird (Zaheer et al. 2020) have been integrated into GTs. However, they need to introduce additional computational overhead, which becomes the dominating source com- putation for medium-sized graphs (Rampasek al., (022). An alternative approach is sparse attention. [Shirzad et al. (2023) introduced Exphormer whose efficiency benefits from the sparsity of graphs. However, the complexity in- creases to quadratic with the number of nodes as graphs become denser, thereby still limiting its scalability.
To fundamentally enhance the scalability of GT's eru- cial avoid pair-wise computations, prompting us con- sider the primal-dual relationship in kernel machines. Ex- amples of models leveraging this relationship include the support vector machine (Cortes & Vapnik 1995). the least squares support vector machine (Suykens & Vandewalle 1999), and the kernel principal component analysis (Mika ct al. 1999). The primal-dual relationship represents pair- wise and symmetric similarity in duality as an inner product of feature mappings in the primal space. By solving opti- mization problems in the primal space with these feature mappings, quadratic complexity can be avoided.
1. Introduction
Graph representation learning has been successfully ap- plied in various fields, including social network analysis (Li et al.] 2023). traffic prediction (Dong al.] 2003). drug discovery (Liu al. 2023), and more. Much of the research in graph representation learning has focused Message Passing Neural Networks (MPNNs) which rely on local message-passinng passing mechanisms. Although MPNNs have emerged as a powerful approach to short-range tasks that require information exchange among nodes neigh- borhoods, MPNNs face inherent limitations such as over- smoothing (guyen et al. 2023). over-squashing (Gialdoo ett al. 2023 in long-range tasks (Dwivedi et al. 20226).
When constructing the primal representation of the self- attention mechanism, we encounter an essential problem that attention scores are inherently asymmetric, violating Mercer's condition (Mercer, 1909). which causes the clas- sical primal-dual discussion fail. Recent research on primal-dual relationships has sought to explore methods for accommodating asymmetry in kernel machines (Suykens) 2016 He et al. [203a Chen et al.] (023). Chen et al.
To overcome the limitations, Graph Transformers (GTs)
'Institute of Image Processing and Pattern Recognition, Shanghai Jiao Tong University, Shanghai, China. Correspon- dence to: Xiaolin Huang <xiaolinhuang sjtu.edu.cn>.
2023 interpreted the primal-dual relationship of the self- attention on sequences through asymmetric kernel singular value decomposition. This approach collects data informa- tion through uniformly sampling the sequence under an in-
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Primphormer: Efficient Graph Transformers with Primal Representations
ductive biay assumption that sequences are ordered. How- ever, this assumption does not hold for graphs, as the struc- ture of graph is defined by its edges, and the arrangement or ordering of nodes is not explicitly specified, leaving a question about discussing the primal-dual relationship of the self-attention on graphs.
try of G. Its directed edges denote directed interaction or similarity between two nodes i, computed by the inner product in the attention mechanism. Mathematically, we define the attention mechanism ATTN as follows,
Our contributions. We propose novel primal representa- tion for GTs, named Primphormer This method supports asymmetry in self-attention on graphs by introducing asymmetric kernel trick. It avoids costly pair-wise compu- tations and storage overhead without introducing additional heavy computational burden. The primal-dual analysis re- veals that Primphormer can leverage graph information to adaptively adjust the output basis, thereby potentially en- hancing the model's flexibility. Since Primphormer is new architecture for GTs, are also interested in its the- oretical properties. To explore this, we demonstrate that Primphormer serves as a universal approximator for arbi- trary continuous functions on a compact domain and that it preserves expressive power in terms of distinguishing non-isomorphic graphs. Through extensive experimental evaluations on various graph benchmarks, we show that Primphormer achieves competitive results while maintain- ing more user-friendly memory and computational costs.
<()x,,))) = N
(2.1)
0, = m(aa)) E -
where k(æ,, Dzj is the attention score from node i to node j and o, is the attention output of vertex i. o is an activation function. We denote q(x) == W2 k(x))= = Wg and v(x) == W. for queries, keys, and values, respectively, and Wq, WE, W. E RRmx are learnable weights. The Transformer block T (Vaswani et al. 2017) is defined by T(x) = FFN (X + ATTN(X)) where X and FFN are token embeddings and feed-forward layer, respectively.
It is worth noting that the attention score is computed for every pair of nodes, leading to memory and computational complexity of ((2)). which becomes prohibitively expen- sive for large-scale graphs. Many computationally efficient attention mechanisms are proposed to tackle this issue (Za- Choromanski et al.. 202 Zhuang al.
heer al. 2020 Shirzad et al.) 2023). Exphormer (Shirzad et al. sparse GT, is specifically designed for graphs, which facilitates information exchange across real and ex- pander edges. However, Exphormer loses its efficiency when dealing with denser graphs, as its computational complexity increases O(N2) again with the growth in graph density, significantly limiting its scalability.
2. Methods
2023
2023
Notations. We consider a labeled graph G = EV with the node and edge sets V, E and the labeling function l. [ N, F M denote the numbers of nodes and edges. [N] = [1,...,, ,N). AG) (0, 1) N*N denotes the adjacency matrix where Au,, = iff {u, r) E E. We take b, b, B to be a scalar, vector. and a matrix. The in- ner product of two vectors is written as (,, The infinite norm of functions is written as || Il denotes the set of real numbers. R.,, denotes the set of real and positive numbers. (S) denotes the trace of a square matrix S. (B) denotes the vectorization of the matrix B, formed by stacking the columns of B into a single column vec- tor. @ denotes the Kronecker product. 1 and O denote vectors with all 1 and O, respectively. Denote [a, b, c] as column concatenation and ba; as row concatenation. X == [ar..... xx] E B is the embedding matrix for nodes where x; gd is the embedding of the i-th node. For two graphs G and G", a graph isomorphism is bijection sp(-) : VG + Vo such that {i,j} E EG iff (1)()), +()}} E Eg. Two graphs G and G' are isomorphic if there is a graph isomorphism p(-): Va + Ve.
2.2. Primal-dual relationships in kernel machines
Such quadratic complexity also exists in kernel machines, where Mercer's kernels preserve pair-wise similarities in the dual space (Mercer 1909). For large-scale problems, it is more practical to contemplate feature representation in the primal space to circumvent quadratic complexity (Fan) et al.] 2008). One can refer to the representer thcorem (Kimeldorf Wahba 197I), which delineates the optimal solution between the primal and dual spaces,
g(x.)) = E, ajk(zn 2;) =
E, as a,(o(a))
= EE, ()b()) (( == (w, ((x))),
2.1. A Attention mechanism on graphs
(2.2)
where aj E RR and w E R2 are variables in the dual and primal spaces. x(-) Rd + R" is the associated feature mapping of the kernel k. For vector dual variables a,, we can apply (2.2) to each dimension of a, E TR.. Mathemat-
An attention mechanism on a graph G treats nodes V as tokens and is modeled by fully connected, directed graph with the positional encoding (PE) that encodes the geome-
2

---

Primphormer: Efficient Graph Transformers with Primal Representations
ically,
where + == (ee W r 6, r is the parameter set. We, W, E R e R., N₂ < N is small number, and A E I4x represents diagonal regulariza- tion coefficient matrix. (g(+), Φx(-) R - I" corre- spond to the feature maps of queries and keys, respectively. fx E R*XN. N. is a data-dependent projection defined as fx := F+ 1 N. It serves as a virtual node that aggregates information from all nodes in the graph. Here, F RexN, and B E Read are learnable weights.
g(x;)) = Σ, (x)) = =,, vec (a)o(a;)) ((xx))
(a)
(b(a,) 0(m.)) = (W, ((x:)),
(2.3)
where (a) comes from the vectorization property of the Kronecker product (Graham 2018 and W R The output 9 in the dual space and the attention output share similar formulation, indicating that the attention mecha- nism could potentially be represented in the primal space.
The objective function J introduces the variational prin- ciple, as discussed by [Suykens| (2016), which reproduces asymmetric kernels in the dual space. We propose new pri- mal representations for graph data, i.c., E, e in the con- straints. The global aggregation fx preserves permutation equivariance. Then, we incorporate the global information into the projection weights We and Wr, rather than into the feature mappings Φ, and Φx. as done by Chen et al. (2023), forming data-adaptive basis in the dual space. The duality of the optimization problem (2.5) is given as follows,
2.3. Primphormer
However, unique characteristic of the attention score is their asymmetry, denoted as x(2,, y) F k(y, which vi- olates the Mercer condition. Several works studied this is- sue and provided a mathematical foundation for allowing asymmetry as follows,
Definition 2.1 (Asymmetric kernel trick, (Wright & Gon-
Theorem 2.2 (Duality). The dual problem of the optimiza- tion (2.5 under the Karush-Kuhn- Sahn-Tucker (KKT) conditions is the following linear system,
zalez, 2021 Lin et al. 2022 He et al. 2023a Chen et al.) 2023 ). An asymmetric kernel trick from reproducing ker- nel Banach spaces (RKBS) with the associated kernel fune- tion k(..)) X' x Z - R can be defined by the inner product of two real measurable feature maps from a pair of
KH, = H.E,
(2.6)
K H. = H,,
Banach spaces Bx, B2 on X, 2:
which collects the solutions corresponding to the non- zero entries in A such that Σ : A-1 He == Ihe.....,hee] IT Nx8, and H, := [hr....... h,x! IT R. are dual variables. K corresponds to the attention score, induced by Kij == (a)( &2 (b(()))). The proofs, Lagrangian, and KKT are provided in Appendix C.1
<(x, z) (z) dz) (2)),
(2.4)
where a E &b E Bx, = E sn E BB.
Based on 2.3 and Definition 2.1 an intuitive idea is to rep- resent the attention output in the primal space. Chen et al.) (2023) introduced primal representation of the attention output specifically for sequence data. It collected sequence information by uniformly sampling tokens and formed a adtatide weight in the dual space. However, this ap- proach has two main weaknesses. First, unlike sequences, nodes in a graph are unordered, meaning the sampling op- eration may break permutation equivariance, i.e., any per- mutation of the nodes could result in different output. Second, the data-adaptive weight may not be sufficiently flexible, potentially limiting the model's flexibility.
Primal-dual relationship. The KKT conditions yields a fact that the optimized projections W, and W. in the primal space are composed of all the tokens,
We = Σ hrr ,T
(2.7)
W = 02
By applying (2.7) to the projection scores e, r, we can for- mulate them in the following two ways: (a) the primal rep- resentation, and (b) the dual representation the standard self-attention,
To address this, we collect graph information by introduc- ing a virtual node (Cai et al., 2023) that aggregates global information. We then formulate a new optimization prob- lem, which forms data-adaptive basis in the dual space:
e((x)= = fx W. (x), (r(x)= fx W. W.
Primal:
1 N TTA
e(x) > .V
j=1 h, Ri (z, 2y),
(2.8)
min J e
Σ e
Ae;
+
2
Σ
Ar, TY(W. W,)
Dual:
5=1
r(x) = -'" Tee k( x)),
N
s.t. e = fx W. 6y (mx;), E [N].
r3 = fx (2 E [N],
where Fx = fx contains the global information, and
(2.5)
h = Fxhr, he, = Fxhe, are the so-called data-
3

---

Primphormer: Efficient Graph Transformers with Primal Representations
Output from previous layer
MPNN
ATTN
Φ (x)
(x)
(x)
(x)
fx
(xx
Katta (0,(0))+4(0))
(x)
fxW,0x(0
FFN
Katt
0 Wc(e:r]
Output (a)
Output (b)
Output (c)
Figure Illustrations of the architectures one layer. (a) The GPS architecture. (b) The standard self-attention archi- tecture. The attention score kattn involves pair-wise computations. (c) Primphormer eliminates the need for pair-wise
computations by introducing the primal representation, resulting in a new computationally efficient GT.
adaptive basis. In the primal space, we integrate token in- formation into the projection weights W, and W. (2.7). representing the self-attention without pair-wise computa- tions. The global aggregation fx inside serves as a vir- tual node, intended to introduce graph information to each node. Correspondingly, the attention score is computed us- ing an asymmetric kernel trick, denoted as k(æ;, 20-) := (2,(),, (b(xx) (Iz)), )), and values are the data-adaptive basis hyy he,, forming the self-attention in the dual space.
sible. The final output is obtained by concatenating two projection scores o(x) == (e(z)):((z)) To align with the user-dependent dimension da. a compatibility matrix W. E x2 can be further applied to the output score.
In the implementation of Primphormer, our goal to reach the KKT points. Theorem 2.2 establishes that when the KKT conditions are met, the dual representation of Prim- phormer aligns with the standard self-attention formula- tion. However, solving the linear system (2.6) in the dual space introduces a cubic complexity. To efficiently ap- proach the KKT points, we introduce the following lemma,
In contrast, Chen et al. (023)) sampled sequence informa- tion gx C' sub where C' E IRpd and Xsub is uni- formly sampled from X, which is integrated into feature mappings, forming a data-adaptive weight R(2; my) =
Lemma 2.3 (Zero-valued objective with stationary solu- tions). The solutions of He, H,, E in the dual space (2.6) lead a zero-valued objective J in the primal space 2.5
( (x;(,(;;), g cbu (zx)) and a self-attention output ō(x)) = E, h)ū((, 2,). It is easy to check that Ô is incapable of adjusting the space that {hy} spans, limiting its flexibil- ity. Our data-adaptive basis directly adjusts the output basis thus potentially enhancing the model's flexibility.
Implementation. The essence of Lemma 2.3 lies in the necessity for the primal objective value to be zero under the KKT conditions, suggesting an alternative optimization approach instead of solving the dual problem. Therefore, we implement Primphormer by jointly minimizing an ad- ditional loss towards zero as follows,
Model architecture. We replace the self-attention mod- ule in the Transformer block with our primal representa- tion (2.3) and name the resulting method Primphormer, de- fined as Tru == FFN (X + Prim(X)) X)). For a fair compar- ison, we integrate Primphormer into GPS, powerful GT architecture that combines MPNN and Transformer blocks RRampasek et al.] 2022). The architectures are illustrated in Fig. with algorithms provided in Appendix D
Lrask + 1 E, Jr.
(2.9)
where E R4, is regularization coefficient, Leask is the task-oriented loss and the final term sums up the objec- tive loss (.5) across layer l. Through regularization of this additional loss, the self-attention mechanism can be ef- fectively represented in the primal space upon achieving zero-valued objective.
Complexity analysis. The primal representation is a more user-friendly approach in terms of both time and memory costs. The dual representation requires O(N2s) time com- plexity and O Ns) memory complexity. In con- trast, the primal representation only requires (Npp) time complexity and (22,, s. + 2Np) memory complexity with N, < N making an efficient self-attention mechanism fea-
3. Theoretical Results
In this section, we provide the main theorems of Prim- phormer. The proof details can be found in Appendix C
4

---

Primphormer: Efficient Graph Transformers with Primal Representations
3.1. Universal approximation
sequence of ordered pairs ((i,)), ozy)) where i J. i E [N] and an edge indicator dij- It is evident that any permutation on these pairs describes the same graph. Con- sidering the set of functions f IR (N--1)) 7 R (x(-1)
By substituting the self-attention layer with our primal rep- resentation, obtain new network architecture. Sub- sequently, the first question that intrigues concerns the universal approximation property, delving into which fune- tions can be uniformly approximated utilizing our network.
with permutation equivariance, Theorem 3.2 asserts that the function f can be approximated with arbitrary accu- racy by Primphormer on edge input. Similarly, the node Primphormer takes an identity matrix as input and the padded adjacency matrix positional encoding which can be interpreted one-hot encoding of each node's neighbors. Considering the set of continuous functions f 1] - N Theorem 3.3 states that f can be approximated as closely as desired by an appropriate Prim- phormer on node inputs. These ensure that Primphormer universal approximator for functions on graphs.
Here, we demonstrate that Primphormer allows universal approximation for continuous functions on both sequences and graphs. The proofs rely on a mild assumption: let fea- ture spaces be X, C TRd and let X' be a compact set. We first introduce the concept of permutation equivariance and then show that Primphormer is universal approximator.
Definition 3.1 (Permutation equivariance, (Hutter 2020: Alberti et al. 2023)). ) A continuous sequence-to- geuuence-o-sequenee to-sequence function f : X + y is equivariant to the order of ele-
ments in a sequence for each permutation π [M] - [N].
3.2. Expressivity
Beyond approximation theory, the second question per- tains expressivity. We demonstrate that Primphormer is powerful as the 1-dimensional Weisfeiler-Lehman al- gorithm (1-WL) (Weisteiler & Leman 1968, Xu et al. 2019 Morris et al. 2019) in terms of distinguishing non- isomorphic graphs as follows,
f (( ([=+(I):" ". ( [x)]) = .") (((N)
where X x1,"" x. a sequence of N tokens. De- note f E Fay (X, if conforms to this definition.
We are now ready to state the universal approxima- tion property of Primphormer on permutation equivariant sereencet--sequenee functions.
Theorem 3.4. Let G = (V, E) be a labeled graph with N nodes, and node feature matrix (() == H E RaxN consistent with the label f. Then, for all iterations 2 O. there exists a parameterization of Primphormer such that
Theorem 3.2. For any function f FN (X,)) and for each 0 there exists Primphormer Tpu such that
sup - -TPi(X)lls <. XeX
(3.1)
()()) CC)) = (x) xx)) (x) (w),
(3.3)
for all nodes v, E V, where C V N is the coloring function of the 1-WL test at t-th iteration.
Next, we develop the theorem for any continuous sequence- to-sequence function, stating that with a positional encod- ing E E p Primphormer (X) TPai(X + E) can approximate any continuous functions on the compact domain.
Corollary 3.5. Let G (V, E, E) be a labeled graph with N nodes, and node feature matrix X(0) = H E Rax consistent with the label f. Then, for all iterations there exist parameterizations of Transformer and Prim- phormer and a positional encoding such that
O.
Theorem 3.3. For any continuous function f: [0, 1jdxN + BRdx and for each e > 0, there ex- ists a Primphormer TPE with the positional encoding E such that
(v)
= x(2 (() (3.4)
for all nodes v, w E V, where X and X (t) tures of the output of Transformer and Primphormer mod- els, respectively.
Pri are node fea-
sup [I(x)) - TPE(XX)l <e XEXX
(3.2)
These results indicate that the primal representation pre- serves expressivity, ensuring that Primphormer remains a powerful graph learning model.
provide universal approximation proper- ties for functions on sequences. the realm of graph-based learning, an interesting question arises: does the universal- ity extend to functions graphs?
Theorems 3.2 3.3
4. Experimental Results
Universal approximator for functions on graphs. To an- swer the question, we construct node and edge Primphorm- ers on graphs. For the edge Primphormer, we consider the line graph (Cai et al. 202I) whose nodes are edges in the original graph. The edge Primphormer processes input
In this section, we evaluate the empirical performance of Primphormer on various graph benchmarks. To ensure di- versity, datasets are collected from different sources, a de- tailed description of which can found in Appendix A
5

---

Primphormer: Efficient Graph Transformers with Primal Representations
Table 1 Comparison of Primphormer with baselines on LRGB. Best results are colored in first, second, third.
PASCALVOC-SP F1f
COCO-SP FIf
PEPTIDES-FUNC APT
SEPTIDES-STRUH
PCOM-CONTACT MRRT
MODEL
MAEL
GCN
0.1268 = 0.0060
0.0841 + 0.0010
0.5930 0.0023
0.3496 +: 0.0013
0.3234 + 0.0006
GINE
0.1265 0.0076
0.1339 + 0.0044
0.5498 0.0079
0.3547 + 0,0045
0.3180 = 0.0027
GATEDGCN
0.2873 = 0.0219
0.2641 + 0.0045
0.5864 0.0077
0.3420 0.0013
0.3218 = 0.0011
GATEDGCN+RWSE
0.2860 = 0.0085
0.2574 + 0.0034
0.6069 0.0035
0.3357 0.0006
0.3242 = 0.0008
LRAPS
0.2694 = 0.0098
0.2618 + 0.0031
0.6326
0.0126
0.2529 + 0,0016
0.3174 = 0.0020
SAN+LAPPE
0.3230 0.0039
0.2592 + 0.0158
0.6384
0.0121
0.2683 0.0043
0.3350 0.0003
SAN+RWSE
0.3216 0.0027
0.2434 0.0156
0.6439 0.0075
0.2545
0.0012
0.3341 = 0.0006
GRAPHGPS
0.3748 + 0.0109
0.3412 :: 0.0044
0.6535
0.0041
0.2500
0.0005
0.3337 # 0.0006
EXPHORMER
0.3975 = 0.0037
0.3455 + 0.0009
0.0043 0.6527
0.2481
0.0007
0.3637 # 0.0020
PRIMPHORMMR
0.4602 + 0.0077
0.3903 + 0.0061
0.6612 0.0065
0.2495 + 0.0008
0.3757 + 0.0079
Table 2 Comparison of Primphormer with baselines GNN benchmarks. Best results are colored in first, second, third.
CIFAR10 ACCURACY
MALNET-TINY ACCURACYT
MNIST ACCURACYt
CLUSTER ACCURACYt
PATTERN ACCURACYT
MODEL
GCN
55.71 + 0.381
81.0
90.71 + 0.218
68.50 + 0,996
71.89 + 0,334
GIN
55.26 + 1.527
88.98 + 0.557
96.49 + 0.252
64.72 + 1,553
85.39 + 0.136
GAT
64.22 + 0.455
92.10 + 0.242
95.54 + 0.205
70.59 + 0,447
78.27 + 0.186
GATEDGCN
67.31 = 0.311
92.23 + 0.650
97.34 + 0.143
73.84 = 0.326
85.57 + 0.088
PNA
70.35 0.630
97.94 + 0.120
DGN
72.84 + 0.417
86.68 + 0.034
CRAWL
69.01 + 0,259
97.94 + 0.050
GIN-AK+
72.19 + 0.130
86.85 + 0.057
SAN
76.69 + 0.650
86.58 + 0.037
K-SUBGRAPH SAT
77.86 + 0.104
86.85 + 0.037
EGT
68.70 + 0.409
98.17 +: 0.087
79.23 + 0.348
86.82 + 0.020
GRAPHGPS
72.30
0.356
93.50 + 0.410
98.05 + 0.126
78.02 + 0.180
86.69 0.059
EXPHORMER
74.69 + 0.125
94.02 + 0.209
98.55 1 0.039
78.07 + 0.037
86.74 + 0.015
PRIMPHORMER
74.13 0.241
93.62 + 0.242
98.56 + 0.042
78.01 + 0.162
86.68 0.056
In particular, we conducted experiments on the bench- mark datasets including the image- based graph datasets CI- FAR10, MNIST, COCO-SP, and POSSS/VOC-SP: the syn- thetic SBM datasets PATTERN and CLUSTER; the code graph dataset MalNet-Tiny; the molecular datasets includ- ing Peptides- Func, Peptidex-Struct, and PCQM-Contact (Dwivedi et al. 2022a Freitas et al., 2021 Dwivedi et al.) 2022b) 2023); the large-scale ogbn-products dataset (Hu et al. 2020), and the graph isomorphism benchmark BREC Wang & Zhang 2024). In our experiments, we use feature maps defined as Φ, : q(z)//1)) (=)))/ll and (bs(z) :=
GNN benchmark datasets. We also evaluate our method with broader basclines on graph benchmark datasets, namely CIFAR10, MNIST, CLUSTER, PATTERN, and the code graph dataset MalNet-Tiny (Dwivedi al. 2023 Fre- itas al.. (021), reported in Table is observed that Primphormer outperforms MNIST and ranks as the second- best approach on two additional datasets, showcasing its strong performance across various dataset types.
Efficiency validation. Primphormer leverages the primal representation for GT's to reduce the computational burden. As the aforementioned results demonstrate the promising performance of Primphormer, we further validate its effi- ciency by comparing it to other computationally efficient attention mechanisms within the GPS architecture (Ram-) pasek et al. (002).. The selected mechanisms include lin- ear attention models BigBird (Zaheer et al., (020) and Per- former (Choromanski et al. 2021), sparse attention mech- anism, Exphormer (Shirzad al. (023). the sequence- specific Primal-Atten (Chen et al. 2023 and the full at-
k( ((x=)||[{<<>>))) as used by Chen et al. 2023).
Long-range graph benchmark (LRGB). We conducted experiments on LRGB (Dwivedi et al. 2022b) to evaluate the models' capabilities in learning long-range dependen- cies within input graphs. Table [ presents the results of Primphormer with several baselines. Our approach outper- forms the baselines on four of the five datasets while show- ing competitive performance the rest of the datasets.
6

---

Primphormer: Efficient Graph Transformers with Primal Representations
Table Comparison of attentions in GPS. Best results are colored in first, second, third. OOM means out of memory.
MODEL
CIFARIO ACCURACY?
MAINET-TINY
PASCALVOC-SP
PEPTIDES-FUNC
OGBN-PRODUCTS ACCURACY1
GPS
ACCURACYT
Fif
APT
MPNN-ONLY
69.95 0.499
92.23 + 0.650
0.3016 + 0.0031
0.6159 0.0048
74.25 0.214S
+ +TRANSFORMER
72.31 0.344
93.50 + 0.410
0.3748
0.0109
0.6535 + 0.0041
OOM
+ +BIGBIRD
70.48 + 0.106
92.34 + 0.340
0.2762
0.0069
0.5854 + 0.0079
73.82 + 0.412
+PERFORMER
70.67 = 0.338
92.64 = 0,780
0.3724 = 0.0131
0.6475 = 0.0056
74.30
0.211
(PRIM-ATTEN
71.57 0.256
92.97 + 0.228
0.3173
0.0055
0.6447 + 0.0046
74.47 0.134
+EXPHORMER
74.69 + 0.125
94.02 + 0.209
0.3975
0.0037
0.6527 + 0.0043
74.67
0.179
+PRIMPHORMER
74.13 + 0.241
93.62 + 0.242
0.4602 = 0.0077
0.6612 0.0065
74.89 = 0.281
Table 4 Efficiency comparisons on running time and peak memory consumption.
MODEL
TIME (S/EPOCI)
PEAK MEMORY USAGE (GB)
GPS
CIFAR.
MALNET.
PASCAL.
FUNC.
PROD.
CIFAR.
MALNET.
PASCAL.
FUNC.
MPNN-ONLY
20.3
24.5
15.7
4.8
21.1
2.31
1.92
4.18
2.45
11.97
*TRANSFORMER
28.0
232.4
35.6
12.8
3.81
35.32
7.82
8.46
OOM
+BIGBIRD
55.2
325.6
52.3
51.9
93.9
2.81
2.71
4.99
4.99
17.29
PERFORMER
50.8
73.5
49.7
21.7
22.7
10.5
11.59
6.14
7.71
16.14
PPRIM-ATEN
32.1
62.5
25.7
7.9
22.6
2.74
2.58
4.74
3.38
13.63
+EXPHORMER
44.5
62.1
35.2
7.6
25.4
5.54
10.38
7.35
4.81
31.09
+PRIMPHORMER
32.6
61.9
25.3
7.7
22.1
2.74
2.86
4.72
3.41
13.35
tention mechanism. We conduct the experiments on CI- FAR10, MalNet-Tiny, PascalVOC, Peptides-Fume Func, and a large-scale graph ogbn-products. Since ogbn-products is large to be loaded into GPU, we use the random parti- tioning method previously used by Wu et al. 2022 2023a)
Expressivity Tests. We evaluate the expressive power of our approach on the BREC benchmark (Wang & Zhang 2024), as shown in Tab. For reference, we report the re- sults of Graphormer (Ying et 202T) and APEaGT et al. 2024) as graph Transformer baselines, and 3-WL Müller er & Morris 2024). which serves as potential
As shown in Table Primphormer demonstrates supe- rior performance over other attention mechanisms such as BigBird, Performer, and Prim-Atten, while also exhibiting competitive performance with Exphormer. Table4presentt comparison of running time and peak memory usage across different methods. Primphormer demonstrates su- perior performance in both running time and memory con- sumption compared to other approaches. For example, in the MalNet-Tie -iny dataset, linear attention mechanisms in- troduce significant computational overhead. While Prim- Atten offers good efficiency, its performance on graph tasks lags due to its sequence-speciffe nature. Both Primphormer and Exphormer, designed for graphs, exhibit similar run- ning times. Nevertheless, Primphormer consumes less memory its complexity depends solely on the number of nodes, whereas Exphormer's complexity is controlled by the number of nodes and edges. In the ogbn-product, products dataset, which comprises approximately 2 million nodes and million edges, Primphormer showcases the most ef- ficient results compared with other methods. In summary. our experiments demonstrate that Primphormer exhibits competitive performance while maintaining user-friendly memory and computational costs.
pressivity upper-bound. We compare pure Primphormer to the standard Transformer /Vaswani et al. 2017) and Prim- Atten (Chen et al.] (023) using two positional encodings: LAP/LapPE (Kreuzer et al., 202I) and SPE (Huang et al. 2024), all evaluated without the MPNN layer. We find that both Transformer and Primphormer outperform Prim- Atten. And results show that Primphormer and the standard Transformer achieve similar performance, consistent with our theoretical results discussed in Sec. 3.2
Table Results on the BREC benchmark. Basic, Regular, Extension, and CFI are subsets of the BREC benchmark. Experiments are averaged over 5 runs.
MODEL
PE
BAS.f
REG.
Ext.
CFIf
ALL
GRAPHORMER
16
12
41
10
79
APE-GT
50.6
31.3
62.4
145.3
TRANSFORMER
47,2
39
65.2
154.4
PRIM-ATTEN
LAP
12.8
19
13.6
0.6
46
PRIMPHORMER
51.6
42
72.4
169
TRANSPORMER
59.8
49.4
98.6
5.2
213
PRIM-ATTEN PRIMPHORMER
SPE
49
171.4
50
100
9.4
219.4
7

---

Primphormer: Efficient Graph Transformers with Primal Representations
5. Related Work
et al. (0222) proposed an asymmetric kernel trick from pair of RKBSs. He al. (2023b) converted an asymmetric kernel to complex-vaie valued Hermitian function by the mag- netic transform. [Suykens] (2016) introduced novel varia- tional principle to dissect the primal-dual relationship con- cerning the singular value decomposition of an asymmetric kernel matrix, a concept further extended to classífication tasks by He al. (2023a). This variational principle was also leveraged by Chen et al. (2023) to interpret attention mechanisms in sequences. However, due to the distinctions between sequences and graphs, this model is unsuitable for graph-based learning.
Graph Transformers. Transformers have demonstrated success in natural language processing (Vaswani et al.) 2017) and computer vision tasks (Liu et al., 2021). Re- cently, researchers have explored the application of Trans- formers in graph representation learning to address is- sues such as over-smoothing (Nguyen et al. 2023) and
over-squashing (Giraldo et al. 2023) observed in MPNNs. Graph Transformers operate on a fully connected graph where nodes are pairwise connected, encoding the orig- inal graph structure into positional encodings. Spectral Attention Networks (SAN) (Kreuzer et al.. [021]) intro- duced conditional attention for both real and virtual edges and implemented Laplacian positional encoding for nodes. Graphormer (Ying et al. 2021) and GraphiT (Mialon et al.) 2021] incorporated relative positional encodings based on pairwise graph distances and diffusion kernels, respec- tively. GPS proposed a framework that combined MPNNs with attention mechanisms (Rampasek et al., 2022).
6. Conclusion
In this paper, we propose Primphormer, new framework for graph Transformers. Primphormer models the self- attention mechanism on graphs in the primal space, avoid- ing pair-wise computations, which enables an efficient vari- ant of graph Transformers. Our primal-dual analysis shows that Primphormer can be implemented by introducing an additional primal objective loss. Due to its efficiency in both runtime and memory storage, Primphormer has the potential to support larger and deeper neural networks and enable larger batch sizes, enhancing model capacity and generalization ability. Primphormer also benefits from the universal approximation property for functions on both se- quences and graphs, potentially possessing strong general- ization capabilities to unseen data or tasks. We exhibit that its expressive power is as powerful as Transformers in dis- tinguishing non-isomorphic graphs, showing that the pri- mal representation can preserve expressivity. Experimental results on various graph benchmarks demonstrate the effec- tiveness and efficiency of the proposed Primphormer.
The quadratic complexity in traditional GTs has moti- vated the development of computationally efficient atten- tion mechanisms. Linear attention mechanisms, such as NodeFormer (Wu et al. 2022) and SGFormer (Wu et al.] 2023b), aim to reduce computational complexity by de- composing or approximating the kernel matrix, operating in the dual space. For example, NodeFormer uses a random feature-basse based approach, while SGFormer drops the soft- max activation to approximate the kernel matrix. Difformer (Wu et al. 2023a) introduced a diffusion based Trans- former model with linear complexity, although their atten- tion mechanisms are limited to nodes randomly sam- pled mini-batches. Another strategy is the sparse Trans- former, which enhances computational efficiency by re- stricting node interactions. Exphormer (Shirzad et al.) 2023) limited interactions across real and expander edges, achieving linear complexity to the number of nodes and edges. However, the efficiency of Exphormer diminishes as graphs become denser. A survey on efficient Transform- ers is given by Fournier et al. 2023).
An interesting avenue for future work is exploring how edge features can be incorporated into Primphormer's structure. Edge features can be added to attention scores in entry-wise manner data-adaptive kemnlss (Liu et al., 2020). Exploring the primal representation of these kernels allows us to incorporate edge information into attention mechanisms, potentially resulting in a stronger GT. Addi- tionally, fine-tuning schemes like LoRA (Hu et al. 2022) are promising for large models. Studying LoRA from a primal-dual perspective may lead to more efficient fine- tuning methods.
The quadratic com- plexity also arises in kernel machines in duality and can be circumvented by transferring a dual problem to its pri- mal form. Models such as the support vector machine (Cortes& & Vapnik| [995), least squares support vector ma- chine (Suykens& Vandewalle| [199),, and kernel principal component analysis (Mika et al., 1999) exhibit this char- acteristic. The associated pair-wise kernels are symmet- ric and positive-definite, whereas attention scores are in- herently asymmetric, violating the Mercer condition (Mer- cer 1909). Recent research has explored a new primal-dual perspective to accommodate such asymmetry in kernel ma- chines. To incorporate asymmetric kernel functions, Lin
Primal and dual representations.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
8

---

Primphormer: Efficient Graph Transformers with Primal Representations
Acknowledgments
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learnable struc- tural and positional representations. In International Conference on Learning Representations, 2022a.
The authors would like to thank the anonymous reviewers for their insightful comments.
The research leading to these results has received fund- ing from the National Key Research Development Project (2023YFF1 104202) and the National Natural Science Foundation of China (62376155).
Dwivedi, V. P., Rampāšek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. In Thirty-sixth Conference on Neural In- formation Processing Systems Dalasets and Benchmarks Track, 2022b.
References
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Ben- gio, Y., and Bresson, X. Benchmarking graph neural net- works. Journal of Machine Learning Research, 24(43): 1 1-48, 2023.
Alberti, S., Dern, N., Thesing, L., and Kutyniok, G. Sum- former: Universal approximation for efficient transform- ers. In Topological, Algebraic and Geometric Learning Workshops 2023, 2023.
Fan, R.-E., Chang, K.-W., Hsich, C.-J,, Wang, X.-R., and Lin, C.J. Liblinear: A library for large linear classifi- cation. Journal of Machine Learning Research, 9:1871- 1874, 2008
Black, M., Wan, Z. Mishne, G., Nayyeri, A., and Wang, Y. Comparing graph transformers via positional encod- ings. In Forty-first International Conference on Machine Learning. 2024.
Fournier, Q., Caron, G. M., and Aloise, D. A practical sur- vey on faster and lighter transformers. ACM Computing Surveys, 55(1 55(14s): 101 2023.
Cai, C., Hy. T. S., Yu, R., and Wang, Y. On the connec- tion between mpnn and graph transformer. In Interna- tional Conference on Machine Learning, pp. 3408-3430. PMLR, 2023.
Freitas, S., Dong, Y., Neil, J., and Chau, D. H. A large-scale database for graph representation learning. In Thirty-fifth Conference Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
Cai, L., Li, J., Wang, J., and Ji, S. Line graph neural net- works for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5103-5113, 2021.
Giraldo, H., Skianis, K., Bouwmans, T., and Malliaros, F. On the trade-off between over-smoothing and over- squashing in deep graph neural networks. In Proceed- ings of the 32nd ACM International Conference on In- formation and Knowledge Management, 2023.
Chen, D., O' O'Bray, L., and Borgwardt, K. Structure-aware transformer for graph representation learning. In Inter- national Conference on Machine Learning, 2022.
Chen, Y., Tao, Q. Tonin, F., and Suykens, J. A. K. Primal- attention: Self-attention through asymmetric kernel svd in primal representation. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
Graham, A. Kronecker products and matrix calculus with
applications. Courier Dover Publications, 2018.
Grohe, M. The logic of graph neural networks. 2021 36th Annual ACM/IEEE Symposium on Logic in Com- puter Science (LJCS), pp. 1-17. IEER, 2021.
Choromanski, K. M., Likhosherstov, V., Dohan, D., Song. X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mo- hiuddin, A., Kaiser, L., Belanger, D. B., Colwell, L. J., and Weller, A. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
Hc, M., He, F., Shi. L., Huang, X., and Suykens, J. A. K. Learning with asymmetric kernels: Least squares and feature interpretation. IEEE Transactions on Puttern Analysis and Machine Intelligence, 45(8):10044410054, 2023a.
Cortes, C. and Vapnik, V. Support-vector networks. Ma- chine Learning, 20(3):273-297, 1995.
He, M., He, F., Yang, R., and Huang, X. Diffusion rep- resentation for asymmetric kernels via magnetic trans- form. In Thirty-sevnnth Conference Neural Informa- tion Processing Systems, 2023b.
Dong, G., Tang, M., Wang, Z., Gao, J., Guo, S., Cai, L.. Gutierrez, R., Campbel, B., Barnes, L. E., and Boukhechba, M. Graph neural networks iot: A sur- vey. ACM Transactions on Sensor Networks, 19(2):1- 50, 2023.
Hornik, K., Stinchcombe, M., and White, H. Multilayer feedforward networks are universal approximators. Neu- ral Networks, 2(5):359-366) 1989.

---

Primphormer: Efficient Graph Transformers with Primal Representations
Hu, E. J., yelong shen, Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L.,, and Chen, W. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Ma, L.,, Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph induc- tive biases in transformers without message passing. In International Conference on Machine Learning, 2023.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: datasets for machine learning on graphs. In Sourth International Conference on Neural Information Pro- cessing Systems, 2020.
Mercer, J. Functions of positive and negative type, and their connection with the theory of integral equations. Pro- ceedings of the Royal Society of London. Series A, Con- taining Papers of a Mathematical and Physical Charac- ter, 83(559):69 70, 1909.
Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv: 106.0:706 2021.
Huang, Y. Lu, W., Robinson, J., Yang, Y., Zhang, M., Jegelka, S., and Li, P. On the stability expressive posi- tional encodings for graphs. In The Twelfth International Conference on Learning Representations, 2024.
Mika, S., Schölkopf, B., Smola, A., Müller, K.-R., Scholz, M., and Rätsch, G. Kernel PCA and de-noising in fea- ture spaces. In Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems II, 1999.
Hutter, M. On representing (anti) symmetric functions. arXiv preprint arXiv:2007. 2020.
Khesin, B. A. and Tabachnikov, L. ARNOLD: Swim- ming Against the Tide: Swimming Against the Tide, vol- ume 86. American Mathematical Society, 2014.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceed- ings of the AAAI conference on Artificial Intelligence, 2019.
Kimeldorf, G. and Wahba, G. Some results on Tehebychef- fian spline functions. Journal of Mathematical Analysis and Applications, 33(1):82-95, 1971.
Müller, L. and Morris, C. Aligning transformers with weisfeiler-Ieman. In Forty-first International Conference on Machine Learning, 2024.
Kreuzer, D., Beaini, D., Hamilton, W. I.., Létourneau, V., and Tossou, P. Rethinking graph transformers with spec- tral attention. In Advances in Neural Information Pro- cessing Systems, 2021.
Nguyen, K., Hieu, N. M., Nguyen, V. D., Ho, N., Osher, S., and Nguyen, T. M. Revisiting wer-ssno and over- squashing using ollivier-ricci curvature. In International Conference on Machine Learning, 2023.
Li, X., Sun, L., Ling, M., and Peng, Y. A survey of graph neural network based recommendation in social networks. Neurocomputing, 549: 126441, 2023.
Rampasek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, scal- able graph transformer. In Advances in Neural Informa- tion Processing Systems, 2022.
Lin, R. R., Zhang, H. Z., and Zhang, J. On reproducing kernel banach spaces: Generic definitions and unified framework of constructions. Acta Mathematica Sinica, English Series, 388)):145--148, 2022.
Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, J., and Sinop, A. K. Exphormer: Sparse transform- ers for graphs. International Conference on Machine Learning, 2023.
Liu, F., Huang, X., Gong, C., Yang. J., and Li, L. Learning adta-adeetive non parameemttiic kernels. Journal of Ma- chine Learning Research, 21(208):1 2020.
Suykens, J. A. K. Svd revisited: A new variational princi- ple, compatible feature maps and nonlinear extensions. Applied and Computational Harmonic Analysis, 40(3):
Liu, Y. L., Wang. Y., Vu, O., Moretti, R., Bodenheimer, B., Meiler, J., and Derr, T. Interpretable chirality-aware graph neural network for quantitative structure activity relationship modeling in drug discovery. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
600-609, 2016.
Suykens, J. A. K. and Vandewalle, J. Least squares support vector machine classifiers. Neural Processing Letters, 9: 293-300, 1999.
Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang. Z., Lin, S., and Guo, B. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Processing Systems, 2017.
10

---

Primphormer: Efficient Graph Transformers with Primal Representations
Wang, and Zhang, M. An empirical study of realized gnn expressiveness. In Forty-first International Conference Machine Learning, 2024.
Weisfeiler, and Leman, A. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9))12-16, 1968.
Wright, M. A. and Gonzalez, J. E. Transformers are deep dimensoadiiensionall non-mercer binary kernel ma- chines, arXiv preprint urXiv:2106.000 0156, 2021.
Wu, Q. Zhao, W., Li, Z., Wipf, D., and Yan, J. Node- former: A scalable graph structure learning transformer for node classification. In Advances Neural Informa- tion Processing Systems, 2022.
Wu, Q., Yang, C., Zhao, W. He, Y., Wipf, D., and Yan, DIFFormer: Scalable (graph) transformers induced by energy constrained diffusion. International Confer- ence on Learning Representations, 2023a.
Wu, Q., Zhao, W., Yang, C., Zhang, H., Nie, F., Jiang, H., Bian, Y., and Yan, Sgformer: Simplifying and em- powering transformers for large-graph representations. In Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023b.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? In Advances Neural Infor- mation Processing Systems, 2021.
Zaheer, M. Kottur, S., Ravanbhakhsh, S., Póczos, B., Salakhutdinov, R., and Smola, J. Deep sets. In Pro- ceedings of the Thirty-first International Conference on Neural Information Processing Systems, 2017.
Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., AI- berti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q. Yang, L., et al. Big bird: Transformers for longer se- quences. Advances in Neural Information Processing Systems, 2020.
Zhuang, B., Liu, J., Pan. Z., He, H., Weng. Y., and Shen, C. A survey on efficient training of transformers. In Pro- ceedings of the Thirty-Second International Joint Con- ference on Artificial Intelligence, 2023.

---

Primphormer: Efficient Graph Transformers with Primal Representations
Appendix
A. Data Descriptions
Here, we introduce the datasets in the experiments. summary the dataset statistics is shown in Tab. A1
CIFAR10 and MNIST. CIFARIO and MNIST the graph equivalents of the image classification datasets of the same name. A graph is created by constructing the 8-nearest neighbor graph of the SLIC superpixels of the image. These both 10-class graph classification problems (Dwivedi et al. 2023).
PascalVOC-SS and COCO-SP. These are similar graph versions of image datasets, but they are larger images and the task is to perform node classification, iee, semantic segmentation of super-pixels. These graphs are larger, and the tasks are more complex than CIFARIO and MNIST (Dwivedi et al. 2022a
CLUSTER and PATTERN. PATTERN and CLUSTER are node classification problems. Both synthetic datasets that sampled from Stochastic Block Model (SBM), which is popular way model communities. In PATTERN, the prediction task is to identify if node belongs to one of the 100 possible predetermined sub-graph patterns. In CLUSTER, the goal is to classify nodes into six different clusters with the same distribution (Dwivedi et al. 2023
MalNet- Tiny, Malnet-Timg Tiny is smaller dataset generated from larger dataset for identifying malware based on function call graphs from Android APKs. The tiny dataset contains 5000 graphs, each with up to 5000 nodes. The task is to predict the graph as being benign from one of four types of malware (Freitas al. 2021).
Peptides-Func, Peptides-Struct, and PCQM-Contact. These datasets molecular graphs introduced part of the Long Range Graph Benchmark (LRGB). On PCQM-Contact, the task is edge-level, and we need to rank the edges. Peptides-Func is a multi-label graph classification task with 10 labels. Peptides-Strue -Structt-ttccttt is a graph-level regression of 1 structural properties of the molecules (Dwivedi et al. 2022a b).
The ogbn- produuts dataset an undirected and unweighted graph, representing an Amazon product co- po-purchasing network. Nodes represent products sold on Amazon, and edges between two products indicate that the products purchased together. Specifically, node features are generated by extracting bag-of-words features from the product descriptions followed by Principal Component Analysis reduce the dimension to 100. The task is predict the category of product in multi-class classification setup, where the 47 top-level categories are used for target labels (Hu et al., 2020). We use the random partitioning method with ten partitions as previously utilized in Wu et al. (2022) 2023a).
OGBN-products.
BREC. BREC is a dataset for GNN expressiveness comparison. addresses the limitations of previous datasets, including difficulty, granularity, and scale, by incorporating 400 pairs of various graphs four categories (Basic, Regular, Extension, and CFT). The graphs guish them. We use the evaluation method, RPC (Reliable Paired Comparisons). with contrastive training framework as introduced in Wang & Zhang (2024).
organized pair-wise, where each pair is tested individually return whether GNN can distin-
Table A1 Dataset statistics.
DATASET
GRAPHS
AvG. NODES
AVG.EDGES
TASK LEVEL
CLASS
METRIC
MNIST
70,000
70.6
564.5
GRAPH
10
ACC.
CIFARIO
60,000
117.6
941.1
GRAPH
Acc
PATTERN
14,000
118.9
3039.3
INDUCTIVE NODE
2
ACC
CLUSTER
12,000
117.2
2150.9
INDUCTIVE NODE
Acc
MALNET-TINY
5,000
1,410.3
2,859.9
GRAPH
5
Acc
PASCALVOC-SP
11,355
479.4
2710.5
INDUCTIVE NODE
21
F1
COCO-SP
123,286
476.9
2710.5
INDUCTIVE NODE
81
F1
ICOM-CONTACTT
529,434
30.1
61.0
INDUCTIVE LINK
RANKING
MRR
PEPTIDES-FUNG
15,535
150.9
307.3
GRAPH
10
AP
PEPTIDES-STRUCH
15,535
150.9
309.3
GRAPH
MAE
2,449.029
61,859,140
NODE
47
ACC
12

---

Primphormer: Efficient Graph Transformers with Primal Representations
B. Tlyperparameters
Our selection of hyperparameters was guided by the instructions GPS (Rampasek et al. 2022) and Exphormer (Shirzad al.
2023). Further details can be found in Tables. A3
In our model, introduced additional hyperparameters, the dimensions of the data-dependent projection, denoted N, and its low rank and the regularization coefficient 7,. We utilized grid search explore these hyperparameters across 8 E (20, 30, 40, 50, 60). and {0.1, 0.01), For the remaining hyperparameters, we conducted linear search for each parameter to determine the best values. Throughout all experiments, we employed CustomGatedGCN as the MPNN module alongside Primphormer except for ogbn-products dataset where we use GCN. To ensure fair comparisons, we maintained similar parameter budget to that of GraphGPS.
Table A4 presents the hyperparameters used in our efficiency experiments. To maintain consistency in our evaluations of various attention mechanisms, applied the same parameters for fair comparison.
Table A2 Hyperparameters used in Primphormer for datasets: Pascal COCO-SP, Peptides-Func, Peptides-Struce PCQM-Contact.
HYPERPARMETER
PASCALVOC-SP
COCO-SP
PEPTIDES-FUNC
PEPrIDE-STRUCT
PCQM-CONTACT
#LAYERS
6
4
4
HIDDEN DIM
80
96
96
#HEADS
1
4
4
DROPOUT
0.15
0.0
0.1
0.15
0.0
ATTENTION DROPOUT
0.5
0.5
0.1
0.5
0.56
PE
LAPPE
LAPPE
RWSE
RWSE
LAPPE
PE DIM
16
16
16
20
16
BATCH SIZE
200
150
200
200
128
LEARNING RATE
IE-3
1E-3
1E-3
1E-3
3E-4
#EPOCHS
300
300
250
250
WEIGHT DECAY
1E-5
1E-2
1E-2
IB-2
0.0
N.
30
30
"
0.1
0.1
0.1
0.1
0.1
30
20
30
40
30
#PARAMETERS
508305
315305
470693
468783
386526
Table A3 Hyperparameters used in Primphormer for datasets: CIFAR10, MNIST, MalNet-Tiny, PATTERN, CLUSTER,
BREC.
HYPERPARMETER
CIFARI0
MNIST
MALNET-TINY
PATTERN
CLUSTER
BREC
#LAYERS
3
5
12
HIDDEN DIM
52
40
84
48
52
32
#HEADS
1
1
4
DROPOUT
0.15
0.1
0.15
0.0
0.15
0.0
ATTENTION DROPOUT
0.5
0.5
0.5
0.5
0.5
0.5
PE
ESLAPPE
ESLAPPE
ESLAPPE
ESLAPPE
LAPPE/SPE
PE DIM
16
BATCH SIZE
200
200
64
128
48
16
LEARNING RATE
1E-3
1E-3
1E-3
1E-3
1E-3
1E-3
#EPOCHS
300
300
300
200
300
25
WEIGHT DECAY
1E-2
1E-5
1E-3
1E-5
1E-5
1E-2
N
20
30
50
30
40
20
7
0.1
0.1
0.1
0.1
0.1
0.01
20
30
50
30
40
20
#PARAMETERS
112957
101714
519605
208387
499386
52238
13

---

Primphormer: Efficient Graph Transformers with Primal Representations
Table A4 Hyperparameters used in Table.
HYPERPARMETER
CIFARIO
MALNET-TINY
PASVALVOC-SP
PEPTIDE--UUNC OGEN-PRODUCTS
HIDDEN DIM
40
64
96
96
128
BATCH SIZE
128
4
32
128
C. Proofs of theoretical results
In this section, we provide the proof of theoretical results in this paper.
C.1. Proof details of Theorem 2.2
The Lagrangian of 2.5 is defined by,
1 N
C(We, e, W,, Ti her n,,,)
Ae;
25 r Ar; Tr(W. W,)
2
i=1
(CI)
N
heg (e; - fx (x n (ry fx (w))
where her h E R are dual variable vectors corresponding to the equality constraints regarding the projection scores e; and r.
By taking the partial derivatives to the Lagrangian CC equalities,
the Cerush-Kuhn-TTee (KKT) conditions lead to the following
0c = =0 W. Σ
N
fx her 0g
ow.
i=1
J6
N
W. Σ
f 0x (2x))
aW,
j=1
36 = 0 - Ae; = her iN(N]
de.
(C2)
0 Ar; bry JEIN]
3C
= -0 e, fx W. [N[N]
dh..
0C
= =0 r, = fx fxWoo) [e
Th,
By eliminating the primal variables W. and W, have,
N
Fxh,, TT (oy(x,)) - [N(N),
1=1
(C3)
Σ Fxhe, (x A heys j [N),
where = :x E Stxx is the auto-correlation matrix. can be expressed in the following matrix form,
ONXN
[6, (x(x)))
H.
H.
[(b((t)) (xx))
Fx
A-1
(C4)
ONNN
H
H
with H. [he...... hew]" E RN and H, [hr,.... ...,, h T NNs
14

---

Primphormer: Efficient Graph Transformers with Primal Representations
Then it can be noticed that the optimization problem 2.. in the dual space yields the following generalized eigenvalue problem with an asymmetric kernel K,
= =
(C5)
K H,Fx= H,E.
which collects the solutions corresponding to the non-zero entries in A such that = A-1, The asymmetric kernel matrix K, induced by Kij- (xe), 0x (x,)), Vi,j E [N], corresponds the attention matrix.
C.2. Derivation of scores 2.8 in the primal and dual spaces
With the derivations and KKT conditions of the primal-dual optimization above, the primal and dual representation for self-attention be formulated follows.
e((r)= = fx W (1))
Primal:
(C6)
r(x) = fx W, (x))
e(x) = fx W. Wo (x;) = Σ N
j=1 Fxhr, ox (xx) Tg(x))
Dual:
(C7)
Σ Fxhe, (2x)) T (L)()).
r(x: = fx W, dE (m:)
Then, the primal and dual representations for self-attention can be formulated as follows,
Dual: ee(x)= = Σ j=1 M,r, wz), N
(e(x) W (x))) r(xx) (x)),
Primal:
(C8)
r(x)) = Σ im hock((xi, (x),
where Wix e|x == We E RXxp, WT r|x == W, E Roxp and hry == Extery, her = Fxhe, are values for self-
attention, respectively.
C.3. Proof details of Lemma 2.3 Proof. Based on the KKT conditions
C2
and 2.6 the objective on stationary points is,
N
2 e, Ae;
+
rj Ar,
Tr (W. Wr)
2
2
Σ i=1 (A -he)
N
AA he:
+ 2 j=1
Σ
N
(A hrr)) ) AA -hr;
N
-Th j=l
Ds (2 fx)
i=1 (o())
2 D
1 N
TAA A
- -1 he, + -iir
h A
--- Tr ( is 0x(2x)) /h, Fx Fxhe (x.)
j=1
1
Ir (H.
1
Ir (H, Tr EE, is Dol(z) TT (2;))) Extees
2
2
Tr (H.EH.)
1
Tr (H.
Tr (KH,FxH.)
(C9)
2
1
Tr (KH,FxH.))
+ Tr (K' H.FxH.) - Tr (K.,FxH.)
2
2
(K H.FxH.) Tr (H,
2
2
Tr (H.FHH,
Tr (KH,FxH.)
2
Tr FxH. (H..FHH,KK))
2
1 Tr (KH,FxH.)
1
(KH,FHH..)) 0.
2
15

---

Primphormer: Efficient Graph Transformers with Primal Representations
C.4. Proof details of Theorem 3.2
Proof. The proof follows ideas (Alberti al. 2023). We first introduce the Sumformer and divide the approxima- tion into two parts: 1) approximate f by S and 2) approximate S by Primphormer TPri-
Definition C.1 (Sumformer). Let d' E N and let there be two functions & X - Rd v X x Rd¹ - y. A Sumformer is a sequeence-fo-seqquenee function S 2 + y>V which is evaluated by first computing
{(xx):
(C10)
and then
S ((21, ". xx]) = (21, _). ... ( E)
(C11)
Lemma C.2 (Alberti al. 2023), universal approximation of Sunformer). For each function f F (X,)) and for each > 0 there exists Sumjormer S such that
sup [lf(X) S(X) <c
(C12)
XEX
We divide the approximation into steps by the triangular inequality: 1) approximate by Sumformer 8 and 2) approximate S by a Primphormer Tpri.
sup
- - (X)l S sup - - s(X))lo + sup [8(X) -TPr(X))lss XEXN
(C13)
xeXx
XEXX
we know that there exists a Sumformer S which approximates f an error of c/2. This Sumformer has the inherent latent dimension d'.
According Theorem C.2
Secondly, we turn the second term and construct Primphormer that approximate Sumformer to e/2 error. The structure of Transformer is X + FFN (X + Att(X)) where FFN and Att are the feed-forward and self-attention mod- ules, respectively. The attention map Att(X) of Primphormer is calculated in the primal space (2.8) and the rest of the architecture in Primphormer stays the same. Here, we follow the proof idea proposed (Alberti et al. 2023) and refer readers to this work for detailed information on the theoretical result.
We have the input X -..,.... æN] X with æ; Fd. Set the attention in the first layers to zero, we obtain the Reed-forward layers without attention. We first map X with forwaro transformation to
EN EN
22
(C14)
21
Then, a two-layer feed-forward network can be constructed to act as the identity on the first N components while approxi- mating the function & in Sumformer (Hornik et al. 1989 Alberti et al. 2023). We have.
æ1 {(x1)
EN {(ΦN)
E Bll+dd)xN
(C15)
Before getting to the second step, we add a linear mapping with
Oaxı
Ia
Oaxaa
Oaxdd
E (RL+dt2d))(dtd)
W
Oxx1
Oxxd
Is
Oxxd
(C16)
IN
O ONx
E =0++442))xN
and get an output after the first step:
EN
R (
(C17)
{(x1)
{(xN)
0a'x1
0a'x1
16

---

Primphormer: Efficient Graph Transformers with Primal Representations
Secondly, turn the attention scheme represent the sum = E {(x;,) defined in the definition Wg W2= [e1 (((22))) with e1 [1, [1,0 [x((22))))) __ we have,
C.I
Set
( = 0x (1) 1NxI, Oxx(4+20)) E (
(C18)
Let the data-dependent projection f(X) BX1x1X with B (0 Od Id' Od' we have,
N f(x) Σ E(x)),
Σ {(x,) = 1 , Rd'xN, XN
(C19)
Let W. W, = (1td
the projection scores in 2.8 are
e((x)) = f(X,) (o, [ E
R XN
(C20)
(r(x)) -
= E E Rdd x
To fit the dimension of the output, we concatenate the projection scores (e(X i): r (x)) E R2d xdd xN and choose a compat-
ibility matrix We (11++t'')xxx' Ia', Lal E (x+d++dd)x2d such that
E x
0 (1
O O1+d+dd)x1 B((++42d))xN
o We
(C21)
r(Xi)
Then apply residual connection and obtain the same output as outlined in Alberti et al. 2023
1
(C22)
{
E {( E
Because only the attention map (X) is changed in the architecture and the rest stays the same, the construction of yb is as same as that in (Alberti et al. 2023), i.e., ((N(2) /N!) feed-forward layers for approximating v in the discontinuous case and two feed-forward layers for approximating vó in the continuous case. Above all, we can construct a Primphormer that approximates the Sumformer to e/ error.
C.5. Proof details of Theorem
Proof. The proof can be done in a similar way as Theorem 3.2 [9(x1, {x22 ... xN ...- "(g). (x1, tions f., i.e., 9. are also continuous. The compactness of X' shows that X is also compact and therefore uniformly continuous. Without loss of generality, let the compact support of g be contained in [0, 1]dx.N Then we can define piece-wise constant function g by
Firstly, let the target function S(X) =
xN-1))] Since the target function f is continuous, its component func-
g(X)
Σ (()))(XX CCP), PE
(C23)
where the grid G = 10,5....,1 8)x8N for some 8 I with A E N consisting of cubes Cp
- PL,,, P.. + 5). Because g is uniformly continuous, for each > O, there exists a d > 0 such that
sup Xexx
[lg(X) (lo <.
(C24)
Secondly, choose the positional encoding
0
2 N 1
0
2 N -1
E
E R
(C25)
0
1 2
N --1
17

---

Primphormer: Efficient Graph Transformers with Primal Representations
After applying the quantization, the output is in the following set,
His == (P + E D PE Go).
(C26)
Then the i-th column of X + E is in the range [ - 1, 1.i meaning that the entries corresponding to different tokens lie in disjoint intervals. More precisely, for any H E Gg. its i-th column H; E 1 1::::: 6).
Consider a vector
N6-4+1 x (1,8-1,.. 8 1-
Rd. It easy to check that for any H E Go the map
(HH)) = u² H; is one-to-one,
(1 (1-8)(--1) d-1 (1-6)
(1 (1-8)i
d-1 (6-4
u' T H
Σ N8-4+1
Σ 8- k=
(C27)
No-d No-6+1
N8-6-1
Therefore, for each column H, the image of (HH) is an interval disjoint from the other columns. We can know that 1(H)) can be thought as a "column id" for different columns, for any permutation [N] + [N]
1 (HH())) < H (H)())) <.. < ( (M)())
(C28)
Besides, it can be easily checked that the image of lies within the interval [o, 1].
(H)) (Ha()) <... <1 < (N)) 1.
(C29)
Next, we want to represent z using appropriate S. Without loss of generality, we choose the k-th component of f. ie.. g( i き k, e [.]).. Assign each grid point H coordinate x = b e j0, 1 by the construction of the function 1. Let b = [(HH) E [N] E [0, 1} The map is bijective and there are finitely many b. We can enumerate all b using a function μ [0, M| + N. This function could be represented by the Kolmogorov-Amoll representation theorem,
as stated below,
Lemma C.3 (Kolmogorov-Ammoll representation (Khesin& & Tabachnikov be an arbitrary multivariate continuous function iff it has the representation,
2014
Zaheer et al. 2017)). Let f [0, 1] +R
N
f(x1.- .xN) P
Σ (zz)))
(C30)
n=1
with continuous outer and inner functions the function f-
2 + R and @ 12 - 12N-1
The inner function is independent of
Now, we can utilize Lemma
C.3 to find the representation for the function 14,
m(b) = Σ Ab.)
(C31)
Define E = = =(b,)= (b, and quantization function such that b, = l(g(x, + E,)). It is feasible because b,, varies for different indices, as claimed in "column id" (C28) Now we can recover the grid H,
x p (()).
(C32)
We then define the function ub such that the related S is equal g:
(xx, E) y (uxx nt p(=)-E))
(C33)
with 1. P + (Px, Poye) to fit the input requirement of g. Since we chose ō to uniformly approximate g. i.e., each component of f up to e error, it implies that with a positional encoding uniformly approximates ff up to e error.
Thirdly, we need to prove the universal approximation between Sumformer and Primphormer after adding a positional encoding. The proof (C.4) still holds because only involves the architecture. We can claim that there exists a Primphormer with positional encoding TPE uniformly approximating Sumformer S.
Above all, we end the proof by using the triangular inequality.
sup X
[xxx) (Pe(X)le I sup
Ilf(X) - S(x) + sup ||S(X) Tre(()) <c. X
(C34)
XEX
18

---

Primphormer: Efficient Graph Transformers with Primal Representations
C.6. Expressivity of Primphormer
In this subsection, we prove the expressivity of Primphormer. According to the previous work (uüller & Morris (024). which demonstrates that the standard Transformer can simulate the 1-WL test, we prove that Primphormer is also capable of simulating the 1-WL test. This result indicates that the primal representation preserves expressivity, ensuring that Primphormer remains a powerful graph learning model.
Lemma CA4 (Theorem VIII.4, Grrhe 2021 ). Let G = (V, be a labeled graph with N nodes, adjacency matrix (G), and node feature matrix X updates the node feature matrix,
HHE E RaXN consistent with the label E. Assume a GNN that for each layer, t > O.
x FFN (x((-1) -2
(C35)
Then, for all t 2 0, there exists a parameterization FFN such that
[[ = (1) (w),
(C36)
for all nodes v, w E V, where Ct is the coloring function of the I-WL. test at 1-th iteration.
The previous work (Müller & Morris 2024 has shown that the standard graph Transformer i.e., 1-GT, with sufficiently adjacency-identifying structural embeddings such as LAP/LapPE (Kreuzer et al. (02I)) and SPE (Huang et al., 2024) could simulate the (C35), demonstrating the expressive power of the standard graph Transformer is as same as the I-WL test.
Lemma C.5 (Theorem 2, (uüller& & Morris 2024)). Let G = (V, E, be a labeled graph with N nodes, and node feature matrix (0) == H ddd consistent with the label f. Then, for all iterations 1 2 O, there exists a purameterization of 1-GT such that
(v) (ww) = (x) (w),
(C37)
for all nodes v, w E V, where Ct is the coloring function of the I-WL test at 1-th iteration.
In our approach, we replace the standard attention module with the primal representation "Prim", forming model structure FFN(X + Prim(X)). Our goal is to show that the primal representation preserves the expressivity of the standard Transformers. To ensure a fair comparison, we follow the same setup used by Müller & Morris (2024). Let G = (V, E, E) be a labeled graph with N nodes, and node feature matrix X() := H E Rd consistent with the label f. Then, we initialize N node embedding (0) = H + P. where P E RdxN is the structural embeddings, encoding structural information for each node. For each node u,
P(v) == FFN (deg(u) + PF)))),
(C38)
where deg: V > RR! is a learnable embedding of the node degree, PE: V + RC is node-level PE such as LAP and SPE, and FFN: T -> IRd is feed-forward layer.
Definition C.6 (LAPP and SPE (Müller & Morris 2024)). Let (A, V) denotes the eigensystem of the graph Laplacan L of graph G with N nodes where := (A1.-.. An) is the vector of the n smallest eigenvalues and V E Mxx xn is the corresponding matrix of eigenvectors. Then the LAP and SPE are defined as follows,
LAP(A, V) P1 (I .),.... (VV A)))
(C39)
SPE(A, V) = P2 (IVV)
VVn (A)V
where LAP: vb: R22 + RR' is a ford-forward layer applied row-wise and P1 R Nx + Nx! is a permutation-equivaaane neural network; SPE: m is a hyper-parameter, Φ1, , Om : T + R2" and P2 : NxNNx + Nxl are permutation- equivariant neural networks. The graph Laplacian is defined as L == D- A where D and A are the diagonal degree matrix and the adjacency matrix of graph G, respectively. The normalized graph Laplacian is defined as L :== I D AD-
According Definition C.6 there exists a parameterization of LAP and SPE represent the original graph Laplacian. This intuition is also proven See. 3.5 in Kreuzer al. (2021), Sec. 3.4 in Huang al. (2024), and Theorems. 20 and 22 in Müller & Morris 2024).
Lemma C.7 (Initialization of input (Müller & Morris 2024 ). Let G be graph with node features H E gdxN with the degree function dog V + N. For every tokenization ()) = H + P, there exists a parameterization of x (0) such that
for node U E V.
(x)
H HH'()) (v); deg' (w): P'())] E ERRd
(C40)
19

---

Primphormer: Efficient Graph Transformers with Primal Representations
with (())) FFN (deg'(v) (v) + PE(v)), such that H'(v) , R de,ee''u) E RT, and FFN Rd R for d 28 + k, and for every u, V, it holds,
( H(w) + (v) H' (w)
deg(v) deg (w) = deg' (v) deg' (w)
(C41)
P(c) P(w) = P'(v) P (ww).
Moreover, if structure embedding can recover the graph Laplacian, so does P'.
Using the above Lemma, dimension while maintaining unchanged common features.
integrate node and structure information parameterization of X with proper
Next, we give the proof of Theorem 3.4 in the main body.
Theorem C.8. Let G = (V, F,, E) be a labeled graph with N nodes, and node feature matrix x == H E R consistent with the label Then, for all iterations t 2 O, there exists a parameterization of Primphormer such that
C2 (w) = (u) =x((w))
(C42)
for all nodes v, E V, where Ct :
N is the coloring function of the I-WI. test 1-th iteration.
Proof. According to Lemma
C.7 there exists parameterization of the initialization X (0) such that
x (0) (v) = [H' (w); 0; deg' (v); P'(w)]
for each E V and
H(v) = H (w) = (v) H H(ww)
deg(v) deg ()) + deg' (v) = deg' (w)
P(v) = P P(w) = P'(u) = P(w).
with d = 2s + + k. We use the induction method to prove it.
First, according to the definition, we have
(b) (b = H(u) H(w).
Denote (v) as the representation of the color of node iteration f. We set (0) H'))). Demb B such that for i-th column Demb,s deg((v;) where v; is the i-th node in fix but arbitrary node ordering. Then, X can be rewritten as
x (v) = H (v)) O; deg (v); P'u)
and in matrix form,
(0) и (0)) D Dumbi P' E RR
Secondly, suppose the statement holds to iteration t, 2 0. For the induction, we want,
(v) = C++ (w) + HL++)) ( (ww),
which means that the first element of X (++1) should match the 1 W-L-equivalent aggregation,
(++1) H (++1);;;; Dembi p' E 1d
(C43)
Recall Lemma C.4 we know the 1- 1-WL-equivalent aggregation follows,
H (++1) = FFNWL (H()) +2H(
(C44)
where FFNwr. is the feed feed-forward layer to update colors. Then only need to show that our Primphormer simulate C44 to match (C3).
E(x))
e((x) = fx W. (x),
o(x)= W.
with
Jx= F B
(C45)
r(x))
r(x) = fx W, (x)),,
20

---

Primphormer: Efficient Graph Transformers with Primal Representations
By setting W. ( N₂ B 0, and F I (the identity matrix), we can parameterize Primphormer follows:
o(x) e(x) (x),
(C46)
where we set (x)))) | and ΦR (x(x) == (<>)]l with ((x) the projection weight W₂ and Wa with expanded sub-matrices to fit x as
W and k(x) Wg We re-state
Wg [W] q' 9: q:
W w w e Rdxd
(C47)
W W k k: W w E Rd
where W7 W Raxs W q W dx ing output,
W W Raxr and W W R Then, we define the correspond-
q'
o(x W. Wog( X (0) )iag(( q X (2,cml))) = W. W.W, x (0 diag W, x (2,co))
(C48)
where ||A 12,0ol = ||| 1A1122..... IalllAAlll [22] denotes the 12- 12-norm of the each column of A. According to the KKT condi-
tions C2 we have We -i= hr, (2,)) in matrix form We Hr, Φu (x indicating that the row space of
We is spanned by ( }}. Thus, we can re-parameterize We in the row space such that
h
h
h....
h
W. = [0)
Φ (xx
(C49)
h h
h1
hx
where h E R h E IR", h ER" h E R Vi E [N] are weight vectors. Now we can formulate the output of our primal
representation,
oxx H (X (x( (x!1)
(C50)
Hdiag( W. x(1) 112,co1) -1x())
W W, W,X( (1) (,, [22c00)))))
By setting ! W q, W Wt W W zeros, we have
x (1) = H W P' 12)co)) 'p' W T
( P'I2,co))
(C51)
Since the LAP and SPE are permutation-invarian functions, they can universally approximate the eigenfunction f(M)
V M with permutation matrix M where (V, A} is the eigensystem of the (normalized) graph Laplacian. According to
Lemma C.7 we know that the structure embedding P' can also recover the (normalized) graph Laplacian, i.e., PrT p'
L. By setting W4, q W. as [T: 02- we have W.p p' = 0x and W P =
Then o can be re-
parameterized by,
ox (1) Hdiag P' (22 ) pp' p' P'diag() P' (|,00
(C52)
Recall the adjacency matrix (G) without self- and L = D A, we know that Lis- = Dis i.e., P', P = Då, such that diag( co)1) = =
o = -D P H (I-DIIIAAAGG
(C53)
By setting h/ h3, and h to zeros and h (IN(()) (t). we can obtain the output of the "Prim" module as,
Prim(X (1) = x (1) = 00 (9) (Di AGG)D :0:
(C54)
Finally, recalling the model structure FFN(X + Prim(X)) Primphormer computes the next representation X(++) as follows:
x (1+1) FFN X (1) + Prim x ())
H (*),; 0; Demb; P'] + O D - -GG)A( :0:0)
= FFN
(C55)
FFF (); (!))) (D. - A(G) D Dembi P'))
21

---

Primphormer: Efficient Graph Transformers with Primal Representations
and for each node v E VV,
(t) (0)= =FFN (1)) - EmEN(o) [( (w); (og' ('
(C56)
We can define (v) = [ The domain is obviously compact, thus there exists choices of SFUN, Shing - TRd Rdd is continuous. We can use feed-forward layer FFN to approximate fFEN fiin flim o fäeg arbitrarily close. We define fEEN, flimz Jim fdeg follows.
Sdeg ([ [H (0) E
(v)- Em IN(v)) H (w); deg' (v); P'(w))
(C57)
(o): H E EmENO (( deg (v): P'())
(6)
where fdeg multiplies the degree [N() to the second component. Next, fun, conducts a linear transformation such that (b) = x ((b) - (a)),
ftm ( (v);
E | (w)) (v): P'(v)
(C58)
(v): 22 Σ WEN(() |N())I (w): deg deg'u)) P'())
Next, finng conducts a linear transformation such that (a) = (a) [N(b) (b) and (b)= 0.
ftina
(w):: -2 22 E [N(w)) (4) (w) (w): P'(v)
(C55)
(v) (2)++ +2 Σ (eN(v)
H (w): 0: deg' (v); P'())
(a)
Finally, JEEN updates the first component in the same way as FFNWL does in CC4
fPFN
H (() +2
H (1) =
E
EEN(())
deg' P'(v))
FFNWL
(() +2 Σ wEN(o)
(w)) 0; dog'( (v); (')
(C60)
(o): deg''()) (v); P' P'(v)
In matrix form.
X (t+1) = fFEN o fünn a fii o Sacr ([H0H; (D+ (D+-A(G)D-+) D Dembi P!))
(C61)
(++1) 0: Dembi pd]
which completes the proof.
According to Lemma C.5 and Theorem C.8 we know that both Transformer and Primphormer can simulate the 1-WL test in terms of distinguishing non-isomoep graphs.
22

---

Primphormer: Efficient Graph Transformers with Primal Representations
D. Pseudo-code
Algorithm PyTorch-like Pscudo-Code for Primphormer Module.
import torch
import torch,nn
import torch. on. functional as
torch gww.etric. import global mean pool
from torch_geometric. utils import to to_dense_bad batch
class Primphormer Module):
def init _iiit_ (self, in in_dim, out dim, n_heads, Ns, low rank);
super init__t
self. keys out_ding // headd if key dimension. solf,g_proj Ln.iin (in, dim, out_dim) query self.k_proj
Linear (in dim, out_dim) key
colf.va.roo] nn Lineer dim, out_dim) virtual node solf.n heads heads
(Na, n_aeeds, self. keys))) self. Wr Parametee (nn. inn.init, wwt..init..tttiti orthogonal. (torch.Tensor Tensor (Ms, n_heads, self. keyss)) self, Lambda nn. Parameter (nn. init. uni formm (torch. Tensor heads, low_rank))) self. www.enteeweihtt.....eeeeeeeeeeee
self.Ne
(nn.init.... orthogonsl (torch,
Linear 22lko_rrak,, self, keys)
def feature map (selt, :):
Q = F. n.nomallized p=2, dim--1) f.normalized(K, p=2, dim--1) return Q, K
def propagate_ (self, batch, h):
h = salf. vnoffv global pool batch.baten (naqueeze aggregate by virtual node. fx h_vn batch. /t update f_X by the virtual node.
def (srwa batch) batch.x
x dense, mask to dense batch batch. batch
shape batch,
#nodes
fx self. profappop (batch, x)
heads, heads, -1) g solf, p.oj (x danse) vviww (B, M, self.n hoads, -1)
self.q.proj (x_ dense). view (B,
Q, K self, wwaturreetaageeeeee map (Q, K)
compute data-dapandent projections
einsum ('ddv, vhe-obdhe', tx.ttranpose (2, 1), self.We) Nr X torch. einsum ''dv, vhe->bdhe', fx. tx.ntranppose (2, 1), self.We)
compute projection scores
escore torch, einsum(' bmhd,, bhde->bmhe' Q, We x. peruute (0, 2, 3. 11) [mask]
torch. einsum( bmhd, bhde->bmha', K, perrmut (0, 3, [mask]
(escoree, rscore), dim--1) out self self.concate_weetee weight (score) contiguous ()
out. out. view(-1, self.n. heads self,d koys) # output batch.f4 fx fx #update for the next layer
(torch. einsum nhd, hd-2nhd', escore, self Lambda) (dim=-1, p=2)) x*2) .mean
raca_raccore (torch.einsum (' nhd, hd-onhd', rscore, self, Lambda) norm norm(dimea)) (dim=-1, p== *+2) .mean ()
trace einchme loss_ svd (loss_eseas escore joss_rscore loss_ trace) **
peemute 1,
WE) (dimml) .trace ()
return out, loss_avd
23

---

Primphormer: Efficient Graph Transformers with Primal Representations
Algorithm 2 Algorithm for Primphormer in the GPS architecture.
Input: Graph G = (V. with N nodes and M edges; Adjacency matrix A E TRNNNN; Node features X E R Edge features E Rd,xM; Node and edge encoders; Local message passing model instance MPNN,; Primphormer model instance Prim; Positional encoding function fPE: Layers E [L 1].
Output: Node representations X- TRxxN and edge representations EL E RRdxM for downstream tasks.
1: Puodes Pedge
2: Poode, Pedge + [PE E)
3: X - Duode (NodeEncoder(M X), P
4: El + Dddge (EdgeEncoder(()) E)), Podge)
5: for -
6:
X EE+1 +- MPNN (xi, E E A)
7:
X-1 + --rim' (x')
8:
X 4-1 + BatchNorm
Dropout
{ + x
9:
X < BatchNorm
Dropout
x + X
10:
X + MLP' (x M
+ X (+1)
11: end for
Return: X and E
E. Additional experiments
We also conduct experiments to compare against more models (Ma et al. 2023). We report the experimental results in
Table A5
Table A5 Comparisons between method and GRIT Ma al.
2023
MODEL
CIFARIO
MNIST
GPS
ACC1
TOMR(S/FPOCH)
MEMORV((B)
ACCT
TiMe(s/rocC))
MEMORY(GB)
PRIMPHORMER
74.13 + 0.241
32.6
2.74
98. + 0.042
43.7
1.71
GRIT MA AL. 2023
76.46 0.881
158.8
22.8
98.11 0.111
70.1
7.69
We report the performance drop of removing fx in the following table,
Table A6 The removal impact performance of fx.
PASCALVOC
COCO
SETTIDES-FUNC
PEPTIDES PEPTIDES-STRUCT STRUCT
PCQM
PRIMPHORMER
0.4602 + 0.0077 0.3903 + 0.0061
0.6612 + 0.0065
0.2495 + 0.0008
0.3757 + 0.0079
No fx
0.4513 + 0.0089
0.3758 + 0.0082
0.6509 + 0.0072
0.2576 + 0.0011
0.3516 + 0.0126
24


Reviews:
[{"review_id": "lgzW8jFOgl", "reviewer": "Reviewer_kDDD", "summary": "The paper aims to bypass the scale-restricting quadratic complexity of graph transformers with a primal representation of self-attention. This is accomplished by extending the linear-complexity primal representation of self-attention on sequences presented in [1]. The authors identify the lack of ordering in graph data (necessary for permutation equivariance) and the lack of flexibility of the data-adaptive weight as issues in [1]. These are addressed in optimization problem (2.5) with a virtual node allowing for global information collection under permutation equivariance which is then incorporated into projection matrices enabling a data driven dual basis. The duality of (2.5) is established under KKT conditions yielding a primal representation in which pairwise computation can be avoided relying on an asymmetric kernel trick.\n\nThe paper continues with an analysis of Primphormer’s universal approximation property on sequences and graphs, followed by its expressivity in regards to the 1-Weisfeiler-Leman test for subgraph isomorphism. Experiments follow to demonstrate Primphormer’s performance, efficiency, and expressivity compared to baselines for a variety of common datasets and their corresponding tasks.\n\n\n[1] Chen, Y., Tao, Q., Tonin, F., and Suykens, J. A. K. Primal-attention: Self-attention through asymmetric kernel svd in primal representation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and appreciation of this work. We address your concerns below:\n \n- R1.1: The reason for using Sumformer.\n\n> We use Sumformer as a bridge to analyze the approximation. Specifically, we decompose the approximation into two parts: (1) Primphormer to Sumformer and (2) Sumformer to the target function. Leveraging Sumformer allows us to avoid the need for exponentially many attention layers, requiring only one attention layer to represent the Sumformer.\n\n- R1.2: Revised Corollary 3.5.\n\n> Thank you for your insightful comment. We agree with your suggestion that Corollary 3.5 should be revised. Since both the Transformer and Primphormer are capable of simulating the 1-WL test, we claim that there exist parameterizations of the Transformer and Primphormer such that the node features (or colors) produced by these models are identical.\n\n> (Revised corollary 3.5.) Let $G=(V,E,\\ell)$ with $N$ nodes and feature matrix $X^{(0)}\\in\\mathbb{R}^{d\\times N}$ consistent with the label $\\ell$. Then for all iterations $t\\geq 0$, there exist parameterizations of Transformer and Primphormer and a positional encoding such that $X^{(t)}\\_\\mathcal{T}(v)=X^{(t)}\\_\\mathcal{T}(u)\\iff X^{(t)}\\_{\\rm Pri}(v)=X^{(t)}\\_{\\rm Pri}(u)$ for all nodes $v,u\\in V$ where $X^{(t)}\\_\\mathcal{T}$ and $X^{(t)}\\_{\\rm Pri}$ are node features of Transformer and Primphormer, respectively.\n\n- R1.3: Results in Tables 1 and 3.\n\n> Thanks for your careful reading. Table 1 is correct, but the results of Primphormer and GraphGPS+Transformer in Table 3 were not updated (Fortunately, the rankings of the results remain unchanged.). We sincerely apologize for this oversight and ensure that this will be corrected in the final version of the manuscript.\n\n- R1.4: Results of the 1-WL test.\n\n> Table 5 presents the expressive results on the BREC benchmark [1]. The key challenge of this benchmark lies in its distinguishing difficulty, as it includes graphs that are indistinguishable by the (1-WL to 4-WL) tests. Consequently, the 1-WL test fails to distinguish graphs in the BREC benchmark, as demonstrated in the following table.\n>\n>| Model| Basic | Regular |Extension | CFI |\n>| :---: | :---: | :---: | :---: | :---: |\n>| 1-WL  | 0     | 0     | 0     |0      | \n\n- R1.5: The experimental setting regarding runs.\n\n> In our experiments (except Table 5), we reported the average and standard deviation over 10 runs. We will include this description in the final version of the manuscript.\n\n[1] Wang Y, Zhang M. An Empirical Study of Realized GNN Expressiveness. ICML, 2024.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes, Primphormer is compared against several related architectures for a variety of benchmark datasets and their corresponding tasks with the convolutional layer remaining fixed, varying only the self-attention mechanism.", "theoretical_claims": "I found no notable issues with the theoretical claims. However, I was curious as to why Subformer was used for the proof of Theorem 3.2.\n\n\nI believe that Corollary 3.5 is minorly incorrect and also should have a stronger lower-bound. From the proof of Theorem 3.4 it should require positional/structure features and also that the Transformer with such features is strictly more powerful than 1-WL.", "experimental_designs_or_analyses": "Did you check the soundness/validity of any experimental designs or analyses? Please specify which ones, and discuss any issues.\n\nOverall the experimental designs and analysis are fine. However, Primphormer and GraphGPS+Transformer Table 1 and Table 3 the results for PascalVOC-SP do not match. I was not sure if this was simply an oversight. Otherwise, I was curious as to why Primphormer would perform consistently better than GraphGPS+Transformer given the analysis on performance and expressivity.\n\nOriginally, I thought it odd that Table 5 did not include 1-WL given Corollary 3.5. However, if I remember correctly GraphGPS+Transformer and Graphormer, etc. with position information are more powerful than 1-WL, while at least Graphormer is upper-bounded by 3-WL per [2]. I believe this is the reason for its exclusion. I still would be interested in seeing the results of 1-WL just for the sake of comparison.\n\n[2] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. 2022. How powerful are K-hop message passing graph neural networks. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NIPS '22). Curran Associates Inc., Red Hook, NY, USA, Article 345, 4776–4790.", "relation_to_broader_scientific_literature": "The paper advances the state of the art of graph transformers with linear complexity self-attention without the requirement of sparseness in the graph. Though the main concept of a primal-dual formulation is primarily an extension of a previous work on sequence data to graph data, it does have some novel improvement. The analysis and experiments are convincing and Primphormer is something that I would find personally useful.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The other weaknesses of the paper are addressed in other relevant sections. My only additional concern is with the overall novelty as it is primarily an extension of [1] to graphs, but with a data adaptive basis rather than data adaptive weight. However, I find the theoretical and empirical analysis to be quite convincing and help to offset this.", "other_comments_or_suggestions": "Nothing notable", "questions_for_authors": "Tables 1, 2, and 3 appear to report average and standard deviation but it is not specified in the text for how many runs of each architecture. I was unable to find this from a cursory examination of your supplemental materials. Is it the same average over 5 runs as in Table 5?", "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": "gR4RVHgBS5", "reviewer": "Reviewer_3vhH", "summary": "This work presents Primphormer, a graph transformer architecture that leverages a primal-dual framework to reformulate the self-attention mechanism for graphs, which has previously been done for self attention for sequences. Unlike previous graph transformers (such as GraphGPS with a global vanilla Transformer) that compute pairwise attention, leading to quadratic complexity, Primphormer derives a primal representation by integrating a virtual node that aggregates global graph information with learned projection weights. This design reduces the computational and memory costs as expected but also retains the expressiveness and shows competitive performance with prior baselines of efficient graph transformers.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful suggestions. We address your concerns below:\n\n- R2.1: The removal impact performance of $f_X$.\n\n> Following your insightful suggestion, we report the performance drop of removing $f_X$ in the following table.\n>|     |  PascalVOC   |     COCO     | Peptides-Func | Peptides-Struct |    PCQM      |\n>|:------:|:------------:|:------------:|:-------------:|:---------------:|:-------------:|\n>| Metric | F1$\\uparrow$ | F1$\\uparrow$ | AP$\\uparrow$  | MAE$\\downarrow$ | MRR$\\uparrow$ |\n>| Primphormer | 0.4602 ± 0.0077| 0.3903 ± 0.0061 | 0.6612 ± 0.0065   | 0.2495 ± 0.0008  | 0.3757 ± 0.0079 |\n>| No $f_X$ | 0.4513 ± 0.0089| 0.3758 ± 0.0082 | 0.6509 ± 0.0072   | 0.2576 ± 0.0011  | 0.3516 ± 0.0126 |\n>\n> Removing $f_X$ results in lower performance and a higher standard deviation, highlighting its importance in contributing to the model's stability and effectiveness.\n\n- R2.2: Virtual nodes.\n\n> To address the bottleneck in aggregating global information, we can explore the use of multiple or hierarchical virtual nodes:\n\n> (1) Multiple virtual nodes: Introducing multiple virtual nodes instead of a single one can help distribute the burden of global aggregation. Each virtual node could focus on aggregating information from a subset of nodes within the graph. These subsets could be obtained by applying graph partitioning methods [1] before training, thereby reducing the bottleneck effect.\n>\n> (2) Hierarchical virtual nodes: Employing hierarchical virtual nodes enables a multi-level aggregation process. For example, virtual nodes at lower layers could aggregate local information, while higher-level virtual nodes could focus on capturing global information [2]. \n\n>Overall, your comment is highly insightful, and we consider this topic a valuable direction for future research.\n\n- R2.3: Clearer efficiency gains.\n\n> Thank you for your question regarding the gains. Indeed, the previous table may not have been very clear, as it included three metrics across several tasks. To better illustrate the improvements, we now directly report the differences rather than the absolute values. Additionally, we provide the average performance across all tasks for better clarity. The relative gain is defined as $R:=\\frac{\\delta}{L}$, where $\\delta$ represents the difference between the compared method and GPS+Transformer, and $L$ is the value of GPS+Transformer.\n\n>  We present the triplet $(R_A, R_T, R_M)$ where $R_A, R_T$, and $R_M$ denote the relative gains in accuracy, running time, and peak memory usage, respectively. The desired outcome is to achieve a higher $R_A\\uparrow$, alongside lower $R_T\\downarrow$ and $R_M\\downarrow$, reflecting reduced running time and memory usage.\n>| $(R_A\\uparrow, R_T\\downarrow, R_M\\downarrow)$ | Cifar10 | MalNet. |PascalVOC | Peptides-Func | Average |\n>| :--- | :--- | :--- | :--- | :--- | :--- |\n>| GPS+BigBird    | (-2.53\\%, 0.971, -0.262)  | (-1.24\\%, 0.401, -0.923)    | (-26.07\\%, 0.469, -0.362)|(-10.42\\%, 3.054, -0.410) | (-10.07\\%, 1.224, -0.489) |\n>| GPS+Performer  | (-2.26\\%, 0.814, 1.756)   | (-0.92\\%, -0.684, -0.672)    | (-0.32\\%, 0.396, -0.215)|(-0.92\\%, 0.695, -0.089) | (-1.11\\%, 0.305, 0.195) |\n>| GPS+Exphormer  | (3.29\\%, 0.589, 0.454)   | (0.56\\%, -0.732, -0.706)    | (6.40\\%, -0.011, -0.060)|(-0.12\\%, -0.406, -0.431)| (2.53\\%, -0.140, -0.186) |\n>| GPS+Prim-Atten |(-1.02\\%, 0.146, -0.281)  | (-0.57\\%, -0.731, -0.927)   | (-16.38\\%, -0.278, -0.394)|(-1.35\\%, -0.383, -0.601) | (-4.83\\%, -0.311, $\\small\\textbf{-0.550}$) |\n>| GPS+Primphormer| (2.52\\%, 0.164, -0.281)  | (0.13\\%, -0.733, -0.919)   | (6.53\\%, -0.289, -0.396)|(1.18\\%, -0.398, -0.597) | ($\\small\\textbf{2.59}$\\%, $\\small\\textbf{-0.314}$, -0.548) |\n>\n> The table above shows that Primphormer achieves the highest relative gains in accuracy and running time on average, as well as the second-highest (and very close to the best) gain in memory usage. We hope this helps to demonstrate the efficiency gains more clearly.\n\nWe will include the discussion and additional experiments in the final version of the manuscript.\n\n[1] Çatalyürek Ü, et al. More recent advances in (hyper) graph partitioning. ACM Computing Surveys, 2023.\n\n[2] Vonessen C, et al. Next Level Message-Passing with Hierarchical Support Graphs. ArXiv:2406.15852, 2024.", "claims_and_evidence": "- The paper claims that Primphormer can universally approximate continuous functions on graphs while significantly reducing runtime complexity compared to standard GTs. \n- This is supported by- theoretical analysis demonstrating that the primal representation derived via an asymmetric kernel trick which avoids quadratic pairwise computations by integrating global information through a virtual node.\n- Empirical results across a diverse set of benchmarks (e.g., CIFAR10, MalNet-Tiny, ogbn-products) that show competitive performance with improved memory and runtime efficiency over baselines such as Exphormer and traditional Transformer-based approaches.\n- While the use of virtual nodes through f_x transformation is essential as claimed, how does its removal impact performance drop? \n- In addition, a single virtual node may introduce a bottleneck in aggregating global information because of being a single aggregation point. How can this be resolved in principle and keep the overall Primphormer benefits? \n- Also, the evidence for efficiency gains are not clear in Table 4, and the corresponding claim does not seem justified fully in section 4, page 6 (except when graph size is high as in malnet or ogbn-products).", "methods_and_evaluation_criteria": "The method is implemented by having feature maps for queries and keys with learned projection weights (W_e and W_r) and a virtual node via a data-dependent aggregation function (f_X) that captures global graph info and ensures permutation equivariance.\n\nEvaluation is done by replacing the global attention component in GraphGPS with proposed method, and on public graph benchmarks that were used in GraphGPS and subsequent efficient graph transformers.", "theoretical_claims": "A key theoretical claim is that Primphormer is a universal approximator for functions on both sequences and graphs despite using a sparse, efficient attention mechanism. This is justified using the tools employed in previous methods.", "experimental_designs_or_analyses": "Experiment design is done by replacing the global attention component in GraphGPS framework with proposed method, which makes it a fair design.", "relation_to_broader_scientific_literature": "The paper is good positioned within the current literature on scalable/efficient graph transformers and corresponding primal attention works in general transformer literature (eg. Chen et al, 2023).", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "In terms of understanding the contributions of the paper, there may be a concerns, the efficiency gains are not seen clearly in the experiments and the overall contribution is to extend primal attention from general sequential input to graph input while addressing the challenges during generalization.", "other_comments_or_suggestions": "NA", "questions_for_authors": "already included in above sections, eg. in Claims And Evidence section.", "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": "O61XQfOSKV", "reviewer": "Reviewer_1bgR", "summary": "This paper introduces an efficient graph transformer, called Primphormer,  that addresses the quadratic complexity issue of traditional graph transformers by using a primal representation. The authors showed that Primphormer serves as a universal approximator for functions on both sequences and graphs, retaining its expressive power for distinguishing non-isomorphic graphs. Experiments on various graph benchmarks demonstrate that Primphormer achieves competitive empirical results.\n\n## update after rebuttal\nBy considering the additional experiments, I keep my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of the novelty of Primphormer. We address your concerns below:\n\n- R3.1: Broader experiments.\n\n> Following your suggestion, we have compared our method with other efficient graph Transformers such as Polynormer and SGFormer, as illustrated in the following table.\n>| Acc$\\uparrow$ | Computer |  Photo  |   CS   | Physics | WikiCS |\n>|:--------|:--------|:-------|:------|:-------|:------- |\n>| \\#Nodes  |  13,752  |  7,650  | 18,333 | 34,493  | 11,701 |\n>| \\#Edges  | 245,861  | 119,081 | 81,894 | 247,962 | 216,123 |\n>|SGFormer   |92.32±1.66|94.28±1.36| 95.21±1.14 | 96.65±1.26 | 79.48±0.96 |\n>|Exphormer  |91.59±0.31|95.27±0.42| 95.03±0.09 | $\\small{\\textbf{97.16}}$±$\\small\\textbf{0.48}$ | 78.54±0.49 |\n>|Polynormer |$\\small{\\textbf{93.38}}$±$\\small\\textbf{0.13}$|  96.01±0.12  |95.50±0.18|97.12±0.12|79.64±0.67|\n>|Primphormer|92.47±0.55|$\\small{\\textbf{96.22}}$±$\\small\\textbf{0.29}$|$\\small{\\textbf{95.66}}$±$\\small\\textbf{0.22}$|97.02±0.17|$\\small{\\textbf{80.11}}$±$\\small\\textbf{0.84}$|\n>\n> We observed that Primphormer outperforms on three of the five datasets. We hope these results contribute to a comprehensive evaluation of Primphormer's performance.\n\n- R3.2: Presentation, organization, and KSVD.\n\n> Thank you for your insightful suggestions and careful reading. Following your suggestions, we will continue to improve the presentation, particularly in the theoretical section. We believe your feedback will enhance the readability of the manuscript.\n\n> In this paper, we followed a commonly used experimental organization approach in the graph learning community [1,2]. As we are unable to update the PDF during the author-reviewer discussion period, we will revisit the organization based on your suggestion and select one approach for the final version of the manuscript.\n\n> Thank you for your detailed comment. KSVD stands for Kernel Singular Value Decomposition. The KSVD optimization problem mentioned on Line 770 corresponds to our primal optimization problem outlined in Equation 2.5. We will revise this part in the manuscript to improve clarity.\n\nWe will include the experiments and discussion in the final version of the manuscript.\n\n[1] Shirzad H, et al. Exphormer: Sparse transformers for graphs. ICML, 2023.\n\n[2] L Ma, et al. Graph inductive biases in transformers without message passing. ICML, 2023.", "claims_and_evidence": "1. Reduced computational complexity: The paper provides analysis showing that the primal representation used in Primphormer has linear complexity ($O(Nps$) time and $O(2N_ss + 2Np)$ memory), which is significantly more efficient than the quadratic complexity ($O(N^2s$) time and $O(N^2 + Ns)$ memory) of traditional graph transformers. \n2. Theoretical properties: The paper demonstrates through Theorems 3.2 and 3.3 that Primphormer can approximate any continuous function on sequences and graphs arbitrarily well.", "methods_and_evaluation_criteria": "This paper evaluates Primphormer on diverse benchmark datasets, including LRGB, standard GNN benchmarks, molecular datasets, large-scale graph, and graph isomorphism benchmark (BREC). These datasets cover a broad range of graph types and tasks, making them appropriate for comprehensive evaluation.", "theoretical_claims": "I checked the proofs in Appendix C.", "experimental_designs_or_analyses": "Primphormer is tested on a wide range of graph benchmarks, and compared against multiple relevant baselines.The experimental design also includes both running time and memory usage comparisons, which is crucial for validating their claim of improved computational efficiency.  One concern is that it may need to be compared with some more efficient graph transformer approaches, such as [1], [2]. \n\n[1] Polynormer: Polynomial-Expressive Graph Transformer in Linear Time, ICLR 2024\n[2] SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations, NeurIPS 2023", "relation_to_broader_scientific_literature": "This paper proposes a new appraoch of efficient graph transformers.  The proposed Primphformer builds on established concepts from kernel machines, and universal approximation theory, while specifically addressing the unique challenges posed by graph data.", "essential_references_not_discussed": "Please see the Experimental design and analysis, some efficient graph transformers should be cited and compared.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper introduces a novel primal representation for graph transformers that addresses the quadratic complexity issue inherent in traditional self-attention mechanisms.  \n2. Primphormer is proved to be as powerful as Transformer in terms of distinguishing non-isomorphic graphs. \n3. Primphormer is tested on a wide range of graph benchmarks and shows competitive performance.\n\nWeaknesses:\n1. The main contribution of this paper is to design efficient graph transformer, reducing the quadratic complexity to linear. However, it lacks comparisons with other complexity reduction approaches, e.g., some recent advances in efficient attention mechanisms, to name a few [1], [2].\n2. The presentation of this paper could be improved to make it easier to follow, e.g., in the theoretical results section, explain how these theorems relate to the main claims of this paper.\n\n[1] Polynormer: Polynomial-Expressive Graph Transformer in Linear Time, ICLR 2024\n[2] SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations, NeurIPS 2023", "other_comments_or_suggestions": "1. Maybe it is better to organize the experimental results according to different tasks, e.g., for node-level, link-level, and graph-level. Now they are mixed.\n2. What is the KSVD on Line 770?", "questions_for_authors": "I'd like to see more discussions/evaluations with other efficient graph transformer approaches.", "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": "Wpr86pv8Cl", "reviewer": "Reviewer_3RwF", "summary": "This paper proposes a novel Graph Transformer model, named Primphormer, which models the self-attention mechanism in the primal space, avoiding costly pair-wise computations and enabling an efficient variant of Graph Transformers. By introducing an additional primal objective loss, Primphormer achieves high efficiency in terms of both runtime and memory usage, allowing for larger and deeper neural networks and enabling larger batch sizes, thereby enhancing the model's capacity and generalization ability. Furthermore, Primphormer preserves expressive power equivalent to that of traditional Transformers, effectively distinguishing non-isomorphic graphs. Experimental results on various graph benchmarks demonstrate the effectiveness and efficiency of the proposed Primphormer.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of the innovation of Primphormer and insightful comments. We address your concerns below:\n\n- R4.1: Broader experiments.\n\n> Thank you for mentioning the latest baselines, Graph ViT/MLP-mixer [1], GRIT [2], and GEAET [3]. Following your suggestion, we have included comparisons with these methods, as shown in the tables below.\n\n> Table 1 Comparison on the CIFAR10 dataset.\n> |  | Acc$\\uparrow$| Time(s/epoch)$\\downarrow$ | Memory(GB) $\\downarrow$|\n> | :--- | :--- | :---: | :---: |\n> |Graph MLP-Mixer|  73.96±0.33    |   47.5   | 3.11 |\n> |Graph ViT      |  72.11±0.55    |   49.7   | 3.05 |\n> |GRIT           |$\\small{\\textbf{76.46}}$±$\\small\\textbf{0.88}$|158.8 | 22.8 |\n> |GEAET          |  76.33±0.43    | 45.8     | 4.9 |\n> |Primphormer    |  74.13±0.24    | $\\small{\\textbf{32.6}}$ | $\\small{\\textbf{2.7}}$ |\n\n> Table 2 Comparison on the MNIST dataset.\n> |  | Acc$\\uparrow$| Time(s/epoch)$\\downarrow$ | Memory(GB) $\\downarrow$|\n> | :--- | :--- | :---: | :---: |\n> |Graph MLP-Mixer|97.42±0.11|57.2|2.26|\n> |Graph ViT      |97.25±0.23|53.6|2.25|\n> |GRIT           |98.11±0.11|70.1|7.69|\n> |GEAET          |98.41±0.09|49.2|2.11|\n> |Primphormer    |$\\small{\\textbf{98.56}}$±$\\small{\\textbf{0.04}}$|$\\small{\\textbf{43.7}}$|$\\small{\\textbf{1.71}}$|\n>\n> It can be observed that our method achieves the lowest time and memory costs while maintaining competitive performance, which aligns with the motivation of this paper. \n\n> We have also conducted experiments on large graph datasets for node-level tasks, including ogbn-arxiv, ogbn-proteins, and Amazon2m.\n>\n>|  | ogbn-arxiv |  ogbn-proteins  |   Amazon2m   |\n>|:--------|:--------|:-------|:------|\n>| \\#Nodes  |  169,343 |  132,534  | 2,449,029 |\n>| \\#Edges  | 1,166,243| 39,561,252| 61,589,140 | \n>|NodeFormer |59.90±0.42|77.45±1.15| 87.85±0.24 |\n>|SGFormer   |72.63±0.13|$\\small{\\textbf{79.53}}$±$\\small{\\textbf{0.38}}$| 89.09±0.10|\n>|Primphormer|$\\small{\\textbf{73.10}}$±$\\small{\\textbf{0.24}}$|78.93±0.31|$\\small{\\textbf{90.33}}$±$\\small{\\textbf{0.32}}$|\n>\n> We hope these results contribute to a comprehensive evaluation of Primphormer's performance.\n\n- R4.2: Discussion with other linear attention methods.\n\n> Linear attention mechanisms, such as NodeFormer [4] and SGFormer [5], aim to reduce computational complexity by decomposing or approximating the kernel matrix, operating in the dual space. For example, NodeFormer uses a random feature-based approach, while SGFormer drops the softmax activation to approximate the kernel matrix. In contrast, our method adopts a technically different approach by leveraging the asymmetric kernel trick. Instead of operating in the dual space, we directly model the representation of attention outputs in the primal space.\n\nWe will include the experiments and discussion in the final version of the manuscript.\n\n[1] X He, et al. A generalization of vit/mlp-mixer to graphs. ICML, 2023.\n\n[2] L Ma, et al. Graph inductive biases in transformers without message passing. ICML, 2023.\n\n[3] J Liang, M Chen and J Liang. Graph External Attention Enhanced Transformer. ICML, 2024.\n\n[4] Wu Q, et al. Nodeformer: A scalable graph structure learning transformer for node classification. NeurIPS, 2022.\n\n[5] Wu Q, et al. SGFormer: Simplifying and empowering transformers for large-graph representations[J]. NeurIPS, 2023.", "claims_and_evidence": "The paper provides convincing experimental results and theoretical evidence to support its claims.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are suitable for the given problem and application context.", "theoretical_claims": "I have reviewed the theoretical content of this paper, and there are no significant issues. For example, Theorem 2.2's duality derivation and the introduction of the KKT conditions are sound and consistent with related optimization theory. Lemma 2.3 effectively shows that the solutions in the dual space lead to a zero-valued objective in the primal space, which aligns with common results in duality theory. Furthermore, Theorem 3.2 provides a rigorous proof of the approximation ability of Primphormer for any continuous function, confirming its strong performance. Overall, the theoretical derivations in the paper are correct.", "experimental_designs_or_analyses": "I have reviewed the experimental design of this paper and found some issues. Specifically, the paper does not compare the latest baselines. For instance, it does not include comparisons with the GRIT [2] model and Graph ViT [1] model from ICML 2023, nor the GEAET [3] model from ICML 2024. These models have significant impact in the field of graph representation learning, and the lack of comparison could affect the comprehensive evaluation of Primphormer's performance.\n\n[1] X He, et al. A generalization of vit/mlp-mixer to graphs. ICML, 2023.\n\n[2] L Ma, et al. Graph inductive biases in transformers without message passing. ICML, 2023.\n\n[3] J Liang, M Chen and J Liang. Graph External Attention Enhanced Transformer. ICML, 2024.", "relation_to_broader_scientific_literature": "The key contribution of the paper is the introduction of Primphormer, based on primal space, which improves efficiency by avoiding pairwise computations. Unlike existing methods, Primphormer uses a dual approach to reduce computational complexity while maintaining expressiveness.", "essential_references_not_discussed": "The paper overlooks Graph ViT [1] and GRIT [2] from ICML 2023, as well as GEAET [3] from ICML 2024, which could serve as meaningful comparison baselines.\n\n[1] X He, et al. A generalization of vit/mlp-mixer to graphs. ICML, 2023.\n\n[2] L Ma, et al. Graph inductive biases in transformers without message passing. ICML, 2023.\n\n[3] J Liang, M Chen and J Liang. Graph External Attention Enhanced Transformer. ICML, 2024.", "other_strengths_and_weaknesses": "Strengths:  \n-The proposed method is innovative.  \n-The theoretical analysis is thorough and detailed.  \n\nWeaknesses：  \n-The performance of the proposed method is not particularly outstanding, and several models from 2023/2024 are not compared, such as GRIT, Graph ViT from ICML 2023, and GEAET from ICML 2024.  \n-The paper claims to be an Efficient Graph Transformer, but it lacks testing on large graph datasets and only evaluates on graph-level tasks.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. The proposed method in this paper seems similar to linear attention methods. Could the authors explain the differences between the two approaches? Additionally, could the authors highlight the advantages of the proposed method compared to Graph Transformer methods with linear attention, such as Nodeformer from NeurIPS 2022 and SGFormer from NeurIPS 2023?\n2. Could the authors provide performance results on large graph datasets?", "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:

Meta-review: This paper introduces a linear-time self-attention for graphs based on primal representation. All reviewers acknowledged that both the technical and empirical contributions of the paper are solid. The main concerns raised by the reviewers include: (1) missing analysis on the impact of virtual node, (2) concerns regarding information bottleneck in aggregating global graph information into a single virtual node, (3) missing comparisons to efficient graph transformer methods, (4) missing comparisons to graph representation learning approaches, and (5)  missing results on larger graph datasets. The authors provided a comprehensive rebuttal addressing most of these concerns, leading the consensus among reviewers to recommend the acceptance. After reading the paper, reviews, and rebuttal, AC agrees with the reviewers' decision and recommends acceptance.
Decision: Accept (poster)