Is Complex Query Answering Really Complex?

Cosimo Gregucci; Bo Xiong; Daniel Hernandez; Lorenzo Loconte; Pasquale Minervini; Steffen Staab; Antonio Vergari

cs.LGOct 16, 2024

Is Complex Query Answering Really Complex?

Authors: Cosimo Gregucci, Bo Xiong, Daniel Hernandez, Lorenzo Loconte, Pasquale Minervini, Steffen Staab, Antonio Vergari

Organizations: Institute for Artificial Intelligence, University of Stuttgart, Germany · Stanford University · School of Informatics University of Edinburgh Edinburgh, UK · University of Southampton, UK

Abstract

Complex query answering (CQA) on knowledge graphs (KGs) is gaining momentum as a challenging reasoning task. In this paper, we show that the current benchmarks for CQA might not be as complex as we think, as the way they are built distorts our perception of progress in this field. For example, we find that in these benchmarks, most queries (up to 98% for some query types) can be reduced to simpler problems, e.g., link prediction, where only one link needs to be predicted. The performance of state-of-the-art CQA models decreases significantly when such models are evaluated on queries that cannot be reduced to easier types. Thus, we propose a set of more challenging benchmarks composed of queries that require models to reason over multiple hops and better reflect the construction of real-world KGs. In a systematic empirical investigation, the new benchmarks show that current methods leave much to be desired from current CQA methods.

Figures & tables

Panel of Figure 1 — Figure 1: Query answers are not all equally hard when some links can be found in the training data as shown for the 2i1p query q 1 and fragments of the KG $\mathsf{FB15k237}$ , where $r_{1}=\mathsf{distributedVia}^{-1}$ , $r_{2}=\mathsf{locatedIn}^{-1}$ and $r_{3}=\mathsf{performedIn}^{-1}$ . Its different answers can be obtained by traversing the training graph (continuous line) and predicting the missing links (dotted lines). (Top) Example answer that requires all links to be predicted. (Bottom) Example answers that require only a subset of the links to be predicted and that, therefore, can be reduced to the simpler types 1p , 2p , and 2i (see Sec. 2 and Figure 2 ).

Figure 2: Query structures we consider , adapted from Ren & Leskovec (2020) and including path ( p ), intersection ( i ), union ( u ) structures. Sec. 2 for their logical formulation. See App. B for additional query structures including negation .

	$\mathsf{FB15k237}$									$\mathsf{NELL995}$
	1p	2p	3p	2i	3i	1p2i	2i1p	2u	2u1p	1p	2p	3p	2i	3i	1p2i	2i1p	2u	2u1p
1p	100	-	-	-	-	-	-	-	-	100	-	-	-	-	-	-	-	-
2p	98.1	1.9	-	-	-	-	-	-	-	97.6	2.4	-	-	-	-	-	-	-
3p	97.2	2.7	0.1	-	-	-	-	-	-	95.6	4.3	0.1	-	-	-	-	-	-
2i	96.0	-	-	4.0	-	-	-	-	-	94.0	-	-	6.0	-	-	-	-	-
3i	91.6	-	-	8.2	0.2	-	-	-	-	87.4	-	-	12.1	0.5	-	-	-	-

Table 1: The great majority of QA pairs are of the much easier partial-inference type (non-diagonal), rather than of the harder full-inference type (diagonal). For each query type (as rows) we show the percentage of the QA pairs that can be reduced to an easier query type (as columns) for datasets

\mathsf{FB15k237}

and

\mathsf{NELL995}

. Most of the complex queries can be reduced to simple link prediction queries (i.e., 1p ). We denote as ‘-’ those reductions that are not possible given the sub-graph structure induced by the query type.

	3p								2i1p
