Learning Graph Quantized Tokenizers
Authors: Limei Wang
Kaveh Hassani
Si Zhang
Dongqi Fu
Baichuan Yuan
Weilin Cong
Zhigang Hua
Hao Wu
Ning Yao
Bo Long
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Learning
Graph Tokenization
Graph Transformer
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce a quantized graph tokenizer that is trained using multi-task self-supervised objectives.

Abstract: Transformers serve as the backbone architectures of Foundational Models, where domain-specific tokenizers allow them to adapt to various domains. Graph Transformers (GTs) have recently emerged as leading models in geometric deep learning, outperforming Graph Neural Networks (GNNs) in various graph learning tasks. However, the development of tokenizers for graphs has lagged behind other modalities, with existing approaches relying on heuristics or GNNs co-trained with Transformers. To address this, we introduce GQT (\textbf{G}raph \textbf{Q}uantized \textbf{T}okenizer), which decouples tokenizer training from Transformer training by leveraging multi-task graph self-supervised learning, yielding robust and generalizable graph tokens. Furthermore, the GQT utilizes Residual Vector Quantization (RVQ) to learn hierarchical discrete tokens, resulting in significantly reduced memory requirements and improved generalization capabilities. By combining the GQT with token modulation, a Transformer encoder achieves state-of-the-art performance on 20 out of 22 benchmarks, including large-scale homophilic and heterophilic datasets. The implementation is publicly available at \href{https://github.com/limei0307/GQT}{https://github.com/limei0307/GQT}.

Published as a conference paper at ICLR 2025
LEARNING GRAPH QUANTIZED TOKENIZERS
Limei Wang, Kaveh Hassani', Si Zhang, Dongqi Fu, Baichuan Yuan, Weilin Cong, Zhigang Hua, Hao Wu, Ning Yao, Bo Long
Meta AI
ABSTRACT
Transformers serve as the backbone architectures of Foundational Models, where domain-specifie tokenizers allow them to adapt to various domains. Graph Trans- formers (GTs) have recently emerged as leading models in geometric deep learning, outperforming Graph Neural Networks (GNNs) in various graph learning tasks. However, the development of tokenizers for graphs has lagged behind other modal- ities, with existing approaches relying on heuristics or GNNs co-trained with Transformers. To address this, we introduce GQT (Graph Quantized Tokenizer), which decouples tokenizer training from Transformer training by leveraging multi- task graph self-supervised learning, yielding robust and generalizable graph tokens. Furthermore, the GQT utilizes Residual Vector Quantization (RVQ) to learn hierar- chical discrete tokens, resulting in significantly reduced memory requirements and improved generalization capabilities. By combining the GQT with token modu- lation, Transformer encoder achieves state-of-the-art performance 20 out of 22 benchmarks, including large-scale homophilic and heterophilic datasets. The implementation is publicly available at hhttps://githubb... http://hhhhbbomm//////33////////
INTRODUCTION
Following the success of Transformers (Vaswani et al. 2017 in Natural Language Processing (Devlin
al. 2019 Brown al. 2020) and Computer Vision (Dosovitskiy et al. 202T). Graph Transformers
(GTs) (Dwivedi & Bresson| 2020 Ying et al. 2021 Rampasek et al. [022] Shirzad et al. 2023 Chen
al.
2023] Wu et 2022 have emerged as strong models in geometric deep learning. In contrast
to message-passing Graph Neural Networks (GNNs), which are inherently constrained by strong
locality inductive biases (Battaglia al. 2018 Veličković et al. 2018 Hou et al. 2020; Hamilton
ett al. 2017 Kipf & Welling 2017 Zheng al. 2024). GTs exhibit greater expressivity due their
capacity to capture long-range interactions between nodes (Ma et al. [0233] Kim et al. [022]] Zopf
2022). This is particularly beneficial in heterophilic settings where local aligmment does not hold
(Fu et al. 2024). This dichotomy highlights a fundamental trade-off between GNNs, which focus on local neighborhood aggregation, and GT's which employ pairwise attention to model global graph structures. A natural question arises: can we synergistically integrate the strengths of both approaches leverage the complementary benefits of local and global representations? Specifically, is possible to harness the locality-awas aware representations learned by GNNs to construct discrete tokens, thereby enabling GTs to operate efficiently while still capturing salient graph properties?
GTs require consideration of both graph structure and features, as nodes with identical features will otherwise projected into the same representation regardless of their surrounding structures (Hoang et al. 2024). There are three general approaches to address this limitation (Hoang et al.) 2024): (1) node feature modulation, which involves injecting structural information into the node features; (2) context node sampling, where sampling strategy is used to construct sequence over the neighbor nodes; and (3) modifying the architecture of vanilla Transformer to directly incorporate structural biases. Given that Transformers are universal approximators of sequence-tor sequence-to-sequenee -os-uuenceee functions (Yun et al. (020)) and considering the rapid developments in efficient implementation of Multi-Head Attention (MHA) module (Dao et al. 2022 Liu al. 2024). which enables longer context sizes (Reid et al. 2024), we argue that a well-designed graph tokenizer can allow a vanilla
"Equal Contributions

---

