Contextual Tokenization for Graph Inverted Indices

We would like to thank the reviewer for their comment, which will improve our paper

architecture, training of Graph Tokenizer

GTN 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)$.

We 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.

After 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:
$\widehat{\mathbf{z}}(u)[i] = \mathbf{1}[\mathbf{z}(u)[i] \ge \text{threshold}]$

Therefore, CORGII avoids sampling-based approximations like Gumbel-softmax or vector quantization and instead relies on a fully differentiable training process with late discretization.

We discussed them in paper in Section 3.1. Minute details are given in Appendix D.2.

Is the Vocabulary shared

The 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.

Details about multiprobing

Each 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).

CORGII 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$.

How is impact score computed and trained? is it input dependent/globally paremeterized

$\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).

Ablation study.

We 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.

First 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.

Next, 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.

Next, 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.

Index construction cost ...Scaling for million graphs.

We 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.

Suppose 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$. $\int _{1} ^M f(k)dk = 1 \implies A\frac{M^{1-\delta}}{(1-\delta)} - \frac{A}{1-\delta}=1$ Since $M$ is large, we have $A = O(M^{\delta-1})$

Let the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have: $\frac{LA}{k^{\delta}} = 1 \text{ at } k = M$ This 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 $\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$ Now, $\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)$.

On 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|)$. Since 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).

Can CORGII be used without reranking from IsoNet?

Many 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.

Hence, 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.

We 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.

[A] Graph Matching Networks for Learning the Similarity of Graph Structured Objects. Li et al, ICML 2019.

Heavy reliance on a pretrained IsoNet backbone .

Note 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.

Only 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

(1) Instead of pre-trained embeddings $h$, we use $x$ to as input to the impact scoring model (Impact($\tau,x$), Eq. 8).

(2) Instead of training $h$ on the same dataset, we train $h$ on PTC-FM dataset and apply it to PTC-FR.

Following 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.

We observe that the efficiency does not change much and even if we do not use pre trained embeddings, our method outperforms baselines.

Performance change under graph structure perturbations

We perform experiments with noised PTC-FR graphs, which results in $\sim 10\\%$ noise in embedding space. We report the MAP values for different values of k/C (retrieved graph fraction for PTC-FR), which shows that our method performs better.

Dear reviewer 69TG,

We addressed your comments, to the best of our abilities. Could you please let us know if you have any concerns/questions? Did our rebuttal address your concerns?

We would like to thank the reviewer for their comment, which will improve our paper.

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.

We agree that clearly distinguishing between $\mathbf{x}(u)$ and $\mathbf{h}(u)$ is essential. To clarify:

• $\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.

• $\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.

Importantly, 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.

There 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.

The paper does not provide in-depth theoretical analysis or guarantees regarding the effects of tokenization or multi-probing on retrieval performance.

Here 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$.

$\int _{1} ^M f(k)dk = 1 \implies A\frac{M^{1-\delta}}{(1-\delta)} - \frac{A}{1-\delta}=1$

Since $M$ is large, we have $A = O(M^{\delta-1})$

Let the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have: $\frac{LA}{k^{\delta}} = 1 \text{ at } k = M$

This 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

$\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$

Now, $\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 is $O(M^{2\delta-1})$. Similarly, the space complexity of index is the total length of posting list $O(L) = O(M)$

On 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|)$.

Since 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.

Extending 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.

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.

We 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.

PTC-FR

COX2

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.

Thank 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.

We will correct this line in the final version to avoid confusion and ensure consistency with Figure 1 and the overall description of the model.

What would be the trade-offs in terms of retrieval accuracy, index size, and efficiency.

We 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.

Indexing of CORGII on the PTC-FR dataset takes 46MB and 272s for a million graphs, which is quite modest.

We also compare CoRGII against FHN, showing that CoRGII achieves the same MAP up to 2× faster than FHN on PTC-FR dataset:

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?

We 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.

Below, 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.

PTC-FR

COX2

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?

We observe that our QPS is much higher.

Dear reviewer DMJr,

First, we would like to thank you for your review. We found it really insightful.

Lately, we realized that we could have better answered your question on multi-level quantization

