Research map / Graph learning / Graph self-supervised learning
Contextual Tokenization for Graph Inverted Indices
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 CoRGII, which discretizes contextual graph node embeddings into binary tokens over a learned latent vocabulary so subgraph-containment retrieval can run on classic inverted indices, with learned token impact weights and co-occurrence multiprobing, reranked by IsoNet.
Problem
Retrieving corpus graphs that contain a subgraph isomorphic to a query graph is accurate with multi-vector alignment scores but requires exhaustively scoring every corpus graph, giving Omega(C) query time.
Approach
Use a graph tokenizer network (GNN plus separate query/corpus MLPs with sigmoid, then rounding to D-bit codes) trained with a Chamfer-distance ranking loss, so node tokens map to posting lists; add a trainable token impact MLP in place of TF-IDF/BM25 and co-occurrence-based token expansion for multi-probing.
Key results
- On COX2, CoRGII reaches MAP around 0.50 at k/C=0.5 while FourierHashNet saturates near 0.35.
- On PTC-FR, CoRGII attains MAP around 0.36 retrieving under 33% of the corpus, while most baselines need over 75%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use co-occurrence multiprobing instead of Hamming multiprobing or single probing (ablation) | CoRGII token retrieval · PTC-FR, PTC-FM, COX2, PTC-MR | MAP versus retrieval selectivity | Helped |
| Increase the number of co-occurrence-expanded tokens; gains diminish and saturate beyond b=32 (ablation) | CoRGII with co-occurrence multiprobing · PTC-FR, PTC-FM, COX2, PTC-MR | MAP | Helped |
| Increase the Hamming expansion radius r (ablation) | CoRGII with Hamming multiprobing · PTC-FR, PTC-FM | MAP | Hurt |
| Add learned impact weighting rather than uniform token aggregation (ablation) | CoRGII · PTC-FR, PTC-FM, COX2, PTC-MR | MAP versus retrieval selectivity | Helped |
| Use separate query and corpus MLPs instead of a shared Siamese MLP (ablation) | GTNet · PTC-FR, PTC-FM, COX2, PTC-MR | MAP versus retrieval selectivity | Helped |
| Use co-occurrence multiprobing with a Siamese GTNet instead of Hamming multiprobing (ablation) | Siamese GTNet · PTC-FR, PTC-FM | MAP | Hurt |
| Use Chamfer matching instead of injective soft-permutation alignment (ablation) | GTNet graph matching · Graph retrieval datasets | MAP | Helped |
| Remove learned impact weights from co-occurrence multiprobing (ablation) | CoRGII · COX2, PTC-MR | MAP | Hurt |
| Use uniform aggregation with Hamming multiprobing instead of learned impact weighting (ablation) | CoRGII · COX2 | MAP | Mixed |
| Use single probing instead of multiprobing (ablation) | CoRGII · PTC-FR, PTC-FM, COX2, PTC-MR | retrieval selectivity coverage | Hurt |
Surprising findings
- Single-vector baselines sometimes perform below the Random baseline.
Limitations
- Static token vocabulary fixed by binary code length D
- Only purely structural graphs; no node/edge attributes
- Assumes a static corpus with no support for updates
Experimental setup
Datasets: PTC-FR PTC-FM COX2 PTC-MR
Benchmarks: PTC-FR PTC-FM COX2 PTC-MR
Metrics: MAP k/C retrieval fraction
Baselines: FourierHashNet IVF (single-vector) IVF (multi-vector) DiskANN (single-vector) DiskANN (multi-vector) Random
Builds on: IsoNet ColBERT SPLADE FourierHashNet
Closest papers by meaning
- A Systematic Exploration of Knowledge Graph Alignment with Large Language Models in Retrieval Augmented Generation (AAAI 2025 · similarity 0.85)
- DTGB: A Comprehensive Benchmark for Dynamic Text-Attributed Graphs (NeurIPS 2024 · similarity 0.85)
- TEG-DB: A Comprehensive Dataset and Benchmark of Textual-Edge Graphs (NeurIPS 2024 · similarity 0.85)
- SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches (ICLR 2025 · similarity 0.84)
- Generalization Principles for Inference over Text-Attributed Graphs with Large Language Models (ICML 2025 · similarity 0.84)
- Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation (ICLR 2025 · similarity 0.84)
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.