acceptodds
Under review as a conference paper at ICLR 2027

UniRel: Relation-Centric Knowledge Graph Question Answering with RL-Tuned LLM Reasoning

Abstract

Knowledge Graph Question Answering (KGQA) has largely focused on entity-centric queries that return a single answer entity. However, many real-world questions are inherently relational, aiming to understand how entities are associated rather than which entity satisfies a query. In this work, we introduce relation-centric KGQA, a complementary setting in which the answer is a subgraph that represents the semantic relations among entities. The main challenge lies in the abundance of candidate subgraphs, where trivial or overly common connections often obscure the identification of unique and informative answers. To tackle this, we propose UniRel, a unified modular framework that combines a subgraph retriever with an LLM fine-tuned using reinforcement learning. The framework uses a reward function to prefer compact and specific subgraphs with informative relations and low-degree intermediate entities. Experiments show that UniRel not only produces more coherent and informative relational answers than existing baselines, but also generalizes effectively to unseen entities and relations. Additionally, UniRel can be applied to conventional entity-centric KGQA, achieving competitive or improved performance in several settings. A human evaluation further shows that participants prefer UniRel's answers over the baselines.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Knowledge Graph Question Answering (KGQA), Large Language Models (LLMs), Reinforcement Learning, Human Evaluation

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_aiXJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces relation-centric knowledge graph question answering, where the goal is to identify informative relational subgraphs connecting given entities rather than retrieving a single answer entity. The proposed UniRel framework combines multi-stage subgraph retrieval with reinforcement learning-based LLM reasoning, using rewards that encourage connectivity, compactness, and informativeness. Experiments across seven knowledge graphs demonstrate improvements over existing baselines, supported by ablation studies, cross-domain evaluations, and human assessments.

Critical strengths

(1) The paper introduces a meaningful relation-centric KGQA setting that complements traditional entity-centric question answering and addresses a practically relevant problem. (2) The proposed framework effectively combines structured subgraph pruning with reward-guided LLM reasoning, providing a coherent approach to generating informative relational answers. (3) The experiments cover seven knowledge graphs and multiple LLM backbones, with strong results across baseline comparisons, ablation studies, and cross-domain generalization.

Critical weaknesses

(1) The evaluation relies heavily on metrics derived from the same reward function used for training, making it difficult to independently assess whether the generated subgraphs are genuinely more informative. (2) The relation-centric queries are primarily constructed from sampled entity pairs and manually designed templates, which may not adequately reflect the complexity and diversity of real-world user questions. (3) The human evaluation covers only four queries, limiting the strength of the evidence that UniRel's preference-based objective aligns with human judgments across different domains and query types. (4) The pipeline figure is messy.

Questions for authors

Could the authors evaluate UniRel on a broader set of naturally occurring relation-centric questions to demonstrate that its improvements generalize beyond template-generated queries?

4 comments
AuthorsOpenReview ↗

Response to W1 and W2

We thank the reviewer for the feedback, and apologize for the late response. We used the time to run an extended human evaluation (35 queries across all seven KGs, 205 participants), which directly addresses W3 and supports W1.

W1: We agree with this concern, and the paper states it directly at the start of Sec. 5: ``Our automatic metrics all rely on the reward we optimize.'' This is why we ran an independent human evaluation.

  • Role of automatic metrics. Average Reward measures how well a method meets our preference objective. Subgraph F1 measures agreement with a reward-optimal reference. We do not present either as independent evidence of answer quality. Connectivity Ratio measures structural validity and does not depend on the informativeness terms.
  • Independent validation of answer quality. In a blinded human evaluation, participants ranked anonymized answers by informativeness, coherence and usefulness. The instructions explain what a valid answer is, but never mention node degree, relation frequency, compactness or our reward.
    • Original study (Sec. 5, Appendix C). In a small-scale study with 4 queries and 49 participants, UniRel was preferred over GNN-RAG and SubgraphRAG in 80-92% of informativeness and 67-96% of usefulness judgments, significant on all four queries. It was also significantly preferred over its variant without entity informativeness in 11 of 12 query-criterion pairs, and over its variant without relation informativeness in 7 of 12.
    • Extended study. To strengthen this evidence, we extended the study to 35 queries across all seven KGs with 205 participants (details in W3 below). UniRel is preferred over the baseline in 64% of informativeness, 61% of coherence and 64% of usefulness judgments. It is also preferred over w/o RentR_{ent} and w/o RrelR_{rel} in 55-58% of judgments, so both terms contribute, with smaller margins than against the baseline. All comparisons are significant (p<0.001p < 0.001).
    • Participant comments. In both studies, participants said without being told that they preferred specific connections over generic shared attributes such as gender or nationality (Appendix C.4).