method	ovr	1p	2p	3p	2i	3i	1p2i	2i1p	ovr	1p	2p	3p	2i	3i	1p2i	2i1p
GNN-QE	11.8	12.0	4.4	4.8	-	-	-	-	18.9	19.2	8.2	-	6.2	-	-	3.4
ULTRAQ	8.9	9.0	4.6	4.4	-	-	-	-	18.6	18.9	8.5	-	5.1	-	-	8.1
ConE	11.0	11.0	5.4	2.6	-	-	-	-	14.0	13.8	9.7	-	12.8	-	-	5.6
CQD	7.8	7.8	3.4	1.8	-	-	-	-	20.7	21.0	10.5	-	6.7	-	-	7.6
CQD-Hybrid	11.0	11.1	3.6	4.4	-	-	-	-	24.0	24.6	10.0	-	4.6	-	-	7.5

Table 2: SoTA performance drops significantly on full-inference QA pairs as shown for the MRR for 3p and 2i1p queries on

\mathsf{FB15k237}

. Compare the overall MRR achieved on all available testing queries (column “ovr”) with that achieved on the 1p reductions (“1p” column, i.e., when only a single link is truly missing): they are extremely close. This is because

Panel of Figure 3 — Figure 3: Some answers of union queries can be reached by a single missing link, while the other link does not exist , as shown for this 2u query and fragments of the KG $\mathsf{FB15k237}$ , where $r_{1}=\mathsf{releasedIn}$ , $r_{2}=\mathsf{crewMemberOf}$ . (Top) Example of an answer that we retain in our benchmark, being reachable by two missing links. (Bottom) Example of answers we filter out, being only reachable by one missing link.

	Model	2p	3p	2i	3i	1p2i	2i1p	2u1p
$\mathsf{FB15k237}$	GNN-QE	14.7	11.8	38.3	54.1	31.1	18.9	9.7
	ULTRAQ	11.5	8.9	35.7	51.0	29.6	18.6	7.3
	CQD	13.2	7.8	35.0	48.5	27.5	20.7	10.5
	ConE	12.8	11.0	32.6	47.3	25.5	14.0	7.4
	CLMPT	13.9	11.3	37.5	51.9	28.4	19.3	11.4
	CQD-Hybrid	15.0	11.0	37.6	52.7	31.2	24.0	10.3

Table 3: Exploiting training links during inference boosts MRR on existing benchmarks, as shown by our CQD-Hybrid model compared to previous SoTA, for several query types. CQD-Hybrid always achieves higher MRR scores when compared to CQD, and outperforms more sophisticated non-hybrid baselines 9/14 times. Best values in bold and second best underlined.

Figure 4: MRR of SoTA on the new benchmarks is significantly lower than the old ones as reported for

\mathsf{FB15k237}

and

\mathsf{NELL995}

(in blue) versus our new

\mathsf{FB15k237}

\mathsf{H}

and

\mathsf{NELL995}

\mathsf{H}

(in orange) for different query types and SoTA models.

$\mathsf{FB15k237}$			$\mathsf{NELL995}$
method	1p	2u all	2u filtered	1p	2u all	2u filtered
GNN-QE	42.8	16.2	40.7	53.6	15.4	34.8
ULTRAQ	40.6	13.2	33.6	38.9	10.2	21.3
CQD	46.7	17.6	32.7	60.4	19.9	35.9
ConE	41.8	14.9	29.9	60.0	14.9	28.2
CLMPT	45.3	14.8	32.8	58.1	18.6	39.6

Table 4: Queries of type 2u are less hard than previously thought in terms of MRR, with our filtered 2u queries having comparable performance to 1p , as discussed in Sec. 2 , in contrast with the results of the 2u queries originally used ( 2u all).

	Model	1p	2p	3p	2i	3i	1p2i	2i1p	2u	2u1p	4p	4i	2in	3in	2pi1pn	2nu1p	2in1p