Have you considered using more than one bit per element of z (i.e., multi-level or quantized discretization) to increase accuracy?

We performed experiments and observed the following results.

We observe that multiple bits improve the performance. There results indicate that there is a sweet spot around 3 bits, which provides very good tradeoff. In Appendix F.1, we already provided results in a figure format in more detail.

We would like to thank the reviewer for their comment, which will improve our paper

The method relies on a pre-trained GNN.... the effect of the specific data used to train IsoNet

We 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.

Since 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.

However, 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.

To 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. _ denotes places where the method is unable to achieve target MAP.

k/C values for PTC-FR

k/C values for COX2

Even if we use IsoNet embeddings trained on other datasets, CORGII beats baselines. Moreover, it is more robust with respect to changing those embeddings.

CORGII scores, as well as the baselines, are reranked by IsoNet?

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.

It 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.

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.

In 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.

Through two experiments, we further show that the superiority of our method holds true even if we use different embeddings.

(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).

Following 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.

k/C for PTC-FR

k/C for COX2

We observe that our performance is better, regardless of using the nature of embeddings.

(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:

k/C for PTC-FR

k/C for COX2

We observe that our performance is better, regardless of using the nature of embeddings.

[A] Graph Matching Networks for Learning the Similarity of Graph Structured Objects. Li et al, ICML 2019.

cost of CORGII in comparison with FHN

FHN 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. In 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

Suppose 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$.

$\int _{1} ^M f(k)dk = 1 \implies A\frac{M^{1-\delta}}{(1-\delta)} - \frac{A}{1-\delta}=1$

Since $M$ is large, we have $A = O(M^{\delta-1})$

Let the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have:

$\frac{LA}{k^{\delta}} = 1 \text{ at } k = M$

This 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

$\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$

Now, $\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)$

Indyk 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|)$.

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. CORGII is also fast in practice.

FHN, a single-vector method, outperforms IVF-multi and DiskANN-multi

IVF-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.

On the other hand, FHN is specifically designed for hinge distance. Therefore, despite single vector based representation, it performs better.

An alternative is to rely on relaxed distributions. [1].

We 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.

Below, we report the MAP values on the PTC-FR dataset under different $k/C$ ratios:

We observe that the results are comparable.

clarification

Line 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.

Dear Reviewer R7bo,

I kindly ask that you take a moment to review the author responses, including their replies to other reviewers’ comments, and acknowledge them by clicking the “Mandatory Acknowledgement” button. It is very important that you read the reviews and discuss any disagreements or concerns during this author-reviewer discussion phase so we can work toward a well-informed consensus.

Thank you again for your time and contributions.

Best, AC, NeurIPS 2025

We would like to thank the reviewer for their comment, which will improve our paper

It is not clear what is meant by "dense graph representation".

In 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".

In 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.

A multi-vector representation .. seems significantly more computationally expensive than single-vector-based continuous graph representations. How does the proposed CoRGII compensate ...?

There are two key technical challenges in any graph search (and any information retrieval) system:

1. 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.
2. 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.

Many contemporary search systems are built as a cascade of a retriever (the first stage) and a reranker (the second stage).

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. 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.

CORGII 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.

Indeed, 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.

Specifically, 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.

In this regard, no empirical results, theoretical complexity analysis being provided.

We fix MAP at target levels $m^*$ and compare retrieval time required by different pipelines on PTC-FR, while maintaining comparable accuracy.

First, we compare CoRGII against FHN, showing that CoRGII achieves the same MAP up to 2× faster than FHN:

Next, 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.

Thus, 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.

Notably, 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.

We 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:

Suppose 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$. $\int _{1} ^M f(k)dk = 1 \implies A\frac{M^{1-\delta}}{(1-\delta)} - \frac{A}{1-\delta}=1$ Since $M$ is large, we have $A = O(M^{\delta-1})$ Let the aggregated length of posting lists is $L$. Then, assuming the $M$-th popular token will occur only once, we have: $\frac{LA}{k^{\delta}} = 1 \text{ at } k = M$ This 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 $\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$ Now, $\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 is $O(M^{2\delta-1})$. Similarly, the space complexity of index is the total length of posting list $O(L) = O(M)$

