Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning

## Abstract

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 will be made available at https://github.com/LUOyk1999/NodeID .

## 1 Introduction

Machine learning on graphs involves leveraging graph topology and node/edge attributes to perform various tasks, including node and graph classification (Kipf & Welling, ), link prediction (Lü & Zhou, ; Zhang & Chen, ), community detection (Fortunato, ; Fortunato & Hric, ), and recommendation (Konstas et al., ; Fan et al., ). Various methods have been developed to address these challenges, including random walk based-models (Perozzi et al., ; Grover & Leskovec, ; Wu et al., ), spectral methods (Bruna et al., ; Defferrard et al., ), and graph neural networks (GNNs) (Hamilton et al., ; Kipf & Welling, ; Veličković et al., ; Xu et al., ; Morris et al., ; Li et al., ; Chen et al., ).
GNNs employ a message-passing mechanism (Gilmer et al., ) to iteratively aggregate information from a node’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 to large-scale scenarios requiring low latency and fast inference remains challenging (Zhang et al., ; Jia et al., ; Yang et al., ). The inherent bottleneck is the message-passing mechanism, which necessitates loading the entire graph—potentially comprising billions of edges—during inference for target nodes, which is computationally demanding and time-consuming. To address this challenge, recent studies (Zhang et al., ; Tian et al., ; Yang et al., ) have explored knowledge distillation techniques to distill a small MLP model that captures essential information from a pre-trained GNN, making it suitable for latency-critical applications (Tian et al., ). However, these GNN-to-MLP methods require supervised training using class labels and lack the ability to generate effective node representations.

Figure: Figure 1: Illustration of 2-dimensional node IDs generated by our NID framework using a two-layer GCN, with the first ID code derived from the node embedding in the first layer, and the second ID code derived from the node embeddings in the second layer. *Center:* t-SNE visualization of node embeddings in the PubMed Dataset, with colors representing different class labels. *Left:* Display of six nodes, each with their ID and 1-hop substructure. Nodes with the same first ID code share similar 1-hop structures, though this does not necessarily indicate the same class label. *Right:* Nodes E and F are further analyzed with their 2-hop substructures. Variations in these structures are reflected by their distinct second ID code (blue) and class label.
Refer to caption: x1.png

An alternative approach to facilitate inference on large-scale graphs involves learning effective, low-dimensional node embeddings that can be directly utilized for downstream prediction tasks. This method has been extensively explored in early works on network/graph embedding, such as DeepWalk (Perozzi et al., ) and node2vec (Grover & Leskovec, ), as well as in recent efforts leveraging GNNs to learn embeddings for graph tokens (Liu et al., ; ; Xia et al., ; Luo et al., ), 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 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 a novel end-to-end framework called NID, which employs vector quantization (Gray, ) to compress the continuous node embeddings generated at each layer of a GNN into discrete codes, where the GNN and codebooks are trained jointly. This approach effectively captures the multi-order neighborhood structures within the graph. Fig. 1 illustrates examples of two-dimensional node IDs generated by a 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—including node and graph classification, link prediction, and attributed graph clustering—shows that these node IDs achieve performance competitive with state-of-the-art methods while significantly enhancing speed and memory efficiency. We also offer a theoretical justification for our approach.
- •
Our proposed NID framework can be integrated with state-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 in some cases, leading to significantly improved performance. This warrants deeper investigation.
- •
Our findings indicate significant redundancy in GNN embeddings. The generated compact, discrete node IDs provide a 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 a tuple $\mathcal{G}=(\mathcal{V},\mathcal{E},\bm{X})$, where $\mathcal{V}$ is the set of nodes, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges, and $\bm{X}\in\mathbb{R}^{|\mathcal{V}|\times d}$ is the node feature matrix, with $|\mathcal{V}|$ representing the number of nodes and $d$ the dimension of the node features. Let $\bm{A}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$ denote the adjacency matrix of $\mathcal{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, ). Gilmer et al. () reformulated early GNNs into a framework of message passing GNNs, which computes representations $\bm{h}_{v}^{l}$ for any node $v$ in each layer $l$ as:

$$ $\bm{h}_{v}^{l}=\text{UPDATE}^{l}\left(\bm{h}_{v}^{l-1},\text{AGG}^{l}\left( \left\{\bm{h}_{u}^{l-1}\mid u\in\mathcal{N}\left(v\right)\right\}\right)\right),$ (1) $$

where ${\mathcal{N}}(v)$ denotes the neighborhood of $v$, $\text{AGG}^{l}$ is the message function, and $\text{UPDATE}^{l}$ is the update function.
The initial node representation $\bm{h}_{v}^{0}$ is the node feature vector $\bm{x}_{v}\in\mathbb{R}^{d}$.
The message function aggregates information from the neighbors of $v$ to update its representation. The output of the last layer, i.e., $\text{MPNN}(v,\bm{A},\bm{X})=\bm{h}_{v}^{L}$, is the representation of $v$ produced by the MPNN.

Prediction tasks on graphs involve node-level, edge-level, and graph-level tasks. Each type of tasks requires a tailored graph readout function, $\mathrm{R}$, which aggregates the output node representations, $\bm{h}_{v}^{L}$, from the last layer $L$, to compute the final prediction result:

$$ $\bm{h}_{\text{readout}}=\mathrm{R}\left(\left\{\bm{h}_{v}^{L},v\in\mathcal{V} \right\}\right).$ (2) $$

Specifically, for *node-level* tasks, which involve classifying individual nodes, $\mathrm{R}$ is simply an identity mapping. For *edge-level* tasks, which focus on analyzing the relationship between any node pair $(u,v)$, $\mathrm{R}$ is typically modeled as the Hadamard product of the node representations (Kipf & Welling, ), i.e., $\bm{h}_{\text{readout}}=\bm{h}_{v}^{L}\odot\bm{h}_{u}^{L}$. For *graph-level* tasks that aim to make predictions about the entire graph, $\mathrm{R}$ often functions as a global mean pooling operation, expressed as $\bm{h}_{\text{readout}}=\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}}\bm{h}_{v
}^{L}$.

Vector Quantization (VQ) (Gray, ) aims to represent a large set of vectors, $\bm{Z}=\{\bm{z}_{i}\}_{i=1}^{N}$, with a small set of prototype (code) vectors of a codebook $\bm{C}=\{\bm{e}_{k}\}_{k=1}^{K}$, where $N\gg K$. The codebook is often created using algorithms such as $k$-means clustering via optimizing the following objective:

$$ $\textbf{VQ:}~{}~{}~{}\min_{\bm{C}}\sum_{i=1}^{N}\min_{k=1}^{K}\left|\left|\bm{ z}_{i}-\bm{e}_{k}\right|\right|_{2}^{2}.$ (3) $$

Once the codebook is learned, each vector $\bm{z}_{i}$ can be approximated by its closet prototype vector $\bm{e}_{t}$, where $t=\arg\min_{k}\left|\left|\bm{z}_{i}-\bm{e}_{k}\right|\right|_{2}^{2}$ is the index of the prototype vector. Residual Vector Quantization (RVQ) (Juang & Gray, ; Martinez et al., ) is an extension of the basic VQ. After performing an initial VQ, the *residual vector* is calculated:

$$ $\bm{r}_{i}=\bm{z}_{i}-\bm{e}_{t},$ (4) $$

which represents the quantization error from the initial quantization. Then, the residual vectors $\bm{r}_{i}$ are quantized using a second codebook. This process can be repeated multiple times, with each stage quantizing the residual error from the previous stage.

## 3 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. At each layer, the node embedding is quantized into a tuple of structural codewords. The tuples are then combined to form what we refer to as the node ID.

2. *Utilizing the generated node IDs as node representations 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. 2 illustrates the diverse clustering patterns of node representations produced by an MPNN at different layers $l$. This diversity arises from the cumulative smoothing effect caused by successive applications of graph convolution at each layer (Li et al., ; ). To generate structure-aware node IDs, we employ an $L$-layer MPNN to capture multi-order neighborhood structures. At each layer, we use vector quantization to encode the node embeddings produced by the MPNN into $M$ codewords (integer indices). For each node $v$, we define the node ID of $v$ as a tuple composed of $L\times M$ codewords, structured as follows:

$$ $\text{Node_ID}(v)=\left(c_{11},\cdots,c_{1M},c_{21},\cdots,c_{2M},\cdots,c_{L 1},\cdots,c_{LM}\right),$ (5) $$

where $c_{lm}$ represents the $m$-th codeword at the $l$-th layer. Both $M$ and $L$ can be very small. For the node IDs in Fig. 1, $M=1$ and $L=2$. In our experiments, we typically set $M=3$ and $L\in[2,5]$.

Figure: Figure 2: t-SNE visualization of the node representations of the Cora dataset generated by an MPNN at different layers $l$.
Refer to caption: extracted/5936721/ana_tsne_cora_0.png

Figure: Figure 3: Overview of our proposed NID framework.
Refer to caption: x2.png

Learning Node IDs. As illustrated in Fig. 3, at each layer $l$ ($1\leq l\leq L)$ of the MPNN, we employ RVQ (see Sec. 2) to quantize the node embeddings and produce $M$ tiers of codewords for each node $v$. Each codeword $c_{lm}$ ($1\leq m\leq M$) is generated by a *distinct* codebook $\bm{C}_{lm}=\{\bm{e}_{k}^{lm}\}_{k=1}^{K}$, where $K$ is the size of the codebook. Hence, there are a total of $L\times M$ codebooks, indexed by $lm$. Let $\bm{r}_{lm}$ denote the vector to be quantized. Note that $\bm{r}_{l1}$ is the node embedding $\bm{h}_{v}^{l}$ produced by the MPNN. When $m>1$, $\bm{r}_{lm}$ represents the residual vector.
Then, $\bm{r}_{lm}$ is approximated by its nearest code vector from the corresponding codebook $\bm{C}_{lm}$:

$$ $c_{lm}=\arg\min_{k}||\bm{r}_{lm}-\bm{e}_{k}^{lm}||,$ (6) $$

producing the codeword $c_{lm}$, which is the index of the nearest code vector.

We introduce a simple, generic framework for learning node IDs (codewords $c_{lm}$) by jointly training the MPNN and the codebooks with the following loss function:

$$ $\mathcal{L}_{\text{NID}}=\mathcal{L}_{\mathcal{G}}+\mathcal{L}_{\text{VQ}},$ (7) $$

where $\mathcal{L}_{\mathcal{G}}$ is a (self)-supervised graph learning objective, and $\mathcal{L}_{\text{VQ}}$ is a vector quantization loss. $\mathcal{L}_{\mathcal{G}}$ aims to train the MPNN to produce effective node embeddings, while $\mathcal{L}_{\text{VQ}}$ ensures the codebook vectors align well with the node embeddings. For a single node $v$, $\mathcal{L}_{\text{VQ}}$ is defined as

$$ $\mathcal{L}_{\text{VQ}}=\sum_{l=1}^{L}\sum_{m=1}^{M}\|\text{sg}(\bm{r}_{lm})- \bm{e}_{c_{lm}}^{lm}\|+\beta\|\bm{r}_{lm}-\text{sg}(\bm{e}_{c_{lm}}^{lm})\|,$ (8) $$

where sg denotes the stop gradient operation, and $\beta$ is a weight parameter. The first term in Eq. (8) is the *codebook loss* (Van Den Oord et al., ), which only affects the codebook and brings the selected code vector close to the node embedding. The second term is the *commitment loss* (Van Den Oord et al., ), which only influences the node embedding and ensures the proximity of the node embedding to the selected code vector.
In practice, we can use exponential moving averages (Razavi et al., ) as a substitute for the *codebook loss*.

Self-supervised Learning. The graph learning objective $\mathcal{L}_{\mathcal{G}}$ can be a self-supervised learning task, such as graph reconstruction (i.e., reconstructing the node features or graph structures) or contrastive learning (Liu et al., ).
In this paper, we examine two representative models: GraphMAE (Hou et al., ) and GraphCL (You et al., ). We discuss GraphMAE here and address GraphCL in the App. A due to space limitations. Specifically, GraphMAE involves sampling a subset of nodes $\tilde{\mathcal{V}}\subset\mathcal{V}$, masking the node features as $\tilde{\bm{X}}$, encoding the masked node features using an MPNN, and subsequently reconstructing the masked features with a decoder. The reconstruction loss is based on the scaled cosine error, expressed as:

$$ $\mathcal{L}_{\mathcal{G}}=\mathcal{L}_{\text{MAE}}=\frac{1}{|\tilde{\mathcal{V }}|}\sum_{v\in\tilde{\mathcal{V}}}\left(1-\frac{\bm{x}_{v}^{T}\bm{z}_{v}}{\| \bm{x}_{v}\|\cdot\|\bm{z}_{v}\|}\cdot\gamma\right),$ $$

where $\tilde{\mathcal{V}}$ is the set of masked nodes, $\bm{z}_{v}=f_{D}(\tilde{\bm{h}}_{v}^{L})$ is the reconstructed node features by a decoder $f_{D}$, $\tilde{\bm{h}}_{v}^{L}=\text{MPNN}(v,\bm{A},\tilde{\bm{X}})$, and $\gamma\geq 1$ is a scaling factor. Let $\tilde{\bm{r}}_{l1}:=\tilde{\bm{h}}_{v}^{l}$ denote the node embedding generated by the $l$-th layer of the MPNN with the masked features. The overall training loss is

$$ $\mathcal{L}_{\text{NID}}=\mathcal{L}_{\text{MAE}}+\sum_{v\in\tilde{\mathcal{V} }}\sum_{l=1}^{L}\sum_{m=1}^{M}\|\text{sg}(\tilde{\bm{r}}_{lm})-\bm{e}_{c_{lm}} \|+\beta\|\tilde{\bm{r}}_{lm}-\text{sg}(\bm{e}_{c_{lm}})\|.$ (9) $$

Supervised Learning.
The graph learning objective $\mathcal{L}_{\mathcal{G}}$ can also be a supervised learning task, such as node classification, link prediction, or graph classification. For classification tasks, $\mathcal{L}_{\mathcal{G}}$ can be the cross-entropy loss between the target label $y$ and the prediction $\bm{h}_{\text{readout}}$ (see Eq. (2)):

$$ $\mathcal{L}_{\mathcal{G}}=\mathcal{L}_{\text{CE}}(y,\bm{h}_{\text{readout}}).$ (10) $$

Remark. Our NID framework differs from VQ-VAE (Van Den Oord et al., ) and similar approaches (Lee et al., ; Yang et al., ) in codebook learning. Unlike these methods, our training objective $\mathcal{L}_{\text{NID}}$ does not involve using the code vectors ($\bm{e}_{k}$) for a reconstruction task. Instead, we guide the codebook learning process solely via graph learning tasks ($\mathcal{L}_{\mathcal{G}}$). This is because our 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, ), GAT (Veličković et al., ), SAGE (Hamilton et al., ) and GIN (Xu et al., ).

### 3.2 Applications of 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 $v$ in the graph is associated with a label $y_{v}$, representing its category. We can directly utilize the node IDs of the labeled nodes to train an MLP network for classification. The prediction is formulated as

$$ $\hat{y}_{v}=\text{MLP}(\text{Node_ID}(v)).$ (11) $$

For node clustering, one can directly apply vector-based clustering algorithms such as $k$-means (MacQueen et al., ) 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

$$ $\hat{y}_{(u,v)}=\text{MLP}(\text{Node_ID}(u)\odot\text{Node_ID}(v)),$ (12) $$

where $\odot$ is the Hadamard product.

Graph-level tasks include *graph classification* and *graph regression*. These tasks involve predicting a categorical label or numerical value for the entire graph $\mathcal{G}$. The prediction can be formulated as

$$ $\hat{y}_{\mathcal{G}}=\text{MLP}(\frac{1}{|\mathcal{V}|}\sum_{v\in\mathcal{V}} \text{Node_ID}(v)),$ (13) $$

where a global mean pooling function is applied on all the node IDs to generate a representation for the graph $\mathcal{G}$, which is then input into an MLP for prediction.
Note that the selection of the readout function, such as mean pooling, is considered a hyper-parameter.

Remark. Due to the high compactness of the node IDs, which usually consists of multiple codewords (int4 type in 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 a high-level abstraction of structural and feature information in a 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 a simplified model. We prove the optimized codebook by VQ can distinguish nodes based on a widely used data formulation, which leads to a desired classification performance by training a linear layer.

Theoretical formulation. Consider a node-level $P$-classification problem on a graph $\mathcal{G}=\{\mathcal{V},\mathcal{E},\bm{X}\}$ with $\bm{A}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}$ as the adjacency matrix and $\bm{Y}$ as the labels. We use a one-layer GCN to generate the node embedding $\bm{h}_{v}$ for $v\in\mathcal{V}$, i.e., $\bm{h}_{v}=\sigma(\frac{1}{|\mathcal{N}(u)|}\sum_{u\in\mathcal{N}(u)}\bm{W}\bm
{x}_{u})$, where $\bm{W}\in\mathbb{R}^{d^{\prime}\times d}$ and we assume $\sigma(\cdot)$ as an identity function. Given the obtained natural number $\text{Node_ID}(v)\in\mathbb{N}^{r}$ for node $v\in\mathcal{V}$, $r<K$, we map each entry to a $d_{e}$-dimensional embedding, where different digits correspond to orthogonal embeddings. Hence, $\text{Node_ID}(v)$ is projected to a $rd_{e}$-dimensional vector, denoted by $\bm{z}_{v}$. We use nodes from $\mathcal{V}_{R}$ to train a linear head $\bm{V}\in\mathbb{R}^{rd_{e}\times P}$, i.e., $\min_{\bm{V}}\frac{1}{|\mathcal{V}_{R}|}\sum_{v\in\mathcal{V}_{R}}\ell(\bm{z}_
{v},y_{v};\bm{V})$, where $\ell(\bm{z}_{v},y_{v};\bm{V})=-\bm{y}_{i}^{\top}\log(\hat{\bm{p}}_{v}):=-\bm{y
}_{i}^{\top}\log(\text{softmax}(\bm{z}_{v}^{\top}\bm{V}))$. Here $\bm{y}_{i}$ is the one-hot vector of $y_{i}\in\mathbb{N}$, where only the $y_{i}+1$-th entry is $1$ and others are 0 0. The classification error is defined by $\mathbbm{1}[y_{v}\neq\arg\max_{i\in[P]}\hat{\bm{p}}_{v,i}]$ for $v\in\mathcal{V}$, where $\hat{\bm{p}}_{v,i}$ is the $i$-th entry of $\hat{\bm{p}}_{v}$.

We define a set of orthonormal vectors $\{\bm{\mu}_{i}\}_{i=1}^{Q}$. For a $P$-classification problem ($P<Q$), denote $\{\bm{\mu}_{i}\}_{i=1}^{P}$ as the set of discriminative patterns that directly determine the label, while $\{\bm{\mu}_{i}\}_{i=P+1}^{Q}$ as the set of non-discriminative patterns that are irrelevant to the label. Specifically, we assume that for any node $v\in\mathcal{V}$ with label $p\in[P]$, $\bm{x}_{v}=\bm{\mu}_{p}$ or at least one of its neighbor equals $\bm{\mu}_{p}$, and no neighbor of $\bm{x}_{v}$ or itself equals $\bm{\mu}_{j}$ for $j\in[P],j\neq p$. This formulation extends from binary node classification in (Zhang et al., ; Li et al., ), which is verified on real-world datasets. We also assume rows of the optimized $\bm{W}$ by (7) are in directions of $\bm{\mu}_{i},i\in[P]$ uniformly by theoretical findings in (Zhang et al., ; Li et al., ). Then, we have the following theorem.

