A collection of resources on the topic of Complex Logical Query Answering accompanying the paper Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases. Feel free to open PRs and issues to add new papers, datasets, and implementations!

This repo follows the Neural Query Engine taxonomy proposed in the paper (Figure 9).

Progressive scale of supported operators. That is, all models listed under the "NOT" category also support JOIN and UNION.

• Original metrics: ROC AUC and Average Percentile Rank over 1000 negative samples.
  • Proposed by original GQE (NeurIPS 2018), used by GQE+hashing, CGA, and TractOR. Not used after.
• Generalization: predicting hard answers (MRR / Hits@k).
  • Introduced by Query2Box (ICLR 2020). Standard metric.
• Generalization: from ranking to binary classification
  • Proposed in Approximate knowledge graph query answering: from ranking to binary classification
• Entailment: faithfulness - ability to recover easy answers (no link prediction) (MRR / Hits@k)
  • Proposed by EmQL (NeurIPS 2020)
• Estimating the cardinality of answer set size (Spearman's rank correlation, MAPE)
  • Used in GNN-QE, QTO
• Predicting easy answers before hard answers (ROC-AUC)
  • Used in NodePiece-QE
• Multiple variable queries, (multiply / marginal / joint) x (MRR/ HITs@k)
  • Proposed in EFOk-CQA arxiv 2023

Are Bio and Reddit available at all? Introduced in GQE, used in 4 papers overall (GQE, GQE+hashing, CGA, TractOR).

The main difference with Query2Box datasets: queries in the BetaE datasets have less than 100 answers. Has queries with negation.

Introduced in Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs, NeurIPS 2020

Introduced in Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings, ICLR 2020.

EPFO queries are considered easier than BetaE datasets. Doesn't have queries with negations.

GQE-like patterns mined on subsets of DBpedia and Wikidata. The datasets are DB18 and WikiGeo19, introduced in CGA, K-CAP 2019.

As of Sept 2022: not available.

Queries emulating property paths in SPARQL with variable length of relation paths (up to length 5). Queries are EPFO queries, i.e., no negation. New operators over relations resemble those from SPARQL:

• $r_1 / r_2 / \dots$ - relational path, aka classic projection queries
• $r_1 \lor r_2$ - a union of decomposed patterns $(e, r_1, ?) \lor (e, r_2, ?)$
• Kleene plus $r^{+}$ - one or more occurence of relation $r$, eg, $r_1/r_2^{+}$ corresponds to $r_1 / r_2$, $r_1 / r_2 / r_2$, $r_1 / r_2 / r_2 / r_2 / \dots$ up to some final depth. Those can be cyclic patterns.

Two datasets:

• FB15k-Regex is based on Freebase, queries have less than 50 answers, 21 query types
• Wiki100-Regex is based on query logs from the official Wikidata SPARQL endpoint, 5 query types.

Introduced in RotatE-Box, AKBC 2021.

Repo: GitHub - no actual data dumps are present :(

Conjunctive queries (w/o union) not limited to 9 patterns from Query2Box/BetaE datasets. The task is to predict all intermediate entities, not just final leaf nodes. Query depth: 2-5; max 3 intersecting branches.

Introduced in Answering complex queries in knowledge graphs with bidirectional sequence encoders, AAAI 2021.

New FB15K-237-CQ and WN18RR-CQ datasets have two variations:

• CQ (conjunctive queries) - Training on triples + paths + DAGs, Validation/Test on DAGs only;
• Paths - Training on triples + paths, Validation/Test on paths only

Sept 2022: the datasets are not publicly available.

Existential First-Order queries with Single Free Variable, extended from BetaE. The goal is to evaluate the combinatorial generalizability.

Introduced in Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs, NeurIPS 2021 (Datasets and Benchmarks)

Rethinking the EFO-1 formulation by introducing leaf nodes, multi edge, and cycle. For standard FB15k, FB15k-237, and NELL - 9 new query types (10 with reworked pni type) including:

• l - queries with existentially quantified variables as leaf nodes (2il, 3il)
• m - queries with multiple relation projection edges from one variable to another (2m, 2nm, 3mp, 3pm, im)
• c - queries with cycles (3c, cm)

All new query have 5000 instances in three KGs. Introduced in On Existential First Order Queries Inference on Knowledge Graphs, arxiv 2023. The dataset can be downloaded from here.

Based on a variation of the FB15k-237 dataset with entity attributes (12,390 entities, 237 relations, 115 attributes, 29,229 (?) triples). Literals are restricted to numerical values, three additional filter functions (less than, equal, greater then).

The dataset includes standard 9 EPFO query types and adds 8 more variations of those patterns enriched with literals:

• 5 query types where literals are in queries, but the answer is an entity (ai, 2ai, pai, aip, au)
• 3 query types where literals are in queries, and the answer is a mean of relevant literal values (1ap, 2ap, 3ap)

Introduced in LitCQD: Multi-Hop Reasoning in Incomplete Knowledge Graphs with Numeric Literals, arxiv 2023

Existential First-Order queries aimed at evaluating compositional generalization to OOD query patterns (29 in-distribution types, 29 out-of-distribution). In contrast to BetaE datasets, does not have restrictions on the number of answers per query, long tails are possible.

Introduced in Sequential Query Encoding For Complex Query Answering on Knowledge Graphs

Introduced by (EFOk-CQA) EFOk-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation with 741 query types in total.

Featured by:

• existential first-order queries with more than multiple variables.
• combinatorial space with multi-edge and cyclic queries

The Numerical CQA queries both include entities and typed numerical attribute values.

Introduced by Knowledge Graph Reasoning over Entities and Numerical Values

In addition to a normal graph of entities (instances) a-la BetaE datasets, the type-aware datasets offer an additional set of classes, classes hierarchy (from a pre-existing ontology), and instanceOf links between entities and classes.

Those datasets might include an additional task of predicting types of answer entities (Concept Retrieval).

• LUBM, introduced in Neuro-Symbolic Ontology-Mediated Query Answering, OpenReview 2021
• NELL, introduced in Neuro-Symbolic Ontology-Mediated Query Answering, OpenReview 2021. The base graph is the same as in the BetaE datasets, but a few ontological axioms were added.
• YAGO 4, introduced in TAR: Neural Logical Reasoning across TBox and ABox
• DBpedia, introduced in TAR: Neural Logical Reasoning across TBox and ABox

LUBM and NELL employ ontological axioms of the DL-Lite (R) family of Description Logics.

Introduced in SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs, KDD 2022.

Training queries are sampled on-the-fly during training due to the huge size of underlying graphs.

The underlying graphs are FB400k (400K nodes), WikiKG 2 (2.5M nodes) (from OGB), and full Freebase (86M nodes) TODO: confirm with Hongyu the number of validation / test queries.

The main difference of hyper-relational datasets is that edges are no longer plain triples $(h, r, t)$ but statements (in terms of Wikidata or RDF-Star) $\Big(h, r, t, (q_{ri}, q_{ei})_i\Big)$ with key-value (relation:entity) qualifiers $(q_{r}, q_{e})$ over the main triple. For example, in the statment (Albert Einstein, educated at, ETH Zurich, (degree, Bachelor)), the main triple is Albert Einstein, educated at, ETH Zurich and its unique qualifier is (degree, Bachelor). Qualifiers provide an additional context to the edge - the tail node might change with another qualifier, e.g., (Albert Einstein, educated at, University of Zurich, (degree, Doctorate)).

Entities and relations in qualifiers are still legit entities and relations which could be present in main triples. Some entities and relations can be found only in qualifiers.

The WD50K dataset has only conjunctive queries (projection + intersection), neither union nor negation.

Introduced in Query Embedding on Hyper-Relational Knowledge Graphs, ICLR 2022

The WD50K-NFOL dataset introduced in NQE: N-ary Query Embedding for Complex Query Answering over Hyper-relational Knowledge Graphsadds unions and negations, as well as possibility of variables at qualifier entity positions. **As of Nov 2022, not openly available)

As of March 2023, there are no existing purely inductive datasets such that the training and validation/test graphs are different (validation and test containing new unseen entities) and predictions should only rely on the graph structure w/o external data.

As a bridge between shallow transductive models and inductive inference, Type-aware Embeddings for Multi-Hop Reasoning over Knowledge Graphs propose to mine entity types as the invariant that remains the same at training and inference.

As a result, the following datasets assume an existing and known in advance class hierarchy (or a graph of classes). Technically, those can be put in the Type-Aware Datasets category. The query datasets only have EPFO queries (no negation).

Inductive splits have been published, see the GitHub issue

The dataset proposed in GNNQ frames query answering as node classification. The dataset has 9 tree-like conjunctive queries (6 synthetic from WatDiv and 3 from FB15k237), no unions nor negations. For each query, there are P KGs with an answer entity satisfying a query and N KGs with negative samplies where an answer does not satisfy a query. Test splits have graphs with new entities (but the same query shapes).

Introduced in TFLEX: Temporal Feature-Logic Embedding Framework for Complex Reasoning over Temporal Knowledge Graph, KDD 2022.

Based on FOL operators, the dataset focuses on temporal reasoning, which includes after, before and between on any timestamp set.

• Graph Query Sampler: Not a method, rather a dataset generator
• EFO-1-QA-benchmark: Generating combiantorial tree-formed query types and sampling the data.
• EFOk-CQA: Generating combinatorial existential first order query types with multiple (k) variables and sampling the data.

• KGReasoning: GQE, Query2Box, BetaE
• CQD: GQE, Query2Box, BetaE, CQD
• EFO-1-QA-benchmark: Query2Box, BetaE, LogicE, NewLook, ConE, FuzzQE
• Query2particles
• StarQE: StarQE
• SMORE: GQE, Query2Box, BetaE + Very Large Datasets
• GNN-QE: GNN-QE
• InductiveQE: Inductive QE with NodePiece and GNN-QE
• TAR: TAR
• QE-TeMP: TeMP (based on KGReasoning)
• GNNQ: GNNQ
• SE-KGE: GQE, CGA, and geospatial model
• LARK: LARK (uses Huggingface LLMs)
• WFRE: WFRE
• FIT: FIT
• SQE: SQE with Transformer/LSTM/GRU/TCN, Tree-LSTM, Tree-RNN, BetaE, BiQE, ConE, FuzzQE, GQE, HypE, NerualMLP (Mixer), Query2Box, Query2Particles
• NRN: NRN with GQE, Query2Box, Query2Particles
• EFOk-CQA: EFOk

If you find this work useful, please cite the original paper:

@article{ren2023ngdb,
    title={Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases},
    author={Hongyu Ren and Mikhail Galkin and Michael Cochez and Zhaocheng Zhu and Jure Leskovec},
    year={2023},
    eprint={2303.14617},
    archivePrefix={arXiv},
}