acceptodds
Under review as a conference paper at ICLR 2027

UBER: Uncertainty-Aware Bridge-structured Evidence Routing for Multi-Knowledge Graph Joint Reasoning

Abstract

Multi-knowledge graph (multi-KG) joint reasoning aims to answer queries or complete missing facts by exploiting complementary evidence distributed across multiple knowledge graphs. Existing methods mainly focus on cross-KG alignment, global graph integration, or federated representation learning, but often overlook two key challenges: how to route query-specific evidence across different source KGs, and how to reason robustly when cross-KG bridge links are incomplete or unreliable. To address these challenges, we propose UBER, an Uncertainty-aware Bridge-structured Evidence Routing framework for multi-KG joint reasoning. UBER consists of three tightly coupled modules: a Query-aware Source Router (QSR) that dynamically allocates evidence budgets across KGs, an Uncertainty-aware Bridge Constructor (UBC) that models reliable entity- and relation-level bridges, and a Reliability-Gated Fusion Reasoner (RFR) that performs query-conditioned reasoning over compact fused evidence graphs. Instead of globally merging all KGs, UBER constructs a query-specific evidence graph and controls cross-KG propagation according to bridge reliability and relation compatibility. Extensive experiments on three constructed multi-KG completion benchmarks demonstrate that UBER achieves the strongest overall performance over representative non-federated multi-KG, cross-KG, and federated baselines.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Multi-Knowledge Graph Reasoning, Query-Aware Evidence Routing, Uncertainty-Aware Bridge Modeling, Reliability-Gated Reasoning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_4DqAOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3(+1)
Soundness
2
Read review
Paper summary

This paper proposes an uncertainty-aware, bridge-structured evidence routing framework for multi-KG joint reasoning. This framework consists of three techniques: 1) a query-aware source router for allocating evidence budgets among KGs, 2) an uncertainty-aware bridge constructor for modeling reliable entity- and relation-level bridges, and 3) a reliability-gated fusion reasoner that performs query-conditioned reasoning over compact fused evidence graphs. Experiments demonstrate the effectiveness of the proposed framework.

Critical strengths
  • S1. This paper is well-motivated.
  • S2. Extensive ablation experiments validate the effectiveness of each component in the proposed framework.
  • S3. The paper compares with recent baselines and demonstrates the effectiveness of the proposed framework.
Critical weaknesses
  • W1. The paper’s technical depth needs to be improved. I acknowledge that multi-domain mixing is a promising approach. However, using only a budget constraint to implement dynamic allocation seems overly trivial. The authors should provide more technical discussion on how multi-domain KG mixing is achieved.

  • W2. This work mainly addresses the problem from the KG data perspective, but it lacks discussion on the KG model side. For example, the paper does not clarify how the choice of a KG backbone may affect the overall framework.

  • W3. The paper’s presentation needs to be improved. For instance, Figure 2 contains a lot of information, but the caption lacks sufficient description to explain what the figure represents and how to interpret it.

Questions for authors
  • Q1. Could the authors provide more technical discussion on how multi-domain KG mixing is achieved? (See W1)

  • Q2. Could the authors further extend the evaluation by using additional knowledge graph models as backbones, e.g., KnowFormer [1] and DuetGraph [2]? (See W2)


[1] KnowFormer: Revisiting Transformers for Knowledge Graph Reasoning. ICML 2024

[2] DuetGraph: Coarse-to-Fine Knowledge Graph Reasoning with Dual-Pathway Global-Local Fusion. NeurIPS 2025

3 comments
AuthorsOpenReview ↗

Response to Reviewer 4DqA

Response to Reviewer 4DqA

We thank the reviewer for the constructive comments on technical depth, backbone dependence, and presentation. We have clarified how source routing interacts with cross-KG evidence construction and expanded the backbone evaluation.

Q1/W1. How is multi-KG evidence actually combined?

The dynamic budget rule in Eq. (2) converts learned query-dependent source relevance into integer retrieval budgets; it is only one part of the mechanism. UBER's source weights depend on the query and candidate anchor evidence (Eq. 1), and query–relation compatibility guides local evidence expansion (Eq. 3). The hard budget and retrieval operators are trained through source-level and path-level supervision derived from target-masked graphs, rather than by differentiating through discrete top-BmB_m selection.