$\mathsf{FB15k237}$ + $\mathsf{H}$	GNN-QE	42.8	5.2	4.0	6.0	8.8	5.6	9.9	32.5	10.0	4.3	20.0	6.8	6.5	3.7	5.0	3.3
	ULTRAQ	40.6	4.5	3.5	5.2	7.2	5.3	10.1	29.4	8.3	3.8	16.4	5.3	5.5	2.6	3.7	2.2
	CQD	46.7	4.4	2.4	11.3	12.8	6.0	11.5	40.1	10.6	1.1	23.8	3.3	2.6	0.6	4.2	1.2
	CQD-Hybrid	46.7	4.8	3.1	6.0	8.6	5.5	12.9	42.2	12.0	2.4	17.4	4.7	1.6	1.0	2.4	1.3
	ConE	41.8	4.6	3.9	9.1	10.3	3.8	7.9	22.8	6.0	3.5	20.3	5.1	4.9	2.9	3.3	3.6
	QTO	46.7	4.9	3.7	8.7	10.1	6.1	13.5	30.6	11.2	3.9	20.2	10.6	3.1	2.0	3.3	1.5

Table 5: There is no clear SoTA method for the new benchmarks. As shown in Figure 4 , the MRR on the new benchmarks is significantly lower than the old ones. For example, for 3i queries on

\mathsf{FB15k237}

\mathsf{H}

, QTO has an MRR of 10.1, while for

\mathsf{FB15k237}

it was 54.6. For the stratified analysis see Tables D.3 , D.4 , D.5 and D.6 .

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

	$\mathsf{FB15k237}$		$\mathsf{NELL995}$
	partial-inference	full-inference		partial-inference	full-inference
2in	-	100		-	100
3in	95.4	4.6		93.9	6.1
2pi1pn	98.4	1.6		97.8	2.2
2nu1p	-	100		-	100
2in1p	97.4	2.6		95.6	4.4

Appendix

Table A.1: Most negated queries have training links in the positive reasoning tree of the QA pairs . Partial-inference and full-inference refer to the positive reasoning tree. ’-’ refers to reductions that are not possible.

$\mathsf{FB15k237}$				$\mathsf{NELL995}$
Query type	method	overall	partial-inf	full-inf	overall	partial-inf	full-inf
2in	GNN-QE	6.8	-	6.8	5.5	-	5.5
	ULTRAQ	5.3	-	5.3	4.5	-	4.5
	CQD	3.3	-	3.3	4.2	-	4.2
	CQD-hybrid	4.7	-	4.7	5.1	-	5.1
	QTO	10.6	-	10.6	11.3	-	11.3

Appendix

Table A.2: Even for queries including negation the MRR results are highly influenced by the presence of existing links in the positive reasoning tree of the QA pairs. For example, for 3in queries of

\mathsf{FB15k237}

, the overall MRR of QTO is 16.1, while its MRR on the portion of full-inference QA pairs is only 2.1. Hence, the overall result is highly influence by the vast number of partial inference QA pairs in the benchmark (see Table A.1 )

$\mathsf{FB15k237}$					$\mathsf{NELL995}$
Query type	method	overall	overall (new)	1p	2u	2u1p	overall	overall (new)	1p	2u	2u1p
2u	GNN-QE	16.2	40.7	/	40.7	-	15.4	34.8	/	34.8	-
	ULTRAQ	13.2	33.6	/	33.6	-	10.2	21.3	/	21.3	-
	CQD	17.6	32.7	/	32.7	-	19.9	35.9	/	35.9	-
	ConE	14.3	29.9	/	29.9	-	14.9	28.2	/	28.2	-
2u1p	GNN-QE	13.4	9.7	8.7	50.9	13.1	8.8	8.8	6.3	53.1	2.0

Appendix

Table A.3: Full inference 2u QA pairs show higher performance than non-filtered, while full-inference 2u1p pairs show lower or comparable performance. Results on union queries for existing benchmarks and comparison between old and new overalls. ‘-’ refers to reductions that are not possible, while ‘/’ to reductions that are possible but that are not present in the data.

