Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning
Authors: Yuankai Luo
Hongkang Li
Qijiong Liu
Lei Shi
Xiao-Ming Wu
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Graph Tokenizers
Symbolic Compression
Efficient Graph Learning
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose an end-to-end framework that generates compact (6-15 dimensions), discrete (int4), and interpretable node representations, offering competitive performance and improved efficiency across tasks.

Abstract: We present a novel end-to-end framework that generates highly compact (typically 6-15 dimensions), discrete (int4 type), and interpretable node representations—termed node identifiers (node IDs)—to tackle inference challenges on large-scale graphs. By employing vector quantization, we compress continuous node embeddings from multiple layers of a Graph Neural Network (GNN) into discrete codes, applicable under both self-supervised and supervised learning paradigms. These node IDs capture high-level abstractions of graph data and offer interpretability that traditional GNN embeddings lack. Extensive experiments on 34 datasets, encompassing node classification, graph classification, link prediction, and attributed graph clustering tasks, demonstrate that the generated node IDs significantly enhance speed and memory efficiency while achieving competitive performance compared to current state-of-the-art methods. Our source code is available at https://github.com/LUOyk1999/NodeID.

Published as a conference paper at ICLR 2025
NODE IDENTIFIERS: COMPACT, DISCRETE REPRESEN- TATIONS FOR EFFICIENT GRAPH LEARNING
Yuankai Luo
Hongkang Li
Qijiong Liu
Lei Shilt
Xiao-Ming Wu²t
Beihang University
The Hong Kong Polytechnic University Rensselaer Polytechnic Institute
ABSTRACT
We present a novel end-to-end framework that generates highly compact (typ- ically 6-15 dimensions), discrete (int4 type), and interpretable node represen- aations-terned node identifiers (node IDs)-to tackle inference challenges on large-scale graphs. By employing vector quantization, node embeddings from multiple layers of Graph Neural Network (GNN) into discrete codes, applicable under both self-supervised and supervised learning paradigms. These node IDs capture high-level abstractions of graph data and offer interpretability that traditional GNN embeddings lack. Extensive experiments on 34 datasets, encompassing node classification, graph classification, link prediction, and attributed graph clustering tasks, demonstrate that the generated node IDs significantly enhance speed and memory efficiency while achieving competitive performance compared to current state-of-the-art methods.
compress continuous
INTRODUCTION
Machine learning on graphs involves leveraging graph topology and node/edge attributes to perform various tasks, including node and graph classification (Hu et al., 2020; Luo et al., 2023b), link prediction (Lü & Zhou, 201 I; Zhang & Chen, 201 8), community detection (Fortunato, 2010; Fortunato Hric, 2016), and recommendation (Konstas et al., 2009). Various methods have been developed to address these challenges, including random walk based-models (Perozzi et al., 2014; Grover & Leskovec, 2016), spectral methods (Bruna et al., 2013; Defferrard et al., 2016), and graph neural networks (GNNs) (Hamilton et al., 2017; Kipf & Welling, 2017; Veličković et al., 2018a). GNNs employ a message- saassgggpsssing mechanism (Gilmer et al., 2017) to iteratively aggregate information from node's 's neighbors. This process enables GNNs to learn node representations by effectively integrating graph topology and node attributes, leading to impressive results across various tasks.
Despite the advancements in GNNs, their application large-scale scenarios requiring low latency and fast inference remains challenging (Zhang et al., 2020; Jia et al., 2020; Yang et al., 2024). The inherent bottleneck the message-passing mechanism, which necessitates loading the entire comprising billions of edges-during tationally demanding and cone-con To address this challenge, recent studies (Zhang et al., 2021b; Tian et al., 2022; Yang et al., 2024) have explored knowledge distillation techniques to distill a small MLP model that captures essential information from a pre-trained GNN, making suitable for latency-criticee applications (Tian et al., 2023). However, these GNN-to-MLA methods require supervised training using class labels and lack the ability to generate effective node representations.
during inference for target nodes, which is compu-
An alternative approach to facilitate inference low-dimensional node embeddings that can be directly utilized for downstream prediction tasks. This method has been extensively explored in early works network/graph embedding, such DeepWalk (Perozzi et al., 2014) and node2vec (Grover & Leskovec, 2016), as well as in recent efforts leveraging GNNs to learn embeddings for graph tokens (Liu et al., 2024d;a; Qu et al., 2024; Xia al., 2023), including nodes, edges, and (sub)graphs. To balance representation effectiveness and computational efficiency, embeddings generated by GNNs typically have dimensions of 128 or 256. However, this
large-scale graphs involves learning effective,
'Contributed equally as the second authors. 'Coresponding authors. Correspondence to: lunyk @ thaa..cd..c xiao-ming.wa caddmming.wu@@polyuu.u....

---

Published as a conference paper at ICLR 2025
Node
Node
HOOP
2-HOP
Node ID:
E
Node 4.2
Node 4
1-HOP
2-HOP
2-HOP
2.
2.
Node ID:
Figure I: Illustration of 2-dimensional node IDs generated by our NID framework using two-layer GCN, The first ID code is derived from the first-layer node embeddings. and the second ID code from the second-layer embeddings. Center: t-SNE visualization of node embeddings in the PubMed Dataset, with colors indicating different class labels. Left: Six nodes are shown with their IDs and I-hop neighborhoods (topology and label distribution). Nodes sharing the same first ID code have similar 1- h-hop neighborhoods, though not necessarily the same class label. Right: Nodes E and F are further analyzed with their 2-hop neighborhoods, where differences reflected their distinct second ID code (blue) and class label.
relatively high dimensionality poses challenges in terms of storage and computational efficiency for large-scale applications. Furthermore, the real-valued embeddings often lack interpretability.
In this work, we tackle this challenge by learning highly compact (typically 6-15 dimensions), discrete (int4 type), and interpretable node representations, termed node identifiers (node IDs). We introduce novel end-to-end framework called NID, which employs vector quantization (Gray, 1984) to compress the continuous node embeddings generated at each layer of GNN into discrete codes, where the GNN and codebooks are trained jointly. This approach effectively captures the multi-orde neighborhood structures within the graph. Fig. illustrates examples of two-dimensional node IDs generated by two-layer GNN, demonstrating their ability to capture multi-level structural patterns, as well as their interpretability. We summarize the significance of our work as follows:
We empirically and theoretically demonstrate the feasibility of learning highly compact, discrete codes (node IDs) as effective node representations for efficient graph learning, without relying on knowledge distillation. Our extensive evaluation across 34 diverse datasets and tasks tasks-including node and graph classification, link prediction, and attributed graph clustering-shows that these node IDs achieve performance competitive with state-of-the-ar methods while significantly en- hancing speed and memory efficiency. We also offer a theoretical justification for our approach.
Our proposed NID framework can integrated with state-of- of-the-art unsupervised and supervised GNN methods to enhance performance. Experiments demonstrate that the generated node IDs not only retain essential information from GNN embeddings but also uncover hidden patterns some cases, leading to significantly improved performance. This warrants deeper investigation.
Our findings indicate significant redundancy in GNN embeddings. The generated compact, dis- crete node IDs provide high-level abstraction of graph data, offering interpretability that GNN embeddings lack. This may facilitate graph tokenization and applications involving LLMs.
2 PRELIMINARIES
We define a graph as tuple 9 = (V, X), where V is the set of nodes, & C V x V is the set of edges, and X E TR xd is the node feature matrix, with |V] representing the number of nodes and the dimension of the node features. Let A E I [|V| denote the adjacency matrix of G.
Message Passing Neural Networks (MPNNs) have become the dominant approach for learning graph representations. A typical example is graph convolutional networks (GCNs) (Kipf & Welling, 2017). Gilmer et al. (2017) reformulated early GNNs into a framework of message passing GNNs, which computes representations h. for any node v in each layer / as:
h = UPDATE (h1- AGG (fh-- E N (b))))
(1)
2

---