So, without being told what our reward favors, people judge the answers it produces as more informative and useful.

W2: Our queries are grounded in existing KGQA benchmarks, and the diversity of the task lies in the relational structures the model must discover rather than in the wording of the question.

  • Entity pairs. A portion of the queries are converted from entity-centric benchmarks (e.g., WebQSP, CWQ, SimpleDBpediaQA and MetaQA), so each seed pair comes from a real question. The remaining pairs are sampled from an entity pool built from the same benchmarks, within 4 hops, consistent with the reasoning depth of these benchmarks.
  • Templates and diversity. The templates only vary the wording. The reasoning each query requires varies widely. (1) Domains: seven KGs covering general knowledge, movies and biomedicine. (2) Reasoning distance: range between 1 to 4 hops. (3) Number of seeds: both two-entity and multi-entity queries.

Please refer to our response to Reviewer paDH (Q1) for the detailed construction procedure and per-KG sources, and to our response to Reviewer eB42 (Q2) for the full template list.

AuthorsOpenReview ↗

Response to W3 and W4

We have extended the human study from 4 to 35 queries covering all seven KGs, with 205 participants. UniRel is preferred over the baseline in 61–64% of judgments and over each reward ablation in 55–58%, with all comparisons significant.

(1) Setup.

  • Queries. We selected five queries per KG, for which GNN-RAG and SubgraphRAG return a valid (connected) answer. On these queries, the two baselines return the same answer. As in the original study, participants compared four answers: UniRel, the baseline, w/o RentR_{ent} and w/o RrelR_{rel}.
  • Design. Each query asks participants to read four answers and rank them on three criteria, which is demanding. Longer questionnaires are known to lower response quality, as participants answer faster and less carefully toward the end [1]. We therefore kept each session to five queries, which took a median of 13 minutes, and used a between-subjects design to cover all 35 queries: participants were split into seven groups of five queries each, and each group covers five different KGs. Participants ranked the four answers by informativeness, coherence and usefulness, without knowing which method produced which answer.
  • Participants. We recruited participants on Prolific. After pre-specified exclusions (e.g., failed attention check, completion under 5 minutes), 205 participants remained, 28–30 per group.

(2) Results. We report statistics in the same format as Appendix C.

vs. baselinevs. w/o RentR_{ent}vs. w/o RrelR_{rel}
Informativeness64%55%57%
Coherence61%56%58%
Usefulness64%56%56%
  • Pairwise preference. The table above reports how often participants rank UniRel above each alternative. Each cell is based on about 1,000 judgments, and all nine comparisons are significant (p<0.001p < 0.001, with standard errors clustered by participant).
  • First place. UniRel is ranked first in 34% of informativeness judgments, against 29%, 21% and 16% for w/o RrelR_{rel}, w/o RentR_{ent} and the baseline.
  • Agreement. Kendall's WW is significant (Friedman test, p<0.05p < 0.05) on 29 of 35 queries for informativeness and usefulness, and on 23 for coherence. As in the original study, participants agree least on coherence.

(3) Participants' own descriptions. As in the original study, participants described what guided their choices in a free-text question. Many explicitly said they preferred specific connections over generic or broad ones. Representative responses include:

  • "I just picked the ones with real, specific connections and put the generic ones like gender or nationality at the bottom."
  • "I ranked answers higher when they linked entities through concrete facts (like shared careers or historical events) and ranked generic links (like gender or broad locations) at the bottom."
  • "I favored granular entities for Informativeness."

As before, the instructions never mentioned node degree, relation frequency or compactness, so this preference was not suggested to participants.

(4) Variation across KGs. UniRel is preferred over the baseline on five of the seven KGs, most strongly on FB13 (88% on informativeness), DBpedia50 (72%), FB15k (71%) and YAGO3-10 (69%). It is not preferred on DBpedia500 and UMLS. Our response to Reviewer paDH (Q3) analyzes these cases, which point to two failure modes of our informativeness measures: rare but meaningless relations, and abstract ontologies where node degree carries little signal.

