Retrieval-augmented question answering fails in a characteristic way when the question and the evidence use different words. A system that looks up evidence by embedding similarity finds the passage that sounds like the question. It then misses the fact that actually answers it, which is phrased in domain jargon or reached only through an intermediate fact. We propose to recover those missing facts from structure rather than wording. Knowledge is stored as n-ary facts: single records that bind several entities, together with qualifiers such as time, place, or role. From the few facts that similarity search finds confidently, a random walk over the fact–entity graph spreads relevance to facts that share participants with them, even when those facts share no words with the query. A penalty on hub entities, the generic connectors that appear in thousands of facts, keeps the walk from drifting toward generic context.
The claim is specific and falsifiable. Structural propagation over n-ary facts helps most on exactly the questions where the query and its gold evidence share few content words, and that benefit comes from reaching facts that are absent from the dense retriever's candidate pool. It does not come from reordering the facts already in that pool. If the gain is flat across levels of word overlap, or if a strong reranker applied to the dense candidates matches it, the idea is wrong.
Core Claim and Positioning
Three lines of prior work leave this particular combination open. HyperGraphRAG builds an LLM-extracted knowledge hypergraph, a graph whose edges can join any number of entities. It stores the hypergraph as a bipartite graph in which facts and entities are both nodes, retrieves entities and facts by dense similarity, and then expands to every neighbour without ranking or pruning. This paper supplies our representation and our strongest baseline. Our contribution is to replace its unranked expansion with a query-personalized, hub-penalized ranking.
G-Retriever selects a connected subgraph with a Prize-Collecting Steiner Tree, which trades relevance "prizes" against the "cost" of the edges needed to connect them. It reports large drops in tokens and hallucination, but it works only on pairwise graphs. A Systematic Exploration of Knowledge Graph Alignment finds that node centrality is the dominant factor in how well an LLM reasons over a linearized graph. Its analysis covers binary triples only, and it assumes retrieval has already succeeded. Together these two papers motivate the proposal: structure-aware selection and central "anchor" nodes matter. Neither tests n-ary facts, and neither tests the case where retrieval is hard because of vocabulary mismatch.
The main constraint on our design comes from GoWvis. It argues that PageRank over word graphs is distorted by high-degree hubs and that k-core decomposition finds the cohesive nucleus more reliably. A k-core is the largest subgraph in which every node has at least k neighbours. Under a lexical gap, the entities that bridge the query to distant evidence are often exactly such generic hubs, so a naive walk would flood the context with them. Hub suppression is therefore part of the method, not an optional refinement. Whether degree-penalized walks or a hypergraph k-core filter does this better is one of our empirical questions.
The last group of prior work concerns the lexical gap itself. SciTaiL and NSnet bridge it by decomposing text into flat tuples. FacTree grounds question phrases to n-ary KG facts through parse trees and Sentence-BERT. Hierarchical Lexical Graph routes retrieval through topic clusters. All of these close the gap on the query side, by parsing or rewriting it, and SciTaiL attributes 35% of errors to parsing failures. We close it on the evidence side, using structure, and we leave the query untouched.
Research Program
We reuse HyperGraphRAG's construction. An LLM extracts n-ary facts from the corpus, each fact carries its natural-language description, and the result is stored as a bipartite incidence graph between entities and facts. Given a query, a dense encoder scores every fact's description. The top $m$ facts form a normalized restart vector $r$, which is deliberately small and high-precision.
We then run a personalized random walk that alternates between facts and entities:
$$ p_{t+1} = (1-\beta)\, r + \beta\, P_{EF}\, D_E^{-\gamma}\, P_{FE}\, p_t . $$
Here $p_t$ is the relevance mass on facts at step $t$. $P_{FE}$ moves mass from each fact uniformly to its participating entities, and $P_{EF}$ moves mass from each entity uniformly to the facts it appears in. $D_E$ is the diagonal matrix of entity degrees (the number of facts each entity belongs to), and $\gamma \ge 0$ controls how strongly hubs are damped. $\beta$ is the probability of continuing the walk rather than restarting. With $\gamma=0$ this is ordinary personalized PageRank on the incidence graph. With $\gamma>0$, a hub passes little mass onward, so a fact gains score by sharing specific participants with several seed facts, not by sharing a common one.
The mass stays inside whole facts, and this matters. If the hypergraph is clique-expanded into pairwise edges, the walk can mix entities that never co-occurred in a single fact, and that mixing is the lossiness HyperGraphRAG proves binary projection suffers from. As an alternative to degree damping, we implement hub suppression as a hypergraph core filter. The filter iteratively removes entities that participate in fewer than $k$ surviving facts within the query's two-hop neighbourhood, and the walk then runs on the remaining nucleus.
The final score for each fact interpolates its walk mass and its dense similarity. The top facts, together with their qualifiers, are linearized with the highest-scoring shared entities placed first. This ordering borrows the "reasoning anchor" finding from the KG-alignment study. The whole context must fit within a fixed token budget that is shared by every system.
Hybrid semantic-structural embedding plays a deliberately limited role here. We do not use deep fusion in the style of HyperBERT, which mixes hypergraph layers into BERT attention. That approach is expensive and was shown only for node classification on corpora where vocabulary is shared. Instead, we test the cheapest form of hybrid embedding as a competitor: smoothing each fact's embedding over its hypergraph neighbours before dense search. This asks whether structure should live in the representation or in the ranking.
The analysis is built around one measurement. For each question we compute the content-word overlap between the question and its gold supporting evidence, and we report every result stratified into overlap bins. We also build gap-injected variants of the questions. An LLM rewrites each question to remove every content word shared with the gold evidence, and a manual audit of a sample checks that the answer is unchanged. We then record how each method degrades as overlap is forced toward zero.
Baselines
The naive reference point is standard chunk-level dense RAG using the same encoder and the same generator. HyperGraphRAG reports being 7.45 F1 above this baseline on its suite. A pure lexical matcher gives us a second floor. On SciTaiL, n-gram overlap reaches 70.6% accuracy, the same as ESIM, according to SciTaiL. This reminds us that lexical baselines are stronger than they look on data with high overlap, which is why we stratify.
The strongest direct competitor is HyperGraphRAG itself. It uses the same hypergraph, the same dense retrieval, and full bidirectional expansion. It reports LLM-as-judge Correctness of 64.8, Relevance of 66.0, and Factuality of 64.2 on its benchmark suite. We will rerun it on its own released suite, with an identical extracted hypergraph, generator, and context-token budget. We truncate its expansion to the same budget, ordering by similarity, so that the only difference is how facts are selected. Beating it means higher F1 and Correctness overall. More importantly, the margin must grow in the low-overlap bins.
For multi-hop retrieval on binary structure, the reference is GraphAnchor, which reports 32.60 F1 on MuSiQue with Qwen2.5-7B against 18.05 for vanilla RAG. We will run our method with Qwen2.5-7B on MuSiQue for a like-for-like comparison. On n-ary KBQA, the reference is FacTree, which reports 54.4% accuracy on WikiPeopleQA and 40.1% on its three-fact subset. We will compare against these reported numbers, noting that FacTree uses a trained modular pipeline rather than LLM generation.
Four ablations isolate the key ingredient. The first sets $\gamma=0$, removing hub damping. The second replaces the incidence walk with a walk on the clique-expanded pairwise graph, which isolates the contribution of n-ary structure. The third runs G-Retriever's PCST selection on that clique-expanded graph. The fourth ranks by global, non-personalized PageRank, which tests whether query personalization matters. Every variant uses the same seeds, budget, and hyperparameter search. That search covers $m$, $\beta$, $\gamma$, and $k$, tuned on a development split with an equal number of trials for our method and for the tunable baselines.
Why not just…?
Why not just rerank HyperGraphRAG's candidates with a cross-encoder or an LLM judge? This is the most serious threat. On questions whose answering facts are already in the dense top-$k$, a strong reranker may equal or beat us. Our claim is narrower. A reranker scores each candidate in isolation and can only reorder what dense retrieval surfaced, whereas the walk can reach a bridging fact that looks irrelevant on its own. We will measure gold-fact recall at a fixed budget, split into facts inside and outside the dense candidate pool. We will also run the reranker on the union pool, dense candidates plus walk candidates. If reranking the dense pool alone matches us in the low-overlap bins, the structural argument fails and we will report that.
Why not just rewrite the query to close the gap, then use plain dense retrieval? Query rewriting attacks the same symptom from the query side. The file's summary of that line of work notes that rewriting can drift from the user's constraints and invent pseudo-facts, but it gives no numbers. We will include an LLM rewrite-then-retrieve baseline under the same generator, and we will also combine rewriting with our walk. If rewriting alone closes the low-overlap gap, the walk's value reduces to what it adds on top. We expect the two to be complementary, because rewriting improves the seeds and the walk improves how far the seeds reach.
Why not just clique-expand the hypergraph and run PageRank or G-Retriever's Steiner tree? This is the natural reuse of existing binary tooling, and it is one of our ablations. The prediction that separates the two approaches comes from HyperGraphRAG's lossiness result. A pairwise walk can combine entities from unrelated facts, so it should retrieve qualifier-mismatched facts, for example the right people at the wrong time. We will measure this directly as the rate at which retrieved facts violate a question's qualifier constraint, on WikiPeopleQA and on the n-ary questions in the HyperGraphRAG suite. HyperBERT's reported 7.7% drop when its hypergraph layer is replaced by a pairwise GNN is consistent with this prediction, though it comes from a different task.
Why not just bake structure into the embeddings and keep retrieval flat? One step of hypergraph smoothing over fact embeddings is cheap, and it is a fair test of the hybrid-embedding direction. Its limitation is also our hypothesis. Smoothing is query-independent, so it blurs every fact toward its neighbourhood regardless of what is being asked, and it risks the over-smoothing on dense cliques noted for hypergraph GNNs. We run it as a baseline and in combination with the walk. If it matches the walk, the simpler system wins.
Proposed Experiments and Decisive Checks
The main evaluation uses the HyperGraphRAG suite (Medicine; the CS, Agriculture, and Law domains of UltraDomain; and Mix), where the n-ary structure and the strongest baseline both exist. We report F1 and the three LLM-as-judge scores there, alongside gold-fact recall at a fixed token budget. MuSiQue tests whether the method transfers to multi-hop open-domain retrieval over an LLM-extracted hypergraph. WikiPeopleQA, and especially its three-fact subset, tests whether qualifier-preserving selection helps when the facts are curated rather than extracted.
Three results would settle the proposal. First, in the lowest-overlap bin and on gap-injected questions, the full method's gain over truncated HyperGraphRAG must exceed its gain in the high-overlap bin, and most of the added gold-fact recall must come from facts outside the dense pool. Second, hub damping, or the core filter, must beat undamped personalized PageRank. The damping should also lower the fraction of context tokens spent on facts attached to the top 1% highest-degree entities. This would resolve, for n-ary retrieval, the prestige-versus-degeneracy tension between the KG-alignment study and GoWvis. Third, the incidence-graph walk must beat its clique-expanded counterpart on qualifier-violation rate.
If the first check fails, the method is at best a token-saving variant of HyperGraphRAG, and we would write it up as such. If the second fails, the paper becomes a negative result about hub sensitivity in hypergraph retrieval, which the literature currently lacks.
References
- HyperGraphRAG: Retrieval-Augmented Generation via Hypergraph-Structured Knowledge Representation
- G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering
- A Systematic Exploration of Knowledge Graph Alignment with Large Language Models in Retrieval Augmented Generation
- GoWvis: A Web Application for Graph-of-Words-based Text Visualization and Summarization
- SciTaiL: A Textual Entailment Dataset from Science Question Answering
- Bridging Knowledge Gaps in Neural Entailment via Symbolic Models
- Fact-Tree Reasoning for N-ary Question Answering over Knowledge Graphs
- Hierarchical Lexical Graph for Enhanced Multi-Hop Retrieval
- HyperBERT: Mixing Hypergraph-Aware Layers with Language Models for Node Classification on Text-Attributed Hypergraphs
- Graph-Anchored Knowledge Indexing for Retrieval-Augmented Generation