Published as a conference paper at ICLR 2025
Transformer to efficiently process even large-scale graphs. Recent studies on applying Large Language Models (LLMs) to Text-Attib Graphs (TAGs) have shown surprisingly strong performance gains surpassing those of GNNs, suggesting that vanilla Transformers
indeed capable of effectively learning graph structures (Ye et al. 2024 Xu et al. 2025). Nonetheless, L.LMs are not efficient at inference time. Our goal is to devise lightweight and efficient graph tokenizater that allows vanilla Transformer encoders to learn graph structures effectively.
Tokenizers typically employ self-supervised objectives abstract data into sequence of discrete tokens, allowing Transformers to learn representations across various modalities as unified stream of data. The discretization usually achieved through vector quantization techniques (Van Den Oord et al., 2017: [ee et al.) 2022), which offer several benefits, including: (1) significantly reduced memory requiremets, (2) improved inference efficiency, (3) allowing Transformers
focus on long-range dependencies rather than local information, and (4) the capacity to learn more high-level representations due to a compact latent space (Yuan al. [021] Yu al., 2022a). These advantages particularly important in auto-regressive generative modeling, where quantized tokens allow Transformers to generate high-quality outputs multiple modalities (Dubey et al. 2024; Lee et al. 2022, Dhariwal et al., 2020 Ramesh et al. 2021: Team 2024). Despite its importance in other domains, tokenization remains under-explored for graph-structured data. To address this limitation, we propose the Graph Quantized Tokenizer (GQT), novel approach that learns hierarchical sequence of tokens over graphs using self-supervised objectives tailored to graph-structured data. More specifically, our contributions are as follows:
We propose graph tokenizer that uses multi-task graph self-super learning to train graph encoder, enabling it to fully capture local interactions and allowing the Transformer to focus on long-range dependencies.
Our approach adapts Residual Vector Quantization (RVQ) within the graph tokenizer to learn hierarchical discrete tokens, resulting in significantly reduced memory requirements and improved generalization capabilities.
We introduce novel combination of semantic edges and random walks to facilitate access to long-range interactions, and employ hierarchical encoding and gating mechanisms to modulate the tokens and provide informative representations to the Transformer.
Through extensive experiments on both homophilic and heterophilic datasets, including large-scale and long-range benchmarks, we demonstrate that our tokenizer enables Trans- former encoders to achieve state-of-the-art performance on 20 out of 22 benchmarks while substantially reducing the memory footprint of the embeddings.
2 RELATED WORKS
Graph Transformers (GTss have shown promising performance on various graph learning tasks, surpassing GNNs on many benchmarks. Designing GT's can broadly categorized into two directions (Hoang et al. 2024 Müller et al., 2 (1) modifying the vanilla Transformer architecture to incorporate structural inductive biases, or (2) encoding the input graph to make it compatible with the vanilla Transformer. Early examples of the first approach include Graph Attention Network (GAT) (Veličković et al. 2018), which uses an attention module to compute pairwise node attention and masks the attention matrix based on connectivity information. Subsequent works have replaced
the scaled-dot attention module with various structure-awars sparse attention modules (Rampášek]
al. 2022
Bo et al. 2023 Ying al. 2021 Deng et al., 2024 Wu al. 2023b Liu et al.) 2023a]
Chen et al.
2022 Dwivedi & Bresson 2020 Shirzad et al. 2023) 23 Ma et al. (023). Graph Memory
Network (GMN) Khasahmadi al. (020) an example of the second approach. which passes non-
model. Structural encodings such Laplacian eigenvectors or Random walk-based encoding (Dwivedi et al. 2022a
linear projections of node features and structural encoding to a Transformer-
Ma et al. 2023] Cantürk et al. 2024), allow injecting structural information directly into the node features. Some works use GNNs to encode local structure along with node features into embeddings that are passed to vanilla Transformers to capture long-range dependencies (Rong et al.) 2020: Wu jt al. 2 Chen et al. 2023 2022). Recent studies leverage LLMs, where graphs are represented through natural language, and LLM performs graph-related tasks through in-context learning, instruction -utiinngttnnnn.... or soft- prompprompiin (Fatemi et al., [024 Ye et al. 2024: He et al. 2024). For a
detailed survey GT's, see (Müller al. 2024 Hoang et al. 2024
2

---

Published as a conference paper at ICLR 2025
Graph Tokenization provides GTs with rich node tokens that encapsulate both structural and semantic information. TokenGT (Kim et al.] al.] (2022) treats nodes and edges as independent tokens defined by their features, type identifiers, and structural encodings. NAGphormer (Chen et al.) 2023) represents each node as a set of I. tokens, where the 1 token is the representation of the node from the 1th hop aggregation. In contrast, GraphiT (Mialon al. 2021) defines node token as the concatenation of its feature and representation from graph convolutional kernel network (GCKN). VCR- Cra-Graphrreer (Fu et al. 2024) expands the notion of node tokens include sequences comprising the node feature and features of semantically and community-
neighboring nodes. SGT (Liu et al., (023c) is a non con--aaamttiie tokenizer designed for molecular tasks, which unlike motif-based tokenizers (Zhng et al., 2021 Jin et al. 2018) or GNN pre-training methods (Xia et al., 2023), simplifies the tokenization process to a non-parametric graph operator without non-linearity. NodePiece (Galkin et al. 2022) is a inowledge-graph tokenizer that represents a target node as hash of its top-k closest anchors, their distances, and relational context. While Vector Quantization
(VQ) has been explored in other modalities (Van Den Oord et al. 2017 Lee et al. 2022 Yu et al.) 2022b Van Kempen et al.) 2024 Li et al. 2024), its application in graph learning is limited. Notable exceptions include VQ-GNN (Ding et al., 2021). which uses quantized representations combined with a low-rank version of the graph convolution matrix to avoid neighbor explosion problem, VQGraph (Yang et al. 2024), which employs VQ for distilling a GNN into an MLP, and NID (Luo et al. 2024a).
which uses VQ to learn discrete node IDs for downstream prediction tasks.
3 PRELIMINARIES
Messag-Passinng GNNs. Let G denote the space of graphs. A graph g E G defined as (V, X, E) where the set of nodes and & C V x V is the set of edges. X E R xV]xd represents the node features of dimension d,, and E [X] represents the edge features of dimension de. A message-passing GNN takes as input and learns representations h1 for v layer as follows (Gilmer et al. 2017]:
E V (h.. Ix) in each
h4 = fo (hL ds (((,))) .ew)) lue
(I)
where fe and 9 are known as combine and aggregate functions, respectively. N, denotes the set of immediate neighbors of the node v. Once the node representations are computed, we can perform various tasks including node classification MLP (hw),, edge prediction as MLP (h. O hw), or graph classification as MLP (R (fh,, /u E V/))), where R a pooling (readout) function.
Graph Transformers use a tokenizer T, = T (N())) to map each node e E V into sequence of tokens Tn by considering a notion of neighborhood N. The simplest design is when is zero-hop neighborhood (i.e., the node itself) and Tp is node feature lookup function. The neighborhood N can be extended to include the node's ego network (Zhao et al. 202T) or top-k Random Walk based neighbors (Fu et al.) 2024), and To can be enhanced to representations from GNN (Chen) (PE) are passed to the Transformer as PE (u)). The representations in the 1thh layer of Transformer encoder are computed as:
et al. 2023). Node tokens along with positional encodings
h = LN (MHA (LN (1) + 11
h - Mo + MLP (KL)
where LN and MHA are LayerNorm and multi-head attention, respectively. Similar to Transformer encoders in other modalities (Devlin et al. [019 Dosovitskiy et al., 202I). we can append a special classification token ([CLS) to the input and use its representation to perform various classification tasks on the graph: MLP (Njass))
Vector Quantization projects embeddings X Bxd, into more compact space of codebooks CE E kg,,, where is < n. The codebooks can be learned by minimizing various objectives such as K-means clustering. The new representation of x; is then computed (Van Den Oord al. 2017))
=(xx)) Ck where k: = arg min
Building upon this concept, Residual-Vo VQ (RVQ) (Lee et al. 2022) extends VQ to a sequence of codebooks, where each consecutive codebook quantizes the residual error from the previous codebook, ie., r; = 2 Cg- This hierarchical approach constructs a multi-level quantized representation, enhancing the overall quantization quality. More details of RVQ are included in Appendix B
3

---

Published as a conference paper at ICLR 2025
4 SELF-SUPERVISED GRAPH TOKENIZATION
4.1 TOKENIZER PROPERTIES
Our goal is to design graph tokenizer that learns node tokens that exhibit three key characteristics:
Modeling Local Interactions. The tokens should encapsulate local interactions, allowing the Transformer focus on long-range dependencies. This analogous Vision Transformers (ViTs), where the Transformer attends to image patches instead of pixels (Dosovitskiy et al. [02T:] Liu et al. 202Ip. To achieve this, we leverage GNNs as the tokenizer encoder to model local interactions in the representation space (Battaglia et al.) 2018). Our design accommodates various GNN layer choices without constraints; for simplicity, we opt for a GAT encoder (Veličković al. 2018).
Memory Efficiency. The tokens also should be compact to facilitate efficient memory usage. To achieve this, we introduce Residual-Ve VQ (RVQ) (Lee et al. 2022) layer to quantize the GNN representations into sequence of discrete tokens. Quantization not only helps with generalization due to its regularization effect but also significantly reduces memory usage. Using an RVQ with e codebooks (typically = {2, ... ,8)), graph with feature matrix X E R&xxdz can be represented as XQ E N x and codebook representation of C E R K Xde, where c is the number of codebooks (i.e.. levels of quantization), K is the codebook size, and de is the code dimension. To illustrate the benefits of this approach, consider a graph with 106 nodes and a feature dimension of 1024 (X E IR 100 x 1024). Using an RVQ with 3 codebooks and a codebook size of 256, this graph can be represented XQ E N110 x3 plus C E 23x256611224 resulting in 270-fold reduction in memory.
Robustness and Generalization. The tokens should be robust and generalizable. To achieve this, we rely graph self-supervised learning. Self-supervised representations have been shown to be more robust to class imbalance (Liu et al., 2022) and distribution shift (Shi et al., 2023), while also capturing better semantic information (Assran et al. 2023) compared representations learned through supervised objectives. Moreover, self-supervised graph representations have demonstrated superior performance on downstream tasks compared representations learned in fully supervised
manner, indicating better generalization capabilities (Hu et al., 2020b Sun et al. 2020 You et al.
2020 Fu et al. 2020 You al., |021 Hassani & Khasahmadi 2020 Veličković et 2019 Zhu
et al. 2020b). Additionally, multi- musk learning with self- objectives has been shown to achieve better performance on downstream tasks (Doersch & Zisserman, 2017 Ghiasi et al. 2021).
To leverage these benefits, we propose training the GNN encoder with three self-supervised objectives. Unlike RQ-VAB (Lee et al. 2022), which uses reconstruction as its primary objective, we employ graph-specific objectives to capture the nuances of both structure and features.
4.2 TRAINING
To capture different aspects of information, we employ a multi-task learning framework that leverages three distinct families of graph self superviee objectives: ttudent-teacher distillation (Thakoor et al.) 2022), masked autoencoding (Hou et al. (022), and Infomax (Veličković et al.] (209).. We also introduce a commitment loss (Van Den Oord et 2017) to enforce alignment between learned node representations and the codebook representations. Specifically, the GNN encoder is trained through gradient descent minimize loss function comprising of three terms, where is the loss weight:
[ Lagi f.gmae + C
The first term is the Deep Graph Infomax (DGI) (eeičkovii et al. 2019) objective, which maximizes mutual information (MI) between node representations and graph (sub-graph) representations, based on the
divergence between the joint and product of marginals as follows:
Lagi = E
Log (D (hm hz))) + vEg
Σ log (1 - D (han (hu)) wEg
(6)
where h, is the representation of node hg is the global (sub-graph/graph) representation, computed as the mean of node representations. ğ is the corrupted version of the original graph, with the same structure but randomly shuffled features, providing negative examples for contrastive learning. D (h,,, hg) = a (h,,) is the discriminator that scores whether a node belongs to the graph, and is defined as bilinear classifier.
4

---

Published as a conference paper at ICLR 2025
Tokenizer
-MA
RVQ
MASK]
000
DDG
Distallation
MASK
300
MLP
GNN
poo
GNN
Reconstraction
[MASK]
Linear
Infomax
SubGraph
Masked Subgraph
Encoder
Quantizer
SSL Heads
SSL Loss
Tramsformer
Positional
Token Lookup
Hieeurchical
AtSention
Encodings
Stractural
Gating
Transformer
MLP
Emnedding
Original Graph
Semaatic Edges PPR
Token Modulation
Eucodder
Classifer
Figure I: Overview of our proposed Graph Quantization Transformer (GQT) consisting three main com-
ponents: (1) GNN to encode local interactions, (2) vector quantization for compact representation, and (3) generative and contrastive heads for robust representation learning. We also utilize Transformers encoder to model long-range interactions. We augment the graph with semantic edges (dashed lines) and generate se- quence for each node based on Personalized PageRank scores. We then modulate the tokens through hierarchical encoding and structural gating, and feed them into the Transformer and aggregate the learned representations through attention module before passing it to the classification head.
The second term the GraphMAE2 objective (Hou et al. 2023), which combines the generative loss of GraphMAE (Hou et al. 2022) with the teacher-(noisy) sttudent distillation loss of BGRL (Thakoor) jet al., 2022). This combination enables the model to avoid overfitting and learn more semantic representations. The GraphMAE2 loss is computed as follows:
The
1 A
Lgnae2
Σ DEg
+
#Eg
where I is the masked graph, h. is the node representation of masked node learned by the noisy student, h, is the corresponding node representation learned by the teacher over the original graph, and > 2 1 is scaling factor. The teacher's parameters updated using an Exponential Moving Average (EMA) of the noisy student's parameters.
The third term is the commitment loss, which encourages the representations to get close to their corresponding codebook embeddings within the RVQ layer. This loss is computed as:
Loommit
Σ
11,,
[cx] l|2
V
where sg is the stop-gradient operator, and eæ is the representation of the codebook that h, is assigned to (i.e., the centroid or prototype vector). Note that this loss only affects the node representations and does not update the codebooks.
To initialize and update the codebooks, we employ K-Means clustering and EMA with weight decay e [0, 1J, respectively. Specifically, the codebooks are updated as follows:
& = TCk + (1 7)
h
99)
VEV.
where V4 is the set of nodes assigned to codebook C₁. This update rule allows the codebooks to adapt the changing node representations while maintaining stability.
5