Published as a conference paper at ICLR 2025
where N(e) denotes the neighborhood of AGG' is the message function, and UPDATE' is the update function. The initial node representation h. is the node feature vector I, E R The message function aggregates information from the neighbors of update its representation. The output of the last layer, i.e., MPNN(u, A, X = h is the representation
produced by the MPNN.
Prediction tasks graphs involve node-level, edge-level, and graph-level tasks. Each type of tasks requires a tailored graph readout function, R, which aggregates the output node representations, h. from the last layer L, compute the final prediction result:
Preadout R ((h,, , E v]).
Specifically, for node-level tasks, which involve classifying individual nodes, simply identity mapping. For edge-level tasks, which focus on analyzing the relationship between any node pair (u, v), R is typically modeled the Hadamard product of the node representations (Kipf & Welling, 2016). i.c., Pryadour h @ h For graph-level tasks that aim to make predictions about the entire graph, R. often functions as a global mean pooling operation, expressed as Rredout [>] Ever hy
Vector Quantization (VQ) (Gray, 1984) aims to represent large set of vectors, Z = {2;
i=1. with
small set of prototype (code) vectors of a codebook C = often created using algorithms such as k-means clustering via optimizing the following objective:
{ where N > K. The codebook
N
VQ:
min
min
z - ex
Once the codebook is learned, each vector 2; can be approximated by closet prototype vector et where = arg ming ||= ex 1 is the index the prototype vector. Residual Vector Quantization (RVQ) (Juang & Gray, 1982; Martinez al., 2014) extends the basic VQ by performing the quantization process M times. Initially, a standard VQ is performed. Then, the residual vector is calculated:
2, Ct.
which represents the quantization eπror from the initial quantization. Then, the residual vectors r quantized using second codebook. This process can be performed repeatedly, with each stage quantizing the residual error from the previous stage, ultimately producing M tiers of codes.
OUR PROPOSED NODE ID (NID) FRAMEWORK
Our proposed NID framework consists of two stages:
1. Generating compact, discrete node IDs. Nodes are encoded using multi-layer MPNNs to capture multi-order neighborhood structures. each layer, the node embedding quantized into a tuple of structural codewords. The tuples are then combined to form what we refer to the node ID.
Utilizing the generated node IDs as node reprexentations in various downstream tasks. We directly use the node IDs for unsupervised tasks such as node clustering. We train simple MLPs with the node IDs for supervised tasks including node classification, link prediction, and graph classification.
3.1 GENERATION OF NODE IDs
Fig. illustrates the diverse cluster- ing patterns of node representations produced by an MPNN at different layers I. This diversity arises from the cumulative smoothing effect caused by successive applications of graph convolution at each layer (Li et al., 2018; 2019). To generate structure- aware node IDs, we employ an L- layer MPNN to capture multi-order neighborhood structures. At each
(a) Raw features
(b)l=1
(c)
Figure t-SNE visualization the node representations of Cora dataset generated by an MPNN at different layers I.
layer, we use vector quantization encode the node embeddings produced by the MPNN into
3

---

Published as a conference paper at ICLR 2025
Loye
(Self-) Supervised Loss
netereberligg
enheddige
Pretraining
Discrete Tokenizer
+
Discrete Tokenizer
Takenizer
Discrete
Loss
Groph Tosks
Figure 3: Overview of our proposed NID framework.
M codewords (integer indices). For each node v, we define the node of as a tuple composed of L x M codewords, structured as follows:
Node_ID((e (cn,.... CIM, C21, C2M, ,LL,' CLM)
(5)
where Qi represents the m-th codeword at the 1-th layer. Both M and L can be very small. For the node IDs in Fig. MM 1 and L 2. In our experiments, we typically set M and | 5].
Learning Node IDs. As illustrated in Fig. 3, at each layer 7 (1 S S L) of the MPNN, we employ RVQ to quantize the node embeddings and produce M tiers of codewords for each node v (see App. E.1 for detailed explanation). Each codeword Ctm. (1 S m < M) is generated by a distinct codebook Cim - (e 1K 1K where the size of the codebook. Hence, there are a total of x M codebooks, indexed by Im. Let Fim denote the vector to be quantized. Note that is the node embedding h" produced by the MPNN. When m > 1, Tim represents the residual vector. Then, Tim is approximated by its nearest code vector from the corresponding codebook Cim:
Gtm = arg min Pmmm - Aml k
producing the codeword Com. which is the index of the nearest code vector.
We introduce simple, generic framework for learning node IDs (codewords (mm) by jointly training the MPNN and the codebooks with the following loss function:
LND = Ls + Lvy.
(7)
where Cg is a -upeli-seeerviee graph learning objective, and Lvo is a vector quantization loss. Lg aims to train the MPNN produce effective node embeddings, while Lvo ensures the codebook vectors align well with the node embeddings. For a single node v, Lvo is defined as
M
LvQ
e 3| sg(ee )l|,
(8)
1=
m=1
where sg denotes the stop gradient operation, and is a weight parameter. The first term in Eq. (8) is the codebook loss (Van Den Oord et al., 2017), which only affects the codebook and brings the selected code vector close the node embedding. The second term is the commitment loss (Van Den Oord et al., 2017), which only influences the node embedding and ensures the proximity of the node embedding the selected code vector. In practice, we can use exponential moving averages (Razavi et al., 2019) as substitute for the codebook loss.
Self-supervised Learning. The graph learning objective Lg can be self-supervised learning task, such as graph reconstruction (i.e., reconstructing the node features or adjacency matrix) or contrastive learning (Liu et al., 2021). 1). In this paper, we examine two representative models: GraphMAE (Hou et al., 2022) and GraphCL (You et al., 2020). We discuss GraphMAE here and address GraphCL in the App. A due to space limitations. Specifically, GraphMAE involves sampling a subset of nodes c V. masking the node features as X, encoding the masked node features using an MPNN, and subsequently reconstructing the masked features with decoder. The reconstruction loss is based on the scaled cosine error, expressed as:
1 1V
12 :7)
Lg LMAE
VEİ
where >> is the set of masked nodes, 2, = fo (h ) is the reconstructed node features by a decoder fp. h/ = (P,N( A, X), and y 2 1 is scaling factor. Let rn := h', denote the node embedding generated by the 1-th layer of the MPNN with the masked features. The overall training loss is
4

---

Published as a conference paper at ICLR 2025
L ΣΣΣ lisg(fim)) - Cerm + Bl sg(Cemm 311-
M
NID = MMA +
(9)
VED
Supervised Learning. The graph learning objective Lg can also be supervised learning task, such as node classification, link prediction, or graph classification. For classification tasks, Lg can be the cross-entropy loss between the target label y and the prediction Predout (see Eq. (2)):
gg = (yE breadou).
(10)
Remark. Our NID framework differs from VQ-VAR (Van Den Oord et al., 2017) and similar approaches (Lee et al., 2022; Yang al., 2024) in codebook learning. Unlike these methods, our training objective LNID does not involve using the code vectors (ex) for a reconstruction task. Instead, guide the codebook learning process solely via graph learning tasks (Cş). This is because experiments show that omitting the reconstruction loss has a negligible impact on performance (see Appendix D.5 for details). Moreover, our NID framework is compatible with any MPNN model. In experiments, We use popular models like GCN (Kipf& & Welling, 201 7), GAT (Veličković et al., 2018a), SAGE (Hamilton et al., 2017) and GIN (Xu al., 2018).
3.2 APPLICATIONS NODE IDS FOR GRAPH LEARNING
The generated node IDs can be considered as highly compact node representations and used directly for various downstream graph learning tasks, as outlined below.
Node-level tasks include node classification and node clustering. For node classification, each node in the graph is associated with label yu- representing category. We can directly utilize the node IDs of the labeled nodes to train an MLP network for classification. The prediction is formulated as
ye MLP (Node (
(11)
For node clustering, one can directly apply vector-based clustering algorithms such k-means (Mac- Queen et al., 1967) to the node IDs to obtain clustering results.
Edge-level tasks typically involve link prediction. The aim is to predict whether an edge should exist between any node pair (u, v). The prediction can be made by
(.n MLP(Node ID(u) @ Node ID(v)),
(12)
where 3 is the Hadamard product.
Graph-level tasks include graph classification and graph regression. These tasks involve predicting categorical label or numerical value for the entire graph G. The prediction can be formulated as
ig MLP Σ
Node (D))),
(13)
where global mean pooling function is applied on all the node IDs generate a representation for the graph G, which is then input into an MLP for prediction. Note that the selection of the readout function, such as mean pooling, is considered hyper- parametrr.
Remark. Due to the high compactness of the node IDs, which usually consists of multiple codewords (int4 type our experiments). the inference process of the aforementioned graph learning tasks can be greatly accelerated. Furthermore, as illustrated in Fig. 1, the node IDs represent high- level abstraction of structure-aware information graph, enabling them to achieve competitive performance across various tasks, as evidenced in our evaluation.
3.3 THEORETICAL ANALYSIS
We provide a theoretical analysis to verify the validity of the proposed method with simplified model. We prove the optimized codebook by VQ distinguish nodes based widely used data formulation, which leads to desired classification performance by training a linear layer.
Theoretical formulation. Consider node-level P-classification problem on a graph {V,E, X) with A RPVx|| as the adjacency matrix and Y the labels. We use one-layer GCN generate
5

---

Published as a conference paper at ICLR 2025
Table 1: Node classification results in supervised representation learning over homophilic and heterophilic graphs (%). The baseline results are primarily taken from Polynormer (Deng et al., 2024).
Transdactive
Cora
CiueSerr
PubMod
Computer
Photo
CS
Physics
WikiCS
Squired
Chameloon
Ratings
Questions
nodes
2,708
19,217
7,650
18,333
34,493
2223
850
24,4%2
48,921
4 edges
5,278
4,732
44,324
245.861
119,081
247.962
216,123
46,988
8,854
32.927
153,540
Metric
Accumeyt
Accuncyt
Accuncyt
Accuncyt
Accussyy
Accuracy
Accuracyt
Accuracy
Accuracy
Accuracy?
Accuracyt
ROC-AUC1
GPRGNN
39.32 and
94.49 2014
95.13 uca
96.35 aa
78.12 vn
38.95 .13
39.93 J33
44.38 vo
55,48 43
APPNP
87.87 1..
76.53
88.43 von
90.18 mm
94.32 .014
94.49 vmm
96.54 von
75.87 .m
5688
-1
41.62
52.74...
77.82 +:
SGFormer
77.24xcN
89.31
105
92.42 cn
95.58 103
95.71 1024
96.75
80.05.r
42.65
124
45.21
54.14
73.81 23
Polynoemer
88.11
76.77.13
87.39 aoo
93.18 a0a
96.11 102
95.51
97.22
79.53 vMa
40357
43.82.40
54.46 vok
78.92 .399
Graph MLP
87.06
68.93.om 76.4
90.78 cna
95.43
94.68 c0
95.45
75.35 c0
VQGirph
86.11-1m
75.64.m.
68.03
94.98
93.82.vor
95.93
ac.77
77.53 aco
90.04
93.78
96.14
95.94 u02s
97.36
90.91 voa
44.50
46.11
53.57 was
77.40
NIDggs
87.88 vr
76.89
80:42
voa
03.41 voe
96:17 ceM
95.52 vore 97.
78.55
45,09
46.29
53.55 am
96.8
GAT
18.
77.08 ac
89.47 and 93.53 anu
96.27..o. 2015
94.46 2014
97.17 a0n
80.98 via
38.72 1.0
43.44
100
54.88 vo
78.35 a.
NIDGK:
87.35 76.13
88.97
voe 93.38 vid
96.47 v0.
94. vore
97.13 wne 79.56 van
$7.68
42.83 .ce
54.92 m
97.08 -sr
the node embedding hy for E V.i.. h, = - ((() EveN(w) Wx,), where W E R xd and we assume (-) as an identity function. Given the obtained natural number Node [D(e_I(()) E N" for node E V. < K, we map each entry to a de-dimensional embedding, where different digits correspond to orthogonal embeddings. Hence, Node_ [I(v)) is projected to rde-dimensional vector, denoted by z.. We use nodes from VR to train a linear head V E Rrd, xP, i.e., miny [Vnl Evevn {(z.. Yo: V).
-y log (z, V)). Here y; is the one-hot vector of y: E N. where only the y + 1-th entry is 1 and others are 0. The classification error is defined by ly/, o arg [aX po.i] for o V. where pu,; is the i-th entry of p...
where (( Yo; V)- y. log(Pe)
We define a set of orthonormal vectors { For a P-classification problem (P < Q), denote {pr J== the set of discriminative patterns that directly determine the label, while {u.):=p4 as the set of -ondimccrimineiiee patterns that are irrelevant to the label. Specifically, we assume that for any node E V with label p [P], D. Mp or at least
of its neighbor equals Hy, and no neighbor of a, or itself equals μ, for j E [P],] + p. This formulation extends from binary node classification in (Zhang et al., 2023b; Li et al., 2024), which is verified on real-world datasets. We also assume rows of the optimized W by (7) are in directions of pa, i E [P] uniformly by theoretical findings in (Zhang et al., 2023b; Li al., 2024). Then, we have the following theorem.
Theorem 1. The optimizer C' of VQ objective (7) satisfies that, for any In and x.- u, U. E V with different labels, Node Node_ID(us [D(u) # Node_ID(u), Then, as long as VR uniformly include node IDs from all the classes, by training the linear head V with sufficient gradient descent steps, we can achieve that the classification error 1 [Bv # arg m
Pe..] = foror any U E V.
Remark. Theorem illustrates that the optimized C of VQ objective (7) ensures that the obtained IDs from different classes are distinct. Then, we demonstrate that with node IDs in the training set, linear head can be learned to achieve a zero classification error. The proof can be found App. B.
EVALUATION
In this section, we demonstrate the versatility of our NID framework across various graph learning tasks. We detail its application in two distinct scenarios:
Supervised representation learning for node classification, link prediction and graph classifi- cation. Here, we evaluate our NID against several SOTA models for graph representation learning, following learning protocols (Luo et al., 2024b; Rampášek et al., 2022; Wang et al., 2023c). Unsupervised representation learning for attributed graph clustering, node classification, and graph classification. In these unsupervised tasks, NID is benchmarked against well-known contrastive and generative SSL methods. We adhere strictly to the established experimental procedures as the standard settings (Bhowmick et al., 2024; Hou et al., 2022; You et al., 2020).
Detailed datasets, baselines, and hyperparameters are provided in App. C due to space constraints.
4.1 OVERALL PERFORMANCE
The learned node IDs, typically comprising 6 to 15 int4 integers, serve as effective node representations. They achieve competitive or superior performance across a wide range of tasks while significantly enhancing speed and memory efficiency, Additionally, our NID framework can be integrated with SOTA supervised or unsupervised GNN methods to enhance performance.
6

---

Published as a conference paper at ICLR 2025
Table 2: Node classification results in supervised representation Table 3: Graph-level performance in super-
learning on large-scale graphs (%).
vised representation learning from LRGB.
Transductive
oggnn-protcins
ogba-arxiv
ogbn-products
pokec
Inductive
Peptides-func
Peptides-struct
nodes
132,534
169,343
2,449,029
1,632,803
Avg. # nodes
150.9
150.9
eddees
39,561,252
1,166,243
61,859,140 Accuracyt
30,622,564 Accuracyt
Avg. # edges
307.3
307.3
Metric
ROC-AUCt
Accuracyt
Metric
APT
MAE]
GPRONN
75.68 acm
71.10 4012
79.76 am
78,83 Luv
LINKX
71.37
66.18 -03
71.59 aa
82.04 -o0
GT
0,6326 =00125
0.2529
a00006
GraphGPS
76.83 +036
70.97 -
00M
0OM
GraphGPS
0,6535 =0.041
0.2500
=000012
SGFormer
79.53
72.63 2033
74.16 sun
73.76
GRIT
0.6988
1000s
0.2460
100012
Polynormer
75.97 2040
7182 1023
82.97 402s
85.95 .oon
Exphormer Graph VIT
0.6527 00005
0.2481
100007
SAGE
79.43 4075
72.67 .am:
83.27 -a3s
85.97 nm
0.6970 =0.000
0.2449
0.0006
Infer. Time
158. lms
416.5ms
11.9%
129,6s
GCN
0.6762 400055
0.2512 0000077
Storage Space
129.4MB
165.7MB
1,9BB
1.6GB
Infer. Time
471.1ms
424.9ms
SAD
76.78 ass
70:52 2034
81.83 a0.
85.63 .n31
Infer. Time
0.4ms
0.3ms
0.7ms
1m.
NID
0.6608 200055
0.2589 x 100014
Storage Space
0.4MB
1.2MB
17,5MB
16.4MB
Infer. Time
0.4ms
0.4ms
Table 4: Link prediction in supervised representation Icarn ing. The baselines are from Wang et al, (2023c) (%).
90
Corn PubMed
Inductive
Cora
CiteSeer
PuhMed
ogbl-collab
Accuracy
80-
# nodes
2,708
3,327
19.717
235,868
# edges
5,278
4,552
44,324
1,285,465
70
Metric
HR 1000
1001
HI @ 1001
HR
SEAL
81.71
83.89
2115 75.54.
64.74 604
NBFret
71.65
74.07 113 58.73
00M
60
Neo GNN
80.42
84.67
411 73.93
1:39
57.52 n01
RUDDY
88.00 -om: 92.93
65.94- +4.1
1.5 101520
30
60
NCN
89.05 sum
91.56
79.05
64.76
The Ratio of Truiiiing Samples (%)
GCN
85.73 su
89.67 can
80.36 ess
64.05 100
Figure 4: Supervised node classification results of NIDeCN with varying ratios training samples.
Inference Time
44.2ms
51.5ms
102.
1ms
517.1ms
NIDEcN
90.33 s0.
88, e3
75.67 ...
64.31 2013
Inference Time
10.9ms
9.1ms
22.1ms
119.7ms
4.1.1 SUPERVISED NODE IDs FOR SUPERVISED REPRESENTATION LEARNING
Node Classification, Tables 1, 2, Figure 4. We have conducted extensive evaluations on homophilic and 4 heterophilic graphs, testing scalability on 4 targe-scale graphs, each with millions of nodes. Recently, Luo et al. (2024b; 2025b) observed that classic GNNs can achieve competitive performance in node classification with proper hyperparameter tuning. Building this, we implement our NID on GCN, GAT and SAGE, maintaining all experimental settings as described by Luo et al. (2024b), as they match the hyperparameter search space used in SOTA Polynormer (Deng et al., 2024). We compare NID against SOTA GNNs and Graph Transformers (GTs). Additionally, we compare NID against SOTA GNN-to-MLP methods VQGraph and Graph-MLP under the same settings.
As demonstrated in Table 1, our NID performs competitively with SOTA methods on both homophilic and heterophilic graphs suggesting that our compact discrete node IDs retain nearly all essential information compared to original GNN node embeddings. Furthermore, the performance comparison clearly shows the superior quality of our NID over SOTA GNN-to-MLP method VQGraph. Notably, NID surpasses all basclines across 4 heterophilic graphs. In detailed analysis of Questions, we observe that NID outperforms GCN by 20%. This dataset represents highly imbalanced binary classification task, with 98% of nodes classified into the same category. This example illustrates that the node IDs may preserve information beyond that of original GNN node embeddings.
As shown in Table 2, NID not only achieves near-SOTA performance on datasets with millions of nodes but also maintains fast inference times; notably, NID achieves a speed increase ranging from 400x to 17,000x faster than SAGE across 4 large graphs. Remarkably, our IDs require only a small fraction of labels for training. For instance, in the case of the ogbn-products dataset, only 8% of the data is used for training. We analyze the training ratio in Figure 4, showing that merely 15% of the training dataset is sufficient to train node IDs that achieve effective predictive performance.
Graph Classification, Table 3. We compare NID against SOTA GNNs and GTs designed for graph- level tasks on two peptide graph benchmarks from LRGB (Dwivedi et al., 2022): Peptides- and Peptides-struse We take all evaluation protocols suggested by Rampášek et al. (2022). As evidenced in Table 3. applying pooling to the node IDs achieves excellent performance with notable efficiency improvement, highlighting the potential of NID for supervised learning in graph-level tasks.
7

---

Published as a conference paper at ICLR 2025
Table 5: Attributed graph clustering results; normalized mutual information, and Fl-score (%)
Corn NMI
CiteSear NMI
PubMed NMI
Computer NMI
Photo
Physics NMI
ogba-arxiv
F11
Fi
Fi
FI
NMI1
F11
FI1
NMI
F11
SBM
36.2
30.2
15.3
19.1
16.4
16.7
48.4
34.6
59.3
47.4
45.4
30.4
31.9
28.3
AGC
34.1
28.9
25.5
27.5
18.2
18.4
51.3
35.3
59.0
44.2
STCN
27.9
29.9
31.4
41.9
19.5
29.9
24.9
45.2
41.7
45.1
50.4
39.9
15.3
28.8
DAEGC
4.3
18.0
42.5
37.3
NOCD
46.3
36.7
20.0
24.1
25.5
20.8
44.8
37.8
62.3
60.2
51.9
28.7
20.7
38.2
DifiPool
32.9
34.4
20.0
23.5
20.2
26.3
22.1
38.3
35,9
41.8
MinCut
35.8
25.0
25.9
20.1
25.4
15.8
48.3
24.9
36.0
27.1
Ortho
38.4
26.6
26.1
20.5
20.3
13.9
44.7
23.7
35.6
26.7
DMrN
48.8
48.8
33.7
43.2
29.8
33.9
49.3
45.4
63.3
61.0
56.7
42.4
37.6
45.7
DGCluster
62.1
54.5
41.0
32.2
32,6
34.6
60.4
52.2
77.3
75,9
65.7
49.2
31.2
32,4
Clustering Time
93.6ms
119.6ms
405.5ms
286.1ms
204.6ms
547.4ms
2.7s
NiDoacssses
73.9
54.1
50.9
62.1
58.2
75.4
65.4
Clastering Time
78.3ms
77.2ms
292.5ms
223.6m
140.6ms
442.0ms
1.8s
Table 6: Node classification results in unsu- pervised representation learning (%).
Table 7: Graph classification results in unsupervised representation learning on TUDataset; Accuracy (%)
Cora Accuracy?
CiteSoor Accuracyt
PubMed Accuracyt
NCII
PROTEINN
DD
MUTTN
COLLAB
RDTB B
RDT MSK
IMDB D
Metric
dim
grapts
4,110
1,113
1,178
183
5,000
2,000
4.999
1,000
Arg. modes
2988
39.1
264.3
17.9
74.5
429.7
508.5
19.3
GAE
71.5
65.8
IntoGraph
76.2
74.4
22.8.12
89.0
70.6
82.5
53.4.
a3.0
DGI
82.3 c3*
71.8 c07
76.8 2os
512
MVGRL
89.7
$4.5
T4.2
MVGRI.
83,5
73.3
80.1
512
10AD
73.3
74.0
27.
87.6
69.3
56.5
56.0
70.8
InfoGCL
83.5
73.5
79.1 s02
512
GrapEMAE
75.3
81.1
80.3
53.0
75.5
CCA-SSG
84.0-a4
73.
81.0
512
AD-OCL
69.6
73.5
74.4
v3.3
65.5
53.0
41.
GrapACL
77.8 vo
74.3
78.5
96.8
T1.3
k9.5
15.9
7M.1
MLP
17.8
14.7
73.3 ios
500
Nilks.
75.9
75.1
x7.8
88.6
76.9
98.7
35.0
v2.
GraphMAE
s34
c34
81.1
512
AutGCC
.2.
75.8
77.5 205
a8.6
70.1
58.5 a/
56.7
aM
NIDMAE
80.8 -33
74.2
76.4.02
NID
.8.
75.9 Ae
77.2
98.4
74.5
80.8 31
54.2
72.4
Link Prediction, Table 4. We test NID on 4 well-known link prediction benchmarks: Cora, Citeseer, Pubmed and ogbl-collab from the OGB (Hu et al., 2020), following the data splits, evaluation metrics and baselines specified by the NCN (Wang et al., 2023c). The results in Table 4 highlight NID's competitive performance, demonstrating both high accuracy and efficiency in link prediction tasks.
4.1.2 SELF-SUPERVISED NODE IDs FOR UNSUPERVISED REPRESENTATION LEARNING
Attributed Graph Clustering, Table Attributed graph clustering (Cai et al., 2018) focuses on clustering nodes in an attributed graph, where each node is associated with set of feature attributes. DGCluster (Bhowmick et al., 2024), utilizes GNNs optimize modularity for this task, representing the latest SOTA method. In this study, we apply the NID framework within DGCluster, quantizing the embeddings learned by the GCN in DGCluster into node IDs, which are then used for clustering, We select 7 datasets from DGCluster and adopt all experimental settings and baselines as described in DGCluster (Bhowmick et al., 2024). As demonstrated in Table 5, NIDpociuser outperforms all baseline models by considerable margin on 5 datasets and achieves significantly faster runtime 7 datasets due to the reduced dimensionality of our node IDs.
Node Classification, Table 6. We evaluate the performance of our NID on three standard benchmarks: Cora, CiteSeer, and PubMed (Yang et al., 2016). For this purpose, we employ GraphMAE to provide graph learning objective during the training of node IDs. Specifically, we train 2-layer GAT following the GraphMAE without supervision, resulting in the generation of 6-dim node IDs, denoted as NID Subsequently, we train an MLP and report the mean accuracy on the test nodes. For the evaluation protocol, we follow all the experimental settings used in GraphMAE (Hou et al., 2022), including data splits and evaluation metries, using all baselines reported by Hou et al. (2022). Table 6 lists the results. MI.P refers to predictions made directly on the initial node features. Notably, NIDMaE achieves competitive results comparison to SOTA self-supervised approaches, and even surpasses all other approaches CiteSeer. Remarkably, our node IDs comprised of only 6 discrete codes, with each code having a maximum of 32 possible values. This demonstrates that our NID effectively compresses the node's representation into concise yet information-rich ID.
Graph Classification, Tables 7 and 13. We evaluate our NID framework on datasets from TUDataset (Morris al., 2020): NCII, PROTEINS, DD, MUTAG, COLLAB. REDDIT-B, REDDIT- M5K, and IMDB-B, utilizing two different methods, GraphCL (You et al., 2020) and AutoGCL (Yin al., 2022), as graph learning objectives guide node IDs pre-training. Specifically, using
8

---

Published as a conference paper at ICLR 2025
Table 8: Comparison of codebook Table 9: Average GEDs of lhhop Table 10: Accuracy vs Inference Time. subgraphs among nodes.
usage rates (%).
Computer
ogbn products Acc"
Usago rate?
Cora
CiteSoer
PubMed
GEDsL
Corn
CiteSeer
PuhMad
Metric
Accf
Timel
Time]
82.33
12.8s
VQGraph
1.3
0.8
18.1
Random
7.21
4.83
9.61
SAGE
93.59
95.7ms
83.27
11.9s
NIDaeS
84.7
VQGraph
6.85
4.73
9.05
VQGraph
90.28
1.4ms
79.17
1.6ms
83.3
81.3
78.1
NIDocs
6.15
3.89
6.22
NIDS
93.32
0,5ms
81.83
0.7ms
Distribation of the First Node ID (Cys
Discibution of the Fourth Node ID (C21)
2.40
Tabe
Label D
Label 1
Label 2
1000
002
C11 (Principal Component code the Pinst GCN Layer)
Cy: (Principal Componeent
GCN Layer)
Figure 5: Codeword distributions of en and 621 in PubMed colored by the ground-trute labels.
GraphCL as an example, we employ GIN with the default settings from GraphCL as the GNN-based encoder, denoted as NIDeL. We adhere to the evaluation protocol outlined in GraphCL (You et al., 2020). The results are presented in Table 7, where NID outperforms all baselines on 3 out of datasets. This performance demonstrates that our NID is capable of learning meaningful information and demonstrates potential for application in graph-level tasks. Additional linear probing results on MoleculeNet datasets (Wu al., 2018) are discussed in App. D, showing consistent findings.
4.2 ANALYSIS OF NODE IDs
High Codebook Usage, Table 8. We calculate the codebook usage rates for VQGraph tokenizer and NID. We find that VQGraph suffers from severe codebook collapse (Dhariwal et al., 2020), where the majority of nodes are quantized into a small number of code vectors, leaving most of the codebook unused. In contrast, our NID achieves high codebook usage, effectively avoiding codebook collapse.
Qualitative Analysis, Figures 5, 7, 8. We analyze the supervised node IDs of NID for the PubMed dataset, depicted in Figures 5 & 7. The number of RVQ levels M is set to 3, and the MPNN layers I. is set to 2, with a codebook size K of 16. For given node ID (C11, 612, C13: C21, C22; C23) of node, 0 < Ctm < 15. The codes C11 and C21 capture the high-level information of the first and second MPNN layers, respectively. We present the distribution of C11 and C21 according to different labels. For instance, C11 10 generally corresponds to label "2". Similarly, the majority of nodes with 621 13 are labeled "1". Our node IDs have overlapping codewords for similar labels, allowing the model effectively share knowledge from similar nodes in the dataset.
Subgraph Retrieval, Table 9. We conduct node-centered subgraph retrieval using the supervised node IDs of NIDGcx on Cora, CiteSeer and PubMed. We identify the five nodes closest query node based on Hamming distances between their node IDs, then compute the average graph edit distance (GED) between the I-hop subgraph of the query node and the I-hop subgraphs of these five nodes. The average GED across all nodes is detailed in Table 9. For comparison, we also calculate the GEDs using the VQGraph tokens and the randomly selected nodes. The results show that node IDs perform better in subgraph retrieval, with similar IDs more likely to exhibit similar structures.
Acceleration in Inference Time, Table 10. We show the supervised node classification accuracy and model inference time on the Computer and geoduutroduct datasets in Table 10. Our results indicate that we achieve the high accuracy of 81 % and 93% while maintaining a fast inference time of 0.5ms and 0.7ms, respectively. Since the ogbn-products dataset contains over sixty million edges, graph loading is very slow. However, under the NID framework, we reduce the SAGE inference time from 11.9s to 0.7ms, demonstrating significant inference speedup of our approach in large networks.
Abltion Study of the Codebook Size K, RVQ Level M and MPNNs Layer L, Figure 6. First, examine the influence of the codebook size K. The optimal K varies across different graphs; however, generally. K < 16 yields the best performance on most datasets. A larger codebook size may lead codebook collapse, impairing performance. Second, regarding the RVQ level M,

---

Published as a conference paper at ICLR 2025
90
50
CleSses RuMMed opteoorch
80
Accuncy
80
Accomiy
70
70
The Codebook Steee RC
The RVQ M
Layer
Figure 6: Impact of codebook size, RVQ levels, and MPNN layers on node classification using NIDocv.
find that M performs the best, which validates our fixed choice. Notably, when M 1, RVQ degenerates into VQ, which leads to decreased performance. Third, the number of MPNN layers required also differs based on the graph size. For instance, smaller graphs like CiteSeer perform well with just 2 layers, while larger graphs, such ogbn-arxiv, may require more than 6 layers.
RELATED WORKS
Inference Acceleration for GNNs. GNNs are the preferred method for representation learning on graph-structured data but suffer from decreased inference efficiency as graph size and the number of layers increase, especially in real-time and resource-limited scenarios (Kaler et al., 2022). To address this issue, three main strategies are employed (Ma et al., 2024): knowledge distillation, model pruning, and model quantization. Knowledge distillation includes GNN-1o-GNN methods (Yan et al., 2020; Yang et al., 2022) and GNN-to-Mil MLL approaches (Hu et al., 2021; Yang et al., 2024)). Model pruning methods include UGS (Chen et al., 2021) and Snowflake (Wang et al., 2023a)). Lastly, model quantization methods include VQ-GNN (Ding et al., 2021) and QLR (Wang et al., 2023b)).
Graph Tokenization. In graph representation learning, significant strides have been made to vectorize structured data for downstream machine learning applications (Chami et al., 2022). Farly pionecring efforts, such as DeepWalk (Perozzi et al., 2014) and node2vec (Grover & Leskovee, 2016), popularized the concept of node embedding learning. Subsequently. GNNs have been extensively used as encoders to learn embeddings for graph tokens including nodes, edges, and (sub)graphs, with applications across various domains including molecular motifs (Liu al., 2024d; Rong et al., 2020; Zhang et al., 2021c; Luo et al., 2023a), recommendation systems (Tang et al., 2024; Liu al., 2024a), and knowledge graphs (Tang al., 2023; Lou al., 2023; Liang al., 2024b; 2023; 2024a). The emergence of Large Language Models (LL.M)) has spurred recent explorations into graph tokenization. Works like InstructGLM (Ye al., 2023), GraphText (Zhao al., 2023), and GPT4Graph (Guo et al., 2023) use natural language descriptions of graphs as tokens inputted to LLMs. Additionally, GraphToken (Perozzi al., 2024) integrates graph tokens generated by GNNs with textual tokens to explicitly represent structured data for LLMs.
Differences between Our NID and VQGraph. We clarify that our NID framework fundamentally different from VQGraph (Yang et al., 2024), even though both approaches utilize VQ techniques to tokenize nodes as discrete codes. VQGraph uses VQ- VAE (Van Den Oord et al., 2017) to obtain soft code assignments, which serve targets to aid the GNN-to-MI.P distillation process. However, similar to other GNN-to-MLP methods, VQGraph lacks the capability to generate interpretable node representations, limiting its application to supervised node classification. In contrast, NID framework is designed to learn compact discrect node representations in both supervised and unsupervised manners, enabling its use across wide range of downstream tasks. Moreover, VQGraph employs sizable codebook for tokenization, with capacity comparable to the size of the input graph, leading to codebook collapse (Tab. 8). In contrast, our NID tokenizer utilizes multiple, small-sized codebooks to achieve a large representational capacity and effectively prevents codebook collapse.
CONCLUSIONS
We have both empirically and theoretically validated the feasibility of learning highly compact, dis- crete, and interpretable codes (node IDs) as effective node representations for efficient graph learning. Our proposed NID framework can be seamlessly integrated with sfate-of-the-art unsupervised and supervised GNN methods to further enhance their performance. These findings have the potential to facilitate graph tokenization and applications involving large language models.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We extend our gratitude Yiwen Sun for her invaluable assistance. We also express our appreciation to all the anonymous reviewers and ACS for their insightful and constructive feedback. This work received support from National Key R&D Program of China 22021YF33000000) NSFC Grant 62172026, National Social Science Fund of China 22&2D153, the Fundamental Research Funds for the Central Universities, State Key Laboratory of Complex Critical Software Environment (SKI.CCSE), and the HK PolyU Grant POO5 1029. Lei Shi is with School of Computer Science and Engineering, Beihang University, and the State Key Laboratory of Complex Critical Software Environment.
REFERENCES
Mohammad Sadegh Akhondzadeh, Vijay Lingam, and Aleksandar Bojchevski. Probing graph representations. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 11630-11644 PMLR, 25 27 Apr 2023. URL www..rrreee//200/ooooooddddeee
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Aritra Bhowmick, Mert Kosan, Zexi Huang, Ambuj Singh, and Sourav Medya. Dgeluster: neural framework for attributed graph clustering via modularity maximization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 1069--11077, 2024.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning, pp. 874-883, PMLR, 2020.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. Proceedings of the web conference 2020, pp. 1400-1410, 2020.
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. arXiv preprint arXiv:2303.01022, 2023.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint 13Xiv:13/2.6203, 2013.
Hongyun Cai, Vincent Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE transactions knowledge and data engineering, 10977 2018.
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca. Thomas Markovich, Nils Yannick Hammerla, Michael M Bronstein, and Max Hansmire. Graph neu- ral networks for link prediction with subgraph sketching. In The eleventh international conference on learning representations, 2022.
Ines Chami, Sami Abu-Fil-Haja, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning graphs: A model and comprehensive taxonomy. Journal of Machine Learning Research, 23 189):1-64, 2022.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 23) 2011.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt, Structure-aware transformer for graph representation learning. In International Conference on Machine Learning. pp. 3489-3489. PMLR. 2022a.
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, 2022b.
11

---

Published as a conference paper at ICLR 2025
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International conference on machine learning, pp- 1695-1706. PMLR, 2021.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expressive graph transformer in linear time. arXiv preprint arXiv:2403.0/232, 2024.
Prafulla Dhariwal, Heewoo Jun, Christine Payne, Jong Wook Kim, Alec Radford, and Ilya Sutskever. Jukebox: A generative model for music. arXiv preprint arXiv:2005.0034/ 2020.
Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John Dickerson, Furong Huang, and Tom Goldstein. Vq-gnn: A universal framework to scale up graph neural networks using vector quantization. Advances in Neural Information Processing Systems, 34:6733-6746, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699 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, 2021.
Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. arXiv preprint arXiv:2206.08164 2022.
Vijay Prakash Dwivedi, Yozen Liu, Anh Tuan Luu, Xavier Bresson, Neil Shah, and Tong Zhao. Graph transformers for large graphs. arXiv preprint arXiv:2312.11109, 2023.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903, 02428, 2019.
Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5):75-174, 2010.
Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics reports, 659:1-44, 2016.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: 2018.
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. PMLR, 2017.
Robert Gray. Vector quantization. IEEE Assp Magazine, 1(2)4429 29, 1984.
Aditya Grover and Jure Leskovee. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 855-80 864, 2016.
Jiayan Guo, Lun Du, and Hengyu Liu. Gpt4graph: Can large language models understand graph structured data? empirical evaluation and benchmarking. arXiv preprint 1506:23355.50066 2023.
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-view view representation learning on graphs. In International conference on machine learning, pp. 41 16-4266. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2025
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-mixer to graphs. In International Conference on Machine Learning, pp. 12724-12745. PMLR, 2023.
Van Thuy Hoang, O Lee, et al. A survey on structure- structureepreseeringg preserving graph transformers. arXiv preprint arXiv:2401.16176, 2024.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjje Wang, and Jie Tang. Graphmae: supervied masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 594-594449 604, 2022.
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 1122118-22133 2020.
Weihua Hu*, Bowen Liu*, Joseph Gomes, Marinka Zitnik. Perey Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-tre mre-training graph neural networks. In International Conference Learning Representations, 2020. URL https://ppeneeiieee///fonnnnnnnp WIWISSHD
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: Node classification without message passing in graph. arXiv preprint arXiv:2106.0400 2021.
Zhihao Jia, Sina Lin, Rex Ying, Jiaxuan You, Jure Leskovec, and Alex Aiken. Redundancy-fres computation for graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 997-1005, 2020.
Biing-Hwand Juang and A Gray. Multiple stage vector quantization for speech coding. In ICASSP 82. IEEE International Conference Acoustics, Speech, and Signal Processing, volume 7, pp. 597- 600, IEEE, 1982.
Tim Kaler, Nickolas Stathas, Anne Ouyang, Sexandross-ttavre Iliopoulos, Tao Schardl, Charles E Leiserson, and Jie Chen. Accelerating training and inference of graph neural networks with fast sampling and pipelining. Proceedings of Machine Learning and Systems, 4: 4:17 2022.
Jinwoo Kim, Dat Nguyen, Sconwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Scunghoon Hong, Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems,
2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6980, 2014.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308. 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://openreview.nee/ forum?id=SJU4ayYye
Kezhi Kong. Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A global transformer on large-scale graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 17375-17390. PMLR, 23-29 Jul 2023. URL https://proceedings mlr pressss/ pr05s/v22// kong23a.htmi.
Ioannis Konstas, Vassilios Stathopoulos, and Joemon M Jose. On social networks and collaborative recommendation. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pp. 195-202, 2009.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létoumeau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-21666 116229699,, 2021.
13

---

Published as a conference paper at ICLR 2025
Weirui Kuang, WANG Zhen, Yaliang Li, Zhewei Wei, and Bolin Ding. Coarformer: Transformer for large graph via graph coarsening. 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.
Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection. 2014. 2016.
Hongkang Li, Meng Wang, Tengfei Ma, Sijia Liu, ZAIXI ZHANG, and Pin-Yu Chen. What improves the generalization of graph transformers? theoretical dive into the self-attention and positional encoding. In Forty-first International Conference on Machine Learning, 2024. URL
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference artificial intelligence, 2018.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. In Proceedings of the IEEE/CVF conference on computer vision and pallern recognition, pp. 9582-9591, 2019.
Ke Liang, Yue Liu, Sihang Zhou, Wenxuan Tu, Wen, Xihong Yang. Xiangjun Dong, and Xinwang Liu. Knowledge graph contrastive learning based on relation-symmeerical structure. IEEE Transactions on Knowledge and Data Engineering, 36( (:22))):22220 238,, 2023.
Ke Liang, Lingyuan Meng, Hao Li, Meng L Liu, Siwei Wang, Sihang Zhou, Xinwang Liu, and Kunlun He. Mgksite: Multi-modal knowledge-drive site selection via intra and inter-modal graph fusion. IEEE Transactions on Multimedia, 2024a.
Ke Liang, Lingyuan Meng, Meng Liu, Yue Liu, Wenxuan Tu, Siwei Wang, Sihang Zhou, Xinwang Liu, Fuchun Sun, and Kunlun He. A survey of knowledge graph reasoning on graph types: Static, dynamic, and multi-modal. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024b.
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-20902, 2021.
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-Seconl International Joint Conference Artificial Intelligence, IJCAI, pp. 2196-2205 2023.
Han Liu, Yinwei Wei, Xuemeng Song, Weili Guan, Yuan-Fang Li, and Liqiang Nie. Mmgrec: Multimodal generative recommendation with transformer model. arXiv preprint arXiv:2404. 16555, 2024a.
Qijiong Liu, Xiaoyu Dong, Jiaren Xiao, Nuo Chen, Hengchang Hu, Jieming Zhu, Chenxu Zhu, Tetsuya Sakai, and Xiao-Ming Wu. Vector quantization for recommender systems: A review and outlook. arXiv preprint arXiv:2405.031110 2024b.
Qijiong Liu, Hengchang Hu, Jiahao Wu, Jieming Zhu, Min-Yen Kan, and Xiao-Ming Wu. Discrete semantic tokenization for deep ctr prediction. arXiv preprint arXiv:2403.0822 2024c.
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self- supervised learning: Generative or contrastive. IEEE transactions on knowledge and data engi- neering, 35(1):857-876 2021.
Zhiyuan Liu, Yaorui Shi, An Zhang, Enzhi Zhang, Kenji Kawaguchi, Xiang Wang, and Tat-Seng Chua. Rethinking tokenizer and decoder masked graph modeling for molecules. Advances in Neural Information Processing Systems, 36, 2024d.
14