Cross-source mixing occurs in the query-specific fused evidence graph. UBC selects entity bridges using matching confidence and learned reliability attenuation, while the Relation Bridge Matcher supplies relation-level compatibility priors. RFR then propagates messages across source-local edges and retained cross-KG entity bridges, weighting each message according to query relevance, bridge reliability, and relation compatibility (Eqs. 5–12). Thus, evidence from different KGs contributes through controlled multi-hop propagation, not merely through distributing the retrieval budget.

In the main ablation (Table 2), removing dynamic budget allocation reduces MRR by 0.012–0.014 across the three benchmarks. Removing UBC reduces MRR by 0.031–0.040, and removing RFR reduces it by 0.038–0.046, emphasizing the contribution of bridge construction and reliability-gated reasoning beyond allocation alone.

Manuscript additions: Sections 3.2–3.5 describe the route–connect–reason pipeline, including the fusion-graph and propagation equations; Appendix B.2 specifies the observable source/path supervision, including the routing and retrieval losses. Figure 2 and its caption identify the roles of QSR, UBC, and RFR in the end-to-end graph.

Q2/W2. Does UBER generalize across KG reasoning backbones?

We added a controlled study replacing RFR with adapted KnowFormer and DuetGraph backbones. All variants use the same query-specific fused evidence graphs and observable source features; bridge reliability and relation-compatibility signals enter the alternative backbones as edge-message factors. Each backbone and its scoring head is trained under a common setting, with the same filtered-ranking protocol.

BackboneFB15k-237-MKG MRRWN18RR-MKG MRRYAGO3-10-MKG MRRMacro MRR
RFR0.3840.5160.5690.490
KnowFormer0.3750.5040.5620.480
DuetGraph0.3960.5080.5840.496

DuetGraph yields the highest MRR on FB15k-237-MKG and YAGO3-10-MKG, while RFR performs best on WN18RR-MKG. In the corresponding interventions, removing explicit bridge signals or propagation gating reduces MRR for all three backbones. These results support the portability of UBER's evidence-routing and reliability mechanisms across different reasoning architectures, while showing that the backbone can affect final performance.

Manuscript additions: Appendix G.4, Effect of the reasoning backbone, describes the backbone adaptations and includes the performance comparison (Table 24) and component interventions (Table 25). Section 3.2 and Figure 2 provide a clearer description of the framework components and their interactions.

W3. Presentation of the overall framework

Figure 2 and its caption identify the responsibilities of QSR (where and how much evidence to retrieve), UBC (which cross-KG links to trust), and RFR (how to propagate evidence on the query-specific fused graph). Section 3.2 (Framework Overview) explains their execution order as a route–connect–reason pipeline and distinguishes source allocation from bridge construction and gated propagation.

Thank you for your response. Some of my concerns are addressed. I have improved the score accordingly.

We sincerely thank the reviewer for the thoughtful and constructive feedback throughout the review cycle. The comments were genuinely helpful in improving the paper, and we are glad that the revisions and clarifications addressed your concerns. We truly appreciate the time and care you invested in this review.

Reviewer_qNdJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates joint reasoning over fragmented, multi-source knowledge graphs. It employs source-routing allocation to manage retrieval budgets for queries and organizes evidence by leveraging entity-bridge confidence, uncertainty weighting, and relational-bridge information. The approach is evaluated on a multi-source benchmark—constructed by partitioning standard knowledge graphs—with a focus on link prediction, bridge reliability, robustness against perturbations, and evidence-based intervention. While the overall framework is of research interest, the mathematical interpretation of uncertainty, the boundaries for cross-source benchmarking, and certain implementation definitions remain areas that could affect the credibility of the core conclusions.

Critical strengths

We propose a query-aware dynamic evidence routing and uncertainty-gating mechanism, which effectively mitigates noise interference during reasoning across knowledge graphs. Extensive experiments demonstrate strong reasoning performance and robustness.