###### Theorem 1 .

The optimizer $\bm{C}^{*}$ of VQ objective (7) satisfies that, for any $\bm{x}_{u}$ and $\bm{x}_{v}$, $u,v\in\mathcal{V}$ with different labels, $\text{Node_ID}(u)\neq\text{Node_ID}(v)$. Then, as long as $\mathcal{V}_{R}$ uniformly include node IDs from all the classes, by training the linear head $\bm{V}$ with sufficient gradient descent steps, we can achieve that the classification error $\mathbbm{1}[y_{v}\neq\arg\max_{i\in[P]}\hat{\bm{p}}_{v,i}]=0$ for any $v\in\mathcal{V}$.

Remark. Theorem 1 illustrates that the optimized $\bm{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, a linear head can be learned to achieve a zero classification error. The proof can be found in App. B.

###### Theorem 1 .

## 4 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 classification.
Here, we evaluate our NID against several SOTA models for graph representation learning, following learning protocols (Luo et al., ; Rampášek et al., ; Wang et al., ).
- •
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., ; Hou et al., ; You et al., ).

RVQ Implementation Details. As outlined in Sec. 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. The codebook size $K$ is tuned in $\{4,6,8,16,32\}$. The $\beta$ is set to 1.

Detailed datasets, baselines, and hyperparameters are provided in App. C due to space constraints.

**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., ).**
| Transductive | Cora | CiteSeer | PubMed | Computer | Photo | CS | Physics | WikiCS | Squirrel | Chameleon | Ratings | Questions |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| # nodes | 2,708 | 3,327 | 19,717 | 13,752 | 7,650 | 18,333 | 34,493 | 11,701 | 2223 | 890 | 24,492 | 48,921 |
| # edges | 5,278 | 4,732 | 44,324 | 245,861 | 119,081 | 81,894 | 247,962 | 216,123 | 46,998 | 8,854 | 32,927 | 153,540 |
| Metric | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | ROC-AUC$\uparrow$ |
| GPRGNN | 87.95 ± 1.18 | 77.13 ± 1.67 | 87.54 ± 0.38 | 89.32 ± 0.29 | 94.49 ± 0.14 | 95.13 ± 0.09 | 96.85 ± 0.08 | 78.12 ± 0.23 | 38.95 ± 1.99 | 39.93 ± 3.30 | 44.88 ± 0.34 | 55.48 ± 0.91 |
| APPNP | 87.87 ± 0.82 | 76.53 ± 1.16 | 88.43 ± 0.15 | 90.18 ± 0.17 | 94.32 ± 0.14 | 94.49 ± 0.07 | 96.54 ± 0.07 | 78.87 ± 0.11 | 36.88 ± 1.27 | 41.62 ± 3.13 | 52.74 ± 0.73 | 77.82 ± 1.31 |
| SGFormer | 87.83 ± 0.92 | 77.24 ± 0.74 | 89.31 ± 0.54 | 92.42 ± 0.66 | 95.58 ± 0.36 | 95.71 ± 0.24 | 96.75 ± 0.26 | 80.05 ± 0.46 | 42.65 ± 2.41 | 45.21 ± 3.72 | 54.14 ± 0.62 | 73.81 ± 0.59 |
| Polynormer | 88.11 ± 1.08 | 76.77 ± 1.01 | 87.34 ± 0.43 | 93.18 ± 0.18 | 96.11 ± 0.23 | 95.51 ± 0.29 | 97.22 ± 0.06 | 79.53 ± 0.83 | 40.87 ± 1.96 | 41.82 ± 3.45 | 54.46 ± 0.40 | 78.92 ± 0.89 |
| Graph-MLP | 87.06 ± 1.38 | 76.43 ± 1.44 | 88.93 ± 0.63 | 90.78 ± 0.41 | 95.43 ± 0.76 | 94.68 ± 0.28 | 95.45 ± 0.24 | 75.35 ± 0.55 | - | - | - | - |
| VQGraph | 86.11 ± 1.26 | 75.64 ± 0.92 | 88.03 ± 0.63 | 90.28 ± 0.47 | 94.98 ± 0.59 | 93.82 ± 0.17 | 95.93 ± 0.28 | 77.92 ± 0.61 | - | - | - | - |
| GCN | 88.77 ± 0.61 | 77.53 ± 0.92 | 90.04 ± 0.25 | 93.78 ± 0.31 | 96.14 ± 0.21 | 95.94 ± 0.28 | 97.36 ± 0.07 | 80.91 ± 0.81 | 44.50 ± 1.92 | 46.11 ± 3.16 | 53.57 ± 0.32 | 77.40 ± 1.07 |
| $\textbf{NID}_{\text{GCN}}$ | 87.88 ± 0.69 | 76.89 ± 1.09 | 89.42 ± 0.44 | 93.41 ± 0.08 | 96.17 ± 0.04 | 95.52 ± 0.10 | 97.34 ± 0.04 | 78.55 ± 0.15 | 45.09 ± 1.72 | 46.29 ± 2.92 | 53.55 ± 0.13 | 96.85 ± 0.10 |
| GAT | 88.22 ± 1.24 | 77.08 ± 0.84 | 89.47 ± 0.25 | 93.53 ± 0.18 | 96.27 ± 0.15 | 94.46 ± 0.14 | 97.17 ± 0.09 | 80.98 ± 0.83 | 38.72 ± 1.46 | 43.44 ± 3.00 | 54.88 ± 0.74 | 78.35 ± 1.16 |
| $\textbf{NID}_{\text{GAT}}$ | 87.35 ± 0.57 | 76.13 ± 1.35 | 88.97 ± 0.36 | 93.38 ± 0.16 | 96.47 ± 0.27 | 94.75 ± 0.16 | 97.13 ± 0.08 | 79.56 ± 0.43 | 37.68 ± 2.04 | 42.83 ± 3.42 | 54.92 ± 0.42 | 97.03 ± 0.02 |

**Table 2: Node classification results in supervised representation learning on large-scale graphs (%).**
| Transductive | ogbn-proteins | ogbn-arxiv | ogbn-products | pokec |
| --- | --- | --- | --- | --- |
| # nodes | 132,534 | 169,343 | 2,449,029 | 1,632,803 |
| # edges | 39,561,252 | 1,166,243 | 61,859,140 | 30,622,564 |
| Metric | ROC-AUC$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ |
| GPRGNN | 75.68 ± 0.49 | 71.10 ± 0.12 | 79.76 ± 0.59 | 78.83 ± 0.05 |
| LINKX | 71.37 ± 0.58 | 66.18 ± 0.33 | 71.59 ± 0.71 | 82.04 ± 0.07 |
| GraphGPS | 76.83 ± 0.26 | 70.97 ± 0.41 | OOM | OOM |
| SGFormer | 79.53 ± 0.38 | 72.63 ± 0.13 | 74.16 ± 0.31 | 73.76 ± 0.24 |
| Polynormer | 75.97 ± 0.47 | 71.82 ± 0.23 | 82.97 ± 0.28 | 85.95 ± 0.07 |
| SAGE | 79.43 ± 0.75 | 72.67 ± 0.31 | 83.27 ± 0.35 | 85.97 ± 0.21 |
| Infer. Time | 158.1ms | 416.5ms | 11.9s | 129.6s |
| Storage Space | 129.4MB | 165.7MB | 1.9GB | 1.6GB |
| ${\textbf{NID}_{\text{SAGE}}}$ | 76.78 ± 0.59 | 70.52 ± 0.14 | 81.83 ± 0.26 | 85.63 ± 0.31 |
| Infer. Time | 0.4ms | 0.3ms | 0.7ms | 27.1ms |
| Storage Space | 0.4MB | 1.2MB | 17.5MB | 16.4MB |

### 4.1 Overall Performance

**Figure 4: Supervised node classification results of $\textbf{NID}_{\text{GCN}}$ with varying ratios of training samples.**
| Inductive | Cora | CiteSeer | PubMed | ogbl-collab |
| --- | --- | --- | --- | --- |
| # nodes | 2,708 | 3,327 | 19,717 | 235,868 |
| # edges | 5,278 | 4,552 | 44,324 | 1,285,465 |
| Metric | HR@100$\uparrow$ | HR@100$\uparrow$ | HR@100$\uparrow$ | HR@50$\uparrow$ |
| SEAL | 81.71 ± 1.30 | 83.89 ± 2.15 | 75.54 ± 1.32 | 64.74 ± 0.43 |
| NBFnet | 71.65 ± 2.27 | 74.07 ± 1.75 | 58.73 ± 1.99 | OOM |
| Neo-GNN | 80.42 ± 1.31 | 84.67 ± 2.16 | 73.93 ± 1.19 | 57.52 ± 0.37 |
| BUDDY | 88.00 ± 0.44 | 92.93 ± 0.27 | 74.10 ± 0.78 | 65.94 ± 0.58 |
| NCN | 89.05 ± 0.96 | 91.56 ± 1.43 | 79.05 ± 1.16 | 64.76 ± 0.87 |
| GCN | 85.73 ± 1.13 | 89.67 ± 0.81 | 80.36 ± 0.58 | 64.05 ± 0.63 |
| Inference Time | 44.2ms | 51.5ms | 102.7ms | 517.1ms |
| $\textbf{NID}_{\text{GCN}}$ | 90.33 ± 0.76 | 88.56 ± 0.72 | 75.67 ± 0.63 | 64.31 ± 0.48 |
| Inference Time | 10.9ms | 9.1ms | 22.1ms | 119.7ms |

#### 4.1.1 Supervised Node IDs for Supervised Representation Learning