---

Published as a conference paper at ICLR 2025
Yunzhong Lou, Xueyang Li, Haotian Chen, and Xiangdong Zhou. Brep-bert: Pre-training boundary representation bert with sub-graph node contrastive learning. Proceedings of the 32nd ACM International Conference Information and Knowledge Management, pp. 1657-1666, 2023.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its upplications, 390(6): 150-1170, 2011.
Yuankai Luo, Lei Shi, and Veronika Thost. Improving self-supervised molecular representation leamn ing using persistent homology. In Thirty-seventh Conference on Neural Information Processing Systems, 2023a. URL https://peeaeiieeeeccooooottttte
Yuankai Luo, Lei Shi, Mufan Xu, Yuwen Ji, Fengli Xiao, Chunming Hu, and Zhiguang Shan. Impact- oriented contextual scholar profiling using self-citation graphs. arXiv preprini arXiv:2304. 12217, 2023b.
Yuankai Luo, Hongkang Li, Lei Shi, and Xiao-Ming Wu. Enhancing graph transformers with hierarchical distance structural encoding. In The ehirty-eighth Annual Conference on Neural Information Processing Systems, 2024a. URL
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Classic gnns are strong baselines: Reassessing gnns for node classification. arXiv preprint arXiv:2406.0899 2024b.
Yuankai Luo, Veronika Thost, and Lei Shi. Transformers over directed acyclic graphs. Advances in Neural Information Processing Systems, 36, 2024c.
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Unlocking the potential of classic gnns for graph-level tasks: Simple architectures meet excellence. arXiv preprint arXiv:2502.09263, 2025a.
Yuankai Luo, Xiao-Ming Wu, and Hao Zhu. Beyond random masking: When dropout meets graph convolutional networks. The Thirteenth International Conference on Learning Representations, 2025b. URL http:///poaaeveieeeeee//ooneecee
YoMMwyy..
Liheng Ma. Chen Lin, Derek Lim, Adriana Comero-Soriange Puncet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing, arXiv preprint 23X.:23305.15888 2023.
Lu Ma, Zeang Sheng, Xunkai Li, Xinyi Gao, Zhezheng Hao, Ling Yang. Wentao Zhang, and Bin Cui. Acceleration algorithms in gnns: A survey. arXiv preprint 2rXii:2405.04144 2024.
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium mathematical statistics and probability, volume 1, pp. 281-297. Oakland, CA, USA, 1967.
Julieta Martinez, Holger H Hoos, and James J Little. Stacked quantizers for compositional vector compression. arXiv preprint arXiv:/41/ 1. 173, 2014.
Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and com- plementary products. In Proceedings of the 2/th ACM SIGKDD international conference knowledge discovery and data mining, pp. 785-794, 2015.
Fabian Mentzer, David Minnen, Eirikur Agustsson, and Michael Tschannen. Finite scalar quantization: VQEVAE made simple. In The Twelfth International Conference on Learning Representations, 2024. URL http:///wwwwweeeee////////n///aa
Péter Mernyei and Cătälina Cangea. Wiki-es: wikipedia-based benchmark for graph neural networks. arXiv preprint arXin:2007.0090),,200
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs arXiv preprint arXiv:2007.08663, 2020.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers. arXiv preprint arXiv:2302.04181, 2023.
15

