BubbleRAG: Evidence-Driven Retrieval-Augmented Generation for Black-Box Knowledge Graphs

Yiwen Wu HKUST (GZ)

• Mingyu Yang is listed with HKUST (GZ) and HKUST.Source: Yiwen Wu HKUST (GZ) · p. 1

• Semantic instantiation and structural path uncertainty cause recall loss, while evidential comparison uncertainty causes precision loss in black-box knowledge graph retrieval.Source: §1 · pp. 1–2, Figure 1 · p. 2
• Schema-translation [1, 22, 25], random-walk [7, 8, 33, 46], iterative multi-hop [19, 21, 29, 35, 38, 42], and pre-indexed methods [3, 18, 28] have recall or precision limitations.Their limits include brittle assumed structures, hub bias, sensitivity to anchor selection, and costly query-agnostic indices; none jointly optimizes recall and precision.Source: §1 · p. 2
• BubbleRAG unifies semantic anchor grouping, heuristic bubble expansion, composite ranking, and LLM-guided expansion to retrieve candidate evidence graphs for black-box knowledge graphs.It uses anchor groups to tolerate heterogeneous graph realizations, then refines the evidence coverage of top-ranked candidates.Source: §1 · p. 2
• OISR formalizes retrieval as selecting an informative candidate evidence graph, modeling the dual goals of semantic coverage and information density; it is NP-hard and APX-hard.Source: §1 · pp. 2–3
• On HotpotQA, MuSiQue, and 2WikiMultiHopQA, BubbleRAG achieves state-of-the-art results, outperforming strong structure-aware baselines in F1 and accuracy, with largest gains on MuSiQue.Source: §1 · p. 3
• BubbleRAG requires no retriever fine-tuning or knowledge-graph modifications, and its localized subgraph construction and anisotropic search keep retrieval complexity largely independent of global graph size.Source: §1 · p. 3

2.1 Graph-Based RAG

• Graph-based RAG indexes documents into a knowledge graph, retrieves a query-relevant subgraph, and generates an answer grounded in that evidence and optionally its source chunks.Entities and relations from different chunks can be linked across documents, enabling relational reasoning beyond isolated vector-similarity retrieval.Source: §2.1 · p. 3

2.2 Black-Box Knowledge Graphs

• A black-box knowledge graph has no schema available to the retriever, which must use topology and node or edge text rather than predefined types or traversal patterns.This is common for heterogeneous LLM-extracted graphs, evolving public graphs, and proprietary or partially documented enterprise graphs.Source: §2.2 · p. 3

2.3 Motivations

• Answer-supporting evidence is expected to contain semantic anchors for query concepts and form a compact, connected structure that can be expanded and ranked as candidate evidence graphs.Terminology may vary, and query concepts may connect through intermediate nodes or relations.Source: §2.3 · p. 3

2.4 Problem Formulation

• OISR seeks a connected subgraph covering at least one node or edge from each query-derived anchor group while maximizing the average relevance value of selected elements.The formulation assumes the graph contains at least one connected subgraph satisfying coverage; its average-value objective rewards compact, relevant evidence and penalizes long irrelevant paths.Source: §2.4 · p. 4
• OISR is NP-hard and APX-hard, motivating the heuristic approach developed in Section 3.The paper states these results are proved in Section 3.3.Source: §2.4 · p. 4

3.1 Data Preparation

• Embedding the combined text of each triplet directly in its edge enables semantic matching against both entities and relations, including relational query constraints.The graph is built by chunking the corpus, extracting triplets, and linking entities across chunks to support cross-document retrieval.Source: §3.1 · p. 4

3.2 Semantic Anchor Grouping

