Primphormer: Efficient Graph Transformers with Primal Representations

Thank you for your appreciation of the innovation of Primphormer and insightful comments. We address your concerns below:

• R4.1: Broader experiments.

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.

Table 1 Comparison on the CIFAR10 dataset.

	Acc$\uparrow$	Time(s/epoch)$\downarrow$	Memory(GB) $\downarrow$
Graph MLP-Mixer	73.96±0.33	47.5	3.11
Graph ViT	72.11±0.55	49.7	3.05
GRIT	$\small{**76.46**}$±$\small**0.88**$	158.8	22.8
GEAET	76.33±0.43	45.8	4.9
Primphormer	74.13±0.24	$\small{**32.6**}$	$\small{**2.7**}$

Table 2 Comparison on the MNIST dataset.

	Acc$\uparrow$	Time(s/epoch)$\downarrow$	Memory(GB) $\downarrow$
Graph MLP-Mixer	97.42±0.11	57.2	2.26
Graph ViT	97.25±0.23	53.6	2.25
GRIT	98.11±0.11	70.1	7.69
GEAET	98.41±0.09	49.2	2.11
Primphormer	$\small{**98.56**}$±$\small{**0.04**}$	$\small{**43.7**}$	$\small{**1.71**}$

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.

We have also conducted experiments on large graph datasets for node-level tasks, including ogbn-arxiv, ogbn-proteins, and Amazon2m.

	ogbn-arxiv	ogbn-proteins	Amazon2m
#Nodes	169,343	132,534	2,449,029
#Edges	1,166,243	39,561,252	61,589,140
NodeFormer	59.90±0.42	77.45±1.15	87.85±0.24
SGFormer	72.63±0.13	$\small{**79.53**}$±$\small{**0.38**}$	89.09±0.10
Primphormer	$\small{**73.10**}$±$\small{**0.24**}$	78.93±0.31	$\small{**90.33**}$±$\small{**0.32**}$

We hope these results contribute to a comprehensive evaluation of Primphormer's performance.

• R4.2: Discussion with other linear attention methods.

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.

We will include the experiments and discussion in the final version of the manuscript.

[1] X He, et al. A generalization of vit/mlp-mixer to graphs. ICML, 2023.

[2] L Ma, et al. Graph inductive biases in transformers without message passing. ICML, 2023.

[3] J Liang, M Chen and J Liang. Graph External Attention Enhanced Transformer. ICML, 2024.

[4] Wu Q, et al. Nodeformer: A scalable graph structure learning transformer for node classification. NeurIPS, 2022.

[5] Wu Q, et al. SGFormer: Simplifying and empowering transformers for large-graph representations[J]. NeurIPS, 2023.

Thank you for your appreciation of the novelty of Primphormer. We address your concerns below:

• R3.1: Broader experiments.

Following your suggestion, we have compared our method with other efficient graph Transformers such as Polynormer and SGFormer, as illustrated in the following table.

Acc$\uparrow$	Computer	Photo	CS	Physics	WikiCS
#Nodes	13,752	7,650	18,333	34,493	11,701
#Edges	245,861	119,081	81,894	247,962	216,123
SGFormer	92.32±1.66	94.28±1.36	95.21±1.14	96.65±1.26	79.48±0.96
Exphormer	91.59±0.31	95.27±0.42	95.03±0.09	$\small{**97.16**}$±$\small**0.48**$	78.54±0.49
Polynormer	$\small{**93.38**}$±$\small**0.13**$	96.01±0.12	95.50±0.18	97.12±0.12	79.64±0.67
Primphormer	92.47±0.55	$\small{**96.22**}$±$\small**0.29**$	$\small{**95.66**}$±$\small**0.22**$	97.02±0.17	$\small{**80.11**}$±$\small**0.84**$

We observed that Primphormer outperforms on three of the five datasets. We hope these results contribute to a comprehensive evaluation of Primphormer's performance.

• R3.2: Presentation, organization, and KSVD.

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.

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.

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.

We will include the experiments and discussion in the final version of the manuscript.

[1] Shirzad H, et al. Exphormer: Sparse transformers for graphs. ICML, 2023.

[2] L Ma, et al. Graph inductive biases in transformers without message passing. ICML, 2023.

Thank you for your insightful suggestions. We address your concerns below:

• R2.1: The removal impact performance of $f_X$.

Following your insightful suggestion, we report the performance drop of removing $f_X$ in the following table.

	PascalVOC	COCO	Peptides-Func	Peptides-Struct	PCQM
Metric	F1$\uparrow$	F1$\uparrow$	AP$\uparrow$	MAE$\downarrow$	MRR$\uparrow$
Primphormer	0.4602 ± 0.0077	0.3903 ± 0.0061	0.6612 ± 0.0065	0.2495 ± 0.0008	0.3757 ± 0.0079
No $f_X$	0.4513 ± 0.0089	0.3758 ± 0.0082	0.6509 ± 0.0072	0.2576 ± 0.0011	0.3516 ± 0.0126

Removing $f_X$ results in lower performance and a higher standard deviation, highlighting its importance in contributing to the model's stability and effectiveness.

• R2.2: Virtual nodes.

To address the bottleneck in aggregating global information, we can explore the use of multiple or hierarchical virtual nodes:

(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.

(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].

Overall, your comment is highly insightful, and we consider this topic a valuable direction for future research.

• R2.3: Clearer efficiency gains.

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.

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.

$(R_A\uparrow, R_T\downarrow, R_M\downarrow)$	Cifar10	MalNet.	PascalVOC	Peptides-Func	Average
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)
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)
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)
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**-0.550**$)
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**2.59**$%, $\small**-0.314**$, -0.548)

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.

We will include the discussion and additional experiments in the final version of the manuscript.

[1] Çatalyürek Ü, et al. More recent advances in (hyper) graph partitioning. ACM Computing Surveys, 2023.

[2] Vonessen C, et al. Next Level Message-Passing with Hierarchical Support Graphs. ArXiv:2406.15852, 2024.

Thanks for your insightful comments and appreciation of this work. We address your concerns below:

• R1.1: The reason for using Sumformer.

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.

• R1.2: Revised Corollary 3.5.

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.

(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.

• R1.3: Results in Tables 1 and 3.

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.

• R1.4: Results of the 1-WL test.

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.

Model	Basic	Regular	Extension	CFI
1-WL	0	0	0	0

• R1.5: The experimental setting regarding runs.

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.

[1] Wang Y, Zhang M. An Empirical Study of Realized GNN Expressiveness. ICML, 2024.