---

Published as a conference paper at ICLR 2025
Hongbin Pei, Bingzhe Wei, Kevin Chen- Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2019.
Tiago P Peixoto. Efficient monte carlo and greedy heuristic for the inference of stochastic block models. Physical Review E, (9(1):012804) 2014.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 701-710, 2014.
Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami AI-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862, 2024.
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? arXiv preprint arXiv:2302. 1/640, 2023.
Haohao Qu, Wenqi Fan, Zihuai Zhao, and Qing Li. Tokenrec: Learning to tokenize id for Ilm-based generative recommendation. arXiv preprint arXiv:2406. 10450, 2024.
Shashank Rajput, Nikhil Mehta, Anima Singh, Raghunandan Hulikal Keshavan, Trung Vu, Lukasz Heldt, Lichan Hong, Yi Tay, Vinh Tran, Jonah Samost, et al. Recommender systems with generative retrieval. Advances in Neural Information Processing Systems, 36, 2024.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. arXiv preprint arXiv:2205. 12454, 2022.
Bharath Ramsundar, Peter Eastman, Patrick Walters, and Vijay Pande. Deep learning for the life sciences: applying deep learning to genomics, microscopy, drug discovery, and more. O' O'Reilly Media, 2019.
Ali Razavi, Aaron Van den Oord, and Oriol Vinyals. Generating diverse high-fidelity images with vq-vae-2. Advances in neural information processing systems, 32, 2019.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer large-scale molecular data. Advances in neural information processing systems, 33: 13559-11125 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnab014, 2021.
Oleksandr Shchur and Stephan Günnemann. Overlapping community detection with graph neural networks. arXiv preprint arXiv: /909. /2201, 2019.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. arXiv preprint a7Xiv:2303.06147, 2023.
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. Advances in neural information processing systems, 29, 2016.
Fan- Run-Yu Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv: /908: 0000, 2019.
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systemx, 34:15920-15933, 2021.
Jiabin Tang, Yuhao Yang. Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. arXiv preprint arXiv:2310.1330 13023, 2023.
16

