Borrowing Words from Neighbors: Graph-Propagated Lexical Enrichment for Retrieval

Search systems miss relevant documents when the searcher and the author use different words for the same thing. This is the vocabulary mismatch problem. Dense retrievers, which turn queries and documents into vectors and match them by similarity, were supposed to solve it. In practice they often drop rare but decisive words, such as names, codes and technical terms. In many collections, though, documents do not stand alone. Papers cite each other, products sit in taxonomies, and cases cite precedents. A paper's neighbors often describe it in vocabulary the paper itself never uses, and that vocabulary is frequently the searcher's.

We propose to make this concrete and testable. Every document vector is translated into a weighted list of words, which shows what the retriever "thinks" the document is about. These word lists are passed along graph edges. A gate then adds back to each document only the rare words its neighbors share but the document lacks. All of this happens offline, at indexing time, so query-time cost does not change.

The claim is narrow and falsifiable. Graph neighbors carry vocabulary that closes the lexical gap, and this information is lost when structure is used the usual way, either as averaged dense vectors or as raw concatenated text.

Core Claim

Two findings motivate the idea. The first is What Are You Token About?. It projected dense retrieval vectors into vocabulary space through a frozen masked-language-model head, the layer that predicts words from hidden states. It found "token amnesia": dense vectors forget rare tokens. It repaired this with Lexical Enrichment, which adds the inverse-document-frequency-weighted (IDF-weighted) embeddings of a document's own tokens back into its vector. That repair can only restore words the document already contains. It cannot supply the colloquial or adjacent-field words a searcher uses.

The second finding comes from hybrid text-graph models such as GraphFormers and GLEM. They show that neighbor text improves node representations. Nobody has asked what message passing does at the level of individual words: whether it propagates missing words or smooths away the rare ones.

Our hypothesis is that the outcome depends on where propagation happens. Averaging neighbor dense vectors should make amnesia worse, because rare-token directions cancel. Propagating gated vocabulary distributions should cure it, because the gate keeps exactly the tokens that are concentrated in the neighborhood and absent from the document.

Mechanism

Let $E(d)$ be the dense vector a retriever assigns to document $d$. Let $p_d = \mathrm{softmax}(W E(d))$ be its distribution over the vocabulary, where $W$ is the frozen projection head from Ram et al. For neighbors $\mathcal{N}(d)$ in the corpus graph, with edge weights $w_{du}$ (uniform, or personalized-PageRank weights as in RTA), we compute two quantities. The neighbor evidence $r_d(t) = \sum_{u \in \mathcal{N}(d)} w_{du}\, p_u(t)$ measures how strongly the neighborhood points to token $t$. The gate $g_d(t) = \max(0,\, r_d(t) - \beta\, p_d(t))$ keeps only tokens the neighborhood emphasizes more than the document does. Here $\beta$ is a scalar, and $g_d$ is truncated to its top $k$ tokens.

The enriched index vector is

$$v_d = E(d) + \lambda \sum_{t} g_d(t)\, \mathrm{idf}(t)\, x_t,$$

where $x_t$ is the single-token embedding of $t$ produced by the same encoder, $\mathrm{idf}(t)$ is the token's inverse document frequency in the corpus, and $\lambda$ sets the strength of enrichment. Queries are encoded unchanged. This mirrors the real asymmetry of search: queries have no graph, but documents do.

The top-$k$ truncation and the IDF weighting are the direct answer to the "attribute noise" result in ECLASS-Augmented Semantic Product Search. There, appending full attribute text ("Advanced") did worse than appending a minimal subset ("Basic"). In a second stage, we replace the hand-set gate with a small learned gate. It is trained contrastively with citation-walk hard negatives from BiCA. In that setup the graph is used both to train and to index, whereas BiCA uses it only to mine training pairs.

Research Program

The work has three parts.

The first part is diagnostic. We take query–relevant-document pairs and select those where the query shares no content words with the document, the regime Yang et al. showed is common in open-domain question answering. For each pair we measure query-term recall in the document's vocabulary distribution $p_d$ under three conditions. The first is the document alone. The second is after dense-space neighbor averaging, which is a GNN-style step. The third is after gated vocabulary-space propagation. This directly tests whether message passing alleviates or worsens token amnesia, and the result is useful whichever way it comes out.

The second part is the training-free method above. It is applied to off-the-shelf retrievers: DPR, S-MPNet, GTE, and BiCA itself.

The third part is the learned gate, plus a robustness analysis on heterophilic or noisy edges. We compare citation edges with degree-preserving shuffled edges, and we inject edges at increasing rates. The goal is to find out when structure stops helping, a concern raised for heterophilic graphs by Wu et al. and RTA.