Critical weaknesses
  1. In Equation (40), for a fixed binary cross-entropy (BCE) loss BB, the optimal non-negative uncertainty value is max⁡(0,log⁡B)\max(0, \log B), which approaches zero for all B≤1B \le 1. This term primarily serves to reweight pseudo-label errors; its interpretation in terms of probabilistic uncertainty remains undefined.
  2. The semantic representations in Equation (17) incorporate trainable projections, yet Equation (24) asserts that the candidate sets derived from these representations can be precomputed once. The conditions under which these projections can be updated while maintaining the validity of the static candidate sets are not specified.
  3. Equation (10) defines the weight of an individual relation by taking the maximum compatibility score across all candidate relations; however, it fails to constrain the actual pairs of relations traversed along a path. There is a lack of alignment between the matching of "relation bridges" and the compatibility with the ground-truth chain of evidence.
  4. Equation (49) in Appendix C.2 removes all known true answers without providing an exception for the current target entity. This contradicts the description of "filtered ranking" provided in the accompanying text, rendering the definition of the evaluation metric ambiguous.
  5. While the benchmarks distribute original training triples across different sources—maintaining the same overall union—they lack a control condition where modeling occurs under identical observable information and bridge candidate sets. Consequently, the gains attributed to the routing structure have not been disentangled from the differences in the scope of accessible information.
  6. All multi-source benchmarks in Appendix C.3 are derived from a single knowledge graph through manual partitioning. This approach fails to account for ontological discrepancies or entity ambiguities that would naturally arise from independently constructed knowledge bases; thus, the applicability of the method across heterogeneous knowledge graphs remains unverified.
  7. The source-ablation experiments in Appendix F compare sources with high versus low routing scores; however, sources with higher scores are inherently allocated a larger share of the retrieval budget. Since the total volume of evidence varies across these interventions, the observed performance degradation is insufficient to definitively demonstrate the "faithfulness" of the routing mechanism.
  8. In Appendix C.2, queries are mapped to local source-specific representations; however, no selection rule is defined for cases where query entities or relations possess copies across multiple sources. This initial mapping directly influences the evidence accessible to the model and the subsequent source-routing process.
Questions for authors
  1. How does Equation (40) ensure that the learned uncertainty reflects meaningful bridge uncertainty rather than merely reweighting pseudo-label errors?
  2. How are the precomputed candidate sets in Equation (24) kept valid when the semantic projections in Equation (17) are trainable? How are entities appearing in multiple source KGs handled?
  3. How does the maximum relation compatibility in Equation (10) ensure consistency with the actual reasoning paths, rather than potentially unrelated relation matches?
  4. Could the authors clarify the filtered-ranking protocol in Equation (49) and explain how the experiments disentangle the benefits of evidence routing from differences in accessible information and retrieval budgets?
2 comments
AuthorsOpenReview ↗

Response to Reviewer qNdJ

Response to Reviewer qNdJ

We thank the reviewer for the detailed technical questions. We have clarified the interpretation of bridge uncertainty and the separation between frozen candidate retrieval and trainable reranking, and added controlled bridge diagnostics.

Q1. What does the learned bridge uncertainty represent?

We agree that the BCE-based attenuation term alone does not establish probabilistically calibrated uncertainty. With fixed pseudo-label loss ℓb=BCE(y~b,μb)\ell_b=\mathrm{BCE}(\tilde y_b,\mu_b), minimizing ℓbe−νb+νb\ell_b e^{-\nu_b}+\nu_b over νb≥0\nu_b\geq0 gives

νbBCE=log⁡max⁡(1,ℓb).\nu_b^{\mathrm{BCE}}=\log\max(1,\ell_b).

Accordingly, we interpret the learned νb\nu_b as a bridge-reliability attenuation signal, rather than a calibrated probability. We further compare confidence-only scoring, pointwise BCE attenuation, and learned attenuation using the same checkpoint, bridge candidates, confidence estimates, and retained-bridge count on FB15k-237-MKG (4KG–20%).

For 10,000 retained query–bridge occurrences, bridge precision is 0.8246 with confidence-only scoring, 0.8369 with BCE attenuation, and 0.8567 with learned attenuation. On 2,000 matched correct–incorrect bridge pairs, the concordance of pseudo-label loss, BCE attenuation, and learned attenuation is 0.5045, 0.5025, and 0.6695, respectively.

The matched pairs contain one correct and one incorrect bridge with the same pseudo-label and a BCE gap at most 0.02. Learned attenuation improves retained-bridge precision by 1.98 percentage points over BCE attenuation and better separates the matched correct/incorrect bridges. This provides evidence of a useful reliability signal beyond pointwise pseudo-label loss attenuation.

Manuscript additions: Appendix B.3, Bridge confidence and uncertainty, clarifies the training objective; Appendix G.1, Bridge reliability conditional on pseudo-label loss, reports the matched-retention and error-discrimination diagnostics (Tables 19–20).