In 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|)$.

Since 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.

We also report index construction time and memory usage, both of which remain modest and practical across datasets, supporting the scalability of CORGII.

The reason behind the use of Chamfer score instead of permutation-based node alignment ... not exactly obvious.

When $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.

But, 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.

To 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.

... 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.

Even 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.

This can be further enhanced by using the following modification of the impact scores

\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)) \mathbf{1}(\hat{z} _q(u) \in \omega(G _c))$$ Here, $\lambda$ is a hyperparameter which is more than 1 and is only applied if $\hat{z} _q (u)$ is a rare token.

I thank the authors for taking my comments into account and preparing a rebuttal, which addresses a number of my concerns. Below, I provide my response to their rebuttal.

1. So, is the difference between dense vs sparse in the usage of discrete vs continuous-valued tokens? In their response, the authors mention that in sparse indices, the number of document (IDs) is "vastly" smaller than the corpus size. "Vastly" is a relative term and is not quantitatively defined. How big of a difference does there need to be in order to qualify as vast? For instance, in LSH, the number of hash buckets can be chosen to also be vastly smaller than the corpus size, but this does not make LSH a sparse indexing method. Although I get the sense, it is important to be precise about these terminologies. Further, I understand the usage of sparse vs dense indices in the context of text. However, the authors borrow this idea from text retrieval and apply it to graphs, so it needs to be defined in the context of graphs too.

2. The provided explanations, supported by the empirical and theoretical results showing the accuracy-efficiency trade-off of CORGII in conjunction with single and multi-vector reranking addresses my concerns.

3. The motivation behind the usage of Chamfer distance is now clear. However, it would be good to have an estimate on the error that is incurred due to conversion from continuous to discrete, bit-like representations, or at least a proposed strategy on how an estimator might be designed for this purpose. Otherwise, it is difficult to gauge a priori the downstream impact of this conversion in the form of lost recall.

4. I am not entirely convinced by the strategy that the authors proposed for learning the impact score function with rare label types. Although the authors propose a canonical way of upweighting the impact function for rare label types, a common practice for dealing with label imbalance, it is well known that simple reweighting often does not resolve the issues posed by imbalance [1, 2, 3]. Additionally, contrastive learning (which is essentially the form that the proposed ranking loss admits) is known to have high sample complexity with increasing dimensionality [4]. I am not looking for the authors to provide solutions to these in this work as they could constitute independent research questions, but there needs to be discussions on these as potential challenges / limitations.

In view of these, I presently choose to retain my score.

References:

[1] Duggal et al., "HAR: Hardness Aware Reweighting for Imbalanced Datasets", IEEE International Conference on Big Data 2021.

[2] Yu et al., "A Re-Balancing Strategy for Class-Imbalanced Classification Based on Instance Difficulty", CVPR 2022.

[3] Luo et al., "Revive Re-weighting in Imbalanced Learning by Density Ratio Estimation", NeurIPS 2024.

[4] Alon et al., "Optimal Sample Complexity of Contrastive Learning", ICLR 2024.

Dear reviewer d1NF,

We thank you for your interest and detailed response to our rebuttal. We agree that the issues you raised require further clarification, which we provide below.

(1) Dense vs Sparse; "vastly"

We agree with you that “vastly” was imprecise and should be avoided. Note that an index built on a corpus is described as “sparse” or “dense” depending on the way in which the corpus is presented to the indexer and not whether the index itself is sparse or dense.

Suppose the raw textual vocabulary size is $10^4$ tokens, and there are $10^7$ documents. Then the document-term matrix is $10^7 \times 10^4$, with $10^{11}$ elements. Each document may typically have very small number of terms (by Zipf law, as also discussed in our theoretical analysis). This results in “sparse” matrix. However, we could not find any folklore threshold of sparsity in the Information Retrieval literature. An inverted index built from this matrix is traditionally called a “sparse index” (but sparsity arises from the source: the sparse input matrix).