The test beds are chosen so that a real graph exists. The scientific subsets of BEIR qualify: SCIDOCS, SciFact, TREC-COVID and NFCorpus. For these we build citation graphs from paper metadata, as BiCA did through PubMed. The resulting graphs are partial, so we report edge coverage per corpus. The Phoenix Contact ECLASS catalog of 10,346 products gives a taxonomy graph with documented novice–expert vocabulary mismatch. The DBLP citation graph from GraphFormers gives a large-scale check of title-to-paper retrieval.

Baselines

The naive reference points are BM25 and the unmodified dense retriever. BEIR shows BM25 is often hard to beat out of domain. On the ECLASS expert queries, BM25 reaches 31.4% Hit_Rate@5, against 94.3% for the taxonomy-augmented, reranked pipeline (ECLASS).

The closest existing method is Lexical Enrichment applied to the document's own tokens (Ram et al.). It reports BEIR nDCG@10 rising from 21.4 to 26.4 for DPR and from 43.1 to 44.1 for S-MPNet. It is the strongest competitor because our method differs from it in only one respect: where the added tokens come from. We run it with identical $\lambda$ and top-$k$ tuning budgets on the same validation splits. Beating it means a statistically significant nDCG@10 gain on the graph-bearing subsets, concentrated in the zero-overlap queries.

The strongest graph-trained retriever is BiCA, which reports 0.518 average nDCG@10 on BEIR against 0.486 for GTR-xxl (BiCA). We apply our enrichment on top of BiCA's encoder. A gain there shows that using the graph at indexing time adds something beyond using it at training time. For the individual SCIDOCS, SciFact or TREC-COVID scores of BiCA and our other baselines, no reported result was found on Lacuna, so we will rerun every system on those corpora ourselves.

The key ablation propagates in dense space instead of vocabulary space: we add $\lambda$ times the mean neighbor vector. If this matches our method, the vocabulary-space machinery is unnecessary. A second control runs the same pipeline over shuffled edges, which separates the effect of the graph from that of extra tokens. A third baseline appends neighbor titles to document text before encoding, the cascaded approach of Alternative 4. All systems share the same encoder checkpoints, corpora and validation-based tuning grid.

Why not just…?

Why not just append neighbor text to each document before encoding? It is cheaper conceptually, and it is the obvious way to use neighbors. But the ECLASS study found that adding more structured text degraded dense similarity. Concatenation also cannot choose which neighbor words matter. The concatenation baseline above will settle the question. If it matches gated propagation on the zero-overlap queries, our gate adds nothing, and we will report that.

Why not just expand documents with LLM-generated pseudo-queries? This is the most serious threat. MINDER shows that synthetic queries as an extra document view improve generative retrieval, reaching 65.8 Hits@5 on NQ against 61.3 for SEAL. A generator can invent searcher vocabulary without any graph. Its weakness is that it is limited by what the generator already knows, and specialized domains are where generators fail, as the drift in ECLASS's rewriting experiments suggests. Neighbor vocabulary comes from real authors in the field. We will run pseudo-query expansion at a matched token budget, alone and combined with ours. If pseudo-queries dominate on every corpus and adding ours gives no further gain, the graph claim fails. If the two are complementary, that is the expected finding on technical corpora.

Why not just rewrite the query instead? Query-side methods such as RaFe and InteR do bridge gaps; InteR reports 50.0 MAP on TREC DL'19 against 30.1 for BM25. But they add work at query time. On specialized catalogs, ECLASS found that rewriting removed constraints. Our method costs nothing at query time and can be combined with any rewriter. We include a RaFe-style rewriter as an orthogonal comparison on the ECLASS catalog.

Why not just fuse a GNN into the encoder, as GraphFormers does? Deep fusion requires neighbor sampling and joint training. More importantly, it cannot be applied to a query, which has no neighbors, without architectural changes. GraphFormers is a reference ceiling on DBLP only, where it was designed to run.

Decisive Checks

The diagnostic must show that gated vocabulary propagation raises query-term recall in $p_d$ on zero-overlap pairs, while dense-space averaging does not. Otherwise the mechanism is wrong.

Retrieval gains over document-only Lexical Enrichment must be concentrated in zero-overlap queries, and they must disappear under shuffled edges. Otherwise the gain is generic token padding.

The method must still add to BiCA and to pseudo-query expansion. Otherwise structure at indexing time is redundant with structure at training time or with generated text.

We report nDCG@10 for BEIR subsets, Hit_Rate@5 and MRR for ECLASS, and P@1 and MRR for DBLP, all with paired significance tests and with indexing-time cost.