Query type	method	overall	1p	2p	3p	2i	3i	1p2i	2i1p	2u	2u1p
1p	GNN-QE	53.6	53.6	-	-	-	-	-	-	-	-
	ULTRA-query	38.9	38.9	-	-	-	-	-	-	-	-
	ConE	60.0	60.0	-	-	-	-	-	-	-	-
	CQD	60.4	60.4	-	-	-	-	-	-	-	-
	CQD-hybrid	60.4	60.4	-	-	-	-	-	-	-	-
	QTO	60.3	60.3	-	-	-	-	-	-	-	-

Appendix

Table A.4: The best model on all available

\mathsf{NELL995}

queries (column “overall”) and the best on the full inference queries (diagonal) is different for 6/7 query types , excluding 1p and 2u, being already of type full-inference. Comparison of MRR scores for SoTA methods for the different subtypes

\mathsf{NELL995}

queries can be reduced to. Best in bold.

Query type	method	overall	1p	2p	3p	2i	3i	1p2i	2i1p	2u	2u1p
1p	GNN-QE	42.8	42.8	-	-	-	-	-	-	-	-
	ULTRA-query	40.6	40.6	-	-	-	-	-	-	-	-
	ConE	41.8	41.8	-	-	-	-	-	-	-	-
	CQD	46.7	46.7	-	-	-	-	-	-	-	-
	CQD-hybrid	46.7	46.7	-	-	-	-	-	-	-	-
	QTO	46.7	46.7	-	-	-	-	-	-	-	-

Appendix

Table A.5: The best model on all available

\mathsf{FB15k237}

queries (column “overall”) and the best on the full inference queries (diagonal) is different for 5/7 query types , excluding 1p and 2u, those (q,a) pairs being all of type full-inference. Comparison of MRR scores for SoTA methods for the different subtypes

\mathsf{FB15k237}

queries can be reduced to. Best in bold.

Query	relation name	frequency(%)	anchor entity	frequency(%)
$\mathsf{FB15k237}$
1p	film_release_region	7.5	USA	0.7
2p	location/location/contains	8.6	USA	4.0
3p	location/location/contains	11.6	USA	3.3
2i	people/person/profession	16.4	USA	16.4
3i	people/person/gender	18.7	USA	30.1

Appendix

Table A.6: There is no significant unbalancement in anchor nor relation names for each query type . Most frequent relation name and anchor per query type in the old benchmarks. Highest value in bold.

Figure B.1: Query structures including negation , adapted from Ren & Leskovec (2020) , where “2in1p” queries are referred as “inp”. We explicitly mention the number of steps involved in a path or conjunction, as this is a factor of complexity. Analogously, “pin”, “pni” queries from Ren & Leskovec (2020) are now “2pi1np”, and “2nu1p”. See App. B for their logical formulation.

Query	relation name	frequency(%)	anchor entity	frequency(%)
$\mathsf{FB15k237}$ + $\mathsf{H}$
1p	film_release_region	7.5	USA	0.7
2p	/people/person/nationality	15.3	/m/08mbj5d/m/08mbj5d	3.6
3p	/people/person/profession	14.2	/m/092ys_y	5.4
4p	/dataworld/gardening_hint/split_to	20.0	/m/0dq_5	5.5
2i	/people/person/profession	17.2	/m/09c7w0	15.5

Appendix

Table D.1: The new benchmarks are generated such that anchors and relation names cannot appear more than 20% in each query type. Most frequent relation name and anchor per query type in the new benchmarks.

Model	CLMPT	CQD	CQD-h	ConE	GNNQE	QTO	ULTRA
CLMPT	—	3.32e-63	1.82e-80	3.92e-01	8.28e-71	1.06e-188	8.55e-35
CQD	3.32e-63	—	1.48e-04	1.94e-52	1.72e-01	5.27e-38	2.31e-06
CQD-h	1.82e-80	1.48e-04	—	8.88e-75	5.08e-03	8.41e-15	6.91e-16
ConE	3.92e-01	1.94e-52	8.88e-75	—	6.65e-60	1.38e-165	7.04e-28
GNNQE	8.28e-71	1.72e-01	5.08e-03	6.65e-60	—	4.79e-30	2.32e-09
QTO	1.06e-188	5.27e-38	8.41e-15	1.38e-165	4.79e-30	—	2.22e-70