We will add the full study, including per-KG and per-query results, to Appendix C.

W4: Thank you. Fig. 1 has two parts. Fig.1(a) contrasts entity-centric and relation-centric KGQA. Fig.1(b) shows the two main components of UniRel: subgraph retrieval and RL-tuned LLM reasoning. We kept the multi-stage pruning out of this overview and show it separately in Fig. 2, so that the overview stays readable. In the revised version, we will expand the caption of Fig. 1 to explain how to read each part.

References:

[1] Galesic and Bosnjak, "Effects of Questionnaire Length on Participation and Indicators of Response Quality in a Web Survey", Public Opinion Quarterly 2009.

Thank you for the detailed rebuttal and the extended evaluation, which address several of my concerns. However, I remain concerned about the limited diversity of naturally occurring queries and the inconsistent preference results across datasets.

AuthorsOpenReview ↗

Response to remaining concerns

Thank you for the follow-up. We respond to the two remaining points below.

1. Diversity of naturally occurring queries.

  • Question types in entity-centric KGQA. Entity-centric KGQA asks for a specific target, and the question word follows from the type of that target. In MetaQA, for example, who questions ask for a person (e.g., "Who directed [movie]?"), when questions for a year (e.g., "When was [movie] released?"), what questions for an attribute (e.g., "What genre is [movie]?"), and which questions for a set of movies (e.g., "Which movies did [actor] star in?").
  • Relation-centric questions are common in practice. Many real-world questions aim to understand how entities are associated rather than which entity satisfies a query, for example in education, scientific exploration and decision support. Here the target is the connection itself, and no target relation or answer type is given, so the who/when/what distinction does not apply. The diversity instead lies in the kind of connection the model must discover, such as a shared director, a shared genre or a family tie.
  • Our queries inherit the variety of entity-centric questions. Most of our queries are converted from entity-centric questions of all these types. A who question gives a (movie, person) pair, a which question a (person, movie) pair, and a multi-hop question gives a pair that is several hops apart. Beyond two-entity queries, we also construct queries with three and four entities.
  • We follow MetaQA's construction practice. MetaQA generates its questions from templates: each question type, defined by its reasoning path, has 10 text templates. We likewise generate relation-centric questions from 8 templates. The difference is that MetaQA fixes the reasoning path for each question type, while our task leaves the path open for the model to discover.
  • No existing benchmark. To our knowledge, no existing benchmark contains naturally occurring relation-centric questions. If the reviewer has suggestions for better ways to construct such a dataset, we would be glad to hear them and to include experiments on it in the revised version.

2. Consistency across datasets.

Note that to compare answer quality rather than validity, the human study only includes queries where the baseline also returns a valid (connected) answer.

  • Clarification of our earlier statement. In our previous response, we wrote that UniRel “is not preferred” on DBpedia500 and UMLS. To be precise, on these two KGs UniRel is on par with the baseline in informativeness (50% and 53%, not significantly different), rather than worse. Overall, participants prefer UniRel over the baseline on every criterion (p<0.001p < 0.001).
  • The remaining gap reflects properties of the KGs. This matches the limitation cases we analyzed in our response to Reviewer paDH (Q3). DBpedia contains schema-level relations, such as type_of_union, that are rare but carry little meaning. UMLS is a biomedical ontology. Its nodes are abstract semantic types, such as Family Group or Fungus, rather than concrete entities like people or films. Every answer is therefore a chain of categories, and node degree reflects how general a type is in the ontology, not how informative an answer is to a reader. In both KGs, the proxies behind RrelR_{rel} and RentR_{ent} carry less signal than in KGs of real-world entities, so optimizing them helps less. Since UniRel builds its answers from KG facts, answer quality depends on KG quality, as noted in Sec. 7.

As the first framework for the relation-centric KGQA task introduced in this paper, UniRel already improves human-judged informativeness with simple proxies. As better proxies are developed, for example personalized ones (Sec. 7), they can be used directly within the same framework.

We hope this addresses your remaining concerns.

