Research map / Graph learning / Graph self-supervised learning
Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes NID, an end-to-end framework that compresses multi-layer GNN node embeddings via residual vector quantization into compact 6-15 dimensional int4 node IDs usable for fast node, link, graph, and clustering tasks under self-supervised and supervised training.
Problem
GNN inference on large-scale graphs is slow and memory-heavy because message passing requires loading the graph, and GNN embeddings are high-dimensional (128-256) and uninterpretable; GNN-to-MLP distillation needs labels and yields poor representations.
Approach
Quantize each GNN layer's node embedding with a multi-tier residual VQ (distinct small codebooks per layer and tier) and jointly train the GNN and codebooks with the downstream or self-supervised objective, so the concatenated codeword tuple serves as a compact discrete node ID; no reconstruction loss on code vectors and no distillation.
Key results
- NID_SAGE on ogbn-products reaches 81.83% accuracy with 0.7ms inference versus 11.9s for SAGE and 17.5MB storage, a speedup of roughly 17,000x.
- NID_GCN achieves 90.33% HR@100 on Cora link prediction versus 85.73% for GCN.
- NID_MAE on unsupervised node classification reaches 74.2% on CiteSeer, the best among compared methods, using 6-dimensional node IDs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace GCN embeddings with discrete NID_GCN representations | GCN · Questions node classification | ROC-AUC: 77.40 -> 96.85 | Helped |
| Replace SAGE embeddings with discrete NID_SAGE representations | SAGE · ogbn-products node classification | accuracy: 83.27 -> 81.83 | Hurt |
| Replace SAGE inference with precomputed NID_SAGE codes | SAGE · ogbn-products node classification | inference time: 11.9s -> 0.7ms | Helped |
| Replace GCN embeddings with NID_GCN and train on node IDs | GCN · Cora link prediction | HR@100: 85.73 -> 90.33 | Helped |
| Replace GCN embeddings with NID_GCN and train on node IDs | GCN · CiteSeer link prediction | HR@100: 89.67 -> 88.56 | Hurt |
| Quantize DGCluster node embeddings into node IDs | DGCluster · Cora attributed graph clustering | NMI: 62.1 -> 70.5 | Helped |
| Use 6-code NID_MAE representations instead of GraphMAE representations | GraphMAE · CiteSeer node classification (unsupervised) | accuracy: 73.4 -> 74.2 | Helped |
| Use 6-code NID_MAE representations instead of GraphMAE representations | GraphMAE · Cora node classification (unsupervised) | accuracy: 84.2 -> 80.8 | Hurt |
| Quantize GraphCL-learned node embeddings into NID_CL codes | GraphCL · REDDIT-B graph classification | accuracy: 89.5 -> 90.7 | Helped |
| Quantize GraphCL-learned node embeddings into NID_CL codes | GraphCL · NCI1 graph classification | accuracy: 77.8 -> 75.9 | Hurt |
| Quantize GraphCL embeddings into NID_CL codes for linear probing | GraphCL · Sider molecular property prediction | ROC-AUC: 54.6 ± 0.3 -> 60.1 ± 0.4 | Helped |
| Set RVQ level M to 3 rather than M=1 (ablation) | NID_GCN · Node classification benchmarks | performance | Helped |
Surprising findings
- NID_GCN outperforms GCN by about 20% on the highly imbalanced Questions dataset.
- Omitting the reconstruction loss on codebook vectors has a negligible effect on performance.
Limitations
- Performance is not uniformly better than baselines; NID trails GCN/SAGE on several datasets such as ogbn-arxiv and Computer accuracy.
- Codebook size and MPNN depth must be tuned per dataset.
Experimental setup
Datasets: Cora CiteSeer PubMed Computer Photo CS Physics WikiCS Squirrel Chameleon Amazon-ratings Questions
Benchmarks: Cora CiteSeer PubMed Computer Photo CS Physics WikiCS Squirrel Chameleon Amazon-ratings Questions
Metrics: accuracy ROC-AUC AP MAE NMI F1 inference time storage space
Baselines: VQGraph Graph-MLP GCN GAT SAGE Polynormer SGFormer GraphMAE
Builds on: VQ-VAE GraphMAE GraphCL VQGraph DGCluster
Closest papers by meaning
- Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning (NeurIPS 2021 · similarity 0.91)
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (NeurIPS 2020 · similarity 0.90)
- Identity-aware Graph Neural Networks (AAAI 2021 · similarity 0.89)
- Learning Representations for Hierarchies with Minimal Support (NeurIPS 2024 · similarity 0.89)
- Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction (ICLR 2022 · similarity 0.89)
- Subgraph Invariant Learning Towards Large-Scale Graph Node Classification (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.