---

Published as a conference paper at ICLR 2025
5 GRAPH TRANSFORMER
5.1 GRAPH SERIALIZATION
Once the tokenizer trained, each node is mapped to discrete tokens: T, Iey,.... ty] E N (i.c., T. = Xo (e), encoding local interactions of that node. We then need to serialize the graph in order to input
the Transformer.
Semantic Edges. To enable the Transformer to capture long-range interactions, the input should consist of a sequence of tokens from nodes that are likely to have long-range dependencies. To facilitate this. we first augment the graph with semantic edges denoted as E,. which are computed as follows:
{ Cu. arg topk sim (ʃ (xr) o (xr)) Yu EV} wEV
E,-
(10)
where sim(:;.) denotes the similarity functionn Fy is the feature vector of node u. and f is a projection function. We use cosine similarity as the similarity function and Principal Component Analysis (PCA) as the projection function. The semantic edge augmentation effectively creates sparse edges between each node and its k-nearest neighbors in the feature space, enhancing the model's ability to recognize and utilize long-range dependencies.
Structural Serialization. We combine the semantic edges with the original edges and use Per- sonalized PageRank (PPR) to generate a sequence per target node. This enriches the sequence with information beyond local interactions, allowing the Transformer access potential long-range dependencies. We construct the sequence S, for each node v as follows:
S.
TT [ wEarg PoR
(11)
where S, = [1 ........ E. 1 Pa ... 1 ................................ pux is a sequence of length e x (I: + 1). comprising discrete tokens that represent the target node v, followed by discrete tokens of the top-k relevant nodes to node v. These relevant nodes are determined based on PPR scores. Note that the computation of semantic edges and PPR sequences is performed only once as pre-processing step, thereby reducing the computational overhead during training.
5.2 TOKEN MODULATION
Token Embeddings. There are c x K possible discrete tokens, where c is the number of codebooks and K is the codebook size. We randomly initialize embedding matrix X7 E R xds, which trained end-to-end alongside the Transformer. To further enrich the token representations, we introduce additional token for each node that aggregating the embeddings of its assigned codebooks from the pretrained tokenizer:
Σ C(i,4))
(12)
where Jli j] is the embedding corresponding to index in the ith codebook. We found that adding this explicit aggregated token from the codebook leads better performance compared initializing X7 directly with C. The input representation of the sequence for node is then defined as:
S. = Xy j
el
Xx
II i=1
[i I| h
(13)
where X YJ denotes concatenation of sequences X and Y. This representation combines the individ- ual token embeddings with the aggregated codebook embeddings, providing a more comprehensive and nuanced input to the Transformer.
Structural Gating, In order to provide the Transformer with the global structural importance scores of the nodes within the sequence with respect the target node, we introduce a gating mechanism over the input token embeddings as follows:
S, S. Softmax (lopk PPR (v, U.E.))
(14)
where we first apply softmax function with temperature 7 = to normalize the PPR scores, and then multiply each node token's 's representation by its corresponding normalized score.

---

Published as a conference paper at ICLR 2025
Positional Encoding. We also introduce two trainable positional encodings the input tokens. The first positional encoding enables the Transformer to distinguish between tokens from different nodes, while the second encoding, referred to hierarchical encoding. allows the Transformer to recognize the hierarchy level of each token within the codebooks. We randomly initialize the positional encodings PE [[(+1)xd, and HE E Rx and sum them with the encoding of their corresponding token. For example, the final encoding of the token j of the node i within the sequence computed as: z = Xr t [E[] + HE Note that we did not use any structural encoding, such Laplacian eigenvectórs,
did not observe any significant gains from them.
5.3 TRANSFORMER ENCODER
We use / layers of standard Transformer encoder with flash attention (Dao et al. 2022) to generate contextual representations per token in the sequence: H E [(c+))x(++)xxdd We then aggregate the token representations for j-th node in the sequence by summing along the token dimension:
Σ (iiE (++1)xd
E
(15)
To obtain single representation for the entire sequence, We further aggregate the representation using a linear attention layer:
k+1 Σ agh4
exp (X)) a; a= Σ, exp Wh)g)
where
(16)
We feed the resulting representation into a fully-connected classifier and train the model end-to-end using cross-entropy loss. Note that during inference, only the Transformer and classifier are utilized, as the tokenizer is pretrained and the sequences are pre-computed. Furthermore, since we only require discrete tokens and codebook embeddings, our approach enables efficient memory usage, regardless of graph size, allowing for efficient training and inference on large-scale graphs
EXPERIMENTS
We evaluate GQT on both medium- and large-scale graph learning tasks, encompassing 22 ho- mophilic, heterophilic, and long-range benchmarks. We follow the established experimental protocols from previous works to ensure fair comparisons. Details of the datasets, experimental setup, and hyperparameters are provided in Appendices C and respectively.
6.1 COMPARISON WITH STATE-OF-THE-ART
Long-Range Benchmarks. We four datasets from the Long-Range Graph Benchmark (LRGB) (Dwivedi et al. 2022b). including the Peptides-Fuut Func dataset for graph classification with Average Precision (AP) metric, the Peptides-Struct dataset for graph regression with Mean Absolute Error (MAE) metric, the COCO-SP dataset for inductive node classification with macro F1 metric, and the PCQM-Contact for link prediction with Mean Reciprocal Rank (MRR) metric. We compare our results to baselines reported in (Wang et al. (0224). The results shown in Table [ suggest that GQT is able to capture long-range dependencies and performs well on various graph prediction tasks.
Homophilic Node Classificattin. We use eight medium-scale homophilic datasets including: Cora- Full (Bojchevski & Günnemann] 2017), CiteSeer, PubMed (Yang al. (016),, Amazon Computers. Amazon Photos, Co-author CS, Co-author Physics (Shchur et 2011)). and WikiCS (Mernyci &
Cangea 2020). We compare our results with eight GNNs including: GCN (Kipf
Velling||0117 GAT, APPNP (Gasteiger et al. 2018). GPRGNN (Chien et al. 2020), GraphSAINT (Zeng et al.
2020 GraphSAGE (Hamilton et al. 2017). PPRGo (Bojchevski et al. (2200,, and GTAND+ (Feng We also compare against ten GT's including GT (Dwivedi & Bresson 2020). Graphormer GOAT (Kong NodeFormer (Wu al. 2022), DiftFormer (Wu et al.) 2023a). NAGphormer (Chen
al. 2022).
(Ying et al.
2021). SAN (Kreuzer et al. 2021), GraphGPS (Rampášek et
et al.
2023
ct al.
2023). Exphormer (Shirzad et al. 2023), and VCR-Graphin Graphrrrrrreerr (Fu et al. 2024). The baseline
performance is reported from (Wu et al. 2023b Luo et al. 2024a). GQT outperforms the baseline
7

---

Published as a conference paper at ICLR 2025
Table 1: Mean performance on inductive long-range benchmarks over five runs.
Task
Graph Classification Graph Regression Node Classification Link Prediction
Dataset
Peptides-Fune
Peptides-Struct
COCO-SP
PCQM-Contase
#Graphs
15,535
15,535
123,286
529,45 439,43
Avg. #Nooes
150.94
150,90 94
476.88
30.14
Avg. #Edges
307.30
307.30
2,693.67
61.09
Metric
AP 1
MAE I
F1 t
MRR 1
GCN
0.5930=0.0023
0.3496++t0.0011
0.0841=000000
0.3234=000006
Exphormer
0.6258=0.0092
0.2512:10. 0.05
0.3430:10.0100
0.3587.10.0225
GPS
0.6535 1.000
0.2500++0.000
0.3412++0.004
333377+000000
Graph-Mamhe
0.6739=0.0087
0.2478 1.00000.0000 1.00006
0.3960:10.0175
0.3395
GQT (Ours)
0.6903=0.0085
0,2452+000018
0.405
0.3427+000012
Table 2: Mean node classification accuracy medium-scale homophilic datasets over five runs.
CoraFull
CiteSeer
PubMed
Computer
Photo
CS
Physies
WikiCS
Datuset
#Nodes
19,793
3,327
19,717
13,752
7,650
18,333
34,493
11,701
#Edges
126.842
4,522
88.651
491.722
238,163
163,788
495,924
216,123
#Features
8,710
3,703
500
767
745
6,805
8.415
300
#Classes
70
6
3
10
15
10
GCN
61.76:::0.1
1..36
86.54-10.12
09.65
92.70++.200
92.92-40.12
96. 18-+0.07
77.47-40.85
GAT
64.47:10.18
76.55:1.222
86.32:+0.16
10.7810.13
93.87:+0.11
93.61=0.14
16.17:0.08
76.91:10.82
APPNP
65.16:10.28
1.6
88.43:10.15
90.1810.17
94.32-10114
94,49=0.07
96,54=0.07
78.87:00111
GNN
GPRGNN
67. 02:10.13311
77.13:1.67
89.34-10.25
89.32:1..29
94,49 14
05.13
96.85-10.08
78.124:..2
GraphSAINT
67.85++0.21
88.96+0.16
90.22+0.15
91.72+0.133
94.41+0.09
96.43+0005
GraphSAGE
1.33
87.4810.38
01.20:0.29
94,59=0.14
93.91=0.13
96,49=0.06
74.77-10.95
PPRGo
63.54:10.25
87,38
88 38.6910.21
93.6140.12
92.52-
95.51=0.08
78.1240.22
GRANDD+
71.37+0..11
88.64+0.09
88.74+0.11
94.75+0.12
93.92+1.08
96.47+0.04
GT
61.05-10.38
88.79:0.112
91.18=0.17
94.74=0.113 94.64=0.13
97.05=:0055
Graphormer
0OM
00M
0OM
92.74+0.14
94.64+0.13
0OM
SAN
59.01:10.34
88.22:10.15
89.93-0.116
94.86:0.10
94.51=0.15
0OM
GraphGPS
55.76:10.23
7.19
88.9411.116
00M
95.0610.113
93.93-10.15
0OM
78.66::0.44
GOAT
1.19
86.87+0.224
90,96+0.90
92,96+1448
94.21+00.8
96.2440.24
07.00+H0.77
NodeFormer
76.33:10.59
89.32:10.25
8..98:0.62
93.46:10.35
95.64=0.22
96.45=00288
74.73+10.94
DIFFormer
76.72=0..8
89.51=0.67
91.9910.76
95.1010.47
94.78-0020
96.60+0.18
73 56
NAGphormer
71.51++0.13
1.44
89.70=10119
91.222+0144
95,4940.11
95.75=00.99
97.34-0.03
17.16:t0.72
Exphormer
69.09:+0.72
76.83 1.24
89.52+0.54
91.5990.31
95.27+4.42
95.77=0.115
97.16
78.54+0.49
VCR- Graphhahhermr
71.67:10.10
89.77=0.15
91.75+0.15
95.5310.14
95.37-0.04
97.3410.04
GQT (ours)
71.81:10.21
77.8410.44
90.14110.16
93.37 95.7310018 96.11.0.09 97.53-1.06 80.1410.57
GNN and GT models on 7 out of 8 benchmarks (Table Notably, this achievement comes with significant memory reduction. For example, on the Physics dataset with 34,493 nodes, we only use 256 x 6 tokens, i.e., 23-fold memory reduction.
Heterophilic Node Classification. We also evaluate GQT on six medium-scale heterophilic datasets: Squirrel, Chameleon (Rozemberczki et al., (021). Questions, Roman -mmire, Amazon Amazon-Ratings, and Minesweeper (Platonov et al.] (023). We compare the performance with seven GNNs: GCN, GraphSAGE, GAT, GPRGNN, H2GCN (Zhu al. 2020a), CPGNN (Zhu et al.) (021), and GloGNN ([) et al. 2022). and six GT's: GraphGPS, GOAT, , NodeFormer, SGFormer, NAGphormer, and Exphormer. The baseline performance is reported from (Wu et al. 2023b Luo al.) 2024b Platonov ct al. 2023 Behrouz & Hashemi 2024). As shown in Table GQT outperforms the baselines on live out of six datasets. We observe that introducing semantic edges and structural gating specifically benefits the heterophilic setting (Appendix[E]) as they enable the Transformer to capture long-range dependencies that are not easily accessible through the original graph structure.
Large-scale Node Classification We also use four large-scale datasets: ogbn-pro,eins, ogbn-arxiv, ogbn- gronuurodscts (Hu et al.) 2020a),, and pokec (heterogeneous) (Leskovec & Krevi 2014). We compare the performance against six GNN: LINKX (Lim et al.) 2021). SIGN (Frasca et al., (020), GCN, GAT, GraphSAGE, and GPRGNN; and six GTs: GraphGPS, GOAT, Nodeformerr, NAGphormer, Exphormer, and SGFormer (Wu et al. 2023b), We report the baseline performance from (Wu et al.)
20236 Luo et al. 2024a). The results (Table show that GQT outperforms the baseline models on all large-scale benchmarks. This achievement comes with a significant reduction in required memory. For instance, on the ogbn-products dataset with 2, 2,449.029 9,09 nodes and 100-dimensional node features, GQT requires only 3 codebooks of size 4096, resulting in 30-fold memory reduction.
8

---

Published as a conference paper at ICLR 2025
Table 3: Mean node classification performance on heterophilic graphs over runs.
Squirrel
Chameleon
Amazon-Ratings
Roman-Empire
Minesweeper
Questions
#Nodes
5,201
2,277
22,662
24,492
10,000
48,921
Dataset
#Edges
216,933 2,089
36,101
32,927
93,050
39,402
153,540
#Features
2,325
300
300
7
301
#Classes
5
18
5
2
Measure
Accuracy!
Accuracyt
Accuracyt
Accuracyt
ROC-AUCT
ROC-AUCT
GCN
38.67:1:1.84
41.31=3.05
48.70:10.63
73.69:10.74
89.75:10.52
76.09=1.27
GraphSAGE
36.09:1:1.99
37.77=4.14
53.63:10.39
85.74::0.67
93.51+00.57
76.44=0.62
GNN
GAT
35.62:1:2.06
39.2113.008
52.70110.62
88.75:10.41
93.91
7..79=0.71
H2GCN
35.10:11.15
26.75:13.64
36.47100.23
60.11110.52
89.71110.11
1..59-1.46
CPGNN
30.04:12.003
33.00::..15
39.79=0.77
63.96:10.22
52.03-15.46
65, 65.96=1995
GPRGNN
38.95=t1.99
39.93+3.30
04.88+0.34
64.85+00.27
86.24:00.61
5..48-0911
GloGNN
35.11=:1224
25.90
36.8910.14
59.63:10.69
$1,08
6..74-1.19
GraphGPS
39.67:12.84
40.7911.003
53,10:10.42
82,0010.61
90.63:10.67
71.73=1.47
NodeFormer
38.52:11.57
34.7311.11
03.86210.35
64,49110.73
86.71110.88
74.27=1.46
6
SGFormer 41.80:12.27
44.9313.91
48.01
79.101:0.22
90,89-10,58
72.15=1.31
NAGphormer 3..3
51.26::0072
74.34
19:00.6
Exphormer 36.04:1..44
53.51:10.46
89.03+10.37
90.74:10.53
GQT(ours)
42.72:11..69
44.2313.05
54.32.10.41
90.98:10.24
97.36.10.35
78.94-0.86
Table 4: Mean node classification performance large-scale datasets over five runs.
ogbn-proteins
ogbn-arxiv
ogbn-products
pokec
#Nodes
132,534
169,343
2,449,029 61,859,140
1,632,803 30,622,564
Datuset
#Edges
39,561,252
I, 1,166,243
#Features
128
100
65
#Classes
40
2
47
2
Measure
ROC-AUC1
Accuracy
Accuracy 1
Accuracy 1
GCN
72.51+00.35
71.74+0.29
75.64+10.21
75.45++0.17 17
GAT
72.02-10.44
71.95-0.36
79.45-10.59
72.23-10.18
GNN
GPRGNN
75.68=00.49
71.10+0.12
79.76=00.59
72.23=00.18 0818
LINKX
71.37-0.58
66.18+0.33
71.59
82.04=10.07
GraphSAGE
77.68-0.20
71.49:0.27
18.29:10.16
75.63
SIGN
71.95+00.1
80.52+00116
GraphGPS
76.83-00.26
70.9710.41
OOM
0OM
GOAT
74.18+0..7
72.41+0.40
82,00=00443
66.37-0.94
NodeFormer
17.4
59.9011.442
72.93.10.13
1.300-11.30
SGFormer
79.53-0038
72.63+0.13
14.16+0..31
73.76#0.24
NAGphormer
73.61-10.33
70.13+4..55
73.55+0..1
76.59
Exphormer
74.58:0:26
72.4410.28
OOM
OOM
GQT(ours)
82.13+0.34
73.14+0..16
82.46+0.17
83.76+0..24
6.2 ABLATION STUDY
Effect of Tokenization. We examine the performance of the tokenizer by training linear model on the representations of the learned tokens without modulation, augmentation, or Transformer (1). As shown in Table within the linear evaluation protocol, the tokenizer shows strong performance. surpassing that of GTs such as GraphGPS and NAGphormer, as well as GNNs like GAT and SIGN 4). This implies that the tokenizer capable of learning effective token representations. To further investigate the importance of the tokenizer, we exclude it and train the Transformer directly on the original node features (2). As expected, this results significant degradation in performance, highlighting the crucial role of the tokenizer. Additionally, to study the effects of vector quantization, GraphMAE2, and DGI objectives, we train the model by excluding each component (3-5). The results suggest that the SSL objectives contribute more significantly to the performance compared to vector quantization. This because the primary purpose vector quantization is to compress information into discrete tokens, reducing memory requirements. Between GraphMAF2 A22 and DGI, the former

---

Published as a conference paper at ICLR 2025
Table 6: Ablation study on effect of proposed components on ogbn-arks arxiv dataset.
Graph Tokenizer
Token Modulation
Augmentation
Model
Performance
RVQ GMAE2 DGI
Codebook Embeddings
Positional
Structural Gating
Semantic Edges
PPR
Accuracy!
Encoding
Sequence
(1)
Linear
71.91:1..13
(2)
Transformer
70.68:0.177
/
Transformer
72.84:10.23
Transformer
71.83:10.19
/
/
Transformer
72.7111.24
(6)
/
/
Transformer
71.34++0.16
(7)
/
/
Transformer
72.69++0.21
(8)
/
/
Transformer
73.08:1:0.14
/
/
/
Transformer 72.59+00.25
(10)
/
/
d
/
Transformer 73.14:10.16
yields the highest gain. This is due its composition of two objectives: masked reconstruction and teacher-(noisyystudenn distillation. Both of these objectives have been shown to outperform InfoMax objectives on downstream tasks (Hou al. 2022: Thakoor et al. 2022).
Effect of Modulation. We also investigate the impact of codebook embeddings, positional encoding, and structural gating on the model's performance (6-8). As shown in Table 6 introducing aggre- gated codebook embeddings leads to improved downstream performance because it provides the Transformer with richer representations of each token. Positional encoding, as observed in other domains, contributes moderately to downstream performance. We also note that introducing structural gating yields moderate improvements in homophilic settings, whereas the gains are significant in heterophilic benchmarks (E.I) This disparity can be attributed to the ability of structural gating to provide the Transformer with importance scores computed over the global graph structure, which particularly beneficial in heterophilic scenarios.
Effect of Augmentation. We study the effect of semantic edges on downstream performance (9). The results suggest that augmenting the graph structure with semantic edges yields significant gains. This is because introducing semantic edges allows the Transformer to access semantic information that may not be captured by the original graph structure. Furthermore, when combined with random walks, this also enables the Transformer to attend to long-range dependencies which is particularly important in heterophilic benchmarks, where semantic relationships between nodes are more nuanced.
Robustness Analysis. To measure robustness, use Greedy Randomized Block Coordinate Descent (GRBCD) and Projected Randomized Block Coordinate Descent (PR-BCD) (Geisler et al. 2021) adversarial attacks to measure the accuracy degradation. We compare the GQT with an RQ- VAE (Lee et al.) 2022). The results (5) suggest that our tokenizer more ro- bust to attacks. This is because GQT is trained with multi-task self-supervised objectives while RQ-VAE is trained with autoencoding objective. More details are provided in Appendix
Table 5: Accuracy drop under adversarial attack.
Attack
GR-BCD
PR-BCD
PubMed ogbn-arxiv PubMed ogbn-arxiv
RQ-VAE GQT (ours)
20.40%
14.80%
23.30%
17.20% 11.30%
15.80%
10.40%
18.10%
7 CONCLUSION
We introduced the Graph Quantized Tokenizer (GQT) to provide standard Transformer encoders to acces discrete graph tokens that encapsulate local interactions and allow Transformers to attend to long-range dependencies within the graph structure. This allows us to seamlessly take advantage of the rapid advances in scaling Transformers. We achieved state-of-the-art performance on 20 out of 22 datasets, including large-scale and long-range homophilic and heterophilic datasets. As future directions, we plan to explore the potential of GQT in generative graph learning. Additionally, we aim to couple GQT with LLMs to provide a shared feature space across various graph datasets, paving the way for true Graph Foundational Models (GFMs) (Liu al. 2023b Mao et al. 2024)..
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels compared state-of-the-art superpixel methods. IEEE transactions on pattern analysis and machine intelligence, 34(1 (4211))2274-228,, 2012.
Mahmoud Assran, Quentin Duval, Ishan Misra, Piotr Bojanowski, Pascal Vincent, Michael Rabbat, Yann LeCun, and Nicolas Ballas. Self-supervised learning from images with joint-embedding predictive architecture. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15619-15629, 2023.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1.X6::800.00166 2018.
Ali Behrouz and Farnoosh Hashemi. Graph mamba: Towards learning graphs with state space models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 119-130, 2024.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations, 2023.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. arXiv preprint arXiv: 1IXiv:1707.03155 2017.
Aleksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik. and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464-2473, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, pp. 1877-1901, 2020.
Semih Cantürk, Renming Liu, Olivier Aeppoitte-Ganné Vincent Létourneau, Guy Wolf, Dominique Beaini, and Ladislav Rampášek. Graph positional and structural encoder. In Proceedings of the 41st International Conference on Machine Learning, pp. 5533-5566, 2024.
Dexiong Chen, Leslie O' Braa, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In Proceedings of the 39th International Conference Machine Learning, pp. 3469-3489, 2022.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: A tokenized graph transformer for node classification in large graphs. In The Eleventh International Conference on Learning Representations, 2023.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988 2020.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344-1633 16359, 2022.
Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: folynomial-expressiv graph transformer in linear time. In The Twelfth International Conference on Learning Representations, 2024.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre- fre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 4171-41 771-4186, 1166 June 2019.
11

---

Published as a conference paper at ICLR 2025
Prafulla Dhariwal, Heewoo Jun, Christine Payne, Jong Wook Kim, Alec Radford, and Ilya Sutskever. Jukebox: A generative model for music. arXiv preprint arXiv:2005.00341, 2020.
Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John P Dickerson, Furong Huang, and Tom Goldstein. VQ-GNN: A universal framework to scale up graph neural networks using vector quantization. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Carl Doersch and Andrew Zisserman. Multi-task self-supervised visual learning. In Proceedings of the IEEE international conference on computer vision, pp. 2051-2060, 2017.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference on Learning Representations, 2021.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.217585 2024.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.0969,, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022a.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326 223440, 2022b.
Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like graph: Encoding graphs for large language models. In The Twelfth International Conference on Learning Representations, 2024.
Wenzheng Feng, Yuxiao Dong, Tinglin Huang. Ziqi Yin, Xu Cheng, Evgeny Kharlamov, and Jie Tang. Grand+: Scalable graph random neural networks. In Proceedings of the ACM Web Conference 2022, pp. 3248-3258, 2022.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198, 2020.
Dongqi Fu, Zhe Xu, Bo Li, Hanghang Tong, and Jingrui He. view-adversarial framework for multi-view network embedding. In CIKM, 2020.
Dongqi Fu, Zhigang Hua, Yan Xie, Jin Fang, Si Zhang, Kaan Sancak, Hao Wu, Andrey Malevich, Jin- grui He, and Bo Long, gra-hraphommer: A mini-batch graph transformer via virtual connections. In The Twelfth International Conference on Leurning Representations, 2024.
Mikhail Galkin, Etienne Denis, Jiapeng Wu, and William L. Hamilton. Nodepiece: Compositional and parameter-efficient representations of large knowledge graphs. International Conference on Learning Representations, 2022.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.005997 2018.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34:7637-7649, 2021.
Golnaz Ghiasi, Barret Zoph, Ekin D Cubuk, Quoc V Le, and Tsung- Yi Lin. Multi-tast Multi-taskaan self-training for learning general representations. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 8856-8865 2021.
12

---

Published as a conference paper at ICLR 2025
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-vier representation learning on graphs. In International Conference Machine Learning, pp. 4116-4126, 2020.
Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi. Har-
nessing explanations: LLM-to-LM interpreter for enhanced text-attributed graph representation learning. The Twelfth International Conference on Learning Representations, 2024.
Van Thuy Hoang, O Lee, al. A survey on structure-preserving graph transformers. arXiv preprini arXiv:2401.611 2024.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference on Learning Representations, 2020.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjje Wang, and Jie Tang. Graphmac: sulf-super masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 594-604, 2022.
Zhenyu Hou, Yufei He. Yukuo Cen, Xiao Liu. Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. Graphmae2: A decooding-enhancee masked self-supervised graph learner. In Proceedings of the ACM web conference 2023, pp. 737-746, 2023.
Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18 1211333, 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020b.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. International conference on machine learning, pp. 2323-2332, 2018.
Amir Hosein Khasahmadi, Kaveh Hassani, Parsa Moradi, Leo Lee, and Quaid Morris. Memory-based graph networks. In International Conference on Learning Representations, 2020.
Jinwoo Kim, Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong, Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, pp. 14582-14595, 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C Bayan Bruss, and Tom Goldstein. Goat: A global transformer on large-scale graphs. In International Conference on Machine Learning, pp. 17375-17390, 2023.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618- 1221122, 2021.
Doyup Lee, Chiheon Kim, Sachoon Kim, Minsu Cho, and Wook-Shin Han. Autoregressive image generation using residual quantization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11523-11532 2022.
13

---

Published as a conference paper at ICLR 2025
Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: //snap. staaarrd.aaoodd.ccm edu/ data June 2014.
Xiang Li, Renyu Zhu, Yao Cheng. Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Leurning, pp. 13242-13256 2022.
Xiner Li, Limei Wang, Youzhi Luo, Carl Edwards, Shurui Gui, Yuchao Lin, Heng Ji, and Shuiwang Ji. Geometry informed tokenization of molecules for language model generation. arXiv preprint arXiv:2408. 10/20, 2024.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20900 2021.
Tsung-Yr Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and Lawrence Zitmick. Microsoft coco: Common objects in context. In Computer vision- ECCV 2014: 13th European conference, zurich, Switzerland, September 12, 2014, proceedings, part v 13, pp. 740-755. Springer, 2014.
Chuang Liu, Yibing Zhan, Xueqi Ma, Liang Ding, Dapeng Tao, Jia Wu, and Wenbin Hu. Gapformer: graph transformer with graph pooling for node classification. In Proceedings of the Thirty-Second International Joini Conference on Artificial Intelligence, 2023a.
Hao Liu, Matei Zaharia, and Pieter Abbeel. Ringattention with blockwise transformers for near- infinite context. In The Twelfth International Conference on Learning Representations, 2024.
Hong Liu, Jeff Z. HaoChen, Adrien Gaidon, and Tengyu Ma. Self-supervised learning is more robust to dataset imbalance. In International Conference on Learning Representations, 2022.
Jiawei Liu, Cheng Yang. Zhiyuan Lu, Junze Chen, Yibo Li, Mengmei Zhang, Ting Bai, Yuan Fang, Lichao Sun, Philip S Yu, et al. Towards graph foundation models: A survey and beyond. arXiv preprint ar arXiv:2310. 1829, 2023b.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference computer vision, pp. 10012-10022, 2021.
Zhiyuan Liu, Yaorui Shi, An Zhang, Enzhi Zhang, Kenji Kawaguchi, Xiang Wang, and Tat-Seng Chua. Rethinking tokenizer and decoder in masked graph modeling for molecules. In Teirth- Conference on Neural Information Processing Systems, 2023c.
Yuankai Luo, Qijiong Liu, Lei Shi, and Xiao-Ming Wu. Atructure-wwar semantic node identifiers for learning on graphs. arXiv preprint arXiv:2405.16455 2024a.
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Classic GNNs are strong baselines: Reassessing GNNs for node classification. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024b.
Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K. Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In Proceedings of the 40th International Conference on Machine Learning, pp. 23321-23337, 2023.
Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Mikhail Galkin, and Jiliang Tang. Position: Graph foundation models are already here. In Forty-first International Conference Machine Learning, 2024.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image- recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-52, 2015.
Péter Mernyei and Cätälina Cangea. Wiki-cs: A wikipedia- benchmark for graph neural networks. arXiv preprint arXiv:2007.02901, 2020.
14

---

Published as a conference paper at ICLR 2025
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667, 2021.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Maho Nakata and Tomomi Shimazaki. Pubchemqe project: a large-scale frrst-rrinippes electronic structure database for data-driven chemistry. Journal of chemical information and modeling, 57(6): 1300-1308, 2017.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. 10th international workshop on mining and learning with graphs, volume 8, pp. 1, 2012.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint urXiv:2002.0528)) 2020.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? The Eleventh International Conference Learning Representations, 2023.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In Proceedings of the 38th International Conference on Machine Learning, pp. 8821-8831, 2021.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14515, 2022.
Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean-baptiste Alayrac, Radu Soricut, Angeliki Lazaridou, Orhan Firat, Julian Schrittwieser, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context, arXiv preprint arXiv:2403.055300 2024.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in neural information processing systems, pp. 12559-12571, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2)cnnab014, 2021.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1XXXv:1811.055600 2018
Yuge Shi, Imant Daunhawer, Julia E Vogt, Philip Torr, and Amartya Sanyal. How robust is unsuper- vised representation learning distribution shift? In The Eleventh International Conference on Learning Representations, 2023.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In Proceedings of the 40th International Conference Machine Learning, pp. 31613-31632, 2023.
Sandeep Singh, Kumardeep Chaudhary, Sandeep Kumar Dhanda, Sherry Bhalla, Salman Sadullah Usmani, Ankur Gautam, Abhishek Tuknait, Piyush Agrawal, Deepika Mathur, and Gajendra PS Raghava. Satpdb: a database of structurally annotated therapeutic peptides. Nucleic acids research, 44(D1):D1119-D)
2016.
Fan-Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised graph-level representation learning via mutual information maximization. In International Conference on Learning Representations, 2020.
Chameleon Team. Chamelcon: Mixed-mole carly-fusion foundation models. arXiv preprint vrXiv:2405.09811 2024.
15

---

Published as a conference paper at ICLR 2025
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In International Conference Learning Representations, 2022.
Aaron Van Den Oord, Oriol Vinyals, al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
Michel Van Kempen, Stephanie S Kim, Charlotte Tumescheit, Milot Mirdita, Jeongjae Lee, Cameron LM Gilchrist, Johannes Söding, and Martin Steinegger. Fast and accurate protein structure search with foldseek. Nature biotechnology. 42(2):243-246, 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces, arXiv preprint urXiv:2402.00789, 2024.
Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are enough. Quantitative Science Studies, 1(I): 396-413, 2020.
Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scal- able (graph) transformers induced by energy constrained diffusion. In The Eleventh International Conference on Learning Representations, 2023a.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations. In seirty- Conference on Neural Information Processing Systems, 2023b.
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, pp. 13266-13279, 2021.
Jun Xia, Chengshuai Zhao, Bozhen Hu, Zhangyang Gao, Cheng Tan, Yue Liu, Siyuan Li, and Stan Z. Li. Mole-BERT: Rethinking pre-training graph neural networks for molecules. In The Eleventh International Conference on Learning Representations, 2023.
Zhe Xu, Kaveh Hassani, Si Zhang, Hanqing Zeng, Michihiro Yasunaga, Limei Wang, Dongqi Fu, Ning Yao, Bo Long, and Hanghang Tong. How make lims strong node classifiers? arXiv preprint arXiv:2410.02296 2025.
L Ling Yang, Ye Tian, Minkai Xu, Zhongyi Liu, Shenda Hong, Wei Qu, Wentao Zhang Bin CUI, Muhan Zhang, and Jure Leskovec. VQGraph: Rethinking graph representation space for bridging GNNs and MLPs. In The Twelfth International Conference on Learning Representations, 2024.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning. pp. 40-48. PMLR, 2016.
Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. Language is all graph needs. In Findings of the Association for Computational Linguistics: EACL 2024, pp. 1955-1973, 2024.
16

---

Published as a conference paper at ICLR 2025
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888 2021.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pp. 12121-12132, 2021.
Jiahui Yu, Xin Li, Jing Yu Koh, Han Zhang. Ruoming Pang, James Qin, Alexander Ku, Yuanzhong Xu, Jason Baldridge, and Yonghui Wu. Vector-quantized image modeling with improved VQGAN. In International Conference on Learning Representations, 2022a.
Xumin Yu, Lulu Tang, Yongming Rao, Tiejun Huang, Jie Zhou, and Jiwen Lu. Point-bert: Pre- training 3d point cloud transformers with masked point modeling. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 19313-19322, 2022b.
Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis E.H. Tay, Jiashi Feng, and Shuicheng Yan. Tokens-to-token vit: Training vision transformers from scratch on imagenet. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 558 567, 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans- formers universal approximators of sequence-to--squeeee functions? In International Conference on Learning Representations, 2020.
Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee. Motif-based graph self- supervised learning for molecular property prediction. Advances in Neural Information Processing Systems, 34:15870-1558 2021.
Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification. arXiv preprint arXiv:2110.1304. 10094 2021.
Lecheng Zheng, Dongqi Fu, Ross Maciejewski, and Jingrui He. Drgnn: Deep residual graph neural network with contrastive learning. In TMLR, 2024.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020a.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 11168-11176. 2021.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.0 04131, 2020b.
Markus Zopf. 1-w1 expressiveness is (almost) all you need. In 2022 International Joint Conference on Neural Networks (IJCNN), pp. 1-8, 2022.
17

---

Published as a conference paper at ICLR 2025
Appendix
A PRELIMINARIES
Graph Attention Networks (GAT). The representation of node in layer / is computed as:
exp
(o
W2
W Wing (1 / w
M =
any aay-Wih-1 aij
(17)
W W h (1-1) w n "))
JEN;
Σ KEN.
exp
where a is non-linearity, and ai the normalized attention score between two connected nodes and j.
Personalized PageRank (PPR). A PPR vector for node captures the relative importance of other nodes with respect to node by exploring the graph structure through iterative random walks:
oPr + (1 a)g
(18)
where P D AD
E R**" q is a stochastic personalized vector, r the stationary distribution of random walks, and is damping factor.
B MODEL DETAILS
Algorithm Graph Tokenizer
1: Input: Graph g = (V,E,)), Graph Encoder GNNg, Residual Quantizer RQ BGRL Loss RQ
2: H, = GNNo(9)
(Node Representations
3: C, Z, T, Lcommit RQ+,H,)
(codebooks, quantized representation, discrete tokens)
4: Ldgi DGI(Z)
[Compute DGI Loss] j
5: Lógri BGRL(Z)
(Compute BGRL Loss]
6: Lmae MAE(Z)
[Compute MAE Loss]
7: L =Lagi + Lngri + Liac Loommit
(Compute Multi-Tast Loss]
8: return Z,T, L.
Algorithm 2 Residual Vector Quantization
Input: Data X, Number of codebooks N, Size of codebook K, Dimension of codebooks
2: Lcommit 0
3: C Random( N, K, d)
4: Z Zeros() X|, d)
5: T Zeros( X N)
6: for in X do
7: r = X
8: for
to N do
9:
1: = arg min, ||
C(j. A|
r || Clj k
11:
T
k
Z
Z + Ciil(
13:
Loommit = Lcommit + || sg Clj. x3]113
end for 15: end for
return Z. X
C DATASETS
We provide detailed description of the datasets used in this study. All datasets publicly available.
18

---

Published as a conference paper at ICLR 2025
CoraFull (Bojchevski & Günnemann 2017). CiteSeer, and Pubmed (Namata al. 2012)
are citation datasets, where nodes represent documents and edges represent citation links.
Labels indicate the paper category.
Computer and Photo (Shchur et al. 2018) are from the Amazon co-purchase graph (McAuley et al., 2015), where nodes represent goods and edges indicate that two goods are frequently bought together. Node features are hag-of-words encoded product reviews, and class labels are given by the product category.
CS and Physies (Shchur et al. 2018) are co-authorship graphs based on the Microsoft Academic Graph from the KDD Cup 2016 challenges. Here. nodes are authors connected by an edge if they co-authored a paper; node features represent paper keywords for each author's 8 papers, and class labels indicate the most active fields of study for each author.
WikiCS (Mernyei & Cangea 2020) derived from Wikipedia, where nodes represent Computer Science articles, and edges are based on hyperlinks. The nodes are classified into 10 classes representing different branches of the field.
Squirrel and Chameleon (Rozemberozki et al. 2021 Pei et al. 2020) are Wikipedia page- page networks, where nodes represent articles from the English Wikipedia, and edges reflect mutual links between them. The nodes were classified into five classes based on their average monthly traffic.
Amazon-Rating (Platonov et al. 2023) is based on Amazon product co- purchassing data. Nodes represent products (books, music CDs, DVDs, VHS video tapes), and edges connect products that are frequently bought together. The task is to predict the average rating given to a product by reviewers.
Roman-Empire (Platonov et 2023 is based on the Roman Empire article from the English Wikipedia. Each node in the graph corresponds to one word (not necessarily unique) in the text, so the number of nodes equals the length of the article. Two words are connected if they follow each other in the text or are linked in the sentence's 's dependency tree. A node's class represents its syntactic role.
Minesweeper (Platonov al. 2023) inspired by the Minesweeper game. The graph consists of regular 100x 100 grid, where each node (cell) is connected to eight neighboring nodes (except for nodes at the edge of the grid, which have fewer neighbors). 20% of the nodes are randomly selected as mines. The task is to predict which nodes are mines. Node features are me-hoot-enooded numbers of neighboring mines, however, for 50% of the nodes, these features are unknown, indicated by a separate binary feature.
Questions (Platonov et al. 22023) is based on data from the crestion-answerigg website Yandex Q, where nodes represent users, and edges connect two nodes if one user answered another user's question during a one-year time interval. The task is to predict which users remained active on the website, forming binary classification task.
ogbn-proteins (Hu et al. 2020a) is protein-protein association network, where nodes represent proteins, and edges indicate biologically meaningful associations between proteins, such as physical interactions, co-expression, homology. The task is predict the presence of protein functions in a multi-label binary classification setup.
agbn-arxiv (Hu et al.) 2020a) is a citation network between all Computer Science (CS) arXiv papers indexed by MAG (Wang et al.) 2020). Each node presents an arXiv paper, and directed edges indicate that one paper cites another. The task to predict the 40 subject areas of arXiv CS papers, such cs.AI, cs.LG, and cs.OS.
ogbn-products (Hu et al. 2020a) is an Amazon product co-purchasing network of 2 million products. Edges indicate that products are purchased together. The task is to predict the product category.
pokec (Leskovec & Krevl 2014 Lim et al. 2021 is a social network, where nodes represent users, and edges represent friendships. The task predict the gender of users.
Peptides-Fune is peptide dataset retrieved from SATPdb (Singh et al. (0166) with over 15K peptides. Each node corresponds to a heavy atom, and edges are chemical bonds. The task is to predict 10 peptide functions, forming multi-label graph classification task.
http::/ kva horgaaaaiiaaaaaaaaaooooooooooo wttp///c///.////eeeeeeec tory.htm]
19

---

Published as a conference paper at ICLR 2025
Peptides-Struct consists the same graphs Peptides-Struct, but with different task. Here the task is to predict aggregated 3D properties (i.e., mäss, valence) of the peptides at the graph level.
COCO-SP is node classification dataset based on the MC COCO image dataset (Lin et al. 2014). Each node corresponds to a region of the image belonging to a particular class. These superpixels nodes are extracted with the SLIC algorithm (Achanta al. (002), and two nodes are connected with edge if the node regions share common boundary. The task is to predict the semantic segmentation label for each superpixel node out of 81 classes.
PCOM-Contact is a molecule dataset with over 529K molecules (Nakata & Shimazaki 2017p. Atoms are nodes, and chemical bonds are edges. The task is to predict pairs of nodes that will be contacting with each other in the 3D space.
For CoraFull, Pubmed, PubMed, Computer, Photo, CS, and Physics, we follow previous work and use 60%/20%/20% train/valid/test split. For WiKiCS, follow the official split in Mernyei & Cangea (2020). For Squirrel, Chameleon,
noman-Empire, Minesweeper, and Questions, follow the splits in Platonov al. (2023). For ogbn-proteins, ogbn-arxiv, and ogbn-products, we follow the splits in Hu et al. (2020a). For pokec, we follow the split used in Lim et al. (2021). For Peptides-Func, Peptides-Struct, COCO-SP, and PCQM-Contact, follow the split provided in
Amazonn-Ratnnge
Dwivedi et al. (2022b).
D EXPERIMENTAL SETUP
P DGI and the vector-quantize- pytorch packagd Most datasets can be accessed through PyG and DGL. All experiments are conducted on single Nvidia A100 GPU.
Software & Hardware. GQT is implemented using PyTorct
Hyperparameters & Experimental Details. As illustrated in Figure I our method consists two parts: the tokenizer and the Transformer encoder. We provide the hyperparameters and experimental details for each part below.
During the training of the graph tokenizer, datasets, and apply sampling for large-scale graphs. We consider different sampling methods, including random partitioning. which randomly samples nodes within a graph and returns their induced subgraph; neighbor sampling (Hamilton et al.] 2017). GraphSAINT (Zeng et al.) (222)] and local clustering Hou et (2023). For the GNN encoder and decoder, we use GCN or GAT as our backbone and tune the number of layers from { (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) and hidden dimensions from [128, 256, 512, 1024). For the quantizer, we use residual- VQ (RVQ) (Lee et al. 2022 and
full- -gaph training for small- and medium-scale
tune the number of codebooks from (1, 2, 3, 6, 9} and the codebook size from [128, 256, 512, 1024, 2048, 4096). We set the code dimension to be equal the hidden dimension of the GNN encoder.
During the training of the Transformer, we use KNN to add semantic edges and tune the number of semantic neighbors from [0, 5, 10, 15, 20). Then, we use PPR to generate a sequence of nodes for each target node. We tune the number of PPR neighbors from {0, 5, 10, 20, 30, 50). For the Transformer model, we use the TransformerEncoderr module in PyTorch as our backbone, and tune the number of layers from 1, 2, 3, 4. 5, 6). the number of heads from (4, 8). and the feedforward dimension from {512, 1024, 2048). Note that for some small- and medium scale datasets, we do not need PPR to generate sequences, instead, can directly take all nodes from graph sequence as in Rampášek et al. 2022).
httpps://pytorch.oom
https://pyq.orq/
https://www.dg/
http:://ttttt.ooooo//c/aaaaaaaer ott. pytorch
http:://gittubbcomm/
20

---

Published as a conference paper at ICLR 2025
Table 7: Selected hyperparameters for each dataset.
GNN Encoder
Quantizer
Transformer
layers
Hidden dim Codebooks
Codebook size
KNN
PPR
Layers
Heads
FFN dim
CoraFull
256
CiteSeer
256
512
PubMed
256
256
15
512
Computer
256
3
30
512
Photo
512
3
128
30
4
1024
CS
2
512
3
128
20
4
1024
Physics
2
256
3
256
30
4
512
WikiCS
2
256
3
128
30
4
512
Squirrel
256
3
128
30
2
4
512
Chameleon
3
256
3
128
5
30
2
4
512
Amazzon-Rttnng
512
3
128
5
20
2
4
1024
Roman-Fampir
6
256
3
256
10
15
4
512
Minesweeper
6
128
3
128
10
15
4
512
Questions
3
256
3
512
10
15
4
512
ogbn-proteins
6
256
3
512
O
50
3
4
512
oghn-arxiv
512
30
4
1024
ogbn-products
1024
30
2
8
2048
pokec
256
512
Peptides- Func
128
Peptides-Struct
128
128
2
512
COCO-SP
4
128
3
128
2
4
512
PCQM-Contact
4
128
3
128
0
4
512
E ADDITIONAL RESULTS
E.1 FURTHER ABLATION STUDY
We also provide an ablation study on one of the heterophilic datasets. The results shown in Table suggest that introducing semantic edges and structural gating mechanisms specifically benefits the heterophilic setting.
Table 8: Ablation study on effect proposed components on the Minesweeper dataset.
Graph Tokenizer
Token Modulation
Augmentation
Model
Performance
RVQ
GMAE2
DGI
Codebook Embeddings
Positional Encoding
Structural Gating
Semantic Edges
PPR Sequence
ROC-AUCT
(1)
Linear
90.24+-0.49
(2)
Transfomer
90.52:10.39
(3)
Transformer
95.27-+-046
(4)
V
Transformer
92.91-10.55
(5)
/
Transformer
93.82:10:46
(6)
/
Transfomerr
93.24:10.36
(7)
Transformer
94.82-10.41
(8)
/
Transformer
93.97:10.58
(9)
/
/
/
/
Transformer
92.83:10.35
(10)
/
Trunsformer
95.28::0.44
E.2 GENERALIZATION ANALYSIS
To measure improved generalization, we follow the com- mon practice of treating downstream predictive perfor- mance as proxy for generalization. As shown in Table and Table every component of the tokenizer, includ- ing both SSL objectives and the quantization layer, con- tributes to the downstream predictive performance, thereby improving the model's generalizability. Furthermore, to evaluate the contribution of multi-task SSL objectives to downstream performance, compare results with
Table 9: Comparison between mean GQT and RQ-VAE performance five runs.
ogbn-arxiv
Minesweeper
RQ- VAE GQT (ours) 73.14=0.16 95.28-0.44
66.05=0.48 89.69-0.35
21

---

Published as a conference paper at ICLR 2025
those of tokenizer trained using the RQ-VAE (Lee et al. 2022) design, which employs construction objective. The results presented below indicate that using multi-task SSL objectives significantly improves downstream predictive performance, which is strongly correlated with the method's generalization.
E.3 EFFICIENCY ANALYSIS
As mentioned in Section 6.1 using discrete tokens instead of node fea- tures results in significant memory re- duction. For instance, the ogbn- products dataset with 2,449,029 nodes and 100-dimensional node features, GQT requires only 3 codebooks of size 4096, resulting in remarkable 30-fold reduction in memory usage.
Table 10: Memory and time during inference.
Attack
GPU Memory
Full Inference Time
ogbn-arxa arxiv Minesweeper ogbn-arxiv Minesweeper
GAT
27B 1324MB
2108M
5s
Is Is
GQT (ours)
1037MB
4s
This memory reduction occurs after training the tokenizer. Since the encoder of the tokenizer is GNN that processes the graph with original node features, its memory footprint is comparable to that of any arbitrary GNN, However, because the Transformer encoder only consumes discrete tokens, which are significantly fewer than the total number of nodes, we achieve substantial reduction in memory footprint. As an additional experiment, we compare the inference time and memory usage between our Transformer encoder and a Graph Attention Network (GAT) when performing inference on all graph nodes. The results shown Table show that while our Transformer on par with sparse implementation of GAT in terms of inference time, it requires half the GPU memory.
22


Reviews:
[{"review_id": "DOGTOdz776", "reviewer": "Reviewer_cTGj", "summary": "the paper proposes a graph tokenizer that utilizes multi-task graph self-supervised objectives to train a graph encoder, which can capture local interaction and have memory efficiency", "questions": "NO", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. paper is well written and easy to follow\n2. experiment demonstrate strong results compared with baseline methods.\n3. motivation and methodology is clear", "weaknesses": "NO", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WnVsUyx2ln", "reviewer": "Reviewer_rTiq", "summary": "The paper proposes Graph Quantized Tokenizer (GQT) that considers three key properties such as local interactions, memory efficiency, and robustness & generalization for graph Transformer. Different existing works that train tokenizer and Transformer architecture in an end-to-end manner, GQA decouples the training tokenizer from the Transformer. In other words, it first trains the tokenizer and then learns graph Transformer architecture given the tokenized graph. From the experimental results, GQA shows the best performance compared to other baselines on 7 out of 8 datasets. It also achieves the best performance on large-scale datsets.", "questions": "Please refer to the weaknesses.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The design of tokenizers in graph Transformers is really an important research topic. The paper well describes the existing works of graph Transformers and tokenizers in the related works.\n- The paper is easy to follow.\n- The experiments of the paper demonstrate that the proposed method is effective with multiple experiments including homophilious, heterophilious and large-scale datasets.", "weaknesses": "- I think that the novelty of the paper is limited.\n   - One of the main contributions highlighted in this paper is quantized tokenization for graph Transformers. However, the paper simply combines graph neural networks for dealing with graph-structured data and existing residual vector quantization for the quantization. \n   - Another contribution is multi-task self-supervised learning. The paper uses two self-supervised learning objectives such as DGI and GMAE2, which are not proposed self-supervised training scheme in this paper. I think that using two self-supervised objectives to improve the effectiveness of the model is hard to become a good contribution in top-tier ML conferences.\n\n- More experiments need to be included.\n   - The author claims that the proposed quantization method improves the robustness and generalization of the model. But, there is no experimental result concerning the robustness and generalization.\n   - In the similar manner, the validation of efficiency needs to be added to empirically prove that the proposed quantization is effective and efficient.\n   - Also, the paper only deals with node classification tasks. It would be better if the paper included other graph-related tasks, such as node regression and graph classification, which have been actively dealt with in other graph Transformer papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ot9q5SPvyV", "reviewer": "Reviewer_cy7L", "summary": "This paper proposes a self-supervised method, named GQT, for graph token learning. GQT adopts the residual vector quantization to generate graph tokens and trains the model with mutual information maximization, graph reconstruction loss and distillation loss minimization. Given the learned codebook, GQT augments the input graph with edges between similar nodes and generates a node sequence for each node with topK-related nodes in personalized PageRank. Extensive results on node classification are provided to demonstrate the effectiveness of GQT.", "questions": "-  How does GQT perform with different sizes of codebooks ($K$, $c$ and $d_c$).\n- The graph codebook learning resembles node clustering. Can authors provide a comparison between these two types of methods? Or how does node clustering perform in the graph codebook learning?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- This paper decouples the graph tokenizer from transformer training, which poses an interesting thread for developing graph transformers.\n- The proposed method achieves competitive performance on node classification, including heterophilic and homophilic datasets.\n- GQT scales to benchmarks with large graphs.", "weaknesses": "- As the core module in GQT, the authors did not provide a sufficient description of the residual vector quantization (nor in the appendix). How does GQT learn the mapping from graph nodes to the codebook tokens? The mapping relation $X_Q$ is introduced in L194/199 and never used again in the following context.\n- The writing of section 5.2 is rather arbitrary. I cannot fully comprehend the embedding matrix $X_T$, which is 'trained end-to-end with the Transformer'. How does $X_T$ be learned in GQT? In L333-334, the authors argue that 'adding this explicit aggregated token leads to better performance compared to initializing $X_T$ with $C$. Does this mean that $X_T$ is initialized with $C$ or not?\n- The operator $[\\cdot,\\cdot]$ in Eq 14/15 lacks a definition.\n- The GQT (or tokenizer) is claimed to (1) capture long-range dependencies; (2) less memory footprint; (3) improved generalization capabilities, which lack of supportive analysis in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u9ozacAPEl", "reviewer": "Reviewer_FMi4", "summary": "This work attempt to design a graph tokenizer that utilizes graph self-supervised learning to train a encoder. And then leverage the Transformer to capture long-range dependencies. Specifically, the authors adapts Residual Vector Quantization to learn hierarchical discrete tokens for reducing memory requirements and improving generalization capabilities.", "questions": "1. Could the authors provide the explanation about why GQT obtains lower performance than classic GNNs?\n\n2. I think the authors need to re-emphasize the innovation of this work.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed Graph Quantized Tokenizer utilizes discrete tokens, which can significantly reduce memory requirements.", "weaknesses": "1. The major concern of this manuscript is the experiment part. According to [1], classic GNNs (e.g. GCN, GraphSAGE and GAT) can also achieve excellent performance on node classification tasks. However, the proposed GQT obtains lower performance on almost all datasets. This makes me worry about the actual contribution of this work.\n\n2. The novelty of the proposed method is limited. There are already some works try to utilize vector quantization to learn discrete tokens for graph learning [2,3]. And there are also existing work utilize graph augmentation and Personalized PageRank to generate a sequence per node [4].\n\n3. There are also some concept errors in the manuscript. For example, the authors mention that \"Recent studies on applying Large Language Models (LLMs) to graph-related tasks have found the representing ...\" in the introduction section. But most recent methods about combining LLMs with graph learning can only work on textual-attributed graph, and they just leverage LLMs to capture better textual  understanding [5, 6].\n\n\n[1] Luo, Yuankai, Lei Shi, and Xiao-Ming Wu. \"Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification.\" arXiv preprint arXiv:2406.08993 (2024).\n\n[2] Yang, Ling, et al. \"VQGraph: Rethinking graph representation space for bridging GNNs and MLPs.\" The Twelfth International Conference on Learning Representations. 2024.\n\n[3] Xia, Jun, et al. \"Mole-bert: Rethinking pre-training graph neural networks for molecules.\" (2023).\n\n[4] Fu, Dongqi, et al. \"VCR-graphormer: A mini-batch graph transformer via virtual connections.\" arXiv preprint arXiv:2403.16030 (2024).\n\n[5] Li, Yuhan, et al. \"A survey of graph meets large language model: Progress and future directions.\" arXiv preprint arXiv:2311.12399 (2023).\n\n[6] Jin, Bowen, et al. \"Large language models on graphs: A comprehensive survey.\" IEEE Transactions on Knowledge and Data Engineering (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hWbZC7G7Dy", "reviewer": "Reviewer_D7qL", "summary": "In this work, the authors propose GQT, a transformer-based framework for graph prediction tasks. GQT consists of a variety of proposed components, including a custom training loss and a tokenizer trained separately with a self-supervised learning approach. The tokenizer leverages vector quantization, resulting in a highly efficient tokenization that can be fed into a standard transformer encoder and applied to very large graphs with up to 2.5 million nodes. Empirically, GQT outperforms a variety of GNN and transformer baselines on 16 out of 18 transductive node classification problems, including both homophilic and heterophilic graphs.", "questions": "- **Q1**: Which components of GQT are also applicable to baselines? For example, while the tokenizer is certainly unique to GQT, adding semantic edges and PPR features to nodes may also improve baseline performance. I wonder whether the authors can give any indication as to whether the improved performance of GQT stems largely from components unique to GQT or whether their proposed components may be useful in improving the results of transformers for transductive node classification in general.\n- **Q2**: Table 4 and 5: Are the standard deviations missing from these tables or was the ablation study performed only on a single seed? In case the study was performed on a single seed, I strongly recommend to repeat the ablation study for at least three seeds to verify that the results are statistically significant.\n- **Q3**: Figure 1, the experimental section, the ablation studies as well as the conclusion mention “structural gating”. However, this term is never formally introduced. I suppose the authors refer to the gating mechanism in Equation 16. If this is the case, I encourage the authors to define properly define the term there.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- **S1**: The authors evaluate their model on a wide variety of transductive node classification datasets, both homophilic and heterophilic and up to 2.5 million nodes. The empirical results are impressive and indicate that GQT is a versatile approach to transductive node classification.\n- **S2**: The authors present an ablation study in Table 4 and Table 5 on the various components of their approach. The study indicates that most components help with improving the overall model performance; see **Q1** for a follow-up question on the ablation study.\n- **S3**: The approach for learning a tokenizer using vector quantization is highly interesting and should be further explored in future research. In particular, I expect that GQT can be readily adapted to other types of graph learning problems (such as inductive settings) while being highly efficient.", "weaknesses": "- **W1**: While the results are impressive, the authors evaluate exclusively on transductive node classification problems. In my opinion, the authors should be more upfront about this limitation or include results for inductive settings, e.g., the inductive tasks in [https://arxiv.org/abs/2206.08164](https://arxiv.org/abs/2205.12454).\n- **W2**: Section 4.2 introduces the training loss with three different loss terms. However, the authors do not provide any intuition or justification for these choices. As such, it is difficult for a reader to understand why these choices were made and how crucial they are to the overall framework. A similar issue appears in Sections 5.1 and 5.2.\n- **W3**: In the introduction in L35-36, the authors state that “GTs possess an expressive power equivalent to the 2-Weisfeiler-Lehman (WL) isomorphism test”, citing Kim et al. (https://arxiv.org/abs/2207.02505).  The transformer used in Kim et al. is entirely different from the transformers used in transductive node classification and in particular, different from GQT. As such, this reference does not serve as a motivation to the approach present in this work. Further, note that the GQT uses a GNN to learn local interactions and would suffer from the same expressivity limitations as GNNs, leading to the next statement in L37-38: “This [the 2-WL expressivity of GTs] surpasses the expressive power of message-passing GNNs, which are limited to the 1-WL test”. This statement is incorrect. The 1-WL and 2-WL tests as defined in Kim et al. are equivalent in expressive power. Finally, in L38-39, the authors state that “[…] a Transformer with sufficient attention heads can match or exceed the expressive power of a second-order invariant graph network, outperforming message-passing GNNs”, again citing Kim et al. Here, the authors omit the fact that transformers can only achieve said result when receiving as input $O(n^3)$ number of tokens, resulting in a transformer with $O(n^6)$ runtime and memory complexity. Again, this approach is entirely different to GQT and does not serve as a motivation for GQT. I strongly recommend the authors to adjust the introduction, remove the incorrect claims and provide a proper motivation for their approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)