Q2. How are static candidate pools compatible with trainable semantic projections?

We now explicitly separate offline retrieval from online reranking. An offline index uses frozen text embeddings zˉv=Norm⁡(ftext(xv))\bar{\mathbf z}_v=\operatorname{Norm}(f_{\mathrm{text}}(x_v)), retrieving the top K0=100K_0=100 candidates from each other KG and taking a bidirectional union. Its membership therefore remains unchanged as model parameters are updated. The trainable representation zv(θ)=Norm⁡(Wzftext(xv)+bz)\mathbf z_v(\theta)=\operatorname{Norm}(\mathbf W_z f_{\mathrm{text}}(x_v)+\mathbf b_z) is used only to rerank candidates within the frozen pool, together with graph-dependent relation profiles computed on target-masked support graphs during training.

Entities shared across source KGs retain separate source-local IDs, graph neighborhoods, and retrieval entries. Cross-source candidates are matched explicitly; copies are not merged inside the model. For canonical evaluation, source-local scores are aggregated by canonical answer entity before filtering and ranking.

Manuscript additions: Section 3.3 now states the two-stage design; Appendix B.1 (Semantic representations) defines the frozen and projected representations; Appendix B.2 (Two-stage observable candidate generation) specifies the top-K0K_0 retrieval, bidirectional union, cache conditions, and trainable reranking. Appendix C.2 details canonical score aggregation.

AuthorsOpenReview ↗

Response to Reviewer qNdJ

Response to Reviewer qNdJ

Q3. Does maximum relation compatibility correspond to actual reasoning paths?

The maximum in Eq. (10) is a relation-level compatibility prior, rather than a path-level proof. Actual propagation is restricted to edges in the retrieved, query-specific fused graph (Eqs. 11–12). We added an evidence-restricted alternative that computes the maximum only over relation types present in the retrieved intra-KG evidence, while keeping the checkpoint, graph, candidate bridges, and bridge counts fixed.

Compatibility settingOverall MRRMRR on 12,256 queries with changed priors
Global maximum0.38640.3917
Evidence-restricted maximum0.38580.3897
Zero compatibility prior0.37930.3828

The restricted maximum is only 0.0006 MRR below the original globally defined prior, whereas removing the prior reduces MRR by 0.0071. Thus, relation compatibility remains beneficial when restricted to relation types actually retrieved for the query.

Manuscript additions: Appendix G.2, Sensitivity to relation matches outside the retrieved evidence, defines the three settings and reports the controlled comparison (Table 21). The role of the prior in actual edge propagation is clarified alongside Eqs. (10–12).

Q4. Filtered ranking and a fair test of query-aware routing

We have made the target-retention rule explicit. For a test triple (h,r,t)(h,r,t), the canonical filtered candidate sets remove other known true answers while retaining tt for tail prediction and hh for head prediction:

=\mathcal E\setminus\\{e'\ne t:(h,r,e')\in\mathcal T_{\mathrm{all}}\\},$$ with the analogous condition for head prediction. Source-local scores are first aggregated for each canonical entity; filtering uses train/validation/test facts **only in the evaluator**, whereas inference uses training-available evidence. To isolate routing policy from information access, we compare **uniform, static, permuted, and adaptive** allocation using the same checkpoint, source anchors, candidate bridges, full candidate domain, and total budget ($B_{\mathrm{tot}}=256$). The permuted policy preserves each query's budget-weight multiset while changing its assignment to sources. We first match the realized **number of nodes** per query and then additionally match **nodes, source-local triples, and entity bridges**. | Routing policy | Node-matched MRR | Node/triple/bridge-matched MRR | |---|---:|---:| | Uniform | 0.3748 | 0.3726 | | Static | 0.3786 | 0.3764 | | Permuted | 0.3736 | 0.3713 | | **Adaptive UBER** | **0.3864** | **0.3827** | After matching all three evidence quantities, adaptive routing retains gains of **0.0101/0.0063/0.0114 MRR** over uniform/static/permuted allocation. This shows a benefit from **assigning the available evidence to query-relevant sources**, rather than simply increasing evidence volume. **Manuscript additions:** **Appendix C.2, *Canonical Evaluation and Ranking Protocol***, now specifies filtered head and tail ranking with explicit target retention. **Appendix G.3, *Routing under matched information and evidence budgets***, details the controlled allocation policies and comparisons (**Tables 22–23**).
Reviewer_qWQjOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes UBER, a framework for multi-KG joint reasoning. It combines query-aware source routing and dynamic evidence budgeting, uncertainty-aware entity and relation bridging, and reliability-gated message passing over query-specific fused evidence graphs. Experiments on three multi-KG completion benchmarks demonstrate competitive link prediction performance.