Reviewer_paDHOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper focuses on relation-centric knowledge graph question answering (KGQA), which aims to answer questions by identifying relational subgraphs rather than individual entities in a knowledge graph. Specifically, it proposes UniRel, a unified framework that combines subgraph retrieval with reinforcement learning-based LLM fine-tuning. The key idea is to generate informative relational subgraphs, where entity informativeness is measured by node degree and relation informativeness by inverse document frequency (IDF). The experimental results demonstrate the effectiveness of the proposed method.

The paper studies an interesting and underexplored task and proposes a reasonable framework. However, several concerns regarding dataset construction, evaluation validity, and the informativeness measures remain insufficiently addressed. These issues limit the extent to which the experimental results support the paper's main claims. Overall, this reviewer leans toward a negative score.

Critical strengths
  1. This paper investigates an underexplored problem, namely, relation-centric KGQA.
  2. The proposed framework is reasonable.
  3. The experiments are extensive, covering multiple datasets and LLM backbones.
Critical weaknesses
  1. The validity of the dataset construction is insufficiently justified.
    The paper constructs questions by sampling connected entity pairs from knowledge graphs. However, it remains unclear whether these questions and their corresponding relational paths reflect meaningful information needs in real-world applications. One possible improvement is to convert existing entity-centric KGQA datasets, such as CWQ and WebQSP, into relation-centric ones and retain the original reasoning paths as ground-truth references. Although these paths are not necessarily the only valid answers, they may better reflect the underlying user intent and provide a more meaningful basis for automatic evaluation.
  2. The automatic evaluation is closely aligned with the method's optimization objective.
    In particular, the Average Reward metric uses the same entity and relation informativeness measures that the proposed method explicitly optimizes. Moreover, the reference subgraphs for Subgraph F1 are constructed under the same reward function. Consequently, the evaluation criteria inherently favor the proposed method, raising concerns about whether the reported improvements reflect better relational answer quality in real-world applications rather than simply better optimization of the predefined objective.
  3. The proposed informativeness measures are insufficiently validated.
    The paper heuristically defines entity informativeness based on node degree and relation informativeness based on IDF. Although these measures are intuitively reasonable, it remains unclear to what extent they reflect the actual informativeness of relational answers. The paper lacks failure case analysis to investigate when these measures may fail to identify meaningful relational answers. Such an analysis would help clarify the limitations and applicability of the proposed informativeness measures.
Questions for authors

None

4 comments
AuthorsOpenReview ↗

Response to W1

We thank the reviewer for the thoughtful feedback, and apologize for the late response. We used the time to run an extended human evaluation (35 queries across all seven KGs, 205 participants), which we use in W2 and W3.

W1: Converting entity-centric benchmarks is already a core part of our dataset construction. Appendix B.2 states: ``A portion of our two-entity queries are converted from such entity-centric KGQA benchmarks, where the head entity and the gold answer naturally form a seed pair under relation-centric reformulation. The remaining queries are randomly sampled following Algorithm 1.'' We give more detail below and will add it to Appendix B.2.

  • Query Built. We use two complementary approaches.
    • QA-based construction. We take topic-answer pairs from existing KGQA benchmarks. For example, ``Who directed Interstellar?'' with the answer Christopher Nolan gives the seed pair (Interstellar, Christopher Nolan). We also compose QA-derived pairs through shared entities: given (e1,e2)(e_1, e_2) and (e2,e3)(e_2, e_3), we form (e1,e3)(e_1, e_3). We check the actual shortest-path distance of every resulting pair in the KG.
    • Graph-based construction. Existing benchmarks cover few multi-hop pairs. To fill this gap, we collect the topic and answer entities of these benchmarks into an entity pool. Following Algorithm 1, we sample a start entity from this pool, run BFS up to four hops, and sample an end entity from the reachable entities in the same pool. | KG | QA source | Direct conversion | Composition / sampling | | --- | --- | --- | --- | | FB15k-237 | WebQSP [1], CWQ [2] | Mainly 1–3 hops | Compose 2–3; sample 4 | | Freebase13 | WebQSP [1], CWQ [2] | 1–4 hops (limited alignment) | Mainly graph sampling | | DBpedia50 | SimpleDBpediaQA [3] | Mainly 1 hop | Compose 2–3; sample 4 | | DBpedia500 | SimpleDBpediaQA [3], QALD-9 [4] | Mainly 1–3 hops | Compose 2–3; sample 4 | | MetaQA | MetaQA [5] | 1–3 hops | Sample 4 | | YAGO3-10 | ProbeKGC-YG [6] | 1 hop | Compose 2–3; sample 4 | | UMLS | Constructed from UMLS triples [7] | Mainly 1–2 hops | Compose 2 hops |