Node Classification, Tables 1, 3, Figure 4. We have conducted extensive evaluations on 8 homophilic and 4 heterophilic graphs, testing scalability on 4 large-scale graphs, each with millions of nodes. Recently, Luo et al. () observed that classic GNNs can achieve highly competitive performance in node classification with proper hyperparameter tuning. Building on this, we implement our NID on GCN, GAT and SAGE, maintaining all experimental settings as described in Luo et al. (). 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 baselines across 4 heterophilic graphs. In a detailed analysis of Questions, we observe that $\textbf{NID}_{\text{GCN}}$ outperforms GCN by 20%. This dataset represents a 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 3, ${\textbf{NID}_{\text{SAGE}}}$ not only achieves near-SOTA performance on datasets with millions of nodes but also maintains fast inference times; notably, ${\textbf{NID}_{\text{SAGE}}}$ achieves a speed increase ranging from 400$\times$ to 17,000$\times$ 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., ): Peptides-func and Peptides-struct. We take all evaluation protocols suggested by Rampášek et al. (). 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.

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., ), following the data splits, evaluation metrics and baselines specified by the NCN (Wang et al., ). 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 5. Attributed graph clustering (Cai et al., ) focuses on clustering nodes in an attributed graph, where each node is associated with a set of feature attributes. DGCluster (Bhowmick et al., ), utilizes GNNs to 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., ). As demonstrated in Table 5, $\textbf{NID}_{\text{DGCluster}}$ outperforms all baseline models by a considerable margin on 5 datasets and achieves significantly faster runtime on 7 datasets due to the reduced dimensionality of our node IDs.

Node Classification, Table 7.
We evaluate the performance of our NID on three standard benchmarks: Cora, CiteSeer, and PubMed (Yang et al., ). For this purpose, we employ GraphMAE to provide graph learning objective during the training of node IDs. Specifically, we train a 2-layer GAT following the GraphMAE without supervision, resulting in the generation of 6-dim node IDs, denoted as $\textbf{NID}_{\text{MAE}}$. 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., ), including data splits and evaluation metrics, using all baselines reported by Hou et al. (). Table 7 lists the results. MLP refers to predictions made directly on the initial node features. Notably, $\textbf{NID}_{\text{MAE}}$ achieves competitive results in comparison to SOTA self-supervised approaches, and even surpasses all other approaches on CiteSeer. Remarkably, our node IDs are 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 a concise yet information-rich ID.

**Table 5: Attributed graph clustering results; normalized mutual information, and F1-score (%).**
|  | Cora | CiteSeer | PubMed | Computer | Photo | Physics | ogbn-arxiv |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | NMI$\uparrow$ | F1$\uparrow$ | NMI$\uparrow$ | F1$\uparrow$ | NMI$\uparrow$ | F1$\uparrow$ | NMI$\uparrow$ | F1$\uparrow$ | NMI$\uparrow$ | F1$\uparrow$ | NMI$\uparrow$ | F1$\uparrow$ | NMI$\uparrow$ | F1$\uparrow$ |
| 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 | - | - | - | - |
| SDCN | 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 | 8.3 | 13.6 | 4.3 | 18.0 | 4.4 | 11.6 | 42.5 | 37.3 | 47.6 | 45.0 | - | - | - | - |
| 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 |
| DiffPool | 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 |
| DMoN | 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 |  |  |  |  |  |  |  |
| $\textbf{NID}_{\text{DGCluster}}$ | 70.5 | 73.9 | 54.1 | 63.3 | 40.6 | 50.9 | 62.1 | 58.2 | 75.6 | 75.4 | 69.8 | 65.4 | 32.4 | 35.6 |
| Clustering Time | 78.3ms | 77.2ms | 292.5ms | 223.6ms | 140.6ms | 442.0ms | 1.8s |  |  |  |  |  |  |  |

**Table 6: Node classification results in unsupervised representation learning (%).**
|  | Cora | CiteSeer | PubMed |  |
| --- | --- | --- | --- | --- |
| Metric | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | dim |
| GAE | 71.5 ± 0.4 | 65.8 ± 0.4 | 72.1 ± 0.5 | 16 |
| DGI | 82.3 ± 0.6 | 71.8 ± 0.7 | 76.8 ± 0.6 | 512 |
| MVGRL | 83.5 ± 0.4 | 73.3 ± 0.5 | 80.1 ± 0.7 | 512 |
| InfoGCL | 83.5 ± 0.3 | 73.5 ± 0.4 | 79.1 ± 0.2 | 512 |
| CCA-SSG | 84.0 ± 0.4 | 73.1 ± 0.3 | 81.0 ± 0.4 | 512 |
| MLP | 57.8 ± 0.5 | 54.7 ± 0.4 | 73.3 ± 0.6 | 500 |
| GraphMAE | 84.2 ± 0.4 | 73.4 ± 0.4 | 81.1 ± 0.4 | 512 |
| $\textbf{NID}_{\text{MAE}}$ | 80.8 ± 0.7 | 74.2 ± 0.6 | 76.4 ± 0.8 | 6 |

Graph Classification, Tables 7 and 13. We evaluate our NID framework on 8 datasets from TUDataset (Morris et al., ): NCI1, PROTEINS, DD, MUTAG, COLLAB, REDDIT-B, REDDIT-M5K, and IMDB-B, utilizing two different methods, GraphCL (You et al., ) and AutoGCL (Yin et al., ), as graph learning objectives to guide node IDs pre-training. Specifically, using GraphCL as an example, we employ a GIN with the default settings from GraphCL as the GNN-based encoder, denoted as $\textbf{NID}_{\text{CL}}$. We adhere to the evaluation protocol outlined in GraphCL (You et al., ). The results are presented in Table 7, where NID outperforms all baselines on 3 out of 8 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 et al., ) are discussed in App. D, showing consistent findings.

### 4.2 Analysis of Node IDs

**Table 8: Comparison of codebook usage rates (%).**
| Usage rate$\uparrow$ | Cora | CiteSeer | PubMed |
| --- | --- | --- | --- |
| VQGraph | 1.3 | 0.8 | 18.1 |
| $\textbf{NID}_{\text{GCN}}$ | 84.7 | 97.9 | 79.1 |
| $\textbf{NID}_{\text{GCN}(M\text{=}1)}$ | 83.3 | 81.3 | 78.1 |

Figure: Figure 5: Codeword distributions of $c_{11}$ and $c_{21}$ in PubMed colored by the ground-truth labels.
Refer to caption: extracted/5936721/analysis_id_distribution_pubmed.png

High Codebook Usage, Table 4.2. We calculate the codebook usage rates for VQGraph tokenizer and NID. We find that VQGraph suffers from severe codebook collapse (Dhariwal et al., ), 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 $\textbf{NID}_{\text{GCN}}$ for the PubMed dataset, depicted in Figures 5 & 7. The number of RVQ levels $M$ is set to 3, and the MPNN layers $L$ is set to 2, with a codebook size $K$ of 16. For a given node ID $\left(c_{11},c_{12},c_{13},c_{21},c_{22},c_{23}\right)$ of a node, $0\leq c_{lm}\leq 15$. The codes $c_{11}$ and $c_{21}$ capture the high-level information of the first and second MPNN layers, respectively. We present the distribution of $c_{11}$ and $c_{21}$ according to different labels. For instance, $c_{11}$ = 10 generally corresponds to label "2". Similarly, the majority of nodes with $c_{21}$ = 13 are labeled "1". Our node IDs have overlapping codewords for similar labels, allowing the model to effectively share knowledge from similar nodes in the dataset.

Subgraph Retrieval, Table 4.2. We conduct node-centered subgraph retrieval using the supervised node IDs of $\textbf{NID}_{\text{GCN}}$ on Cora, CiteSeer and PubMed. We identify the five nodes closest to a query node based on Hamming distances between their node IDs, then compute the average graph edit distance (GED) between the 1-hop subgraph of the query node and the 1-hop subgraphs of these five nodes. The average GED across all nodes is detailed in Table 4.2. 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 4.2. We show the supervised node classification accuracy and model inference time on the Computer and ogbn-products datasets in Table 4.2. 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 a significant inference speedup of our approach in large networks.

Figure: Figure 6: Ablation studies of codebook size, RVQ level and MPNNs layer on $\textbf{NID}_{\text{GCN}}$.

Ablation Study of the Codebook Size $K$, RVQ Level $M$ and MPNNs Layer $L$, Figure 6. First, we examine the influence of the codebook size $K$. The optimal $K$ varies across different graphs; however, generally, $K\leq 16$ yields the best performance on most datasets. A larger codebook size may lead to codebook collapse, impairing performance. Second, regarding the RVQ level $M$, we find that $M=3$ 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 as ogbn-arxiv, may require more than 6 layers.

## 5 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., ). To address this issue, three main strategies are employed (Ma et al., ): knowledge distillation, model pruning, and model quantization. Knowledge distillation includes GNN-to-GNN methods (Yan et al., ; Yang et al., ) and GNN-to-MLP approaches (Hu et al., ; Yang et al., )). Model pruning methods include UGS (Chen et al., ) and Snowflake (Wang et al., )). Lastly, model quantization methods include VQ-GNN (Ding et al., ) and QLR (Wang et al., )).