Appendix

Table D.2: Pairwise Mann–Whitney U test

p

-values on reciprocal ranks of 2p queries in

\mathsf{FB15k237}

\mathsf{H}

. Lower values indicate stronger evidence of a significant difference between model performances.

Query type	method	overall	1p	2p	3p	4p	2i	3i	4i	1p2i	2i1p	2u	2u1p
1p	GNN-QE	42.8	42.8	-	-	-	-	-	-	-	-	-	-
	ULTRA-query	40.6	40.6	-	-	-	-	-	-	-	-	-	-
	ConE	41.8	41.8	-	-	-	-	-	-	-	-	-	-
	CQD	46.7	46.7	-	-	-	-	-	-	-	-	-	-
	CQD-hybrid	46.7	46.7	-	-	-	-	-	-	-	-	-	-
	QTO	46.7	46.7	-	-	-	-	-	-	-	-	-	-

Appendix

Table D.3: Stratified analysis on

\mathsf{FB15k237}

\mathsf{H}

Query type	method	overall	1p	2p	3p	4p	2i	3i	4i	1p2i	2i1p	2u	2u1p
1p	GNN-QE	53.6	53.6	-	-	-	-	-	-	-	-	-	-
	ULTRA-query	38.9	38.9	-	-	-	-	-	-	-	-	-	-
	ConE	60.0	60.0	-	-	-	-	-	-	-	-	-	-
	CQD	60.4	60.4	-	-	-	-	-	-	-	-	-	-
	CQD-hybrid	60.4	60.4	-	-	-	-	-	-	-	-	-	-
	QTO	60.3	60.3	-	-	-	-	-	-	-	-	-	-

Appendix

Table D.4: Stratified analysis on

\mathsf{NELL995}

\mathsf{H}

Query type	method	overall	1p	2p	3p	4p	2i	3i	4i	1p2i	2i1p	2u	2u1p
1p	GNN-QE	12.2	12.2	-	-	-	-	-	-	-	-	-	-
	ULTRA-query	6.3	6.3	-	-	-	-	-	-	-	-	-	-
	ConE	3.5	3.5	-	-	-	-	-	-	-	-	-	-
	CQD	16.6	16.6	-	-	-	-	-	-	-	-	-	-
	CQD-hybrid	16.6	16.6	-	-	-	-	-	-	-	-	-	-
	QTO	16.6	16.6	-	-	-	-	-	-	-	-	-	-

Appendix

Table D.5: Stratified analysis on

\mathsf{ICEWS18}

\mathsf{H}

$\mathsf{FB15k237}$ + $\mathsf{H}$				$\mathsf{NELL995}$ + $\mathsf{H}$			$\mathsf{ICEWS18}$ + $\mathsf{H}$
Query type	method	ovr	part-inf	full-inf	ovr	par-inf	full-inf	ovr	par-inf	full-inf
2in	GNN-QE	6.8	-	6.8	5.5	-	5.5	4.5	-	4.5
	ULTRAQ	5.3	-	5.3	4.5	-	4.5	2.3	-	2.3
	CQD	3.3	-	3.3	4.2	-	4.2	1.5	-	1.5
	CQD-hybrid	4.7	-	4.7	5.1	-	5.1	1.7	-	1.7
	QTO	10.6	-	10.6	11.3	-	11.3	4.9	-	4.9

Appendix

Table D.6: Also for queries involving negation, there is no clear SoTA method for the new benchmarks. The MRR on the new benchmarks is significantly lower than the old ones. For example, for 3in queries on

\mathsf{FB15k237}

\mathsf{H}

, QTO has an MRR of only 3.1, while for

\mathsf{FB15k237}

it was 16.1.

Dataset

1p2i

2i1p

2u1p

2in

3in

2pi1pn

2nu1p

2in1p

\mathsf{FB15k237}

512

