VecFormer: Towards Efficient and Generalizable Graph Transformer with Graph Token Attention

Jingbo Zhou; Jun Xia; Siyuan Li; Yunfan Liu; Wenjun Wang; Yufei Huang; Changxi Chi; Mutian Hong

cs.LGFeb 23, 2026

VecFormer: Towards Efficient and Generalizable Graph Transformer with Graph Token Attention

Authors: Jingbo Zhou, Jun Xia, Siyuan Li, Yunfan Liu, Wenjun Wang, Yufei Huang, Changxi Chi, Mutian Hong,

Organizations: Zhejiang University Hangzhou, Zhejiang, China · Westlake University Hangzhou, Zhejiang, China · Hong Kong University of Science and Technology (Guangzhou) Guangzhou, Guangdong, China · Tongji University Shanghai, China ·

Abstract

Graph Transformer has demonstrated impressive capabilities in the field of graph representation learning. However, existing approaches face two critical challenges: (1) most models suffer from exponentially increasing computational complexity, making it difficult to scale to large graphs; (2) attention mechanisms based on node-level operations limit the flexibility of the model and result in poor generalization performance in out-of-distribution (OOD) scenarios. To address these issues, we propose VecFormer (the Vector Quantized Graph Transformer), an efficient and highly generalizable model for node classification, particularly under OOD settings. VecFormer adopts a two-stage training paradigm. In the first stage, two codebooks are used to reconstruct the node features and the graph structure, aiming to learn the rich semantic Graph Codes. In the second stage, attention mechanisms are performed at the Graph Token level based on the transformed cross codebook, reducing computational complexity while enhancing the model's generalization capability. Extensive experiments on datasets of various sizes demonstrate that VecFormer outperforms the existing Graph Transformer in both performance and speed.

Figures & tables

Figure 1. Standard deviation of attention weights and performance evaluation of Node Level Attention and Graph Token Attention in OOD setting.

Figure 2. Illustration of the VecFormer’s architecture and the training process.

Notation	Meaning
$\mathcal{G}$	Attribute Graph
$N$	Number of nodes
$A$	Adjacency matrix
$T$	Temperature parameter
${X}\in\mathbb{R}^{n\times d}$	Feature matrix
$H\in\mathbb{R}^{n\times d^{\prime}}$	GNN’s output matrix

Table 1. Basic notation and their meanings.

Category	Model	Pubmed	CoraFull	Computer	Photo	CS	Physics
	GCN	87.36 $\pm$ 0.35	67.44 $\pm$ 0.64	91.08 $\pm$ 0.62	94.44 $\pm$ 0.57	93.40 $\pm$ 0.24	96.53 $\pm$ 0.14
GNN	GAT	86.12 $\pm$ 0.44	66.74 $\pm$ 0.75	91.31 $\pm$ 0.45	94.46 $\pm$ 0.69	93.70 $\pm$ 0.29	96.47 $\pm$ 0.19
	SAGE	87.83 $\pm$ 0.34	68.59 $\pm$ 0.80	90.29 $\pm$ 0.68	94.03 $\pm$ 0.69	93.04 $\pm$ 0.26	96.29 $\pm$ 0.17
	GOAT	89.15 $\pm$ 0.39	53.30 $\pm$ 3.89	88.95 $\pm$ 1.00	92.11 $\pm$ 0.95	89.96 $\pm$ 0.63	96.27 $\pm$ 0.30
	GraphGPS	87.72 $\pm$ 0.30	59.11 $\pm$ 2.22	87.62 $\pm$ 0.68	94.18 $\pm$ 0.64	95.42 $\pm$ 0.28	97.05 $\pm$ 0.18
	NodeFormer	81.87 $\pm$ 2.24	60.14 $\pm$ 2.97	85.69 $\pm$ 1.25	93.82 $\pm$ 0.97	95.07 $\pm$ 0.39	96.80 $\pm$ 0.63

Table 2. Node classification performance (%) of VecFormer and three types of GNNs. The best results are in bold, and the second-best results are underlined.