---

Published as a conference paper at ICLR 2025
Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Long Xia, Dawei Yin, and Chao Huang. Higpt: Heterogeneous graph language model. arXiv preprint arXiv:2402.16024, 2024.
Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang. and Nitesh Chawla. Learning mips on graphs: A unified view of effectiveness, robustness, and efficiency. In The Eleventh International Conference on Learning Representations, 2022.
Yijun Tian, Shichao Pei, Xiangliang Zhang, Chuxu Zhang, and Nitesh V Chawla. Knowledge distillation on graphs: A survey. arXiv preprint arXiv:2302.002/9, 2023.
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth, and Martin Grohe Where did the gap go? reassessing the long-range graph benchmark. arXiv preprint arXiv:2309.00367, 2023.
Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24(127):1-21, 2023.
Aaron Van Den Oord, Oriol Vinyals, et al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018a.
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. arXiv preprint arXiv:1809.10333 2018b.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
Chun Wang. Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Atrrbuted graph clustering: A deep attentional embedding approach. arXiv preprint orXiv:1906.06520 2019a.
Kun Wang, Guohao Li, Shilong Wang, Guibin Zhang, Kai Wang, Yang You, Xiaojiang Peng, Yuxuan Liang, and Yang Wang- The snowflake hypothesis: Training deep gnn with one node one receptive field. arXiv preprint ar0ivv2308. 10051, 2023a.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performan package for graph neural networks. arXiv preprini arXiv: arXiv:1909.0111 1900001355 2019b.
Shuang Wang, Bahaeddin Eravei, Rustam Guliyev, and Hakan Ferhatosmanoglu. Low-bit quantization for deep graph neural networks with smoothness-awan message propagation. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 2626-2636. 2023b.
Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. arXiv preprint arXiv:2302.008: 2023c.
Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information P Processing Systems, 35:27387-27401 2022.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang. Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for prage-graphho representations. In Thirty- seventh Conference on Neural Information Processing Systems, 2023. URL https///openreview.ned/ DRWpp.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9():51335300 2018.
Jun Xia. Chengshuai Zhao, Bozhen Hu, Zhangyang Gao, Cheng Tan, Yue Liu, Siyuan Li, and Stan Li. Mole-bert: Rethinking pre-training graph neural networks for molecules. 2023.
17

---

Published as a conference paper at ICLR 2025
Yan Xia, Hai Huang, Jieming Zhu, and Zhou Zhao. Achieving cross modal generalization with multimodal unified representation. Advances in Neural Information Processing Systems, 36, 2024.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. Advances in Neural Information Processing Systems, 34: 30414-30425, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXi::1810.0088 2018.
Bencheng Yan, Chaokun Wang, Gaoyang Guo, and Yunkai Lou. Tinygnn: Learning efficient graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1848-1856, 2020.
Chenxiao Yang, Qitian Wu, and Junchi Yan. Geometric knowledge distillation: Topology compression for graph neural networks. Advances in Neural Information Processing Systems, 35:29761-29775. 2022.
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. URL http:://wwwooooeeee//////oo/t//d
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. Natural language is all graph needs. arXiv preprint arXiv:2308.07133 2023.
Yihang Yin, Qingzhong Wang, Siyu Huang, Haoyi Xiong, and Xiang Zhang. Autogel: Automated graph contrastive learning via learnable view generators. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp.
2022.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, $4:28877-28888, 2021.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33: 5812-5823, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pp. 12121-12132. PMLR, 2021.
Scongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neigh- borhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34: 14:13683-13694, 2021.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference Learning Representations, 2023a. URL https://peanrevio..efffooo Niw
Dalong Zhang, Xin Huang. Ziqi Liu, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Zhiqiang Zhang, Lin Wang, Jun Zhou, Yang Shuang, et al. Agl: a scalable system for industrial-puns -purposee graph machine learning. arXiv preprint arXiv:2003. 02400..02444... 2020.
Hengrui Zhang. Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-super graph neural networks. Advances in Neural Information Processing Systems, 34:76-89, 2021a.
18

---

Published as a conference paper at ICLR 2025
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. Advances in neural information processing systems, 31, 2018.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah, Graph-less neural networks: Teaching old mlps new tricks via distillation. arXiv preprint arXiv:2110008727, 2021b.
Shuai Zhang, Meng Wang. Pin-Yu Chen, Sijia Liu, Songtao Lu, and Miao Liu. Joint edge-model sparse learning is provably efficient for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b. URL http://ppeeeeveeeweee/m/mdd-dddd
CVF.
Xiaotong Zhang. Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. arXiv preprint arXiv: 100,001000 2019.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee. Motif-based graph self- supervised learning for molccular property prediction. Advances in Neural Information Processing Systems, 34:15870-15882, 2021c.
Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoning in text space. arXiv preprint 1rXiv:2310.01089, 2023.
Sipeng Zheng, Bohan Zhou, Yicheng Feng, Ye Wang, and Zongqing Lu. Unicode: Learning a unified codebook for multimodal large language models. arXiv preprint arXiv:2403.09072. 2024.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 1-29476-29499) 2021.
19

---