• LLM reasoning infers implicit query concepts beyond surface keywords, while query-conditioned specialization and context-guided schema relaxation address underspecified terms and label mismatches.Retrieved text chunks can preview locally connected concepts and guide relaxation of strict structural conditions to preserve recall.Source: §3.2 · pp. 4–6
• LLM grouping merges candidate nodes representing the same query intent into weighted anchor groups, allowing partial alignment and penalizing missing high-importance concepts more strongly.Weights reflect each group’s centrality to answering the query, enabling ranking to tolerate missing peripheral concepts while retaining partially informative subgraphs.Source: §3.2 · p. 6

3.3 Candidate Evidence Graph Discovery

• OISR, which seeks connected evidence subgraphs covering anchor groups, is NP-hard and APX-hard, motivating a heuristic rather than exact or constant-factor approximation methods.The hardness results follow from a reduction from Group Steiner Tree, including for binary-valued OISR instances.Source: §3.3 · pp. 6–7
• Bubble Expansion searches a localized anchor neighborhood using multi-source, semantic-cost-guided expansion, then fuses low-cost paths when frontiers from different groups meet.It also permits within-group connections with a ranking penalty and falls back to anchor nodes when expansion fails to connect them within budget.Source: §3.3 · p. 7
• Localized retrieval keeps query-time complexity largely independent of global graph size; experiments typically used fewer than 10^3 localized nodes for graphs with 10^5+ nodes.The expansion’s worst-case time is O(|E′|·m·log |V′|), with collision detection and fusion taking O(|V′|·m).Source: §3.3 · p. 8

3.4 Candidate Evidence Graph Ranking

• BubbleRAG ranks connected CEGs by combining average query-semantic dissonance with a weighted penalty for uncovered anchor groups, discouraging vacuous hubs and incomplete evidence.A mean semantic cost avoids penalizing longer evidence chains solely for containing more nodes, while α controls how strongly missing groups affect the score.Source: §3.4 · pp. 8–9
• Adjusting α lets ranking favor complete-anchor CEGs for AND queries or semantic matches for OR queries; top-n CEGs also support side-by-side comparison queries.The selected candidates are passed together to reasoning-aware expansion and answer generation for comparison.Source: §3.4 · p. 9

3.5 Reasoning-Aware Expansion

• For only the top-n CEGs, an LLM iteratively selects relevant frontier neighbors up to depth d, stopping at the limit or when no useful additions remain.Expansion can proceed through candidates in rank order and stop when the time budget is exhausted.Source: §3.5 · pp. 9–10

3.6 Answer Generation

• BubbleRAG merges expanded candidate subgraphs, maps unified-graph nodes to source chunks, and gives the LLM serialized triples and raw text alongside the query to generate an answer.Source: §3.6 · p. 10

4.1 Experimental Setup

• Experiments use 1,000-question validation splits from MuSiQue, HotpotQA, and 2WikiMultiHopQA, with a shared 15-chunk retrieval limit and F1 and LLM-as-a-Judge Accuracy metrics.All methods use Qwen3-Embedding-8B; Qwen3-7B judges semantic answer equivalence. The comparison includes general LLM and standard retrieval, iterative multi-hop, random-walk, and pre-indexed structure methods.Source: §4.1 · p. 10

4.2 Main Results

• On 30B models, BubbleRAG leads ten baselines by an average 2.52% in F1 and 2.23% in LLM-as-a-Judge Accuracy; it also achieves the highest averages across settings.The comparison covers MuSiQue, HotpotQA, and 2WikiMultiHopQA.Source: §4.2 · p. 10, Table 2 · p. 11
• On MuSiQue, BubbleRAG reaches 53.03 F1 with the 30B model, approximately 8 percentage points above HippoRAG2, using group-aware expansion for variable-length reasoning.MuSiQue requires 3–4-hop reasoning; the paper attributes the result to heuristic Steiner Tree search that supports semantically grounded, complete reasoning chains without predefined hop limits.Source: §4.2 · pp. 10–11

4.3 Ablation Studies