Model	Cora		Citeseer		Twitch
Model	OOD	ID	OOD	ID	OOD1	OOD2	OOD3	ID
ERM	91.10 $\pm$ 2.26	95.57 $\pm$ 0.40	82.60 $\pm$ 0.51	89.02 $\pm$ 0.32	65.67 $\pm$ 0.02	52.00 $\pm$ 0.10	61.85 $\pm$ 0.05	75.75 $\pm$ 0.15
IRM	91.63 $\pm$ 1.27	95.72 $\pm$ 0.31	82.73 $\pm$ 0.37	89.11 $\pm$ 0.36	67.27 $\pm$ 0.19	52.85 $\pm$ 0.15	62.40 $\pm$ 0.24	75.30 $\pm$ 0.09
Coral	91.82 $\pm$ 1.30	95.74 $\pm$ 0.39	82.44 $\pm$ 0.58	89.05 $\pm$ 0.37	67.12 $\pm$ 0.03	52.61 $\pm$ 0.01	63.41 $\pm$ 0.01	75.20 $\pm$ 0.01
DANN	92.40 $\pm$ 2.05	95.66 $\pm$ 0.28	82.49 $\pm$ 0.67	89.02 $\pm$ 0.31	66.59 $\pm$ 0.38	52.88 $\pm$ 0.12	62.47 $\pm$ 0.32	75.82 $\pm$ 0.27
GroupDRO	90.54 $\pm$ 0.94	95.38 $\pm$ 0.23	82.64 $\pm$ 0.61	89.13 $\pm$ 0.27	67.41 $\pm$ 0.04	52.99 $\pm$ 0.08	62.29 $\pm$ 0.03	75.74 $\pm$ 0.02

Table 3. Results of classification accuracy (%) on OOD datasets. The best results are in bold, and the second-best results are underlined.

\Delta_{OODM}

and

\Delta_{GT}

represent the performance improvement of VecFormer compared to the best-performing OOD method and Graph Transformer on each dataset, respectively.

Model	Ogbn-proteins	Amazon2m	Pokec
# nodes	132,534	2,449,029	1,632,803
# edges	39,561,252	61,859,140	30,622,564
MLP	72.04 $\pm$ 0.48	63.46 $\pm$ 0.10	60.15 $\pm$ 0.03
GCN	72.51 $\pm$ 0.35	83.90 $\pm$ 0.10	62.31 $\pm$ 1.13
SGC	70.31 $\pm$ 0.23	81.21 $\pm$ 0.12	52.03 $\pm$ 0.84
GCN-NSampler	73.51 $\pm$ 1.31	83.84 $\pm$ 0.42	63.75 $\pm$ 0.77

Table 4. Performance comparison (%) of different methods on large datasets. The best results are in bold, and the second-best results are underlined.

Figure 3. Experimental results(%) for node classification task on heterophily graph datasets Chameleon and Squirrel.

Figure 4. The training time per epoch and GPU memory usage of three linear-complexity graph transformers on graphs with varying numbers of nodes.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Feature Codebook Size	Structure Codebook Size	$N_{f}$	$N_{s}$
Pubmed	256	256	64	64
CoraFull	256	256	64	64
Computer	256	256	64	64
Photo	256	256	64	64
CS	256	256	64	64
Physics	256	256	64	64

Appendix

Table 5. Hyper-parameter settings of our proposed method.

Dataset	# Nodes	# Edges	# Feature Dims	# Classes
Pubmed	19,717	44,324	500	3
CoraFull	19,793	126,842	8,710	70
Computer	13,752	245,861	767	10
Photo	7,650	119,081	745	8
CS	18,333	81,894	6,805	15
Physics	34,493	247,962	8,415	5

Appendix

Table 6. The statistical information of eight datasets.

Figure 5. Reconstruction losses of different types and the total loss under varying numbers of Graph Codes .