Now suppose each document is converted into a 768-dimensional real vector using BERT. All elements in such a vector are expected to be nonzeros. The corpus can now be represented using a $10^7 \times 768$ matrix, which is completely filled with nonzeros, and therefore classically called a “dense” matrix. The columns of this matrix are completely dense. An approximate nearest neighbor (ANN) index built from this matrix (be it an LSH, or a HNSW) is called a “dense index”. One cannot gainfully build an inverted index from this matrix using columns as pseudo-"words" because every pseudo-word would have occurred in every document.

In the context of graphs, our usage of the term “sparse indexing”, inherits from the conventional usage in text retrieval, where it refers to discrete token-based lookup structures such as inverted indices. In contrast, “dense indexing” operates over continuous vector spaces, such as might be obtained as direct outputs of a GNN.

(3) However, it would be good to have an estimate on the error... gauge a priori the downstream impact

Final recall computation requires impact score and multiprobing. We agree that, it would be useful to gauge the effect of Chamfer before going to that stage. Toward that goal, we provide the following error based estimator to evaluate the efficacy of Chamfer without measuring recall.

We compute ground-truth distance $\text{dist}^*$, distance $\text{dist} _{\text{soft}}$ under soft permtuation and Chamfer distance $\text{dist} _{\text{chamfer}}$ (as defined in the paper, see equation 4 there):

$\text{dist}^* = \min _{\mathbf{P}} \sum _{i, j} \big[ \mathbf{A} _q - \mathbf{P} \mathbf{A} _c\mathbf{P}^{ T} \big] _+[i, j]$

$\text{dist} _{\text{soft}} = \sum _{i, j} \big[ \mathbf{Z} _q - \mathbf{P}^{\text{soft}}\mathbf{Z} _c \big] _+ [i, j]$

The following table shows that $\text{dist}^*$ is better approximated by $\text{dist} _{\text{chamfer}}$ than by $\text{dist} _{\text{soft}}$.

(4) Discussion on label imbalance, sample complexity

Many thanks for pointing out these references [A-D], listed below. We can adapt some of these proposals to enhance impact score computation as follows. Consider the resampling or re-balancing algorithm proposed in [A]. At each iteration $t$, we use a sampling procedure, formulated as a multinomial distribution Multinomial$(D ^t)$ over all corpus items (with $D^t = [D _c ^t : c\in C]$) over difficulty estimates $D _c ^t$ of tokenizing the graphs arising due to presence of rare tokens. Then, we re-train or fine-tune the tokenizer GTNet on graphs sampled from this distribution. In this case, we can compute predictions of tokens as $z^{(t)} (u)$ for each node $u$. Then, we leverage the prediction variations $z^{(t)}(u)-z^{(t-1)}(u)$ (and their signs) to compute difficulty for each node. Then, we can aggregate these difficulty across nodes to compute difficulty $D _c ^{(t)}$ for $G _c$. We can also compute $\text{Impact}(z ^{(t)} (u), h)\cdot\mathbf{1}(z ^{(t)} (u) \in \omega(G _c))- \text{Impact}(z ^{(t-1)} (u), h) \cdot \mathbf{1}(z ^{(t-1)} (u) \in \omega(G _c))$ as a proxy difficulty per node. This would be a more principled alternative to our earlier proposal involving $\lambda$.

The paper [B] assigns suitable weights $\alpha(x,y)$ on the loss per each instance. It would be an interesting research problem to design $\alpha(z (u) , G _c)$, similar to [B]. A key challenge in immediately adapting [B] is that we may need to estimate $P(G _c | z(u))$ as used in Eq. (2) in [B], which would pose an interesting research question.

Discussion of Alon et al. [C] Contrastive training is ubiquitous in dense retrieval, starting from such classic papers as DPR [Karpukhin et al., 2020 arXiv:2004.04906], ANCE [Xiong et al., 2021 arXiv:2007.00808], and RocketQA [Qu et al., 2021 arXiv:2010.08191]. Further enhancements were reported in COIL [Gao et al., 2021 arXiv:2104.07186], SimCSE [Gao et al., 2021 arXiv:2104.08821] and GTR [Ni et al., 2021 arXiv:2112.07899]. Alon et al. [C] provide extremely insightful observations on the sampling complexity of contrastive learning from a PAC point of view. They show that, for contrastive training, with $n$ points in $d$ dimensionl space, $\widetilde{\Omega}(\min\{nd, n^2\})$ samples are needed. They do 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 a demand for large separation, then the lower bound drops to $\widetilde{\Omega}(n)$. 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 $\ge (1+\epsilon)$ times farther than near points) should fall into other buckets (Hamming distance $\ge 1$). It is possible that this is what makes contrastive training work well in retrieval applications. It would be of great interest to collect empirical evidence for or against this hypothesis.

