Research map / Large language models / Retrieval and knowledge
Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Rethinks query-embedding complex query answering by formalizing EFO queries, shows prior tree-form formulation is not a subset of EFO, adds a 10-formula real EFO dataset, and proposes FIT, a fuzzy-logic neural-symbolic method on pretrained link predictors.
Problem
Complex query answering on incomplete knowledge graphs is usually studied via tree-form queries under query embedding, which does not cover the full family of existential first-order (EFO) queries; prior formulations are syntactically and semantically unsound for general EFO queries.
Approach
Characterize tree-form queries, show they are not a subset of EFO, define EFO queries as multigraph query graphs, and apply fuzzy t-norm/t-conorm semantics over neural link predictor matrices with a stepwise graph-reduction inference (FIT) that is differentiable and provably faithful/perfect.
Key results
- On the new real EFO dataset, FIT averages 23.9 MRR on FB15k-237, 64.8 on FB15k, and 37.3 on NELL, outperforming all baselines (best baseline QTO: 21.8, 53.4, 35.3).
- On positive tree-form queries, FIT averages 27.4 MRR on FB15k-237 vs 25.3 for CQD and 24.1 for LMPNN; on FB15k it averages 72.5 vs 68.5 for CQD.
- Deductible answers on BetaE query types reach 100 MRR for 1p, 2p, 3p, 2i, 3i, pi, ip, 2u, up, but lower for negated types (e.g., 65.3 for 3in).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FIT instead of QTO | Real EFO query answering · FB15k-237 | MRR (%): 21.8 -> 23.9 | Helped |
| Use FIT instead of QTO | Real EFO query answering · FB15k | MRR (%): 53.4 -> 64.8 | Helped |
| Use FIT instead of QTO | Real EFO query answering · NELL | MRR (%): 35.3 -> 37.3 | Helped |
| Use FIT instead of CQD | Tree-Form positive query answering · FB15k-237 | MRR (%): 25.3 -> 27.4 | Helped |
| Use FIT instead of LMPNN | Tree-Form negative query answering · FB15k-237 | MRR (%): 8.5 -> 13.4 | Helped |
| Use FIT instead of CQD | Tree-Form positive query answering · FB15k | MRR (%): 68.5 -> 72.5 | Helped |
| Use FIT instead of LMPNN | Tree-Form negative query answering · FB15k | MRR (%): 20.9 -> 35.5 | Helped |
| Use FIT instead of CQD | Tree-Form positive query answering · NELL | MRR (%): 31.8 -> 33.4 | Helped |
| Use FIT instead of LMPNN | Tree-Form negative query answering · NELL | MRR (%): 8.9 -> 13.2 | Helped |
Surprising findings
- The tree-form 'pni' query in prior datasets actually encodes a universal quantifier, so previous datasets do not represent the intended EFO semantics.
- Previously reported pni answers are inconsistent with EFO semantics; the authors re-sampled answers for it.
Limitations
- Self-loop query graphs are excluded from the new dataset.
- Testing-time neural matrix construction is more complicated and relies on approximation of observed-triple scaling.
- Enumeration on cycles relies on hyperparameter M to bound candidate enumeration.
Experimental setup
Datasets: FB15k-237 FB15k NELL BetaE query dataset
Benchmarks: Real EFO dataset (new) BetaE query dataset (tree-form, FB15k-237, FB15k, NELL)
Metrics: MRR
Baselines: BetaE LogicE ConE QTO CQD LMPNN
Builds on: BetaE CQD QTO LMPNN ConE
Closest papers by meaning
- Efficient Embeddings of Logical Variables for Query Answering over Incomplete Knowledge Graphs (AAAI 2023 · similarity 0.92)
- Neural-Symbolic Models for Logical Queries on Knowledge Graphs (ICML 2022 · similarity 0.92)
- Neural Methods for Logical Reasoning over Knowledge Graphs (ICLR 2022 · similarity 0.92)
- Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning (AAAI 2025 · similarity 0.88)
- Is Complex Query Answering Really Complex? (ICML 2025 · similarity 0.88)
- Reasoning of Large Language Models over Knowledge Graphs with Super-Relations (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.