For converted queries, the seed pair comes directly from a real question. For sampled queries, both entities come from real questions, but the pairing is ours. We cap all pairs at 4 hops, consistent with the reasoning depth of widely used entity-centric benchmarks (typically 1–3 hops). Beyond this distance, paths tend to pass through loosely related intermediates and rarely form coherent associations (Appendix B.2).

  • Original reasoning paths as references. We agree that the original paths are meaningful. We see them as one valid answer, NOT the only target, because the information need changes when an entity-centric question becomes a relation-centric one (Fig. 1(a)). "Who is Meghan Markle's husband's grandmother?" is answered by path A2. After reformulation, "How are Meghan Markle and Queen Elizabeth II associated?" is answered well by both A2 and A3, although A3 is not the original path.

Scoring against the original path would therefore measure how well a method recovers the original entity-centric reasoning, NOT how informative the relational answer is. This is why we use preference-based metrics together with an independent human evaluation (Sec. 5), which we have extended to 35 queries across all seven KGs (see our response to Reviewer aiXJ, Q3).

References:

[1] Yih et al., "The Value of Semantic Parse Labeling for Knowledge Base Question Answering", ACL 2016.

[2] Talmor and Berant, "The Web as a Knowledge-base for Answering Complex Questions", NAACL 2018.

[3] Azmy et al., "Farewell Freebase: Migrating the SimpleQuestions Dataset to DBpedia", COLING 2018.

[4] Usbeck et al., "9th Challenge on Question Answering over Linked Data (QALD-9)", NLIWoD-4 @ ISWC 2018.

[5] Zhang et al., "Variational Reasoning for Question Answering with Knowledge Graph", AAAI 2018.

[6] Liu et al., "Are LLMs Really Knowledgeable for Knowledge Graph Completion?", ISWC 2025.

[7] Kok and Domingos, "Statistical Predicate Invention", ICML 2007.

AuthorsOpenReview ↗

Response to W2 and W3

W2: We agree with this concern, and the paper states it directly at the start of Sec. 5: ``Our automatic metrics all rely on the reward we optimize.'' This is why we ran an independent human evaluation.

  • Role of automatic metrics. Average Reward measures how well a method meets our preference objective. Subgraph F1 measures agreement with a reward-optimal reference. We do not present either as independent evidence of answer quality. Connectivity Ratio measures structural validity and does not depend on the informativeness terms.
  • Independent validation of answer quality. In a blinded human evaluation, participants ranked anonymized answers by informativeness, coherence and usefulness. The instructions explain what a valid answer is, but never mention node degree, relation frequency, compactness or our reward.
    • Original study (Sec. 5, Appendix C). In a small-scale study with 4 queries and 49 participants, UniRel was preferred over GNN-RAG and SubgraphRAG in 80-92% of informativeness and 67-96% of usefulness judgments, significant on all four queries. It was also significantly preferred over its variant without entity informativeness in 11 of 12 query-criterion pairs, and over its variant without relation informativeness in 7 of 12.
    • Extended study. To strengthen this evidence, we extended the study to 35 queries across all seven KGs with 205 participants (see our response to Reviewer aiXJ, Q3). UniRel is preferred over the baseline in 64% of informativeness, 61% of coherence and 64% of usefulness judgments. It is also preferred over w/o RentR_{ent} and w/o RrelR_{rel} in 55-58% of judgments, so both terms contribute, with smaller margins than against the baseline. All comparisons are significant (p<0.001p < 0.001).
    • Participant comments. In both studies, participants said without being told that they preferred specific connections over generic shared attributes such as gender or nationality (Appendix C.4).

So, without being told what our reward favors, people judge the answers it produces as more informative and useful.