We thank the reviewer for pointing us to these intriguing recent works [A,B,C,D], and we will be sure to include a discussion in our manuscript (Neurips allows an extra page in camera ready. Therefore, we plan to include this discussion in the main, if our paper gets accepted)

[A] Yu et al., "A Re-Balancing Strategy for Class-Imbalanced Classification Based on Instance Difficulty", CVPR 2022.

[B] Luo et al., "Revive Re-weighting in Imbalanced Learning by Density Ratio Estimation", NeurIPS 2024.

[C] Alon et al., "Optimal Sample Complexity of Contrastive Learning", ICLR 2024.

[D] Duggal et al., "HAR: Hardness Aware Reweighting for Imbalanced Datasets", IEEE International Conference on Big Data 2021.

We thank the reviewer for the comments, which will improve our paper.

empirical exploration of probing strategies.

We 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.

We see that single probing cannot trade off between accuracy-efficiency effectively. 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.

Some technical sections are dense, and concepts like latent vocabulary structure, token reuse, or token collisions could be elaborated for better accessibility.

In 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.

pre-trained GNNs ... clarifying the extent to which performance depends on pretraining quality would be beneficial.

We 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. Since the tokenizer operates without any pre-trained GNN, the resulting index ― built solely on the tokens ― is also independent of pre-trained embeddings.

Only 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:

1. Instead of pre-trained embeddings $h$, we use $x$ to as input to the impact scoring model (Impact($\tau,x$), Eq. 8).
2. 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.

Following 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.

The efficiency does not change much and even if we do not use pre-trained embeddings, our method outperforms baselines.

... validate scalability claims.

We perform experiments with noisy graphs, which results in $\sim 10\\%$ noise in the embedding space. We 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.

We 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.

Regularization, Interpretability

To 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.

We can impose a regularizer to enhance more sparsity in $\hat{z}$ embeddings, which can control the above rank correlation for PTC-FR.

Our 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.

qualitative or visual analysis of the token distribution?

In Fig. 14 in Appendix, we showed this qualitative analysis. Here, 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 descending order of unique token count for PTC-FR.

Similar 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)

Are tokens reused across similar subgraphs

As 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.

What is trade off between vocabulary size and retrieval efficiency

We 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.

There 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.

How would CORGII handle temporal graphs, where node connectivity evolves?

This 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.

[Moffat1996] [Managing Gigabytes: Compressing and Indexing Documents and Images]

[Buttcher2006] [Hybrid index maintenance for growing text collections]

[Lester2005] [Fast On-Line Index Construction by Geometric Partitioning]

There 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.

Is the framework compatible with privacy-preserving representation?

We 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$.

Dear reviewer WWoV,

We discovered minor errors in some rebuttal tables. Due to the image restriction, we converted scatter plot pickle files into tables using a script. A small bug was found and fixed near the deadline, but we accidentally pasted the older version of the table in the rebuttal.

Therefore, we are reaching out to you immediately after the discussion windows open.

For clarity, we present the erroneous and corrected results in response to An empirical exploration of probing strategies below:

Recall that all the numbers are the maximum MAP reached until the given k/C value (PTC-FR)

These corrected results further reinforce the importance of Cooccurrence Multiprobing (CM). Notably, Appendix F.1 already shows these correct numbers in figure form, where Single Probe and HM (r=1) fail to improve MAP beyond 0.38 and 0.41 after k/C = 0.6 and 0.7, respectively.

In response to ... validate scalability claims.:

PTC-FR

COX2

These results show that our method is robust to noisy graph inputs.

Please also note that we had initially misunderstood what you had meant by token reuse and collisions. We now understand that you mean token collision by token matching. We fully agree with you. If our paper gets accepted, we will get one extra page, where we can elaborate the preliminaries and will also expand Appendix.