Contextual Tokenization for Graph Inverted Indices
Authors: Pritish Chakraborty
Indradyumna Roy
Soumen Chakrabarti
Abir De
Venue: NeurIPS 2025 poster ()
Keywords: graph indexing
graph retrieval
graph representation learning
Primary area: infrastructure
TL;DR: We design inverted indices for graph-structured objects.

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 indexes, while supporting soft (vector) set containment scores. Improving on this paradigm further, we replace the classical impact score of a `word' on a graph (such as defined by TFIDF or BM25) with a data-driven, trainable impact score.
Crucially, CoRGII is trained end-to-end using only binary relevance labels, without fine-grained supervision of query-to-document set alignments. Extensive experiments show that CoRGII provides better trade-offs between efficiency and accuracy, compared to several baselines.

Contextual Tokenization for Graph Inverted Indices
Pritish Chakraborty
Indradyumna Roy Bombay
Soumen Chakrabarti IIT Bombay
Abir De IIT Bombay
ITT Bombay
Emails: (pritish, indraroy15, soumen, abir) iitb. ac in
Abstract
Retrieving graphs from large corpus, that contain subgraph isomorphic to 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 remains limited by their need score corpus graphs exhaustively. We introduce CoRGII (Contextual Representation of Graphs for Inverted Indexing), graph indexing framework in which, starting with contextual dense graph representation, a differentiable discretization module computes sparse binary codes over a learned leverage
retrieval
latent vocabulary. This text bicument-like representation allows classic, highly optimized inverted indices, while supporting soft (vector) set con- tainment scores. Pushing this paradigm further, replace the classical, fixed impact weight of a 'token' on graph (such as TFIDF or BM25) with a data-driven, trainable impact weight. Finally, explore token expansion to support multi- probing the index for smoother sccuracy-efficienyy 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 CORGIT provides better trade-offs between accuracy and efficiency, compared several baselines. Code is in: bttps://githhb...
gighttt..b.... com cttp http:/sttuuctetettiet corgii
Introduction
Given a query graph G a common graph retrieval task is to find, from a large corpus of C' graphs, graphs G. that each contain subgraph isomorphic G2 (M] The ranking relaxation to find K graphs that 'best' contain Gy. under a suitable notion of approximate subgraph containment score. This task has several applications, e.g., functional group search 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 NP-complete [5] but this can be circumvented via suitable score approximations, even heuristic in nature. The more pressing global challenge is that the best approximations need early cross-interaction between G, and G., leading to an impractical ((C') query time. Our goal is to devise a novel indexing framework attack the global bottleneck.
Single vs. multi-vector graph representation tradeoffss Approximate scores for graph containment may be computed by two families of neural networks. Early methods 7 represent a whole graph, enabling efficient relevance computation in (hashable/indexable) Euclidean represent a graph as set
use single vector to 8
space, but miss fine-grained structural details. Later methods 99 10 11
of node embedding vectors and solve a form of optimal transport 10 between them to get better score approximations. This parallels the shift in dense text retrieval from inte-interaction or "dual encoder" or "bi-encoder" style that pools a passage into a single vector [12 representations [15] ColBERT].
13 [4] to multi-vector
Lessons from text retrieval Classical text retrieval used inverted indices keyed on discrete tokens or words [16] 17 [8] 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,
39th Conference on Ncural Information Processing Systems (NcurIPS 2025).

---

leading to rapid adoption of upproximate nearest neighbor (ANN) indexing methods 22 23 24 25
26
28
29 30
33 34
Mirroring the situation with graphs, late interaction between query and passage emheddings via cosine, 1.2 or dot product scores leads to efficient indices, but these scores not accurate those obtained by early cross-interaction, which are not directly indexable. A notable and effective compromise was separate confextualization of query and passage words, followed by novel Chamfer score [35] as an indexable surrogate of cross-interaction, as in ColBERT [5] 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 cooss-inteaation 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 apply the wisdom acquired from the recent history of dense text retrieval to devise 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 graph neural network (GNN) to map each node to a structure-awar token over 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 10 [1, most of which employ Siamese networks with hinge distance to learn order embeddings. In contrast, inverted indices basically implement fast sparse not-product computation. To reconcile this gap, networks for query and corpus graphs, but allow a symmetric distance between the matched nodes.
separate tokenizer
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 learned analog of classical term weights like TFIDF and BM25, but for tokenized graphs instead of text. Given 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 corpus graph typically requires global optimization over all nodes. In contrast, inverted indexing performs independent per-node matching, often leading to false positives. To tackle this problem, we introduce a novel co-occurrence based multiprobing strategy, where, given token, we probe other tokens with large overlap between their posting lists. Finally, we perform a thresholded aggregation, which facilitates smooth, tunable control over the trade-off curve between accuracy and efficiency.
Experiments on several datasets show that CORGII is superior to several baselines. Moreover, the design of CORGII naturally enables a smooth trade-off' between query latency and ranking quality, which is critical in many applications.

---

2 Preliminaries
Notation. We denote Gyj = (Vy, Fig) query graph and G. (Ve, F.e) as corpus graph. Let (G1, G2...,,Ga be the set C' corpus graphs. Each query-corpus pair (Gg. G.) is annotated with binary label Bue E {0, 1}, where Vqe 1 iff Gg [ Ge. Given corpus item indices C = [C] {I.... C}, we define the set of relevant graphs as Cye {c: Mge = 1} and the set of non-relevant m obtained after suitable padding, we write Ag. A. E {0, } 1)m as the adjacency matrices for G2 and Ge respectively. [+]+ = max {0, +) is the ReLU or hinge function. [ denotes the indicator function which is 1 if predicate holds and 0
graphs Cog
Cg Assuming IV, |Vol
if it does not.
Subgraph isomorphism Given Gg and Ge. the subgraph isomorphism problem seeks to deter- mine iff Gg S Ge- This is equivalent checking whether there exists a permutation matrix P such that A, < PA.P". which results in a coverage loss based relevance distance, defined as: min A - PA.PT
Computation of A(G Go) defined above requires solving a quadratic assignment problem (QAP), which is NP-hard. Therefore, existing works [9] [0] propose a differentiable surrogate of this QAP using asymmetric set distance. Given Gg and G.. they employ graph neural network (GNN) to compute the node embeddings h (u), ha(v) E Rddmm for u E V,, and v E V. respectively, then collect them in H, R.xxdima and H E Rmxxdims, where m is the number of nodes (after padding). These embeddings are fed into a Gumbel-Sinkhorn network [38]9, (39, which produces a doubly stochastic matrix P - a relaxed surrogate of the binary permutation matrix thus providing approximate, injective node alignment map. This enables an approximation of minpepy (A, PA. [+ the following surrogate relevance distance:
(I) The underlying GNN and Gumbel--Snkhonn network is trained under the distant supervision of binary relevance labels, without any demonstration of ground truth permutation matrix P. We shall regard Hg, H. and Eqn. (1) references to compute final scores of qualifying candidates that survive our
AG Ge) = Eie (e [H, PH i], Pe [0,1]mmm is doubly stochastic.
index probes.
Pretrained backbone We use an existing subgraph matching model, namely IsoNet 9 which provides relevance distance A(G,, Ge) of the form given in Eq. ① for any query-corpus graph pair (G G.). This pre-trained backbone is employed solely at the final stage to compute AG G.) for ranking the retrieved candidates. Therefore, we can access Hg, H. and the corresponding node alignment map P.
Inverted Index Here, we describe inverted index based retrieval in a general information retrieval setting with query q and corpus objects wih IDs C = {1,..., C}. Given a vocabulary w, we represent each instance e by a set of discrete tokens w(c) = (7()), -(2) ...... where each T(*) E w. For a collection of corpus items C, the inverted index maps each token in W the set of corpus items con- taining it. Specifically, each token 7 is associated with a posting list PostingList(rr) which consists List((r I E (c))))
of all C containing T, i.e., w(c) 3 T. Formally, write PostingL.ist(7) In "iimpac-orddeedd" posting lists, corpus items are sorted in decreasing order of "impact scores" document. Typically, text retrieval, impact scores are that capture the importance of word modeled using term frequency (TF) and inverted document frequency (IDF) [17]. Given a query Tgg we obtain the token set w(q) and then probe the inverted index traverse across the posting list of each token 7 E w(g). Finally, we retrieve candidates from all such posting lists and return a subset from them as top-k candidates.
3 Proposed approach
We now present CoRGIE a scalable retrieval system for graph retrieval that takes advantage of decades of optimization of inverted indices on discrete tokens, and yet supports scoring and ranking using continuous node embeddings. Starting with the hinge distance ( we propose a series of steps that adapt GNN-based contextual node embeddings toward a discrete token space, enabling to use inverted indices. Before describing the modules of CORGII, we outline these adaptation steps.
GNN-based node embeddings As described in Section 2 (differentiable) GNN contextualizes nodes in their graph neighborhood to output {a,,(u)} and (v)).. The cenppporaaionnisspiree hinge distance between them, found effective for ranking in earlier work, is asymmetric and based
3

---

(2c(1))
T= T=(+)=
(Posting List (r))
(T((0)
Ge
GNN
MLPP.. 0.
Co-occurrence Multiprobing
G 9
GNN
MLP 0g
Pre-trained hg (u)
(2g
Impact
+
Simpact, CM
Retrieved
graphs
Figure 1: CORGII block diagram, Each (query, corpus) graph pair (G,, Ge) is encoded using shared GNN,, followed by separate MLPs (MLPg) p, and MLP&,) to compute soft binary node embeddings zc(v), zg (u) E (0,1) These are thresholded to obtain discrete binary codes (c( (u) e
{0, 1) mapped to integer-valued latent tokens т E T = [2 Corpus tokens are indexed into posting lists PostingList(r). enabling sparse inverted indexing. During retrieval, query tokens (u) are expanded via co-occurrence-bass multi-probing (CM) to select similar tokens (T, (u)) Each expanded token contributes to the corpus score through an impact score Impact, (T, hi (u)).
producing the overall retrieval score Simpac..om (G., Ge). Graphs with score exceeding threshold 8 are shortlisted and reranked using the alignment distance AGG,, G.) (Eq. (.).
on (soft) permutation P. These introduce two major hurdles in the way of deploying inverted indices. CORGII approximates the asymmetric, early- perly-interaction distance [T) with an asymmetric dual encoder (late interaction) network, but based on a non-injective granular scoring function.
Efficient differentiable vokeniitoennizttion As first step toward tokenization,
apply two (still differentiable, but distinct) networks to (u), (v).), ending with sigmoid activations, which take the outputs zz(u), (v)v) closer to bit-vector representation of tokens. The GNN, together with these networks, are trained for retrieval accuracy (and not, e.g., any kind of reconstruction), We also replace the permutation with Chamfer distance [35] which brings closer to inverted indices.
Token discretization and indexing Finally, we round 2, (u), (v) to 0/1 bit vectors
assigning a bit-vector token to each node. Much like text documents, graph is now represented as multiset of discrete tokens. With this step, we lose differentiability, but directly use an inverted index.
Impact weights and multi-probing All tokens should not contribute equally to match scores. Based on corpus and query workloads, we learn suitable impact weights of these (manufactured) tokens. We further optimize the performance of CoRGII by designing suitable aggregation mechanism to prune the posting lists obtained from all the query tokens. Finally, we consider one folklore and one novel means to explore the 'vicinity" of a query token, to provide a smooth trade-off between query latency and ranking accuracy.
3.1 Graph tokenizer network GTNet
We now proceed to describe the major components of CORGII.
The first stage of GTNet is standard GNN similar to that described in Section 2 but here will train exclusively for indexing and retrieval. The GNN will share the same parameters across query and corpus graphs. After the GNN, we will append multi-layer perceptron (MIP) layer with different parameters Φ1 and d2 for the query and corpus graphs.
Zg (u) a (MLP di (u))) for E Vg where, (x²(1)) = GNNo zo o (MLP dz (xe (v))) for Ve where, (x) GN.o(G.).
(2)
Rationale behind different MLP networks Unlike exact graph matching, the subgraph matching task inherently asymmetric, where G, C G. does not mean Ge C Gy. To model this asymmetry, existing works 7 9 10] employs hinge distance A(G Ge) (L. while sharing a a Siamese network with the same parameters for query and corpus pairs. However, such approach will preserve subgraph matching through order embeddings: Z, < SZ But inverted indexing requires exact token matching, making order embeddings incompatible with token- indexing. Therefore, we retain asymmetry through separate MI.Ps for queries and corpus.
Introducing Chamfer Distance between graphs An asymmetric Siamese network lets us replace hinge distance [H, , PH.)e c]+ with the normed distance I| P PZ but, for the sake of indexing, we need to avoid the permutation P (whose best choice depends on both H, and H.), so that "document" graphs can be indexed independent of queries. Moreover, training from relevance labels

---

require P to be modeled as doubly stochastic soft permutation matrix (see Eq. 1). However, its continuous nature of P smears the values in Zg and c.. leading to poor discretization. Due to these reasons, we avoid the permutation, and for each query node match (") to =z(v) for some corpus node v, independently of other query nodes; as opposed to the joint matching of all nodes in query corpus pairs, thus permitting non-injective mappings via the Chamfer distance [35]:
Chamfer(G,, Go) = E'nev, min.ev, ||=,(u) z.(r)]lı:
but GTNet produces approximate binary representations, making exact matches unlikely. To ensure a robust separation between the relevant and non-relevant query-corpus pairs, we seek to impose margin of separation m: non-relevant graphs should differ by at least one additional bit per node compared to the relevant graphs, corresponding total Chamfer distance separation of m.
Ideally, relevant graphs yield Chamfer (G,, G.)
Formally, for a query graph Gy. and the set of relevant and irrelevant (or less relevant) corpus graphs Cg E Cg and ce Cye, we require Chamfer Geg ) < Chamfer (G. Gog). ). This yields the following ranking loss optimized over parameters of GTNet, i.e., 8, Ø1, 02:
min Σ 8,01
Σ
[Chamfer(Gr, Gog) Chamfer(G,, Geg) + m]+
(5)
? og CGEnge.c4CC
Note that node embeddings Z Ze still allow backprop, but are closer to "bit vectors". Moreover, the training of 0, Φi, 02 is guided not by reconstruction considerations, but purely by retrieval efficacy.
3.2
Discretization and inverted index
Once GTNet is trained, we compute, for each corpus graph and node therein, =c(v), and, from there, a bit vector (1) = [x)(v) > 0.5] as 'hard' representation of each corpus node (and similarly from (u) to (u) for query nodes u). Given =n(v) E (0, 1) this means (v(v) E [0,1] 1) i.e., each node gets associated with D-bit integer. Let us call this the token space ' = [2 Note that
multiple nodes in graph may get assigned the same token. Thus, each query graph G2 and corpus graph Ge are associated with multisets of tokens, denoted
(G,))) = (u)
V and w(G.) (v) : e V.B-
(6)
(If a graph is padded for efficient tensor operations, the tokens corresponding to padded nodes are logically excluded from the multisets. We elide this code detail for clarity.)
Conceptually, basic inverted index is a map where the keys are tokens. Each token T E T is mapped to the set (without multiplicity) of corpus graphs (analog of 'documents') )) in which it appears: PostingList(r) = {c E C T wG.)). Intuitively, the goal of minimizing the Chamfer distance (4) in the pre-discretized space corresponds, in the post-discretized space, to locating documents that have large token overlap with the query, which finally enables us to plug an inverted index.
Candidate generation using uniform impact At query time, the query graph G, is processed as in (6), to obtain w(Gg). Given the inverted index, each token т w(Gg) is used to retrieve PostingList (T). As a simple starting point (that we soon improve), a corpus graph can be scored as Sunit (G,, Go) = >nev, (2) E WG.)]
(7)
(If multiple nodes u have the same token ž. they are counted multiple times. Belongingness in (G.) is Boolean, without considering multiplicities.) These scores are used to select a subset of can- didates from the whole corpus. These qualifying candidates are reranked using the (computationally more expensive) alignment- based distance A(Gg. Ge) I
3.3 Impact weight network
The crude unweighted score has some limitations: (1) Information is lost from H to Z to Z. Nodes with minor differences neighborhood structure may be mapped to overlapping tokens, resulting in large candidate pools. (2) Similar to IDF, we need to discriminate against common graph motifs with poor selectivity. In our setting, the combinatorial explosion of motif's makes the estimation of motif frequencies intractable [40). Moreover, unlike IDF in text retrieval [17), frequent structures cannot be weighte,, as subgraph retrieval requires matching all query components, regardless of the frequency of the subgraphs.
To mitigate the above difficulties, we use notion of token impact weight in the same spirit in traditional text retrieval, although there are some crucial differences. We introduce an impact weight network Impact, T x Igdim, + R, parameterized with vi where dim, is the dimension of the
5

---

(a) 2-stage training of CORGII
(b) Retrieval and reranking
input: graph corpus C, training queries {Ga} with
inputs: query Gg. threshold t, pre ave-trained embed-
relevance labels {Uge}
dings (h,(u) } for Gg.
2: D Train GTNet
2: P. Obtain appreximate binary representation
3: for each query-corpus pair (G, G.) do
3: Compute Zg GTNet((Gg) (Fq. 2
4: Compute Z, GTNet (Ga) (Eq. 2
Compute hinary embeddings and tokens
Compute Z. GTNet (Eq.
{2n(u)} = 1 > 0.5]
Compute Chamfer (Gan G.) (Eq.
6: w(G,)) = Obtain TokenSet( (2)()
7: Train GTNet by minimizing nargin-based ranking
7: b. Compute impact weights
loss on Chamfer(GG. Go) (Eq. (5)
for each node V2 do
8: Train impact network
Compute Impact, (m (u)) (Eq. ( 10: & Probe index using query node tokens and their impacts (with optional token expansion) and aggregate preliminary relevance scores
for each query-corpus pair (Gy: Gc) do
10:
Compute Z = GTTNet(Gg)
11:
>. Compute binary embeddings
12:
{Ra(u)} = [Zg 0.5]
11: Simpar, (Ca..MMGGg.... G.) (Eq. 9
13:
compute impact scores of all query graphs
12: b Shortlist candidates
14:
compute (Gapar(Ga, G2) (Eq. (})
13: R,, = {G. Simpacs, CM (G Go) (G))00 6)
15:
Train Impact,. network by minimizing margin-
14: rerank surviving candidates using A Ga)
based ranking loss on Simpuc (G,, Ge) (Eq. (10)
15: return top-k corpus graphs
Figure 2: (a) preprocessing and (b) query-time components of CORGII.
pre-trained continuous node embedding hgg or (c(.). We often substitute with 2q(u) in the input to Impact depending on context.
Neural architecture of Impact& Network Impact, is implemented as a lightweight multi layer perceptron (MLP). Given input token т, presented as a binary code from {0, 1)2, and input node embedding h, we concatenate them and pass the result through a multi-layer perceptron, i.e.
Impact, (T. h) = MLP y (concat (T, h)).
(8)
Rather than count all matched tokens uniformly we compute an weight- aggregate:
Sumpuct (Gr: G.)
Impact (2, (u), (w)) [2, E (G2)]
VV
Thus, token matches are weighted according to their learned structural importance rather than treated uniformly, enabling fine- tha-graiddd, query-sensitive retrieval over the inverted index.
Training Impacty Let Cyep and Coea be the relevant and non-relevant graphs for query Gq. Similar to Eq. 5 we encourage that Simpact (G., Gag) > SiG,; Gao) ) + y for ca E Cgo and co E Cyo, where 7 > 0 is a margin hyperparameter. As before, this leads to pairwise hinge loss to train tb: argmin
Σ Σ
[Simpaer (Gg: Gea) )
Simpace ( (G Geg) + 7]_-.
(10)
q CC bg ECg
Note that the networks described earlier, with parameters 0, Φ1, 62 are frozen before training the impact parameters v/. Unlike in classical inverted indices, impact weights are not associated with documents, or stored the index. Figure a) shows all the training steps of CORGII.
3.4 Query processing steps and multi-probing
At retrieval time, the query graph Gg is first embedded using the pretrained encoder E to obtain node embeddings Hq. The graph tokenizer GTNet then discretizes H, into soft binary codes Z and later hard binary codes 2, and Impact, computes impact weights (if used).
Each query graph token is used to probe the inverted index. Candidate corpus graphs are retrieved by aggregating impact scores across matching tokens. Graphs with eumulative relevance scores above a tunable threshold 5 form the shortlist:
(o) Ic C S (G.) 22)25,
(1))
where {unif, impact). Here, 8 controls the trade-off between the query time and retrieval accuracy. High 5 results in smaller size of R. (5), yielding low query time, whereas a low ō gives high query time. Note that, S. (G,: G.) is used only to obtain Rg Candidates in R. are further reranked using the pretrained alignment-based 'true" distance AGG,, G.) (T. Details are in Figure b).
Limitation of single probe per query node We have described how candidate corpus graphs are scored using uniform and impact-weigher aggregates. In both methods, each token (u) from the query resulted in exactly probe into the index. Preliminary experiments suggested that single

---

probe using each query token leads to lost recall, brought on partly by losing signal from continuous node alignment with Chamfer
bit-like node representations. and by replacing permutation-biee score. We must discover and exploit affinities between tokens while accessing posting lists.
In the of this section, we explore two means to this end. The first, Hamming expansion, has already been used in the literature on locality-sensitrv hashing. The second, co-occurrence expansion, a proposal novel CORGII.
Term weighting
Single Probe Hamming multiprohe (HM) Co-occurrence multiprohe (CM)
Uniform
Sunit
Suii (r ...)
Suit.M (b ...)
Impact
Simpact
SimpaciIIM (r
SimpacLCM (b ...) (CORGII)
Table 3: Possible combinations of term weighting and probing strategies. Default CORGII corre- sponds to Simpact.CM. r and b indicate Hamming radius for HM and number of tokens chosen for CM.
Hamming expansion multiprobe (HM) While exact token matches may be adequate when query and corpus graphs are locally near-isomorphic, discretization emrors and structural noise can cause relevant corpus graphs to be missed if no exact token match is found. To improve recall, we "smooth the boundaries of token bit encodings" by introducing lightweight token expansion mechanism: given a query token т E TT we probe the inverted index using not only but also nearby tokens within a Hamming ball of radius in the binary space {0, 10,1]D Given
and are the corresponding binary vectors of r, r' respectively, we write (, = [T' | z' || r). impact from is extended, by summing over the ball, to
Simpac. (Gg: Ge) EEE Σ
Impact (T. (w)) [T (G.)].
(12)
NEV, (E,.(2,()))
This expansion allows retrieval of corpus graphs containing approximate matches, mitigating the brittleness of hard discretization without requiring dense alignment. Hamming expansion has the potential to improve recall, but there risk of too many false positive candidates to eliminate through expensive scoring later.
Co-occurrence expansion multiprobe (CM) In classical text indexing, a token is sometimes characterized by the set of documents that mention it. Two tokens can then be compared by comparing their respective posting lists. A large overlap in these posting lists hints that the tokens have high affinity to each other. Adapting this idea to graph indexing can provide an alternative to Hamming- based affinity, which can be used either by itself, or in conjunction with Hamming- baasinggbassed token expansion.
For each query token E T, we identify additional tokens 7' whose posting lists overlap significantly with the posting list of r, ie., PostingTisstr)) Specifically, we define similarity score between tokens and r' as
(PostingLiss(() n PostingT.sst("")
sim(T,T')= Σr.et (oostnggist(r)) n PostingList(r.))
(13)
and expanded token set set No argmax sim(T, r'), where b is the number of similar tokens. Similar to Impacty, we overload the input notation for sim where necessary. Simpact from ( is then updated to aggregate over this expanded neighborhood, weighted by similarity:
EMmpae..M(Ge.. Gy) Σ
sim(r, 2,(1) Impact & (T, ha(u)) [ E (G.]] (14)
WEV, (E).
This way, corpus graph Ge can receive a non-zero score for a query node u. if any token 7 in the expanded set No N,,z,(()) appears in w(G.) - not just zy(u) itself. Table 3 lists different variants including CORGII.
Experiments
We assess the effectiveness of CORGII against several baselines real-world graph datasets and analyze the effect of different components of CORGII. Appendix G contains additional experiments.
Dataset We evaluate CoRGII on four datasets from the TU benchmark suite 41: PTC-FR,
PTC-FM, COX2, and PTC-MR, which are also used existing works on graph matching 10
Baselines We compare CoRGIT against six baselines as follows: (1) Noshier
(FHN) 42
It is an LSH for shift-invariant asymmetric distance, computed using distance spe-
7

---

CaRGG
TVF-iingl
IVP-mmld
DiskANN-muli
Randonn
0.18
0.49
0.56
0.18
000000
MA
0.36
0.37
0.12
0.36
0.21
0.24
0.28
0.21
0.12
0.25
0.12
0
0.25
0.75
0.5 0.75
0.12
0.25 0.5 0.75
k/C²
k/CC
k/C
k/C +
(a) PTC-FR
(b) PTC-FM
(c) COX2
(d) PTC-MR
Figure 4: Tradeoff between retrieval accuracy and efficiency for CORGII, FHN 42, IVF-single 25
IVF-multi (25], DiskANN-singe [29], DiskANN [29] and Random, 20% test queries all four datasets. Here, retrieval accuracy is measured in terms of mean average precision (MAP) and efficiency is measured as fraction of corpus graphs retrieved (k/C).
cific Fourier transform. takes single vector graph embeddings as a = Euev, (n/(w)/VV and ag = - he / V.J as input and builds LSH buckets for the corpus graphs C. (2) sin-single: is a variant of IVF (25.. used for single vector retrieval. Here, we build the inverted index using single vector dense corpus representations {a.} and perform retrieval by probing once with ag.
(3) IVF-multi: It is multi-vector variant of IVF [25], similar to [15] ColBert]. Here, we build the index over individual node embeddings from all corpus graphs, each tagged with its parent graph ID. During retrieval, we probe the inverted index with each query node embedding and aggregating the hits by the corresponding graph IDs. (4) DiskANN-singl (29]: It is graph-based ANN that uses HNSW index, over single vector representations. (5) DiskANN-multi [29]: It a multi-vector variant of DisKANN analogous to IVF-multi. Note that IVF and DiskANN typically support L2 or cosine distance. We report the results for the best performing metric. (6) Random: Here, we select top-k items from C uniformly random without replacement.
Evaluation Given the set of queries and the set of corpus graphs we split Q in 60:20:20 train (Qurain), dev (Qevv) and test (Qee) folds. For each query in Qress we retrieve the corpus graphs Rg that are marked relevant by the corresponding model. We rerank the retrieved candidates using the pretrained ranking model 1 For each ranked list, we compute average precision (AP) and average the AP values across test queries Quest to report on mean average precision (MAP). Given an accurate ranking model, MAP typically improves as the size of the candidate set R. increases- larger sets are more likely to hit most of the relevant items, whereas smaller sets may miss many them. To evaluate this trade-off between retrieval quality and efficiency, we measure MAP vs. the average size of the retrieved set, computed
Quall Enee... RRyl To generate this trade-off curve, for FHN, we sweep over its training hyperparameters to learn multiple hashcode variants, and vary the number of hash table buckets during lookup. The implementations of IVF and Disk accept as input. For these baselines, we directly vary ls to obtain the trade-off. Appendix F report the details datasets, baselines and evaluations.
We set D = 10, yielding the size of the vocabulary [7] = expanded token set set (2, (u)) used in co-occurrence based multi-probing (CM) in Eq. (14).
Hyperparameters
-220, 32 in the
4.1 Results
CoRGII baselines We first measure retrieval accuracy (MAP) and efficiency (inversely related to the fraction of corpus retrieved, k/C) across four datasets. Each curve shows how performance scales as the top-k retrieved candidates vary. Figure 4 summarizes the results. We make the following observations.
(1) CoRGII achieves the best accuracy-efficienge trade-offs among all methods. While FHN is the strongest among the baselines, CORGII shows particularly large gains in the high MAP regime. For example, the COX2 dataset, CORGII achieves MAP of ~0.50 at k/C 0.5, whereas FHN saturates around 0.35. (2) Across all datasets, CORGII achieves high MAP, very quickly at significantly lower retrieval budgets. For example, on PTC-FR, CoRGII attains MAP of ~ 0.36 by retrieving less than l = 33% corpus graphs, while most baselines require more than 75% of the corpus to match that level.
(3) Multivector variants of IVF and DiskANN outperform their single-vector counterparts, highlight- ing the benefit of retaining node-level granularity. However, they still perform poorly compared to
8

---

CORGII, largely due to their reliance on symmetric distance functions, which are unsuitable for subgraph matching - task inherently asymmetric in nature. Single-vector variants perform the worst, sometimes even below the Random baseline, due to both the coarse nature of single-vector representations and use of symmetric distance.
HM, CM. b-g probing 0.48-
HM. CM, h=22 (GaRGIT)
HM, CM, b-64
Benefits of co-occurrence based multipp Here, we analyze the effect of co-occurence based multiprob- ing (CM) strategy (14) by comparing it with a tradi- tional Hamming distance-based multiprobing variant (HM) TTable 2nd vs. 3rd column, second row).
MAP
0.36
0.37
0.24
0.24
Figure shows the results for HM and CM, with dif- ferent values r and b, and single probing strategy. We make the following observations.
0.5 0.7G
0.5 0.75
k/C +
k/C -
(a) PTC-FR
(b) PTC-FM
(1) Single probing fails to span the full accuracy-efficienne trade-off curve
Figure 5: Multiprobing: CM vs. HM
across all datasets. The retrieved set is noticeably sparse at k/C 2 0.50. These results highlight the necessity of multiprobing to achieve sufficient candidate coverage across varying levels of retrieval selectivity. (2) CM consistently achieves better trade-off than the corresponding variant of HM and single-probing strategy, while smoothly spanning the full range of retrieval selectivity. As b increases, its performance improves consistently but with diminishing gains, saturating beyond indicates that a moderate number of co-occurrence-bace bbased token expansions suffices to approach near-exhaustive token expansion performance. (3) HM retrieves broader range of candidates and spans the selectivity axis more effectively than the base impact score. However, as the Hamming radius r increases, the expansion becomes increasingly aaga-agnostic, ignoring semantic alignment from Impact.. This leads to degraded MAP at large r.
32. This
unif. HM (r=3)
imppact HM (em3)
Effect of impact weighting network Next, ana-
S unif CM (bm52)
impaact CM (b~82) (CoRGH)
lyze the effect of impact weight network, by comparing with the variants of our model for both co-occurrence
0.48
0.49
0.36
0.37
based multiprobing (CM, Eq. (14) and Hamming dis-
tance based multiprobing (HM, Eq. (22) This results in four models whose scores are SuMif,IIM. SImpact.IIM- Sunit,CM and Impact, (CORGII). Figure 7 summa- rizes the results. We observe that addition of impact weighting network improves the quality of trade-off, with significant performance gains observed for co-occurrence based multiprobing.
0.24
0.24
0.120
0.25 0.5 0.75
0.12
0.25 0.5
0.76
k/C -
k/C
(a) PTC-FR
(b) PTC-FM
Figure 7: Ablation on impact weight network
Siamese Asymmetric architecture As discussed in Section 3.1 GTNet employs an asymmetric network architecture, which enables exact token matching while capturing the inherent asymmetry of subgraph match- ing. Here, we investigate its benefits by comparing against a Siamese variant of GTNet, which shares the same MLP across query and corpus graphs. Figure 9 summarizes the results for both co-occurrence based multiprobing (Eq. (14) and Hamming based multiprob- ing (Eq. [2]) We highlight the following key observations: (1) The asymmetric variant of GTNeet consistently outperforms the Siamese variant for both HM and CM. The performance boost is strik- ingly high for CM. (2) When using the asymmetric network, CM gives notable improvements over HM. However, for the Siamese variant, CM performs poorly on both PTC-FR and PTC-FM, while HM also suffers significantly on PTC-FM. This contrast highlights the importance of architectural asymmetry, especially for effective co-occurrence- beaseeeeceeebaeed token matching.
Slammse (HM, r=))
Asymmettri (HM, r=]]
Stamese (CM, bwa2)
Asyimetrri (UM, ba33) (CoRGII)
0.48
0.49
0.36
0.37
0.24
0.24
0.12
0.25 0.5 0.75
0.12
0
0.25 0.5
0.7G
k/C +
k/C
(a) PTC-FR
(b) PTC-FM
Figure 9: Siamese vs Asymmetric architecture
Chamfer distance vs injective mapping Chamfer dis- tance provides non-injective mapping. Here, com- pare its performance against traditional graph matching distance with injective mapping, i.e., 1|, PZelli. where P is a soft permutation (doubly stochastic) ma- trix. Figure 10 shows that Chamfer distance outper- forms injective alignment-bann based graph matching. This
Chander (CM, b-32) (CoRGII)
Injective (CML b-32)
0.56
0.448
0.41
0.36
0.28
0.24
0.14
0.25 0.5 0.75
0.12
0.25 0.5 0.75
k/C -
k/C -
(a) COX2
(b) PTC-MR
Figure 10: Injective vs. Chamfer
9

---

100K
100K
100K
100K
60K
60K
60K
60K
20K
20K
20K
20K
01 25
50
75 100
0
25
50
75 100
25
50 75 100
01
25
50 75 100
Ptoken (T)
7
Proken
(T)
Proken (T)
Proken (T) 7
15
(Tolege
15
15
15
10
10
5
0
20K 60K 100K
20K 60K 100K
20K 60K 100K
20K 60K 100K
Pdoe (C) +
Pdocc (C) +
Pdoc (C) -
Pdoc (C') -
(a) PTC-FR
(b) PTC-FM
(c) COX2
(d) PTC-MR
Figure 11: Top row: Posting list length descending token rank. Bottom row: Number of unique tokens vs descending document rank. (uoken(T) represents the rank of the token t when sorted in descending order of posting list lengths. Pdoc (C) is the rank of the document C' when sorted in descending order of unique token count.
because injective mappings tightly couple corpus embeddings Ze with query embeddings Z preventing effective inverted indexing.
We rank each token in the vocabulary by the length of its posting list, Σ PostingList(77 in descending order. Similarly, we rank each document by the number of unique tokens contains, i.c., [Tokens(C))..
Token rank Document frequency
In the top row of Figure II we plot the posting list lengths tokens by rank. A small number of high-frequency tokens associated with nearly all documents in the whole corpus, while the vast majority tokens have short posting lists. The distribution exhibits a steep drop-off with rank, reminiscent of Zipfian pattern. Inverted indexes settings. In the second row, we plot the 'fill' of documents against documents ranked by their fills. A similar decay trend is observed, showing that most documents have small number of tokens with non-zero impacts. Appendix G.4 contains more results.
expected to be efficient in precisely these
Conclusion
We proposed CORGII, a scalable graph retrieval framework that bridges highly accurate late in- teraction query containment scoring with the efficiency of inverted indices. By discretizing node embeddings into structure-aware discrete tokens, and learning contextual impact scores, CORGII enables fast and accurate retrieval. Experiments show that CoRGi consistently outperforms several baselines. Our work opens up several avenues of future work. It would be interesting incorporate richly attributed graphs, capturing temporal dynamics in evolving corpora, learning adaptive token vocabularies, and exploring differentiable indexing mechanisms for end-to-end training. Another avenue is to integrate CoRGIl into large retrieval-augnnen auggmenedd systems that require structured subgraph reasoning at scale.
Acknowledgements
Pritish acknowledges funding from the Qualcomm Innovation Fellowship. Indradyumna acknowl- edges funding from the Google PhD Fellowship and the Microsoft Research India PhD Award. Abir acknowledges funding from grants given by Amazon and Google, and the Bhide Family Chair Endowment Fund. Soumen acknowledges funding from Amazon and IBM, and the Halepete Family Chair Fund.
10

---

References
[1] Bingqing Lyu, Lu Qin, Xuemin Lin, Lijun Chang, Jeffrey Xu Yu. Scalable supergraph search in large graph databases. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 157-168, 2016. doi: 10.1 10.1109//CDEE:201674483333
[2] Robert P Sheridan and Simon K Kearsley. Why do we need so many chemical similarity search methods? Drug discovery today. 7(17):033911, 2002.
[3] Xiang Ling, Lingfei Wu, Saizhuo Wang. Gaoning Pan, Tengfei Ma, Fangli Xu, Alex X Liu, Chumming Wu, and Shouling Ji. Deep graph matching and searching for semantic code retrieval. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(5):1-21, 2021.
[4] Justin Johnson, Ranjay Krishna, Michael Stark, Li-Jia Li, David Shamma, Michael Bernstein, and Li Fei-Fei. Image retrieval using scene graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8668-3678, 2015.
[5] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. International journal of pattern recognition and artificial intelligence, 18(03):265-29) 298, 2004.
[6] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprint AXXv:20077003092, 2020.
[7] Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sab- harwal, and Sayan Ranu. Greed: A neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, 2022.
[8] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference machine learning, pages 3835-3845. PMLR, 2019.
[9] Indradyumna Roy, Venkata Sai Velugoti, Soumen Chakrabarti, and Abir De. Interpretable Neural Subgraph Matching for Graph Retrieval. AAAI, 2022.
[10] Ashwin Ramachandran, Vaibhav Raj. Indradyumna Roy, Soumen Chakrabarti, and Abir De. Iteratively refined early interaction alignment for subgraph matching based graph retrieval. Advances in Neural Information Processing Systems, 37:77593-77629, 2024.
[11] Wei Zhuo and Guang Tan. Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems, 35:30181-30193, 2022.
[12] Aliaksei Severyn and Alessandro Moschitti. Learning to rank short text pairs with convolutional deep neural networks. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR *15, page 373-382, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450336215. doi: 10. 10.1145/2766462.277773
[13] Zhe Dong. Jianmo Ni, Dan Bikel, Enrique Alfonseca, Yuan Wang, Chen Qu, and Imed Zitouni. Exploring dual encoder architectures for question answering. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 1499419, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.18865///1 20053//v//0 /tt//22222emmmmppp main.640. https htt.lhttss//aaaaantolooo/o org/ 2022. mmmmlmmmmm..0//
[14] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6769- 6781, Online, November 2020. Association for Computational Linguistics. doi: 10. 18653/v 1/2020.cmma 550.
11

---

[15] Omar Khattab and Matei Zaharia. Colbert: Efficient and effective passage search via contextual- ized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pages 39 39-48, 2020.
[16] Gerard Salton. Modern information reirieval. McGraw-Hill, 1983.
[17] C.D. Manning, P. Raghavan, and H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. ISBN 9780521865715.
[18] Ricardo Baeza- Rates and Berthier Ribeiro-Neto. Modern Information Retrieval. ACM Press, 2nd edition, 1999.
[19] Otis Gospodnetic, Erik Hatcher, and Michael McCandless. Lucene in action. Simon and Schuster, 2010.
[20] Clinton Gormley and Zachary Tong. Elarth: The definitive guide: a distributed real-time search and analytics engine. O' O'Reilly Media, Inc., 2015.
[21] Jimmy Lin, Xueguang Ma, Sheng-Chieh Lin, theng-Hong Yang, Ronak Pradeep, and Rodrigo Nogueira. Pyserini: A python toolkit for reproducible information retrieval research with sparse and dense representations.
Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '21, page 2356-2362, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380379. doi: (0.1145/4448335.46622
[22] Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: A survey, arXiv preprint arXiv: 2927,927, 2014.
[23] Yu A Malkov and Dmitry Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824 836, 2018.
[24] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887-3896. PMLR, 2020.
[25] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library, arXiv preprint arXiv:2401.08281, 2024.
[26] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. Similarity search in high dimensions via hashing. In Vldb. volume 99, pages 518-529, 1999.
[27] Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman. Indexing by latent semantic analysis. Journal of the American society for information science, 41(:333 107, 1990.
[28] Christos Faloutsos and Douglas Oard. survey of information retrieval and filtering methods. Citeseer, 1995.
[29] Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, Andrija Antonijevic, Dax Pryce, David Kaczynski, Shane Williams, Siddarth Gollapudi, Varun Sivashankar, Neel Karia, Aditi Singh. Shikhar Jaiswal, Neelam Mahap- atro, Philip Adams, Bryan Tower, and Yash Patel. DiskANN: Graph-structured indices for scalable, fast, fresh and filtered approximate nearest neighbor search, 2023. URL https://githun com Mi Microsoft/// t/DiskANN
[30] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest. neighbor in high dimensions. Communications of the ACM, 51(1):117-122 2008
[31] Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the sorty-seventh annual ACM symposium Theory of computing, pages 793-801, 2015.
12

---

[32] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. Advances in neural information processing systems, 28, 2015.
[33] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint (KKY::/777.000433 2017.
[34] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approximate nearest neighbor search on high dimensional data experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering, 32(8):1475-1488 2019.
[35] Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, and Erik Waingarten. A near-linear time algorithm for the chamfer distance, 2023. URL arxiv .rg/ abs /t///3300000000
[36] Keshav Santhanam, Omar Khattab, Christopher Potts, and Matei Zaharia. Plaid: an efficient engine for late interaction retrieval. In Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pages 1747-1756, 2022.
[37] Thibault Formal. Benjamin Piwowarski, and Stéphane Clinchant. Splade: Sparse lexical and expansion model for first stage ranking. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages
2021.
[38] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
[39] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent per- mutations with gumbel-sinkhom networks. arXiv preprint arXiv: 1802.08600 2018. URL
/stps://arxiv.com
wwtpo//////////////oo/////e//w 1802. 08665. pdf
[40] Number of simple connected graphs on n unlabeled nodes. Online. URL httpstps::// /eei:. /A001349
[41] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.0866 2020.
[42] Indradyumna Roy, Rishi Agarwal, Soumen Chakrabarti, Anirban Dasgupta, and Abir De. Locality sensitive hashing in fourier frequency domain for soft set containment search. Advances Neural Information Processing Systems, 36:56352-56383, 2023.
[43] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed repre- sentations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
[44] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532-1543, 2014.
[45] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume (long and short papers), pages 4171-4186, 2019.
[46] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117-128, 2010.
[47] Vaibhav Raj, Indradyumna Roy, Ashwin Ramachandran, Soumen Chakrabarti, and Abir De. Charting the design space of neural graph representations for subgraph matching. In The Thirteenth International Conference on Learning Representations, 2025.
[48] Indradyumna Roy, Soumen Chakrabarti, and Abir De. Maximum common subgraph guided graph retrieval: late and early interaction networks. Advances in Neural Information Processing Systems, 35:32112-32122 2022.
13

---

[49] Eeshaan Jain, Indradyumna Roy, Saswat Meher. Soumen Chakrabarti, and Abir De. Graph edit distance with general costs using neural set divergence. Advances in Neural Information Processing Systems, 37:73399-73436 2024.
[50] Indradyumna Roy, Eeshaan Jain, Saswat Meher, Soumen Chakrabarti, and Abir De. Graph edit distance with general costs using neural set divergence. The Third Learning on Graphs Conference, 2024.
[51] Indradyumna Roy, Saswat Meher, Eeshaan Jain, Soumen Chakrabarti, and Abir De. Position: Graph matching systems deserve better benchmarks. In Forty-second International Conference on Machine Learning Position Paper Truck.
[52] Yu A Malkov and Dmitry Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824 836, 2018.
[53] Antonella Falini. A review on the selection criteria for the truncated SVD in data science applications. Journal of Computational Mathematics and Data Science, 5:100064, 2022.
[54] Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive data sets. Cambridge University Press, 2020.
[55] Sihao Yu, Jiafeng Guo, Ruqing Zhang, Yixing Fan, Zizhen Wang, and Xueqi Cheng. A re-balancing strategy for class-imbalanced classification based instance difficulty. In Pro- ceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 70-79, 2022.
[56] Jiaan Luo, Feng Hong. Jiangehao Yao, Bo Han, Ya Zhang, and Yanfeng Wang. Revive re- weighting in imbalanced learning by density ratio estimation. Advances in Neural Information Processing Systems, 37:79909-79934, 2024.
[57] Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, and Grigory Yaroslavtsev. Optimal sample complexity of contrastive learning. arXiv preprint arXiv:2312.00379, 2023.
[58] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. arXiv preprint 200::2000000000 2020.
[59] Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. Rocketqa: An optimized training approach to dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2010.08191, 2020.
[60] Luyu Gao, Zhuyun Dai, and Jamie Callan. Coil: Revisit exact lexical match in information retrieval with contextualized inverted list. arXiv preprint arXiv:2 104.07/86, 2021.
[61] Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint
2021.
[62] Jianmo Ni, Chen Qu, Jing Lu, Zhuyun Dai, Gustavo Hernandez Abrego, Ji Ma, Vincent Y Zhao,
Yi Luan, Keith B Hall, Ming-Wei Wei Chang, al. Large dual encoders are generalizable retrievers. arXiv preprini arXiv:21 2021.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claim that we have developed novel indexing and retrieval system for graphs over a latent vocabulary, with sparse binary codes. The rest of the paper provides experiments and data to corroborate these claims. Please see figure for an overview of the system, and section for results. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification:
We provide the limitations in Appendix section B
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification: We do not include theoretical results in this paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
15

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results. All the theorems, formulas, and proofs in the paper should be numbered and cross
referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide code, confgurraioosshyyepaaaanttter and instructions how to run our experiments in the supplementary. Additionally, we provide the hyperparameters to our experiments in the main paper. Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken
to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the link of these items.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https:/ htapss://nips... cc pub
lic/ lic/guides Soaaddes/oodeSuubisssioooooooo
for more details.
16

---

reproducible, they While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results, See the NeurIPS code and data submission guidelines (https /ttps..ccppbblleee cc.publicc/guii gww.g/udeeeeeee /CodeSubmi huti////giiiessoodeeuuuuiiiiii ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: These details are provided in the experiments section and will be included in greater detail in Appendix section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[No]
Justification: Error bars not required in experiments. This is because have provided scatter plots where each point represents data collected from the experiment run for separate configuration, for wide variety of configurations. That is, our plot data in the form of aggregates. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
17

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: These details have been provided in experiments. Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htte///euripppp ht.pp.ccppppppcpp wwtppblcccccccccccccccccccccctct /eeellicc//hiieeee Cttiiccuuelleneess [Yes]
Answer:
Justification: The research conducted follows the ethics guidelines laid out by NeurIPS. Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes],
Justification: Provided in Appendix A Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Justification: Our work does not pose such risks of misuse.
18

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have provided citations wherever possible any baseline dataset that we have used in this paper. We have also ensured license compliance.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide sufficient documentation for all our assets, including for e.g. code. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their
submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
19

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable). such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs not utilized in research in this work. Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer our LLM policy (https: (https://neurippsco /tt/unuuripp.ee hwtp://coooooooeeeeeeeeeeeeeeeee 2025 /LLM) for what should or should not be described.
20

---

Appendix
A Broader Impact
Graph retrieval is a key enabler in many real-world domains where structured relationships are central. Our work on CoRGII contributes subgraph-basee retrieval, offering benefits across a range of applications:
Drug discovery and molecular search: Efficient subgraph containment enables rapid screening of compounds containing functional motifs, aiding in virtual screening pipelines.
Program analysis and code intelligence: Retrieval over control-flor or abstract syntax graphs can improve vulnerability detection and semantic code search.
Scene understanding and vision-language systems: Graph-based representations of scenes or object relationships benefit from scalable matching of structured queries.
Scientific knowledge extraction: Structured retrieval over citation concept graphs supports discovery in large corpora of scientific knowledge.
By enabling fast and accurate retrieval of graphs under substructure containment, our work has the potential to improve the scalability and responsiveness of systems that rely on structured search over large graph collections. The proposed method, CORGII, contributes toward democratizing structure- aware search by bridging discrete indexing methods with neural representations, making such systems more accessible to low-resource settings where dense model inference may be prohibitive.
While CoRGII offers efficiency and interpretability advantages, like any retrieval system, it may raise concerns when applied to sensitive haaph-strutturd data-such as personal social networks or proprietary molecular datasets pornsstt--otentiallly risking privacy or intellectual property leakage. Moreover, since training relies on learned embeddings, there remains a possibility of inherited biases from the underlying data. Practitioners are advised to apply appropriate safeguards, including privacy- preserving techniques and fairness auditing, when deploying the system in sensitive domains.
B Limitations
While CoRGII demonstrates strong performance in scalable graph retrieval, several aspects offer room for further improvement. We outline them below as avenues for future exploration:
Static token vocabulary: Our framework relies fixed latent vocabulary defined by binary token length. Learning adaptive or dynamic vocabularies could improve representation flexibility and efficiency.
Lack of support for attributed heterogeneous graphs: CoRGII currently operates on purely structural information. Extending the framework to incorporate rich node/edge attributes and
heterogeneous graph types is a natural next step.
Limited handling of evolving corpora: The inverted index assumes a static corpus. Incorporating apdate-friendly indexing or continual learning mechanisms would enable deployment in dynamic settings, such as codebases or scientific repositories.
Addressing these limitations can further improve the adaptability, expressivity, and deployment readiness of CORGII in diverse graph-based retrieval settings.
C Clarifications
In this section, we provide few clarifications follows.
Sparse vs dense representations. In text retrieval, a "sparse" index is keyed on discrete tokens. Sparse text indexes inverted posting lists [7), in which the number of document (IDs) is vastly smaller than the corpus size, hence the name "sparse". In contrast, in a "dense" text index (25 26
34, text encoder converts text into continuous vectors and then they are indexed. Such dense representations are used for IVF, LSH (e.g., FHN) or DiskANN. Dense indexes are larger and slower to navigate than inverted indexes.
29 30
31
32
Latent token structure and token collisions. The latent vocabulary structured in the form of posting list matrix PL E {0, 1) 1021x 1021x100K 100K Each row of this matrix represents a token and each column a corpus item. The tokens themselves are not interpretable as they usually are in text indexing. However, the expectation from our pipeline and training scheme is that distinctive
21

---

subgraph motifs will be mapped to the same or strongly correlated groups of tokens. It is possible that different nodes from different graphs are mapped onto the same latent token. based on initial dense representation characteristics. This is further expanded upon in Appendix G.4
D Related Work
D.1 Brief History of Text-based Retrieval Architectures
Early information retrieval (IR) systems for text, relied on sparse lexical matching using pag-of-wordd (BoW) representations. Documents were encoded as high-dimensional sparse vectors over fixed vocabulary, with inverted indices mapping each term to its corresponding document sets. Statistical term-weight oerm-weighting schemes like TF-IDF and BM25 were used estimate relevance, prioritizing terms that were both frequent within document yet discriminative across the corpus. Decades of research culminated in highly optimized sparse retrieval systems, such as Lucene [19 and Elasticsearch (20] which remain industry standards for lexical search.
Despite their efficiency, lexical methods are fundamentally limited by their reliance on surface-level token matching, failing to capture deeper semantic similarity. To address this, dense neural IR models were proposed, using learned embeddings-initially static (e.g.. Word2 [43] Glo'ee 44) and later contextual (e.g.. BERT [45))- to encode text into compact, low-dimensional vector spaces that support semantic retrieval. As these dense representations are incompatible with inverted indices, retrieval relies on Approximate Nearest Neighbor (ANN) search techniques such as LSH (22), HNSW (23 and IVF 46). with efficient implementations provided by libraries like FAISS
25 and ScaNN
Early dense retrieval systems typically compressed entire texts into single-vector representations, but this proved suboptimal for longer inputs due over-compression, which obscures token-level distinctions. This limitation motivated a shift toward multi-vector representations, which preserve token-level information and enable more precise semantic alignment. Architectures such as Col- BERT [5] and PLAID (36] adopt late interaction mechanisms that allow scalable token-wise retrieval. However, these methods still rely on ANN search as a subroutine, which despite its effectiveness in dense settings is slower than inverted indexing in practice.
To bridge the gap between dense semantic modeling and efficient retrieval, recent work has revisited sparse representations through a neural lens. Sparse neural IR models seek to combine the semantic expressiveness of dense models with the scalability and efficiency of traditional inverted indices. Approaches like SPLADE (37] learn document-speccffe inputs onto a high-dimeeniooal vocabulary space. Crucially, this space is not limited to surface-level input tokens; the model can activate latent or implicitly relevant terms through learned expansions, effectively enriching the document representation beyond what is explicitly present in the text. This allows for crmantically-nnormme exact matching within classical IR frameworks, effectively narrowing the gap between dense retrieval and sparse indexing.
weighted sparse vectors by projecting
D.2 Briefer History of Neural Traph-Containmen Scoring Models
Graph containmentt whether a query graph Gg is (approximately) embedded within a corpus graph G long been a central problem in graph-based search. Traditional methods rely on combinatorial algorithms and subgraph isomorphism solvers, which are computationally expensive and scale poorly to large graph corpora. To address this, recent neural methods propose differentiable surrogates for containment using graph neural networks (GNNs). Raj et al. 47 provides a comprehensive analysis on different design components of neural models for subgraph isomorphism.
NeuroMatch [6] introduced a Siamese GNN with a hinge loss over aggregated node embeddings, but its global pooling loses fine structural detail. IsoNet [9] addresses this by retaining node-level embeddings H q. H computing soft alignments via a Gumbel-Sinkhorn network to produce doubly stochastic matrix P, and scoring relevance using an asymmetric hinge loss [H better models subgraph containment and achieves improved empirical performance. IsoNet++ [IO] extends this with carly-interaction message passing for richer local-global representation. However, both IsoNet and IsoNet++ require dense, pairwise alignment across the corpus, limiting scalability. use similar approaches for other type of graph similarities. Other recent works, such as g. model graph similarity via node-level interactions using matching networks or soft attention. While these approaches capture structural alignment to some extent, they are tailored for general-purpose similarity tasks, making them less suited for subgraph containment and less scalable to large graph corpora.
PH This
48
40 50
22

---

E Additional details about our model and training
E.1 Pre-trained backbone
We use Isonet [9] for final scoring mechanism. IsoNet has two components: (1) a GNN and (2) permutation network. GNN comprises of feature initialization network F1; a message computation network F2 and an embedding update (or combination) network F3. Specifically, for the query graph Gg. we execute L mesage passing layers as follows:
o = Fi (Feature(u))
for all u E Vg
(15)
hg. (u) F3 hn
Σ I((,,))E
F2(hnn((u),, Mys(()))))) for all u Vq, k E (0, I 1}
(16)
We use the same procedure to compute the embeddings he.k for corpus graphs. We collect these em- beddings in H H. E R.mxdimm, These embeddings are finally used fed into multilayer perceptron, followed by dot product, obtain an affinity matrix MLP ,,) (MLP(H.) which is then provided
as input into node alignment network to obtain P. Given a temperature hyperparameter temp, this network outputs a peff-permutation matrix using Sinkhorn iterations 38
P Sinkhorn (MT. M.. /temp)
(17)
Gumbel-Sinkhond network consists of iterative row-column normalization as follows:
Po exp(MLP(H,) MLP(H.) /temp)
(18)
P++1 RowNormalize (ColumnNormalize(PP.)
S l S 7 11
(19)
As T + 0o Pr approaches as doubly stochastic matrix and as temp + 0, T - oc, the matrix Pr approaches permutation matrix.
In our work, we set dim,- = 10. Here, Fj is 10-dimensional encoder; F2 consists of a combination of propagator layer with hidden dimension of 20 and GRU layer the output, with final dimension 10: and F'3 consists of an aggregator layer with hidden dimension 20 and output dimension 10. The MLPs used in Sinkhorn network, are Linear-ReLU--ineee networks. Each MLP has hidden layer of 25 dimensions, and the output is of 25 dimensions. Finally, we minimize the ranking loss to obtain the parameters of F1, F2 and F's (Eq. [15) (6)); ) and MLP used in Eq. (19)
ΣΣ Σ G0 EC CD ECEO
|A Geg) - AGG Geg) + Margin
(20)
We used a margin of 0.5. Note that A is only used in the final stage of ranking. In Sinkhorn network, we set the number of iterations T 10 and temparature 0.1.
E.2 Details about CORGII
Architecture of GTNet and Impact,, The GNN in GTNet consists of same architecture as in Eqs. [15) (16), with the same number of layers and hidden dimensions. Here, we set dim(x.) (x.) = 10. Each of the MLPs in GTNet, i.e., MLP MLP&, in Eqs. (2) and (3) consist of a Lincar-ReLU-lingg network with input dimension 10, hidden layer of size 64 and output dimension 10. Note that GTNet does not share any components with the pre-trained backbone.
MLP e used in Eq. (8) model the impact scorer admits similar architecture MLP & MLP des It consists of a ReU---ea network with input dimension 10, hidden layer of size 64 and output dimension 10.
Optimization and Early Stopping. We train both models using the Adam optimizer with learning rate of 1 x 10- and batch size of 3000. During GTNet training, early stopping is performed at the sub-epoch level (i.e., across batches) with a patience of 30 steps and validation every 30 steps. For Impact,, early stopping is applied at the epoch level with maximum of 20,000 epochs and patience set to 50. Validation is conducted every epoch, with default tolerance threshold of 5 x 10-3, In both cases, the model is evaluated using the score function aligned with its training objective.
Margin Hyperparameter Tuning. For the baamfer-based ranking loss in Eq. (5) we experiment with margin values of (0.01, 0.1, 1.0, 10. 30). The best-performing margins are for PTC-FR and PTC-FM, and 30 for COX2 and PTC-MR. For the impact network loss in Eq. 10 tested margins
23

---

include (0.01,0.1,1.0) Margins of 0.01, 0.01, 1.0, and 0.1 work best for PTC-FR, PTC-FM, COX2, and PTC-MR, respectively.
Training Under Co-Occurrence Expansion. During training with co-oceurrence multiprobing. the token neighborhood (2, (1)) in Eq. (14) is replaced with the full vocabulary T. This allows Impact, to learn a relevance- aware importance score for every token, At retrieval time, top-b tokens selected based on sim, using the learned impact scores.
Reproducibility. All experiments are run with fixed random seed 42 across libraries and frame- works. We leverage PyTorch's 's deterministic execution setting and CuBLAS workspace configuration to ensure reproducible execution.
F
Additional details about experiments
Dataset
Vil(
max([Vel)
E
min(
max (Ec|)
E[ ||
PTC-ER
16
25
18.68
15
28
20.16
PTC-FM
16
25
18.70
15
28
20.13
COX2
16
25
19.65
15
26
20.23
PTC-MR
25
18.71
15
20.17
(a) Corpus graph statistics.
Dataset
min((Vo))
max((Vo))
B[[V
min( (EQ))
max((Eol)
B[
y-1
PTC-FR
15
12.64
6
15
12.41
0.11
PTC-FM
7
15
12.58
7
15
12.34
0.12
COX2
6
15
13.21
6
16
12.81
0.11
PTC-MR
6
15
12.65
7
15
12.41
0.12
(b) Query graph statistics and average positive-to-negative label ratio (El y= D)
Table 12: Statistics of sampled subgraph datasets used in our experiments, Each dataset consists of 500 query graphs and 100,000 corpus graphs.
F.1
Datasets
All experiments are performed on the following datasets: PTC-FR, PTC-FM, COX2 and PTC-
MR [1. From each dataset, we extract corpus and query graphs using the sampling procedure outlined in (9), such that |C] = 100000 and [2] = 500. The queryset is split such that Iuuaia = 300, [Qav| 100 and Quell 100. Each dataset has its relevant statistics outlined in Table including the minimum, maximum and average number of nodes and edges in both the corpus set and the queryset. Additionally, the table also lists the per-query average ratio of positive ground truth relationships to negative ground truth relationships.
F.2 Baselines
We provide a detailed description of cach of the baselines used in our experiments.
FourierHashhNet It is Locality-sensitive Hashing (LSH) mechanism designed specifically for the set containment problem [42], applied subgraph matching. particular, overcomes weaknesses of symmetric relevance measures. Earlier work employed measures such as Jaccard similarity, cosine similarity and the dot product to compute similarity between pair of items, which do not reflect the asymmetric nature of the problem. FHN, the other hand, employs hinge- distance guided dominance similarity measure, which is further processed using a Fourier transform into the frequency domain. The idea is to enable compatibility with existing fast LSH techniques by leveraging inner products in the frequency domain, while retaining asymmetric notion of relevance.
We adopt the original architecture and training settings of FourierHashNet 42 without modification. The model employs 10 sampled Fourier frequencies to compute learned asymmetric embeddings, which are then optimized using binary cross-entropy loss over embedding vectors of dimension 10. The final hash representation consists of 64-bit codes. For training, we perform full grid sweep over the hyperparameter configurations proposed in the original work, including all specified loss weights.

---

To study the trade-ofi off between retrieval accuracy and index efficiency, we vary the number of hash table buckets at query time, ranging from 2' 2
The FAISS library provides facilities for inverted file indexing (IVF) [25]. IVF clusters the corpus of vectors using a suitable quantization method. The quantization method produces centroid vectors for each corpus vector, and each centroid represents cluster. Internally, the library stores the vectors assigned to each cluster the form of (possibly compressed) contiguous postings lists. To search this construction, a query vector is transformed into its corresponding centroid to match with the given cluster. Depending on the number of probes argument given during search time, one may expand their search into multiple neighboring clusters. We implement single-vector and multi-vector variants of IVF.
IVF
Note that we use the faiss. IndexFlatIP as the quantizer and faiss. IndexIVFFlat as the indexer.
DiskANN To tackle the challenge of having to store search indices in memory for strong recall, DiskANN introduces efficient SSD-resident indices for billion-scale datasets (29]. To this end, the authors develop a graph construction algorithm inspired by methods such as HNSW [2) but which produce more compact graphs (smaller diameter). They construct smaller individual indices using this algorithm on overlapping portions of the dataset, and then merge them into single all-encompassing index. These disk-resident indices can then be searched using standard techniques. One of the key benefits of DiskANN is that it requires modest hardware for the construction and probing of their disk-resident indices. We implement single-vector and multi-vector variants. Note that we against the memory-resident version of DiskANN.
We employ a graph degree of 16, complexity level of 32, alpha parameter of 1.2 during indexing. During search, we use an initial search complexity of 221
F3 Evaluation metric
We report Mean Average Precision (MAP) and the average number of retrieved candidates to characterize the efficiency-accuracy tradeoff. Retrieved candidates are reranked using the pretrained alignment model for consistent evaluation. For query q with relevant corpus set Cyg and retrieved ranking T we define the average precision (AP) as
Prec@r (r),
(21)
C
where (rl, E {0, 1} indicates whether the r-th ranked item is relevant to y and Prec@r is the precision at rank r. MAP is the mean of AP over all queries. This formulation penalizes high precision with low recall, ensuring models are rewarded only when most number of relevant items are retrieved with high retrieval accuracy.
F,4 System configuration
All experiments were conducted on an in-house NAS server equipped with seven 48GB RTX A6000 GPUs respectively. All model training is done on GPU memory. Further, the server is equipped with 96-core CPU and maximum storage of 20TB, and runs Debian 1. We found that this hardware was sufficient to train CORGII.
E.5 Licenses
Our code will be released under the MIT license. DiskANN, FAISS and FourierHashNet are all released under the MIT license.
25

---

G Additional experiments
We present additional experimental results covering the comparison between co-occurrence-busee multiprobing (CM) and Hamming multiprobing (HM), the ablation study on the impact scorer Impacty, and the effect of using Siamese versus asymmetric architecture in GTNet. We also include supporting analyses on posting list statistics such as token frequency distributions and posting list co-occurrence patterns as well as extended results for various CoRGII variants.
G.1
CM vs HM
Figure
in the main paper compares co-occurrence multiprobing (CM) with Hamming multiprobing (HM) on the PTC-FR and PTC-FM datasets. Here, we present additional results on the COX2 and
5
PTC-MR datasets.
Figure 13 confirms that CoRGII remains the best-performing method overall, though the gap between CM and HM narrows on PTC-MR. (1) On COX2, HM fails to sweep the entire selectivity axis; with 7, it only reaches up k/C 0.6. (2) CM steadily improves with increasing b. approaching exhaustive coverage, and saturates beyond b = 32. (3) On PTC-MR, while the difference between HM (r 7) and CM (b 32) less pronounced, HM still does not cover the full selectivity
range. (4) The trends and conclusions drawn in Section 4.1 remain consistent across these datasets.
HM,
HMM, r=3
HM,
CM, 8-8
CM, b=32 (CoRGII)
CM, b-64
Single-probing
0.48
0.49
MAP
0.36
0.37
0.24
0.24
0.12
0.5
0.75
1
0.10
0.5
0.75
k 4/C-
+
k/C +
(a)
PTC-FR
(b) PTC-PM
0.56
0.48
MAP
0.42
0.36
0.28
0.24
0.12
0.5
0.75
1
0.15
0.5
0.75
k C/C- +
k/C +
(c) COX2
(d) PTC-MR
Figure 13: Comparison of Hamming expansion multiprobing (HM) against co-occurrence expansion multiprobing (CM) across four real-world datasets and across several values of (Hamming ball radius) and b (number of topmost co-occurring tokens). Each plot consists of tradeoffs between selectivity (k/C) and MAP, for different values of and b. b = 32 is sufficient for CM to outperform HM variants. To deal with the crowding and overlapping problem in the plots, have applied point sub-sampling on CORGII.
26

---

G.2 Impact weight network ablation
Figure 7 in the main paper examines the impact of the weighting network on the PTC-FR and PTC-FM datasets, We now extend this analysis to COX2 and PTC-MR in Figure [4 with the following observations: (1) CoRGII continues outperform all other variants across the full retrieval budget spectrum on both datasets. (2) On COX2, uniform aggregation with Hamming multiprobing (HM) briefly approaches CoRGII low k k/C values, but quickly falls behind as selectivity increases. (3) Removing impact weights causes a significant drop in CM performance across both datasets, underscoring the value of learned token-level importance. (4) Uniform aggregation under CM fails to deliver competitive trade-offs, confirming that context-aware impact scoring is essential for effective retrieval.
S unif, HM (r=3)
impaact HM (r=3)
S unif, CM (b=32)
impact, CM (b=32) (CoRGIT)
0.48
0.49
MAP
0.36
0.37
0.24
0.24
0.12
0.12
0
0.25 0.5 0.75
0.25 0.5 0.75
k/C
k/ C +
(a) PTC-FR
(b) PTC-FM
0.56
0.48
00G0 1EA0
MAP
0.42
0.36
0.28
0.24
0.14
0.12
0
0.25 0.5 0.75
0
0.25 0.5 0.75
k k/C +
k/ B/C -
(c) COX2
(d) PTC-MR
Figure 14: Effect of ablation on the impact weight network across four datasets. Each subplot com- pares four retrieval variants: uniform aggregation with Hamming multiprobing (Sunif, HM), uniform aggregation with co-occurrence multiprobing (Sunit, cM). impact-weighted Hamming multiprobing (Simpaa, HM), and weight- co-occurrence multiprobing (Simpuc, CM, the default CORGIT).
27

---

G.3 Siamese vs Asymmetric networks
Figure the main paper analyzes the contribution of CoRGIl's asymmetric architecture on the PTC-FR and PTC-FM datasets. Figure 15 complements this analysis with results on COX2 and PTC-MR.
We observe: (1) CoRGIl consistently outperforms both Siamese variants (with CM and HM probing), reaffirming the importance of architectural asymmetry for subgraph containment. (2) Among the HM variants, the asymmetric network achieves better tradeoff curve compared to the Siamese counter- part, particularly evident in the mid-selectivity range. (3) Despite this, HM-based variants-both asymmetric and Siamese-fail to span the full selectivity axis, highlighting the limitations of Ham- ming multiprobing for recall. (4) These results further validate the need for asymmetry in the encoder architecture to accurately reflect containment semantics under both probing schemes.
Siamese (HM, r=3)
Asymmetric (HM, r=3)
Siamese (CM, b=32)
Asymmetric (CM, b=32) (CoRGII)
0.48
0.49
MAP
0.36
0.37
am
0.24
0.24
0.12
0.12
0
0.25
0.5 0.75
0.25 0.5 0.75
k/C >
k/C +
(a) PTC-FR
(b) PTC-FM
0.56
100000000000
0.48
10000000000
MAP
0.42
0.36
0.28
0.24
0.14
0.12
0
0.25
0.5
0.75
0.25 0.5 0.75
k k/C +
k k/C C +
COX2
(d) PTC-MR
Figure 15: Ablation comparing Siamese and asymmetric network architectures under different
probing strategies. Each variant combines one of two network architectures Siaamesstrrss-Simesee for query and corpus) and Asymmetric (separate MLPs)-wind one of two probing strategies: HM (Hamming multiprobing with radius = 3) or CM (Co-occurrence multiprobing with b 32). CORGII corresponds to the Asymmetric + CM configuration, shown as black circles.
Siamese (shared MLP
28

---

G.4 Insights into token co-oecurrence
Drawing parallels from natural language and retrieval systems, the structure of posting lists and corresponding token co-occurrence statistics are of key interest. In this section, we examine how these properties vary across datasets.
Co-occurrence statistics Table 16 reports structural statistics of the posting list matrix across all datasets. Let the posting list matrix be PL {0, 1011122x0000 where each represents a token and each column a document. The corresponding co-occurrence matrix is defined as C PL PLT E 2 11024x1024
We list both the actual rank and the effective rank of PL, the latter computed using the energy- preserving criterion from truncated singular value decomposition (SVD) [53] (4). Let 01...... On K
denote the singular values of PL. The effective rank is the smallest K such that with 7 0.95. Since rank(PL) rank C) but rank (PL) serves an informative upper bound for that of C.
Eis o0
(PL) 2 rank" (C), the effective rank of PL
The large gap between the actual and effective rank across datasets partilulary the low effective mank-indicater that token co-occurrences lie on a low-dimensional manifold. This suggests that both PL and C are highly compressible, enabling projection onto a lower-dimensional subspace without significant loss information. This again resembles the behavior of text corpora, where the discrete word space may be in the tens hundreds of thousands, but few hundred dense dimensions suffice to encode words and documents [27]
Dataset
Actual Rank
Effective Rank
PTC-FR
393
PTC-FM
498
COX2
250
PTC-MR
232
3
Table 16: Actual and effective rank (95% SVD energy threshold) of the posting list matrix PL for each dataset.
29

---

G.5 End-to-End Training vs Frozen Backbone for Sunit, CM and Sunit, HM
key design consideration is whether GTNet benefits from end-to-end training using its own GNN encoder, or whether comparable results can be obtained using frozen embeddings from a pretrained backbone. Figure compares the performance of Sunif, CM and Suiit, HM under both configurations.
We observe that: (1) End-to-end training consistently yields better Mel-stlectivtt tradeoffs for both CM and HM variants, indicating that learning task-specific embeddings improves token discrim- inability. (2) The frozen backbone variant spans a wider range of selectivity values (k/C), suggesting looser token matching and higher recall, but at the cost of reduced precision. (3) End-to-end models tend to retrieve fewer candidates for the same threshold, reflecting tighter, more precise tokenization.
Sunif. HM (e=3) (end-to-end)
Sunif, HM (rm3) (pre-trained)
Suntf, CM (b=32) (end-to-ond)
Sunff, CM (b=32) (prestrained)
0.56
0.56
MAP
0.42
0.42
0.28
0.28
0.14
0.14
0.25
0.5 0.75
0.25 0.5 0.75 k //C +
k/
C +
(a) PTC-FR
(b) PTC-FM
0.56
0.56
MAP
0.42
0.42
0.28
0.28
0.14
0.14
0
0.25 0.5 0.75
0
0.25 0.5 0.75
k/C
k/C²
(c) COX2
(d) PTC-MR
Figure 17: Comparison of end-to-end training versus using frozen backbone for Sunit, CM and Sunit, HM. with 3 and = 32. End-to-end training refers to learning the GTNet encoder jointly, while the frozen variant reuses pretrained embeddings.
In the next set of ablations, we show that the impact network does not need pre-trained IsoNet embeddings of the given dataset to maintain superior tradeoffs.
G.6 Using pre-trained IsoNet embeddings of different dataset as input to Impact.
Instead of using pre-trained IsoNet embeddings h on the same dataset, we use h trained on the PTC-FM dataset as input to the impact network for PTC-FR, and likewise use trained on PTC-MR and apply the impact network for COX2. Table 18 shows the efficiency in terms of fraction of graphs k/C' retrieved to achieve atleast a certain MAP=m* Lower k/C' is better and indicates higher efficiency. denotes places where the method is unable to achieve the target MAP.
G.7 Using intermediate embeddings of GTNet input to Impact..
Next, instead pre-trained embeddings h, we use x as input to the impact scoring model (Impact, (T, x)), (8), where is the embedding from the GTNet GNN, (which is not pretrained and trained as part of the CORGII scheme).
The following Table 19 shows the efficiency in terms of fraction of graphs k/C retrieved to achieve atleast a certain MAP=m for PTC-FR (first subtable) and COX2 (second subtable) datasets. Lower k/C is better and indicates higher efficiency.
30

---

CORCII
FHN
IVF
current
(h trained on PTC-FM)
default
(A trained on PTC-FM)
default
(h trained on PTC-FM)
0.38
0.38
0.42
0.51
0.97
0.76
0.81
0.40
0.44
0.47
0.81
1.0
0.89
0.81
0.45
0.645
0.69
0.99
1.0
0.96
0.91
(a) k/C values for PTC-ER.
m
CORGH
FHN
IVF
current
(h trained PTC-MR)
default
(h trained on PTC-MR)
default
(h trained on PTC-MR)
0.36
0.31
0.27
0.61
1,0
0.64
0.57
0.38
0.35
0.29
0.71
0.64
0.81
0.40
0.45
0.99
0.83
0.81
(b) k/C values for COX2.
Table 18: k/C values comparing CORGII, FHN, and IVF with and without transferring across datasets. CoRGII outperforms the baselines even when the pre-trained h of different dataset is used.
172
CoRGH
FHN
DistANN-muli
IVF-multi
(current)
(use z]
0.57
0.4
0.44
043
0.81
0.87
0.45
0.64
0.62
0.99
0.93
0.96
(a) k/C for PTC-FR.
CoRGH
PHN
DiskANN-multi
IVF-mult
(current)
(use x]
0.64
0,38
0.35
0.48
0.71
0.82
0.64
0.42
0.45
0.58
0.99
0.82
0.3
(b) k/C for COX2.
Table 19: k/C values comparing CORGIT (current vs. using r), FHN, DiskANN-muli, and IVF-multi. CoRGII outperforms each of the baselines even when not using h as impact network input.
G.8 Using pre-trained Graph Embedding Network embeddings as input to Impact,
We pre-train different model called Graph Embedding Network (GEN) g which is different from the final reranking model. Table 20 contains the results, with denoting places where the method is unable to achieve target MAP:
Ours (prvirained GEN-mbbed.)
DiskANN-mali (pritesiieed GRN-mbbdd))
-mulli (pestraiond GRN-mbedd
(currvad)
(current)
(pretrained GEN-mbbed)
(curmot))
(curman)
0.38
0.38
0.88
0.51
038
USC
0.45
0.64
0,65
0.99
893
095
0.96
0.4
(a) k/C for
(currved)
(pedrainudl (ENembbrl))
(current)
(pretrained GFNembbul)
(curmnt)
(pritisined GRN-mbbdd)
(curmet)
(pntrrinnd GEN-mmbed)
0.30
0.31
0.25
0.1
0100
0.55
0.6
U.64
0.55
(b) K/C for COX2.
Table 20: k/C values comparing CORGII, FHN, DiskANN-multi, and IVF-multi models under both current and pretrained GEN-embedding settings. CORGIT outperforms other methods when the impact network is not conditioned on pre-trained IsoNet embeddings.
31

---

G99
Estimating the error of the Chamfer approximation
Final recall computation requires impact scoring and multiprobing. It would useful to gauge the effect of the Chamfer approximation before getting to that stage. Towards this goal, provide the following error-based estimator to evaluate the efficacy of the Chamfer approximation without measuring recall.
We compute ground-truth distance dist.. distance distanf under soft permutation, and Chamfer distance distchamfer (see Equation 4):
dist
min
Σ A - PA.PT [i.5]]
],
{.j
distsoft
Σ w
Zy
psoft
Ze
|i,
The following Table 21 shows that dist is better approximated by distchanfer than by dist
Dataset
Average( dist distson:))
Average( dist* distcchamfrr)
PTC-FR
26.9
20.18
PTC-FM
35.42
22.53
Table 21: Chamfer better approximates dist" (lower is better).
H
Further discussion
In this section, we include further material of interest. Specifically, we include index memory and timing statistics for our method, discussion on the generalizability of our impact scorer and discussion on the sample complexity of contrastive learning.
H.1 Index memory and timing statistics
In the Table 22 below, we report index construction time and memory usage, both of which remain modest and practical across datasets, supporting the scalability of CORGII. Further, observe that indexing of CoRGII on the PTC-FR dataset takes 46M and 272s for million graphs. which is quite modest.
Dataset
Indexing time
Index memory
PTC-FR
29s
3.6M
COX2
27.2s
4.3M
Table 22: Index construction time and memory usage for CoRGII.
H.2 Discussion on generalizability of impact score function
Below, we discuss the effect of node types that may occur very infrequently in the corpus, and whether there may not be sufficiently many samples to guarantee good generalization of the learned impact score function Impact...
We emphasize that even if there are such rare graphs, we train the impact scorer using ranking loss on the aggregated ranked list. Suppose we have relevant query-corpus pairs G, and Go. each with rare tokens. During the batching procedure, our ranking loss ensures that S(G Ge) > S(G Ge) whenever G. and Ge are not relevant, including for graphs that have richly contextualized tokens. This allows the training algorithm to reinforce a strong enough signal into the impact scorer. If we use 5(Gg. Ge) as the sole scoring function, then we obtain modest MAP z 0.28 even S is not any graph-matching model and is driven by a simple MLP.
This can be further enhanced by using the following modification of the impact scores:
Σ Impact,/ (w), hy (2) E w(G)) V
Σ
A Almpact (2, (u). by (u)) [2 (u) e w(G))
aEV,
Here, À is hyperparameter greater than I and is only applied if (u) is rare token.
32

---

H.3 Discussion sample complexity of contrastive learning
Here, we discuss the sample complexity of the contrastive learning methods that we have employed to train our pipeline (especially the impact scorer). in the context of relevant past work. Consider the resampling or re- ee-bllancing algorithm proposed in [55] each iteration t, we may use a sampling procedure, formulated as multinomial distribution Multinomial(D") over all corpus items (with CT) over difficulty estimates D of tokenizing the graphs arising due to presence of rare tokens. Then, we re- trairain or fine-tune the tokenizer GTNet on graphs sampled from this distribution. In this case, we can compute predictions of tokens as 2(() (u) for each node u. Then, we leverage the prediction variations z²() (u) ((t11)(u (u) (and their signs) to compute difficulty for each node. Then, we can aggregate these difficulty values across nodes compute difficulty D for Ge- We can also compute
D' [
Impact (w), (u)) (2)(u) E wGG)) VEV
Σ
Impact, by (u)) (1) E (G.))
WEV,
as proxy difficulty per node. This would be a more principled alternative to our proposal in Section H.2 involving X.
Next, the paper [56] assigns suitable weights a(x, y) on the loss per each instance. It would be an interesting research problem to design a (=z(u,, Ge) similar to [56]. key challenge in immediately adapting [56] is that we may need to estimate P(Ge 2(u)) as used in Eq. (2) in [36), which would
pose an interesting research question.
Discussion of Alon et al. [57] Contrastive training is ubiquitous in dense retrieval, starting from such classic papers DPR [14,, ANCE [58], and RocketQA (59] Further enhancements were reported in COIL. [60] SimCSE [61, and GTR [62). Alon et al. [57 provide extremely insightful observations the sampling complexity of contrastive learning from PAC point of view. They show that, for contrastive training with points in d-dimensional space, 22(min n²)) samples are needed. They provide two escape clauses, however. First, the number of samples needed reduces if the points admit some underlying clusters. Second, if each triplet comes with demand for large separation, then the lower bound drops (2()). In LSH-style retrieval, large separation is usually the goal, in the sense that points "near" the query should fall into the same bucket (Hamming distance 0) as the query, and "far" points (that are (1+ e) times farther than near points) should fall into other buckets (Hamming distance 2 1). It is possible that this is what makes contrastive training work well in retrieval applications.
33


Reviews:
[{"review_id": "9ZusX5zp7F", "reviewer": "Reviewer_WWoV", "summary": "The paper presents CORGII, a novel framework that integrates dense neural graph embeddings with scalable, classical retrieval mechanisms. CORGII proposes contextual tokenization of graphs through a differentiable process that converts node-level representations into discrete binary tokens mapped to a latent vocabulary.\nThese tokens are used to construct efficient inverted indices similar to those in text retrieval, enabling\nscalable subgraph search and retrieval with fast candidate generation. Unlike prior dense approaches that\nrequire exhaustive scoring, CORGII supports a trainable impact scoring scheme and a multi-probing strategy that balances accuracy and efficiency. The approach shows strong empirical results on multiple datasets and outperforms recent baselines in both precision and latency", "questions": "- Could the authors provide a qualitative or visual analysis of the token distribution over the graph space? Are tokens reused across semantically similar subgraphs?\n- What is the trade-off between token vocabulary size and retrieval efficiency? Is there a trade-off point?\n- How would CORGII handle temporal graphs, where node connectivity evolves?\n- Can the impact scoring scheme be regularized or interpreted in ways that reveal important graph patterns or regions?\n- Are there graph types or domains where contextual tokenization fails to outperform dense or exact\nmethods?\n- Is the framework compatible with privacy-preserving graph representation ?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n- CORGII successfully bridges classical IR techniques with graph neural networks, enabling scalable and\ninterpretable graph retrieval.\n- The core idea of contextual tokenization, inspired by language tokenization, is original and well-justified for representing graph structures sparsely.\n- The use of a differentiable tokenizer enables an end-to-end training process, ensuring that tokenization is aligned with retrieval goals rather than static feature engineering.\n- Incorporating impact scores adds flexibility to the ranking process, thus making it more adaptive than heuristic scoring schemes.\n- The experimental results are strong, demonstrating consistent  and visible improvements in retrieval precision and\nlatency.\n\nWeaknesses:\n- Multi-probing is used effectively to balance trade-offs, but more theoretical or empirical exploration of\nprobing strategies would strengthen the work.\n- Some technical sections are dense, and concepts like latent vocabulary structure, token reuse, or token\ncollisions could be elaborated for better accessibility.\n- There is a reliance on pre-trained GNNs and clarifying the extent to which performance depends on pretraining quality would be beneficial.\n- Additional benchmarks, especially on very large or noisy graphs, could help validate scalability claims.\n- Lack of interpretability in the learned token representations and impact scores limits their usability in critical decision-making settings.", "was_revised": true, "final_justification": "The responses from the authors completely cleared all my concerns. I updated my initial score from borderline accept to accept since the paper is solid and valid.", "rebuttal": "We thank the reviewer for the comments, which will improve our paper. \n\n> *empirical exploration of probing strategies.*\n\nWe experiment with various multiprobing strategies. Specifically, we compare the cooccurrence multiprobing (CM) strategy with a traditional Hamming distance-based multiprobing variant (HM). In HM, we probe the inverted index using not only $\\tau$, but also nearby tokens within a Hamming ball of radius $r$ in the binary space $(0,1)^D$. Thus, HM enables token matching by leveraging proximity in Hamming space. We also experiment with a single-probing strategy, which is equivalent to setting $r=0$. The table below shows MAP values for different $r$ and $b$ for the PTC-FR dataset. $b$ is the number of similar tokens in the CM strategy. Higher $r$ and $b$ indicate a more diffused neighborhood and more candidates.\n \n|$k/C$|Single-Probe(r=0)|HM,r=1|HM,r=3|HM,r=7|CM,b=8|CM,b=32 |CM,b=64|\n|---|------------------|------|------|------|------|--------------|--------|\n|0.1|0.16|0.16|0.16|0.12|0.15|0.17|0.18|\n|0.2|0.25|0.25|0.25|0.21|0.24|0.27|0.28|\n|0.3|0.31|0.31|0.32|0.29|0.30|0.34|0.34|\n|0.4|0.36|0.36|0.36|0.25|0.35|0.38|0.39|\n|0.5|0.38|0.39|0.40|0.39|0.39|0.42|0.42|\n|0.6|0.48|0.41|0.42|0.43|0.42|0.44|0.44|\n|0.7|0.48|0.48|0.44|0.45|0.44|0.46|0.46|\n|0.8|0.48|0.48|0.48|0.46|0.46|0.47|0.47|\n|0.9|0.48|0.48|0.48|0.48|0.47|0.48|0.48|\n|1.0|0.48|0.48|0.48|0.48|0.48|0.48|0.48|\n \nWe see that single probing cannot trade off between accuracy-efficiency effectively.  CM consistently achieves better trade-off\nthan the corresponding variant of HM and single-probing strategy, while smoothly spanning the full range of retrieval selectivity.\n \n> *Some technical sections are dense, and concepts like latent vocabulary structure, token reuse, or token collisions could be elaborated for better accessibility.*\n\nIn sparse indices, the indexed tokens are interpretable words. In CORGII, tokens are not interpretable, but the expectation is that distinctive subgraph motifs will be mapped to the same or strongly correlated tokens. We cannot find usage of the phrases \"token reuse\" or \"token collisions\" in our manuscript.\n\n> *pre-trained GNNs ... clarifying the extent to which performance depends on pretraining quality would be beneficial.*\n\nWe clarify that our **GNN is not pre-trained**; it is trained independently for indexing, as described in lines 165–167 and illustrated in Figure 1. Consequently, the tokenization network (GTNet) does not rely on any pre-trained embeddings.\nSince the tokenizer operates without any pre-trained GNN, the resulting index ― built solely on the tokens ― is also independent of pre-trained embeddings.\n\nOnly our impact scoring model does utilize pre-trained embeddings from IsoNet. However, this results in minor dependence of pre-trained embeddings. We illustrate this by using two alternatives of current pre-trained embeddings from IsoNet:\n1. Instead of pre-trained embeddings $h$,  we use $x$ to as input to the impact scoring model (Impact($\\tau,x$), Eq. 8).\n1. Instead of training $h$ on the same dataset, we train $h$ some other dataset and then transfer cross-domain embeddings into the impact scoring model. Specifically, we train h on the PTC-FM dataset and apply it to PTC-FR, and likewise train on PTC-MR and apply to COX2. \n \nFollowing tables show the efficiency in terms of fraction of graphs $k/C$ retrieved to achieve atleast a certain MAP=$m^*$ for PTC-FR (first table) and COX2 (second table) datasets. Lower k/C is better and indicates higher efficiency.\n\n|$m^*$|Our (current) | Our (use $x$)|Our ($h$ trained on other dataset)|FHN|DiskANN-multi|IVF-multi|\n|-|-|-|-|-|-|-|\n|0.38|0.38|0.376|0.42|0.51|0.875|0.762|\n|0.40|0.44|0.436|0.47|0.81|0.875|0.896|\n|0.45|0.645|0.626|0.69|0.99|0.935|0.964|\n\n|$m^*$|Our (current) | Our (use $x$)|Our ($h$ trained on other dataset)|FHN|DiskANN-multi|IVF-multi|\n|-|-|-|-|-|-|-|\n|0.38|0.31|0.425|0.27|0.61|0.552|0.644|\n|0.40|0.35|0.482|0.29|0.71|0.821|0.644|\n|0.45|0.45|0.526|0.37|0.99|0.821|0.833|\n\nThe efficiency does not change much and even if we do not use pre-trained embeddings, our method outperforms baselines.\n \n> *... validate scalability claims.*\n\nWe perform experiments with noisy graphs, which results in $\\sim 10\\\\%$ noise in the embedding space. \nWe report the MAP values achieved at different retrieval fractions $k/C$ for various hashing-based methods for PTC-FR (first table) and COX2 (second table) datasets. Higher MAP is better. We observe that our method consistently achieves stronger retrieval quality across a range of candidate pool sizes, demonstrating superior efficiency and robustness compared to the baselines.\n\n|  $k/C$ | CoRGII  | FHN | DiskANN-multi | IVF-multi |\n|-----|---|----|------|------|\n|0.1|0.18|0.15|0.10|0.10|\n|0.2|0.28|0.25|0.16|0.16|\n|0.3|0.35|0.34|0.16|0.16|\n|0.4|0.38|0.34|0.21|0.23|\n|0.5|0.42|0.38|0.37|0.30|\n|0.6|0.44|0.38|0.37|0.30|\n|0.7|0.46|0.42|0.37|0.48|\n|0.8|0.47|0.42|0.44|0.48|\n|0.9|0.48|0.48|0.46|0.48|\n|1.0|0.48|0.48|0.48|0.48|\n\n|$k/C$| CoRGII | FHN  | DiskANN-multi  | IVF-multi |\n|---|-----|-----|------------|-----------|\n|0.1|0.22|0.14|0.19|0.10|\n|0.2|0.32|0.23|0.19|0.19|\n|0.3|0.39|0.33|0.29|0.27|\n|0.4|0.44|0.33|0.35|0.32|\n|0.5|0.48|0.34|0.39|0.36|\n|0.6|0.51|0.46|0.51|0.40|\n|0.7|0.53|0.46|0.51|0.56|\n|0.8|0.55|0.48|0.51|0.56|\n|0.9|0.56|0.53|0.55|0.56|\n|1.0|0.56|0.56|0.56|0.56|\n\nWe also perform experiments with large number of graphs (10^6). It takes 272s to index and 5.44 GB GPU memory (or 19.4 GB CPU memory). Hence, it can be easily run in a very lightweight server.\n\n> *Regularization, Interpretability*\n\nTo examine interpretability of learned token, we compute $(||\\hat{z} _u- \\hat{z} _v|| _1) _{u,v}$ ― a list of pairwise Hamming distance of discrete token embeddings $\\hat{z}$ between nodes. Similarly we obtain a list of distance between the $L$-hop neighborhoods of the nodes in the Eucledian space. We observe the rank correlation between these lists is 0.71, which indicate the token embeddings capture the structures.\n\n\nWe can impose a regularizer to enhance more sparsity in $\\hat{z}$ embeddings, which can control the above rank correlation for PTC-FR.\n\n|L1 norm of \\hat{z}|rankCorr |\n|-|-|\n|2.99|0.71|\n|3.27|0.62| \n|3.50|0.61| \n\nOur impact score is also trained to assign higher score to relevant graph $G _{c}$ to a given query $G _q$, even if $G _c$ is not relevant to other queries. We explicitly use ranking loss rather than classification loss to ensure this, which encourages $S(G _q, G _{c+})> S(G _q, G _{c-}) +m$. We tried with m=0.1, 0.01 and 1 and observed the best performance m =0.1. If we use $S(G_q,G_c)$ as the sole scoring function, then we obtain a modest MAP~0.28 even if $S$ is not any graph matching model and is driven by a simple MLP.\n\n> *qualitative or visual analysis of the token distribution?*\n\nIn Fig. 14 in Appendix, we showed this qualitative analysis.\nHere, we show a small corresponding table, which shows |Token(G)|, the size of the unique token set of corpus graph G vs $\\rho(G)$, the rank of graph G when sorted in\ndescending order of unique token count for PTC-FR.\n\n|Token(G) size |$\\rho(G)$|\n|-|-|\n|14|5K| \n|13|10K|  \n|12|20K|\n|11|30K| \n|10|40K| \n|9|60K| \n|8|80K|\n|6|90K|\n|2|100K|  \n\nSimilar to text, it shows that that most documents have a small number of unique tokens. More details are in App F.4 (page 25, Appendix)\n\n> *Are tokens reused across similar subgraphs*\n\nAs mentioned before, we compare the list of pairwise hamming distance between discrete tokens $(||\\hat{z} _u- \\hat{z} _v|| _1) _{u,v}$ and the distance between the $L$-hop neighborhoods of the nodes in the continuous embedding space. We observe the rank correlation between these lists is 0.71, which indicate the token capture similar subgraphs.\n\n\n> *What is trade off between vocabulary size and retrieval efficiency*\n\nWe explore this trade-off by varying the vocabulary size, which directly affects the average posting list length-a key factor governing retrieval efficiency. The table below reports MAP values for three configurations in PTC-FR.\n\n|Average Posting List Length|MAP|\n|-|-|\n|1642.9|0.31|\n|1792.28|0.31| \n|965.4|0.29| \n\nThere is a trade off between accuracy and efficiency (inverse to fraction of retrieved graphs). Notably, the configuration with a posting list length of ~965 retrieves approximately half as many candidates as the larger configurations, while incurring only a minor drop in MAP, suggesting this setting strikes a favorable balance between speed and performance.\n\n\n>*How would CORGII handle temporal graphs, where node connectivity evolves?*\n\nThis is an excellent branch-out for future work. Much depends on the rate of change. If the graph can change while the query is executing, perhaps little can be done. For slower rates, given CORGII turns graphs into documents in discrete term space, classic literature on mutable corpora can be harnessed.\n\n[Moffat1996] [Managing Gigabytes: Compressing and Indexing Documents and Images]\n\n[Buttcher2006] [Hybrid index maintenance for growing text collections]\n\n[Lester2005] [Fast On-Line Index Construction by Geometric Partitioning]\n\nThere are classic ideas available to support corpus mutation: Log-structured merge trees (LSM), segment-based indexing, buffering and batched updates, deletion markers, and index snapshots and versioning.\n\n> *Is the framework compatible with privacy-preserving  representation?*\n\nWe believe that the discretization scheme allows some obfuscation to protect privacy. Currently, the discretization is deterministic. However, we can use sample the entries in discrete embeddings using a Bernoulli distribution:  instead of $\\hat{z} _u =  \\mathbf{1}(sigmoid(x_u) >0.5)$, we can use $\\hat{z} _u  = \\text{Bernoulli}(sigmoid(x_u/\\lambda))$. This will allow us to ensure privacy through differential privacy more formally, where the amount of privacy will be controlled by $\\lambda$."}, {"review_id": "0vIkIGoADH", "reviewer": "Reviewer_d1NF", "summary": "This paper proposed CORGII (COntextual Representation of Graphs for Inverted Indexing), which aims to improve upon currently existing graph retrieval algorithms in terms of accuracy-efficiency trade-offs. The authors borrow ideas from the text retrieval literature, proposing counterparts in the graph domain such as differentiable graph tokenization, the usage of (trainable) impact scores for query-key matching, and the usage of inverted indices. Their experimental results suggest that CorGII is able to achieve significant improvement in retrieval accuracy-efficiency trade-offs over existing methods.", "questions": "Please refer to the Weaknesses in the Strengths and Weaknesses section.", "limitations": "Please refer to the Weaknesses in the Strengths and Weaknesses section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n\n1. The authors propose to use Chamfer distance for token matching across the discretized graphs. This brings about improved computational efficiency, and the authors argue with theoretical rationale that support the usage of non-injective mappings via the Chamfer distance in this context.\n\n2. The authors propose an effective remedy to the degradation in recall caused by using only a single probe per query token into the indices, which is a result of using discrete node representations as opposed to continuous ones, and also, as claimed by the authors, of using Chamfer score for node alignment, via a co-occurrence expansion based mechanism from classical text retrieval.\n\n3. The paper is very well written, with a well-justified motivation, well-organized development and description of the algorithms, as well as a systematic presentation of empirical results.\n\n4. The authors were thorough in their empirical analysis that validate the decisions taken at most of the steps involved in the algorithm design process. Additionally, the results suggest strong improvements provided by the proposed CoRGII in terms of retrieval accuracy-efficiency trade-offs.\n\n\n\n## Weaknesses:\n\n1. It is not clear what is meant by \"dense graph representation\". How do the authors measure density in the context of graph representations?\n\n2. A discrete, tokenized, multi-vector representation for node-wise matching, although may be able to capture more fine-grained information, seems significantly more computationally expensive than single-vector-based continuous graph representations that can return similarities with a single dot-product computation. How does the proposed CoRGII compensate for this gap? In this regard, no empirical results are provided either that compares CoRGII with single-vector-based continuous approaches in terms of computation overhead, nor is any theoretical time and space complexity analysis being provided.\n\n3. The reason behind the use of Chamfer score instead of permutation-based node alignment causing a loss in recall is not exactly obvious. It is unintuitive as Chamfer score is also meant to capture the same alignment property.\n\n4. Regarding the query-aware learning of the impact score using the MLP $\\psi$, it is important to understand the effect of label imbalance. For node-types that occur very infrequently in the corpus, there may not be sufficiently many samples to guarantee good generalization of the learned impact score function.\n\nMinors:\n\nLine 387: capturi -> capture", "was_revised": true, "final_justification": "I thank the authors for preparing a detailed response to my post-rebuttal comments. They concretized the usage of \"dense\" vs \"sparse\" as essentially based on \"continuous\" vs \"discrete\" representations, and clarified what they mean by \"vastly\". Commendably, during this short discussion timeframe, they designed and evaluated a candidate estimator that gauges the impact of different distance metrics and justifies their usage of Chamfer distance. They also provide a discussion hypothesizing why their method, despite the high default sample complexity of contrastive learning, could potentially satisfy certain conditions that could relax the worst-case upper-bound criterion of a large number of samples, based on theoretical results from existing works. This is sufficient to address my concerns and I am thus happy to increase my score.", "rebuttal": "We would like to thank the reviewer for their comment, which will improve our paper\n\n\n> It is not clear what is meant by \"dense graph representation\".\n\nIn text retrieval, a \"sparse\" index is keyed on discrete tokens. Sparse text indexes use inverted posting lists, in which the number of document (IDs) is vastly smaller than the corpus size, hence the name \"sparse\".\n\nIn a \"dense\" text index, a text encoder converts text into continuous vectors and then they are indexed. Such dense representations are used for IVF, LSH (e.g., FHN) or DiskANN. Dense indexes are larger and slower to navigate than inverted indexes.\n\n> A multi-vector representation .. seems significantly more computationally expensive than single-vector-based continuous graph representations. How does the proposed CoRGII compensate ...? \n\nThere are two key technical challenges in any graph search (and any information retrieval) system:\n1. The number of corpus graphs is large, leading to impractical $\\Omega(|C|)$ execution time for each query, necessitating some mechanism to **eliminate a large fraction of the corpus** at the very outset, via suitable indexing.\n1. Suitable **scoring function design**, which will approximate the similarity between query and corpus graphs. In both text and graph retrieval, the score is frequently learnt from relevant and irrelevant items given a query.\n\nMany contemporary search systems are built as a cascade of a *retriever* (the first stage) and a *reranker* (the second stage).\n\nCORGII is fundamentally a *retriever*, which, given a query, efficiently cuts down the corpus to a much smaller *subset* of eligible candidates. How this subset is scored and reranked is orthogonal to the retriever. The computational trade-offs between single-vector and multi-vector representations that the reviewer refers to manifest primarily in the reranking stage—not in the retrieval stage where CoRGII operates. \n\nCORGII need not be hardwired to a fixed reranking policy. CoRGII is agnostic to the downstream reranker and can be seamlessly paired with any representation based on practical efficiency-accuracy requirements.  Currently CORGII is cascaded with a multi-vector-based ranker (IsoNet). Instead, it can be paired with a single-vector-based reranker.\n\nIndeed, multivector based score computation is slower than single vector based score computation, but CorGII builds an efficient retrieval system that supports faster retrieval than even single vector based dense retrieval.\n\nSpecifically, instead of indexing single dense vector representations and probing the index with multiple dense query vectors, CORGII uses a subsequent encoder step to discretize dense vectors to sparse representations, making graphs appear like documents (with synthetic tokens), so that efficient inverted indices can be used. As with text inverted indices,  queries are discrete tokens and not vectors.\n\n> *In this regard, no empirical results, theoretical  complexity analysis being provided.*\n\nWe fix MAP at target levels $m^*$ and compare retrieval **time** required by different pipelines on **PTC-FR**, while maintaining comparable accuracy.\n\nFirst, we compare CoRGII against FHN, showing that CoRGII achieves the same MAP up to 2× faster than FHN:\n|$m^*$|FHN| CoRGII|\n|-|-|-|\n|0.38|0.06s|0.04s|\n|0.40|0.10s|0.05s|\n|0.45|0.12s|0.08s|\n\nNext, we compare CoRGII with multi-vector reranking against CoRGII with single-vector reranking. While single-vector reranking is faster per comparison, it requires retrieving a much larger portion of the corpus to achieve even moderate MAP values (e.g., 0.38), resulting in higher overall latency. Moreover, due to its limited expressiveness, single-vector reranking fails to reach higher accuracy regimes altogether.\n|$m^*$|CoRGII + Multi-vector reranking| CoRGII + Single-vector reranking\n|-|-|-|\n|0.38|0.06s|0.08s|\n|0.40|0.10s|Never reaches this MAP|\n|0.45|0.12s|Never reaches this MAP|\n\nThus, CoRGII + Multi-vector reranking achieves the best trade-off. While multi-vector scoring is slower per candidate, the number of candidates it needs to consider is substantially lower due to its higher precision. This leads to fewer pairwise computations overall—making it faster in practice than using single-vector representations to achieve the same accuracy.\n\nNotably, CORGII is such an efficient and high-quality retriever compared to the baselines that it is able to compensate the slow reranking time of the multivector methods, resulting in the faster retrieval+ranking time than the baselines including those using faster single-vector-reranker.\n\nWe understand that multivector based reranking is slower than single vector based reranking. However, in contrast, multivector guided retriever, especially inverted indices  like CORGII is much faster than single vector guided retriever, like FHN. We provide a theoretical analysis of this as follows:\n\nSuppose the vocabulary size is $M$. Posting list lengths typically follow Zipf's law, as we see in the literature and also shown in our problem in App F.4 (page 25, Appendix). Hence, by definition of Zipf law, the probability distribution of occurrence of the $k$th most frequent token (in the corpus) is $f(k) = \\frac{A}{k^{\\delta}}$ with $0.5<\\delta < 1$.\n$$\\int _{1} ^M f(k)dk = 1 \\implies A\\frac{M^{1-\\delta}}{(1-\\delta)} - \\frac{A}{1-\\delta}=1$$\nSince $M$ is large, we have $$A = O(M^{\\delta-1})$$\nLet the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have:\n$$ \\frac{LA}{k^{\\delta}} = 1 \\text{ at } k = M$$\nThis implies $L = O(M)$. For one query token, the expected number of corpus graphs returned will be expected length of posting list under Zipf law. For a whole query, the expected number of retrieved graphs is $|V_q| \\mathbb{E} (\\text{Length of posting list})$, where\n$$\\mathbb{E} (\\text{Length of posting list}) = \\int _{1} ^{M} Lf(k) \\times f(k) dk = O(M M^{2\\delta-2})  \\int _{1} ^{M} {k^{2\\delta}} dk$$\nNow, $\\int _{1} ^{M} {k^{2\\delta}} dk =$ constant since $\\delta\\in (0.5,1)$. Therefore, expected posting list length is $O(M^{2\\delta-1}) \\in [O(\\sqrt{M}),O(M)].$ Hence, the expected time complexity of CORGII\nis $O(M^{2\\delta-1})$. Similarly, the space complexity of index is the total length of posting list $O(L) = O(M)$\n\nIn contrast, for the single vector representation in FHN, the seminal paper of (Indyk, Motwani, 1998) showed that the time complexity is $O(|C|^{\\gamma})$ where $\\gamma<1$ is the efficiency parameter of LSH. The space complexity is $O(|C|^{1+\\gamma})+O(|C|)$.\n\nSince in practice, number of corpus items is much more larger than size of the vocabulary, i.e., $|C|\\gg M$, CORGII is more efficient than single vector retrieval in terms of time and accuracy. Moreover, this is consistent with text based retrieval where inverted index is widely adopted over single vector based indexing.\n\nWe also report index construction time and memory usage, both of which remain modest and practical across datasets, supporting the scalability of CORGII.\n|Indexing time|CoRGII|\n|-|-|\n|PTC-FR|29s|\n|COX2|27.2s|\n\n|Indexing memory|CoRGII|\n|-|-|\n|PTC-FR|3.6M|\n|COX2|4.3M|\n>*The reason behind the use of Chamfer score instead of permutation-based node alignment ... not exactly obvious.*\n\nWhen  $G_q\\subseteq G_c$, we would want that $Z _q := (z _q(u) : u\\in V _q )= Z _c :=(z _c(v) : v\\in V _c)$, to ensure exact token matching in inverted index for the relevant query corpus pairs. To compute the matching distance between the sets of tokens, it would have been natural to adopt permutation which gives us the normed distance $||Z _q - P Z _c || _1$. Now, if $P$ is a hard permutation matrix and provides an accurate alignment between query and corpus, then indeed the above normed distance could have been used to train.  \n\nBut, in practice, any graph retrieval model is trained under distance supervision of relevance labels $y _{qc}$ and therefore, the ground truth alignments are not known a-priori. Consequently, $P$ is typically modeled as a doubly stochastic soft permutation matrix and trained end-to-end. While this approximation enables end-to-end differentiability, the continuous nature of $P$ smears the values in $Z _q$ and $Z _c$, leading to poor discretization. \n\nTo ensure a high quality discretization, we avoid soft permutation based approximation and seek a **discrete approximation** of the permutation. In this case, $P _{u,u'} \\approx \\mathbf{1} [ argmin _{v} ||z _q (u) - z _c (v)|| _1==u']$, where $\\mathbf{1}( . )$ is an indicator function. This readily gives $||Z _q - P Z _c || _1$ to be the same as Chamfer score. Instead of continuous approximation, Chamfer score provides a discrete approximation, which is amenable for training z since it is a discrete embedding.\n>... For node-types that occur very infrequently in the corpus, there may not be sufficiently many samples to guarantee good generalization of the learned impact score function.\n\nEven if there are rare graphs, we are able to train impact score, because we are using ranking loss on the aggregated ranked list. Suppose, we have  relevant query corpus pairs G_q and G_c each with rare tokens. In batching, our ranking loss ensures that $S(G _q, G _c) > S(G _{q'}, G _{c'})$ whenever $G _{q'}$ and $G _{c'}$ are not relevant, including graphs which have rich tokens. This allows the trainer to feed sufficient signal into the impact scorer. If we use $S(G _q,G _c)$ as the sole scoring function, then we obtain a modest MAP~0.28 even if $S$ is not any graph matching model and is driven by a simple MLP.\n\nThis can be further enhanced by using the following modification of the impact scores\n$$\\sum  _{u \\in V _q} Impact _{\\psi}(\\hat{z}  _q(u), h  _q(u))\n \\mathbf{1}(\\hat{z}  _q(u) \\in \\omega(G _c)) \\to \\sum _{u \\in V _q}  \\lambda  Impact _{\\psi}(\\hat{z}  _q(u), h _q(u))\n \\mathbf{1}(\\hat{z}  _q(u) \\in \\omega(G _c))$$\nHere, $\\lambda$ is a hyperparameter which is more than 1 and is only applied if $\\hat{z}  _q (u)$ is a rare token."}, {"review_id": "Q2ZN2GXuL3", "reviewer": "Reviewer_R7bo", "summary": "The authors propose CORGII, a method for graph retrieval. Given a small query graph, and a corpus consisting of a collection of several graphs, the goal is to retrieve a list of corpus graphs that contain the query graph. In principle, this requires solving an NP-hard optimization problem, which motivates their method that relaxes the problem into approximate search using vector representations of the query and corpus graphs. CORGII uses GNNs to compute binary representations of nodes in query and corpus graphs, which can in turn be used to compute scores of candidate graphs in an efficient way. The GNNs in CORGII are trained with an approximate objective that seeks to match embeddings of query nodes and notdes in relevant graphs in the corpus. The authors additionally propose several ways to compute scores to account for the information lost in binary representations.", "questions": "1. What is the effect of the specific data used to train IsoNet on the performance of CORGII? How well do you expect it to generalize?\n2. Could you please clarify whether IsoNet is used to rerank all baselines during the evaluation, and if so, whether the comparison is fair since CORGII is trained with IsoNet embeddings?\n3. What is the cost of running CORGII in comparison with FHN?\n4. Did you consider approaches like continuous relaxation of discrete variables when designing GTNet?\n\n- **Clarification questions:**\n\n  4. In Line 22: \"$K$ graphs that 'best' contain $G_c$\"---shouldn't this be $G_q$?\n\n  5. L105: What is the intepretation of $\\leq$ in this context?\n\n  6. L129: The posting list is first defined as a function of $\\tau$ (PostingList($\\tau$)), and later as a function of $c$ (PostingList($c$)). Which is the right one?", "limitations": "The authors do discuss some limitations in the Appendix, though I would suggest to indicate the most critical ones in the main body of the paper to better inform readers of the feasibility and implications of the proposed method.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n1. The problem of graph retrieval is well-motivated and the proposed approach is novel. Different model decisions, such as using different MLPs in the GTNet, the use of the Chamfer distance, the impact networks, and multi-probing strategies are well motivated in relation to issues that are likely to occur during retrieval.\n2. The work seems to be well-positioned with respect to the related work.\n3. The experiments indicate that CORGII outperforms the baselines in the task, over a broad budget (i.e. fraction of the corpus retrieved) range.\n4. The authors provide additional ablation experiments that for the most part support the efficacy of the different parts in CORGII.\n\n**Weaknesses**\n\n1. The method relies on a pre-trained GNN to compute node representations. This could potentially limit how well CORGII generalizes, for example to graphs very different to those used to train IsoNet. This is an important part of CORGII that in my opinion should be discussed in the main body.\n2. One aspect not entirely clear to me during the evaluation is the reranking. Sec. 4, L307 states: *\"For each query* $\\mathcal{Q}_{\\text{test}}$*, we retrieve the corpus graphs* $\\mathcal{R}_q$ *that are relevant by the corresponding model. We rerank the retrieved candidates using the pretrained ranking model.*\" Does this mean that CORGII scores, as well as the baselines, are reranked by IsoNet? If this is the case, the comparison is not entirely fair because CORGII is trained with IsoNet embeddings.\n3. Interestingly, FHN seems to closely follow CORGII in performance, all while being a much simpler and possible cheaper baseline that averages node embeddings. A discussion on the cost of CORGII in comparison with such a simple baseline would help better contextualize the observed benefits.\n4. The performance of FHN also leads to some dubious claims, such as there being a \"benefit of retaining node-level granularity\" (L331). That FHN, a single-vector method, outperforms IVF-multi and DiskANN-multi suggests otherwise.\n5. There are several works on learning discrete representations in neural networks, which appears to not have been considered. GTNet is trained to compute continuous representations, but at test time these are discretized, which causes a mismatch between the training and test distribution. An alternative is to rely on relaxed distributions which try to approximate discrete variables while still allowing gradient-based learning, see e.g. [1].\n6. There are some issues with clarity in the paper, see questions.\n\nOverall, I believe this is a technically solid paper, and I would be open to raising my score if the authors are able to address these weaknesses and my questions.\n\n**References**\n\n[1] Madddison et al. (ICLR 2017), \"The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables\".", "was_revised": true, "final_justification": "CORGII is an efficient and performant method for graph indexing. The evaluation methodology and empirical results are strong, and the dicussion has led to additional insights that point to its effectiveness, thus I have decided to increase my score. The work can still be improved in terms of clarity, which I encourage the authors to address.", "rebuttal": "We would like to thank the reviewer for their comment, which will improve our paper\n\n\n> *The method relies on a pre-trained GNN.... the effect of the specific data used to train IsoNet*\n \n\nWe clarify that our GNN model is not pre-trained; it is trained independently for indexing.  Figure 1 shows the correct picture. $\\text{GNN}_\\theta$ is not informed by and has no connection to the pretrained node embeddings $h$. Moreover, we also clarified in lines 165–167 and the loss function clearly shows that GNN model parameter theta is trained using Chamfer scores and it is not pretrained.\n\n\nSince GNN does not use pretrained embeddings,  tokenization network  also does not rely on any pre-trained embeddings. Hence, the resulting index ― built solely on the tokens ― is also completely of pre-trained embeddings.\n\n\nHowever, our impact scoring model does utilize pre-trained embeddings $h$ from IsoNet. This results in minor dependence of pre-trained embeddings, which does not affect our performance. IsoNet can be readily replaced by any other scoring method. Scoring methods can even transfer between domains.\n\n\nTo demonstrate this, instead of pre-training $h$ on the same dataset, we train h on the PTC-FM dataset and apply it to PTC-FR, and likewise train on PTC-MR and apply to COX2. Following tables show  the efficiency in terms of fraction of graphs $k/C$ retrieved to achieve atleast a certain MAP=$m^*$. Lower k/C is better and indicates higher efficiency.\n  _ denotes places where the method is unable to achieve target MAP. \n\n**k/C values for PTC-FR** \n\n|$m^*$|Our (current) |Our ($h$ trained on PTC-FM dataset)|FHN|FHN (uses $h$ trained on PTC-FM dataset) |IVF|IVF (uses $h$ trained on PTC-FM dataset)\n|-|-|-|-|-|-|-|\n|0.38|0.38|0.42|0.51|0.97|0.76|0.81|\n|0.40|0.44|0.47|0.81|1.0|0.89|0.81|\n|0.45|0.645|0.69|0.99|1.0|0.96|0.91|\n\n\n\n**k/C values for COX2** \n|$m^*$|Our (current) |Our ($h$ trained on PTC-MR dataset)|FHN|FHN (uses $h$ trained on PTC-MR  dataset) |IVF|IVF (uses $h$ trained on PTC-MR  dataset)\n|-|-|-|-|-|-|-|\n|0.36|0.31|0.27|0.61|1.0|0.64|0.57|\n|0.38|0.35|0.29|0.71|-|0.64|0.81|\n|0.40|0.45|0.37|0.99|-|0.83|0.81|\n\nEven if we use IsoNet embeddings trained on other datasets, CORGII beats baselines. Moreover, it is more robust with respect to changing those embeddings.\n\n\n> *CORGII scores, as well as the baselines, are reranked by IsoNet?*\n\n\n**Use of IsoNet reranker:** Many contemporary search systems are built as a cascade of a *retriever* and a *reranker*.  CORGII is fundamentally a *retriever*, which, given a query, efficiently cuts down the corpus to a much smaller *subset* of eligible candidates. How this subset is scored and reranked is orthogonal to the retriever.  \n\nIt is essential that competing retrievers are compared keeping the reranker fixed. Given that IsoNet offered a competitive scoring function, we used IsoNet as reranker. This gives all baselines the same benefit. If we use different rerankers, the difference in performance is difficult to \"factor\" across retriever and reranker.\n\n**On fair comparison:** All baselines use pretrained embeddings. FHN uses Fourier features from the pretrained embeddings and train an intermediate embeddings based on those pretrained embeddings based Fourier features. Since the baselines require pre-trained embedding vectors, we use the same pre-trained embeddings across all baselines including our (in impact scoring model). Hence, our comparison is fair ― we do not use any additional signals as input, that the baselines cannot access.\n\nIn CORGII, the **GNN is not pretrained and does not use any pretrained embeddings**.  Pretrained embeddings $h$ are used only to learn impact scores. **Any** pretrained embedding leading to scores can be used in place of IsoNet here.\n\nThrough two experiments, we further show that the superiority of our method holds true even if we use different embeddings.\n\n(1) First, instead of pre-trained embeddings $h$,  we use $x$ to as input to the impact scoring model (Impact($\\tau,x$), Eq. 8), where $x$ is the embedding from the CorGII GNN, (which is not pretrained and trained as a part of CorGII scheme). \n\nFollowing tables show  the efficiency in terms of fraction of graphs $k/C$ retrieved to achieve atleast a certain MAP=$m^*$ for **PTC-FR (first table) and COX2 (second table) datasets**. Lower k/C is better and indicates higher efficiency.\n\n**k/C for PTC-FR**\n|$m^*$|Our (current) | Our (use $x$)|FHN|DiskANN-multi|IVF-multi|\n|-|-|-|-|-|-|\n|0.38|0.38|0.37|0.51|0.87|0.76|\n|0.4|0.44|0.43|0.81|0.87|0.89|\n|0.45|0.64|0.62|0.99|0.93|0.96|\n\n**k/C for COX2**\n|$m^*$|Our (current) | Our (use $x$)|FHN|DiskANN-multi|IVF-multi|\n|-|-|-|-|-|-|\n|0.36|0.31|0.42|0.61|0.55|0.64|\n|0.38|0.35|0.48|0.71|0.82|0.64|\n|0.42|0.45|0.58|0.99|0.82|0.83|\n\nWe observe that our performance is better, regardless of using the nature of embeddings.\n\n(2) We pre-train a different model called Graph Embedding Network (GEN)[A], which is different from the final reranking model and use them for all methods and our (again, only impact scoring). Following are the results, with _ denoting places where the method is unable to achieve target MAP:\n\n\n**k/C for PTC-FR**\n\n|$m^*$|Our (current) | Our (pretrained GEN-embedding)|FHN (current)| FHN(pretrained GEN-embedding)|DiskANN-multi|DiskANN-multi (pretrained GEN-embedding)|IVF-multi|IVF-multi (pretrained GEN-embedding)|\n|-|-|-|-|-|-|-|-|-|\n|0.38|0.38|0.38|0.51|1.0|0.87|0.82|0.76|0.82|\n|0.40|0.44|0.44|0.81|-|0.87|0.88|0.89|0.94|\n|0.45|0.64|0.65|0.99|-|0.93|0.98|0.96|0.94|\n\n\n**k/C for COX2**\n\n|$m^*$|Our (current) | Our (pretrained GEN-embedding)|FHN (current)| FHN(pretrained GEN-embedding)|DiskANN-multi|DiskANN-multi (pretrained GEN-embedding)|IVF-multi|IVF-multi (pretrained GEN-embedding)|\n|-|-|-|-|-|-|-|-|-|\n|0.36|0.31|0.25|0.61|0.6|0.55|0.65|0.64|0.65|\n|0.38|0.35|0.29|0.71|0.6|0.82|0.76|0.64|0.76|\n|0.40|0.45|0.35|0.99|0.8|0.82|0.76|0.83|0.76|\n\n \n\n\nWe observe that our performance is better, regardless of using the nature of embeddings.\n\n\n\n\n[A] Graph Matching Networks for Learning the Similarity of Graph Structured Objects. Li et al, ICML 2019.\n\n\n> *cost of CORGII in comparison with FHN*\n\nFHN is not that cheaper. It samples frequencies, feeds the resulting Fourier vectors into a neural network to learn a Fourier map, and then uses this map in a neural hashcode generator. \nIn contrast, CORGII discretizes dense graph embeddings into tokens, enabling fast retrieval using inverted indices—similar to text search. Unlike dense retrieval with single or multiple probes, CORGII operates with discrete tokens, making it faster. Next, we give a complexity analysis\n\n\n\nSuppose the vocabulary size is $M$. Posting list lengths typically follow Zipf's law. Hence, by definition of Zipf law, the probability distribution of occurrence of the $k$th most frequent token (in the corpus) is $f(k) = \\frac{A}{k^{\\delta}}$ with $0.5<\\delta < 1$.\n\n\n$$\\int _{1} ^M  f(k)dk = 1 \\implies A\\frac{M^{1-\\delta}}{(1-\\delta)} - \\frac{A}{1-\\delta}=1$$\n\nSince $M$ is large, we have $$A = O(M^{\\delta-1})$$\n\n\nLet the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have:\n\n$$ \\frac{LA}{k^{\\delta}} = 1 \\text{ at } k = M$$\n\nThis implies $L = O(M)$. The expected number of retrieved graphs per token will be expected length of posting list under Zipf law. Hence, the expected number of retrived graphs is $|V_q| \\mathbb{E} (\\text{Length of posting list})$, where\n\n$$\\mathbb{E} (\\text{Length of posting list}) = \\int _{1} ^{M} Lf(k) \\times f(k) dk = O(M M^{2\\delta-2})  \\int _{1} ^{M} {k^{2\\delta}} dk $$\n\nNow, $\\int _{1} ^{M} {k^{2\\delta}} dk =$ constant since $\\delta\\in (0.5,1)$.  Hence, the expected time complexity of our method\nis $O(M^{2\\delta-1})$. Similarly, the space complexity of index is the total length of posting list $O(L) = O(M)$\n\n\nIndyk and Motwani (1998) showed that the time complexity FHN is $O(|C|^{\\gamma})$ where $\\gamma<1$ is the efficiency parameter of LSH. The space complexity is $O(|C|^{1+\\gamma})+O(|C|)$.\n\nIn practice, number of corpus items is much more larger than size of the vocabulary, i.e., $|C| \\gg M$, CORGII is more efficient than single vector retrieval in terms of time and accuracy. \nCORGII is also fast in practice.\n \n|Running time for **PTC-FR dataset**|CoRGII|FHN|\n|-|-|-|\n|MAP = 0.38|0.04s|0.06s|\n|MAP = 0.45|0.08s|0.12s|\n\n\n> *FHN, a single-vector method, outperforms IVF-multi and DiskANN-multi*\n\nIVF-multi and DiskANN-multi indices are built using norm-based distances (e.g., Euclidean) between query and corpus embeddings. In contrast, our subgraph matching task requires ranking based on hinge distance between query and corpus embeddings. Incorporating hinge distance into these methods is non-trivial, as their indexing relies on corpus–corpus distances rather than query–corpus distances.  \n\nOn the other hand, FHN is specifically designed for hinge distance. Therefore, despite single vector based representation, it performs better.\n\n\n> *An alternative is to rely on relaxed distributions. [1].*\n\n\nWe experimented with the approach in [1] by incorporating a relaxed, continuous approximation to the tokenization step using a **temperature-controlled sigmoid function**, varying the **temperature hyperparameter** $\\lambda$, which controls the sharpness of the relaxation.\n\nBelow, we report the MAP values on the **PTC-FR** dataset under different $k/C$ ratios:\n\n|$k/C$|CoRGII (current)|CoRGII ($\\lambda = 0.5$)|CoRGII ($\\lambda = 1$)|\n|-|-|-|-|\n|0.1|0.17|0.18|0.17|\n|0.2|0.27|0.28|0.26|\n|0.5|0.42|0.42|0.42|\n\nWe observe that the results are comparable.\n\n\n> *clarification*\n\nLine 22: Yes , it should be $G_q$; L105: $\\le$ means entriwise inequality ($A \\le B$) means $A[i,j] \\le B[i,j]$ for all $i,j$; L129: PostingList($\\tau$) is correct."}, {"review_id": "rNj0My2Cxv", "reviewer": "Reviewer_DMJr", "summary": "This paper introduces CORGII, a novel framework for the retrieval of graphs containing a given query subgraph. The core idea is to represent each graph as a set of discrete, structure-aware tokens generated by GNN and a differentiable binarization process. These tokens make it possible to leverage classic inverted index techniques (which were originally developed for text retrieval) to index and search large graph collections efficiently. Furthermore, the use of co-occurrence-based multi-probing enhances recall by expanding the set of candidate matches. In summary, CORGII effectively combines the expressive power of dense neural graph representations with the scalability and efficiency of sparse inverted indices, enabling practical and high-performance subgraph retrieval.", "questions": "1.\tIn the paper you mention, “as a first step toward tokenization, we apply two (still differentiable, but distinct) networks to hq(u), hc(v).” According to Figure 2, are these corresponding to x_q(u) and x_c(v)? There seems to be some confusion or mixing between x(u) and h(u) in the text and diagrams.\n2.\tIn Section 3.2 (“Discretization and inverted index”), you mention binarizing z by thresholding at 0.5. Have you considered using more than one bit per element of z (i.e., multi-level or quantized discretization) to increase accuracy? What would be the trade-offs in terms of retrieval accuracy, index size, and efficiency? A brief discussion or experiment on this design choice would be helpful.\n3.\tYou note that “if multiple nodes u have the same token \\hat{z}_q(u), they are counted multiple times.” I am concerned this might violate the injectivity constraint in subgraph isomorphism/graph matching. How does this affect retrieval quality or correctness? Would deduplication or enforcing uniqueness help, or is there a principled reason for allowing duplicates?\n4.\tThe current evaluation focuses on MAP versus retrieval set size, but does not report practical efficiency metrics such as query-per-second (QPS) versus recall (as is common in ANN literature). Could you provide this type of result?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.\tInspired by text retrieval, CORGII combines neural graph embeddings with inverted index structures to enable efficient subgraph retrieval.\n\n2.\tThe method is tested on several benchmark datasets and compared with existing baselines.\n\n3.\tThe paper is well-motivated, clearly explains each system component, and includes ablation studies to show the impact of its design choices.\n\n\nWeaknesses:\n\n1.\tThe presentation could be improved. Specifically, the framework would benefit from a clearer breakdown of each component; In addition, the distinction between variables such as x(u) and h(u) could be clarified.\n2.\tThe paper does not provide in-depth theoretical analysis or guarantees regarding the effects of tokenization or multi-probing on retrieval performance.\n3.\tThe evaluation mainly reports MAP versus retrieval set size, but does not present retrieval time or runtime efficiency results, making it less convincing for readers concerned with practical scalability.", "was_revised": true, "final_justification": "Most of my concerns have been adressed. I will increase my score.", "rebuttal": "We would like to thank the reviewer for their comment, which will improve our paper.\n\n\n> The presentation could be improved. Specifically, the framework would benefit from a clearer breakdown of each component; In addition, the distinction between variables such as x(u) and h(u) could be clarified.\n\nWe agree that clearly distinguishing between $\\mathbf{x}(u)$ and $\\mathbf{h}(u)$ is essential. To clarify:\n\n- $\\mathbf{h}(u)$ denotes **contextual node embeddings from a pretrained subgraph matching model** (IsoNet). These are **used exclusively as input to the impact scoring network**, both during training and inference. They do **not** influence the tokenization process. In other words, our GNN is trained without any pretraining and as a result, the subsequent tokenization and **indexing does not depend on pre-trained embeddings.**\n\n- $\\mathbf{x}(u)$ refers to the contextual node representations **computed within CORGII itself**, using a shared GNN applied to both query and corpus graphs. These representations are input to **separate MLPs** that generate tokenization logits $\\mathbf{z}(u) \\in (0, 1)^D$. After training, these logits are thresholded to obtain binary codes $\\widehat{\\mathbf{z}}(u) \\in (0,1)^D$, which are then mapped to token IDs for inverted indexing.\n\nImportantly, the **tokenization and retrieval pipeline relies solely on $\\mathbf{x}_q(u)$**, as shown in **Figure 1**. The pretrained embeddings $\\mathbf{h}(u)$ from IsoNet are **only used as auxiliary inputs for impact scoring**, and are not involved in computing or indexing token representations.  A different source of node encoding than IsoNet can readily be plugged in, replacing IsoNet.\n\nThere is a typo in the text: It should be written as \"we apply two networks to xq(u), xc(v)\" and   Figure 1is correct. Many thanks for pointing this out.\n\n\n \n\n> The paper does not provide in-depth theoretical analysis or guarantees regarding the effects of tokenization or multi-probing on retrieval performance.\n\n\nHere is some basic analysis of the complexity of CORGII under certain common assumptions on the corpus.  Suppose the vocabulary size is $M$. Posting list lengths typically follow Zipf's law, as we see in the literature [A] and also shown in our problem in App F.4 (page 25, Appendix). By Zipf's law, the probability distribution of occurrence of the $k$th most frequent token (in the corpus) is $f(k) = \\frac{A}{k^{\\delta}}$ with $0.5<\\delta < 1$.\n\n$$\\int _{1} ^M f(k)dk = 1 \\implies A\\frac{M^{1-\\delta}}{(1-\\delta)} - \\frac{A}{1-\\delta}=1$$\n\nSince $M$ is large, we have $$A = O(M^{\\delta-1})$$\n\nLet the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have:\n$$ \\frac{LA}{k^{\\delta}} = 1 \\text{ at } k = M$$\n\nThis implies $L = O(M)$. For one query token, the expected number of corpus graphs returned will be the expected length of the posting list of the token.  The expected query cost is thus $|V _q| \\mathbb{E} (\\text{Length of posting list})$, where\n\n$$\\mathbb{E} (\\text{length of posting list}) \\approx \\int _{1} ^{M} Lf(k) \\times f(k) dk = O(M M^{2\\delta-2})  \\int _{1} ^{M} {k^{2\\delta}} dk $$\n\nNow, $\\int _{1} ^{M} {k^{2\\delta}} dk =$ constant since $\\delta\\in (0.5,1)$. Therefore, the expected posting list length is $O(M^{2\\delta-1}) \\in [O(\\sqrt{M}),O(M)].$ Hence, the expected time complexity of our method\nis $O(M^{2\\delta-1})$. Similarly, the space complexity of index is the total length of posting list $O(L) = O(M)$\n\n\nOn the other hand, for the single vector representation in FHN, the seminal paper of (Indyk and Motwani, 1998) showed that the time complexity is $O(|C|^{\\gamma})$ where $\\gamma<1$ is the efficiency parameter of LSH. The space complexity is $O(|C|^{1+\\gamma})+O(|C|)$.\n\nSince in practice, number of corpus items is much more larger than size of the vocabulary, i.e., $|C| \\gg M$, our method is more efficient than single vector retrieval in terms of time and accuracy. Moreover, this is consistent with text based retrieval where inverted index is widely adopted over single vector based indexing.\n\nExtending to multi-token queries is messy, because then we need to model a _joint_ distribution over words in a very high dimensional space. For this reason, there has been no serious analysis of this form in the Information Retrieval literature.\n\n\n> The evaluation mainly reports MAP versus retrieval set size, but does not present retrieval time or runtime efficiency results, making it less convincing for readers concerned with practical scalability.\n\nWe present a modified view of our results which directly addresses retrieval latency and scalability.  The following table reports both the size of the candidate pool and the corresponding retrieval latency (in seconds). As seen, CORGII outperforms all the baselines in terms of candidate efficiency and query time at comparable MAP thresholds (m*). CORGII retrieves significantly fewer candidates while achieving competitive or better latency and MAP, clearly demonstrating its practical scalability and efficiency.\n\n\n#### **PTC-FR**\n\n| MAP ≥ m* | FHN         | CoRGII        | IVF | DiskANN|\n|-----------------|-------------|---------------|-----------|----------------|\n| 0.38            | 0.06s | 0.04s   | 0.09s    | 0.10s         |\n| 0.40            | 0.10s | 0.05s   | 0.10s    | 0.10s        |\n| 0.45            | 0.12s | 0.08s | 0.11s     | 0.11s         |\n\n#### **COX2**\n\n| MAP ≥ m* | FHN         | CoRGII        | IVF | DiskANN |\n|-----------------|-------------|---------------|-----------|----------------|\n| 0.36            | 0.08s | 0.03s   | 0.07s     | 0.06s         |\n| 0.38            | 0.09s | 0.04s   | 0.07s    | 0.9s       |\n| 0.42            | 0.12s | 0.05s   | 0.9s     | 0.09s         |\n\n> In the paper you mention, “as a first step toward tokenization, we apply two (still differentiable, but distinct) networks to hq(u), hc(v).” According to Figure 2, are these corresponding to x_q(u) and x_c(v)? There seems to be some confusion or mixing between x(u) and h(u) in the text and diagrams.\n\nThank you for pointing this out. You are absolutely right — the line in question should refer to $x_q(u)$ and $x_c(v)$, not $h_q(u)$ and $h_c(v)$. As clarified in our earlier response, CORGII uses GNN-derived contextual node embeddings x(u) for tokenization and impact scoring. The pretrained embeddings $h(u)$ are used only during training to supervise the impact scoring function and are never passed as inputs to any component of the CORGII architecture.\n\nWe will correct this line in the final version to avoid confusion and ensure consistency with Figure 1 and the overall description of the model.\n\n\n> What would be the trade-offs in terms of retrieval accuracy, index size, and efficiency.\n\nWe change the discretization, which resulted in different posting list sizes. Following is the table, which shows that with respect to posting list, MAP is robust.\n\n\n\n|Average Posting List Length|MAP|\n|-|-|\n|1642.9|0.31|\n|1792.28|0.31| \n|965.4|0.29|\n\n\nIndexing of CORGII on the PTC-FR dataset takes 46MB and 272s for a million graphs, which is quite modest.  \n\nWe also compare CoRGII against FHN, showing that CoRGII achieves the same MAP up to 2× faster than FHN on PTC-FR dataset:\n\n|$m^*$|FHN| CoRGII|\n|-|-|-|\n|0.38|0.06s|0.04s|\n|0.40|0.10s|0.05s|\n|0.45|0.12s|0.08s|\n\n> You note that “if multiple nodes u have the same token $\\hat{z}_q(u)$, they are counted multiple times.” I am concerned this might violate the injectivity constraint in subgraph isomorphism/graph matching. How does this affect retrieval quality or correctness? Would deduplication or enforcing uniqueness help, or is there a principled reason for allowing duplicates?\n\n\nWe consider multiset-based token matching is more faithful to subgraph matching than enforcing set-based uniqueness. In subgraph isomorphism, it is possible for multiple nodes to map to the same structure or token, and discarding duplicates would remove crucial count-based information. By retaining token multiplicity, CORGII preserves these mass constraints, enabling more accurate retrieval aligned with the structural semantics of subgraph matching.\n\nBelow, we compare retrieval performance with and without deduplication for two datasets **PTC-FR** (first table) and **COX2** (second table). We observe that deduplication **slightly reduces recall**, confirming that duplicate tokens improve retrieval quality in our setup.\n\n **PTC-FR** \n|$k/C$|Original|Dedup|\n|---|--------|-----|\n|0.1|0.17|0.15|\n|0.2|0.27|0.25|\n|0.3|0.34|0.32|\n|0.4|0.38|0.36|\n|0.5|0.42|0.40|\n|0.6|0.44|0.41|\n|0.7|0.46|0.43|\n|0.8|0.47|0.44|\n|0.9|0.48|0.46|\n|1.0|0.48|0.48|\n\n**COX2**\n|$k/C$|Original|Dedup|\n|---|--------|-----|\n|0.1|0.22|0.17|\n|0.2|0.32|0.28|\n|0.3|0.39|0.35|\n|0.4|0.44|0.40|\n|0.5|0.48|0.45|\n|0.6|0.51|0.48|\n|0.7|0.53|0.50|\n|0.8|0.55|0.52|\n|0.9|0.56|0.54|\n|1.0|0.56|0.56|\n\n\n\n> The current evaluation focuses on MAP versus retrieval set size, but does not report practical efficiency metrics such as query-per-second (QPS) versus recall (as is common in ANN literature). Could you provide this type of result?\n\n\n\n|Throughput on PTC-FR Dataset|Queries|Corpus Items|Query-per-second|\n|-------------|-------|------------|----------------|\n|CoRGII|100|38K|555.55|\n|FHN|75|51K|357.14|\n\n\n\n|Throughput on COX2 Dataset|Queries|Corpus Items|Query-per-second|\n|-------------|-------|------------|----------------|\n|CoRGII|123|31K|1021.75|\n|FHN|63|61K|311.6|\n\nWe observe that our QPS is much higher."}, {"review_id": "GtpEpDZVNU", "reviewer": "Reviewer_69TG", "summary": "This paper proposes a novel framework for subgraph retrieval from large graph corpora. The key idea is to discretize contextualized node embeddings (via a GNN-based tokenizer) into sparse binary tokens over a latent vocabulary, enabling efficient inverted indexing similar to classical document retrieval. CORGII further introduces trainable impact scores for tokens, replacing static metrics, and a co-occurrence-based multi-probing strategy to improve recall. Experiments across several datasets demonstrate competitive accuracy-efficiency trade-offs compared to baselines.", "questions": "1. What is the precise architecture of the tokenizer module? How is the vocabulary defined, and is it shared between query and corpus graphs?\n\n2. How is the impact score computed and trained? Is it input-dependent or globally parameterized?\n\n3. Can CORGII be used without reranking from IsoNet? What is the standalone retrieval accuracy?\n\n4. What is the index construction time and memory footprint? How does it scale to millions of graphs?\n\n5. How does performance change under graph structure perturbations or with unseen topologies?", "limitations": "1. Discrete tokens may not be robust to minor structural variations in graphs.\n2. Indexing large corpora with learned tokens may be memory-intensive, but this is not analyzed.\n3. Heavy reliance on a pretrained IsoNet backbone suggests CORGII is not an end-to-end solution.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. The motivation is sound. Subgraph retrieval is a fundamental problem in applications such as molecular search and program analysis, and accelerating this process remains a relevant challenge.\n2. The integration of GNNs, differentiable tokenization, and inverted indexing is a reasonable engineering direction in analogous developments in dense text retrieval.\n3. Experimental results cover multiple datasets and baselines, showing great results on accuracy and latency.\n\nWeaknesses\n1. The presentation is somewhat vague in some places. The architecture and training procedure of the Graph Tokenizer Network are under-specified. It's unclear whether tokenization is learned via soft clustering, Gumbel-softmax, or discrete vector quantization. The multi-probing strategy is only described conceptually, without algorithmic detail or pseudocode. How token co-occurrence is estimated or utilized remains vague.\n\n2. No ablation study is provided to evaluate the necessity of core components (e.g., impact score, multi-probing, GNN tokenization). Without this, it is difficult to assess what actually drives performance. Index construction cost (in terms of memory, latency, or scalability) is not discussed or measured, despite being central to the claimed efficiency.", "was_revised": true, "final_justification": "The motivation is sound and the experimental results are great in the reported benchmarks", "rebuttal": "We would like to thank the reviewer for their comment, which will improve our paper\n\n>architecture, training  of Graph Tokenizer\n\nGTN consists of two components (1) GNN and (2) two MLPs. The pipeline begins with a shared GNN $\\mathrm{GNN} _\\theta$, which computes structure-aware node embeddings $\\mathbf{x} _q(u)$ for query graphs  $G _q$, and $\\mathbf{x} _c(v)$ for corpus graphs $G _c$. These embeddings $\\mathbf{x}(u)$ are distinct from the pretrained IsoNet embeddings $\\mathbf{h}(u)$.\n\nWe apply separate MLPs (Eqns. 2–3) to $\\mathbf{x} _q(u)$ and $\\mathbf{x} _c(v)$, each ending with a sigmoid activation to produce continuous outputs in $(0,1)^D$. These yield soft tokenization vectors $\\mathbf{z}(u) \\in \\mathbb{R}^D$ for every node. These scores are **trained using the Chamfer distance loss** (Eqn. 4) and a **ranking loss** (Eqn. 5) that encourages correct subgraph retrieval ordering.  \n\nAfter training is completed, the continuous logits $\\mathbf{z}(u) \\in (0,1)^D$ are converted into binary token vectors $\\widehat{\\mathbf{z}}(u) \\in (0,1)^D$ via hard thresholding at test time for indexing and retrieval:  \n$$\\widehat{\\mathbf{z}}(u)[i] = \\mathbf{1}[\\mathbf{z}(u)[i] \\ge \\text{threshold}]$$\n\nTherefore, CORGII avoids sampling-based approximations like Gumbel-softmax or vector quantization and instead relies on a fully differentiable training process with late discretization.\n\nWe discussed them in paper in Section 3.1. Minute details are given in Appendix D.2.\n\n\n>*Is the Vocabulary shared*\n\nThe token vocabulary is implicitly defined as the set of all possible $D$-bit binary codes, i.e., $\\mathcal{T} = (0,1)^D$. This vocabulary is **shared** between query and corpus graphs; however, the use of separate MLPs allows us to learn **asymmetric containment-aware representations** within a **symmetrically shared token space**—a crucial design choice for aligning with containment-style relevance while still enabling efficient token-based matching via an inverted index.\n>*Details about multiprobing*\n\nEach graph is represented as a multiset of discrete tokens aggregated from its node-level $\\widehat{\\mathbf{z}}(u)$ vector. In single probing, we proceed as follows: Given a token $\\widehat{\\mathbf{z}}(u)$, we return the graphs in the posting list corresponding to this token. In multiprobing, we also collect PostingList($\\tau$), where $\\tau$ is ($u$ or sufficiently) similar to $u$ in the sense that the posting lists of $\\tau$ and $u$ have large overlap ― eqn. (13).\n\nCORGII compute this similarity based on **co-occurrence**. A token co-occurrence graph is constructed offline by estimating the overlap between token posting lists across the training corpus. As defined in Equation (13), a normalized similarity score is computed between tokens based on how much their posting lists overlap. At query time, for each query token $\\tau _i$, we retrieve both its posting list and those of its top-$k$ co-occurring tokens $\\tau _j$.  \n> *How is impact score computed and trained? is it input dependent/globally paremeterized*\n\n$\\text{Impact} _\\psi(\\tau _u, \\text{Embedding}(u))$ is an MLP which takes the binary embedding of $\\tau$, i.e., $\\hat{z}$ and some continuous embedding (intermediate GNN embeddings or pretrained embeddings) as input and output a scalar value. This design makes the impact score **input-dependent** and **query-aware**, rather than being globally parameterized or fixed like traditional TF-IDF or BM25 weights. This is trained by minimizing a pairwise ranking loss (Eqn. 10).\n>Ablation study. \n\nWe presented several ablation study in the experiments (see L343 to L383). We did not clearly highlight them as ablation study and we are sorry for that. We will mention them in the revised version.\n\nFirst we perform ablation on multiprobing, by comparing between co-occurence based multi-probing (CM), Hamming multiprobing (HM in Eq. 12) and single probing. Following table shows the results for PTC-FR which shows that CORGII performs best and Single probe is worst.\n\n|$k/C$|CORGII (CM)|HM|Single Probe|\n|-|-|-|-|\n|0.1|0.17|0.16|0.16|\n|0.2|0.27|0.25|0.25|\n|0.3|0.34|0.32|0.31|\n|0.4|0.38|0.36|0.36|\n|0.5|0.42|0.4|0.38|\n|0.6|0.44|0.42|0.38|\n|0.7|0.46|0.44|0.38|\n|0.8|0.47|0.48|0.38|\n|0.9|0.48|0.48|0.38|\n|1.0|0.48|0.48|0.48|\n\nNext, we perform ablation on impact scores, by comparing our method against uniform impact (equal impact for all tokens and all corpus graphs). Following table shows the results for PTC-FR which shows that CORGII performs better than uniform impact.\n\n|$k/C$|CORGII|Unif. impact|\n|-|-|-|\n|0.1|0.17|0.09|\n|0.2|0.27|0.17|\n|0.3|0.34|0.23|\n|0.4|0.38|0.28|\n|0.5|0.42|0.33|\n|0.6|0.44|0.37|\n|0.7|0.46|0.40|\n|0.8|0.47|0.43|\n|0.9|0.48|0.46|\n|1.0|0.48|0.48|\n\nNext, we use a Siamese module, instead of our current tokenizer module. The following table shows the results for PTC-FR, which shows that CORGII performs better than the alternative.\n\n|$k/C$ | CORGII | Siamese|\n|-|-|-|\n|0.1|0.17|0.03|\n|0.2|0.27|0.07|\n|0.3|0.34|0.11|\n|0.4|0.38|0.16|\n|0.5|0.42|0.20|\n|0.6|0.44|0.26|\n|0.7|0.46|0.30|\n|0.8|0.47|0.36|\n|0.9|0.48|0.42|\n|1.0|0.48|0.48|\n>Index construction cost ...Scaling for million graphs.\n\nWe observe that indexing of CORGII on the PTC-FR dataset takes 46MB and 272s for a million graphs, which is quite modest. Next we provide a theoretical complexity for time and space.\n\nSuppose the vocabulary size is $M$. Posting list lengths typically follow Zipf's law. Hence, by definition of Zipf law, the probability distribution of occurrence of the $k$th most frequent token (in the corpus) is $f(k) = \\frac{A}{k^{\\delta}}$ with $0.5<\\delta < 1$.\n$$\\int  _{1} ^M f(k)dk = 1 \\implies A\\frac{M^{1-\\delta}}{(1-\\delta)} - \\frac{A}{1-\\delta}=1$$\nSince $M$ is large, we have $$A = O(M^{\\delta-1})$$\n\nLet the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have:\n$$\\frac{LA}{k^{\\delta}} = 1 \\text{ at } k = M$$\nThis implies $L = O(M)$. For one query token, the expected number of corpus graphs returned will be the expected length of the posting list of the token. The expected query cost is thus $|V _q| \\mathbb{E} (\\text{Length of posting list})$, where\n$$\\mathbb{E} (\\text{Length of posting list}) = \\int  _{1} ^{M} Lf(k) \\times f(k) dk = O(M M^{2\\delta-2})  \\int  _{1} ^{M} {k^{2\\delta}} dk$$\nNow, $\\int  _{1} ^{M} {k^{2\\delta}} dk =$ constant since $\\delta\\in (0.5,1)$. Hence, the expected time complexity of our method is $O(M^{2\\delta-1})$. Similarly, the space complexity of index is the total length of posting list $O(L) = O(M)$.\n\nOn the other hand, for the single vector representation in FHN, the seminal paper of (Indyk and Motwani, 1998) showed that the time complexity is $O(|C|^{\\gamma})$ where $\\gamma<1$ is the efficiency parameter of LSH. The space complexity is $O(|C|^{1+\\gamma})+O(|C|)$.\nSince in practice, number of corpus items is much larger than size of the vocabulary, i.e., $|C| \\gg M$, CORGII is more efficient than single vector retrieval in terms of time and accuracy (also see following table). \n\n|Running time for **PTC-FR**|CoRGII|FHN|\n|-|-|-|\n|MAP = 0.38|0.04s|0.06s|\n|MAP = 0.45|0.08s|0.12s|\n\n> Can CORGII be used without reranking from IsoNet?  \n\nMany contemporary search systems are built as a cascade of a *retriever*  and a *reranker*. CORGII is fundamentally a *retriever*, which, given a query, effciently cuts down the corpus to a much smaller *subset* of eligible candidates. How this subset is scored and reranked is orthogonal to the retriever. \n\nHence, CORGII can be used standalone to return a set of IDs, just like any other retriever like DiskANN, LSH etc. It does not rank the documents. Hence, like any other retriever, we must need some ranker to rank those documents. But, CORGII is not dependent on fixed reranking policy. It can be paired with any ranking policy.\n\nWe used IsoNet because it is a SOTA reranker. Instead of this, if we use some other reranker like GEN [A], we observed significant degradation of the accuracy-speed trade off of the baselines (MAP from 0.42 to 0.37 for k/C = 0.7; MAP  from 0.38 to 0.33 for k/C = 0.5), while we still perform better.  \n\n[A] Graph Matching Networks for Learning the Similarity of Graph Structured Objects. Li et al, ICML 2019.\n\n> Heavy reliance on a pretrained IsoNet backbone .\n\nNote that we did not pre-train our GNN model (Fig 1). Hence, the tokenizer operates without any pre-trained GNN and therefore, the resulting index ― built solely on the tokens ― is also completely independent of pre-trained embeddings.\n\nOnly our impact scoring model does utilize pre-trained embeddings from IsoNet. However, this results in minor dependence of pre-trained embeddings. We illusrate this by using two alternatives of current pre-trained embeddings from IsoNet\n\n(1) Instead of pre-trained embeddings $h$,  we use $x$ to as input to the impact scoring model (Impact($\\tau,x$), Eq. 8).\n\n(2) Instead of training $h$ on the same dataset, we train $h$ on PTC-FM dataset and apply it to PTC-FR. \n\nFollowing tables shows the efficiency in terms of fraction of graphs $k/C$ retrieved to achieve atleast a certain MAP=$m^*$ for PTC-FR   datasets. Lower k/C is better and indicates higher efficiency.\n \n|$m^*$|Our (current)|Our (use $x$)|Our ($h$ trained on other dataset)|FHN|\n|-|-|-|-|-|\n|0.38|0.38|0.376|0.42|0.51|\n|0.40|0.44|0.436|0.47|0.81|\n|0.45|0.645|0.626|0.69|0.99|\n \nWe observe that the efficiency does not change much and even if we do not use pre trained embeddings, our method outperforms baselines.\n\n> Performance change under graph structure perturbations\n\nWe perform experiments with noised PTC-FR graphs, which results in $\\sim 10\\\\%$ noise in embedding space. \nWe report the MAP values  for different values of k/C (retrieved graph fraction for PTC-FR), which shows that our method performs better.\n|k/C|CoRGII|FHN| \n|-|-|-|\n|0.1|0.18|0.15|\n|0.2|0.28|0.25|\n|0.3|0.35|0.34|\n|0.4|0.38|0.34|\n|0.5|0.42|0.38|\n|0.6|0.44|0.38|\n|0.7|0.46|0.42|\n|0.8|0.47|0.42|\n|0.9|0.48|0.48|\n|1.0|0.48|0.48|"}]

Author rebuttal:

Meta-review: **Summary:** This paper presents CoRGII, a pipeline that combines contextual graph tokenization, differentiable discretization, and inverted indices for efficient graph retrieval. The method achieves strong accuracy - efficiency trade-offs and is supported by extensive experiments, ablations, and complexity analysis.

**Strengths:** The reviewers highlighted: (1) the importance of the problem; (2) a novel adaptation of classical IR techniques (contextual tokenization, differentiable discretization, and inverted indices) for graph retrieval; (3) producing strong empirical results over strong baselines with extensive ablations.

**Weaknesses:** Initial concerns included (1) unclear presentation; (2) missing complexity/runtime analysis, (3) reliance on IsoNet embeddings, (4) effects of discretization, and (5) robustness to rare tokens and noisy graphs.

The rebuttal and discussion resolved most of the reviewers' concerns. The authors clarified terminology, detailed the tokenizer architecture, and showed that CoRGII does not rely on pre-trained GNN embeddings. They added experiments on runtime efficiency, multiprobing, Chamfer error estimation, token interpretability, and rare-token handling, alongside clearer ablations. Reviewers acknowledged these clarifications, raised scores, and agreed that despite some remaining clarity issues (which the authors have agreed to resolve in the final version), the contribution is solid, novel, and impactful. The consensus is that this is a strong paper deserving acceptance at NeurIPS.
Decision: Accept (poster)