W3: We agree that degree and IDF are statistical proxies. We use the extended human study (35 queries, 205 participants; see our response to Reviewer aiXJ, Q3).

  • Human validation. On average, both terms make answers more informative to people. UniRel is preferred over w/o RentR_{ent} in 55% and over w/o RrelR_{rel} in 57% of informativeness judgments (p<0.001p < 0.001), although participants were never told what our reward favors.

    • Entity informativeness. For ``How are Meghan Markle and Queen Elizabeth II associated?'' (Fig. 1(a)), UniRel answers that Meghan married Prince Harry, whose grandmother is the Queen. Without RentR_{ent}, the answer is only that both belong to the British Royal Family, a large group with many members. 24 of 30 participants ranked UniRel's answer higher.
    • Relation informativeness. For ``How are Princess Eugénie of Sweden and Lovisa of Sweden connected?'', UniRel answers that Eugénie is Lovisa's aunt. Without RrelR_{rel}, the answer is that both were born in Stockholm Palace, which relies on a very common relation (place of birth). 20 of 30 participants ranked UniRel's answer higher.
  • Limitations. The gains vary by KG and are smallest on DBpedia and UMLS. The study reveals two failure modes behind this.

    • Rare but meaningless relations (DBpedia). IDF rewards rare relations, but some rare relations carry little meaning. For "How are 2001: A Space Odyssey and Dune related?", UniRel answers that both are in English, through the rare relation tv_program_languages. Without RrelR_{rel}, the answer is that both are science fiction. 24 of 30 participants ranked the science fiction answer first.
    • Abstract ontologies (UMLS). In UMLS, nodes are abstract categories such as Fungus or Family Group, not real-world entities, so node degree says little about how specific an answer is. For example, to connect Family Group and Self Help or Relief Organization, 19 of 29 participants ranked first a path through Professional or Occupational Group, which interacts with families and manages relief organizations. UniRel's path instead states that families perform Governmental or Regulatory Activity.
  • Applicability. Degree and IDF are simple statistics that need no annotation, and they improve human-judged informativeness on average. Their failures are specific: rare relations that carry little meaning, and KGs whose nodes are abstract categories. We will add this analysis, with the full per-query results, to Appendix C.

These limitations show that there is still room to design better reward proxies, including personalized ones. Such work is orthogonal to our main contributions: the problem definition of relation-centric KGQA and the UniRel framework. Since each component of UniRel is modular (Sec. 3), better proxies can be used directly within the same framework.

Thanks for the response. This reviewer suggests moving some key information from the appendix to the main text to improve clarity. Based on the authors' response, this reviewer decides to raise the score to 3.

Thank you for your positive feedback and for raising the score. We appreciate your suggestion and will move the key information from the appendix to the main text in the revised version to improve clarity and readability.

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

This paper introduces relation centric KGQA, in which the answer is a subgraph that represents the semantic relations among entities. To address the relation centric KGQA, this paper proposes UniRel, which is a unified modular framework that combines a subgraph retriever with an LLM fine-tuned using reinforcement learning. The framework uses a reward function to prefer compact and specific subgraphs with informative relations and low-degree intermediate entities. Experiments across seven knowledge graphs and five backbones show that UniRel improves answer quality over existing baselines.

Critical strengths
  1. This paper extends the KGQA task from entity centric KGQA to relation centric KGQA.

  2. This paper proposes an unified modular framework (e.g., UniRel) to address the relation centric KGQA.

Critical weaknesses
  1. The proposed method requires iterative pruning of subgraphs, which is inefficient, especially for large-scale dense graphs.

  2. The detailed process of query construction is insufficient. It does not clearly explain what templates are used to convert entity pairs into queries and what question types are involved. If the only question asked is "How are two entities associated?", then the question type is too monotonous.

  3. Only Qwen and Llama are included, lacking other types of LLMs.

  4. There are only two baselines for comparison, lacking comparison with more recent methods; moreover, these two baselines have not been adapted in any way for this new task, so whether such a comparison is fair is questionable.

  5. The credibility of evaluating only with Connectivity Ratio (C) and Average Reward, without providing ground-truth answers, is also debatable.

Questions for authors

See Weaknesses.

3 comments
AuthorsOpenReview ↗

Responses to W1, W2, and W3

We thank the reviewer for the detailed feedback, and apologize for the late response. We used the time to run an extended human evaluation (35 queries across all seven KGs, 205 participants), which we report in W5.

