Contextual Tokenization for Graph Inverted Indices
Pritish Chakraborty Indradyumna Roy Soumen Chakrabarti Abir De · 2025
Read Contextual Tokenization for Graph Inverted Indices by Pritish Chakraborty Indradyumna Roy Soumen Chakrabarti Abir De (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22479.txt.
Introduction
Finding stored graphs that contain a smaller query graph is the problem addressed in a 2025 paper by Pritish Chakraborty, with Indradyumna Roy, Soumen Chakrabarti, and Abir De. Graphs here are networks of linked points, and older accurate tests were too slow because they scored every stored graph one by one.
Their system, called CORGII, turns a rich graph description into short binary codes, much like words in a text index. Learned weights replace fixed scoring rules, and extra token copies let users trade speed against accuracy. Tests against several rival methods show CORGII gives a better balance of accuracy and efficiency.
Catalog record
| CREATOR | Pritish Chakraborty Indradyumna Roy Soumen Chakrabarti Abir De |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22479
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Contextual Tokenization for Graph Inverted Indices Pritish Chakraborty Indradyumna Roy Soumen Chakrabarti Abir De Abstract Retrieving graphs from a large corpus, that contain a subgraph isomorphic to a given query graph, is a core operation in many real-world applications. While recent multi-vector graph representations and scores based on set alignment and containment can provide accurate subgraph isomorphism tests, their use in retrieval remains limited by their need to score corpus graphs exhaustively. We introduce CoRGII (Contextual Representation of Graphs for Inverted Indexing), a graph indexing framework in which, starting with a contextual dense graph representation, a differentiable discretization module computes sparse binary codes over a learned latent vocabulary. This text document-like representation allows us to leverage classic, highly optimized inverted indices, while supporting soft (vector) set containment scores. Pushing this paradigm further, we replace the classical, fixed impact weight of a ‘token’ on a graph (such as TFIDF or BM25) with a data-driven, trainable impact weight. Finally, we explore token expansion to support multi-probing the index for smoother accuracy-efficiency tradeoffs. To our knowledge, CoRGII is the first indexer of dense graph representations using discrete tokens mapping to efficient inverted lists. Extensive experiments show that CoRGII provides better trade-offs between accuracy and efficiency, compared to several baselines. Code is in: https://github.com/structlearning/corgii . 1 Introduction Given a query graph G_{q} , a common graph retrieval task is to find, from a large corpus of C graphs, graphs G_{c} that each contain a subgraph isomorphic to G_{q} [ 1 ] . The ranking relaxation is to find K graphs that ‘best’ contain G_{q} , under a suitable notion of approximate subgraph containment score. This task has several applications, e.g. , functional group search in molecular databases [ 2 ] , control-flow pattern detection in program analysis [ 3 ] , semantic search in scene graphs [ 4 ] , etc . Graph retrieval faces two challenges. Locally, the exact subgraph isomorphism decision problem is NP-complete [ 5 ] — but this can be circumvented via suitable score approximations, even if heuristic in nature. The more pressing global challenge is that the best approximations need early cross-interaction between G_{q} and G_{c} , leading to an impractical \Omega(C) query time. Our goal is to devise a novel indexing framework to attack the global bottleneck. Single vs. multi-vector graph representation tradeoffs Approximate scores for graph containment may be computed by two families of neural networks. Early methods [ 6 , 7 , 8 ] use a single vector to represent a whole graph, enabling efficient relevance computation in (hashable/indexable) Euclidean space, but miss fine-grained structural details. Later methods [ 9 , 10 , 11 ] represent a graph as a set of node embedding vectors and solve a form of optimal transport [ 9 , 10 ] between them to get better score approximations. This parallels the shift in dense text retrieval from late-interaction or “dual encoder” or “bi-encoder” style that pools a passage into a single vector [ 12 , 13 , 14 ] to multi-vector representations [ 15 , ColBERT] . Lessons from text retrieval Classical text retrieval used inverted indices keyed on discrete tokens or words [ 16 , 17 , 18 ] mapping to posting lists of document IDs, with highly optimized implementations [ 19 , 20 , 21 ] that are still widely used. When word embeddings and neural text encoders became popular, first-generation dense retrieval systems used single vectors to represent queries and passage, leading to rapid adoption of approximate nearest neighbor (ANN) indexing methods [ 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 ] . Mirroring the situation with graphs, late interaction between query and passage embeddings via cosine, L2 or dot product scores leads to efficient indices, but these scores are not as accurate as those obtained by early cross-interaction, which are not directly indexable. A notable and effective compromise was separate contextualization of query and passage words, followed by a novel Chamfer score [ 35 ] as an indexable surrogate of cross-interaction, as in ColBERT [ 15 ] and PLAID [ 36 ] . These methods probe the ANN index once per query word, and perform extra decompression and bookkeeping steps for scoring passages. Thus, even the partial contextualization and limited cross-interaction come at a performance premium. SPLADE [ 37 ] further improves efficiency by pre-expanding documents to include extra related words, and then use a standard inverted index on these expanded documents. In case of text, contextual similarity between words provides the signals needed for expansion. 1.1 Our Contributions In proposing our system, CoRGII (Contextual Representation of Graphs for Inverted Indexing), our goal is to apply the wisdom acquired from the recent history of dense text retrieval to devise a scalable index for graphs to support subgraph containment queries. In doing so, we want to use a contextual graph representation that gives accurate containment scores, but also takes advantage of decades of performance engineering invested in classic inverted indices. Differentiable graph tokenization We introduce a graph tokenizer network (GTNet) which uses a graph neural network (GNN) to map each node to a structure-aware token over a latent vocabulary. At the outset, GTNet computes binary node representations, which serve as discrete tokens, thereby forming multi-vector discrete graph representations. Our approach is significantly different from existing continuous graph embedding methods [ 6 , 7 , 9 , 10 , 8 , 11 ] , most of which employ Siamese networks with hinge distance to learn order embeddings. In contrast, inverted indices basically implement fast sparse dot-product computation. To reconcile this gap, we use separate tokenizer networks for query and corpus graphs, but allow a symmetric distance between the matched nodes. Prior works [ 9 , 10 ] also use injective alignment. However, we find it suboptimal, due to the subtle inconsistencies introduced by its continuous relaxation. Instead, we compute the Chamfer distance [ 35 ] over discrete node representations, which supports accurate token matching, even without injective alignment. We use these tokens to build an inverted index, where each token is mapped to the posting lists of corpus graphs containing it. Query-aware trainable impact score Text queries and documents represented as pure word sets (ignoring word counts or rarity) are not as effective for retrieval as vector space models , where each word has a certain impact on the document, based on raw word frequency, rarity of the word in the corpus (inverse document frequency or IDF), etc. Thus the query and each document are turned into sparse, non-negative, real-valued vectors. We introduce a trainable token impact score that acts as a learned analog of classical term weights like TFIDF and BM25, but for tokenized graphs instead of text. Given a query node, this score function takes as input both its continuous and discrete representation and assigns different importance weights to the same words based on the structural information, captured through the continuous representation. This enables fine-grained, query-aware scoring while maintaining compatibility with inverted indexing. Recall-enhancing candidate generation prior to reranking Identifying the best match for a query node in a corpus graph typically requires global optimization over all nodes. In