Graph Tokenization. In graph representation learning, significant strides have been made to vectorize structured data for downstream machine learning applications (Chami et al., ). Early pioneering efforts, such as DeepWalk (Perozzi et al., ) and node2vec (Grover & Leskovec, ), 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 et al., ; Rong et al., ; Zhang et al., ), recommendation systems (Tang et al., ; Liu et al., ), and knowledge graphs (Tang et al., ; Lou et al., ). The emergence of Large Language Models (LLMs) has spurred recent explorations into graph tokenization. Works like InstructGLM (Ye et al., ), GraphText (Zhao et al., ), and GPT4Graph (Guo et al., ) use natural language descriptions of graphs as tokens inputted to LLMs. Additionally, GraphToken (Perozzi et al., ) 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 is fundamentally different from VQGraph (Yang et al., ), even though both approaches utilize VQ techniques to tokenize nodes as discrete codes. VQGraph uses VQ-VAE (Van Den Oord et al., ) to obtain soft code assignments, which serve as targets to aid the GNN-to-MLP 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, our NID framework is designed to learn compact discrect node representations in both supervised and unsupervised manners, enabling its use across a wide range of downstream tasks. Moreover, VQGraph employs a sizable codebook for tokenization, with a capacity comparable to the size of the input graph, leading to codebook collapse (Tab. 4.2). In contrast, our NID tokenizer utilizes multiple, small-sized codebooks to achieve a large representational capacity and effectively prevents codebook collapse.

## 6 Conclusions

We have both empirically and theoretically validated the feasibility of learning highly compact, discrete, and interpretable codes (node IDs) as effective node representations for efficient graph learning. Our proposed NID framework can be seamlessly integrated with state-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.

## Appendix A Self-supervised Node IDs using GraphCL

In this section, we discuss GraphCL (You et al., ) as a 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 as its own class, that is, a positive pair consists of two different views of it; and all other samples in a batch are used as the negative pairs during training.

Specifically, a 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 $\bm{z}_{n,i}$ and $\bm{z}_{n,j}$ for the $n$-th graph in the minibatch. Negative pairs are not explicitly sampled but are instead generated from the other $N-1$ augmented graphs within the same minibatch. The cosine similarity function is denoted as $\text{sim}(\bm{z}_{n,i},\bm{z}_{n,j})=\frac{\bm{z}_{n,i}^{T}\bm{z}_{n,j}}{\|
\bm{z}_{n,i}\|\|\bm{z}_{n,j}\|}$. The NT-Xent loss (Sohn, ) for the $n$-th graph is then defined as:

$$ $\mathcal{L}_{\text{GraphCL}}=-\log\frac{\exp(\text{sim}(\bm{z}_{n,i},\bm{z}_{n ,j})/\tau)}{\sum_{n^{\prime}=1,n^{\prime}\neq n}^{N}\exp(\text{sim}(\bm{z}_{n, i},\bm{z}_{n^{\prime},j})/\tau)},$ $$

$$ $\bm{z}_{n,i}=\mathrm{R}\left(\text{MPNN}(v_{n,i},\bm{A}_{n,i},\bm{X}_{n,i}) \right),$ $$

where $\tau$ represents the temperature parameter. The final loss is computed across all positive pairs in the minibatch. Consequently, Equation 7 is reformulated as:

$$ $\mathcal{L}_{\text{NID}}=\mathcal{L}_{\text{GraphCL}}+\sum_{n\in[1,N]}\sum_{v_ {n,i}\in\mathcal{V}_{n,i}}\mathcal{L}_{\text{VQ}}(v_{n,i})+\sum_{v_{n,j}\in \mathcal{V}_{n,j}}\mathcal{L}_{\text{VQ}}(v_{n,j}),$ (14) $$

## Appendix B Proof of Theorem 1

###### Proof.

For node $v\in\mathcal{V}$ with label $p\in\{0,1,\cdots,P-1\}$, by data formulation in Section 3.3, we have that there exists at least one node $u\in\mathcal{N}(v)$ that satisfies $\bm{x}_{u}=\bm{\mu}_{p}$. Given (7), let the first-round clustering center for $v$ be $\bm{c}_{v}=\bm{c}_{v}^{\parallel}+\bm{c}_{v}^{\perp}$, where $\bm{c}_{v}^{\parallel}$ is in the direction of $\bm{W}\bm{\mu}_{p}$ and $\bm{c}_{v}^{\perp}\perp\bm{W}\bm{\mu}_{p}$. By the assumption on $\bm{W}$, we know that $\bm{W}\bm{\mu}_{i}\perp\bm{W}\bm{\mu}_{j}$ if $i\neq j$, $i,j\in[P]$, and $\bm{W}\bm{\mu}_{i}=0$ for $i>P$. Therefore,

$$ $\displaystyle\|\frac{1}{|\mathcal{N}(v)|}\sum_{u\in\mathcal{N}_{v}}\bm{W}\bm{x }_{u}-\bm{c}_{v}\|^{2}$ (15) $\displaystyle=$ $\displaystyle\|\frac{1}{|\mathcal{N}(v)|}\sum_{u\in\mathcal{N}_{v},\bm{x}_{u}= \bm{\mu}_{p}}\bm{W}\bm{x}_{u}-\bm{c}_{v}^{\parallel}\|^{2}+\|\frac{1}{| \mathcal{N}(v)|}\sum_{u\in\mathcal{N}_{v},\bm{x}_{u}\neq\bm{\mu}_{p}}\bm{W}\bm {x}_{u}-\bm{c}_{v}^{\perp}\|^{2}.$ $$

Note that there is no node $u\in\mathcal{N}(v)$ such that $\bm{x}_{u}=\bm{\mu}_{j}$ for $j\neq p$ and $j\in[P]$. Therefore, we can show that the optimized $\bm{c}_{v}^{\parallel}$ by (7) is in the direction of $\bm{W}\bm{\mu}_{p}$, and

$$ $\|\bm{c}_{v}^{\parallel}\|\geq\frac{1}{D_{\mathcal{G}}},$ (16) $$

since that

$$ $\frac{1}{|\mathcal{N}(v)|}\sum_{u\in\mathcal{N}_{v}}\mathbbm{1}[\bm{x}_{u}=\bm {\mu}_{p}]\geq\frac{1}{D_{\mathcal{G}}}.$ (17) $$

Hence, we can obtain that the optimized clustering center $\bm{c}_{v_{1}}$ and $\bm{c}_{v_{2}}$ for $v_{1},v_{2}\in\mathcal{V}$ with $y_{v_{1}}\neq y_{v_{2}}$, we have

$$ $\|\bm{c}_{v_{1}}-\bm{c}_{v_{2}}\|\geq\frac{\sqrt{2}}{D_{\mathcal{G}}}\geq \Omega(1),$ (18) $$

which means that $\bm{c}_{v_{1}}$ and $\bm{c}_{v_{1}}$ are distinct enough given $D_{\mathcal{G}}\leq O(1)$. Then, we have

$$ $\text{Node_ID}(v_{1})\neq\text{Node_ID}(v_{2}).$ (19) $$

Then, we analyze the learning process with a linear layer. Let $\bm{V}=(\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{P})$. The gradient of the loss function against $\bm{v}_{j}$, $j\in[P]$, is computed as

$$ $\displaystyle\frac{1}{|\mathcal{V}_{R}|}\sum_{v\in\mathcal{V}_{R}}\frac{ \partial\ell(\bm{z}_{v},y_{v};\bm{V})}{\partial\bm{v}_{j}}$ (20) $\displaystyle=$ $\displaystyle\frac{1}{|\mathcal{V}_{R}|}\sum_{v\in\mathcal{V}_{R},y_{v}=j}- \frac{1}{\hat{p}_{v,j}}\hat{p}_{v,j}(1-\hat{p}_{v,j})\bm{z}_{v}+\frac{1}{| \mathcal{V}_{R}|}\sum_{v\in\mathcal{V}_{R},y_{v}=j^{\prime}\neq j}-\frac{1}{ \hat{p}_{v,j}}(-\hat{p}_{v,j}\hat{p}_{v,j^{\prime}})\bm{z}_{v}$ $\displaystyle=$ $\displaystyle\frac{1}{|\mathcal{V}_{R}|}\sum_{v\in\mathcal{V}_{R},y_{v}=j}( \hat{p}_{v,j}-1)\bm{z}_{v}+\frac{1}{|\mathcal{V}_{R}|}\sum_{v\in\mathcal{V}_{R },y_{v}=j^{\prime}\neq j}\hat{p}_{v,j^{\prime}}\bm{z}_{v}.$ $$

Note that $\hat{p}_{v,j}-1<0$, $\hat{p}_{v,j^{\prime}}>0$. At iteration 0 0, $\bm{V}$ follows a Gaussian distribution and is close to 0 0, which makes the distribution of $\{\hat{p}_{v,i}\}_{i=1}^{P}$ close to be uniform. Therefore, after $T$ iterations, we have that

$$ $\displaystyle\bm{v}_{j}^{(T)}=\bm{v}_{j}^{(0)}+\frac{\eta}{|\mathcal{V}_{R}|} \sum_{v\in\mathcal{V}_{R},y_{v}=j}(1-\hat{p}_{v,j})\bm{z}_{v}-\frac{\eta}{| \mathcal{V}_{R}|}\sum_{v\in\mathcal{V}_{R},y_{v}=j^{\prime}\neq j}\hat{p}_{v,j ^{\prime}}\bm{z}_{v},$ (21) $$

where $\eta\leq O(1)$ is the step size. We know that for all the nodes $v\in\mathcal{V}_{R}$ with $y_{v}=j$, the first $d_{e}$ dimensions are the same. Denote the first $d_{e}$ dimensions of $\bm{v}_{j}^{(T)}$ as $\bm{v}_{j,1:d_{e}}^{(T)}$. Then, after $T=\Omega(\eta^{-1}P)$ iterations, the magnitude of $\bm{v}_{j,1:d_{e}}^{(T)}$ in the direction of the embedding of the first digit of $\text{Node_ID}(v)$ is

$$ $\Omega(\eta^{-1}P)\cdot\frac{\eta}{\mathcal{V}_{R}}\sum_{v\in\mathcal{V}_{R}} \mathbbm{1}[y_{v}=j]\geq\Omega(1).$ (22) $$

Moreover, the magnitude of $\bm{v}_{j,1:d_{e}}^{(T)}$ in the direction of the embedding of other digit of $\text{Node_ID}(v)$ is