Published as a conference paper at ICLR 2025
A SELE-SUPERVISED NODE IDs USING GRAPHCL
In this section, we discuss GraphCL (You et al., 2020) as self-supervised learning (SSL) model for self-supervised Node IDs. Contrastive learning aims at learning an embedding space by comparing training samples and encouraging representations from positive pairs of examples to be close in the embedding space while representations from negative pairs are pushed away from each other. Such approaches usually consider each sample its own class, that is, positíve pair consists of two different views of it; and other samples in batch are used as the negative pairs during training.
Specifically, minibatch of N graphs is randomly sampled and subjected to contrastive learning. This process results in 2N augmented graphs, along with a corresponding contrastive loss to be optimized. We redefine žn,i and zn.j for the 1-th graph in the minibatch. Negative pairs are not explicitly sampled but are instead generated from the other N augmented graphs within the same =n,
minibatch. The cosine similarity function is denoted as Zn,;; kn.j) = || Illl The NT-Xent loss (Sohn, 2016) for the n-th graph is then defined as:
(op(sim(zn.::2..)))
LurphiC. log
E Ln'=1,' exp(sim(zn,t Zut 3//)
n R (MPNN( An,i xx,)))
where 7 represents the temperature parameter. The final loss is computed across all positive pairs in the minibatch. Consequently, Equation 7 is reformulated as:
CNID = -GraphicL +
Σ
Σ
EvolUna)+ Σ
Evo(uns)s
(14)
nE(N,]] E,,
B PROOF OF THEOREM
Proof. For node V with label p E 1, 1J. by data formulation in Section 3.3, have that there exists at least one node u E ((e) that satisfies I. = Hpp Given (7), let the first-round
clustering center for v be c, = c!l + ct where ell is in the direction of W M4 and of 1 W Up. By the assumption on W, we know that W 1 W uj i + j. i [P]. and W Wy,- = 0 for > P. Therefore.
Σ
Wo. - c,,l2
W(D)
ueN
(15)
=I [(O
Σ
Wa.. - c W(v)
Σ
Wa, - 122
uENu.
Note that there is no node u E (v) such that x. = H for j + and j E [P]. Therefore, we can show that the optimized cl! by (7) in the direction of W Up. and
1
|c!!
(16)
Dg
since that
Σ
1|2, = Upl 2 Dg
(17)
NEN,
Hence, we obtain that the optimized clustering center Co and c.2 for U1, Uh V with Ve, Yerr we have
||e,, Copl > V2
S((1,
(18)
Dg
which means that Co2 and co2 are distinct enough given Dg < O(1). Then, we have
Node_ID(1)) * Node_ID(va2.
(19)
20

---

Published as a conference paper at ICLR 2025
Then, analyze the learning process with linear layer. Let V (V1, U2,... Up)) The gradient of the loss function against Vj, J E [P]. is computed as
0l(zu, Mui V)
Val
DEVn
[Val
Σ
Po.j
Po -Dooj) +
[vll
Σ
Pu.j
(- DuiiDoo))
(20)
vEVn.yo=)
vEVn.vo=j+t)
Σ
(Prij - 1)20 +
Σ
Pug Zn.
[V
Vn
DEVR.N==j
vEVn..==(+)
Note that Pe.j - 1 O. Pe.j' > iteration V follows a Gaussian distribution and is close to which makes the distribution of { close to uniform. Therefore, after T iterations, we have that
= -
Σ
(1-Peu (ospe
Σ
Peit Zu:
VR
V
(21)
DE VEVR.V==j
VEVR.N==**j
where 7) & O(1) is the step size. We know that for all the nodes v E VR with ye = j. the first de
dimensions the same. Denote the first de dimensions of (T) as V "i Then, after T = O iterations, the magnitude of v (T) j,1:d, in the direction of the embedding of the first digit of Node [
(T)
is
Q(1 PP)
7
1 1| 2(1).
(22)
VR BEVn
(T) Moreover, the magnitude Iid, in the direction of the embedding of other digit of Node_ID(v)
-Q(n P)
7 VR vEVR
-/ -
(23)
Note that the probability of de -imennioonl embedding for other digits other than the first one is ((/K)). Hence, by r < K, we can ensure that the first de dimensions are the dominant part for prediction. Therefore, for given zu for
G. yo
have
z o3 2 2(1),
(24)
so that
Po > po.j'.
(25)
We can then derive that for any u E V.
1 [yv * arg max Po.i]
(26)
:E(P)
C DATASETS AND EXPERIMENTAL DETAILS
C.1 COMPUTING ENVIRONMENT
Our implementation is based on PyG (Fey & Lenssen, 2019) and DGL (Wang et al., 2019b). The experiments are conducted single workstation with 8 RTX 3090 GPUs.
C.2 DESCRIPTION OF DATASETS
Table 11 presents summary of the statistics and characteristics of the datasets. The initial eight datasets are sourced from TUDataset (Morris et al., 2020), followed by two from LRGB (Dwivedi et al., 2022), and finally the remaining datasets are obtained from Hu et al. (2020); Kipf & Welling (2017); Chien et al. (2020); Pei et al. (2019); Rozemberezki et al. (2021); McAuley et al. (2015); Leskovec & Krevl (2016); Mernyei & Cangea (2020); Lim et al. (2021); Platonov al. (2023).
21

---

Published as a conference paper at ICLR 2025
Table 11: Overview of the graph learning dataset used in this work (Morris al., 2020; Dwivedi et al., 2022; Kipf Welling, 2017; Chien et al., 2020; Pei al., 2019; Rozemberczki et al., 2021; Hu al., 2020; McAuley et al., 2015; Leskovec & Krevi, 2016; Mernyei & Cangea, 2020; Lim et al., 2021; Platonov et al., 2023).
Dataset
# Graphs
Avg. # nodes
Avg. # edges
Feats
Prediction level
Prediction task
Metric
Cora
2,708
5,278
2,708
node
7-class classif.
Accuracy
Citeseer
3,327
4,522
3,703
node
6-class classif.
Accuracy
Pubmed
44,324
500
3-class classif.
Accuracy
Computer
13.752
245,861
767
node
10 class classif.
Accuracy
Photo
7,650
119,081
745
node
8-class classif.
Accuracy
CS
18,333
81,894
6,805
nade
15 class classif.
Accuracy
Physics
34,493
247,962
8,415
node
5-class classif.
Accurncy
WikiCS
11,701
216,123
300
node
10-class classif.
Accuracy
Squirrel
2,223
46,998
2,089
node
5-class classif.
Accuracy
Chameleon
890
8,854
2,325
node
5-class classif.
Accuracy
Amazon Aanzon-ratings
24,492
93,050
300
nade
class clussif.
Accuracy
Questions
48,921
153,540
301
node
2-class classif.
ROC-AUC
ogbn-arxiv
169.343
1,166,243
128
node
40-class classif.
Accuracy
ogbn-pen proteins
132.534
39,561,252
8
node
112 binary classil.
ROC-AUC
oghn products
2,449,0229
61,859,140
100
made
47 class classif.
Accuracy
pokec
1,632,803
30,622,564
65
node
hinary classif.
Accurney
ogbl-collab
235,868
1,285,465
128
odge
link prediction
Hits@50
Peptides-func
15,535
150.9
307.3
gruph
10-tnsk classif.
AP
Poptides-struct
15,535
150.9
307.3
graph
11-task regression
MAE
NCI1
4,110
29.87
32.30
37
graph
2-class classif.
Accuracy
MUTAG
188
17.93
19.79
7
graph
2 2-class classif.
Accuracy
PROTEINS
1,113
39.06
72.82
3
graph
2. class clussif.
Accuracy
DD
1,178
284.32
715.66
89
graph
2-class classif.
Accuraey
COLLAB
5,000
74.49
2457.78
graph
3-class classif.
Accuracy
REDDIT-BINARY
2,000
429.63
497.75
graph
2-class classif.
Accuracy
REDDIT-MULTI-SK
4,999
508.52
594.87
graph
S-class classif.
Accuracy
IMDB-BINARY
1,000
19.77
96.53
graph
2-class classif.
Accuracy
Supervised Node Classification: Cora, Citeseer, Pubmed, Computer, Photo, CS, Physics, WikiCS, Amazon-ratings, Questions, Squirrel, Chameleon, ogbn-arxiv, ogbn-proteins, ogbn-proo products and pokec. For Cora, Citeseer, and Pubmed, we employ a training/validationnessnng split ratio of 60%/20%/20% and use accuracy the evaluation metric, consistent with Pei et al. (2019). For Squirrel, Chameleon, Amazon-ratings and Questions, we adhere to the standard splits and evaluation metrics outlined in Platonov et al. (2023). For the remaining datasets, standard splits and metrics are followed as specified in Luo et al. (2024b). For comprehensive details on these datasets, please refer to the respective studies (Pei et al., 2019; Luo et al., 2024b).
Supervised Link Prediction: Cora, Citeseer, Pubmed, ogbl-collab. We follow the standard splits and evaluation metrics specified in Wang et al. (2023c), with further details provided therein.
Supervised Graph Classification: Peptides-fung and Peptides-struct. For each dataset, follow the standard train/ valiiationttttt splits and evaluation metrics in Rampášek et al. (2022). For more comprehensive details, readers encouraged to refer to Rampášek et al. (2022).
Attributed Graph Clustering: Cora, Citeseer, PubMed, Computer, Photo, Physics, ogbn-arxiv. To evaluate the clustering performance, we adopt two performance measures: NMI and F1, following the approach used DGCluster (Bhowmick et al., 2024).
Unsupervised Node Classification: Cora, Citeseer, Pubmed, For each dataset, we follow the standard splits and evaluation metries in GraphMAE (Hou et al., 2022).
Unsupervised Graph Classification: NCII, PROTEINS, DD, MUTAG, COLLAB, REDDIT-B, REDDIT-M5K, and IMDB-B. Each dataset is collection of graphs where each graph is associated with a label. Each dataset consists of a set of graphs, with each graph associated with a label. For NCII. PROTEINS, DD, and MUTAG, node labels serve as input features, while for COLLAB, REDDIT-B, REDDIT-MSK, and IMDB-B, B, node degrees are utilized. In each dataset, we follow exactly the same data splits and evaluation metires the standard settings (You et al., 2020).
22

---

Published as a conference paper at ICLR 2025
C.3 BASELINES
Attributed Graph Clustering. We apply baseline methods from DGCluster (Bhowmick et al., 2024): SBM (Peixoto, 2014), AGC Zhang et al. (2019), SDCN (Bo et al., 2020), DAEGC (Wang al., 2019a), NOCD (Shchur & Günnemann, 2019), DiffPool (Ying et al., 2018), MinCut (Bianchi et al., 2020), Ortho (Bianchi et al., 2020), DMoN (Tsitsulin et al., 2023) and DGCluster (Bhowmick et al., 2024).
Unsupervised Node Classification. We utilize all the baselines from GraphMAE (Hou et al., 2022):
GAE (Kipf & Welling, 2016), DGI (Veličković et al., 2018b), MVGRL (Hassani & Khasahmadi, 2020), InfoGCL (Xu et al., 2021), CCA-SSG(Zhang et al., 2021a) and GraphMAE (Hou et al., 2022).
Unsupervised Graph Classification. We utilize the baselines from GraphCL (You et al., 2020) and AutoGCL (Yin et al., 2022): InfoGraph (Sun et al., 2019), MVGRL (Hassani Khasahmadi, 2020), GraphCL (You et al., 2020), JOAO (You et al., 2021), GraphMAE (Hou et al., 2022), AD-GCL Suresh et al. (2021) and AutoGCL (Yin et al., 2022).
Supervised Node Classification. We compare our method to the following prevalent GNNs and transformer models from Polynormer (Deng et al., 2024): GCN (Kipf & Welling, 2017), SAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018 APPNP (Gasteiger et al., 2018), GPRGNN (Chien et al., 2020), LINKX (Lim et al., 2021), Polynormer (Deng et al., 2024), SGFormer (Wu et al., 2023). Furthermore, various other GTss like (Kong et al., 2023; Wu et al., 2022; Chen et al., 2022b; Rampášek et al., 2022: Shirzad et al., 2023; Dwivedi et al., 2023; Liu et al., 2023; Zhang et al., 2023a; Kuang et al., 2021; Luo et al., 2024a; Bo et al., 2023; Chen al., 2022a; Ying et al., 2021; Dwivedi & Bresson, 2020) exist in related surveys (Hoang et al., 2024; Müller et al., 2023), empirically shown to be inferior to the GTs we compared against for node classification tasks.
Supervised Link Prediction. We employ all the baselines from NCN (Wang et al., 2023c); GCN (Kipf & Welling, 2017), SEAL (Zhang & Chen, 2018), NBFnet (Zhu et al., 2021), Neo-GNN (Yun et al., 2021), BUDDY (Chamberlain et al., 2022), NCN (Wang et al., 2023c).
Supervised Graph Classification. We compare our method to the GCN (Kipf Welling, 2017). In terms of transformer models, we consider GT(Dwivedi & Bresson, 2020), Graph ViT (He et al., 2023), Exphormer (Shirzad et al., 2023), GraphGPS (Rampášek et al., 2022), and GRIT (Ma et al., 2023).
We report the performance of baseline models using results from their original papers or official leaderboards, where available, as these are derived from well-tuned configurations. For baselines without publicly available results on specific datasets, we tune their hyperparameters within our search space and tune their unique hyperparameters (not present in MPNNs) according to the search space specified in their original papers to attain the best possible results.
C.4 HYPERPARAMETERS AND REPRODUCIBILIIT
Our source code is available at
RVQ Implementation Details. As outlined in See. 3.1, RVQ is used to quantize the MPNN multi- layer embeddings of a node. The selection of MPNNs and the number of layers L are tailored to distinct datasets. For the embeddings from each layer, a consistent three-level (M = 3) residual quantization is implemented. And cosine similarity serves as the distance metric || within the RVQ framework. The codebook size K is tuned {4, 6, 8, 16, 32). The is set to 1.
For the hyperparameter selections of our NID framework, in addition to what we have covered, we list other settings Table 12. The tasks are presented in the following order: attributed graph clustering, unsupervised node classification, unsupervised graph classification, supervised node classification, supervised link prediction, and supervised graph classification. Below we detail the experimental settings for pretraining the node ID.
Attributed Graph Clustering. We implement our NID on top of the GCN in DGCluster (Bhowmick al., 2024). To ensure a fair comparison, we the same hyperparameters, including the number of layers, learning rate, hidden dimensions, and clustering method, as in DGCluster (Bhowmick et al., 2024).
23

---

Published as a conference paper at ICLR 2025
Table 12: Task-ipecific hyperparameter settings of NID framework. The tasks presented in the following order: attributed graph clustering. unsupervised node classification, unsupervised graph classification, supervised node classification, supervised link prediction, and supervised graph classification.
Dataset
Codebook size K
MPNN
MPNNs layer I.
Hidden dim
LR
epoch
MLP layer
Cora
GCN
256
0.001
300
Citeseer
6
GCN
256
0.001
300
Pubmed
OCN
Computer
6
GCN
256
0.001
300
Photo
6
GCN
256
0.001
300
Physics
GCN
256
0.001
300
oghn-arxiv
6
GCN
256
0.001
300
Cura
32
GCN
1024
0.001
1500
Ciesser
GCN
256
0.001
500
Pubmed
16
GCN
128
0,0005
500
NCHI
GIN
0.01
MUTAG
16
GIN
32
0.01
20
PROTEINS
GIN
32
0.01
DD
4
GIN
32
0.01
20
COLLAB
32
GIN
32
0.01
20
REDDIT-RINARY
GIN
0.01
REDDIT-MULTI-SK
4
GIN
32
0.01
20
IMDB-BINARY
GIN
Cora
6
GCN
128
0.01
1000
Citeseer
8
GCN
128
0.01
Pubmed
16
GCN
256
0.005
1000
Computer
GAT
0.001
Photo
4
GAT
512
0.001
1200
CS
16
GAT
512
0.001
1600
Physics
4
GAT
512
0.001
1600
WikiCS
8
GAT
512
0.001
1000
Squirell
8
GCN
64
0.005
Chameleon
32
GCN
256
0.005
1000
Amazon-ratings
GAT
Questions
4
GAT
512
0,000003
1500
ogbn-arxiv
16
SAGE
256
0.0005
1000
ogbn proteins
4
SAGE
256
0,0005
1000
oghn- products
16
SAGE
128
0.003
1000
16
SAGE
256
0,0005
2000
Cora
32
GCN
256
0.004
150
Cileseer
8
GCN
256
0.01
Pubmed
8
GCN
256
0.01
100
ogbl-collab
16
GCN
256
0.001
Peptides-func
16
GCN
235
0.001
500
Peptides-struct
16
GCN
235
0.001
250
Unsupervised Node Classification. The pretraining hyperparameters selected within the Graph- MAE's grid search space, as outlined in Table 12. All other experimental parameters, including dropout, batch size, training schemes, and optimizer, etc., align with those used in GraphMAE (Hou et al., 2022).
Unsupervised Graph Classification. Similarly, our pretraining hyperparameters table are deter- mined within GraphCL's grid search space. All other experimental parameters match those used in GraphCL (You al., 2020). Specially for this task, following GraphCL. (You al., 2020), we input NIDeL codes into a downstream LIBSVM (Chang & Lin, 201 1) classifier. And models are trained conduct a 10-fold cross-validation on every dataset.
for 20 epochs and tested every 10 epochs. For each fold, we utilize 90% of the total data as the unlabeled data and the remaining 10% as the labeled testing data. Every experiment is repeated times using different random seeds, with mean and standard deviation of accuracies (%) reported.
Supervised Node Classification. The pretraining hyperparameters listed the table are based on the grid search space from Luo et al. (2024b). All other experimental parameters follow those outlined in the same study.
Supervised Link Prediction. Our pretraining hyperparameters in table are chosen from the NCN's grid search space. All other experimental parameters match those used in NCN (Wang et al., 2023c). For the Cora, CiteSeer, and PubMed datasets, employ the Hadamard product as the readout
24

---

Published as a conference paper at ICLR 2025
function. For ogbl-collab, (Wang et al., 2023c; Barabási Albert, 1999) to nodes u and v for the edge (u, v).
pooling on the node IDs of the 1-hop common neighbors
Supervised Graph Classification. All experimental parameters consistent with those used by Tönshoff et al. (2023); Luo et al. (2025a).
Applications of Node IDs for Graph Learning. After obtaining the ID, train the Multi-Layer Perceptron (MLP) for different tasks, with the number layers specified in Table 12 and hidden dimensions of either 256 or 512. We utilize the Adam optimizer (Kingma & Ba, 2014) with the default settings. We set learning rate of either 0.01 or 0.001 and an epoch limit of 1000. The ReLU function serves the non-linear activation. Further details regarding hyperparameters can be found in the code in the supplementary material. In all experiments, we use the validation set to select the best iyperparameters. All results are derived from 10 independent runs, with mean and standard deviation of results reported.
D ADDITIONAL RESULTS
D.1 QUALITATIVE ANALYSIS
Batdeeike (9g)
Catrbeske Swced Bua)
Ditrbeake Tiid reg)
204
Deoohalie (Pa)
Figure 7: The codeword distributions of the node IDs in PubMed colored by the ground tround-truth labels.
Ditelatin the Fird Nak- iPa)
Diteiladinn of Smadd Nidk
Diddiadeen de Tild Sela iea)
Darichetina Note 18
Deestratoo de Sode 1002
Zbeshetim Sata Sode
Figure The codeword distributions the node IDs in CiteScer colored by the ground-truth labels.
25