W1: UniRel's pruning cost depends on the local neighborhoods of the seed entities, not on the size of the whole KG. Retrieval takes 6--49 ms per query in our experiments, including dense neighborhoods with over 50,000 candidate entities.

  • Cost is local. The pruning steps are graph traversal, set intersection and union-find. All of them are confined to the kk-hop neighborhoods of the seed entities, so the cost is governed by the size of these neighborhoods rather than by the size of the KG (Appendix A.3-A.4).
  • Runtime. The table below reproduces Appendix A.5 (Table 7). We measure the wall-clock time per query on a MacBook Pro (Apple M2 Pro, 16 GB), single-threaded, averaged over the test queries of each dataset. Degree and IDF tables are precomputed once per KG and excluded from the timing. Stages 1–2 and 4–5 each run as one loop and are reported together. Wall-clock retrieval time per query (ms). | Dataset | kk | Total | Selection | Stage 1–2 | Stage 3 | Stage 4–5 | | --- | --- | --- | --- | --- | --- | --- | | Freebase13 | 2 | 29.3 | 16.7 | 12.1 | <0.1 | 0.5 | | DBpedia50 | 2 | 6.3 | 3.7 | 1.4 | <0.1 | 1.2 | | DBpedia50 | 3 | 19.1 | 9.2 | 3.3 | 0.3 | 6.3 | | DBpedia50 | 4 | 49.4 | 23.4 | 7.8 | 1.5 | 16.6 |
  • Results Analysis.
    • Dense neighborhoods. On Freebase13, the initial candidate subgraph contains 54,319 entities on average (Table 12), since hubs such as MaleMale have tens of thousands of neighbors. Retrieval still takes 29.3 ms per query.
    • Graph size. From DBpedia50 to Freebase13 at k=2k = 2, the number of triples grows 8.6×8.6\times, while retrieval time grows 4.6×4.6\times. Runtime grows more slowly than the graph, consistent with Appendix A.4.
    • Reasoning depth. On DBpedia50, time grows from 6.3 to 19.1 to 49.4 ms as kk goes from 2 to 4, with selection time growing by about 2.5×2.5\times per hop.

These results cover the KGs and depths in our experiments. Cost grows with the size of the local neighborhood, especially at larger kk, but stays within tens of milliseconds in all evaluated settings.

W2: All queries share one information need by design: how the given entities are connected. The diversity of the task lies in the relational structures the model must discover, not in the wording of the question.

  • Query construction. Queries are built from existing KGQA benchmarks, either by converting topic--answer pairs into seed pairs or by sampling pairs from an entity pool built from these benchmarks. Our response to Reviewer paDH (Q1) describes the full procedure and the sources for each KG, which we will add to Appendix B.2.
  • Templates. Appendix B.2 shows two of the templates. The full set is:
    • ``How are [entity1] and [entity2] associated?''
    • ``For what reason are [entity1] and [entity2] related?''
    • ``How are [entity1] and [entity2] connected?''
    • ``What is the relationship between [entity1] and [entity2]?''
    • ``What connections exist between [entity1] and [entity2]?''
    • ``Through which entities and relations are [entity1] and [entity2] connected?''
    • ``What relational connections link [entity1] and [entity2]?''
    • ``In what ways are [entity1] and [entity2] related?''

These templates vary the wording while keeping the same open-ended objective.

  • Question type and diversity. Entity-centric KGQA asks for a specific answer, so it uses varied question types such as whatwhat, whenwhen and whowho. Relation-centric KGQA instead asks how the given entities are connected, without naming a target relation. Keeping one information need across queries is therefore part of the task definition, in the same way that entity-centric KGQA always asks for an answer entity. The reasoning each query requires still varies widely: (1) Domains: seven KGs covering general knowledge, movies and biomedicine. (2) Reasoning distance: range from 1 to 4 hops. (3) Number of seeds: both two-entity and multi-entity queries. In every case, the model must find informative connections without being given a target relation or reasoning path.

W3: UniRel trains the reasoner with RL, so it requires open-weight models that can be fine-tuned rather than inference-only APIs. We therefore use two widely adopted open-weight families, covering diverse architectures and scales (Sec. 4.1): Qwen: Qwen-2.5-3B/7B/14B-Instruct; Llama: Llama-3.2-3B-Instruct and Llama-3.1-8B-Instruct. UniRel improves performance within both families (Sec. 4.2). The two families also generalize differently: when entity and relation names are replaced with random identifiers, Qwen degrades sharply while Llama remains largely stable (Sec. 4.4). UniRel remains effective across both, which supports its applicability across model families.