Model	$k=5$	$k=10$	$k=20$
GCN	$0.1286\pm 0.1462$	$0.0085\pm 0.0420$	$0.0031\pm 0.0148$
VecFormer (GCN backbone)	$\textbf{0.1490}\pm\textbf{0.2251}$	$\textbf{0.0699}\pm\textbf{0.1566}$	$\textbf{0.1000}\pm\textbf{0.1989}$
$\Delta$ DES vs. GCN	$+0.0204\;(+15.9\%)$	$+0.0614\;(+722.4\%)$	$+0.0969\;(+3125.8\%)$
GAT	$0.0316\pm 0.0197$	$0.0244\pm 0.0148$	$0.0445\pm 0.0358$
VecFormer (GAT backbone)	$\textbf{0.1322}\pm\textbf{0.2226}$	$\textbf{0.1298}\pm\textbf{0.2045}$	$\textbf{0.1445}\pm\textbf{0.1829}$
$\Delta$ DES vs. GAT	$+0.1006\;(+318.4\%)$	$+0.1054\;(+432.8\%)$	$+0.1000\;(+224.7\%)$

Appendix

Table 7. DES (mean

\pm

std) on the VCC test set under different

k

-NN graph densities. We additionally report the mean improvement of VecFormer over its corresponding backbone:

\Delta

DES (absolute gain in mean DES) with relative improvement in parentheses.

Figure 6. VecFormer’s performance(%) under varying numbers of Graph Tokens .

Figure 7. $t$ -SNE visualization of attention weights on OOD datasets.

Graph Transformer

Graph Transformers adapt self-attention to represent relationships, topology, and long-range dependencies in graph-structured data.

See all 100 papers

TopoFormer: Topology Meets Attention for Graph Learning
Jul 30, 2026Md Joshem Uddin, Astrit Tola, Cuneyt Gurcan Akcora +1Graph Representation Learning Graph Classification
Department of Mathematical Science The University of Texas at Dallas Richardson, TX 75080, USA · Department of Mathematics Florida State University Tallahassee, FL 32306, USA · AI Initiative University of Central Florida Orlando, FL 32816, USA
Graph Tokenization for Bridging Graphs and Transformers
Mar 11, 2026Zeyuan Guo, Enmao Diao, Cheng Yang +1Graph Representation Learning Transformer
Beijing University of Posts and Telecom., Beijing 100876, China · DreamSoul
The Universal Classifier for Graph Learning
Sep 28, 2026Ben Finkelshtein, André Linhares, Petar Veličković +2Graph Representation Learning Graph Foundation Models
Google Research · Google DeepMind

Jul 30, 2026J/K move · Enter open · S save

TopoFormer: Topology Meets Attention for Graph Learning

Md Joshem Uddin, Astrit Tola, Cuneyt Gurcan Akcora, Baris Coskunuzer

Department of Mathematical Science The University of Texas at Dallas Richardson, TX 75080, USA · Department of Mathematics Florida State University Tallahassee, FL 32306, USA · AI Initiative University of Central Florida Orlando, FL 32816, USA

Graph Representation Learning Graph Classification Graph Transformer Topological Representation Learning Molecular Representation Learning

Open paper AskPDF arXiv

We introduce Topoformer, a lightweight and scalable framework for graph representation learning that encodes topological structure into attention-friendly sequences. At the core of our method is Topo-Scan, a novel module that decomposes a graph into a short, ordered sequence of topological tokens by slicing over node or edge filtrations. These sequences capture multi-scale structural patterns, from local motifs to global organization, and are processed by a Transformer to produce expressive graph-level embeddings. Unlike traditional persistent homology pipelines, Topo-Scan is parallelizable, avoids costly diagram computations, and integrates seamlessly with standard deep learning architectures. We provide theoretical guarantees on the stability of our topological encodings and demonstrate state-of-the-art performance across graph classification and molecular property prediction benchmarks. Our results show that Topoformer matches or exceeds strong GNN and topology-based baselines while offering predictable and efficient compute. This work opens a new path for parallelizable and unifying approaches to graph representation learning that integrate topological inductive biases into attention frameworks.

Abstract

Graph Transformer

Explore similar work

TopoFormer: Topology Meets Attention for Graph Learning

Graph Tokenization for Bridging Graphs and Transformers

The Universal Classifier for Graph Learning