---

Published as a conference paper at ICLR 2025
D.2 ADDITIONAL LINEAR PROBING
Datasets. To evaluate the transferability of the proposed method, we test the performance through linear probing on molecular property prediction, adhering to the settings described by You al. (2020). Initially, the NIDcL is pre-trained on 2 million unlabeled molecules soureed from ZINC15 (Hu* et al., 2020).
Node features:
Atom number: [18]
Chirality tag: (unspecified, tetrahedral ew, tetrahedral cow, other)
Edge features:
Bond type: (single, double, triple, aromatic]
Bond direction: {-, endupright, enddownright)
Then, focus molecular property prediction, where adopt the widely-used 7 binary classi- fication datasets contained in MoleculeNet (Wu et al., 2018) for linear probing. The scaffold-split (Ramsundar al., 2019) is used split downstream dataset graphs into arainin//vaidaaiio/eesstt set as 80%/10%/110 which mimics real-world use cases. For the evaluation protocol, we run experiments for 10 times and report the and standard deviation of ROC-AUC scores (%).
Model Hyperparameters. Following You et al. (2020), we adopt a 5-layer GIN (Xu et al., 2018) with 300 hidden dimension as the MPNN architecture, and set the RVQ codebook size K 16. We use mean pooling as the readout function. During the pre-training stage, GIN is pre-trained for 100 epochs with batch-size as 256 and the learning rate as 0.001. After the model trained on the pre-training dataset, it is directly applied to the downstream dataset to obtain node IDs. To evaluate the learned node IDs, we follow the linear probing (linear evaluation) (Akhondzadeh al., 2023), where a linear classifier (1 linear layer) is trained on the node IDs. During the probing stage, we train for 100 epochs with batch-size as 32, dropout rate as 0.5, and report the test performance using ROC-AUC at the best validation epoch.
The results are presented in Table 13. It is noteworthy that NIDcL outperforms the baselines in the SIDER, Clin and BBBP datasets, and shows significant improvement over the embeddings from GraphCL. This suggests the robust transferability of NIDeL.
Table 13: Linear probing: molecular property prediction; binary classification, ROC-AUC (%).
Tox21
ToxCast
Sider
ClinTox
HIV
BBBP
Bace
EdgePred
62.7 = 0.6
55.3 0.4
51.0 0.3
4.5
2.0
54.8 + 0.7
68.8 0.9
ContextPred
6..4
5.2
0.3
1.7
68.9
0.2
6..4
AutMaask
69.1 0.2
58.2
51.7
0.7
6.39
61.0 1.3
6.54
JOAO
70.6 0.4
6.3
0.6
2..1
6.91
0.3
71.2 1.0
SimGRACE
64.6
0.2
5.69
2.64
6.5
6.2
67.8 1.3
GraphCT.
64.4 0.5
0.2
0..6
59.8
63.7
71.1 +.7 0.7
NIDeI.
66.3 0.4
59.1 0.3
60.1
2.2
64.3
66.9 + 0.6
66. + 1.2
D.3 ADDITIONAL COMPARISON RESULTS WITH VQGRAPH
Efficiency. Our NID employs RVQ at every layer of the MPNN, achieving a representational capacity of O(K M²) with only O(K x M L) in codebook size, which far surpasses VQGraph's 's capacity that is limited to its single codebook size. As depicted in Table 14, NID is considerably more efficient than VQGraph.
We specifically compare the node classification results with VQGraph tokens under the same experimental settings. VQGraph tokens refers to training MLP with tokens learned by VQGraph tokenizer from Yang et al. (2024). As shown in Table 15, VQGraph tokens lack structural information, likely due to codebook collapse encountered by their tokenizer (see Table 8).
Quality.
26

---

Published as a conference paper at ICLR 2025
Table 14: Comparison of optimal total codebook sizes.
Cora
CiteSeer
PubMed
Computer
VQGraph
2048
4096
8192 16 x x = 96
16384
NIDGCN (K x M x I.)
6x3x4=77
x 48
8 x x 120
Table 15: Node classification results in supervised representation learning.
Cora Accuracyt
CiteSeer Accuracy?
PubMed Accuracyf
ogbn-arxiv Accuracyt
Metric
VQGraph tokens
63.39 1.15
32.07 2.70
54.37 + 4.76 89.42 0.44
43.57 = 0.49 71.27 = 0.24
NIDGCN
87.88 0.69
76.89 1.09
D.4 HIGH CODEBOOK USAGE IN NID
In response to the surprising high codebook usage of our NID compared VQGraph, believe this primarily due to our small codebook size K.
As detailed in Table 14, NID achieves high codebook utilization without experiencing codebook collapse. This efficiency is attributed to our smaller codebook size K, typically less than 32. In contrast, VQGraph uses significantly larger codebook size, ranging from 2048 32,768 (as reported in Table 12 of the VQGraph paper (Yang et al., 2024)). Their codebook size typically scales the graph size; for example, on the Citeseer dataset, which comprises 2,110 nodes, they used codebook size of 4,096.
We have observed that large codebook size often leads to severe codebook collapse. Our use of a small codebook size ensures high codebook usage and prevents codebook collapse. These observations are consistent with findings reported in FSQ (Mentzer et al., 2024).
D.5 RECONSTRUCTION TASK EXCLUSION IN LNID
In this section, address the exclusion of the reconstruction task in LNID. differentiating it from other methods such as VAE and VQGraph. A reconstruction task typically involves using code vectors regenerate the input data, aiming to minimize the difference between the original input and its reconstruction.
Our decision omit reconstruction loss component was based ablation study comparing our approach with VQGraph. By replicating VQGraph's 's experimental setup, minus the reconstruction loss, we found that omitting this component had negligible impact on performance, as shown in Table 16.
Moreover, suggested by Vignac al. (2022), generative models like VQ- VA-V which are primarily designed for continuous data, encounter challenges with graph data due to difficulties in preserving the sparsity and discrete structure inherent in graphs. Therefore, our approach simplifies the model by not involve using the code vectors for reconstruction task.
Table 16: Impact of excluding reconstruction loss on performance
Model
Cora
CiteSeer
PubMed
ogbn products
VQGraph
76.08 + 0.55 76. = 0.47
78.40 1.71
83,93 + 0.87
79.17 0.21
VQGraph without reconstruction loss
78.03 1.58
83.85 # 1.24
79.23 0.26
D.6 END-TO-END LEARNING WITH RVQ
RVQ can feasibly be applied post-hoc embeddings generated by GNN. However, this approach requires a two-phase training process: initially training the GNN and subsequently training the RVQ model. Each phase demands separate optimization of parameters, such learning rates and epochs.
27