128

256

512

prod

512

prod

512

prod

\mathsf{NELL995}

512

256

512

prod

512

prod

512

prod

Appendix

Table F.1: CQD hyperparameters old benchmarks. tn = tnorm. p=prod, m=min. Note that for 1p neither the k nor the tnorm are needed.

Dataset

1p2i

2i1p

2u1p

2in

3in

2pi1pn

2nu1p

2in1p

\mathsf{ICEWS18}

\mathsf{H}

512

256

512

prod

512

prod

512

prod

Appendix

Table F.2: CQD hyperparameters

\mathsf{ICEWS18}

\mathsf{H}

benchmark. tn = tnorm. p=prod, m=min

Dataset	Entities	Relation Names	Training Links	Validation Links	Test Links	Total Links
$\mathsf{FB15k237}$	14,505	237	272,115	17,526	20,438	310,079
$\mathsf{NELL995}$	63,361	200	114,213	14,324	14,267	142,804
$\mathsf{ICEWS18}$ + $\mathsf{CQ}$ ( new )	20,840	250	213,304	25,048	24,689	263,041

Appendix

Table G.1: Statistics of knowledge graphs used to generate complex queries

Explore similar work

Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models
Aug 24, 2026Chenhui Liu, Jianpeng Zhou, Jiahai WangKnowledge Graph Question Answering LLM Reasoning with Graphs
Sun Yat-sen University, Guangzhou 510006, China
RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering
Mar 20, 2026Bo Yuan, Hexuan Deng, Xuebo Liu +1Knowledge Graph Question Answering LLM Reasoning with Graphs
Institute of Computing and Intelligence, Harbin Institute of Technology, Shenzhen, China · Zhongguancun Academy, Beijing, China
Graph Query Generation with Constraint-guided Large Language Agents
Apr 9, 2026Mengying Wang, Nicolaas Jedema, Rahul Pandey +3Knowledge Graph Question Answering LLM Agents
Case Western Reserve University · Amazon · Meta +1

Aug 24, 2026J/K move · Enter open · S save

Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models

Chenhui Liu, Jianpeng Zhou, Jiahai Wang

Sun Yat-sen University, Guangzhou 510006, China

Knowledge Graph Question Answering LLM Reasoning with Graphs Multi-Hop QA Graph Reasoning LLM Grounding

Open paper AskPDF arXiv

Knowledge graph question answering (KGQA) is a key task for evaluating KG-augmented Large Language Models (LLMs), and complex KGQA that requires multi-hop reasoning is especially challenging. Solving a complex query involves two coupled phases: candidate retrieval, which locates answer candidates over the KG, and constraint handling, which filters these candidates against the query constraints. Faithful reasoning requires grounding both phases in the KG. However, existing agent-based methods ground candidate retrieval through entity-centric exploration, while leaving constraint handling to the LLM's internal knowledge, which leads to two critical limitations. (1) Unreliable entity pruning: entity-centric exploration uses entities as search units and must prune them to a fixed-size subset at each hop. Because entity information in KGs is often incomplete and a fixed-size subset cannot retain all valid entities, such pruning inevitably drops valid entities and ultimately leads to wrong answers. (2) Ungrounded constraint handling: query constraints are resolved from the LLM's internal knowledge rather than the KG, leaving the final answers unverifiable and prone to hallucination. To address these limitations, this paper introduces a relation-centric exploration paradigm, which uses relations rather than entities as search units and thus avoids unreliable entity pruning. Built on this paradigm, this paper proposes Compositional Chain-of-Relations (CCoR), a simple and effective framework that grounds both phases in the KG with two relation chains: a main chain for candidate retrieval and a constraint chain that verifies query constraints through explicit KG exploration. Experiments on four KGQA benchmarks show that CCoR consistently improves accuracy, faithfulness, and efficiency over strong baselines, with more pronounced gains on complex queries.

Abstract

Explore similar work

Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models

RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering

Graph Query Generation with Constraint-guided Large Language Agents