Critical strengths
  1. The framework provides an intuitive approach to query-specific evidence selection and reliability-controlled cross-KG reasoning. The idea of estimating bridge reliability and performing query-conditioned fusion over uncertain cross-KG bridges is straightforward and reasonable.

  2. I particularly appreciate the thorough experimental evaluation. The ablation studies and hyperparameter sensitivity analyses are particularly solid, providing convincing support for the proposed design choices.

Critical weaknesses

The evaluation relies entirely on multi-KG benchmarks constructed by partitioning existing single-KG datasets. While this provides useful experimental control, the resulting source graphs may not capture the schema heterogeneity, inconsistent entity descriptions, and distribution shifts found across independently constructed real-world knowledge graphs.

Questions for authors

How well does UBER generalize to independently constructed knowledge graphs with substantially different schemas, entity descriptions, and relation vocabularies? An evaluation on heterogeneous multi-KG datasets would help establish its practical applicability.

3 comments
AuthorsOpenReview ↗

Response to Reviewer qWQj

Response to Reviewer qWQj

We thank the reviewer for emphasizing the importance of evaluating generalization beyond KGs obtained by partitioning a single graph. We have extended the evaluation to two independently constructed KG pairs and added a no-direct-edge analysis with five-seed variability.

Heterogeneous multi-KG evaluation

We evaluate DBpedia link prediction with DBP-FB (DBpedia–Freebase) and DBpedia–Wikidata (OpenEA D-W-15K V1). The two sources retain their native entity IDs, relation vocabularies, schemas, and textual metadata. We construct disjoint 70/10/20 train/validation/test splits, use filtered head and tail ranking over the same DBpedia candidate set, and use the auxiliary KG only for additional observable evidence. Reference entity alignments are withheld from model training and inference. The cross-source fact audit removes auxiliary training triples that directly restate held-out DBpedia facts, including inverse-predicate cases.

BenchmarkFull-test MRR (5 seeds)No-direct-edge MRR (5 seeds)No-direct-edge triples
DBP-FB0.3895 ± 0.00190.3715 ± 0.002411,746 / 19,283 (60.91%)
DBpedia–Wikidata0.4096 ± 0.00210.3931 ± 0.00265,086 / 7,653 (66.46%)

The no-direct-edge subset requires both DBpedia endpoints to have auxiliary counterparts but excludes triples whose counterparts are directly connected by any predicate in either direction in the original auxiliary KG. It is fixed across methods and seeds. On this subset, full UBER exceeds DMKGC by 0.0067 and 0.0058 MRR on DBP-FB and DBpedia–Wikidata, respectively.

Contribution of query-adaptive routing and reliable bridging

With the same auxiliary source and total retrieval budget, replacing uniform allocation with adaptive UBER routing improves full-test MRR by 0.0143/0.0152 on the two benchmarks. The corresponding improvements on the no-direct-edge subsets are 0.0121/0.0134. Removing relation matching reduces full-test MRR by 0.0156/0.0179, while removing bridge gating reduces it by 0.0242/0.0277, respectively. These results indicate that query-dependent allocation and reliability-controlled evidence fusion remain useful across independently constructed graphs, including cases without a directly corresponding auxiliary edge.

Manuscript additions: Appendix G, Completion across independently constructed KGs, provides the source statistics, split and leakage-audit protocols, and common-protocol comparisons (Tables 15–16). The new no-direct-edge coverage and five-seed results are reported in Tables 17–18, followed by the subset and stability analyses. Published reference results under different test protocols are separated from our controlled comparisons.

Thanks for your response and additional experiments. These results strengthen the paper, although I would appreciate a more comprehensive evaluation in which both KGs serve as prediction targets rather than testing on DBpedia only. Nevertheless, the current version is acceptable, so it's more like a suggestion and will not affect my assessment. As I have already given an original rating of 3, I would like to maintain this positive rating.

Thank you for your affirmation, and likewise, thank you for taking the time to review our paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.