AuthorsOpenReview ↗

Response to W4 and W5

W4: We compare against recent methods at two levels: end-to-end pipelines that run in our setting, and component-level comparisons for methods that do not transfer as a whole.

  • End-to-end baselines. GNN-RAG and SubgraphRAG are compatible with large input graphs in our setting, so we use them as end-to-end baselines (Sec. 4.1).

  • Recent methods as component baselines. Other recent methods are included in the ablations of Sec. 4.3 (Table 2, DBpedia50, Llama-3.1-8B-Instruct). Each comparison replaces a single component of UniRel and keeps all others fixed.

    • Retrievers. The GNN-based retriever of GNN-RAG, PCST from G-Retriever and the SubgraphRAG retriever reach 36.2%, 1.6% and 35.0% connectivity, against 99.0% for UniRel's retriever.
    • Reasoning. Prompting, the recent SFT-based RoE and SFT on the reward-optimal subgraph reach 38.8%, 1.4% and 93.0% connectivity, against 99.0% for RL-tuned UniRel.
  • Methods that do not transfer directly.

    • Agentic search (ToG[1], PoG[2]). These methods list all neighbors of the current entity in the prompt at each hop. This is impractical when a hub such as MaleMale has tens of thousands of neighbors. On Freebase13, our initial candidate subgraphs contain 54,319 entities on average (Table 12). Our pruning reduces them to 6.4-30.2 entities across the seven datasets (Table 13), which the LLM can read at once.
    • Path planning (RoG[3]). RoG trains its planner on paths to a gold answer entity, which our setting does not have.
  • Adaptation and fairness. We adapted GNN-RAG and SubgraphRAG to relation-centric queries while keeping their original retrieval mechanisms. GNN-RAG keeps its GNN-based scoring and path retrieval, but uses the given seed entities to retrieve relational paths instead of predicting a single answer entity. SubgraphRAG keeps its triple-scoring retriever, and the retrieved triples serve as the candidate relational subgraph. Both baselines were retrained on our training split and evaluated on the same KGs, test queries and metrics as UniRel. The component comparisons in ablation study further isolate each part of UniRel from other differences between pipelines.

W5: Relation-centric KGQA has no single ground-truth answer, so we evaluate answers from several angles, including a human evaluation that does not rely on our reward.

  • No single ground truth. Several different subgraphs can be equally valid answers to the same query. In Fig. 1(a), ``How are Meghan Markle and Queen Elizabeth II associated?'' can be answered through Prince Harry (A2) or through Prince Harry and Prince William (A3). Both are informative. Scoring against one reference would penalize the other.
  • Evaluation Metrics.
    • Connectivity Ratio checks structural validity: whether the answer connects all seed entities. It does not depend on the informativeness terms.
    • Average Reward and Subgraph F1 measure how well an answer meets our preference objective. Subgraph F1 compares against a reference subgraph found by exhaustive search under the same objective. Both are tied to our reward, so we do not treat them as independent evidence.
  • Blinded human evaluation provides that independent evidence. Participants ranked anonymized answers by informativeness, coherence and usefulness, without knowing our reward.
    • Original study (Sec. 5, Appendix C): in a small-scale study with 4 queries and 49 participants, UniRel is preferred over the baselines in 80-92% of informativeness and 67-96% of usefulness judgments, significant on each query (p≤0.011p \leq 0.011).
    • Extended study: to strengthen this evidence, we extended the study to 35 queries across all seven KGs with 205 participants (see our response to Reviewer aiXJ, Q3). UniRel is preferred over the baseline in 64% of informativeness, 61% of coherence and 64% of usefulness judgments (p<0.001p < 0.001).

Together, these show that UniRel's answers are structurally valid, meet the stated objective, and are preferred by people who do not know that objective.

References:

[1] Sun et al., "Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph", ICLR 2023.

[2] Chen et al., "Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs", NeurIPS 2024.

[3] Luo et al., "Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning", ICLR 2024.

Thank you for the response. I'll keep my positive score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.