• Removing Schema Relaxation drops F1 by 11.35 points on 2Wiki and 5.17 on HotpotQA; Anchor Specialization drops it by 4.52 and 2.54, respectively.Removing CEG Ranking drops F1 by 6.21 points on 2Wiki and 1.62 on HotpotQA; the authors associate the first two components with recall and ranking with precision.Source: §4.3 · pp. 11–12, Table 3 · p. 11

4.4 Parameter Sensitivity

• With B=10, F1 is 60.52 at 20.99 seconds; increasing B to 20 or 50 gives F1 of 58.32 or 60.42 at 33.67 or 44.98 seconds.On a 100-query 2Wiki sample, F1 rises from 58.25 to 62.28 as reasoning depth increases from 2 to 8, while latency reaches 32.67 seconds at depth 8; F1 peaks at 60.52 for α=1.0 and falls to 57.35 at α=5.0. The localization hop is fixed at h=6.Source: §4.4 · p. 12, Table 4 · p. 12

4.5 Efficiency & Cost Analysis

• BubbleRAG takes 20.99 seconds per query versus ToG’s 45.93 seconds, but HippoRAG2 is faster at 4.26 seconds; BubbleRAG uses 1,064,052 inference tokens.Its 3,840,320-token indexing cost is comparable to HippoRAG2’s 4,575,580 tokens and is amortized across queries; the paper attributes latency overhead to LLM interactions in anchor grouping and reasoning-aware expansion.Source: §4.5 · pp. 12–13, Table 5 · p. 12

Query Rewriting and Schema-Aligned Matching

• SimGRAG [1] and KG-GPT [15] align queries to pre-conceived graph patterns using LLM priors, so invalid patterns can cause hallucinations and retrieval gaps.SimGRAG creates an abstract pattern graph for alignment; KG-GPT decomposes queries into head-relation-tail triples.Source: §5 · p. 13

Iterative Multi-Hop Exploration

• ToG [29], ToG2 [21], and RoG [19] expand from semantic seed nodes, making their multi-hop retrieval vulnerable to cascading failures from a misaligned initial anchor.Their approaches use topology beam search, document-embedding filters, or relation-type search plans, respectively.Source: §5 · p. 13

Stochastic Traversal via Random Walks

• HippoRAG and HippoRAG2 [8], LinearRAG [46], and AGRAG [33] use PPR-based walks from semantic anchors, so erroneous anchor extraction can misguide subsequent exploration.Their variants use PPR to rank passages, aggregate graph importance, or identify influential reasoning subgraphs.Source: §5 · p. 13

Structure-Augmented Retrieval with Auxiliary Graphs

• GraphRAG [3], KAG [18], and ClueRAG [28] depend on pre-built, domain-dependent graph structures that are poorly suited to diverse, specific real-world queries.They construct hierarchical communities, graph-text indices, or multi-partite graph indices during preprocessing.Source: §5 · p. 13

BubbleRAG’s Distinction

• BubbleRAG uses anchor groups and dynamically constructed, query-specific evidence structures to jointly optimize recall and precision through OISR rather than traversal heuristics.Group-covering bubble expansion supports recall, while discriminative candidate evidence graph ranking supports precision.Source: §5 · p. 13

6 Conclusion

• The Optimal Informative Subgraph Retrieval problem models semantic coverage and information density as a Group Steiner Tree variant and is NP-hard and APX-hard.Source: §6 · p. 13
• BubbleRAG addresses recall through semantic anchor grouping and heuristic bubble expansion, and precision through candidate evidence graph ranking and reasoning-aware expansion.Its plug-and-play design requires no retriever fine-tuning or changes to the underlying knowledge graph, while localized subgraph construction ensures scalability to massive graphs.Source: §6 · p. 13
• BubbleRAG consistently outperforms state-of-the-art baselines, including HippoRAG2, in accuracy and F1 on multi-hop QA benchmarks.It also delivers competitive performance with 8B models compared to baselines using 30B models.Source: §6 · p. 13