When a language model answers questions over a large text-attributed graph (a graph whose nodes carry passages of text, such as a citation network or a knowledge base), the graph has to be shrunk before it fits in a prompt. The cheapest way to shrink it is once and offline, before any question arrives. This query-agnostic approach lets the compressed graph be cached and reused, but it has a known cost: the compressor cannot know which facts a future question will need. We argue that this cost is concentrated in one place. It falls on connector nodes, the intermediate entities on a multi-hop answer path that share no words with the question. Today's pipelines delete them twice. Offline compression drops them because they look generic, and query-time pruning drops them because their text does not match the query.
This note proposes an offline compressor built to protect those connectors. It does two things. First, it decides which nodes to keep by how often they sit on answer paths for a large synthetic set of deliberately reworded questions, rather than by text similarity, degree, or community structure. Second, it gives every kept node an embedding that absorbs vocabulary from its graph neighborhood, so that at question time the node is no longer invisible to a cheap similarity search. The claim is testable and specific. At a fixed prompt budget, most of the accuracy lost by query-agnostic compression should come from questions with a vocabulary gap along the answer path, and the proposed compressor should recover that loss mainly on those questions.
Core Claim
Three bodies of evidence motivate the claim. OSCAR, a soft compressor that turns retrieved passages into a few dense vectors, reports that removing the query from compression costs about 6% accuracy (OSCAR: Online Soft Compression for RAG). G-Retriever retrieves a subgraph by scoring each node's text against the question with frozen SentenceBERT. It then solves a Prize-Collecting Steiner Tree (PCST), which picks a small connected subgraph that collects high-relevance "prizes" while paying a cost per included edge (G-Retriever). A connector with no textual overlap earns almost no prize, so the tree survives only if the optimizer routes through it by accident. RSF-GLLM shows that bridging these "semantic voids" on triplet knowledge graphs requires shifting weight from text similarity toward graph structure during the early hops (RSF-GLLM). WikiQA shows the gap is common: 20.3% of correct answers share no content words with the question (WikiQA).
The closest existing method is HS2C, which compresses text-attributed graphs offline by minimizing structural entropy to find homophilous communities and then having an LLM summarize each community. It reports a 94.98% scale reduction on ogbn-arxiv with 3.06–4.92% accuracy gains over random sampling (HS2C). HS2C optimizes for node classification and community coherence. A connector that links two communities is exactly what community summarization smooths away, and HS2C never measures robustness to reworded questions. Our compressor targets multi-hop question answering under vocabulary mismatch, keeps nodes for their path-carrying role, and is evaluated by stratifying on lexical overlap. RSF-GLLM differs in another way: it is query-guided at inference and runs a learned recurrent flow per question. We keep all learning offline and leave only k-nearest-neighbor search plus PCST at query time.
Research Program
The compressor has three offline stages and a cheap online stage.
The first stage builds a synthetic workload. From the training portion of the graph, we sample anchor–answer node pairs that lie two to four hops apart. An LLM writes a question that mentions the anchor and asks for the answer. A second rewriting pass then strips every content word that appears in the text of the intermediate nodes or relations. A verifier model checks that the reworded question still determines the same answer. This is not runtime query rewriting, which ECLASS-Augmented Semantic Product Search found can destroy needed specifications. It is offline data generation, and a bad rewrite only adds noise to a statistic.
The second stage scores and prunes nodes. For each synthetic question $q$, we solve PCST with oracle prizes on the anchor and the answer only, and record the resulting tree $T_q$. A node's bridge score is
$$ b(v) = \frac{1}{|Q|}\sum_{q \in Q} \mathbf{1}[v \in T_q] \cdot w(q), $$
where $Q$ is the synthetic workload and $w(q)$ upweights questions with zero lexical overlap with the path. Nodes are retained by $b(v)$ under a node budget, and edges are retained if they appear in any $T_q$. Nodes that are hubs in degree but rarely on answer paths, which is the failure Deriving a Large-Scale Taxonomy from Wikipedia addressed with PageRank and DA-RAG calls "free-riders", get low scores without any hand-set threshold. Retained node texts are shortened by an extractive summarizer to a fixed token budget, which makes this a hard, human-readable compression.
The third stage trains a neighborhood-aware embedding. We fine-tune the node encoder in two ways, borrowing from existing methods. The first is GLEM-style alternation, where the language model learns from structural pseudo-labels and so absorbs topology into its text encoder (GLEM). The second is a GraphFormers-style nested neighbor attention, where a node's text tokens attend to cached neighbor embeddings (GraphFormers). In both cases, the training objective is contrastive on the synthetic workload: a reworded question should score high against every node on its oracle tree, connectors included. The intended effect is that a connector's embedding carries the vocabulary of the questions it serves.
At question time, we embed the question, compute prizes against the cached embeddings of the compressed graph, run PCST, and feed the subgraph to a frozen generator. We use G-Retriever's interface, a textualized subgraph plus a GNN soft prompt, so that the only change is the compressed index and its embeddings.
Baselines
The naive reference point is no compression: the full k-hop neighborhood textualized into the prompt, truncated to the generator's window. This reveals whether pruning helps accuracy at all or only saves tokens. G-Retriever reports a 99% token reduction on WebQSP relative to such verbalization.
The strongest query-agnostic competitor is HS2C-style compression, meaning structural-entropy partitioning plus community summaries. We will reimplement it at the same retained-token budget and feed it through the same query-time retrieval and generator. We beat it if we achieve higher Hit@1 at equal budget, with the margin concentrated in the zero-overlap stratum.
The strongest query-guided reference is G-Retriever on the uncompressed graph. Its file-reported results are relative only: it improves 30.8–40.6% over GraphToken, and removing its GNN encoder costs 22.5%. No absolute WebQSP Hit@1 for G-Retriever was found on Lacuna, so we will rerun it. RSF-GLLM reports 90.45% Hit@1 on WebQSP at about 0.25 s per question. We treat it as the ceiling for learned query-guided pruning and run it from its released setup if available. We do not expect to beat it. The success criterion is to recover at least half of the gap between HS2C-style compression and uncompressed G-Retriever at a 10% node budget, with no additional query-time learning. For CWQ, no reported RSF-GLLM Hit@1 number was found on Lacuna.
Two ablations isolate the ingredients. The first swaps bridge-score pruning for PageRank, degree, and random pruning while keeping our embeddings. The second keeps bridge-score pruning but swaps our embeddings for frozen SentenceBERT and for the mean of neighbor SentenceBERT vectors. All systems share the generator (frozen LLaMA-2-7b, as in G-Retriever), the same training split for any offline fitting, the same retained-token budget, and an equal hyperparameter search budget.
Why not just…?
Why not just compress at query time, as G-Retriever or QUITO do? Query-guided compression is better per question. OSCAR's 6% gap and QUITO's 58.9% versus 41.2% for LongLLMLingua on NaturalQuestions at 2x both point that way (QUITO). The argument for the offline regime is cost: one cached index serving many questions with only nearest-neighbor search and PCST at query time. This alternative is a real threat. If uncompressed query-time G-Retriever matches our accuracy at equal latency and memory, the offline index has no point. We will report accuracy against measured per-question latency and index memory, so the comparison is decided on those axes and not on accuracy alone.
Why not just expand each node's text with pseudo-queries, as MINDER does for passages? MINDER represents each passage by titles, substrings, and generated pseudo-queries to bridge the query–identifier gap (Multiview Identifiers Enhanced Generative Retrieval). Pseudo-queries generated from a connector's own text describe that connector. They do not resemble a question about an answer two hops away, so this approach fixes vocabulary gaps at the endpoints but not at intermediate nodes. We include it as a baseline, applying pseudo-query expansion to node text under the same budget. Our prediction is that it matches us on endpoint-mismatch questions and loses on connector-mismatch questions.
Why not just average neighbor embeddings instead of training a structure-aware encoder? Mean pooling is free and does import neighbor vocabulary. It is the ablation we take most seriously. Its expected weakness is that hubs dilute it and stacked averaging over-smooths it, the problem that motivated GraphFormers' learned neighbor attention. GraphFormers reports 2.9–6.5% gains over cascaded encoder-then-GNN pipelines. If mean pooling ties our trained encoder, we will drop the encoder and report that the contribution lies in the pruning score alone.
Why not just rewrite the user's question to match graph vocabulary, as RaFe does? RaFe trains small rewriters from reranker feedback and gains 2–3% QA accuracy on flat text retrieval (RaFe). A rewriter cannot invent the name of a connector it has never seen. ECLASS also shows that rewriting can strip constraints. We will run a RaFe-style rewriter in front of the HS2C baseline to test whether rewriting closes the same gap our method targets.
Proposed Experiments
The main benchmarks are WebQSP and the other GraphQA tasks, ExplaGraphs and SceneGraphs, from G-Retriever, along with CWQ for 3–4 hop compositions. We also use ogbn-arxiv as a text-heavy graph, posing questions built from held-out citation chains. Every test question is tagged by lexical overlap between the question and the intermediate nodes of its gold path, following the WikiQA content-word measure. We also build a stress split by rewording test questions to remove that overlap, using a different LLM from the one that generated the training workload, which limits style leakage.
The decisive check is the stratified gap. The proposal is supported only if two things hold. The accuracy drop from uncompressed G-Retriever to HS2C-style compression must be markedly larger on the zero-overlap stratum, and our method must recover most of its gain there. If gains are uniform across strata, the vocabulary-gap explanation is wrong, even if accuracy improves.
A second check addresses workload mismatch. We generate synthetic questions using only a subset of relation types and test on questions whose paths use held-out relation types. This measures how much of the benefit depends on anticipating the question distribution, which is the honest limit of any query-agnostic method under the rate–distortion argument in the file.
A third check reports the full curve of node budget against Hit@1, query latency, and index memory, against both the no-compression reference and query-time G-Retriever. This shows where, if anywhere, offline compression is the better trade.
References
- OSCAR: Online Soft Compression for RAG
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering
- RSF-GLLM: Bridging the Semantic Gap in Multi-Hop Knowledge Graph QA via Recurrent Soft-Flow and Decoupled LLM Generation
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression
- ECLASS-Augmented Semantic Product Search for Electronic Components
- Deriving a Large-Scale Taxonomy from Wikipedia
- DA-RAG: Dynamic Attributed Community Search for Retrieval-Augmented Generation
- Learning on Large-scale Text-attributed Graphs via Variational Inference
- GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph
- QUITO: Accelerating Long-Context Reasoning Through Query-Guided Context Compression
- Multiview Identifiers Enhanced Generative Retrieval
- RaFe: Ranking Feedback Improves Query Rewriting for RAG