$$ $-\Omega(\eta^{-1}P)\cdot\frac{\eta}{\mathcal{V}_{R}}\sum_{v\in\mathcal{V}_{R}} \mathbbm{1}[y_{v}=j^{\prime}\neq j]\cdot\frac{1}{P}\leq-\Omega(\frac{1}{P}).$ (23) $$

Note that the probability of a $d_{e}$-dimensional embedding for other digits other than the first one is $O(1/K)$. Hence, by $r<K$, we can ensure that the first $d_{e}$ dimensions are the dominant part for prediction.
Therefore, for a given $\bm{z}_{v}$ for $v\in\mathcal{G}$, $y_{v}=j$, we have

$$ $\bm{z}_{v}^{\top}\bm{v}_{j}^{(T)}-\bm{z}_{v}^{\top}\bm{v}_{j^{\prime}}^{(T)} \geq\Omega(1),$ (24) $$

so that

$$ $\hat{p}_{v,j}>\hat{p}_{v,j^{\prime}}.$ (25) $$

We can then derive that for any $v\in\mathcal{V}$,

$$ $\mathbbm{1}[y_{v}\neq\arg\max_{i\in[P]}\hat{\bm{p}}_{v,i}]=0.$ (26) $$

∎

###### Proof.

## Appendix C Datasets and Experimental Details

### C.1 Computing Environment

Our implementation is based on PyG (Fey & Lenssen, ) and DGL (Wang et al., ). The experiments are conducted on a single workstation with 8 RTX 3090 GPUs.

**Table 11: Overview of the graph learning dataset used in this work (Morris et al., ; Dwivedi et al., ; Kipf & Welling, ; Chien et al., ; Pei et al., ; Rozemberczki et al., ; Hu et al., ; McAuley et al., ; Leskovec & Krevl, ; Mernyei & Cangea, ; Lim et al., ; Platonov et al., ).**
| Dataset | # Graphs | Avg. # nodes | Avg. # edges | # Feats | Prediction level | Prediction task | Metric |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Cora | 1 | 2,708 | 5,278 | 2,708 | node | 7-class classif. | Accuracy |
| Citeseer | 1 | 3,327 | 4,522 | 3,703 | node | 6-class classif. | Accuracy |
| Pubmed | 1 | 19,717 | 44,324 | 500 | node | 3-class classif. | Accuracy |
| Computer | 1 | 13,752 | 245,861 | 767 | node | 10-class classif. | Accuracy |
| Photo | 1 | 7,650 | 119,081 | 745 | node | 8-class classif. | Accuracy |
| CS | 1 | 18,333 | 81,894 | 6,805 | node | 15-class classif. | Accuracy |
| Physics | 1 | 34,493 | 247,962 | 8,415 | node | 5-class classif. | Accuracy |
| WikiCS | 1 | 11,701 | 216,123 | 300 | node | 10-class classif. | Accuracy |
| Squirrel | 1 | 5,201 | 216,933 | 2,089 | node | 5-class classif. | Accuracy |
| Chameleon | 1 | 2,277 | 36,101 | 2,325 | node | 5-class classif. | Accuracy |
| Amazon-ratings | 1 | 24,492 | 93,050 | 300 | node | 5-class classif. | Accuracy |
| Questions | 1 | 48,921 | 153,540 | 301 | node | 2-class classif. | ROC-AUC |
| ogbn-arxiv | 1 | 169,343 | 1,166,243 | 128 | node | 40-class classif. | Accuracy |
| ogbn-proteins | 1 | 132,534 | 39,561,252 | 8 | node | 112 binary classif. | ROC-AUC |
| ogbn-products | 1 | 2,449,029 | 61,859,140 | 100 | node | 47-class classif. | Accuracy |
| pokec | 1 | 1,632,803 | 30,622,564 | 65 | node | binary classif. | Accuracy |
| ogbl-collab | 1 | 235,868 | 1,285,465 | 128 | edge | link prediction | Hits@50 |
| Peptides-func | 15,535 | 150.9 | 307.3 | 9 | graph | 10-task classif. | AP |
| Peptides-struct | 15,535 | 150.9 | 307.3 | 9 | 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-class classif. | Accuracy |
| PROTEINS | 1,113 | 39.06 | 72.82 | 3 | graph | 2-class classif. | Accuracy |
| DD | 1,178 | 284.32 | 715.66 | 89 | graph | 2-class classif. | Accuracy |
| COLLAB | 5,000 | 74.49 | 2457.78 | 1 | graph | 3-class classif. | Accuracy |
| REDDIT-BINARY | 2,000 | 429.63 | 497.75 | 1 | graph | 2-class classif. | Accuracy |
| REDDIT-MULTI-5K | 4,999 | 508.52 | 594.87 | 1 | graph | 5-class classif. | Accuracy |
| IMDB-BINARY | 1,000 | 19.77 | 96.53 | 1 | graph | 2-class classif. | Accuracy |

### C.2 Description of Datasets

Table 11 presents a summary of the statistics and characteristics of the datasets. The initial eight datasets are sourced from TUDataset (Morris et al., ), followed by two from LRGB (Dwivedi et al., ), and finally the remaining datasets are obtained from Hu et al. (); Kipf & Welling (); Chien et al. (); Pei et al. (); Rozemberczki et al. (); McAuley et al. (); Leskovec & Krevl (); Mernyei & Cangea (); Lim et al. (); Platonov et al. ().

- •
Supervised Node Classification: Cora, Citeseer, Pubmed, Computer, Photo, CS, Physics, WikiCS, Amazon-ratings, Questions, Squirrel, Chameleon, ogbn-arxiv, ogbn-proteins, ogbn-products and pokec. For Cora, Citeseer, and Pubmed, we employ a training/validation/testing split ratio of 60%/20%/20% and use accuracy as the evaluation metric, consistent with Pei et al. (). For Squirrel, Chameleon, Amazon-ratings and Questions, we adhere to the standard splits and evaluation metrics outlined in Platonov et al. (). For the remaining datasets, standard splits and metrics are followed as specified in Luo et al. (). For comprehensive details on these datasets, please refer to the respective studies (Pei et al., ; Luo et al., ).
- •
Supervised Link Prediction: Cora, Citeseer, Pubmed, ogbl-collab. We follow the standard splits and evaluation metrics specified in Wang et al. (), with further details provided therein.
- •
Supervised Graph Classification: Peptides-func and Peptides-struct. For each dataset, we follow the standard train/validation/test splits and evaluation metrics in Rampášek et al. (). For more comprehensive details, readers are encouraged to refer to Rampášek et al. ().
- •
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 in DGCluster (Bhowmick et al., ).
- •
Unsupervised Node Classification: Cora, Citeseer, Pubmed. For each dataset, we follow the standard splits and evaluation metrics in GraphMAE (Hou et al., ).
- •
Unsupervised Graph Classification: NCI1, PROTEINS, DD, MUTAG, COLLAB, REDDIT-B, REDDIT-M5K, and IMDB-B. Each dataset is a 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 NCI1, PROTEINS, DD, and MUTAG, node labels serve as input features, while for COLLAB, REDDIT-B, REDDIT-M5K, and IMDB-B, node degrees are utilized. In each dataset, we follow exactly the same data splits and evaluation metircs as the standard settings (You et al., ).

### C.3 Baselines

Attributed Graph Clustering. We apply baseline methods from DGCluster (Bhowmick et al., ): SBM (Peixoto, ), AGC Zhang et al. (), SDCN (Bo et al., ), DAEGC (Wang et al., ), NOCD (Shchur & Günnemann, ), DiffPool (Ying et al., ), MinCut (Bianchi et al., ), Ortho (Bianchi et al., ), DMoN (Tsitsulin et al., ) and DGCluster (Bhowmick et al., ).

Unsupervised Node Classification. We utilize all the baselines from GraphMAE (Hou et al., ): GAE (Kipf & Welling, ), DGI (Veličković et al., ), MVGRL (Hassani & Khasahmadi, ), InfoGCL (Xu et al., ), CCA-SSG(Zhang et al., ) and GraphMAE (Hou et al., ).

Unsupervised Graph Classification. We utilize the baselines from GraphCL (You et al., ) and AutoGCL (Yin et al., ): InfoGraph (Sun et al., ), MVGRL (Hassani & Khasahmadi, ), GraphCL (You et al., ), JOAO (You et al., ), GraphMAE (Hou et al., ), AD-GCL Suresh et al. () and AutoGCL (Yin et al., ).

Supervised Node Classification. We compare our method to the following prevalent GNNs and transformer models from Polynormer (Deng et al., ): GCN (Kipf & Welling, ), SAGE (Hamilton et al., ), GAT (Veličković et al., ), APPNP (Gasteiger et al., ), GPRGNN (Chien et al., ),
LINKX (Lim et al., ), Polynormer (Deng et al., ), SGFormer (Wu et al., ). Furthermore, various other GTs like (Kong et al., ; Wu et al., ; Chen et al., ; Rampášek et al., ; Shirzad et al., ; Dwivedi et al., ; Liu et al., ; Zhang et al., ; Kuang et al., ; Bo et al., ; Chen et al., ; Ying et al., ; Dwivedi & Bresson, ) exist in related surveys (Hoang et al., ; Müller et al., ), 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., ): GCN (Kipf & Welling, ), SEAL (Zhang & Chen, ), NBFnet (Zhu et al., ), Neo-GNN (Yun et al., ), BUDDY (Chamberlain et al., ), NCN (Wang et al., ).

Supervised Graph Classification. We compare our method to the GCN (Kipf & Welling, ). In terms of transformer models, we consider GT(Dwivedi & Bresson, ), Graph ViT (He et al., ), Exphormer (Shirzad et al., ), GraphGPS (Rampášek et al., ), and GRIT (Ma et al., ).

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 adjust their hyperparameters, conducting a search within the parameter space defined in the original papers, to attain the highest possible accuracy.