---

Published as a conference paper at ICLR 2025
We conducted experiments evaluate both methods: end-to-end learning post-hoe RVQ application. The results, summarized in Table 17, illustrate that end-to-end learning not only streamlines the training process but also improves performance.
Table 17: Comparison of end-to-end and post-hoc RVQ learning performance
Method
Cora
Citeseer
PubMed
NIDGeN (End-to-End Learning)
87.88 + 0.69
76.89 # 1.09 75.47 1.31
89,42 + 0,44
NIDGCN (Post-hoc RVQ)
86.17 0.33
88.32 + 0.54
D.7 TRANSDUCTIVE vs. INDUCTIVE INFERENCE
it important to clarify that manuscript also incorporates inductive inference evaluations. Notably, the experiments documented in Table 3 & 4 involve inductive graph and edge inference.
For instance, in the Peptides-fune dataset detailed in Table were split into training, validation, and test sets. The key point here is that the graphs used during the inference stage were not exposed the model during training. Additionally, we followed the inductive settings described in the VQGraph paper (Yang et al., 2024) to perform node classification dataset. The results in Table 18 clearly demonstrate that our NID
classified 15,535 graphs that
experiments on the method achieves superior performance in both inductive and transductive settings.
Table 18: Comparison of inductive and transductive inference performance on ogbn-products
Model
oghn-products (Inductive)
(Transductive)
VQGraph
77.50 0.25
79.17 17.1 = 0.21
NIDSAGE
79.13 0.32
81.83 + 0.26
E ADDITIONAL DISCUSSION
E. RVQ IMPLEMENTATION DETAILS
In our model, each MPNN layer involves the use of M codewords per node, which implies that RVQ conducted over M iterations.
is crucial to note that for each MPNN layer, an independent set of M codebooks is utilized. Specifically, we quantize the node embedding h' by sequentially selecting the closest code vector from each codebook:
The first code vector ec,, (cn1 the codeword) is chosen based on the initial node embedding
Fn = h/
Subsequent code vectors, such Gagy selected based on the residual vector 7/2
h. Tı. and so forth.
For each codebook approximation, we optimize two types of losses: the codebook loss and the
commitment loss, detailed in Equation Taking the NID as an example, during training, aggregate all losses from each codebook across all layers (L x M) into an additional loss component. This component then jointly optimized with the MAE loss, as described in Equation within single backpropagation step.
E.2 PRETRAINING RUNTIME
One pertinent aspect of our paper involves analyzing the computational complexity associated with the multi-level optimization of codebooks. To elucidate this. compared the training time per epoch of our NID with SAGE on oron-prosucts, ogbn-pprotinn and pokec (see Table 19). The results revealing: the NID model records training time of 5.9 seconds per epoch, closely mirroring
28

---

Published as a conference paper at ICLR 2025
that of SAGE, which is 5.8 seconds per epoch. This comparison substantiates that the additional quantization module integrated into our NID model imposes minimal computational overhead.
These findings underscore the efficiency of NID model, demonstrating its capability to maintain comparable training times to traditional GNNs despite the added complexity the multi-level codebook optimization.
Table 19: Empirical training runtime per epoch on ogbn-proteins, ogbn-products, and pokec.
Dataset
Nodes 132,534
# Edges
Training Time per Epoch
ogbn-proteins
39,561,252
SAGE: 0.45s, NIDSAGE' 0.51s
ogbn-products
2,449.029 1,632.803
61,859,140
SAGE: 5.8s, NIDSAGE: 5.9s
pokec
30,622,564
SAGE: 2.7s, NIDSAGE: 3.1s
E.3 EXAMPLES NODE IDs WITH THE SAME SECOND ID CODE
G
1-HOP
2-HOP
1-HOP
2-HOP
Node ID:
Node ID:
H
1-HOP
2-HOP
1-HOP
2-HOP
Node ID:
Node ID:
Figure 9: real examples of node IDs with the same second code from Figure in the PubMed dataset. Nodes and H have different first ID codes hecause, despite sharing similar 1-hop topology, they differ in the label distribution of their 1-hop neighbors. However, they exhibit similar 2-hop topology and similar label distributions among their 2-hop neighbors, which results in the second ID code. Additionally, nodes I and have different first codes due differences in both their 1-hop topologies their l-hop neighbors. Nevertheless, their 2-hop neighbors share similar label distributions, leading to the same second ID code, even though their 2-hop topologics are not as similar as those of nodes G and H.
the label distributions among
F LIMITATIONS & BROADER IMPACTS
Broader Impacts. This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Limitations. Our node IDs have proven to be effective in large-scale graphs by accelerating clustering and inference processes due their low-dimensional nature. However, have found that the number
29

---

Published as a conference paper at ICLR 2025
of available datasets for very large networks is limited, and acknowledge that there is still room for extension. Additionally, we believe that node IDs could benefit large language models, a topic we intend to explore more extensively in our future work.
G FURTHER RELATED WORKS
Vector Quantization (VQ). VQ compresses the representation space into compact codebook of multiple codewords, using single code to approximate each vector (Liu et al., 2024b). Advanced methods like VQ-VAE (Van Den Oord al., 2017) and RQ-VAE (Lee al., 2022) enhance quanti- zation precision by employing multiple codebooks, initially for image generation and later adapted recommender systems (Rajput et al., 2024; Liu et al., 2024c) and multimodal representation learning (Zheng et al., 2024; Xia et al., 2024). This paper introduces residual quantization for learning structure-awang node IDs, achieving superior feature compression performance.
Transformer models with attention mechanisms can process graphs by tokenizing nodes and edges, incorporating positional or structural graph information through PEs (Müller et al., 2023). The Graph Transformer (Dwivedi & Bresson, 2020) and SAN (Kreuzer et al., 2021) initially employed Laplacian eigenvectors as PEs. Subsequent models like LSPE (Dwivedi et al., 2021) utilized random walk probabilities node tokens. TokenGT (Kim et al., 2022) introduced orthogonal vectors for both node and edge tokens, and follow-up works also consider larger graphs (Luo al., 2024c). However, these methods primarily encode the structural information the graph and overlook the features of nodes, thereby constraining their direct application.
Positional Encodings (PEs) as Graph Tokens.
30


Reviews:
[{"review_id": "9TOtuyAyvP", "reviewer": "Reviewer_k2Gp", "summary": "This paper proposes a vector quantization for GNN representations created from different \"depths\" of the network at each node.  Its similar to other recently proposed works (I'm most reminded of VQGraph), but its not trained with a reconstruction loss.  Extensive experimentation is provided, but it seems like most baselines are just copied from tables in recent work.  In general the quantization seems to work effectively, performing at about the same level as the original GNN.\n\nNote: Interestingly when a baseline is recomputed by the authors (e.g. GCN) it seems to differ from the result reported in the paper the majority of the results come from (Polynormer).  This raises a substantial red flag, as the author's method should only perform as well as the baseline it quantitizes.  If we instead assume the author's methods perform within epsilon of the corresponding baseline in Polynormer, they would not be superior methods.", "questions": "Nice paper.  However when I dove into the experimental results of the Polynormer paper it raised a lot of questions.\n\n1. The core issue is that in this paper you show weak methods (e.g. GCN) performing well on datasets.  \nLets take Photos for example.  In Polynormer, GCN is the weakest method (92%).  In your paper, GCN is the strongest method (96%).  This could be because you did a better grid search (good!) but if you don't similarly do a great grid search for the other baselines then I don't trust them at all :)\n\nIt makes it very hard understand how your method compares at all to the baselines.  (As a VQ paper the goal is not to really \"beat\" anything -- just do more with less)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ very well written paper about a pressing topic (graph quantization)\n+ extensive results help provide details about the method\n+ I'm confident the method seems to work well (but perhaps doesn't actually win on baselines, see weaknesses)", "weaknesses": "- Egregious experimental result reuse raises a number of inconsistencies for the few methods the authors have recomputed.\n- Its difficult to place the results in context with the related work (ie the Polynormer paper results).", "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": "xd6JksBR43", "reviewer": "Reviewer_w4zV", "summary": "This paper introduces a new framework that creates compact and interpretable node representations, called node IDs, using vector quantization to convert GNN embeddings into discrete codes. Experiments across 34 datasets show that these node IDs improve speed and memory efficiency while maintaining competitive performance in various graph tasks.", "questions": "How does the joint training of the GNN and vector quantization components affect the overall computational efficiency, especially when scaling to larger datasets?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a new framework for generating highly compact, discrete node representations (node IDs) that effectively addresses the inference challenges encountered in large-scale graph applications.\n2. The authors conduct comprehensive experiments across 34 diverse datasets and tasks, demonstrating the effectiveness of their method. \n3. The paper is well-structured and easy to read.", "weaknesses": "1. The quantization of node embeddings into discrete node IDs may result in the loss of important structural information, as nuanced variations in node characteristics could be oversimplified into a single codeword. \n2. The framework necessitates joint training of the GNN and vector quantization components, which raises concerns about increased time complexity. The authors should provide an analysis of this complexity, particularly focusing on the impact of joint training on computational efficiency and scalability with larger datasets.", "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": "y9aJyg5nvj", "reviewer": "Reviewer_aCEA", "summary": "The paper proposes an end-to-end framework NID, which represents nodes with highly compact, discrete vectors, to deal with the inference challenges on large-scale graphs. Specifically, vector quantization is adopted to resident embeddings in each layer of the GNN, and NID can be optimized in either self-supervised or supervised learning ways. Extensive experiments show the effectiveness of the proposed framework.", "questions": "1.\tWhat does it mean by “share similar 1-hop structures” in line 71 in the description of Figure 1? Why node in case A&B, C&D have similar 1-hop structure? What is the definition of so-called similar 1-hop structures? It is vague.\n2.\tLet’s extend the first question, so if two nodes have exactly the same second ID code in the figure 1 (but the first ID code is different), does that mean they have “similar 2-hop structures”? If yes, how can they have similar 2-hop structures on the basis of totally different 1-hop neighbors? Which neighbors of the 1-hop neighbors should be considered? If no, what does the same second ID code mean in that case?\n3.\tThe definition of the M is vague. What does M mean in the size of codebook L*M?\n4.\tIn subsection 3.2, the paper says that the Node_ID of each node will be sent into the MLP network, but my question is are you sending the id like “2341” (eg. 4-layer encoder) as the node representation into the MLP network? Why don’t you send the corresponding codeword into the MLP network? I know that code vectors are not used for a reconstruction task, so I am here talking about the downstream tasks.\n5.\tWhat will happen if two different nodes have the exactly same Node_ID? Since the size of each codebook is certain, let’s take figure 1 (2-dimensional) as an example, the codebook size of each layer is 5, then you actually can have 25 (5^2) different discrete representations. So there must be some nodes sharing the same Node_ID (collision). \n6.\tFor the argument in box 4.1, as I say, why directly use IDs as representations instead of corresponding vectors in the codebook?\n7.\tWhat is the interpretation of your discrete representations?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper is well-written and solid, especially practical in the case of large-scale graphs.\n2.\tThe overview of the proposed framework helps readers to understand the main pipeline of the work.\n3.\tThe experiment part is sufficient to clarify the effectiveness and efficiency of NID.", "weaknesses": "1.\tThe interpretability of the discrete representations of NID is not discussed in detail in the paper. As the authors point out that the most existed real-valued embeddings often lack interpretability, there should be a detailed discussion.\n2.\tSome concepts in the paper are vague. Refer to questions for more details. \n3.\tThe introduction of codebook seems useless since the codeword is used in neither loss of VQ nor loss of tasks.", "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)