### C.4 Hyperparameters and Reproducibility

RVQ Implementation Details. As outlined in Sec. 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 $||\cdot||$ within the RVQ framework. The codebook size $K$ is tuned in $\{4,6,8,16,32\}$. The $\beta$ is set to 1.

For the hyperparameter selections of our NID framework, in addition to what we have covered, we list other settings in 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.

**Table 12: Dataset-specific hyperparameter settings of NID framework.**
| Dataset | Codebook size $K$ | MPNN | MPNNs layer $L$ | Hidden dim | LR | epoch | MLP layer |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Cora | 6 | GCN | 3 | 256 | 0.001 | 300 | - |
| Citeseer | 6 | GCN | 3 | 256 | 0.001 | 300 | - |
| Pubmed | 6 | GCN | 3 | 256 | 0.001 | 300 | - |
| Computer | 6 | GCN | 3 | 256 | 0.001 | 300 | - |
| Photo | 6 | GCN | 3 | 256 | 0.001 | 300 | - |
| Physics | 6 | GCN | 3 | 256 | 0.001 | 300 | - |
| ogbn-arxiv | 6 | GCN | 5 | 256 | 0.001 | 300 | - |
| Cora | 32 | GCN | 2 | 1024 | 0.001 | 1500 | 3 |
| Citeseer | 8 | GCN | 2 | 256 | 0.001 | 500 | 3 |
| Pubmed | 16 | GCN | 2 | 128 | 0.0005 | 500 | 3 |
| NCI1 | 4 | GIN | 5 | 32 | 0.01 | 20 | - |
| MUTAG | 16 | GIN | 4 | 32 | 0.01 | 20 | - |
| PROTEINS | 8 | GIN | 3 | 32 | 0.01 | 20 | - |
| DD | 4 | GIN | 4 | 32 | 0.01 | 20 | - |
| COLLAB | 32 | GIN | 5 | 32 | 0.01 | 20 | - |
| REDDIT-BINARY | 4 | GIN | 5 | 32 | 0.01 | 20 | - |
| REDDIT-MULTI-5K | 4 | GIN | 4 | 32 | 0.01 | 20 | - |
| IMDB-BINARY | 8 | GIN | 3 | 32 | 0.01 | 20 | - |
| Cora | 6 | GCN | 4 | 128 | 0.01 | 1000 | 5 |
| Citeseer | 8 | GCN | 2 | 128 | 0.01 | 1000 | 5 |
| Pubmed | 16 | GCN | 2 | 256 | 0.005 | 1000 | 5 |
| Computer | 8 | GAT | 6 | 512 | 0.001 | 1200 | 5 |
| Photo | 4 | GAT | 6 | 512 | 0.001 | 1200 | 4 |
| CS | 16 | GAT | 7 | 512 | 0.001 | 1600 | 4 |
| Physics | 4 | GAT | 5 | 512 | 0.001 | 1600 | 4 |
| WikiCS | 8 | GAT | 8 | 512 | 0.001 | 1000 | 4 |
| Squirrel | 32 | GCN | 5 | 128 | 0.01 | 500 | 3 |
| Chameleon | 16 | GCN | 3 | 64 | 0.01 | 500 | 2 |
| Amazon-ratings | 16 | GAT | 12 | 512 | 0.001 | 2500 | 4 |
| Questions | 4 | GAT | 5 | 512 | 0.00003 | 1500 | 4 |
| ogbn-arxiv | 16 | SAGE | 5 | 256 | 0.0005 | 1000 | 4 |
| ogbn-proteins | 4 | SAGE | 4 | 256 | 0.0005 | 1000 | 5 |
| ogbn-products | 16 | SAGE | 5 | 128 | 0.003 | 1000 | 4 |
| pokec | 16 | SAGE | 7 | 256 | 0.0005 | 2000 | 5 |
| Cora | 32 | GCN | 10 | 256 | 0.004 | 150 | 3 |
| Citeseer | 8 | GCN | 10 | 256 | 0.01 | 10 | 3 |
| Pubmed | 8 | GCN | 10 | 256 | 0.01 | 100 | 3 |
| ogbl-collab | 16 | GCN | 5 | 256 | 0.001 | 150 | 3 |
| Peptides-func | 16 | GCN | 6 | 235 | 0.001 | 500 | 5 |
| Peptides-struct | 16 | GCN | 6 | 235 | 0.001 | 250 | 5 |

Attributed Graph Clustering. We implement our NID on top of the GCN in DGCluster (Bhowmick et al., ). To ensure a fair comparison, we use the same hyperparameters, including the number of layers, learning rate, hidden dimensions, and clustering method, as in DGCluster (Bhowmick et al., ).

Unsupervised Node Classification. The pretraining hyperparameters are selected within the GraphMAE’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., ).

Unsupervised Graph Classification. Similarly, our pretraining hyperparameters in table are determined within GraphCL’s grid search space. All other experimental parameters match those used in GraphCL (You et al., ). Specially for this task, following GraphCL (You et al., ), we input $\textbf{NID}_{\text{CL}}$ codes into a downstream LIBSVM (Chang & Lin, ) classifier. And models are trained for 20 epochs and tested every 10 epochs. We conduct a 10-fold cross-validation on every dataset. 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 5 times using different random seeds, with mean and standard deviation of accuracies (%) reported.

Supervised Node Classification. The pretraining hyperparameters listed in the table are based on the grid search space from Luo et al. (). 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., ). For the Cora, CiteSeer, and PubMed datasets, we employ the Hadamard product as the readout function. For ogbl-collab, we use *sum* pooling on the node IDs of the $1$-hop common neighbors (Barabási & Albert, ) to nodes $u$ and $v$ for the edge $(u,v)$, expressed as
$\sum_{w\in\mathcal{N}(v)\cap\mathcal{N}(u)}\text{Node_ID}(w)$.

Supervised Graph Classification. All experimental parameters are consistent with those used by Tönshoff et al. ().

Applications of Node IDs for Graph Learning.
After obtaining the ID, we train the Multi-Layer Perceptron (MLP) for different tasks, with the number of layers specified in Table 12 and hidden dimensions of either 256 or 512. We utilize the Adam optimizer (Kingma & Ba, ) with the default settings. We set a learning rate of either 0.01 or 0.001 and an epoch limit of 1000. The ReLU function serves as 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 hyperparameters. All results are derived from 10 independent runs, with mean and standard deviation of results reported.

## Appendix D Additional Results

### D.1 Qualitative Analysis

Figure: Figure 7: The codeword distributions of the node IDs in PubMed colored by the ground-truth labels.
Refer to caption: extracted/5936721/analysis_id_distribution_pubmed_all.png

Figure: Figure 8: The codeword distributions of the node IDs in CiteSeer colored by the ground-truth labels.
Refer to caption: extracted/5936721/analysis_id_distribution_citeseer_all.png

### 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 et al. (). Initially, the $\textbf{NID}_{\text{CL}}$ is pre-trained on 2 million unlabeled molecules sourced from ZINC15 (Hu* et al., ).

- •
Node features:
–
Atom number: $[1,118]$
–
Chirality tag: $\{$unspecified, tetrahedral cw, tetrahedral ccw, other$\}$
- •
Edge features:
–
Bond type: $\{$single, double, triple, aromatic$\}$
–
Bond direction: $\{$–, endupright, enddownright$\}$

Then, we focus on molecular property prediction, where we adopt the widely-used 7 binary classification datasets contained in MoleculeNet (Wu et al., ) for linear probing. The scaffold-split (Ramsundar et al., ) is used to split downstream dataset graphs into training/validation/testing set as 80%/10%/10% which mimics real-world use cases. For the evaluation protocol, we run experiments for 10 times
and report the mean and standard deviation of ROC-AUC scores
(%).

Model Hyperparameters. Following You et al. (), we adopt a 5-layer GIN (Xu et al., ) with a 300 hidden dimension as the MPNN architecture, and set the RVQ codebook size at $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 is 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 et al., ), 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 $\textbf{NID}_{\text{CL}}$ outperforms the baselines in the SIDER, ClinTox, and BBBP datasets, and shows significant improvement over the embeddings from GraphCL. This suggests the robust transferability of $\textbf{NID}_{\text{CL}}$.

**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 | 48.9 ± 6.5 | 64.9 ± 2.0 | 54.8 ± 0.7 | 68.8 ± 0.9 |
| ContextPred | 68.4 ± 0.3 | 59.1 ± 0.2 | 59.4 ± 0.3 | 43.2 ± 1.7 | 68.9 ± 0.4 | 59.1 ± 0.2 | 64.4 ± 0.6 |
| AttrMask | 69.1 ± 0.2 | 58.2 ± 0.2 | 51.7 ± 0.1 | 51.6 ± 0.7 | 60.9 ± 1.3 | 61.0 ± 1.3 | 64.4 ± 2.5 |
| JOAO | 70.6 ± 0.4 | 60.5 ± 0.3 | 57.4 ± 0.6 | 54.1 ± 2.6 | 68.1 ± 0.9 | 63.7 ± 0.3 | 71.2 ± 1.0 |
| SimGRACE | 64.6 ± 0.4 | 59.1 ± 0.2 | 54.9 ± 0.6 | 63.4 ± 2.6 | 66.3 ± 1.5 | 65.4 ± 1.2 | 67.8 ± 1.3 |
| GraphCL | 64.4 ± 0.5 | 59.4 ± 0.2 | 54.6 ± 0.3 | 59.8 ± 1.2 | 63.7 ± 2.3 | 62.4 ± 0.7 | 71.1 ± 0.7 |
| $\textbf{NID}_{\text{CL}}$ | 66.3 ± 0.4 | 59.1 ± 0.3 | 60.1 ± 0.4 | 65.3 ± 2.2 | 64.3 ± 0.8 | 66.9 ± 0.6 | 66.1 ± 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^{L}})$ with only $O(K\times M\times L)$ in codebook size, which far surpasses VQGraph’s capacity that is limited to its single codebook size. As depicted in Table 14, $\textbf{NID}_{\text{GCN}}$ is considerably more efficient than VQGraph.

Quality. We specifically compare the node classification results with VQGraph tokens under the same experimental settings. VQGraph tokens refers to training an MLP with tokens learned by VQGraph tokenizer from Yang et al. (). As shown in Table 15, VQGraph tokens lack structural information, likely due to codebook collapse encountered by their tokenizer (see Table 4.2).

**Table 14: Comparison of optimal total codebook sizes.**
|  | Cora | CiteSeer | PubMed | Computer |
| --- | --- | --- | --- | --- |
| VQGraph | 2048 | 4096 | 8192 | 16384 |
| $\textbf{NID}_{\text{GCN}}$ ($K\times M\times L$) | $6\times 3\times 4=72$ | $8\times 3\times 2=48$ | $16\times 3\times 2=96$ | $8\times 3\times 5=120$ |

**Table 15: Node classification results in supervised representation learning.**
|  | Cora | CiteSeer | PubMed | ogbn-arxiv |
| --- | --- | --- | --- | --- |
| Metric | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ | Accuracy$\uparrow$ |
| VQGraph tokens | 63.39 ± 1.15 | 32.07 ± 2.70 | 54.37 ± 4.76 | 43.57 ± 0.49 |
| $\textbf{NID}_{\text{GCN}}$ | 87.88 ± 0.69 | 76.89 ± 1.09 | 89.42 ± 0.44 | 71.27 ± 0.24 |

### D.4 High Codebook Usage in NID

In response to the surprising high codebook usage of our NID compared to VQGraph, we believe this is 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 a significantly larger codebook size, ranging from 2048 to 32,768 (as reported in Table 12 of the VQGraph paper (Yang et al., )). Their codebook size typically scales the graph size; for example, on the Citeseer dataset, which comprises 2,110 nodes, they used a codebook size of 4,096.

We have observed that a 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., ).

### D.5 Reconstruction Task Exclusion in ℒ NID subscript ℒ NID \mathcal{L}_{\text{NID}} caligraphic_L start_POSTSUBSCRIPT NID end_POSTSUBSCRIPT

In this section, we address the exclusion of the reconstruction task in our $\mathcal{L}_{\text{NID}}$, differentiating it from other methods such as VQ-VAE and VQGraph. A reconstruction task typically involves using code vectors to regenerate the input data, aiming to minimize the difference between the original input and its reconstruction.

Our decision to omit a reconstruction loss component was based on an ablation study comparing our approach with VQGraph. By replicating VQGraph’s experimental setup, minus the reconstruction loss, we found that omitting this component had a negligible impact on performance, as shown in Table 16.

Moreover, as suggested by Vignac et al. (), generative models like VQ-VAE, 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 a reconstruction task.

**Table 16: Impact of excluding reconstruction loss on performance**
| Model | Cora | CiteSeer | PubMed | ogbn-products |
| --- | --- | --- | --- | --- |
| VQGraph | 76.08 ± 0.55 | 78.40 ± 1.71 | 83.93 ± 0.87 | 79.17 ± 0.21 |
| VQGraph without reconstruction loss | 76.17 ± 0.47 | 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 to embeddings generated by a 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 as learning rates and epochs.

We conducted experiments to evaluate both methods: end-to-end learning versus post-hoc 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 |
| --- | --- | --- | --- |
| $\textbf{NID}_{\text{GCN}}$ (End-to-End Learning) | 87.88 ± 0.69 | 76.89 ± 1.09 | 89.42 ± 0.44 |
| $\textbf{NID}_{\text{GCN}}$ (Post-hoc RVQ) | 86.17 ± 0.33 | 75.47 ± 1.31 | 88.32 ± 0.54 |

### D.7 Transductive vs. Inductive Inference

It is important to clarify that our 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-func dataset detailed in Table 3, we classified 15,535 graphs that were split into training, validation, and test sets. The key point here is that the graphs used during the inference stage were not exposed to the model during training. Additionally, we followed the inductive settings described in the VQGraph paper (Yang et al., ) to perform node classification experiments on the ogbn-products dataset. The results in Table 18 clearly demonstrate that our NID method achieves superior performance in both inductive and transductive settings.

**Table 18: Comparison of inductive and transductive inference performance on ogbn-products**
| Model | ogbn-products (Inductive) | ogbn-products (Transductive) |
| --- | --- | --- |
| VQGraph | 77.50 ± 0.25 | 79.17 ± 0.21 |
| $\textbf{NID}_{\text{SAGE}}$ | 79.13 ± 0.32 | 81.83 ± 0.26 |

## Appendix E Additional Discussion

### E.1 RVQ Implementation Details

In our model, each MPNN layer involves the use of $M$ codewords per node, which implies that RVQ is conducted over $M$ iterations.

It is crucial to note that each layer utilizes an independent set of $M$ codebooks. Specifically, we quantize the node embedding ${\bm{h}}_{v}^{l}$ by sequentially selecting the closest code vector from each codebook:

- •
The first code vector ${\bm{e}}_{c_{l1}}$ (${c_{l1}}$ is the codeword) is chosen based on the initial node embedding ${\bm{r}}_{l1}={{\bm{h}}}_{v}^{l}$.
- •
Subsequent code vectors, such as ${\bm{e}}_{c_{l2}}$, are selected based on the residual vector ${\bm{r}}_{l2}={{\bm{h}}}_{v}^{l}-{\bm{r}}_{l1}$, and so forth.

For each codebook approximation, we optimize two types of losses: the codebook loss and the commitment loss, as detailed in Equation 8. Taking the $\textbf{NID}_{\text{MAE}}$ as an example, during training, we aggregate all losses from each codebook across all layers ($L\times M$) into an additional loss component. This component is then jointly optimized with the MAE loss, as described in Equation 9, within a 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, we compared the training time per epoch of our $\textbf{NID}_{\text{SAGE}}$ with SAGE on ogbn-products. The results are revealing: the NID model records a training time of 5.9 seconds per epoch, closely mirroring that of SAGE, which is at 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 our NID model, demonstrating its capability to maintain comparable training times to traditional GNNs despite the added complexity of the multi-level codebook optimization.

## Appendix 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 to their low-dimensional nature. However, we have found that the number of available datasets for very large networks is limited, and we 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.

## Appendix G Further Related Works

Vector Quantization (VQ). VQ compresses the representation space into a compact codebook of multiple codewords, using a single code to approximate each vector (Liu et al., ). Advanced methods like VQ-VAE (Van Den Oord et al., ) and RQ-VAE (Lee et al., ) enhance quantization precision by employing multiple codebooks, initially for image generation and later adapted to recommender systems (Rajput et al., ; Liu et al., ) and multimodal representation learning (Zheng et al., ; Xia et al., ). This paper introduces residual quantization for learning structure-aware node IDs, achieving superior feature compression performance.

Positional Encodings (PEs) as Graph Tokens.
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., ). The Graph Transformer (Dwivedi & Bresson, ) and SAN (Kreuzer et al., ) initially employed Laplacian eigenvectors as PEs. Subsequent models like LSPE (Dwivedi et al., ) utilized random walk probabilities as node tokens. TokenGT (Kim et al., ) introduced orthogonal vectors for both node and edge tokens, and follow-up works also consider larger graphs (Luo et al., ; Luo, ). However, these methods primarily encode the structural information of the graph and overlook the features of nodes, thereby constraining their direct application.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Nice paper.  However when I dove into the experimental results of the Polynormer paper it raised a lot of questions.

1. The core issue is that in this paper you show weak methods (e.g. GCN) performing well on datasets.  
Lets 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 :)

It 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)
soundness: 3
strengths: + very well written paper about a pressing topic (graph quantization)
+ extensive results help provide details about the method
+ I'm confident the method seems to work well (but perhaps doesn't actually win on baselines, see weaknesses)
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.

Note: 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.
weaknesses: - Egregious experimental result reuse raises a number of inconsistencies for the few methods the authors have recomputed.
- Its difficult to place the results in context with the related work (ie the Polynormer paper results).

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: How does the joint training of the GNN and vector quantization components affect the overall computational efficiency, especially when scaling to larger datasets?
soundness: 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.
2. The authors conduct comprehensive experiments across 34 diverse datasets and tasks, demonstrating the effectiveness of their method. 
3. The paper is well-structured and easy to read.
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.
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. 
2. 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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1.	What 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.
2.	Let’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?
3.	The definition of the M is vague. What does M mean in the size of codebook L*M?
4.	In 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.
5.	What 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). 
6.	For the argument in box 4.1, as I say, why directly use IDs as representations instead of corresponding vectors in the codebook?
7.	What is the interpretation of your discrete representations?
soundness: 3
strengths: 1.	The paper is well-written and solid, especially practical in the case of large-scale graphs.
2.	The overview of the proposed framework helps readers to understand the main pipeline of the work.
3.	The experiment part is sufficient to clarify the effectiveness and efficiency of NID.
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.
weaknesses: 1.	The 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.
2.	Some concepts in the paper are vague. Refer to questions for more details. 
3.	The introduction of codebook seems useless since the codeword is used in neither loss of VQ nor loss of tasks.

Meta-review: The paper introduces a vector quantization (VQ) method for GNN representations, particularly leveraging node embeddings from varying depths of the network. The method is distinct from recent works (e.g., VQGraph) in not relying on a reconstruction loss. The authors provide extensive experimental validation, demonstrating competitive performance across multiple datasets.

The strengths include the presentation, the novelty, the importance of the problem (GNN representation efficiency) and good empirical performance. There is no big weakness. The only weakness is a lack of guarantees of the information loss due to the quantization and how it may affect different applications.  

Overall, I lean to accept this paper.

Decision: Accept (Poster)