Neural Graph Reasoning: A Survey on Complex Logical Query Answering
Authors: Hongyu Ren
Mikhail Galkin
Zhaocheng Zhu
Jure Leskovec
Michael Cochez
Venue: Accepted by TMLR ()

Abstract: Complex logical query answering (CLQA) is a recently emerged task of graph machine learning that goes beyond simple one-hop link prediction and solves the far more complex task of multi-hop logical reasoning over massive, potentially incomplete graphs. 
The task received significant traction in the community; numerous works expanded the field along theoretical and practical axes to tackle different types of complex queries and graph modalities with efficient systems. 
In this paper, we provide a holistic survey of CLQA with a detailed taxonomy studying the field from multiple angles, including graph types (modality, reasoning domain, background semantics), modeling aspects (encoder, processor, decoder), supported queries (operators, patterns, projected variables), datasets, evaluation metrics, and applications.   
Finally, we point out promising directions, unsolved problems and applications of CLQA for future research.

Published in Transactions on Machine Learning Research (11/2024)
Neural Graph Reasoning: A Survey on Complex Logical
Query Answering
Hongyu Ren"
byrren Secs Cerren@cssstaafonne stanford. edu
Mikhail Galkin
mikhail gaabhaii..alkin@@nnee.ccoo
Zhaocheng Zhu
zhu wwwpebeeng..uuuuuomnenn. ca
Jure Leskovee!
hhre@ecsstanfone edu
Michael Cochez
m..coceeswu..l
Equal contribution
Stanford University 2 Intel AT Lab Mila Québec AT Insfitude and Université de Montréal 4 Vrije Universiteit Amsterdam and Elsevier discovery lab, Amsterdam, the Netherlonds
Reviewed on OpenReview: https: // openreview. net/ forum? id= dd=GGun92Zgg
Abstract
Complex logical query answering (CLQA) is recently emerged task of graph machine learn- ing that goes beyond simple one-hop link prediction and solves the far more complex task of multi-hop logical reasoning over massive, potentially incomplete graphs. The task received significant. traction in the community; numerous works expanded the field along theoretical and practical axes to tackle different types of complex queries and graph modalities with efficient systems. In this paper, we provide a holistic survey of CLQQA with a detailed tax- onomy studying the field from multiple angles, including graph types (modality, reasoning domain, background semantics), modeling aspects (encoder, processor, decoder), supported queries (operators, patterns, projected variables), datasets, evaluation metrics, and appli- cations. Finally, we point out promising directions, unsolved problems and applications of CLQA for future research.
Contents
1. Introduction
2
2 Preliminaries
4
2.1 Types of Graphs
4
2.2 Basic Graph Query Answering
5
2.3 Approximate Graph Query Answering
6
A Taxonomy of Query Reasoning Methods
7
Graphs
9
4.1 Modality
9

---

Published in Transactions on Machine Learning Research (11/2024)
4.2
Reasoning Domain
9
4.3
Background Semantics
11
5
Modeling
13
5.1
Encoder
14
5.2
Processor
17
5.3
Decoder
23
5.4
Computation Complexity
25
6
Queries
26
6.1
Query Operators
26
6.2
Query Patterns
32
6.3 Projected Variables
34
7 Datasets and Metrics
36
7.1
Evaluation Setup
36
................................
7.2
Query Types
36
7.3 Training
37
7.4 Inference
38
7.5 Metrics
40
8 Applications
41
9 Summary and Future Opportunities
42
A Definitions and Theoretical Foundations
56
A.1 Types of Knowledge Graphs
56
A.2 Basic Approximate Graph Query Answering..
57
A.3 Graph Query Answering
58
A.4 Triangular Norms and Conorms
61
A.5 Graph Representation Learning
62
B CLQA KGQA
62
1
Introduction
Graph databases (graph DBs) are key architectures to capture, organize and navigate structured relational information over real-world entities. Unlike (raditional relational DBs storing information in lables with a rigid schema, graph DBs store information in the form of heterogeneous graphs, where nodes represent entities and edges represent relationships between entities. In graph DBs, a relation (i.c. heterogencous connection between entities) is first-class citizen. With the graph structure and more flexible schema, graph DBs allow for efficient and expressive way handle higher-order relationships between distant
2

---

Published in Transactions on Machine Learning Research (11/2024)
At what universities do the Turing Award winners in the field of Deep Learning work?
3V: winnrurrrnnnggaaarr, V) A MfeeadnDeepLaarning, V) A university(V, U,)
UvA
UofT
Stanford
SPARQL query (edge traversal)
collab
b
SELECT ?uni WHERE
win
Turing Award
TuringAward DeepLearning ?person
win field
Pperson
field
Pperson ?uni
university
Hinton
university
Welling
Uoff
given edge
Knuth
Neural query execution link prediction)
predicted - "dage"
Bengio
LeCun
win
Deep Learning
university
field
Easy
Hard
NYU
Answer set
WafT
UdeM
NYU
Lpff
UdeM
NYU
UdeM
Figure 1: A complex logical query and its execution over an incomplete graph b Symbolic engines like SPARQL c perform edge traversal and retrieve an incomplete set of easy answers directly reachable in the graph, i.e., {UofT}. Neural query execution recovers missing ground truth edges (dashed) and returns an additional set of hard answers {UdeM, NYU} unattainable by symbolic methods.
entities, especially navigating through multi-hop hierarchies. While traditional DBs require expensive join operations to retrieve information, graph DBs can directly traverse the graph and navigale through links more efficiently. Due to its capabilities, graph databases serve as the backbone of many critical industrial applications including question answering virtual assistants (Flint, 2021; llyas et al., 2022), recommender systems in marketplaces (Dong, 2018; Hamad et al., 2018), social networking in mobile applications (Bronson et al., 2013), and fraud detection in financial industries (Tian et al., 2019; Pourhabibi et al., 2020).
One of the most important tasks of graph DBs is to perform complex query answering. The goal is to retrieve the answers of given imput query from the graph database. Given the query, graph DBs first translate and optimize the query into more efficient graph traversal pattern with a query planner, and then execute the pattern on the graph database to retrieve the answers from the graph storage using the query executor. The storage compresses the graphs into symbolic indexes suitable for fast. table lookups. Querying thus fast and efficient under the assumption of completeness, i.e., stored graphs have no missing edges.
However, most real-world graphs are notoriously incomplete, e.g., in Freebase, 93.8% of people have place of birth and 78.5% have no nationality (Minix et al., 2009), and about 68% of people do not have any profession (West et al., 2014), while in Wikidata, about 50% of artists have no date of birth (Zhang et al., 2022a), and only 0.4% of known buildings have information about height (Ho et al., 2022). In light of incompleteness, naively traversing the graph to find answers leads to a significant miss of relevant results, and the issue further exacerbates with an increasing query complexity. This inherently hinders the application of graph databases. Link prediction aims to predict missing information, but challenging task. Prior works predict links by learning latent representation of entities links (Bordes et al., 2013; Yang et al., 2015; Trouillon et al, 2016; Sun et al., 2019) mining rules (Galárraga et al., 2013; Xiong et al., 2017; Lin et al., 2018; Qu et al., 2021). While it is possible to use one-hop link predictors to materialize all predicted facts (above certain confidence threshold) and run deterministic query answering pipelines, the computational complexity of this operation quadratic in the number of entities and prohibitively expensive for any real-world graph. Furthermore, these approaches rank possible candidates for complction, meaning that they do not tell which of the completions could be traversed. Also reasoning can be used complete specific information, but there is always trade-off between possibly incomplete results and decidabílity with
3

---

Published in Transactions on Machine Learning Research (11/2024)
denser graph, some SPARQL entailment regimes (Hawke et al., 2013) do not guarantee that query exccution terminates in finite time.
On the other hand, recent advances in graph machine learning enabled expressive reasoning over large graphs in a latent space without facing decidability bottlenecks. The seminal work of Hamilton et al. (2018) on Graph Query Embedding (GQE) laid foundations of answering complex, database-like logical queries over incomplete KGs where inferring missing links during query execution is achieved via parameterization of entities, relations, and logical operators with learnable vector representations and neural networks. For the incomplete knowledge graph in (Fig. 1), given a complex query "At what universities do the Turing Award winners in the field of Deep Learning work?", traditional symbolic graph DBs (SPARQL. or Cypher- like) would return only one answer (UofT), reachable by edge traversal. In contrast, neural query embedding parameterizes the graph and the query with learnable vectors in the embedding space. Neural query execution is akin to traversing the graph and executing logical operators in the embedding space that infers missing links and enriches the answer set with two more relevant answers, UdeM and NYU, unattainable by symbolic DBs.
Since then, the area has seen surge of interest with numerous improvements of supported logical operators, query types, graph modalities, and modeling approaches. In our view, those improvements have been rather scattered, without an overall aim. There still lacks a unifying framework to organize the existing works and guide future research. To this end, we present one of the first holistic studies about the field. Conceptually, we devise the taxonomy of CLQA methods that includes various aspects of query answering and is supposed to be a bridge between data management and ML communities. The taxonomy (Section 3) classifies existing works along three main axes, i.e., (i) Graphs (Section
logical formalisms behind the underlying graph and its schema. (ii) Modeling (Section 5 - what are the neural approaches to answer queries) (iii) Queries (Section 6 what queries can be answered). We then discuss Datasets and Metrics (Section 7 how we measure the performance of query answering). Each of these dimensions is further divided into fin-grainee aspects. Finally, we discuss CLQA applications (Section 8) and summarize open challenges for future research (Section 9).
Related Work. While there exist. insightful surveys on general graph machine learning (Chami et al., 2022), simple link prediction in KGs (Ali et al., 2021; Chen et al., 2023), and logic-based link prediction (Zhang et al., 2022b; Delong et al., 2024), the complex query answering arca remained uncovered so far. With our work, we close this gap and provide holistic view on the state of alfairs in this emerging field. We also elaborate on the similarities and differences between CLQA and KG-based Question Answering (KGQA) (a different subfield of NLP) in Appendix B.
2 Preliminaries
Here, we discuss the foundational terms and preliminaries often seen in the database and graph learning literature. The rest of the preliminaries is deferred to the Appendix A elaborating on the mapping to structured languages like SPARQL, formalizing approximate graph query answering, logical operators, and fuzzy logic. The full hierarchy of definitions is presented in Fig. 3.
2.1 Types of Graphs
Here we introduce different types of graphs relevant for this research area. Our definitions are adaptations from those in (Hogan et al., 2021, ch. 2). We begin by defining set with all elements used in our graph
Definition 2.1 (Con) Con is an infenite set of constants.!
Definition 2.2 (Sttandard / Triple based) Knowledge Graph) We define a knowledge graph (KG) g = (E, R, R),, where E C Con represents set of nodes (entitics), R C Con is a set of relations (edge types), and S C (E x R x E) is set of edges (triples) 2. Each edge s E S on a KG G denotes statement (or fact) (c,, r, eo) in a triple format or or r(e,, Co) as a formula in first-order logic (FOL) form, where e,, eo E E denote
In case the constants da include representations for the real numbers, this set would be countably infinite. 2There might be overlap between E and R, i.e., some constants might he used as an edge and as nade.
4

---

Published in Transactions on Machine Learning Research (11/2024)
education_
education
education
education
education
Cambridge
Bachelor
Edinburgh
Hinton
Cambridge
Edinburgh
Hinton
Cambridge
degree
Hinton
Edinburgh
PhD
Bachelor
PhD
education_phd
Triple-based KG
Hyper- Rlyper-Relational KG (with relation-entity qualifiers)
Hypergraph KG
(with ad-hoc hyperedge types)
Figure 2: An example of KG modalities. Triple-only graphs have directed binary edges between nodes. Hyper-relational graphs allow key-value relation-entity attributes over edges. Hypergraphs consist. of hyper- edges composed multiple nodes.
the subject and object entities, and r E R denotes the relationship between the subject and the object. Often, the graph is restricled such that the set of nodes and edges must. be finile, will make this assumplion unless indicated otherwise.
For example, university (Hinton, UofT). Note all relations are binary KGs, i.e. each relation involves exactly two entities. This is also the choice made for the resource description framework (RDF) (Brickley et al., 2014) that defines a triple as a basic representation of a fact, yet RDF allows a broader definition of triples, where the object can be literals including numbers and timestamps (detailed in the following paragraphs).
statement
the KG in Fig. b is (Hinton, university, UofT)
We elaborate on hyper-relational KGs and hypergraph KGs in Appendix A.1.
2.2 Basic Graph Query Answering
We base our definition of basic graph queries on the one from (Hogan et al., 2021, section 2.2.1 basic graph patterns), but adapt it our graph formalization. Other definitions can be found in Appendix A.2.
Definition 2.3 (Term and Var) Given a knowledge graph G = (E, R, (or equivalent G (E, ( L)), we define the set of variables Var {v1, .2..... which take values from Con, but strictly disjoint from We call the union of the variables and the constants the terms: Term Con Var
With these concepts in place a Basic Graph Query is defined follows:
Baik Grajk Quey (Teliation
Popalee Patl Quer Detaatiss
Crkes (1-)
Chejaaatio Madistag
Definition 2.4 (Basic Graph Query) A ba- sic graph query 4-tuple Q = RE' R'.S'SS.. S (equivalently 5-tuple Q RE,, S L"), with literals), with E' Term set of node terms, R' C Term set of relation terms, and S' S C. E' R' E', two sets of edges (or equiv- alent to how graph edges are defined with literals).
Propetion (A.5
Ausosiia Dedaitic 2.5
Aneoning Ditteikee A.3
(E',
Detiation A.8
Bark Aupe estreato upi Qjecy Delictice
Appeasinato Googl Quayy Ausocias
Figure 3: Graph Query
hierarchy definitions from to Graph Query Answering and more general Approximate Graph Query Answering
The query looks like Iwo (small) graphs; one formed by the edges in S', and another by the edges in St
The former set includes edges that must be matched in the graph obtain answers to the query, while the latter contains edges that must not be matched (i.e., atomic negation).
5

---

Published in Transactions on Machine Learning Research (11/2024)
With Varq (E' U n Var (all variables in the query), the answer to the query is defined as follows.
Definition 2.5 (Basic Graph Query Answering) Given a knowledge graph 9 and a query Q as defined above, an answer to the query is ony mapping μ Varq + Con such that replacing each variable v; in the edges in S' with u(v;) results in un eage in S, and replacing each variable Vj in the edges in S with p(v)) results in an edge that is not in S. The set of all answers the query is the set of all such mappings.
For triple-based KGs, each edge (a, b) in the edge set S' (respectively S') of a query can be seen a relation projection R(a, b) (resp. -R(a, b)), f.e., as binary functions. Now, because the conjunction (d.e., all) of those relation projections (resp. the negation) have to be true, we also call these conjunctive querics with atomic negation (CQneg). The SPARQL query language defines basic graph patterns (BGPs). These closely resemble our basic graph query for RDF graphs, but with 5' 0, i.e. they do not support atomic negation but only conjunctive queries (CQ). We could analogously create CQ and CQneg classes for the other KG types.
In Fig. C we provide an example of a Basic Graph Query expressed in the form of a SPARQL query. This corresponds to our formalism:
((TuringAward, Pperson, DewpLearnin.. Pund), { universily).
Node Terms E¹)
(# Relation Terms R')
(TuringAward, win, &person), (DeepLearning, field, Sperson), ( (Pperson, university, }uni)): 0)
(S')
(S))
A possible answer to this query is the following partial mapping: f4 = {(pperson, Hinton), (Puni, UofT) This is also the only answer, so the set of all answers is {rr}
If we want to exclude people who have worked together with Welling, then we modify the query as follows:
2 = ((TuringAward, Pperson, DeepLearning, Puni],
{ wii, field, university): (TurringAward, win, Sperson), (DeepLearning, field, Sperson), ( (9person, university, luni)}; } {(pperson, collab, Welling)})
The key difference here is that we add (?person, collab, Welling)] to S resulting in the empty answer set.
2.3 Approximate Graph Query Answering
Definition 2.6 (Approximate Graph Query Answering) Given a knowledge graph G, subgraph of a complete, but not observable knowledge graph 9, a query formalism, any graph query Q according to that formalism, and the scoring domain R.
An approzimate graph query answer to the query Q is function f which maps every possible mapping (p: Varq + Con) to R.
Note there that the variables are not always mapped to nodes which occur in the graph. It is well possible that the query contains an aggregation function which results in a literal value.
In the neural logical query answering literature (starting from Hamilton et al. (2018); Ren et al. (2020)), we can find the concepts of easy and hard answers. This refers to whether the answers can be found by only having access to G or not.
Definition 2.7 (Easy and Hard answers) Given a knowledge graph G, subgraph of a larger unobservable graph G, and a query Q. Easy and hard answers are defined in terms of exact query answering (Defini- tion A.5). The set of easy answers is the intersection of the answers obtained from G, and those from g. The set of hard onswers is the set difference between the answers from & and those from G.

---

Published in Transactions on Machine Learning Research (11/2024)
Note the asymmetry in the definitions. Easy answers are those that can be found in both g and g. Hard answers are those that can be found only in 9 but not in g. For example, the query in Fig. has one ensy answer UofT as it is reachable by traversing the original graph & and two hard answers UdeM, NYU since they require predicting missing links (missing in G but true links in the non-observable full graph 9). For Basic Graph Queries (Definition 2.4), all easy answers can also be found from G. However, for some more complex query types (e.g., these which allow negation) there could be answers found in 9 which are not found 9. We call these answers false positives in the context of answering over G.
3 A Taxonomy of Query Reasoning Methods
In the following sections, we devise taxonomy of query answering works. We categorize existing and envisioned approaches along three main directions: (i) Graphs what is the underlying structure against which we answer queries; (ii) Modeling how answer queries and which inductive biases are employed; (iii) Queries what we answer, what are the query structures and what are the expected answers. The taxonomy is presented in Fig. 4. In the following sections, we describe each direction in detail and illustrate them with examples covering the currently existing CLQA literature (more than 50 papers).

---

Published in Transactions on Machine Learning Research (11/2024)
Triple KGs
Repetonelationa KGs
Modality Section 4.1
Hypergraphs
Multi-modal KGs
Discrete
Graphs Section 4
Reasoning Domain Section 4.2
Discrete + Time
Discrete + Continuous
Facts-only (ABOX)
Background Semantics Section 4.3
Class Hierarchies
Complex Axioms (TBOX)
Shallow Embedding
Encoder Section 5.1
Transductive Encoder
Inductive Encoder
Modeling Section 5
Neural
Geometric
Processor Section 5.2
Neuro-Symbolic
Probabilistic
CLQA
Non-parametric
Fuzzy Logic
Decoder Section 5.3
Parametric
Conjunctive (3
EPFO (3
EPFO + Negation (3VV -)
Query Operators Section 6.1
Regex and Property Paths (3 A + * ?!!)
Filter
Aggregations
OPTIONAL, Solution Modifiers
Queries Section 6
Path
Tree
Query Patterns Section
Arbitrary DAGs
Cyelic patterns
Zero Variables
Projected Variables Section 6.3
One Variable
Multiple Variables
Figure 4: The Neural Query Engine Taxonomy consists of three main branches Graphs, Modeling, and Queries. We describe each branch in more detail including prominent examples in the relevant sections.

---

Published in Transactions on Machine Learning Research (11/2024)
4 Graphs
The Graphs category covers the underlying graph structure (g in Definition A.4) against which complex queries sent and the answers produced. Understanding the graph, its contents and modeling paradigms is crucial for designing query answering models. To this end, we propose to analyze the un- derlying graph from three aspects: Modality, Reasoning Domain, and Background Semantics.
4.1 Modality
We highlight four modalities common for KGs and graph databases: standard triple-based KGs, hyper- relational KGs, and hypergraph KGs. The difference among the three modalities is illustrated in Fig. 2. Additionally, we outline multi-modal KGs that contain not just a graph of nodes and edges, but also text, images, audio, video, and other data formats linked to the underlying graph explicitly implicitly.
We categorize the literature along the Modality aspect in Table 1. To date, most query answering approaches operate solely on triple- graphs Among approaches supporting heper-relational graphs, we are only aware of StarQE (Alivanistos et al., 2022) that incorporates rutity-relaion qualifiers over labeled edges and its extension NQE (Luo et al., 2023). We posit that the repet-relationa model might serve as a theoretical foundation of temporal query answering approaches since temporal attributes are in fact continuous key-value edge altribules. To date, we are not aware of complex query answering models supporting hypergraphs or multi-modal graphs. We foresee them as possible area of future research in the area.
Table 1: Complex Query Answering approaches categorized under Modality.
Triple-only
Hyper-Relation
Hypergraph
Multi-modal
GQE (Hamillon et sl., 2018), GQE w bash (Wing et al, 2019), CGA (Mai al,, 2019), TractOR. (Priedman & den Broock, 2020), Query2Box (Ron al, 2020), BetaE (Ren Leskovec, 2020), EmQL (Sun al, 2020), MPQE [Daza Cochez, 20220, Shy (Gebhart al., 2024), Q2B Outo (Andresel et al. 2021), RotatEBBox (Adiikiis sl., 2021), BiQE (Kosnis et al., 2021), IlyPE (Choudiaary et al, 2021b), NewLook (Liu ah,, 2021), CQD (Arakelyan et al, 2021), PERM (Chouiibarry
StarQE (Alivanistos et al, 2022),
None
None
NQE (Lao al., 2023)
2021a), ConE (Zhang al., 20211), LogicE [Lams et 2021), MLPMMxx (Amayyolas ol., 2022), FuzIQE (Clon et al., 2022), GNN-QE (Zhu es ol., 2022), GNNQ (PBuuger al., 2022), SMORE (Ren al. 2022), KGTTaan (Liu 2022), LinE (Huang et al., 2022b), Query2Partices (Bai al., 2022), TAR (Tang al., 2022), TeMP (Hu al., 2022), FLEX (Lin al, 2022), TFLEX (Lin et st, 2023), NodePiece-QE (Galkin al., 20226), ENeSy (Xu et ol., 2022), Gammaa (Yang et nl, 20222), NMP-QEM (Long et al., 2022), QTO (Bai et al., 2023e), SignalE (Wang et al., 2022), LMPNN (Wang et nl., 20236), Var2Vec (Wang et al., 20236), CQDA (Arakalyan et al., 2023), Query2Geom (Sardina es al. 2023), SQE (Bai et al., 2023b), RoConE (El et al. 2023), FIT (Vin es al, 2023b), LicCQD (Demir et al., 2023), CylE (Mguyen et al., 2025b). LARK (Cheodlacy & Reddyy 2023), WFRE (Wang et al, 2023d), BiDAG (Xu et al., 2023s), NRN (Bai et al., 2023s), Query2Itiple (Xu et al., 2023h), SCoNe (Ngayen et al., 2023s), CQD Onto (Andresol et al., 2023); UnRavl. (Cucumides et al., 2024), UltraQuery (Galkin et, al., 2024)
4.2 Reasoning Domain
Following Definition 2.5, a query Q includes constants Con, variables Var, and returns answers as mappings μ: : Varq - Con. By Reasoning Domain we understand the space of possible constants that query answering models reason about. We highlight three common domains (Discrete, Discrete + Time, Díscrete + Continuous), illustrate them in Fig. 5, and categorize existing works in Table 2. Each subsequent domain is a superset of the previous domains, e.g., Discrete + Continuous includes the capabilities of Discrete and Discrele + Time and expands the space to continuous inputs and outputs.
In the Discrete domain, constants, variables, and answers can be entities E and (or) relation types R of the KG, Con C & R, Var S EUR,, p S R. That is, queries may only contain entities (or relations) and their answers are only entities (or relations). For example, a query ?r education(Hinton,, a:) in Fig. 5 can
9

---

Published in Transactions on Machine Learning Research (11/2024)
Edinbbrgh
Hinton
Cambridge
Edinburgh
Hinton
Cambridge
Edinburgh
Hinton
Cambridge
education
education
education
education
education
education
start: 1972
start 1967
astablished: 1983 students: 35,375
established:
1209
1970
students::
24,450
education
education
education
?x
?X
?x
1973
studentss 30,000
?x: education x)
Px: education (year 1973) (Hinton, x)
?x: education (Hinton, x) x. stsuennss 30,000
Discrete (entities + relations only)
Discrete Time (reasoning over timestamps)
Discrete Continuous (including literals, e.g. numbers)
Figure 5: Reasoning Domains. The Discrete domain only allows entitics and relations as constants, variables, and answers. The Discrete + Time domain extends the space to discrete timestamps and time-specific operators. The Discrete + Continuous domain allows continuous inputs (literals) and outputs.
only return two entities (Edinburgh, Cambridge} as answers. Conceptually, the framework allows relation types r E be variables as well. For example, a SPARQL graph pattern (Hinton ?r Cambridge} or Pr: (Hinton,,,, Cambridge) in the functional form that returns all relation types between two nodes Hinton and Cambridge. However, to the best of our knowledge, all current approximate query answering literature and datasets limit the queries such that they do never have variables in the relation position, í.e., R' C Con. (we discuss queries structure in more detail in Section 6). To date, most of the literature in the field belongs to the Discrele reasoning domain (Table 2).
Some nodes and edges might have limestamps from a set of discrete timestamps t TS indicating a validity period of certain statement. In a more general case, certain subgraphs might be timestamped. We define the Discrete Time domain when queries include temporal data. In this domain, the set of constants is extended with the set of timestamps, i.c., TS Con, and relation projections may be instantiated with certain limestamp (a, With such graph, one can exlend set of queries and the set of possible answers to include time information. An example of such work is this is the Temporal Feature-Logie Embedding Framework (TFLEX) by Lin et al. (2023) that defines additional operators before, after, between over edges with discrete timestamps.
For instance (Fig. 5), given timestamped graph and query ?z e (Hinton, æ), the answer set includes only Edinburgh the timestamp 1973 falls into the validity period of only one edge.
Finally, the most expressive domain is Discrete + Continuous that enables reasoning over continuous inputs (such as numbers, texts, continuous timestamps) often available as node and edge attributes or literals. Formally, for numerical data, the space of constants is extended with real numbers R C Con. Also the query formalism is extended to allow reasoning over the real numbers. An example query in Fig. 5 ?x education Adtucation(Hinton,,.. .r) A x. r.students < 30000 includes conjunctive term r.students < 30000 that requires numerical reasoning over the students attribute of variable to produce the answer Cambridge. In similar fashion, extending the answer set to continuous outputs can be framed To date, LitCQD (Demir et al., 2023) and NRN (Bai et al., 2023a) are the only approaches supporting numerical literals (in R) as query constants and potential query answers. NRN, however, treats litorals as discrete entities in the graph. LitCQD employs TransEA (Wu & Wang, 2018) (n addition to the ComplEx- based (Lacroix et al., 2018) link predictor) as a regressor to predict numerical values of entities' attributes. Incorporating litcrals into queries, LitCQD defines filtering operators less than, greater than, equal implemented as exponential functions of predicted and target values. For example, the term z.students < 30000 is represented as conjuction students(2, C) 30000) of relation projection and the less-than
regression task.
10

---

Published in Transactions on Machine Learning Research (11/2024)
filter. The ability to reason over continuous data is crucial for query answering given that most real-world
KGs heavily rely on literals.
Table 2: Complex Query Answering approaches categorized under Reasoning Domain.
Discrete
Discrete
Time
Discrote Continuous
GQE (Hamilton al., 2018), GQE hash (Wang al., 2019), CGA (Mai 2010), TractOR (Friedman Van Brosck, 2020), Query2Box (Hen al.
TFLEX (Lin al., 2023)
LiCCQ (Demir al., 2023), NRN (Bai al,, 2023s)
20200, BetaE (Ren Leskovee, 2020), EnQL (Sun et al., 2020), MPQE (Duss & Cochee, 2020), Shy (Gebhart es sl,, 2023), Q2B Onto (Andreel es sl,, 2021), RotatE-Box (Adlakha et al., 2021), BiQE (Kotnis et al., 2021), HyPE (Choud- al,, 2021b), NewLook (Lin PERM (Choudlarr sl,, 2021s), ConE (Zhang al,, 2021b), LogicE (Luus al., 2021), MLPMix (Amayuelas et al., 2022), FuzzQE (Chea et al., 2022), GNN-QE (Zhu et al., 2022), GNNQ (Pfuuggr es al., 2022), SMORE (Rem et al., 2022), KGTrans (I.i et al., 2022), LinE (Hunng ot al,, 20225), Query2Particles (Bai al., 2022), TAR (Tang et sl, 2022), TeMP (Hu al., 2022), FLEX (Lin al., 2022), NodePiece-QEE (Galkin
2021), CQD (Arakelyan al,, 2021),
2022b), ENeSy (Xa al., 2022), GammaE (Yang et al., 20222), NMP-QEM (Toog al., 2022), StarQE (Ali- vanistos es al, 2022), QTO (Bai et al., 20236), SignalE (Wang et ol., 2022), LMPNN (Wang et al., 2023e), NQE (Luo et al., 2023), Var2Vee (Wang et al, 2028), Query2Geom (Sardina al, 2023),
2023e), CQDA (Arakelyan SQE (Bai sl., 2023b)), RoConE (He 2023), FIT (Yin 20236), CylE (Nguyen sl., 2023b), LARK (Choudlary & Reddy, 2023), WFRE (Wang et al., 2023d), BiDAG (Xu el al., 2023a), Query2Triple (Xu et al, 2023b), SCoNe (Nguyen et ol., 2023a), CQD Onto (Andresel et al,, 2023), UnRavL (Cucumides 2024), UltraQuery (Galkin 2024)
4.3 Background Semantics
Professor E =1 hasStudent
Vwokks. University
TBox
subClassOf
subClassof
type
type
ABox
Facts-only (ABOX)
+ Class Hierarchy
Complex Axioms (TBOX)
Figure 6: Background Semantics. Facts-only graphs that only have assertions (ABox) and have higher-level schema. Class Hierarchy introduces node types (classes) and hierarchical relationships between classes. Finally, Complez Axioms add even more complex logical rules (TBox), for example, governed by certain OWL profiles, e.g., A professor is someone who has one or more sludents and works al universily.
Relational databases often contain a schema, that is, a specification of how tables and columns are organized that gives a high-level overview of the database content. In graphs databascs, schemas exist as well and, for instance, node types are common in the Labeled Property Graph (LPG) paradigm. RDF graphs employ the standards based Description Logics (Baader al., 2003). As incorporating schema is crucial for
11

---

Published in Transactions on Machine Learning Research (11/2024)
designing effective query answering ML models, we introduce Background Semantics (Fig. 6) as the notion of additional schema information available on top of plain facts (statements).
Facts-only. In the simplest case, there is no background schema such that KG consists of statements (facts) only, that is, a KG follows Definition 2.2, g = R.). In terms of description logics, the graph only has assertions (ABox). Queries, depending on the Reasoning Domain (Section 4.2), involve only entities, relations, and literals. The original GQE (Hamilton et al., 2018) focused on facts-only graphs and the majority of subsequent query answering approaches (Table 3) operate exclusively on schema-less KGs.
Class Hierarchy. Classes of entities, or node types, are a natural addition to a facts-only graph as a basic schema. Using Definition 2.2 with a set of types T, a graph g defined as g = (E, R), where E & T (with EnT- - 0). In other words, the types can be used as normal entities. To indicate that an entity has a type, a specially labeled edge can be used (e.g,, rdf: type), or labeling function can be defined; both options have equivalent expressive power, Because types are nodes themselves, it is possible to specify hicrarchical relationships between classes using RDF Schema (RDFS) (Brickley et al., 2014)². In LPG, it is more common to only have a labeling function, and not allow lype hierarchies. Practically, edges involving types might be present physically in a KG or be considered as an additional input to a particular model.
To date, we are aware of three query answering approaches (Table 3) that incorporate entity types. Con- textual Graph Atlention (CGA, Mai et al. (2019)) only uses lypes for entity embedding initialization and requires each entity to have only one type. A similar technique was used in the evaluation of MPQE, but only to initialize the representation of variables (for which types were assuned given). The queries are not conditioned by entity types and the answer set still includes entities only. That is, constants in queries and those bound to variables are never types.
In Awae- Message Passing (TEMP, Hu et al. (2022)), type embeddings are used to enrich entity and relation representations that are later sent to a downstream query answering model. Each node might have several types. In the inductive scenario (we elaborate on inference scenarios in Section 5.1) with unseen nodes at inference time, type and relation embeddings are learned invariants that transfer across training and inference entilies. Queries, and bound variables are still limited lo non-lypes only (im(μ) S E).
The TBox and ABox Neural Reasoner (TAR, Tang et al. (2022)) incorporates types and their hierarchy to improve predictions over entities. They also introduce the task of predicting types of answer entities, that is, p(l) S (E UT) for one specific variable called Other variables cannot bind to types and constants in the query cannot be types either. The class hierarchy in TAR is used in three auxiliary losses besides the original entity prediction, that is, concept retrieval prediction of the answer set of types, subsumption predicting which type is subclass of another type, and instantiation predicting type for each entity.
A natural next step for the Class Hierarchy family of approaches is to incorporate types in queries in the form of constants and variables.
Complex Axioms. Finally, a schema might contain not just a class hierarchy but a set of more complex axioms involving, for example, a hierarchy of relations, restrictions on relations, or composite classes. Such a complex schema can now be treated as an ontology O and we extend the definition of the graph to include it: g= (E, In Fig. 6, the axiom Professor C 2 hasStudent Vworks Vwwrkss.niverssts. University describes that A professor is someone who has one or more sludents and works at universily. In terms of description logics, graph has an additional terminology component (TBox). The expressiveness of the TBox directly affects the complexity of symbolic reasoning engines up to exponential (EXP'TIME) for most expressive fragments.
In graph representation learning, incorporating complex ontological axioms is non-trivial even for simple link prediction models (Zhang et al., 2022b). In the query answering literature, the only attempt to include complex axioms is taken by Andresel et al. (2021). In Q2B Onto (O2B), an extension of Query2Box (Q2B, Ren et al. (2020)), the set of considered complex axioms belongs to the DL-LiteR fragment and supports the hierarchy of classes (subelasses), the hierarchy of relations (subpropertães), well as range and domain of relations. The model architecture is not directly conditioned on the axioms and remains the original
3RDFS has more expressive means (e.g., a hierarchy of relations) but we leave them Compler A Arioms
12

---

Published in Transactions on Machine Learning Research (11/2024)
Query2Box. Instead, the axioms affect the graph structure, query sampling, and an auxiliary loss, that is, query rewriling mechanisms are used to materialize more answers to original queries as if executed against the complete graph (deductive closure) akin to data augmentation. During optimization, an auxiliary regularization loss aims at including a specialized query box into the more general version of this query q'-
Still, even the expensive procedure of incorporating complex axioms in query sampling O2B benefits mostly the deductive capabilities of query answering, that is, inferring answers that are already implied by the graph G and ontology O and does not improve the generolization capabilities when missing edges cannot be inferred by ontological axioms. We elaborate on deductive, generulization, and other setups in Section 7.
Another avenue for future work is a better understanding of theoretical expressiveness of Graph Neural Net- work (GNN) encoders when applied to multi-relational KGs. Initial works on non-relational graphs (Barceló et al., 2020) map the expressiveness to the FOC₂ subset of FOL with two variables and counting quantifiers, and to FOCB (Luo et al., 2022) for hypergraphs of maximum arity B. In relational graphs, Barceló et al. (2022) quantified the expressiveness of relational GNNs in terms of the relational Weisfeiler-Leman (RWL) test proving that RWL is more expressive than classical WL test (Weisfeiler & Leman, 1968) and that com- mon relational GNN architectures like R-GCN (Schlichtkrull et al., 2018) and CompGCN (Vashishth et al., 2020) are bounded by 1-RWL. Using RWL, Huang et al. (2023) derive that the family of GNNs conditioned on the query node, such as Neural Bellman-Ford Networks (Zhu et al., 2021), are bounded by the asymmetric local 2-RWL and expressive as rGFO eut, restricted guarded first-order logic fragment with three variables and counting. Concurrently, Gao et al. (2023) study KGs as double permutation equivariant structures (to permutiin nodes and edge types) and map their expressiveness to universally quantified entity-relation (UQER) Horn clauses. However, it is still an open question if there exists GNNs architectures that can capture OWL-like axioms and leverage them as inductive bias in complex query answering.
Table 3: Complex Query Answering approaches categorized under Background Semanlics.
Facts-only (ABOX)
Class Ilierarchy
Complex Axions (TBOX)
GQE (Hamilton et al., 2018), GQE hash (Wang al., 2019), TractOR (Friedman Van den Broeck, 2020), Query2Box (Ren al., 2020), BetaE (Ren & Leshovee, 2020), EmQL (Sun et al., 2020), Shv (Gebhart et al,, 2023), RotatE-Box (Adlakha et al., 2021), MPQE (Duza & Cochez, 2020), BiQE (Kotnis al., 2021), HyPE (Choudhary et al., 2021b), Newl.ook (Liu et al., 2021), CQD (Arakelyan et sl., 2021), PERM (Choudbary et al., 2021s), ConE (Zhang et al., 2021b), LogicE (Luus et al., 2021), MLP- Mix (Amayuelas al., 2022), FuzuQE (Chen al., 2022), GNN-QE (Zhu al, 2022), GNNQ (PBuueger et al., 2022), SMORE (Ren al. 2022),, KGTrans (Tán et al., 2022), LinE (Huang et al., 20225), Query2Particles (Bai en al,, 2022), FLEX (Tán et al., 2022), TFLEX (Tán et al., 2028), NodePiece-QU: (Galkin al., 2022b), ENeSy (Xu al., 2022), Gam- maE (Yang et al. 20224), "MP-QEM (Loug et al., 2012)), StarQE (Ali- vanistos et al., 2022), QTO (Hai et al., 20123)), SignalE (Wang et al, 2022), LMPNN (Wang et al., 20225)), NQE (Luo et al., 2023), Var2Vee (Wang at, 2023s), CQD4 (Arakelyan et al., 2029), Query2Geom (Sardina et al,, 2023), SQE (Bal et al., 2023b), RoConE (He et al., 2023), FIT (Yin et al., 2023b), LitCQD (Domir et ol., 2023), CylE (Nguyen et al,, 2023b), LARK (Choudhary Reddy, 2023), WFRE (Wang al., 2023d), BiDAG (Xu et al., 2023s), NRN (Bai al., 20238), Query2Triple (Nu et al., 2023b), SCoNe (Nguyen et al, 2023s), UnRavL (Cucumides et al, 2024), UltraQuery (Galkin et al. 2024)
CGA (Mai et al,,
Q2B Onto (Andresel et al., 2021),
2019), TeMP (Hu
CQD Outo (Andresel et al., 2023)
et al., 2022), TAR (Tang et al,, 2022)
5 Modeling
In this section, we discuss the literature from the perspective of Modeling. Following the common methodol- ogy (Battaglia et al., 2018), we segment the Modeling methods through the lens of Encoder-Processon Processor-reeeeeeeeeeee Decoder modules (illustrated in Fig. 7). (1) The Encoder ENc() takes an input query q, target graph g with its en- tities and relations, and auxiliary inputs (e.g., node, edge, graph features) to build their representations in
13

---

Published in Transactions on Machine Learning Research (11/2024)
P
Query
f
g
Discrete Outputs
Graph
Encoder() ()
Processor
Decoder
Continuous Outputs
Additional inputs
Neural Query Executor
Figure 7: Newral Query Execution through the SroondeePrroeesor--Deeee Decoder modules. Encoder function f builds representations of inputs (query, target graph, auxiliary data) in the latent space. Processor executes the query with its logical operators against the graph conditioned on other inputs. Decoder function builds requested outputs that might be discrete or continuous.
the latent space. (2) The Processor P leverages the chosen inductive biases to process representations of the query with its logical operators in the latent or symbolic space. (3) The Decoder DEC() takes the processed latents and builds desired outputs such as a distribution over discrete entities or regression predictions case of continuous lasks. Generally, encoder, processor, and decoder can be parameterized with a neural network 0 or be non-parametric. Finally, we analyze computational complexity of existing processors.
5.1 Encoder
We start the modeling section with encoders, i.e., how different methods encode and represent entities and relations from the KG. There three different categories, Shallow Embedding, Transductive Encoder, and Inductive Encoder each representing different way of producing the neural representation of the enti- ties relateelaionn.... Different encoding methods are suitable in different inference setups (details in Section 7.4), and may further require different logical operator methods (details in Section 5.2). Fig. 8 illustrates the three common encoding approaches.
E
lookup
a
Query
Processor(g, E, R.
Decoder(q, E', R,, S....)
Shallow Embedding
relation
R
lookup
entity
E
lookup
b
Query
Encoderly, E, R. G.....)
Procesorty B.. RR G.....
Decoder E', R', R. .....
Transductive Encoder
reletion lookup
R
c
Query
lookup
R
Encoder G....)
Processor(g G....)
Decoder(g, (g. G....)
Inductive Encoder
set is
optionally
E
entiyy embeddings
roconstruct;
Figure 8: Categorization of Encoders.
a Shallow encoders perform entity and relation embedding lookup Transductive encoders additionally enrich the representations with
and send them to the processor. query, graph, classes, or other latents. Inductive encoders do not need learnable entity embeddings.
Shallow Embeddings. The first line of approaches encodes each entity/relatian on the graph as a low- dimensional vector, and thus we achieve an entity embodding matrix E and relation embedding matrix R. The shape of the entity embedding matrix is [g] x d (|R d), where d the dimension of the embedding, Shallow embedding methods assume independence of the representation of all the nodes the graph.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Table 4: Complex Query Answering approaches categorized under Encoder.
Shallow Embedding
Transductive Encoder
Inductive Encoder
GQE (Hamiiton al., 2018), GQE hash (Wang et al., 2019), CGA (Mai al., 2019), TractOR (Friedman & Van den Broeck, 2020); Query2Box (Ren et al., 2020), BetaE (Ren & Leekover, 2020), EmQL (Sun et al., 2020), Shy (Gebbart et al., 2023), Q2B Onto (Andresel et sl, 2021), RotatE-Box (Adlakha sl., 2021), HyPE (Choudhary et al,, 2021b), NewLook (Liu et al., 2021), CQD (Arakelyan et al., 2021), PERM (Chondhary et al,, 2021n), ConE (Zhang et al., 2021b), LogieE (Luus et al. 2021), FuzzQE (Chen et al., 2022), SMORE (Ren et nl., 2022), LinE (Muang et al., 2022b), Query2Particles (Bai al., 2022), TAR (Tang et al., 2022), FLEX (Lin et al, 2022), TFLEX (Lin et al., 2023), Gam- maE (Yang et sl., 2022s), NMP-QEM (Long et al., 2022), QTO (Bai al. 2023c), SignalE (Wang es al,, 2022), Var2Vee (Wang al., 2023a), CQD4 (Arakelyan et al., 2023), Query2Geom (Sardina et al., 2023), Ro- ConE (Il et. nl., 2023), FIT (Yin et al., 2023b), LitCQD (Demir et al., 2023), CylE (Nguyen al., 2023b), WFRE (Wang et al., 2023d), NRN (Bai nl., 2023a), SCoNe (Nguyen es al., 2023a), CQD Onto (Andresel
MPQE (Doza & Coches, 2020), BiQE (Kotnis al., 2021), KGTrans (Liu et al,, 2022), StarQE (Alivanistos al, 2022), MLPMix (Amayuelus et al., 2022), ENeSy (Xu es al,, 2022), LMPNN (Wang et al. 2023c), NQE (Lao et al,
NodePiece-QU QE
(Galkin
et al,, 2022b), GNN-QE (Zhu es al, 2022), GNNQ
(Pflueger et al., 20223, TeMP (Hu al, 2022), UnRavL
(Cucumides et al. 2020), UltraQuery (Galkin et al, 2024)
2023), SQE (Bai et al,
2023b), BIDAG (Xu es al.,
2023*), Query2Triple (Xu et al., 2023b),
et al., 2028)
This independence assumption gives the model much freedom, free parameters to learn. Such modeling origins from the KG completion literature, where the idea is to learn the entity and relation embedding matrices by optimizing a pre-defined distance/score function over all edges on the graph, e.g., a triplet fact dist(e,, r, eo). The majority of query answering literature follows the same paradigm with various different embedding spaces and distance functions to learn the entity and relation embedding matricos. Multiple embedding spaces have been proposed. For example, GQE (Hamilton et al., 2018) and Query2Box (Ren et al., 2020) embed into Rd (point vector in the Fuclidean space); FuznQF/ (Chen et al., 2022) embeds into the space of real numbers in range [0, 1] (fuzzy logic score); BetaL' (Ren & Leskovec, 2020) uses Beta distribution, probabilistic embedding space; ConE Zhang et al. (2021b) the other hand embeds entities as point on a unit circle. Each design choice motivates the inductive bias for executing logical operators (as we show in Section 5.2). Some approaches employ shallow entity and relation embeddings alrcady pro-trained on a simple link prediction task and just apply on top of them a query answering decoder with non-parametric logical operators. For example, CQD (Arakelyan et al., 2021), LMPNN (Wang et al., 2023e), Var2Vec (Wang et al., 2023a), and CQDA (Arakelyan et al., 2023) take pre-trained embeddings in the complex space Cd and apply non-parametric t-norms and t-conormss to model intersection and union, respectively. QTO (Bai et al., 2023c) goes even further and fully materializes scores of all possible triples in one [0. 1] R x1 matrix given pre-trained entity and relation embeddings at preprocessing stage.
Despite being the mainstream design choice, the downside of shallow methods is that (1) shallow embeddings do not use any inductive bias and prior knowledge of the entity or its neighboring structure since the parameters of all entities/relatiie in the inductive inference setting since these mothods do not have a representation/ heneriiin//mbddiiigg for those unseen novel entities by design. One possible solution to randomly initialize one embedding vector for a novel entity and finetune the embedding vector by sampling queries involving the novel entity (detailed in Section 7.3). However, such a solution requires gradient steps during inference, rendering it not ideal.
are free parameters learned from scratch; (2) they are not applicable
Transductive Encoder. Similar to shallow embedding methods, transductive encoder methods learn the same entity embedding matrix E. Besides, they learn additional encoder ENCp(g, E, R....) (parameter- ized with 0) on top of the query q, entity and relation embedding matrices (and, optionally, other available inputs). The goal is to apply the encoder to the embeddings of entities in the query q in order to capture dependencies between neighboring entities in the graph. Specifically, the additional encoder may take several rows of the feature matrix as input and further apply transformations. For example, BiQE (Kotnis et al., 2021) and kgTrranffommer (Liu et al., 2022) lincarize a query graph G, into a sequence and apply a Trans- former (Vaswani et al., 2017) encoder that attends to all other embeddings in the query and obtain the final representation of the [MASK] token as the target query. MPQE (Daza & Cochez, 2020) and StarQE (Ali-
15

---

Published in Transactions on Machine Learning Research (11/2024)
vanistos et al., 2022) run message passing GNN architecture top of the query graph Gg to enrich entity and relation embeddings and extract the final node representation as the query embedding. These met share similar benefit and disadvantage of the shallow embeddings. Namely, there are many free parameters in the method to train. Unlike the shallow emboddings, the additional encoder leverages relational inductive bias between an entity and its neighboring entities or other entities a query, allowing for a better learned entity representation and generalization capacity. However, since at its core the method is still based on the large look-up matrix of entity embeddings, it still exhibits the same downside that all such methods cannot be directly applied to an inductive setting where we may observe new entities.
Inductive Encoder. In order to address the aforementioned challenges of shallow embeddings and trans- ductive encoders, inductive encoder methods aim to avoid learning an embedding matrix E for a fixed number of entities. Instead, inductive representations are often calculated by leveraging certain invariances, that is, the features that remain the same when transferred onto different graphs with new entities at infer- ence time. As we describe in Section 7.4, inductive encoders might employ different invariances albeit the majority of inductive encoders rely on the assumption of the fixed set of relation types R. Formally, follow- ing Definition 2.4, given a complex query Q= (E', "', composed of entity and relation terms E', R' (that, in turn, contain constants Con and variables Var), relation projections R(a, b) E S (and, optionally, in S"), a target graph 9 (and, optionally, other inputs), inductive encoders learn conditional representation function ExCo(elE', RR, for each entity e E E. Galkin et al. (2022b) devise two families of inductive representations, i.e., (1) inductive node representations and (2) inductive relational structure representations.
Inductive node representation approaches parameterize ENC, as a function of a fixed-size invariant vocab- ulary. For instance, PodePicco-QUE (Galkin et al., 2022b) employs the invariant vocabulary of relation types and parameterizes each entity through the set of incident relations. TeMP (Hu et al., 2022) employs the invariant vocabulary of entity types and class hierarchy and injects their representations into entity represen- tations. Inductive node representation approaches reconstruct embeddings of new entities and can be used as a drop-in replacement of shallow lookup tables paired with any processor method, e.g., NodePieco-QUP used CQD as the processor while TeMP was probed with GQE, Query2Box, BetaF, and LogicE processors.
Inductive relational structure representation methods parameterize ENC₂ as a function of the relative relational structure that only requires learning of relation embeddings and uses relations as invariants. Such methods often employ various labeling tricks (Zhang et al., 2021a) to label constants (anchor entities) of the input query Q such that after the message passing procedure all other nodes would encode graph structure relative to starting nodes. In particular, GNN-QE (Zhu et al., 2022) labels anchor nodes with the embedding vector of the queried relations, e.g., for a projection query rh,r,?) a node h will be initialized with the embedding of relation r, whereas all other nodes are initialized with the zero vector. In this way, GNN- QE learns only relation embeddings R and GNN weights. GNNQ (Pflueger et al., 2022) represents a query with its variables and relations as a hypergraph and learns a relational structure through applying graph convolutions on hyperedges. Hyperedges are parameterized with multi-hot feature vectors of participating relations, so the only learnable parameters are GNN weights.
Still, there exists a set of open problems for inductive models. As the majority of inductive hot rely on learning relation embeddings, they cannot be easily used in setups where at inference time KGs are updated with new, unseen relation types, that is, relations are not invariant. This fact might require exploration of novel invariances and featurization strategies (Huang et al., 2022a; Gao et al., 2023; Chen et al., 2023). To date, the only fully-inductive CLQA model capable of generalizing to new, unseen graphs with new sets of entities and relations at inference time is UltraQuery (Galkin et al., 2024) that leverages the invariance of relational structure. In particular, relational representations (for both seen and new unseen relation types) are obtained through the graph of relational interactions and the conditional message passing GNN encoder which is independent from relation identities and thus generalizable to any multi-rclational graph. Inductive models are more expensive to train in terms of both time and memory than shallow models and cannol yet be easily extended to large-scale graphs. We conjecture that inductive encoders will be in the focus of the future work in CLQA as generalization to unseen entities and graphs at inference time without re-training is crucial for updatability. Furthermore, updatability might increase the role of continual learning (Thrun, 1995; Ring, 1998) and amplify the negative effects of calastrophic forgetting (McCloskey & Cohen, 1989)
16

---

Published in Transactions on Machine Learning Research (11/2024)
that have to be addressed by the encoders. Larger inference graphs also present major size generulization issue (Yehudai et al., 2021; Buffelli et al., 2022; Zhou et al., 2022) when performance of GNNs trained on small graphs decreases when running inference on much larger graphs. The phenomenon has been observed by Galkin et al. (2022b) in the inductive complex query answering sctup.
5.2 Processor
Having encoded the query and other available inputs, the Processor P exccutes the query in the latent (or symbolic) space against the input graph. Recall that a query q is defined as q(E', S,,) where E' and R terms include constants Con and variables Var, statements in S and S include relation projections R(a, b), and logical operators ops over the variables. We define Processor P as a collection of modules that perform relation projections R(a, b) given constants Con and logical operators ops S {A, V,,.,, over variables Var (we elaborate on the logical operators in Section 6.1). Depending on the chosen inductive biases and parameterization strategics behind those modules, we categorize Processors into Newral and Neuro-Symbolic (Table 5a). Furthermore, we break down the Neuro-Symbolic processors inlo Geometric, Probubilistic, and Fuzzy Logic (Table 5b). Note that in this section we omit pure entity encoder approaches like TeMP (Hu et al., 2022), NodePicco-QE (Galkin et al., 2022b), and NRN (Bai al., 2023a) (for numerical litcrals only) that can be paired with any neural or neuro-symbolic processor. To describe processor models more formally, we denote as an entity vector, as a relation vector, and q as the query embedding that is often function of and r. We use Gg as the query graph.
Table 5: Categorization of Query Processors. Table 5a provides general view on Neural, Symbolic, Neuro- Symbolic methods as well as encoders that can be paired with any processor. Table 5b further breaks down neuro-symbolic processors.
(a) Complex Query Answering approaches categorized under the Processor type.
Any Processor
Neural
Neuro-Symbolic
TeMP (Ilu et al., 2022),
GQE (lamilton et al., 2018), GQE w/ hashing (Wang et al.,
Table 5b
NodePiece- QE (Galkin
2019), CGA (Mai et al., 2019), BiQE (Kotnis et al., 2021),
et al., 2022b), NRN (Bai
MPQE (Daza & Cochez, 2020), StarQE (Alivanistos et al., 2022),
et al., 2023a)
MLPMix (Amayuclas al., 2022), Query2Particles (Bai et al.,
2022), KGTrans (Liu et al., 2022), RotatE-m, DistMult-m,
ComplEx-m (Ren et al., 2022), GNNQ (Pftueger et al., 2022):
SignalE (Wang et al., 2022), LMPNN (Wang et al., 2023e), SQE
(Bai et al., 2023b), LARK (Choudhary & Reddy, 2023), BiDAG
(Xu et al., 2023a), Query2Triple (Xu al., 2023b)
(b) Neuro-symbolic Processors
Geometric (Neuro-Symholic]
Probabilistic (Neuro-Symollic]
Fuzzy Logic [Neuro-Symbolic)
Query2Box (Rea et sl. 2020), Query2Onto (Andresel et st, 2021), RotatE-Box (Adlakha
BetaE (Ren & Leskovee, 2020),
EmQL (Sun et al., 2020), TractOR (Friedman
PERM [Choudbary
al., 2021a), LinE (Huang et al.
& Van den Broeck, 2020), CQD (Arakelyan al, 2021), LogicE (Luus et al. 2021), FuzzQE (Chen et al., 2022), TAR (Tang et al,, 2022), FLEX (Lin et al., 2023), TFLEX (Lin et al., 2023), UnRavL (Cucumides et al., 2024), ENeSy (Nu et al., 2022), QTO (Bal et al., 20236), NQE (Tuo et al., 2023), Var2Vec (Wang et al,, 2023a), CQDA (Arakolyan et al, 2023), FIT (Yin es al,, 20235), LitCQD (Demir et al., 2023), WFRE (Wang et al., 20234), CQD Onto (Andresel et al, 2023), UnRavL (Cu- cumides et al., 2024), UltraQuery (Galkin et al,, 2024)
et sl., 2021), NewLook (Liu et al., 2021),
Knowledge Sheaves (Gebbart et al., 2023),
20226), GammaE (Yang et al.
HypE (Choudhary et al. 2021b), ConE (Zhang et al,, 2021b), Query2Geom (Sardina al., 2023), CylE (Nguyen et al., 2023b), RoConE (He et al., 2023), SCoNe (Nguyen et al., 2023n)
2022a), NMP-QEA REP (Long et al.
2022)
Neural Processors. Neural processors exccute relation projections and logical operators directly in the latent space Rd parameterizing them with neural networks. To date, most existing purely neural approaches
17

---

Published in Transactions on Machine Learning Research (11/2024)
graph
NW
R d
Win
IRd
feld
wn
wn
stinesity
Transformer
feld
LADEE
[MAX
linearization
held
Fool
O
(b)
(a)
[MASK
Figure 9: Neural Processors. (a) Relation projections Rø(a, b) and logical operators mnon-parametric or parameterized with 8) are exccuted soquentially in the latent space; (b) a query is encoded graph or linearized to a sequence and passed through the encoder (GNN Transformer, respectively). A pooled representation denotes the query embedding.
operate exclusively the query graph Gy only executing operators within single query and do not condition the exccution process on the full underlying graph structure G. Since the query processing is performed in the latent space with neural networks where Union (V) and Negation (-) are not well-defined, the majority of neural processors implement only relation projection (R(a, b)) and intersection (A) operators. We aggregate the charactoristics of neural processors as their embodding space, the way of exccuting relation projection, logical operators, and the final decoding distance function Table 6. We illustrate the difference between two families of neural processors (sequential execution and joint query encoding) in Fig. 9.
The original GQE (Hamilton et al., 2018) is the first example of the neural processor. That is, queries q: entities e, and relations r are vectors in Rd. Query embedding starts with embeddings of constants (anchor nodes e) and they get progressively refined through relation projection and intersection, i.e., it is common to assume that query embedding at the initial step equivalent to embedding(s) of anchor node(s), q = e. Relation projection is executed in the latent space with the translation function q + r, and intersection DeepSet (Zaheer et al., 2017) neural network. Several follow-up
is modeled with the cettunattiioniivvaaaa works improved GQE to work with hashed binary vectors (+1,-1) (Wang et al., 2019) replaced DeepSet with self-attention and translation-baser projection matrix- vector product (Mai et al., 2019). Recently, Ren et al. (2022) proposed DistMult-m, ComplEx-m, and RotatE-m, extensions of simple link prediction models for complex queries that, inspired by GQE, perform relation projection by the respective composition function and model the intersection operator with DeepSet and, optionally, L2 norm.
The other line of works apply neural encoders to whole query graphs Gg without explicit execution of logical operators. Depending on the query graph representation, such encoders are often GNNs, Transformers, MLPs. It is assumed that neural encoders can implicitly capture logical operators in the latent space during optimization. For instance, MPQE (Daza & Cochez, 2020), StarQF: (Alivanistos et al., 2022), and LMPNN (Wang et al., 2023e) represent queries as relational graphs (optionally, hyper-relational graphs for StarQE) where each edge is relation projection and intersection is modeled as two incoming projections to the same variable node. All constants C and known relation types are initialized from the respective embedding matrices. All variable nodes all query graphs are initialized with the same learnable [VAR] feature vector while all target nodes are initialized with the same [TAR] vector. Then, the query graph is passed through GNN encoder (R-GCN (Schlichtkrull et al., 2018) for MPQE, StarE (Galkin et al., 2020) for StarQE, GIN (Xu et al., 2019) for LMPNN), and the final state of the [TAR] target node is considered the final query embedding ready for dccoding. A recent LMPNN extends query graph encoding with an additional edge feature indicating whether given projection R(a, b) has a negation or not and derives a closed-form solution for the merged projection and negation operator for the ComplEx composition function. A different approach is taken by GNNQ (Pflueger et al., 2022) that frames query answering as a subgraph classification task. That is, an input query not directly executed over a given graph G, but, instead, the task is classify whether given precomputed subgraph G' G satisfies given conjunctive query.
18

---

Published in Transactions on Machine Learning Research (11/2024)
For that, GNNQ first augments the graph with Datalog-derived triples and converts the subgraph to hypergraph where only hyperedges are parameterized with learnable vectors. On the one hand, this strategy allows GNNQ to be inductive and not learn entity embeddings. On the other hand, GNNQ is limited to conjunctive queries only and extensions to union and negation queries are not defined.
A more exotic approach by Gebhart et al. (2023) is based on the sheaf theory and algebraic topology (Hansen & Ghrist, 2019). There, a graph is represented as a cellular sheaf and conjunctive queries are modeled as chains of relations (O-cochains). A sheaf is induced over the query graph and relevant answers should be consistent with the induced sheaf and entity embeddings. The optimization problem is a harmonic extension of a O-cochain using sheaf Laplacian and Schur complement of the sheaf Laplacian. Conceptually, this approach merges execution of projection and intersection operators as functions over topological structures.
Considering Transformer encoders, BiQE (Kotnis et al., 2021), kgsTransformer (Liu et al., 2022), and SQE (Bai ct al., 2023b) lincarize conjunctive query graph into a sequence of relational paths composed of entity constants C. and relation tokens. The order of tokens in paths and intersections of paths are marked with positional encodings. The target node (present in many paths) is marked with the [MASK] token (op- tionally, kgTTransformer also annotates existentially quantified variables with [MASK]). ). SQE does not model variables explicitly but instead relies on auxiliary bracket tokens that separate branches of the computation graph. Passing the sequence through the Transformer encoder, the final query embedding is the aggregated representation of the target node. BiQE only supports conjunctive queries while kg kgTTrnnffrmmrr converts queries with unions to the Disjunctive Normal Form (DNF) with post-processing of score distributions (we elaborate on query rewritings and normal forms in Section 6.1). SQE explicitly includes all operator tokens into the linearized sequence and thus supports negations.
Finally, MLPMix (Amayuelas el al., 2022) sequentially executes operations of the query where projection, intersection, and negation operators are modeled as separate learnable MLPs. Union queries are converted to DNF such that they can be answered with projection and intersection operators with the final post- processing of scores as a union operator. Similarly, Query2Particles (Bai et al., 2022) represents each query as a set of vectors in the embedding space and models projection, intersection, and negation operators as attention over the set of particles followed by an MLP. Union is concatenation of query particles.
Table 6: Neural Processors. Most methods implement only Relation Projection and Intersection operators. The top part of models execute a query sequentially, the bottom part encode the whole query graph Gg.
Model
Embeddiing Spare
Relation Projection
Interscction
Union
Negation
Distance
GQE
q R
--r sgnlq +r]
DeepSet((qi))
11 ell
GQE++hsshig
q.6 [ [i1)", re."
egn(DeopSeti
-os/q. c)
CGA
q.e.r Rd
W.q qor
SelrAtta((qh])
-colq e)
RotatE-m
q.e.r (N
DeapSat: (q:)
DisMult-m
q. g
L2Norn L2Norn(qur) f(q.r)
12llorn(DeepSett (1:)1)
(q.
CompliEx-m
q.e,r CV
L2Norr Deeppett((q))
Ree (ee((4. E))
Quer2Pariiclss
q.e gaxk rre Rd
MLP(Attm(((L_<4))
lq!......**) [") MLP(Actn(q))
max,
is neual gates
SignalE
CVVV=IDF(()) e Rd x E v IDFT(x)
q,e,r [
2 0z
SelfAttn((z..))
DNF
Bly v. vallat
14, x.
MLPMNxx
q.e,re E R
MLP. ML..../9..3))
DNF
MLP(q)
119 el
MPQE
q.e.re Rt
W.q
RG
e)slg.e)
StarQE
q.e.re R
flq.g(r. hamas))
StarElq. Q2)
dot(q.e)
GNNQ
q.r De
Hypergraph GCC
BCE
LMPNN
q.e,r CR
,lq.r, r. dir, neg)
GIN(q.9.)
DNF
plg.r. dir nog)
eaalq.e) e)
BIQE
q.e,r g
Translonerig,, linearized C.)
CE dot(q.e)
kg Transforerr
q. Rd
Transfornerrg. linearied G,)
DNF
SQE
q, Rd
LSTM / Trausfornerrq, linearized G2 with operator tokeus) /4 Sy as coclain)
dotiq.e)
Sleaves
q.e 6 R F, Raxa
F.. F.ell
Neuro-Symbolic Processors. In contrast to purely neural and symbolic models, we define neuro-symbolic processors as those who (1) explicitly design logic modules (or neural logical operators) that simulate the real logic/sct operations, or rely on various kinds of fuzzy logic formulations to provide probabilistic view of the query execution process, and (2) exocute relation traversal in the latent space. The key difference between neuro-symbolic processors and the previous two is that neuro-symbolic processors explicitly model
19

---

Published in Transactions on Machine Learning Research (11/2024)
01
0
02
++
r
q
2π - 0
projection (boxes)
intersection (boxes)
union (cones)
negation (cones)
Figure 10: Geometric Processors and their inductive biases.
the logical operations with strong inductive bias so that the processing / execution is better aligned with the symbolic operation (e.g., by imposing restrictions on the embedding space) and more interpretable. Wo further segment these methods into the following categories.
Geometric Processors. Geometric processors design an entity/query embedding space with different geometric intuitions and further customize neuro-symbolic operators that directly simulate their logical counterparts with similar properties (as illustrated Fig. 10). We aggregate the characteristics of geometric models as to their embodding space and inductive biases for logical operators in Table
Query2Box (Ren et al., 2020) embeds queries q as hyper-rectangles (high-dimensional boxes) in the Euclidean space. To achieve that, entities and relations are embedded as points in the Euclidean space where each relation has additional learnable offset vector (entities" offsets are zeros). The projection operator is modeled as an element-wise summation + of centers and offsets of the query and relation, that is, the initial box is obtained by projecting the original anchor node embedding e (with zero offset) with the relation embedding r and relation offset ro. Accordingly, an attention based neuro-intersection operator is designed simulate the set intersection of the qucry boxes in the Euclidean space. The operator closed, permutation invariant and aligns well with the intuition that the size of the intersected set is smaller than that of all input sets. The union operator is achieved via DNF, that is, union is the final step of concatenating results of operand boxes. Several works extend Query2Box, i.e., Query2Onto (Andresel et al., 2021) attempts to model complex ontological axioms by materializing entailed triples and enforcing hierarchical relationship using inclusion of the box embeddings; Rotat Box (Adlakha et al., 2021) designs an additional rotation- based Kleene plus (+) operator denoting relational paths (we claborate on the Kloene plus operator in Section 6.1); NewLook (Liu el al., 2021) adds symbolic lookup from the adjacency lensor4 to the operators, modifies projection with MLPs and models the difference operator as attention over centers and offsets (note that the difference operator is particular case of the 2in negation qucry, claborate that in Section 6.1); Query2Geom (Sardina el al., 2023) replaces an allention-based intersection operator with a simple non-parametric closed-form geometric intersection of boxes.
HypE (Choudhary et al., 2021b) extends the idea of Query2Box and embeds a query as a hyperboloid (two parallel pairs of arc-aligned horocycles) in a Poincaré hyperball to better capture the hierarchical information. A similar attention- neuro-intersection operator designed for the hyperboloid embeddings with the goal to shrink the limits with DeepSets.
ConE (Zhang et al., 2021b), on the other hand, embeds queries on the surface of set of unit circles. Each query is represented as cone section and the benefit is that in most cases the intersection of cones is still a cone, and the negation/ complement of a cone is also a cone thanks to the angular space bounded by 2r. Based on this intuition, they design geometric neuro-intersection and negation operators. RoConE (He et al.,
Incorrect implementation led the major leakage and incorrect reported results.
20

---

Published in Transactions on Machine Learning Research (11/2024)
Table 7: Geometric Neuro-Symbolic Processors. @ denotes element-wise multiplication, Oe denotes Möbius addition, O denotes Möbius scalar product. DS denotes DeepSets neural network. NewLook only partially implements negation as the difference operator.
Model Query2Box
Embedding Space
Relation Projection
Intersection
Union
Negation
Distance
= (tth((g)))
9. RM,,
Rd q+r
DNF
doat add
Query2Onto
miní (1bb)) () @ ()))((()))))
Query2Geom
q.r R O er
q+r
4
[(9 + (.) (q.
DNF
dont + add
9. 9. -1 4
DNF
RotatE-Boo Box
q.r , C²
(4o o Fo. 4o ro)
DS((q"))
dont + adm
q.r RM Rd
MLP[MLP(qe + ve) NLP(1.) x.]
9. Attm( x²))
Atta A Atta( Atta((gh..))
NewLook
x TRR xIE)
9a (( @ (D8((12)))
DNF
doat + add
9 = Attal [
HypE
q.r Rda, e R
q
4n min( (q..) @. (DS (gh.))
DNF
dont ardm
q. = 10xx 0xp)
9 (MLP(4 r))
e SenanticAvgl ......)))
0xx 0ax
ConE
e= 00 0)
DNF/DM
dout add
0x E [-n, 5)
gates Oux and Oap qor
0up CardMin(qq....
Oup
2x
Oxp
RoConE
0.p e 2,
Same as ConE +
CylE
oMLLP( +
Attn((g'))
DNF
Same ConE
dont ardm
Pnn E x)]
41
42
q
7(() 92))
q1
Mlq)
q2
0
projection (PERM)
intersection (BetaE)
union (PERM)
negation (BetaE)
Figure 11: Probabilistic Processors and their inductive biases.
2023) replaces the projection operator of ConE with the angular rotation in the complex plane. CylE (Nguyen et al., 2023b) turns cones into cylinders by adding an additional height dimension.
To sum up, the geometric-basee processors are often designed with a strong geometric prior such that properties of the logical/sct operations be better simulated satisfied.
Probabilistic Processors. Instead of a geometric embedding space, probabilistic processors aim to model the query and the logic/set operations a probabilistic space. Some examples of implementing logical operators a probabilistic space are illustrated in Fig. 11. The aggregated characteristics are presented Table 8.
BetaE (Ren & Leskovee, 2020) builds upon the Beta distribution and embeds entities/queries as high- dimensional Beta distribution with learnable parameters. The benefit is that one design parameterized neuro-intersoetion operator over two Beta embeddings where the output is still Beta embedding with more concentrated densily function. neuro-negation operator can be designed by simply laking the reciprocal of the parameters in order to flip the density. PERM (Choudhary et al., 2021a) looks at the Gaussian distribution space and embeds queries as a multivariate Gaussian distribution. Since the product of Gaussian probability density functions (PDFs) still Gaussian PDF, the neuro-intersection operator accordingly caleulates the parameters of the Gaussian embedding of the intersected set. NMP-QEM (Long al., 2022)
21

---

Published in Transactions on Machine Learning Research (11/2024)
win
0.5
0.3
0.2
0.3
0.9
0.1
0.5
0.3
0.2
0.3
0.9
0.5
0.3
score(a, win,?) ?)
0.02
0.15
0.27
0.28
0.65
0.93
0.9
0.5
0.7
projection
intersection (product t-norm)
union (product t-conorm)
negation (fuzzy)
(scoring function)
Figure 12: Lozzy-Logic Processors and fuzzy logical operators.
develops this idea. further and represents a query as mixture of Gaussians where logical operators are modeled with MLP or attention over distribution paramcters. LinE (Huang et al., 2022b) transforms the Beta distribution into a discrete sequence of values. taking the reciprocal as BetaE while designing a new neuro- iouro-intersection /union operator by taking element- wise min/mas /max. GammaE (Yang et al., 2022a) replaces Beta distribution with Gamma distribution as entity and query embedding space. Parameterizing logical operators with operations over mixtures of Gamma distributions, union and negation become closed, do not need DNF DM transformations, and can be executed sequentially along the query computation graph. Overall, probabilistic processors are similar to geometric processors since they are all inspired by certain properties of the probability and geometry used for embeddings and customize neuro-logic operators.
similar neuro-negation operator is introduced by
Table 8: Probabilistic Neuro-Symben Processors.
Model
Embedding Space 9,6 g
Relation Projection
Intersoction
Union
Negation
Distance
Betal
MLP,(g)
[ 1020 Σ [m,)))]
DNF/DM
KL(e: q)
Nin, Bes (E 2
Me) Eip
PERM
9.e,r - N((,E)
Atta((gg))
Ya (X M4
Eg (22)
Me)
LinE
q.e R
MLP,(q)
min 92)
max
1
q el
GammaE
9.e E g
MLP,(g)
12 10:06) Σ w(3)
Attal(q:)
1
KL(e: q)
NMP-QEM
0 R"
MLP,(q)
Atto((q:))
DNF
MLP(g)
> >
El WiN(,, E.)
Fuzzy-Logic Processors. Unlike the methods above, fuzzy-logic processors directly model all logical operations using existing fuzzy logic theory (Klement et al., 2013; van Krieken et al., 2022) where intersection can be expressed via t-norms and union via corresponding t-conorms (Section A.4). such a way, fuzzy- logic processors avoid the need to manually design or learn neural logical operators as in the previous two processors but rather directly use established fuzzy operators commonly expressed as differentiable, element- wise algebraic operators the projection operator might still be parameterized with neural network. The aggregated characteristies of fuzzy-logic processors are presented in Table 9. Generally, fuzzy processors aim to combine execution in embedding space (vectors) with entity space (symbols). The described methods are different in designing such a combination.
vectors (Fig. 12). While interscction, union, and negation non-parametric,
One of the first fuzzy processors is EmQL. (Sun et al., 2020) that imbues entity and relation embeddings with a count-min sketch (Cormode & Muthukrishnan, 2005). There, projection, intersection, and union are performed both in the embedding space and in the symbolic sketch space, e.g., intersection is modeled element-wise multiplication and union is element-wise summation of two sketches. CQD (Arakelyan et al., 2021) scores cach atomic formula in a query with pretrained neural link predictor and uses t-norms and I-conorms lo compute the final score of a query directly in the embedding space. CQD does not train any neural logical operators and only requires pretraining the entity and relation embeddings with one-hop links such that the projection operator equivalent to top-k results of the chosen scoring function, e.g., ComplEx (Lacroix et al., 2018). The idea was then extended in several directions: Query Tree Optimization (QTO) (Bai et al., 2023c) added look-up from the materialized tensor of scores of all possible triples
22

---

Published in Transactions on Machine Learning Research (11/2024)
M E [0, 1] R|x|E|X|E| to the relation projection step; CQD4 (Arakelyan et al., 2023) and Var2Vec (Wang et al., 2023a) learn an additional linear transformation of the entity-relation concatenation W(q. r|; Fuzny Inference with Truth Value (FIT) (Yin et al., 2023b) added several query rewriting steps to tackle DAG and cyclic querics, LitCQD (Demir et al., 2023) added a jointly trained regression model on entitics' numerical altributes to include numerical literals into queries and answers. CQD Onto (Andresel el al., 2023) further adds the support for ontological axioms.
LogicE (Luus et al., 2021) designs logic embeddings for each entity with a list of lower bound upper bound pairs in range [0,1], 1], which can be interpreted
uniform distribution between the lower and upper bound. LogicE exccutes negation and conjunction with continuous t-norms over the lower and upper bounds. FuzzQE (Chen et al., 2022), TAR (Tang et al., 2022), and WFRE (Wang et al., 2023d) embed query to a high- dimensional fuzzy space [0, 1)dd and similarly use Gödel t-norm and Lukasiewicz t-norm to model disjunction, conjunction and negation. FuzzQE and WFRE model relation projection as a relation-specific ML.P whereas TAR uses a geometric translation (element-wise sum). FLEX (Lin et al., 2022) and TFLEX (Lin et al., 2023) embed query as a mixture of feature and logic embedding. For the logic part, both methods use the real logical operations in vector logic (Mizraji, 2008). TFLEX adds temporal module conditioning logical operators on the time embedding.
GNN-QE (Zhu et al., 2022) models the likelihood of all entities for each relation projection step with a graph neural network NBFNet (Zhu et al., 2021). It further adopts product logic to directly model the set operations (intersection, union, and negation) over the fuzzy set obtained after a relation projection. GNN-QE employs a node labeling technique where a starting node is initialized with the relation vector (while other nodes are initialized with zeros). This allows GNN-QE to be inductive and not rely on trainable entity embeddings. UnRavL (Cucumides et al., 2024) extends the framework to queries that might not have a starting anchor node. ENeSy (Xu et al., 2022), on the other hand, maintains both vector and symbolic representations for queries, entities, and relations (where symbolic relations are encoded into M, sparse adjacency matricos). Logical operators are executed first in the neural space, 6.g., relation projection is RotatE composition function (Sun et al., 2019), and then get intertwined with symbolic representations. Logical operators in the symbolic space employ a generalized version of the product logic and corresponding t-ooonnorms.
In summary, fuzzy-logic processors directly rely on established fuzzy logic formalisms to perform all the logical operations in the query and avoid manually designing and learning neural operators in (possibly) unbounded embedding space. The fuzzy logic space is continuous but bounded within [0, 1] this is both the advantage and weakness of such processors. The bounded space is beneficial for closed logical operators as their output values still belong to the same bounded space. On the other hand, most of the known t-norms (and corresponding t-conorms) still lead to vanishing gradients and only the Product logie norms are stable (van Kricken et al., 2022: Badreddine et al., 2022). Another caveat is designing effective and differentiable interaction mechanism between the fuzzy space [0, 1jd and unbounded embedding space Fd (or C4) where relation representations are often initialized from. That is, re-scaling and squashing of vector values when processing computation graph might lead to noisy gradients and unstable training which is observed, for instance, by GNN-QE that has to turn off gradients from all but last projection step.
5.3 Decoder
The goal of decoding is to obtain the final set of answers or a ranking of all the entities. It is the final step of the query answering task after processing. Here we categorize the methods into two buckets: non- parametric and parametric. Parametric methods require a parameterized method to score an entity (or predict regression target from the processed latents) while non-parametrie methods can directly measure the similarity (or distance) between pair of query and entity on the graph. Most of the methods belong to the non-parametric category as shown in the Distance column of processor tables Table 6, Table 7, Table 8, Table 9. For instance, geometric models (Ren et al., 2020; Andresel el. al., 2021; Adlakha el al., 2021; Choudhary et al., 2021b; Zhang et al., 2021b) pre-define a distance function between the representation of the query and that of an entity. Commonly employed distance functions are L1 (Hamilton et al., 2018; Ren et al., 2022; Gebhart et al., 2023; Amayuclas et al., 2022; Tang et al., 2022; Xu al., 2022; Long et al., 2022), T.2 (Huang et al., 2022b; Chen et al., 2022), their variations (Laus et al., 2021; Lin et al., 2022;
23

---

Published in Transactions on Machine Learning Research (11/2024)
Table 9: Fuzzy Yeuro-Symbolic Processors.
Model
Embedding Space
Relation Projection
Incersection
Union
Negation
Distance
e E 12", . E h count-min skrtch
(41 + 42)/2
(q + 9a//2
EmQL
NIPS(q, [r,es, ec])
dot(q.e) e)
by @ b2
b, + by
CQD
C*
ming: d(q). r. q2) or
Product: qi qp
91 + 92 91 qa
dist(q.e)
LitCQD
top, (d(q). r,el)
Gödel: min(q;. q2)
max 92)
CQDA
W g2x2d
q.e.r
top, [pold( r.l)l]]
W [
Gödel: min(1u. 42)
Product: 91 qp
91 42 Q11 "aa
max(q1.92) (2)
1 q (1 cos(zq))/2
diat(q.e)
Var2Vee
W Rdxod
q,e,r Qu
9: r]
d.q..
Gödel: min(qs. 92)
Product: q1 q2
91 Q2
max(q1.
(2))
Q1 qa
1 1-4 4
dist(q.e)
QTO
FIT
M E [0, (ix1111))
q,e,r E QR
dqq.
low, (M,)
91-92
q1 + 92
Q1 -92
r. row M,)
dist(q.e)
q.0= u.l.
o (maxx(, max((,
(TC)
d"
4,
LugicE
4.u, E [0, 1))m
Ir. q. FF)))))
T(
DM
1 - ux]]
llq eli
R
1....
FuzeQE
9.0 E [0.
(MLP-()))
Product: 91 4a
9n 92 91 Q2
1 q
dot(q.e)
Gödel: min(q1-9p)
max
WFRE
9.0 [0,
(ML).(())
min/qn. qa)
max qa)
1
wPR(q.e)
TAR
q.e,r E Rd
Attal 9a)
max 92)
1
||q el
GNN-QE
E "R,Rr Eg
OCC q. G)
-p
qu
1
BCB(g)
(0,, 9))
(M, Oraci
2, a,llad
0y L. tanhl MLP( 01))
8, = >> g00
0y E [- L,
0 + 8,,ll)
6 = L. 0n.
1169 1
FLEX
(9;.0) 0)
Eisigsen 0 0
g gates oz.
9: 11,6,.t
A E 1]
+.+ (-1) 11111"-- 11.0
q. = (q), of 9...)..))) 9f.9%. ef E ied
Entity: g(HLP( q a+r+6)) 6])
.. (q.a).
l0g - +
E, p. ((ata)
Σ, ((1,))
af
97 11 +
TFLEX
e (ef, 0,0.0)
Time: (MLPP(
E ((
Σ ( ((Gf.
95.95.
Itty 11
o. E 1]
qi + q2))
Σ, saf, ((91)))))
Σ E. (,(19)
fin (((a))
q.e,r E CH
Noura: q
ENeSy
P. E (0. 1)
Symb: M.),
g(Pi P2)
A(P + P2 Di -Pi-Pa)
-Pa)
P)
||q ell dot(q.e)
M, E [0. 131E(11E)
g - x/sum(xx
NQE
q.e,r E 1j
oTr Gy1)
91 -
91 + 92
q1 -1
1-9 q
2023), cosine similarity (Wang ct al., 2019; Mai et al., 2019; Daza & Cochez, 2020; Wang et al., 2023e), dot product (Sun et al., 2020; Ren et al., 2022; Alivanistos et al., 2022; Liu et al., 2022; Bai et al., 2022; Luo et al., 2023), or naturally model the likelihood of all the entities without the need of a distance function (Arakelyan et al., 2021; Kotnis et al., 2021; Zhu et al., 2022; Pflueger et al., 2022; Bai et al., 2023c; Arakelyan et al., 2023; Wang et al., 2023a). Probabilistic models often employ KL divergence (Ren & Leskovee, 2020; Yang et al., 2022a) or Mahalanobis distance (Choudhary el al., 2021a). A rather exotic approach is Wasserstein-Pisher Rao metric (WFR) used in WFRE Wang et al. (2023d). WFR is an optimal transport (OT) metric between distributions. Duc to its computational complexity, the metric is approximated by the 1D convolution-based Sinkhorn optimization routine.
One important direction (orthogonal to the distance function) that current methods largely ignore is how to perform efficient answer entity retricval over extremely large graphs with billions of entities. A scalable and approximate nearest neighbor (ANN) search algorithm is necessary. Existing frameworks including FAISS (Johnson et al., 2019) or ScaNN (Guo et al., 2020) provide scalable implementations of ANN. However, ANN is limited to L1, L2 and cosine distance and mostly optimized for CPUs. It is still an open research problem how to design efficient scalable ANN search algorithms for more complex distance functions such as KL divergences so that we can retrieve with much better efficiency for different CL.QA methods with different distance functions (prefcrably, using GPUs).
We conjecture that parametric decoders are to gain more traction in numerical tasks top of plain entity retrieval for query answering. Such tasks might involve numerical and categorical features on node-, edge, and graph levels, e.g., training regressor to predict numerical values for node attributes like age, length, etc. Besides, a parametric decoder gives new opportunities lo generalize to inductive sellings where we may have unseen entities during evaluation. SE-K SE-KGE (Mai et al., 2020) takes a step in this direction by predicting goospatial coordinates of query targets. LitCQD (Demir et al., 2023) expands the set of query variables and answers to continuous numerical values by joint training of link prediction model between entities and a regression model on top of entities' attributes with numerical values.
24

---

Published in Transactions on Machine Learning Research (11/2024)
5.4 Computation Complexity
Here we analyze the time complexity different query reasoning models categorized by different operations, including relation projection, intersection, union, negation and answer retrieval after obtaining the repre- sentation of the query. We list the asymptotic complexity in Table 10 for methods that perform stepwise encoding of the query graph, and Table 11 for methods (mostly GNN-based) that encode the whole query graph simultancously including projection and other logic operations.
Table 10: Time complexity of cach operation 9 (E, S). Across all methods, we denote the embedding dimension and hidden dimension of MLPs as d, number of layers of MLPs/GNNV as I, number of branches in an intersection operation as number of branches in a union operation as
Model CQE
Projection
Intersection
Negation
Union
Answer Retrieval
Definitions
GQE+bashing
RotatE-m
(d)
O(ild)
O((Eld)
Distmult-m
ComplEx-m
CGA
Old")
O((E)d)
Query2Particles
O(Kd")
OaKdd")
O(Kd")
DNF
O(E (
K: #particles.
SignalE
O(d)
O(ild")
O(d)
DNF
O(EEld)
MLPMix
O(ld")
O(ild")
O(id")
DNF
O([Eld)
Query2Box
((d)
O(ild")
DNF
O((E]d)
Query2Onto
Query2Ceom
(dd)
O(d)
DNF
O((Eld)
RotatE-Box
((d)
DNF O(uld")
O((Eld)
NewLook
O(18| | Id")
O(((()) (d)))
Oldd)
DNF
O((Eld)
Hypp
(d))
O(ild)
DNF
O([Eld)
ConE//Betal'
(lld)
((ild")
O(d)
DNF
O((E]d)
PERM
Old")
Olid")
DNF
O(EId))
Links
O(ld")
O(d)
O(d)
Old)
O([8/d)
Gammak
O(ld")
O(ild")
O(d)
Ould")
O((8]d)
NMP-QEN
O(Kid")
O(K d)
O(Kld")
DNF
O(E(dK)
K # centers
EmQQ
O(EEd)
O(d)
O(d)
O1EE4)
CQD-CO
O([Eld)
Opt
Opt
O((Eld)
CQD-Beam
([E]d)
((E)kd)
O([E kd)
O([E)d)
('(o) the
(maxx (vx)
maximum truth value
QTO
O((8)
O(EE)
O((S))
O(EE)
> 0|(8))
for the subquery
ronted node
LogicE
O(ld))
O(d)
O(d)
O(d)
O([8]d)
FuzzQE
O(d")
O(d)
O(d)
((d)
O([8]d)
TAR
(d)
O(d)
O(d)
O(d)
O([E]4)
GNN-QE
O(EE)d (S
O[[8])
O(EE)
O(EE)
O(ED
FLEX
O(ld))
O(ild))
O(id")
Oluld" 2
(((84))
TFLEX
O(la")
Olild")
O(la")
(uldd)
Table 11: Time complexity of answering query for methods that directly encode the query graph. Besides the operators defined in Table 10, we denote ny average degree of the query graph G, = (E,, S.))
Model
Projection
Intersection Negation
Union
Answer Retrieval O(E|d)
MPQE GNNQ
Old2n, (iInnlEE Eg
StarQE
ng Egg SSyl1pp
O(E|d)
LMPNN
O (dd ddnn
DNF
O(EEd)
BiQE
O1Egld Eg d)))
O(E|d)
kg Transformer
Olddnn EEg1 E (d))
O(EEd)
SQF
O([[Eg] d² + & Pd)))
O(E|d)
25

---

Published in Transactions on Machine Learning Research (11/2024)
6 Queries
The third direction to segment the methods is from the queries point of view. Under the queries category, we have three subcategories: Query Operators, Query Patterns, and Projected Variables. For query operators, methods have different, operator expressiveness, which means the set of query operators one model is able to handle including existential quantification (3), conjunction (A), disjunction (V), negation (-), Kleene plus (+), filter and various aggregation operators. For query patterns, we refer to the structure/ patter of the (optimized) query plan, ranging from paths and trees to arbitrary directed acyelic graphs (DAGs) and cyclic patterns. As to projected variables (by projected we refer to target variables that have to be bound to particular graph elements like entity or relation), queries might have a different number (zero or more) of larget variables. We are interested in the complexily of such projections as binding of two and more variables involves relational algebra (Codd, 1970) and might result in a Cartesian product of all retrieved answers.
6.1 Query Operators
Different query processors have different expressiveness in terms of operators a method can handle. Through- out all the works, we compiled Table 12 that classifies all methods basod on the supported operators.
Table 12: Query answering processors and supported query operators. Processors supporting unions also support projection and intersection (사). Models supporting negation (-) also support unions, projections,
and intersections.
Projection and Intersection (A)
Union (V)
Negation (-)
Kleene
Filter & Aggr
GQE Mammiton ol,, 2018)
Query2Box [Ren all, 202))
BetaE (Btn & Leskover, 2020)
RotstE-Box. (Adlakha et al., 2021)
LaCQD (numberr)
GQE hashed (Wang es al., 2019)
EmnQ (Sun at al., 2020)
CouE (Zlingg et ol., 2021b)
(Demls et al. 2020)
CGA 2001))
Query2Onto (Andresel al, a21)
LogicE (Lems al,, 2021)
TracsOOt (Prindman & Vian den Browk, 2020)
HypE. (Clomdllory vi al, 20216)
MLPMix (Amayymiiss et al., 2002)
MPQE (Maoa Coches, 2000)
NewTook (Iiu et al., 2011)
Query2Partiche (Taa et al,, 200)
BiQE (Kotnis al., 2021)
PERM (Choudisary
2021a]
LinE (Huncy 20226)
Sheaves (Gebbart ot al., 2022)
CQD (Aralasiya ol., 2021)
Gammall E (Yong et al., 2022a)
StarQE (Alivaniskee st sd., 2022)
kg Traanssfommrr (Liu et al., 2022)
NMP-QUM (Long wi al, 2022)
RotatE-m, DistMult-m,
Query2Geom (Sardinn ol., 2023)
Fuz (Chen
2022)
ComplEx-m (Iten et ol, aned)
LtCQQ (Demtr et al,, 2015))
TAR ("bog al., (azz)
GNNQ (PHugger et al., 2022)
BiDAG (Xi et 20236)
GNN-QE (Zac es all, 2022))
NRN (Bai et al,, 201543
FLEX (I.i nl, 9022)
CQD Outo (Aminsed in al., 2023)
TFLEX (Lin et ol., 2028)
ENeSy (Nu
QTO (Bai al., 2023c)
SigualE [Wang et al., 2022)
LMPNN (Wang
2020a)
NQE (Luo et all, 2023)
Var2Vee (Winng al,, 20036)
CQD (Araladyan al,, asrs)
SQF (Rai et sl., 30239)
RoConB (Nl et al., 8023)
CylE (Ngayen
20256)
FIT (Vin at al., 20236)
WFRE (Wang et nl., 2023d)
LARK (Choudhary Roddy, 2020)
SCoNe (Ngrryen et al,, 201s))
Querr2Tttiple (Xa es al., 2020b)
UnRavL (Cocumshee
20044)
UltrQQuery (Galkin et sl., 2024)
We start from simplest conjunctive queries that involve only existential quantification (4) and conjunction (A) and gradually increase the complexity of supported operators.
Existential Quantification (3). When 3 appears in query, this means that there exists at least one existentially quantificd variable. For example, given a query "At what universities do the Turing Award winners work?" and its logical form q = U, AV win(TuringAward, V) A universily(V Uz), here V is the existentially quantified variable. Query processors model existential quantification by using a relation projection operator. Mapping to query languages like SPARQL, relation projection cquivalent to a triple pattern with one variable, e.g., (TuringAward win ?v) (Fig. 13). Generally, as introduced in Section 5.2, query embedding methods embed a query in bottom-up fashion, starting with the embedding of the anchors
26

---

Published in Transactions on Machine Learning Research (11/2024)
(leaf nodes) and gradually traversing the query tree up to the root. In such way, query embedding methods (e.g., geometric or probabilistic) explicitly obtain an embedding for the existentially quantified variables. The prreedddiggs/pppreenntttiioo
of these variables are calculated by a relation projection function implemented as shallow vector operations (Hamilton et al., 2018; Ren et al., 2020; Choudhary ct al., 2021b; Arakelyan et al., 2021; Ren et al., 2022) or deep neural nets (Ren & Leskovec, 2020; Zhang et al., 2021b; Bai et al., 2022; Amayuclas ct al., 2022). Another set of methods based on GNNs and Transformers directly assigns learnable initial embedding for the existentially quantified variables. These embeddings are then updated through several message passing layers over the query plan (Daza & Cochez, 2020; Alivanistos et al,, 2022; Pflueger et al., 2022; Wang et al., 2023e) or attention layers over the serialized query plan (Kotnis et al., 2021; Liu et al., 2022).
The major drawback of existing neural query processors is the assumption of at least one anchor en- tity in the query from which the answering process starts and relation projections can be executed. It remains an open challenge and an avenuc for future work to support queries without anchor entities, e.g, Q1 U2.301 02 : win((1, 02) A universily( (2, Ut), and queries where relations are variables, e.g.. 92 = rz (Turrnggwward Bengio),
Bengio)) that can be framed as the relation prediction task.
Universal Quantification (V). A universally quantified variable Vz.P(x) means that a logical for- mula P(z) holds for all possible z. Usually, the universal quantifier does not appear in facts-only ABox graphs without lypes and complex axioms (see Section 4.3) as it would imply that some entity is con- nected to all other entities. For example, W...un((TuringAwardd. V) without other constraints implies that all entities are connected to TuringAward by the win relation (which docs not occur in practice). How- ever, universal quantifiers are more useful when paired with the class hierarchy (unary relations), e.g.. 3rpaper, Vr E Researcher: Reeseacche(r)) A authored(r, Ppaper) means that the authored relation projection would be applied only to entities of class Researcher.
Currently, existing CLQA approaches do not support universal quantifiers explicitly nor the datasets include queries with the V quantifier. Still, using the basic identity Vz. = -(Ir.-((=)) it is possible to model the universal quantifier by any approach supporting existential quantification 3 and negation By default, we assume the cloled-world assumption. We leave the implications of universal quantification pertaining to the open-world assumption (OWA) out of the scope of this work.
Conjunction (A). We elaborate on the differences of those query patterns in the following Section 6.2 and emphasize our focus on more complex interscction queries going beyond simpler path-like queries.
Query processors, as described in Section 5.2, employ different parameterizations of conjunctions as permutation-invariant set functions. A family of neural processors (Hamilton et al., 2018; Wang et al., 2019; Ren et al., 2022) often resort to the DeepSet architecture (Zaheer et al., 2017) that first projects cach set element independently and then pools representations logether with a permutation-invarian function (e.g., sum, mean) followed by an MLP. Alternatively, (Mai al., 2019; Bai et al., 2022) self-attention, can serve a replacement of the DeepSet where set elements are weighted with the attention operation. The other family of neural processors combine projection and intersection by processing the whole query graph with GNNs (Daza& & Cochez, 2020; Alivanistos et al., 2022; Pflueger et al., 2022; Wang et al., 2023e) or with the Transformer over linearized query sequences (Kotnis et al., 2021; Liu et al., 2022). Geometric proces- sors (Ren et al., 2020; Liu et al., 2021; Choudhary et al., 2021b; Zhang et al., 2021b; He et al., 2023; Nguyen et al., 2023b) implement conjunction as the attention-based average of centroids and offsets of respective geometric objects (boxes, hyperboloids, concs, or cylinders). Probabilistic processors (Ren Leskovec, 2020; Choudhary el al., 2021a; Huang et al., 2022b; Yang el al., 2022a) implement. intersection as a weighted sum of parametric distributions that represent queries and variables.
Fuzzy-logic processors (Arakelyan et al., 2021; Luus et al., 2021; Chen et al., 2022; Zhu et al., 2022; Wang et al., 2023d; Yin et al., 2023b; Demir et al., 2023) commonly resort to I-norms, generalized versions of conjunctions in the continuous [o, 1] space and corresponding t-comorms for modeling unions (Section A.4). Often, due to the absence of a principal study, the choice of the fuzzy logic is a hyperparameter. We posit that such a study is an important avenue for future works in fuzzy processors. More exotic neuro-symbolic methods for modeling conjunctions include wies product of count-min sketches (Sun et al., 2020) or
27

---

Published in Transactions on Machine Learning Research (11/2024)
SPARQL Basic Graph Pattern
{
{
TuringAward
win ?v.
TuringAward win ?v.
TuringAward win ?v.
?v
uni
?u.
DeepLearning field ?v.
}
3
}
Existential Quantification (Relation Projection)
Intersection (Join)
Intersection (Join)
win
?v
Computation Graph
win
win
uni
?v
?u
field
D
Figure 13: Query operators (relation projection and intersection), corresponding SPARQL basic graph pat-
terns (BGP), and their computation graphs. Relation Projection (left.) corresponds to a triple pattern.
as a weighted sum in the feature logic (Lin et al., 2022; 2023). Finally, some processors (Tang et al., 2022; Xu et al., 2022) perform conjunctions both in the embedding and symbolic space with neural and fuzzy operators.
We note that certain neural query processors that embed queries directly (Hamilton et al., 2018; Wang et al., 2019; Mai et al., 2019; Friedman & Van den Broeck, 2020; Ren et al., 2022) or via GNN/ T'IN/TTraooommee encoder over query graph (Daza & Cochez, 2020; Kotnis et al., 2021; Gebhart et al., 2023; Alivanistos et al., 2022; Das et al., 2022; Pflueger et al., 2022) support only projections and intersections, that is, their extensions to more complex logical operators are non-trivial and might require changing the underlying assumptions of modeling entities, variables, and queries. In some cases, support of unions might be enabled when re- re-writing query to the disjunctive normal form (discussed below).
Disjunction (v). Query processors implement the disjunction operator in several ways. However, model- ing disjunction is notoriously hard since it requires modeling any powerset of entities the graph in vector space. Before delving into details about different ways of modeling disjunction, we first refer the readers to the Theorem in Query2Box (Ren et al., 2020). The theorem proves that we need the VC dimension of the function class of the distance function to be around the number of entities on the graph.
The theorem shows that in order to accurately model any EPFO query with the existing framework, the complexity of the distance function measured by the VC dimension needs to be as large the number of common distance functions based hyper-plane, Euclidean sphere,
KG entitics. This implics that if or axis-aligned rectangle, their parameter dimensionality needs to be at least O((E)) for real KGs. In other words, the dimensionality of the logical query embeddings needs to be (((&)), which is not low-dimensional; thus not scalable to large KGs and not generalizable in the presence of unobserved KG edges.
The first idea proposed in Query2Box (Ren et al., 2020) is that given a model has defined distance function between a query representation and the entity representation, then query can be transformed (or re-written) into its oquivalent disjunctive normal form (DNF), i.c., disjunction of conjunctive queries. For example, can safely convert query (Av (AVB)AN (CV D) to ((AAC) (A V (B A AC) (B (B D)), where A, C, are atomic formulas. In such a way, we only need to process disjunction V at the very last step. For models that have defined a distance function between the query representation and entity representation d(q e) (such as geometric processors (Ren et al., 2020; Andresel et al., 2021; Adlakha et al., 2021; Choudhary et al., 2021b; Zhang al., 2021b; Sardina et al., 2023; He al., 2023; Nguyen et al., 2023b) and some neural processors (Liu et al., 2022; Amayuclas et al., 2022; Wang al., 2023c), the idea of using DNF handle disjunction to (1) embed each alomic formula / conjunctive query in the DNF into vector qi, (2)
For the detailed VC dimensions of these function classes, see Vapnik (2013). Crucially, their VC dimensions are all linear with respect the number parameters d.
28

---

Published in Transactions on Machine Learning Research (11/2024)
SPARQL Basic Graph Pattern
DeepLearning field ?v.}
?s ?p ?V. FILTER NOT EXISTS
UNION
JohnDoe knows+ ?v.
{ Mathematics field ?v.
$DeepLeazning field ?v.
Union
Negation (NOT)
Kleene Plus (+)
(OR)
(Property Path)
field
D
Computation Graph
field
knows
knows
D
?V
?v
field
M
?v
Figure 14: Query operators (union, negation, Kleene plus), corresponding SPARQL basic graph patterns (BGP), and their computation graphs.
calculate the distance between the prrreeenttaiionmmmeedttitn of each atomic formula / conjunctive query and the entity d(qi e), (3) take the minimum of the distances min,(d(;; (d((q,e)). e)). The intuition is that since disjunction models the union operation, as long as the node is close to one atomic formula / conjunctive query, should be close to the whole query. Potentially, many neural processors with the defined distance function and originally supporting only intersection and projection can extended to supporting unions with DNF. One notable downside of this modeling that it exponentially expensive (to the number of disjunctions) in the worst case when converting query to its DNF.
Another category of mostly probabilistic processors (Choudhary et al., 2021a; Yang et al., 2022a) proposes neural disjunction operator implemented with the permutation-invarre invariant attention over the input set with the closure assumption that the result of attention weighting union remains in the same probabilistic space as its inputs. Such models design a more black-box framework to handle the disjunction operation under the strong closure assumption that might. not be true all cases.
The third way of modeling disjunction is based on the De Morgan's laws (Ren & Leskovec, 2020). According to the De Morgan's laws (DM), the disjunction is equivalent the negation of the conjunction of the negation of the statements making up the disjunction, i.e., A B = -(-A A -B). For methods that can handle the negation operator (detailed in the following paragraph). they model disjunction by using three negation operations and one conjunction operation. DM conversion was explicitly probed in probabilistic (Ren & Leskovee, 2020), geometric (Zhang et al., 2021b), and fuzzy (Luus et al., 2021) processors.
Finally, most fuzzy-logic (Arakclyan et al., 2021; Chen al., 2022; Tang al., 2022; Zhu et al., 2022; Bai al., 2023c; Arakelyan al., 2023; Wang al., 2023a;d; Yin al., 2023b; Demir et al., 2023) processors employ t-conorms, generalized versions of disjunctions in the continuous [0, 1] space (Section A.4). More exotic versions of neuro-symbolic disjunctions include alement-wise summation of count-min sketches (Sun et al., 2020), feature logic operations (Lin et al., 2022; 2023), well as performing union in both embedding and symbolic spaces (Tang et al., 2022; Xu et al., 2022) with fuzzy operators.
Negation (-). For negation operation, the goal is to model the complement set,, i.e., the answers A, to query 9 V/2 (r, V%) the exact complement of the answers Ag to query g' = V/ r(v, 14): Ag = V/Ar- Correspondingly, negation in SPARQL can be implemented with FILTER NOT EXISTS or MINUS clauses. For example (Fig. 14), a logical formula with negation -felldDDepLeearinng, V) is equivalent to the SPARQL BGP (?s ?p ?v. FILTER NOT EXISTS (DeepLearning field ?v}} where {?s ?p ?v} models the universe set (1) of all facts that gets filtered by the triple pattern.
Modeling the universe set (1) and its complement is the key problem when designing a negation operator in neural query processors, e.g., arbitrary real Ih or complex C space is unbounded such that I is not
29

---

Published in Transactions on Machine Learning Research (11/2024)
defined. For that reason, many neural processors do not support the negation operator. Still, there exist several approaches to handle negation.
The first line of works (Bai et al., 2022; Amayuelas et al., 2022; Long et al., 2022) designs a purely neural MLP-based negation operator over the query representation avoiding the universe set altogether. Similarly, a token of the negation operator can be included into the linearized query representation (Bai et al., 2023b) to be encoded with Transformer or recurrent network. A step aside from purely neural operators is taken by GNN-based processors (Wang et al., 2023e) that treat negation edge a new edge type during message passing over the query computation graph.
The second line is customized to different embedding spaces and aims to simulate the calculation of the universe and complement in the embedding space, e.G,, using geometric cones (Zhang el al., 2021b; He et al., 2023) or cylinders (Nguyen et al., 2023b), parameters are angles such that the space (and, hence, 1) is bounded to 2n and the complement is straight 2n 0. Probabilistic methods (Ren & Leskovee, 2020; Huang et al., 2022b; Yang et al., 2022a) naturally represent negation as an inverse of distribution parameters.
Thirdly, fuzzy logic processors explicitly model the universe set 1 and the complement over the same real valued logic space. For instance, LogicE (Luus et al., 2021), FuzzQE (Chen et al., 2022). WFRE (Wang et al., 2023d) restrict the query embedding space to the range [0, 1] where each query q E [0, 1] is a vector. This way, the universe 1 is represented with a vector of all ones (in the embedding space 1d) and negation is simply q-q. TAR (Tang et al., 2022), GNN-QE (Zhu et al., 2022), FIT (Yin et al., 2023b) operate over fuzzy sets where each entity has a corresponding scalar q E [0. 1] in the bounded range. Therefore, the universe 1 can still be vector of all ones (in the entity space 11 and negation is 1 q- ENNSSy (Xu et al., 2022) defines the universe as the uniform distribution over the entity space with each clement weighting jεl 2 (a is hyperparameter). CQDA (Arakelyan et al., 2023) employs a strict cosine fuzzy negation _ + cos(zT)) over scalar scores q. More exotic processors (Lin et al., 2022; 2023) employ feature logic for modeling negation. We also note that the difference operator introduced in Liu et al. (2021) is in fact a common interscctionnnegation (2in) query pattern used in all standard benchmarks (Section 7).
Kleene Plus (+) and Property Paths. Kleene Plus is an operator that applies compositionally and recursively to any regular expression (RegEx) that denotes one or more occurrence of the specified pattern. Regular expressions exhibit direct connection to property paths in SPARQI. We defined a very basic regular graph query in Definition A.7, here we generalize that further to property paths. To define property paths more formally, given set of relations R. and operators 2,,,,,,,,,,11 a property path can be obtained from the recursive grammar p ::= r 11ppp p" p? 'p Ø P1/P2 | "Pilp2" Here, r is any element of R, + is a Kloene Plus denoting one or more occurrences, * is a Kleene Star denoting zero or more occurrences, ? denotes zero or one occurences, ! denotes negation of the relation or path, á traverses an edge of type p in the opposite direction, P1 //2 a sequence of relations (corresponds to relation projection), and pi pilp2 denotes an alternative path of p1 or p2 (corresponds to union operation). For example (Fig. 14), an expression with Kleene plus knows( JohnDoe, V)+ can be represented as SPARQL property path [JohnDoe knows+ ?v.).
Property paths are non-trivial to model for neural query processors due to compositionalilty and recursive nature. To the best of our knowledge, RotatE-Box (Adlakha et al., 2021) is the only geometric processor that handles the Kleene Plus operator implementing the subset of operators {+./. RotatE-Box provides two ways to handle Kleene Plus. The first method is to define a r+ embedding for each relation r E R. note this is independent and separate from the regular relation embedding for r; another way is to use a trainable matrix to transform the relation embedding r to the r+ embedding. Note the two methods do not support Kleene Plus over paths. RotatE-Boo Box also implements relation projection (as rotation in the complex space) and union (with DeepSets or DNF) but does not support the intersection operator.
We hypothesize that better support of the property paths vocabulary might be one of main focuses in future neural query processors. Particularly for Kleene Plus, some unresolved issues include supporting idempotence ((++)+ = =+) and infinite union of sets (r+ = (r(r/r)(r/r//))..
Filter. Filter is an operation that can be inserted in a SPARQL query. It takes any expression of boolean type input and aims to filter the results based on the boolean value, i.e., only the results rendered True
30

---

Published in Transactions on Machine Learning Research (11/2024)
SPARQL Basic
SELECT COUNT (?book) as ?n
Stephenking wrote ?book. ?book numPages ?pages FILTER ?pages > 100.
King wrote ?book. OPTIONAL [King award ?a.
Graph Pattern
StephenKing wrote ?book.
Aggregations (COUNT)
Optional (LEFT JOIN)
FILTER
wrote
K
?b
Computation Graph
wrote
pages
wrote
Pred
S
?b
Pp
S
?b
?n
award
>10!?
Optional
Figure 15: Query operators (Filter, Count Aggregation, Optional), corresponding SPARQL basic graph patterns (BGP), and their computation graphs.
under the expression will be returned. The boolean expression thus be seen as condition that the answers to the query should follow. For the filter operator, we can do filter on values/literalss /lliteaas/attriiuttttt /ttrrbbutsts e.g., Filter(Vaate 2 "2000 01 - 01 & < "2000 - 12 - -11)) means we would like to filter dates not in the year 2000; Filter (LAtGrLLAAV(Vbuukk = "en") means we would like to filter books not written in English, Filter(?pages 100) means returning the books that have more than 100 pages (as illustrated in Fig. 15). To the best of our knowledge, there does not exist a reasoning model that claims handle all possible Filters, which leaves room for future work this direction. However, the first attempt towards handling filters is taken by LitCQD (Demir et al., 2023) that allows greater than, less than, and equal filtering operators over numerical values and treats them as conjunctive termss to the main logical query, e.g., W Ppages, 100). Such terms are processed by jointly trained regression model.
We envision several possibilitics to support filtering in neural query engines: (1) the simplest option used by Thorne et al. (2021a:b) in natural language engines to defer filtering to the postprocessing stage when the set of candidate nodes is identified and their attributes can be extracted by a lookup. (2) Filtering often implics reasoning over literal values and numerical node attributes, that is, processors supporting continuous values (as described in Section 4.1) might be able to perform filtering in the latent space by attaching, for instance, a parametric regressor decoder (Section 5.3) when predicting ?pages > 100.
A Aggregation. Aggregation is a set operators SPARQL queries including COUNT (return the number of elements), MIN, MAX, SUM, AVG (return the minimum / maximum sum average value of all elements), SAMPLE (return any sample from the set). For example (Fig. 15), given triple pattern (StephenKing wrote ?book. }, the clause COUNT (?book) as ?n returns the total number of books written by StephenKing.
Most aggregation operators require reasoning over sets of numerical values/literall Such symbolic operations have long been considered a challenge for neural models (Hendrycks et al., 2021). How to design a better representation for numerical values / literals requires remains an open question. Some neural query proces- sors (Ren et al., 2020; Ren & Leskovee, 2020; Zhang et al., 2021b; Zhu al., 2022), however, have the means to estimate the cardinality of the answer set (including predicted hard answers) that directly corresponds to the COUNT aggregation over the target projected variable (assumed to be an entity, not literal). For example, GNN-QE (Zhu et al., 2022) returns a fuzzy set, i.e., scalar likelihood value for each entity, that, after thresholding, has low mean absolute percentage error (MAPE) of the number of ground truth answers. Answer cardinality estimatioo is thus obtained as a byproduct of the neural query processor without tailored predictors. Alternatively, when models cannot predict the exact count, Spearman's rank correlation is a surrogate metric to evaluate the correlation between model predictions and the exact count. Spearman's 's rank correlation and MAPE of the nunber of ground truth answers are common metrics to evaluate the performance of neural query processors and we elaborate on the metrics in Section 7.5. LitCQD (Demir
31

---

Published in Transactions on Machine Learning Research (11/2024)
S
rocmsnalt
student
S
U
S
Stanford
S
stadent
dlasmmate
diassmate
mommatte
roomnaats
Path Queries
Tree-like Queries
DAG Queries
Cyclic Queries
Figure 16: Query patterns: path, treo-like, DAG, and cyclic queries. A DAG query has two branches from the intermediate variable, a cyclic query contains 3-cycle. Existing neural query processors suppori path and tree-like patterns.
et al., 2023) extends the answer set to numerical literals and by default implements the AVG aggregation of predicted values when query has multiple correct target entities. The target metrics are typical regression metrics like mean absolute error (MAE) or mean squared error (MSE).
Optional and Solution Modifiers. SPARQL offers many features yet to be incorporated into neural query engines to extend their expressiveness. Some of those common features include the OPTIONAL clause that essentially a LEFT JOIN operator. For example (Fig. 15), given a triple pattern {King wrote ?book.} that returns books, the optional clause [King wrote ?book. OPTIONAL [King award ?a.}} enriches the answer set with any existing awards received by King. Importantly, if there are no bindings the optional clause, the query still returns the values of ?book. In the query's computation graph, the optional clause corresponds to the optional branch of a relation projection. A particular challenge for neural query processors operating on incomplete graphs is that the absence of the queried edge in the graph does not mean that there are no bindings instead, the edge might be missing and might be predicted during query processing,
Solution modifiers, e.g., GROUP BY, ORDER BY, LIMIT, apply further postprocessing of projected (returned) results and are particularly important when projecting several variables the query. So far, all existing neural query processors are tailored for only one return variable. We elaborate on this matter Section 6.3.
General Note on Incompleteness. Finally, we would like stress out that neural query engines performing all the described operators (Projection, Intersection, Union, Negation, Property Paths, Filters, Aggregations, Optionals, and Modifiers) assunne the underlying graph incomplete and queries might have some missing answers to be predicted, hence, all the operators should incorporate predicted hard answers in addition to easy answers reachable by graph traversal as in symbolic graph databases. Evaluation of query performance with those operators in light of incompleteness is still an open challenge (we elaborate on that in Section 7.5), e.g., having an Optional clause, it might be unclear when there no true answer (even predicted ones are in fact false) or a model is not able to predict them.
6.2 Query Patterns
Here, introduce several types of query patterns commonly used in practical tasks and sort them in the increasing order of complexity. Starting with chain-like Path queries known in the literature for years, we move to Tree-Struclured queries (the main supported pattern in modern CL.QA systems). Then, we overview DAG and cyclic patterns which currently are not supported by any neural query answering system and represent a solid avenue for future work.
Path Queries. As introduced in Section A.3, previous literature starts with path queries (aka multi-hop queries), where the goal is simply to go beyond one-hop queries such as = Vyr((, Vy), where r E R, v E V and Vi2 represents the answer variable. As shown in Fig. 22 and Fig. 16, there is no logical operator such as branch intersoction or union involved. Therefore, order answer such a query, we simply find or infer the neighbors of the entity with relation r. Path queries are a natural extension of one-hop queries. Formally, denote path query as follows. Jpach- V. Vk-1 : ri (v, Vr) V2) Arrerr V)), where
32

---

Published in Transactions on Machine Learning Research (11/2024)
B
sttadent
rocmsnals
F
S
S
stadent
clasamate
dlassmate
mommmtte
roormnaae
D
Answers:
AE
A
Answers:
A
Answers:
D
Figure 17: Answers to example tree-like, DAG, and cyclic query patterns given toy graph. Note the difference in the answer set lo the tree-like and DAG queries in the DAG query, variable must have two outgoing edges from the same node.
Ty E E. E [1, u E V, V, are all existentially quantified variables. We denote a k-hop path query it has A atomic formulas. The query plan of a k-hop path query is chain of length & starting from the anchor entity. For example (Fig. 16), 2-hop path query is V.. student(Stanford, v) A roommate(u, Vt) where Stanford is the starting anchor node, is tail variable of the first projection student and at the same time is the head variable of the second projection roommate thus forming a chain.
As shown in the definition, in order to handle path queries, it is necessary to develop a method to handle existential quantification 3 and conjunction A operators. Several query reasoning methods (Guu et al., 2015; Das el al.; 2017) aim to answer the path queries with sequence models using either chainable KG embeddings (e.g., TransE) in Guu et al. (2015) or LSTM in Das et al. (2017). These methods initiated one of the first efforts that use embeddings and neural methods to answer multi-hop path queries. We acknowledge the efforts in this domain but emphasize their limitations in terms of query expressiveness and, therefore, focus our attention in this work on more expressive query answering methods that operate on tree- like and more complex patterns.
Queries. Path queries only have one anchor entity and one answer variable. Such queries have limited expressiveness and are far away from real-world query complexity seen in the logs (Maly- shev al., 2018) of real-world KGs like Wikidata. One direct extension increase the expressiveness and complexity is to support tree-structured (tree-like) queries. Tree-like queries may have multiple anchor enti- ties, and different branches (from different anchors) will merge at the final single answer node, thus forming tree structured query plan. Such merge can be achieved by intersection, union, or negation operators. For example, as shown in Fig. 1, the query plan of AL what universities do the Turing Award winners in the field of Deep Learning work?" is not a path but a tree. Alternatively, the example in Fig. 16 depicts a query v1) A roommate(vi, Vv) A studend(Stanfonn 02) A classmate(v2. V4) that
= 1/, Ju, U2 : Srudeet(Stanfoor consists of two branches of 2-hop path queries joined by the intersection operator at the end.
Treo-like queries pose more challenges to the previous models that are only able to handle path (multi-hop) queries since a sequence model no longer applies to tree-structured execution plans with logical operators. In light of the challenges, neural and neuro-symbolic query processors (described in Section 5) are designed to execute more complex query patterns. These processors design neural set /logi operators and do bottom-up traversal of the tree up to the single root node.
Arbitrary DAGs. Based on tree-structured queries, one can further increase the complexity of the query pattern to arbitrary directed acyelic graphs (DAGs). The key difference between the two types of queries is that for DAG-structured queries, variable node in the query plan (that represents set of enti- ties) may be split and routed to different reasoning paths, while the number of branches/ seaaches/reasoning paths in the query plan always decreases from the anchor nodes to the answer node. We show one example in Fig. 16 and in Fig. 17. Consider the (ree-like query from the previous paragraph 91 = VG, 22,30, 02 student(Stanforr e1) A roommate(v1, 14) A student(Stann Stanford, U2) A classmate(vz, V/) and the DAG query l = Vg, Ev student(Stanford, v) roommate(v. Vz) A classmate(v, Vz). The two queries search for V,, who are roommate and classmate with Stanford students. However, the answer sets of the two queries are differ- ent. (illustrated in Fig. 17). That is, the answer to the DAG query Vn (A} is the subset. of the answers to
33

---

Published in Transactions on Machine Learning Research (11/2024)
the tree-like query Vy = (A,E) because the answers to 92 have to be both roommate and classmate with the same Stanford student in the intermediate variable v. On the other hand, the two branches of the tree-like query Q1 are independent such that intermediate variables ei and need not be the same entities, hence, the query has more valid intermodiate answers and more correct answers. To the best of our knowledge, there still does not exist a neural query processor that can faithfully handle any DAG query. Although BiQE (Kot- nis et al., 2021) claims to support DAG queries, the mined dataset consists of tree-like queries. FIT (Yin et al., 2023b) processes DAG queries by rewriting and decomposing the query into fragments executable by CQD-like inference mechanism. Nevertheless, we hypothesize that, potentially, processors with message passing or Transformer architectures that consider the entire query graph structure Gg may be capable of handling DAG queries and leave this question for future work.
Cyclic Queries. Cyclic queries are more complex than DAG-structured queries. A cycle in query naturally entails no particular order to traverse the query plan. An example of the cyclic query is illustrated in Fig. 16 and Fig. 17: roommate(U2, v3) A roommate(vs, v1) A classmate(vi, V2). In 9, three variables form a triangle cycle roommate(11 U1, U2) A roommate(1>, 1yy) A roommate(vs, U3 Vt). Given a graph in Fig. 17, the cycle starts and ends node C, hence the only correct answer is obtained after performing the classmate relation projection from ending in D, V0, (D).
= J0,, U2, student[Stanford, U1) A roommate(v1, v2) ) A
Reasoning methods and query processors that assume particular traversal or node ordering the query plan, therefore, cannot faithfully answer cyelic queries. Yin et al. (2023b) attempt to answer cyclic queries by cutting query edges according to pre-defined decomposition rules. UnRavL (Cucumides et al., 2024) approximales cyclic queries by a set of tree-like queries with some theoretical guarantees.) It remains an open question how to effectively model a query with cyclic structures. Moreover, cyclic structures often appear when processing queries with regular expressions and property paths (Section 6.1). We posit that supporting cycles might be a necessary condition to fully enable property paths in neural query engines.
6.3 Projected Variables
By projected variables we understand target query variables that have to be bound to particular graph elements such as entity, relation, or literals. For example, query in Fig. 1 q = V4.3v win(TuringAward, A feld(DeepLe v) A university(e, V3) has one projected variable V/2 that can be bound to three answer nodes in the graph, Vi- = (UofT, UdeM, NYU). In the SPARQT. literature (Hawke et al., 2013), the SELECT query specifies which existentially quantified variables to project as final answers. The pairs of projected variables and answers form bindings as the result of the SELECT query. Generally, queries might have zero, one, or multiple projected variables, and we align our categorization with this notion. Examples of such queries and their possible answers are provided in Fig. 18. Currently, most neural query processors focus the setting where queries have only one answer variable the leaf node of the computation graph, as shown in Fig. 18 (center).
Zero Projected Variables. Queries with zero projected variables (Boolean queries) do not return any bindings but rather probe the graph on the presence of certain subgraph relational pattern where the answer is Boolcan True or False. In SPARQL, the equivalent of zoro-variable queries is the ASK clause. Zero-variable queries might have all entities and relations instantiated with constants, e.g., = student(S, D) A roommate(D, E) as in Fig. 18 (left) is equivalent to the SPARQL query ASK WHERE {s student D. D roommate E.}. The query probes whether a graph contains a particular subgraph (path) induced by the constants. Such a path exists, so the answer is q = (True).
Alternatively, zero-variable queries might have existentially quantified variables that are never projected (up to the cases where all subjects, predicates, or objects are variables). For example, query 41 = Bu,, U2 03 student,
student(e), 02) A roommate(1y) Uz) probes whether there exist any nodes forming a relational path ej U2 roommate, U3. In a general case, a query Q2 = 3p, s, o: p(s, o) asks a graph contains at least one edge.
We note that in the main considered setting with incomplete graphs and missing edges vorovvariable queries are still non-trivial to answer. Particularly, subfield of neural subgraph matching (Rex et al., 2020; Huang
34

---

Published in Transactions on Machine Learning Research (11/2024)
ASK WHERE 1 student roommate
SELECT DISTINCT 2V WHERE {
SELECT 2v1 ?v2 2v WHERE
Stanford ?v1 Stanford 2v2
student
Stanford
student
roommate
Pv
?v1
roommate
PV
}
student
7v2
Stanford
student
vv2
classmate
?V
?v2
classmate
?V
D
?v1
?v2
Projected variables: 0
Projected variables: 1
?v
Projected variables:
F
Tzue
A
C
F
E
D
F
Figure 18: Projected variables of the tree-like query from Fig. 17. Current neural query processors support the single-variable DISTINCT mode (center) whereas queries might have zero return variables akin to a subgraph matching Boolean ASK query (left) or multiple projected variables (right) that imply returning intermediate answers and form output tuples.
et al., 2022a) implies having incomplete graphs. We hypothesize such approaches might be found useful for neural query processors to support answering zero-variable queries.
One Projected Variable. Queries with one projected variable return bindings for one (of possibly many) existentially quantified variable. In SPARQL, the projected variable is specified in the SELECT clause, e.g., SELECT DISTINCT ?v in Fig. 18 (center). Although SPARQL allows projecting variables from any part of a query, most neural query engines covered in Section follow the task formulation of GQE' (Hamilton et al,, 2018) and allow the projected target variable to be only the Icaf node of the query computation graph. This limitation is illustrated in Fig. 18 (center) where the target variable Po is the leaf node of the query graph and has two bindings = (A,
It is worth noting that existing neural query processors are designed to return a unique set of answers to the input query, f.c., it corresponds to the SELECT DISTINCT clause in SPARQL. In contrast, the default SELECT returns mulliisets with possible duplicates. For example, the same query Fig. 18 (center) without DISTINCT would have bindings v (A, A, E} as there exist two matching graph patterns ending in A. Implementing non-DISTINCT query answering remains open challenge.
Most neural query processors have notion of intermediate variables and model their distribution in the entity space. For instance, having a defined distance function, geometric processors (Ren et al., 2020; Choudhary et al., 2021b) can find nearest. entities as intermediate variables. Similarly, fuzzy-logie processors operating on fuzzy sets (Tang et al., 2022; Zhu et al., 2022) already maintain a scalar distribution over all entities after each execution step. Finally, GNN-basod (Daza & Cochez, 2020; Alivanistos et al., 2022) and Transformer- based (Liu et al., 2022) processors explicitly include intermediate variables as nodes in the query graph (or tokens in the query sequence) and can therefore decode their representations to the entity space. The main drawback of all those methods is the lack of filtering mechanisms for the sets of intermediate variables after the leaf node has been identified. That is, in order to filter and project only those intermediate variables that lead to the final answer, some notion of backward pass is required. The first step in this direction is taken by QTO (Bai et al., 2023c) that runs the pruning backward pass after reaching the answer leaf node.
have multiple projected variables as illustrated in Fig. 18 (right). In SPARQL, all projected variables are specified the SELECT clause (with the possibility to project all variables in the query via SELECT +). In the logical form, query has several target variables q =?v,, ?ug ?v student(Stanford, 7o,) A roommate(?es. ?v) A student(Stanford, ?02) A classmate(?ez ?v) such that the output bindings are organized in tuples. For ex- ample, one possible answer tuple is {?oz F, ?o2 F, u.: A} denotes particular nodes (variable bindings) that satisfy the query pattern.
Multiple Projected Variables. The most general and complex case for queries
As shown in the previous paragraph about onc-variable queries, some neural query processors have the means to keep track of the intermediate variables. However, none of them have the means to construct answer tuples with variables bindings and it remains an open challenge how to incorporate multiple projected variables
35

---

Published in Transactions on Machine Learning Research (11/2024)
O+O O+O+O O+O+O+
O+O
1p
2p
3p
2i
3i
O
ip
pi
2u
up
O+O n
2in
3in inp
pni
pin
Figure 19: Standard query pallerns with names, where p is projection, i is intersection, is union, is negation. In a pattern, blue node represents a non-variable entity, grey node represents variable node, and the green node represents the answer node. In a typical training protocol, models are trained on 10 patterns (first and third rows) and evaluated on patterns. In the hardest generalization case, models are only trained on 1p queries. Some datasets further modify the patterns with additional features like qualifiers or temporal timestamps.
into such processors. Furthermore, some common caveats to be taken into account include (1) dealing with unbound variables that often emerge, for example, in OPTIONAL queries covered in Section 6.1, where answer tuples might contain empty value (6 NULL) for some variables; (2) the growing complexity issuc where the answer set might potentially be polynomially large depending on the number of projected variables.
7 Datasets and Metrics
7.1 Evaluation Setup
Multiple datasets have been proposed for evaluation of query reasoning models. Here we introduce the common setup for CLQA task. Given a knowledge graph g (E, S), the standard practice to split G into a training graph Itrains validation graph 9vat and test graph Itest (simulating the unobserved complete graph & from Section 2). The standard experiment protocol is train a query reasoning model only on the training graph Gtrain: and evaluate the model answering queries over the validation graph Goal and the test graph Grest. Given query q. denote the answers of this query training, validation and test graph as [q] Iglersin: 19]va1 and [glttst. During evaluation, queries may have missing answers, e.g. a validation query may have answers [[] that are not in [y]eraan, a lest query q may have answers [gl test that are not in [g]var. The overall goal of CLQA task is to find these missing answers. The details of typical training queries, training protocol, inference and evaluation metrics are introduced Section 7.2, Section 7.3, Section 7.4, and Section 7.5, respectively.
7.2 Query Types
The standard set of graph queries used in many datasets includes 14 types: hp/2p/3p/2i/ http:/pppp///p/////e///
inp/pni/pin where denotes relation projection, i is intersec- tion, u is union, n is negation, and a number denotes the number of hops for projection queries or number of branches to be merged by a logical operator. Fig. 19 illustrates common query patterns. For example, 3p is chain-like query of three consecutive relation projections, is an intersection of two relation projections, Sin an intersection of three relation projections where one of the branches contains negation, up union of two relation projections followed by another projection. The original GQE by Hamilton al. (2018)
36

---

Published in Transactions on Machine Learning Research (11/2024)
introduced 7 query patterns with projection and intersection 1p/2p/ h01pp/pp////p httpp///////////////// Query2Box (Ren et al., 2020) added union queries 2u/up, and BetaF. (Ren & Teskovec, 2020) added five types with negation.
Subsequent works modified the standard set of query types in several ways, e.g., hyper-relational queries (Ali- vanistos et al., 2022; Luo et al., 2023) with entity-relation qualifiers on relation projections, or temporal op- erators on edges (Lin et al., 2023). New query patterns include queries with regular expressions of relations (property paths) (Adlakha al., 2021), more tiee-like queries (Kotuis et al., 2021), and more combinations of projections, intersections, and unions (Wang et al., 2021; Pftueger et al., 2022). We summarize existing query answering datasets and their properties in Table 14 covering supported query operators, inference setups, and additional features like temporal timestamps, class hicrarchies, or complex ontological axioms.
Commonly, query datasets are sampled from different KGs to study model performance under different graph distributions, for example, BetaE datasets include sets of queries from denser Freebase (Bollacker et al., 2008) with average node degree of 18 and sparser WordNet (Miller, 1998) and NELL (Mitchell et al., 2015) with average node degree of 2. Hyper-relational datasets WD50K (Alivanistos el al., 2022) and WD50K- NFOL (Luo et al., 2023) were sampled from Wikidata (Vrandecic & Krötzsch, 2014) where qualifiers are natural. TAR datasets with class hierarchy (Tang et al., 2022) were sampled from YAGO 4 (Pellissier Tanon et al., 2020) and DBpedia (Lehmann et al., 2015) where class hicrarchies are well-curated. Q2B Onto datasets with ontological axioms (Andresel et al., 2021) were sampled from LUBM (Guo et al., 2005) and NELL. Temporal TFLEX datasets (Lin et al., 2023) were sampled from ICEWS (Boschee et al., 2015) and GDELT (Leetaru & Schrodt, 2013) that maintain event information. InductiveQE datasets (Galkin et al., 2022b) were sampled from Freebase and Wikidata, while inductive GNNQ datasets (Pflueger et al., 2022) were sampled from the WatDiv benchmark (Alug et al., 2014) and Freebasc.
7.3 Training
Query reasoning methods are trained on the given Grnain with different objectives/losse and dif- ferent datascts. Following the standard protocol, methods are trained 10 query patterns 1p/2p ht//pp//// //i//ii//i///ee/// tiipppp//piinnn and evaluated on all 14 patterns including generalization to unseen he/pi//e ////////// /up patterns. That is, the training protocol assumes that models trained on atomic logical opera- tors would learn to compositionally generalize to patterns using several operators such as ip and pi queries that use both intersection and projection.
We summarize different training objectives in Table 13. Most methods that learn a representation of the queries and entities on the graph optimize a contrastive loss, i.e., minimizing the distance between the representation of query q and its positive answers while maximizing that between the representation of query and negative answers e'. Various objectives include: (1) max-margin loss (first column in Table 13) with the goal that the distance of negative answers should be larger than that of positive answers at least by the margin y. Such loss is often of the form as the equation below.
f= max ( dist(q. e) + dist(q.e')):
(2) LogSigmoid loss (sccond column in Table 13) with a similar goal that pushes the distance of negatives up and vice versa. Often the loss also includes margin term and the gradient will gradually decrease when the margin is satisfied.
i -=-logo(e -c--ooory-distqq.ee - -
1 log
log o (dist(q, e¹) - 7),
where t is the number of negative answers. Other methods (third column in Table 13) that directly model logit vector over all the nodes the graph may optimize cross entropy loss instead of a contrastive loss. Besides, methods such as the two variants of CQD (Arakelyan et al., 2021; 2023), QTO (Bai et al., 2023c), FIT (Yin et al., 2023b), and LitCQD (Demir et al., 2023) only optimize the link prediction loss since they do not learn a representation of the query.
Almost all the datasets including GQE (Hamilton et al., 2018), Q2B (Ren et al., 2020), BetaE (Ren & Leskovec, 2020), RegEx (Adlakha et al., 2021), BiQE (Kotnis et al., 2021), Query2Onto (Andresel et al., 2021), TAR (Tang et al., 2022), StarQE (Alivanistos et al., 2022), GNNQ (Pflueger et al., 2022), TeMP (Hu
37

---

Published in Transactions on Machine Learning Research (11/2024)
Table 13: Complex Query Answering approaches categorized under Loss.
Max Margin
LogSigmoid (Sun et al., 2019)
Cross Entropy
GQE (Hamilton et al.,
Query2Box (Ren al,, 2020), BetaE (Ren & Leskovec,
BiQE (Kotnis et al,, 2021), NodePiecc-(uP) (Galkin al.,
2018), GQE hash (Wang al., 2019), CGA (Mai al,, 2019), MPQE (Daza & Cochez, 2020), HyPE (Choudhary et al., 2021b),
2020), RotatE-Box (Adlakha al., 2021), ConE (Zhang et al., 2021b), NewLook (Liu el al., 2021), Q2B Onto (Andresel et al., 2021), PERM (Choudhary et al., 2021a), LogicE (Luus et al., 2021), MLPMix (Amayue- et al., 2022), FuzzQE (Chen al., 2022), FLEX (Lin al., 2022), TFLEX (I.in al., 2023), SMORE (Ren et al., 2022), LinE (Huang et al., 2022b), Gam maE (Yang al,, 2022a), NMP- NMP-QEM (Long al., 2022), ENeSy (Xu al., 2022), RoMA el al., 2022), SignalE (Wang al., 2022), Query2Geom (Sardina et al., 2023), RoConE (Ile et al., 2023), CylE (Nguyen et al, 2023b), WFRE (Wang et al., 2023d)
2022b), GNN-QE (Zhu et al.,
2022), GNNQ (Pflueger al.
2022), KGTrans (Liu al., 2022),
Query2Particles (Bai et al,, 2022),
Shv (Gehhart al., 2023)
EmQT. (Sun at 2020), LMPNN (Wang et al., 2023e), StarQE (Ali- vanistos al., 2022), NQE (Luo
et al,, 2023). CQDA (Arakelyan et al,, 2023), SQE (Bai al., 2023b)
al., 2022), TFLEX (Lin al., 2023), InductiveQE (Galkin al., 2022b), SQE (Bai et al., 2023b) provide set of training queries of given structures sampled from the Gtrain The benefit is that during training, methods do not need to sample queries online. However, it often means that only portion of information is utilized from the Gvain since exponentially more multi-hop queries exist on Gvaan and the dataset can never pre-generate all offline. SMORE (Ren et al., 2022) proposes bidirectional online query sampler such that methods can directly do online sampling efficiently without the need to pre-generate training set offline. Alternatively, methods that do not have parameterized ways to handle logical operations, e.g. CQD (Arakelyan et al., 2021), only require one-hop edges to train the overall system.
7.4 Inference
Training and Inference Graph
Inference
Training
Inference
Training
Transductive
Inductive (superset)
known link
Inductive (disjoint)
missing link
Figure 20: Inference Scenarios. In the Transduclive case, training and inference graphs the same and share the same nodes (Ein Esrain) Inductive cases be split into superset (or semi-inductive) where the inference graph extends the training one (Erain C Einf missing links cover both seen and unseen nodes) and disjoint (or hully-inductivr where the inference graph is disconnected (Etrain O Einf = 0, missing links are among unseen nodes).
By Inference we understand testing secnarios on which trained query answering model will be deployed and evaluated. Following the literature, we distinguish Tronsductive and Inductive inference (Fig. 20). In the transductive case, inference is performed on the graph with the same set of nodes and relation types as in training but with different edges. Any other scenario when either the number of nodes or relation types of an inference graph different from that of the training is deemed inductive. The inference scenario plays major role in designing query answering models, that is, transductive models learn shallow entity
38

---

Published in Transactions on Machine Learning Research (11/2024)
Table 14: Existing logical query answering datasets classified along supported query operators, inference
scenarios, and domain propertics. + is partial support some operators on literals can be treated as filters.
Query Operators
Inference
Domain
Conjunctive
Kleene Plus
Filter + Agg
Transductive
+ Timestamps
Contimous
Negation
Inductive
Discrete
Qualifiers
Union
Types
Rules
Source
Dataset
Hamilton et al. (2018)
GQE datasets
Ren et al. (2020)
Q2B datasets
Ren & Leskovee (2020)
BetaE datasets
Adlakha et al. (2021)
Regex queries
Kotnis et al. (2021)
DAG queries
Wang al. (2021)
EFO-1 queries
Andresel et al. (2021)
LUBM/NELL (type)
Tang et al. (2022)
TAR datasets
Ren al. (2022)
SMORE datasets
Alivanistos et al. (2022)
WD50K dataset
Iu al. (2022)
TeMP dataset
Pflueger et al. (2022)
GNNQ dataset
Lin et al. (2023)
TFLEX dataset
Galkin et al. (2022b)
InductiveQE dataset
Luo et al. (2023)
WD50K-NFOL dataset
Bai et al. (2023b)
SQE dataset
Huang al. (2022b)
WN1SRR dataset
Demir et al. (2023)
FB15k237 w/ literals
Yin et al. (2023b)
FIT dataset (w/ cycles)
Bai et al. (2023a)
NRN datasets
Cucumides et al. (2024)
Test set w/ cycles
Yin et al. (2023a)
EFO₂ dataset
Galkin et al. (2024)
CLQA dataset
embedding matrix thanks to the fixed entity set whereas inductive models have to rely on other invariances available the underlying graph order to generalize unseen entity entity/relatin /relation lypes. We discuss many transductive and inductive models Scction 5.2. Below, we categorize existing datasets from the Inference perspective. The overview of existing CLQA datasets presented in Table 14 through the lens of supported query operators, inference scenario, graph domain, and other features like types qualifiers.
Transductive Inference. Formally, given a training graph Gtrain = (Etrain: Rerains Strain); the transductive inference graph Giy contains the same set entities and relation types, that is, Etroin = Einy and Riroi = Ring while the edge set on Gervin is a subset of that on the inference graph Gensi i.e., Struin C S In this setup, query answering is performed on the same nodes and edges seen during training. From the entity set perspective, the prediction patlern is seen-lo-seen missing links are predicted between known entities.
Traditionally, KG link prediction focused more the transductive task. In CLQA, therefore, the majority of existing datasets (Table 14) follow the transductive scenario. Starting from simple trile-based graphs with fixed query patterns in GQE datasets (Hamilton et al., 2018), Query2Box datasets (Ren et al., 2020), and BetaE datasets (Ren & Leskovec, 2020) that became de-facto standard benchmarks for query answering approaches, newer datasets include regex queries (Adlakha et al., 2021), wider set of query patterns (Kotnis et al., 2021; Wang al., 2021: Bai al., 2023b), entity type information (Tang et al., 2022), ontological axioms (Andresel et al., 2021), hyper-relational queries with qualifiers (Alivanistos 2023), temporal queries (Lin et al., 2023), very large graphs up to 100M nodes (Ren et al., 2022), hierarchical
al., 2022; Luo et al.,
6 Below use Gof refer to the graphs we during inference, can Good or Grest without loss generalization.
39

---

Published in Transactions on Machine Learning Research (11/2024)
graphs (Huang et al., 2022b), queries with numerical literals (Demir et al., 2023; Bai et al., 2023a), or queries with cycles and multiedges (Yin et al., 2023b;a; Cucumides et al., 2024).
Inductive Inference. Formally, given a training graph Gvesn (Etrain, Reruin Strai)), the inductive infer- ence graph Ginz = (Einf, Rinf, Sinf) is different. from the training graph in either the entity set or the relation set or both. The nature of this difference explains several subtypes of inductive inference. First, the set of relations might or might not be shared at inference time, that is, Rinf S Rtrain or (Reny) \ Reraia > 0. Most of the literature on inductive link prediction (Teru et al., 2020; Zhu et al., 2021; Galkin et al., 2022a) in KGs assumes the set of relations is shared whereas the setup where new relations appear at inference time is still highly non-trivial (Huang et al., 2022a; Gao et al., 2023; Chen et al., 2023).
On the other hand, the inference graph might be either a superset of the training graph after adding new nodes and edges, Etrain E &in,, or disjoint graph with completely new entities as disconnected component, Eng Etrain = 0 as illustrated in Fig. 20. From the node set perspective, the superset inductive inference case might contain both unseen-to-sed teeen and unseen-tor to--tt--uusss unsenn missing links whereas in the disjoint inference graph only teree-to-uuseen links are naturally appearing.
In CLQA, inductive reasoning is still an emerging area as it has a direct impact on the space of possible variables V, constants C, and answers A that might now include entities unseen at training time. Several most recent works started to explore inductive query answering (Table 14). InductiveQE datasets (Galkin et al., 2022b) focus on the inductive superset case where a training graph can be extended with up to 500% new unseen nodes. Test queries start from unseen constants and answering therefore requires reasoning over both seen and unseen nodes. Similarly, training queries can have many new correct answers when answered against the extended inference graph. GNNQ datasets (Pflueger et al., 2022) focus on the disjoint inductive inference case where constants, variables, and answers all belong to a new entity set. TeMP datasets (Hu et al., 2022) focus on the disjoint inductive inference as well but offer to leverage an additional class hierarchy as a learnable invariant. That is, the set of classes at training and inference time does not change. The only suite of datasets for fully-inductive inference on both unseen entities and relations was introduced in UltraQuery (Galkin et al., 2024).
Inductive inference is crucial to enable running models over updatable graphs without retraining. We con- jecture that inductive datasets and models are likely to be the major contribution area in the future work.
7.5 Metrics
Several metrics have been proposed to evaluate the performance of query reasoning models that can be broadly classified into generalization, entailment, and query representation quality metrics.
Generalization Metrics. Since the aim of query reasoning models to perform reasoning over massive incomplete graphs, most metrics are designed to evaluate models' gencralization capabilities in discovering missing answers, i.e., Iq]keet Vallva for given test query q. As one of the first works in the field, GQE (Hamil- ton et al., 2018) proposes ROC-AUC and average percentile rank (APR). The idea is that for given test VggI query q, GQE calculates a score for all its missing answers e E \ and the negatives e' & [9] Leat. The model's performance is the ROC-AUC score and APR, where they rank a missing answer against at most 1000 randomly sampled negatives of the same entity type. Besides GQE, GQE+hhshing (Wang et al., 2019), CGA (Mai et al., 2019) and TractOR (Friedman & Van den Brocck, 2020) use the same cvaluation metrics.
However, the above metrics do not reflect the real world setting where we often have orders of magnitude more negatives than the missing answers. Instead of ROC-AUC or APR, Query2Box (Ren et al., 2020) proposes ranking-basee based metrics, such as mean reciprocal rank (MRR) and hits@k. Given a test query q, for each missing answer e E [q] \gl we rank it against all the other negatives e' & [4] test. Given the ranking r, MRR is calculated as y and hits@k 1/r < k:). This has been the most used metrics for the task. Note that the final rankings are computed only for the hard answers that require predicting at least one missing link. Rankings for easy answers reachable by edge traversal are usually discarded.
40

---

Published in Transactions on Machine Learning Research (11/2024)
Representation Quality Metrics. Besides evaluating model's capability of finding missing answers, another aspect is to evaluate the quality of the learned query representation for all models. BetaF, (Ren & Leskovec, 2020) proposes to evaluate whether the learned query representation can model the cardinality of a query's answer set, and view this as a proxy of the quality of the query representation. For models with a sense of "volume" (e.g., differential entropy for Bela embeddings), the goal to measure the Spearman's 's rank correlation coefficient and Pearson's correlation coefficient between the "volume" of a query (calculatod from the query representation) and the cardinality of the answer set. BetaE also proposed to evaluate an ability to model queries without answers using ROC-AUC.
Entailment Metrics. The other evaluation protocol is about whether a model is also able to discover the existing answers, e.g. [0] for test queries, that does not require inferring missing links but focuses on memorizing the graph structure (easy answers in the common terminology). This is referred to as faithfulness (or enlailmend) in EmQL (Sun et al., 2020). Natural for database querying lasks, it is expected that query answering models first recover easy answers already existing in the graph (reachable by edge traversal) and then enrich the answer set with predicted hard answers inferred with link prodiction. A natural metric is therefore an ability to rank easy answers higher than hard answers - Chis was st uddied by InduetiveQE (Galkin et al., 2022b) that proposed to use ROC-AUC as the main metric for this task.
Still, we would argue that existing metrics might not fully capture the nature of neural query answering and new metries might be needed. For example, some under-explored but potentially useful metrics include (1) studying reasonable answers (in between easy and hard answers) that can be deduced by symbolic reasoners using higher-level graph schema (ontology) (Andresel et al., 2021). A caveat in computing reasonable answers is a potentially infinite processing time of symbolic reasoners that have to be limited by time or expressiveness in order to complete in a finite time. Hence, the set of reasonable answers might still be incomplete; (2) evaluation in light of the open-world assumption (OWA) stating that unknown triples in the graph might not necessarily be false (as postulated by the standard closeal-world assumplion used a lot in link prediction). Practically, OWA means that even the test set might be incomplete and some high- rank predictions deemed incorrect by the test set might in fact be correct in the (possibly unobservable) complete graph. Initial experiments of Yang et al. (2022b) with OWA evaluation of link prediction explain the saturation of ranking metrics (e.g., MRR) on common datasets by the performance of neural link predictors able to predict the answers from the complete graph missed in the test set. For example, saturated MRR of 0.4 on the test set might correspond to MRR of 0.9 on the true complete graph. Studying OWA evaluation in the query answering task in both transductive and inductive setups is a solid avenue for future work.
8 Applications
The framework of complex query answering is applied in a variety of graph-conditioned machine learning tasks. For example, SF--KG (Mai et al., 2020) applies GQF to answer geospatial queries conditioned on mu- merical {z, y} coordinates. The coordinates encoder fuses numerical representations with entity embeddings such that the prediction task is still entity ranking.
In case-based reasoning. CBR-SUBG (Das et al., 2022) is method for question answering over KGs based on subgraph extraction and encoding. As a byproduct, CBR-SUBG is capable of answering conjunctive queries with projections and intersections. However, due to a non-standard evaluation protocol and custom synthetic dataset, its performance cannot be directly compared to CT.QA models. Similarly, Wang et al. (2023b) merge a Query2Box-like model with a pre-trained language model to improve question answering performance. LEGO (Ren et al., 2021) also applies CLQA models for KG question answering. The idea is to simultaneously parse natural language question as query step and execute the step in the latent space with CLQQ models.
LogiRee (Wu et al., 2022) frames product recommendation as a complex logical query such that source products are root nodes, combinations of multiple products form intersections, and non-similar products to be filtered out form negations. LogiRee employs BetaE as query engine. Similarly, Syed et al. (2022) design an explainable recommender system based on Query2Box. Given a logical query, they first use Query2Box to generate set of candidates and rerank them using neural collaborate filtering (He et al., 2017).
41

---

Published in Transactions on Machine Learning Research (11/2024)
9 Summary and Future Opportunities
We proposed a deep and detailed review of Complex logical query answering (CLQA) methods based on the new laxonomy in Section 3 categorizing the existing approaches along three main areas: Graphs, Modeling, and Queries with their respective sub-areas. Going forward, there is still much room to unlock the full power of CLQA by addressing numerous open challenges. Adhering to the taxonomy, we summarize the challenges in three main areas: Graphs, Modeling, and Queries. Along the Graph branch:
Future systems need to handle a richer variety of graph structures and data types. For ex- ample, beyond conventional knowledge graphs that contain only triples of albject-pradecac-oojject we want to support hyper-relational graphs where edges can connect more than two nodes or have additional qualifiers. We also aim to include hypergraphs, which represent complex relationships with edges that join multiple entities simultaneously. In addition, we envision multimodal data sources where graph data is combined with textual descriptions, images, or other media. For in- stance, a system might. incorporate a knowledge graph of people and places along with associated images and text captions, integrating all these modalities seamlessly.
Modality:
Reasoning Domain:
Another goal is to facilitate logical reasoning and neural query answering over dynamic and continuous information within graphs. Many real-world knowledge graphs include lemporal facts (such as events happening at specific times) and literal values (such as numerical measurements or textual strings). Because large portion a graph's 's information stored as these literal values-like a numerical temperature reading or a textual label-a robust system should be able answer queries that involve these literals. For example, the system might reason over a time- series of events to answer a query about when particular relationship held, or interpret textual data attached to nodes to respond to query that references an entity's description.
Background Semantics: We want to incorporate complex background knowledge encoded by formal somantics and axioms. This means supporting not just direct entity-to-cntity relationships but also higher-order relationships between classes of entities and their hierarchical structures. For example, the system should enable neural reasoning that respects the rules of description logics subsots of the Web Ontology Language (OWL). In practice, this might allow the model to deduce that if an entity belongs to a particular subclass (like "Cat" within "Mammal"), it should inherit relationships and constraints from its superclass. A concrete example might be reasoning that if a graph knows "Fluffy is a Cat" and that "All Cats are Mammals," " then the system can conclude "Fluffy is a Mammal." Supporting these complex axioms will allow more powerful and semantically rich reasoning over graph data.
In the Modeling branch:
Encoder:
We seek inductive encoders that can interpret new relationships in knowledge graph even if they were unseen during training. For example, if a graph's schema is updated with new relation type like "collaboratesWith," the encoder should handle queries involving this relation without requiring retraining. This capability supports two key goals: (1) Updatability: The neural database can quickly adapt to changes the graph's schema or content. For instance, if new nodes and edges appear in KG about scientific publications, the system can incorporate them on the fly. (2) Poetrin-FFintunn Strategy: A model could be pre-trained on general graph structures and then fine-tuned to answer queries Ultimately, we aspire to create a single CLQA model that can respond to queries about any unseen KG, regardless of the vocabulary of entities and relations it uses.
new, custom graph with unique set of entity and relation types.
Processor: We want processor networks that can execute a wide range of complex query operators similar to those in SPARQL or Cypher languages efficiently and effectively. For example, system
42

---

Published in Transactions on Machine Learning Research (11/2024)
should handle queries that require union, intersection, property paths, or filters over nodes and edges. Improving the sample efficiency of these neural processors is crucial- the model should require less training data or time while preserving accuracy. For example, if training a model to interpret SPARQL "FILTER" operator, we want the model to learn from relatively few examples and still apply the filter operator correctly new queries without extensive retraining.
Currently, neural query decoders typically return results as discrete graph nodes. We want to extend this to continuous outputs for queries that involve, for example, numerical attributes or categories not purely represented
Decoder:
nodes. For instance, if the query is "What is the average lemperature of city X in July?" the decoder should produce a numeric result (like 29.5CC) rather than just pointing to node. This ability is essential for real-world datasets where many queries involve combining discrete graph structures with numeric or categorical data.
Complexity: Processor networks can face significant computational challenges, whether from the high dimensionality of their embeddings (in purely neural models) or the large number of graph nodes (in neuro-symbolic approaches). To handle massive KGs with billions of nodes and trillions of edges, need more efficient algorithms for implementing neural logic operators (like those for union or negation) and for retrieving relevant information from the graph. For example, if a query asks about relationships among millions of nodes, the system should use optimized retrieval methods, ensuring that answering complex queries remains feasible at scale.
In the Queries branch:
We aim to develop neural methods that can handle wider variety of complex query operators found in declarative graph query languages. For example, a system should support the Kleene plus and star operators, which let queries match repeated patterns in a path (like "all ancestors" or "paths of any length connecting two nodes"). It should also manage property paths, where queries involve sequences of edges that fulfill certain property constraints (such as "entities connected by a path of type 'friendOf' repeated one or more times"). In addition, the system should handle filters that restrict results based on conditions, for example retrieving people from a graph who over 30 years old and live in specific city.
Operators:
Patterns:
We want query answering systems that can handle patterns beyond simple tree struc- tures. For instance, a query might involve a directed acyelic graph (DAG) pattern such as "Find lopics that are prerequisites for both X and Y courses" or eyclic graph pallern like "Identify people who follow each other on a social network." " This complexity means the system must interpret and respond to queries where relationships loop back or branch in multiple directions, replicating the complexity of many real-world graph queries.
Projected Variables: Instead of only returning a single final answer entity (like the name of a city), queries may require returning intermediate variables or entire tuples of variables. For example, user might ask "Which actors and their respective dircctors collaborated on film in 2020?" The answer requires projecting multiple variables both the actor and the director for each case. Similarly, a query might require returning a relationship as a variable, such as identifying not just the entities but also the nature of their relationship. The formalism presented in this survey supports this, and some papers present preliminary results, but none are evaluated on the quality of bindings to these intermediate variables.
Expressiveness: We want systems to answer queries that go beyond simple fragments like EPFO (existential positive first-order) and EFO (existential first-order). This means supporting the union of conjunclive queries with negations (UCQ and UCQneg) and moving toward the expressiveness found in full database query languages. For instance, the system should handle a query like "Find all persons who are not authors of any paper 2021 but who co-authored a paper in 2020." This query includes negation notot authors") combined with conjunction ("and who co-authored"), illustrating advanced expressiveness.
43

---

Published in Transactions on Machine Learning Research (11/2024)
Finally, we envision work on integrating integrating Knowledge Graph Ques- tion Answering and CL.QA. KGQA systems interpret natural language questions and map them to complex graph queries. Suppose someone asks, "Where do the people who won the most prestigious prize in computer science work?". The system's capabilities will parse this question, interpret it as a graph query with appropriate operators and palterns, and execule the query on a knowledge graph that assumed to be complete. Combining this with CL.QA would lead systems that can answer natural language questions with incomplete knowledge graphs. We elaborate on the similarities and differences between CLQA and KGQA in Appendix B.
Integrate KGQA:
In Datasets and Evaluation:
We require larger, more varied benchmark datasets that reflect real-world complexity. For example, a new benchmark might include not just classic triple-basod knowlodge graphs but also hyper- relational graphs or graphs that combine textual and visual data. These benchmarks should present queries that use more expressive semantics such temporal conditions ("Which actors starred in movies after 2010?") or numeric filters ("Citics with population over one million?"). They should also incorporate a wider range of query operators (like union or intersection) and complex query patterns (such as nested queries). For instance, a robust benchmark might ask the system to handle a query like: "Find images of all institutions connected to entities that are both scientists and authors" requiring the system to interpret graph modalities, apply multiple operators, and return results from multiple data sources. Finally, would need more insight into how difficult. certain evaluation datasets rcally are. Currently, we cannot say whether the queries in dataset are intrinsically harder to answer or whether it is just an artifact of how systems are designed that scores are different. This would also lead to more insight into what query answering system is expected to be better for what datasets and queries.
Current evaluation methods often focus narrowly whether a system predicts the correct "hard" an- swers. We need a more compreheusive evaluation framework that measures a system's performance across the entire query answering process. For example, this framework might include metrics that assess the efficiency of the query plan, how well the system handles uncertainty in queries, how it ranks potential answers by relevance, or how it deals with partial information. Concretely, beyond just checking the system finds the correct city for query like "What is the capital France?" we might evaluate how it handles ambiguous queries ("What is the capital of a big European country near Germany?"). or how well it explains its reasoning steps. This means developing new met- rics that reflect accuracy in retrieving possible answers ("hard" answers), correctness in reasoning about complex semantics, and clarity in explaining results, ensuring more principled and muanced evaluation of query answering systems.
Overall CLQA has demonstrated promisc across a wide range of domains. In this survey we provide a detailed taxonomy study CLQA. We envision CLQA to be among the core tasks and capabilities of the next generation graph databases.
Acknowledgments
We thank Pavel Klinov (Stardog), Matthias Fey (Kumo.Al), Qian Li (Stanford) and Keshav Santhanam (Stanford) for providing valuable feedback on the draft. In addition, Michael wants to thank several people from the L&R group from the VU Amsterdam, including Daniel Daza, Dimitrios Alivanistos, Frank van Harmelen, Ruud van Bakel, Yamnick Brunink, as well as Teodor Aleksiev (BSc. VU), Max Zwager (MSc. VU), and Patrick Koopmann (University Dresden) for discussions on various aspects of the work. Michael was partially funded by the Union (grant 101093202); his research was further made possible by a gift from Accenture, LLP.
project, part of the Horizon Europe programme of the European
44

---

Published in Transactions on Machine Learning Research (11/2024)
References
Vaibhav Adlakha, Parth Shah, Srikanta J. Bedathur, and Mausam. Regex queries over incomplete knowledge bases. In 3rd Conference on Automated Knowledge Base Construction, AKBC, 2021.
Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Sharifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under a unified framework. JEEE Transactions on Paltern Analysis and Machine Intelligence, 2021. doi: 10. 2TA00
Dimitrios Alivanistos, Max Berrendorf, Michael Cochez, and Mikhail Galkin. Query embedding on hyper- relational knowledge graphs. In International Conference Learning Representations, 2022.
Güneg Alug, Olaf Hartig, M Tamer Özsu, and Khuzaima Daudjee. Diversified stress testing of RDF data management systems. In 13th International Semantic Web Conference, pp. 197-212. Springer, 2014.
Alfonso Amayuelas, Shuai Zhang, Xi Susie Rao, and Ce Zhang, Neural methods for logical reasoning over knowledge graphs. In International Conference on Learning Representations, 2022.
Medina Andresel, Csaba Domokos, Daria Stepanova, and Trung-Kien Tran. A neural-symbolic approach for ontology-mediated query answering. arXiv preprint 3rXiv:2106.14052 2021.
Medina Andresel, Trung-Kien Tran, Csaba Domokos, Pasquale Minervini, and Daria Stepanova. Combining inductive and deductive reasoning for query answering over incomplete knowledge graphs. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, 2023. URL hwt//oi..oggg/// https://doi.onn org/r0../....... 10. 10111111113151 /t/.///6688880.11116.666 3614816.
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference Learning Representations, 2021.
Erik Arakelyan, Pasquale Minervini, Daniel Daza, and Michael Cochez Isabelle Augenstein. Adapting neural link predictors for complex query answering. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL. https://openreviee
Akari Asai, Kazuma Hashimoto, Hannaneh Hajishirzi, Richard Socher, and Caiming Xiong. Learning to retrieve reasoning paths over wikipedia graph for question answering. In International Conference on Learning Representations, 2020. URL
Franz Baader, Diego Calvanese, Deborah McGuinness, Peter Patel-Schneider, Daniele Nardi, et al. The description logic handbook: Theory, implementation and applications. Cambridge university press, 2003.
Samy Badreddine, Artur d' Avivia Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence, 303:103649, 2022.
Jinheon Baek, Alham Fikri Aji, and Amir Saffari. Knowledgg--augmented language model prompting for zero-shot knowledge graph question answering. In Proceedings of the 1st Workshop Natural Language Reasoning and Structured Explonations (NLRSE), pp. 78-106, Toronto, Canada, 2023. Association for Computational Linguistics. doi: 111/6633/1122023mnmss 1.7. URL https://aclaatthlloo htt.a//iannnollooooo/////000 nlrse-1.7.
Jiaxin Bai, Zihao Wang, Hongming Zhang, and Yangqiu Song. Query2Particles: Knowledge graph reasoning with particle embeddings. Tn Findings of the Association for Computational Länguistics: NAACL 2022. Association for Computational Linguisties, 2022.
Jiaxin Bai, Chen Luo, Zheng Li, Qingyu Yin, Bing Yin, and Yangqiu Song. Knowledge graph reasoning over entities and numerical values. In KDD 2023, 2023a.
Jiaxin Bai, Tianshi Zheng, and Yangqiu Song. Sequential query encoding for complex query answering on knowledge graphs. Transactions on Machine Learning Research, 2023b. ISSN 2835-8856. URL https: wtwpeeewwwwwweeetunneeeee. net//foumm EdE.R
/ //openreview..
45

---

Published in Transactions on Machine Learning Research (11/2024)
Yushi Bai, Xin Lv, Juanzi Li, and Lei Hou. Answering complex logical queries knowledge graphs via query computation tree optimization. In Proceedings of the 40th International Conference on Machine Learning, pp. 1472 1491, 2023c.
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020. URL https://openrrvieet wttp://www....oooooooooo./1////.
Pablo Barceló, Mikhail Galkin, Christopher Morris, and Miguel Romero Orth. Weisfeiler and leman go relational. In The First Learning on Graphs Conference, 2022. URL http://pppnreve...eeeeee
Ed=wY_IYhh6pp
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gozzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint orXiv:1806. 01261, 2018.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Monagement of data, pp. 1247 1250, 2008.
Antoine Bordes, Nicolas Usumier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
Elizabeth Boschee, Jennifer Lautenschlager, Sean O'Brien, Steve Shellman, James Starz, and Michael Ward. ICEWS Coded Event Data. Harvard Dataverse, 2015. URL https://àoi. org/ 7000////////
Dan Brickley, Ramanathan V Guha, and Brian McBride. RDF schema 1.1. W3C recommendation, 25: 2004-2014, 2014.
Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, al. (TAO): Facebook's distributed data store for the social graph. In 2013 { {USENIX} Annual Technical Conference (( (UUSENIX)AAC)) 13), pp. 49 19-60, 2013.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXim:2104.13473 2021.
Davide Buffelli, Pietro Liò, and Fabio Vandin. SizeShiftReg: regularization method for improving size- generalization in graph neural networks. In Advances in Neural Information Processing Systems, 2022.
Nilesh Chakraborty, Denis Lukovnikov, Gaurav Maheshwari, Priyansh Trivedi, Jens Lehmann, and Asja Fischer. Introduction to neural network-based question answering over knowledge graphs. WIREs Data Mining and Knowledge Discovery, 11(3) 2021. doi: https///oi.orgg/ /tt:///iiirr10110002220/ 10.10000//wwwmmmmmm 1389. URL attps://wires. onlinelibrary wiley. httm///o/ab//0.10000
1389.
Ines Chami, Sami Elu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: A model and comprchensive taxonomy. Journal of Machine Learning Research, 23(89):1-64, 2022.
URL http://jmmr wtwppnt.......eeeeeeeeeeeeeeeeee http//pppaa////222-a02p 25m..tml..
Mingyang Chen, Wen Zhang, Yuxia Geng, Zezhong Xu, Jeff Z Pan, and Huajun Chen. Generalizing to unseen elements: A survey on knowledge extrapolation for knowledge graphs. In Proceedings of the Thirly- Second International Joint Conference on Artificial Intelligence, 2023. doi: 10.24963 (0cai.2023/1 URL
https:///oi. org/ 24963/1jeaa jjcai. 2023/737.
Xuclu Chen, Ziniu Hu, and Yizhou Sun. Fuzzy logic based logical query answering on knowledge graphs. In Thirty-Sizth AAAI Conference on Artificial Intelligence, AAAI, pp. 3939-3948 AAAI Press, 2022.
Nurendra Choudhary and Chandan K. Reddy. Complex logical reasoning over knowledge graphs using large language models. arXiv preprint ar arxi:22055.011 011577 2023.
46

---

Published in Transactions on Machine Learning Research (11/2024)
Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan Reddy. Probabilistic entity representation model for reasoning over knowledge graphs. In Advances in Newral Information Processing Systems, 2021a.
Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan K Reddy. Self- supervised hyperboloid representations from logical queries over knowledge graphs. In Proceedings of the Web Conference 2021, pp. 1373 1384, 2021b.
Michael Cochez. Semantic agent programming language: use and formalization. Master's thesis, University of Jyväskylä, 2012.
Edgar Codd. relational model of data for large shared data banks. Communications of the ACM, (6):377 387, 1970.
Graham Cormode and Shan Muthukrrshhan, An improved data stream summary: the count-min sketch and its applications. Journal of Algorithmms, (5(1):58-78) 75, 2005.
Tamara Cucumides, Daniel Daza, Pablo Barceló, Michael Cochez, Floris Geerls, Juan L Reutter, and Miguel Romero. UnRavL: A neuro-symbolic framework for answering graph pattern queries in knowledge graphs The Third Learning on Graphs Conference, 2024. URL https://
Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pp. 132-141, Valencia, Spain, 2017. Association for Computational Linguistics. URL https://aclantholl.g. .rg/ E17-1013.
Rajarshi Das, Ameya Godbole, Ankita Naik, Elliot Tower, Manzil Zaheer, Hannaneh Hajishirzi, Robin Jia, and Andrew McCallum. Knowledge base question answering by case-based reasoning over subgraphs. In International Conference on Machine Learning, ICML 2022, Proccedings of Machine Learning Research. PMLR, 2022.
Daniel Daza and Michael Cochez. Message passing query embedding. Proceedings of the ICML 2020 Work- shop on Graph Representation Learning and Beyond, 2020.
Lauren Nicole Delong, Ramon Fernández Mir, and Jacques D. Fleuriot. Neurosymbolic AI for reasoning over knowledge graphs: A survey. IEEE Transactions on Neural Networks and Learning Systems, 2024. 2024.342018..
doi: 10.1109/INNIS 210.12
Caglar Demir, Michel Wiebesiek, Renzhong Lu, Axel-Cyrille Ngonga Ngomo, and Stefan Heindorf. LitCQD:
Multi-hop reasoning in incomplete knowledge graphs with numeric literals. In ECML PKDD, 2023.
Xin Luna Dong. Challenges and innovations in building a product knowledge graph. In Proceedings of the 24th ACM SIGKDD International conference on knowledge discovery & data mining, pp. 2869 2669-2869, 2018.
Emma Flint. Announcing alexa entitics (beta): Create more intelligent and engaging skills with easy access to alexa's knowledge, 2021. CRL https://devvlloper amazon. wwwaaa.commeeneee.... Ween-U/bbogg//lleee alexa-skills-iit wttpaa/lllll/t//////////a/a http:////eeeeeeaiiiiieeeeeeeeeee
Tal Friedman and Guy Van den Broeck. Symbolic querying of vector spaces: Probabilistic databases meets relational embeddings. In Conference Uncerlainly in Artificial Intelligence, pp. 1268-1222 1277. PMLR, 2020.
Luis Galárraga, Christina Tefloodi, Katja Hose, and Fabian M. Suchanek. AMIE: Association rule mining under incomplete evidence in ontological knowledge bases. In Proceedings of the International World Wide Web Conference (WWW), 2013.
Mikhail Galkin, Priyansh Trivedi, Gauray Maheshwari, Ricardo Usbeck, and Jens Lehmann. Message passing for hyper-relational knowledge graphs. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, pp. 7346-7359. Association for Computational Linguistics, 2020.
47

---

Published in Transactions on Machine Learning Research (11/2024)
Mikhail Galkin, Etienne Denis, Jiapeng Wu, and William L. Hamilton. NodePiece: Compositional and parameter-elficint representations of large knowledge graphs. In International Conference on Learning Representations, 2022a. URL UtLp:pps///ppeeeisssee////rrrm wttp:///orrmmm/ic.tttt.o.....
Mikhail Galkin, Zhaocheng Zhu, Hongyu Ren, and Jian Tang. Inductive logical query answering in knowledge graphs. In Advances in Neural Information Processing Systems, 2022b.
Mikhail Galkin, Jincheng Zhou, Bruno Ribeiro, Jian Tang, and Zhaocheng Zhu. A foundation model for zero- shot logical query reasoning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: httpss///ppenevieew het/forummid=:RRyyYaa
Jianfei Gao, Yangze Zhou, and Bruno Ribeiro. Double permutation equivariance for knowledge graph com- pletion. arXiv preprint arXix:2302.00 01313, 2023.
Thomas Gebhart, Jakob Hansen, and Paul Schrater. Knowledge sheaves: A sheaf-theoretic framework for knowledge graph embedding. In Proceedings of The 26th International Conference on Artificial Intelligence and Stalistics, pp. 9094 9116, 2023. URL httt:://prroceedngg.. wwwpeeeddinnnmm..........mm.e..e mlr. pre..ppesss/ gebhart23a. html.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, pp.
2017.
Aditya Grover and Jure Leskovee. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp.
2016.
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Acceler- ating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, 2020. URL https:/ httpss///axivvoo// //////axxvvoor/abbeae//a/ http://bs//19...0000 10396.
Yuanbo Guo, Zhengxiang Pan, and Jeff Heflin. LUBM: A benchmark for OWL knowledge base systems. Journal of Web Semantics, 3(2-3):158-182 2005.
Kelvin Guu, John Miller, and Percy Liang. Traversing knowledge graphs in vector space. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 318-327. Association org/
for Computational Linguistios, 2015. doi: 10.18653/w1/D15-1100 URL https://aclanthont D15-1038.
Ferras Hamad, Issac Liu, and Xian Xing Zhang. Food discovery with Uber Eats: Building a query under- standing engine, 2018. URL https://www uber. haam///lo/uubbreeeeeee tttgg//eree---uu-----eeeeeeeeeee uneery--uddrstaddnng/
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovee. Embedding logical queries on knowledge graphs. In Advances in Neural Information Processing Systems, volume 31, 2018.
William L Hamilton. Graph Representation Learning. Morgan & Claypool Publishers, 2020.
Jakob Hansen and Robert Ghrist. Toward a spectral thcory of cellular sheaves. Journal of Applied and Compulational Topology, 3:315 358, 2019.
Olaf Hartig, Picrre-Antoine Champin, Gregg Kellogg, and Andy Scaborne. RDF-star and SPARQL-star. Draft Community Group Report, 2022.
Sandro Hawke, Ivan Herman, Bijan Parsia, Axel Polleres, and Andy Seaborne. SPARQL 1.1 entailment regimes. W3C' recommendation, 2013.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In Proceedings of the 26th international conference on world wide web, pp. 173 173-182, 2017.
Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. G-retriever: Retrieval-angmentee generation for textual graph understanding and question answering. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL
48

---

Published in Transactions on Machine Learning Research (11/2024)
Yunjie He, Mojtaba Nayyeri, Bo Xiong, Evgeny Kharlamov, and Steffen Staab. Modeling relational patterns for logical query answering over knowledge graphs. arXiv preprinl arXiv:2303. 1 11858, 2023.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. NeurIPS, 2021.
Vinh Thinh Ho, Daria Stepanova, Dragan Milchevski, Jannik Strötgen, and Gerhard Weikum. Enhancing knowledge bases with quantity facts. In WWW '22: The ACM Web Conference 2022, pp. 893 901. ACM, 2022.
Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d' Amato, Gerard de Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, et al. Knowledge graphs. ACM Computing Surveys (CSUR), 54(4):1 37, 2021.
Zhiwei Hu, Victor Gutiérrez- Butiérrez-Basulto, Zhiliang Xiang, Xiaoli Li, Ru Li, and Jeff Z Pan. Type-aware embeddings for multi-hop reasoning over knowledge graphs. In Proceedings of the Shirtt-PPirtt In- ternational Joint Conference on Artificial Intelligence, IJCAI-22, pp. aiooi.org//00. 24963/122ccc 2022/427.
2022. URL https:
Qian Huang, Hongyu Ren, and Jure Leskovec. Few-shot relational reasoning via connection subgraph pre- training. In Alice Н. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022a. URL https::/openrevvier http://ew.....toooo.//.///ooo/ra
Xingyue Huang, Miguel Romero Orth, ismail ilkan Ceylan, and Pablo Barceló. A theory of link prediction via relational weimeeiler-leman. In Thirty-sene seventh Conference on Newral Information Processing Systems, 2023.
Zijian Huang, Meng-Fen Chiang, and Wang-Chien Lee. LinE: Logical query reasoning over hierarchical knowledge graphs. In Aidong Zhang and Huzefa Rangwala (cds.), KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Dala Mining, pp. 615 625. ACM, 2022b.
Thab F Ilyas, Theodoros Rekatsinas, Vishnu Konda, Jeffrey Pound, Xiaoguang Qi, and Mohamed Soliman. Saga: A platform for continuous construction and serving of knowledge at scale. In Proceedings of the 2022 International Conference on Management of Data, pp. 2259-2272, 2272, 2022.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transac- tions on Big Data, 7(3):535-547, 2019.
Daniel Keysers, Nathanacl Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. Measuring compositional generalization: comprehensive method on realistic data. International Conference on Learning Representations, 2020. URL ttttp:://operrviiee net/ forum?id SygeCnWWW....
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Erich Peter Klement, Radko Mesiar, and Endre Pap. Triangular norms, volume 8. Springer Science & Business Media, 2013.
Bhushan Kotnis, Carolin Lawrence, and Mathias Niepert. Answering complex queries in knowledge graphs with bidirectional sequence encoders. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4968-44889 4977. AAAI Press, 2021.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In International Conference on Machine Learning, pp. 2863-2872 PMLR, 2018
Kalev Loetaru and Philip A Schrodt. Gdelt: Global data on events, location, and tone, 1979 771220 In ISA annuaal convention, volume 2, pp. 1-49. Citeseer, 2013.
49

---

Published in Transactions on Machine Learning Research (11/2024)
Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick Van Kleef, Sören Auer, and Christian Bizer. Dbpedia-a large-scale, multilingual knowledge base extracted from wikipedia. Semantic web, 6(2):167 195, 2015.
Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. In Empirical Methods in Natural Language Processing (EMNLP), 2018.
Xueyuan Lin, Gengxian Zhou, Tianyi Hu, Li Ningyuan, Mingzhi Sun, Haoran Luo, et al. FLEX: Feature- logic embedding framework for CompleX knowledge graph reasoning. arXiv preprint XrXi:2205511039. 2022.
Xueyuan Lin, Chengjin Xu, Fenglong Su, Gengxian Zhou, Tianyi Hu, Ningyuan Li, Mingzhi Sun, Haoran Luo, et al. TFLEX: Temporal feature-logic embedding framework for complex reasoning over temporal knowledge graph. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL foooforrrnnddodaadg11111.
https://openreviee
Lihui Liu, Boxin Du, Heng Ji, ChengXiang Zhai, and Hanghang Tong. Neural-answering logical queries on knowledge graphs. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1087-1097, 2021.
Xiao Liu, Shiyu Zhao, Kai Su, Yukuo Cen, Jiezhong Qiu, Mengdi Zhang, Wei Wu, Yuxiao Dong, and Jie Tang. Mask and reason: Pre-training knowledge graph transformers for complex logical queries. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery Data Mining, 2022.
Xiao Long, Liansheng Zhuang, Aodi Li, Shafci Wang, and Houqiang Li. Neural-basod mixture probabilistic query embedding for answering FOL queries on knowledge graphs. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, pp. 3001-3013. Association for Computational Linguistics, 2022.
Haoran Luo, Haihong E, Yuhao Yang, Gengxian Zhou, Yikai Guo, Tianyu Yao, Zichen Tang, Xueyuan Lin, and Kaiyang Wan. NQE: N-ary query embedding for complex query answering over hyper-relational knowledge graphs. In AAAT 2023, 2023.
Zhezheng Luo, Jiayuan Mao, Joshua B. Tenenbaum, and Leslie Pack Kaelbling, On the expressiveness and learning of relational neural networks on hypergraphs, 2022. URL attps://openrevi// het/forum?id HRF6T1SayDn.
Francois Luus, Prithviraj Sen, Pavan Kapanipathi, Ryan Riegel, Ndivhuwo Makondo, Thabang Lebese, and Alexander Gray. Logic embeddings for complex query answering. arXiv preprint crXiv:2103.00/11 2021.
Gengehen Mai, Krzysztof Janowicz, Bo Yan, Rui Zhu, Ling Cai, and Ni Lao. Contextual graph attention for answering logical queries over incomplete knowledge graphs. In Proceedings of the 10th International Conference Knowledge Capture, pp. 171 178, 2019.
Gengchen Mai, Krzysztof Janowicz, Ling Cai, Rui Zhu, Blake Regalia, Bo Yan, Meilin Shi, and Ni Lao. SE- KGE: A location-aware knowledge graph embedding model for geographic question answering and spatial semantic lifting. Transactions in GIS, 24(3):623 655, 2020.
Stanislav Malyshev, Markus Krötzsch, Larry González, Julius Gonsior, and Adrian Bielefeldt. Getting the most out of wikidata: Semantic technology usage in Wikipedia's knowledge graph. In Proceedings of the 1 7thh International Semantic. Web Conference (1SWC'18), volume 11137 of LNCS, pp. 376 394. Springer,
2018.
Michacl McCloskey and Neal Cohen. Catastrophic interference in connectionist networks: The soquential learning problem. In Psychology of learning and molivation, volume 24, pp. 109- 109-165. Elsevier, 1989.
George A Miller. WordNet: An electronic lexical dolabase. MIT press, 1998.
50

---

Published in Transactions on Machine Learning Research (11/2024)
Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. Distant supervision for relation extraction without labeled data. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pp. 1003 10010,11,,,1110011 2009.
T. Mitchell, W. Cohen, E. Hruschka, P. Talukdar, J. Betteridge, A. Carlson, B. Dalvi, M. Gardner, B. Kisiel, J. Krishnamurthy, N. Lao, K. Mazaitis, T. Mohamed, N. Nakashole, E. Platanios, A. Ritter, M. Samadi, B. Settles, R. Wang, D. Wijaya, A. Gupta, X. Chen, A. Saparov, M. Greaves, and J. Welling, Never-ending learning. In Proceedings of the Twenty-Ninth AAAT Conference on Artificial Intelligence (AAAT-15), 2015.
Eduardo Mizraji. Vector logie: a natural algebraic representation of the fundamental logical gates. Journal of Logic and Computation, 18(1):97 121, 2008.
Boris Motik, Peter F Patel-Schneider, Bijan Parsia, Conrad Bock, Achille Fokoue, Peter Haase, Rinke Hoekstra, lan Horrocks, Alan Ruttenberg, Uli Sattler, et al. OWL 2 web ontology language: Structural specification and functional-style syntax. W3C recommendation, 27(65):159, 2009.
Chau Nguyen, Tim French, Wei Liu, and Michael Stewart. SConE: Simplified cone embeddings with symbolic operators for complex logical queries. In Findings of the Association for Computational Linguistics: ACL, 2023, pp. 11931 11946, 2023a. URL attts://accaanthologg http://.///.....iin.g.-e--. findings-acll.... aaddings-acl.55..
Chau Due Minh Nguyen, Tim French, Wei Liu, and Michael Stewart. CylE: Cylinder embeddings for multi- hop reasoning over knowledge graphs. In Proceedings of the 17th Conference of the European Chapler of the Association for Computational Linguistics, pp. 1736-1751. Association for Computational Linguistics, 2023b. URL https://aclannthloog org/2023
wegg/2023.eee sacl-main. 127.
Thomas Pellissior Tanon, Gerhard Weikum, and Fabian Suchanek. YAGO 4: reason-able knowledge base. In European Semantic Web Conference, pp. 583 596. Springer, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Decpwalk: Online lcarning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and dala mining, pp. 701-710, 2014.
Maximilian Pflueger, David Tena Cucala, and Egor Kostylev. GNNQ; A neuro-symbllic approach to query answering over incomplete knowledge graphs. In International Semantic Web Conference, 2022.
Tahereh Pourhabibi, Kok-Leong Ong, Booi H Kam, and Yee Ling Boo. Fraud detection: systematic
literature review of graph-basod anomaly detcction approaches. Decision Support Systems, 133:113303, 2020.
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. RNNLogie: Learning logic rules for reasoning on knowledge graphs. In International Conference on Learning Representations (ICLR), 2021.
Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In Advances in Newral Information Processing Systems, volume 33, 2020.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs vector space using box embeddings. In International Conference on Learning Representations, 2020.
Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Michihiro Yasunaga, Haitian Sun, Dale Schuurmans, Jure Leskovec, and Denny Zhou. Lego: Latent execution-guided reasoning for multi-hop question answering on knowledge graphs. In International Conference on Machine Learning, pp. 8959 8970. PMLR, 2021.
Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Denny Zhou, Jure Leskovee, and Dale Schuurmans. SMORE: Knowledge graph completion and multi-hop reasoning in massive knowledge graphs. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2022.
Rex, Ying. Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, and Jure Leskovee. Neural subgraph matching. Xáu preprint ar wxXii:2007.00000 2020.
51

---

Published in Transactions on Machine Learning Research (11/2024)
Mark B Ring. CHILD: A first step towards continual learning. Learning to learn, pp. 261-292, 1998.
Jeffrey Sardina, Callie Sardina, John D Kelleher, and Declan O'Sullivan. Analysis of attention mechanisms box-embbddiig systems. In Artificial Intelligence and Cognitive Science: 30th Irish Conference, AICS 2022, pp. 68-80. Springer, 2023.
Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. Improving multi-hhp question answering over knowl- edge graphs using knowledge base embeddings. In Proceedings of the 58th Annual Meeting of the Associa- lion for Compulational Linguistics, pp. 4498-4507, Online, 2020. Association for Computational Linguis- tics. doi: 10/8653/v122222/ acl- main.412. URL
wwwpogg...gg////0 org/2020. 110000.ac.. acl-main.44
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61 80, 2008.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European semanlic web conference, pp. 593 603-607.600 Springer, 2018.
Haitian Sun, Andrew Arool, Tania Bedrax Weiss, Fernando Pereira, and William W Cohen. Faithful embeddings for knowledge base queries. In Advances in Newral Information Processing Systems, 2020.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. RotatE: Knowledge graph embedding by
relational rotation in complex space. In International Conference on Learning Representations, 2019. URL btctps://openreee httppprreiiieeeeettooorttiaiiiee www./eeeeeteieeeeeeee htt.:/rrrmmidddlllgEEnnRR.
Muzamil Hussain Syed, Tran Quoe Bao Huy, and Sun-Tao Tae Chung. Context-aware explainable recommenda- tion based on domain knowledge graph. Big Data and Cognitive Compuling, 6(1):11, 2022.
Zhenwei Tang, Shichao Pei, Xi Peng, Fuzhen Zhuang, Xiangliang Zhang, and Robert Hoehndorf. TAR: Neural logical reasoning across tbox and abox. arXiv preprint arXiv:200.. 14591, 2022.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In PMLR, 2020.
International Conference on Machine Learning, pp.
James Thorne, Majid Yazdani, Marzieh Saeidi, Fabrizio Silvestri, Sebastian Riedel, and Alon Halevy. Database reasoning over text. In Proceedings of the 59th Annuol Meeting of the Association for Computa- tional Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 3091 3104. Association for Computational Linguistics, 2021a.
James Thorne, Majid Yazdani, Marzich Sacidi, Fabrizio Silvestri, Scbastian Riedel, and Alon Halevy. From natural language processing to neural databases. In Proceedings of the VLDB Endowmend, volume 14, pp. 1033-1039 VLDB Endowment, 2021b.
Sebastian Thrun. A lifelong learning perspective for mobile robot control. In Intelligent robots and systems, pp. 201- 214. Elsevier, 1995.
Yuanyuan Tian, Wen Sun, Sui Jun Tong, En Liang Xu, Mir Hamid Pirahesh, and Wei Zhao. Synergistic graph and sqi analytics inside IBM Db2. Proceedings of the VLDB Endowment, 12(12):1782 1785, 2019.
Théo Trouillon, Johannes Wolbl, Scbastian Riedel, Éric Gaussicr, and Guillaume Bouchard. Complex embed- dings for simple link prediction. In International conference on machine learning, pp. 2071 2080. PMLR, 2016.
Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing differentiable fuzzy logic operators. Artificial Intelligence, 302:103602, 2022. ISSN 0004-3702. doi: http:://000ooor11000166....... artint..22. 103602. URL https://www http::/e//..ieeeeeeeereeee...... http////ccceeeeetcece///////////
V Vapnik. The nature of statistical learning theory. Springer science & business media, Berlin, Germany, 2013.
52

---

Published in Transactions on Machine Learning Research (11/2024)
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition based multi-relational graph convolutional networks. In International Conference on Learning Representations, 2020. URL
C4tPr..
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, 2017.
Petar Velickovic, Guillem Cucurull, Aranixa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Denny Vrandecic and Markus Krötzsch. Wikidata: a free collaborative knowledgebase. Commun. ACM, 57 (10):78-85, 2014.
Dingmin Wang, Yeyuan Chen, and Bernardo Cuenca Grau. Efficient embeddings of logical variables for query answering over incomplete knowledge graphs. In Proceedings of the AAAT Conference on Artificial Intelligence. AAAI Press, 2023a.
Kai Wang, Chunhong Zhang, Jibin Yu, and Qi Sun. Signal embeddings for complex logical reasoning in knowledge graphs. In International Conference on Knowledge Science, Engineering and Management, pp. 255 267. Springer, 2022.
Meng Wang, Haomin Shen, Sen Wang, Lina Yao, Yinlin Jiang, Guilin Qi, and Yang Chen. Learning to hash for efficient soarch over incomplete knowledge graphs. In 2019 IEEE International Conference on Data Mining (ICDM), 2019.
Siyuan Wang, Zhongyu Wei, Jiarong Xu, Taishan Li, and Zhihao Fan. Unifying structure reasoning and language model pre-training for complex reasoning. IEEE/ACM Trans. Audio, Speech and Lang. Proc., pp. 1586-1595, 2023b.
Yanan Wang, Michihiro Yasunaga, Hongyu Ren, Shinya Wada, and Jure Leskovec. Vqa-gnn: Reasoning with multimodal knowledge via graph neural networks for visual question answering. In 2023 IEEE/CVP International Conference on Computer Vision (ICCV), pp. 21525 21335. IEEE Computer Society, 2023c.
URL https://ddot ieeecooppterrsocetyy org/10. wttp//..t//////..//.... 11t.:11119///111111 2023. 01973.
Zihao Wang, Hang Yin, and Yangqiu Song. Benchmarking the combinatorial generalizability of complex query answering knowledge graphs. In Thirty-fifth Conference Neural Information Processing Sys- lems Dalasels and Benchmarks Track (Round 2), 2021.
Zihao Wang, Weizhi Fei, Hang Yin, Yangqiu Song, Ginny Y. Wong, and Simon See. Wasserstein-Fisher Rao embedding: Logical query embeddings with local comparison and global transport. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 13696, 2023d. URL https: Haaclanthllogyoorg/20000 orgg/023.. findings-acl...... 864.
Zihao Wang, Yangqiu Song, Ginny Y. Wong, and Simon See. Logical message passing networks with one- hop inference on atomic formulas. In The Eleventh International Conference on Learning Representations, ICLR, 2023c. URL https://openreviie wttperrwwwwieeeeetonetnotree wet het//torumiid=SSyyppp1.
Boris Weisfeiler and Andrey Leman The reduction of a graph to canonical form and the algebra which appears therein. Nauchno- Tanuchno-TTccmmiccheskuu Informalsia, 2(9):12 16, 1968. English translation by G. Ryabov is available at https://wwwt http://www..iii..../././/......t zcu. wttwwt//w/w////ppt/t http://ddd/l1lppppaaalaa pttpppppptrrtttttslattiiooo translation. pdf.
Robert West, Evgeniy Gabrilovich, Kevin Murphy, Shaohua Sun, Rahul Gupta, and Dekang Lin. Knowledge base completion via search-based question answering. In 23rd International World Wide Web Conference, WWW '14, pp. 515-526. ACM, 2014.
Longfeng WI, Yao Zhou, and Dawei Zhou. Towards high-order complementary recommendation via logical reasoning network. arXie preprint or Xiv:222... 04966, 2022.
53

---

Published in Transactions on Machine Learning Research (11/2024)
Yanrong Wu and Zhichun Wang. Knowledge graph embedding with numeric attributes of entities. In Pro- ceedingg of the Third Workshop on Representation Learning for NIP,, pp. 132-136. Association for Com- putational Linguisties, 2018. doi: 10.18653/v1/ 1..18663/11/W18-311.. URL https:
org/N18-3017..
Zhaohan Xi, Ren Pang, Changjiang Li, Tianyu Du, Shouling Ji, Fenglong Ma, and Ting Wang. Reasoning over multi-view knowlodge graphs. arXiv preprint Xxi::2009119000 2022.
Wenhan Xiong, Chi-Lan--Giss Hoang, and William Yang Wang. DeepPath: A reinforcement learning method for knowledge graph reasoning. In Empirical Methods in Natural Language Processing (EMNLP), 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Represenlations, 2019.
Yao Xu, Shizhu He, Cai, Kang Liu, and Jun Zhao. Prediction and calibration: Complex reasoning over knowledge graph with bi-directional directed acyclic graph neural network. In Pindings of the Association for Computational Linguisties: ACL 2023, pp. 7189 7198, 2023a. URL attps://aclantholl .rr/ 2023. wwwdingnnnciiiiii acl.gs--cl..0 450..
Yao Xu, Shizhu He, Cunguang Wang, Li Cai, Kang Liu, and Jun Zhao. Query2Triple: Unified query encoding for answering diverse complex queries over knowledge graphs. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 11369 11382, 2023b. URL https://aclatthology .rr// 2023. fangsffidinns-emmp...
Zezhong Xu, Wen Zhang, Peng Ye, Hui Chen, and Huajun Chen. Neural-symbblli entangled framework for complex query answering. In Advances in Newral Information Processing Systems, 2022.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In International Conference on Learning Represenlations. 2015.
Dong Yang, Peijun Qing, Yang Li, Haonan Lu, and Xiaodong Lin. GammaE: Gamma embeddings for logical queries on knowledge graphs. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, pp.
Association for Computational Linguistics, 2022a.
Haotong Yang, Zhouchen Lin, and Muhan Zhang. Rethinking knowledge graph evaluation under the open-world assumption. In Advances in Neural Information Processing Systems, 2022b. URL https: //openreview. net/forum? wxt.mmddddxxuuttt....
Michihiro Yasunaga, Hongyu Ren, Antoine Bossclut, Percy Liang, and Jure Leskovee. QA-GNN: Rea- soning with language models and knowledge graphs for question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 535 546, Online, 2021. Association for Computational Linguistics. doi: 10.18653/ h0t0://1v2221////// aaaaalllaiiin... URL https://aclanthology www.aatoooooooooooooooooooo org/20211 baacl-main.. 45.
Gilad Ychudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Hang Yin, Zihao Wang, Weizhi Fei, and Yangqiu Song. FFFO,-CQA: Towards knowledge graph complex query answering beyond set operation. arXiv preprint ar ar1:22330711701,, 2023a.
Hang Yin, Zihao Wang, and Yangqiu Song. On existential first order queries inference on knowledge graphs arXiv preprint arXim:2904.0000 070663, 2023b.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexan- der J Smola. Deep sets. In Advances in Neural Information Processing Systems, volume 30, 2017.
Bohui Zhang, Filip llievski, and Pedro Szekely. Enriching wikidata with linked open data. arXiv preprint arXi::2207.00143 2022a.
54

---

Published in Transactions on Machine Learning Research (11/2024)
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In Advances in Neural Information Processing Systems, volume 34, pp. 9061 9073. Curran Associates, Inc., 2021a.
Wen Zhang, Jiaoyan Chen, Juan Li, Zezhong Xu, Jeff 7 Pan, and Huajun Chen. Knowledge graph reasoning with logics and emboddings: Survey and perspective. arXiv preprint arXi::2202.07/ 2022b.
Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, and Feng Wu. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. In Advances in Neural Information Processing Systems, 2021b.
Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. OOD link prediction generalization capabilities of peessageppsssng GNNs in larger Lest graphs. In Advances in Neural Information Processing Systems, 2022.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pasces Xhonneux, and Jian Tang, Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476 29490, 2021.
Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. Neural-symbolic models for logical queries on knowledge graphs. In International Conference on Machine Learning, ICML 2022, Proceedings of Machine Learning Research. PMLR, 2022.
55

---

Published in Transactions on Machine Learning Research (11/2024)
A Definitions and Theoretical Foundations
A.1 Types of Knowledge Graphs
Hyper-relational KGs generalize triple KGs by allowing edges to have relation-entity qualifiers. We define them as follows:
Definition A.1 (Hyper-relational Knowledge Graph derived from Alivanistos et al. (2022)) With E and R defined as in Definition 2.2, let Q = 2(Rx)),7 7 we define a hyper-relational knowledge graph In this case, the edge set S C (E x R x & x 2) consists of qualified stalements, where each C, ep) includes qp that represent contextual information for the main relation r. This ((qri.qei) (gr2, qe2)...) C R is the set of qualifier pairs, where {gri, QT2:, are
G = (E,
statement s = (e., T, cu.
set qp = [....... the qualifier relations and {qe1.qe2,... the qualifier entities.
We note that if & and R are finite sets, then also Q2 is finite and, there are only finite number of (r. gp) combinations possible. As a consoquence, we find that with these conditions, and by defining a canonical ordering over 22 we can represent the hyper-relational graph using first order logic by coining a new predicate Tap for each combination. The statement from the definition then be written as (e)
For example, one statement on hyper-rolationa KG in (Fig. 2) is (Hinton, education, Cambridge, { (degree, Bachelor)}). The qualifier pair (degree, Bachelor)} provides additional context to the main triple and helps to distinguish it from other education facts. the conditions mentioned above are met, we can write this statement as education ([agattin((dggeeBBaaaal [[dagree.Bachetor]] (Hinton, Cambridge).
Hyper-relational KGs can capture more diverse set of facts by using the additional qualifiers for facts on the graph.
This concept is closely related (albeit with different theoretical foundations) to the RDF-star format introduced in Hartig et al. (2022). RDF-star explicitly separates metadata (context) from data (statements). RDF-star allows us to use a triple as the subject or object of another triple, which gives the same expressive power than hyper-relational graphs. A core difference, affecting the way data is modeled, is that the identity of a triple is solely defined by its con- stituents. This means that if triple is used in two places, it is the same triple, which makes making complex statements about the triple more complicated (Fig. 21). For example, assume we want to express that Max Welling did his BSc thesis on flat universe in Utrecht and his PhD degree on gravity at the same university. With a hyper-relational graph we can make two edges. Each edge would state that Max Welling studied in Utrecht, but each would have two qualifier pairs with the corresponding topic and institute information. In RDF-star, we cannot model it with the same triple as subject of another triples, because RDF-star has no way to 'pair-up' the topic and degree level, and will instead think that the main triple has four pieces of information con- nected to it. The hyper-relational graphs introduced above do not have such issues. RDF-star further extends the values allowed in the object and qualifier value position to include literals, which we will discuss below in Definition A.3.
RDF
education
Welling
Utrecht
Oogres
toplc
Bachelor
PhD Gravity
Flat Universe
Hyper-Relational
education
educution
Utrecht
Welling
Utrecht
lupic
degane
degres
tapic
Gravity
PhD
Bachelor
Flat Universe
Figure 21: RDF-star and Hyper-relational Knowl- edge Graphs
Definition A.2 (Hypergraph Knowledge Graph) With E and R defined as in Desinition 2.2, hu-- pergraph KG is a graph G = (E, R) where statements S C (R x 2 are hyperedges. Such hyperedge s s= (r,e))= = (r, (.....,,,))) has one relation type r and links the entities together, where the order of these entilies not significunt. k, the size of e is called the arity of the hyperedge.
An example hyperedge in Fig. 2 is (education oeducation_degree, [Hinton, Cambridge, Bachelor)). This is 3-ary statement (being comprised of three entities). In contrast to hyper-relational KGs, hyperedges consist of
Given S. use the notation 2 to denote the powerset Here, R x denotes the Cartesian product of the of relations and the entities. So, (xEE)) denotes the containing all possible sets of pairs of relation and an entity.
56

---

Published in Transactions on Machine Learning Research (11/2024)
only one relation type and cannot naturally incorporate more fine-grained relational compositions. Instead, the type of the hyperedge is rather a merged set of statement relations and every composition leads to new relation type on hypergraph KGs. It is thus not as compositional as the hyper-relational KG. That is, when describing, for instance, a major relation of the education in (Hinton, Cambridge) fact, a hyper-relational KG can simply use it as a qualifier and retain both relations whereas a hypergraph model has to come up with a new hyperodge type education ceterttiiommajrr....... With a growing number of relations, such a strategy of creating new hyperedge relation types might lead to a combinatorial explosion. However, the hypergraph model is more suitable for representing relationships of varying arity, with equal contributions of all entities such as partnership (companyA, companyB, companyC).
Each of the graph types introduced above can be extended to also support literals. This happens by allowing nodes or qualifier values to contain a literal value. Literals contain numerical, categorical, discrete timestamps, or text data that cannot be easily discretized in an exhaustive set of possible values, like entities. Similarly to the Web Ontology Language (OWL, Motik al. (2009)) that distinguishes object properties that connect two entities from dalalype properlies that connect an entily and a literal, it is common to use the term relation for an edge between two entities, and attribute for an edge between an entity and a literal.
Definition A.3 (KG with Literals) With E and R as for one of the graph types above, a correspond- ing KG with literals Gz = (E, Rc, L) has an additional set of literals L C Con representing numer- ical, categorical, tertual, images, sound waves, or other continuous values (C is disjoint from E and R). If we eztend standard KGs to RDF graphs, literals can only be used in the objects position, that is In RDFF-tar graphs, literals can be objects or qualifier values, that is, Q = 2((XX(EC) and Se C (E x R x (EUL) x 22) For both of these, we could also define graph types with literals in other positions of the triples, as necessary, or introduce more complex substruclures in the elements of the triple (see e.g., Cochez (2012)). In hypergraph KGs, literals can be introduced in the elements of hyperedge, Sc C (R x 2EUC)
Sc C (E XXXXXXXXEUXX
If the set of possible statements of the KG with literals has the same finiteness properties as the one without literals, then the properties regarding expressing it using first order logic do not change, Some graphs like property graphs allow nodes to contain altributes, but this is equivalent with creating extra nodes with these attribute values and adding relations to those. In theory, also the edge type could be a literal, but since this can be modeled using a hyper-rclatonnal graph with literals, we exclude these from this work.
An example triple with literal object (Fig. 5) is (Cambridge, established, 1209). In (Hinton, education, Cambridge), education is relation, whereas in (Cambridge, established, 1209),
established is an attribute.
The knowledge graph definitions above are not exhaustive. It is possible to create graphs with other prop- erties. Examples include graphs with undirected edges, without edge labels, with time characteristics, with probabilistic or fuzzy relations, etc. Besides, it also possible to have graphs or edges with combined char- acteristics. One could, for instance, define a hyperedge with qualifying information. Because of this plethora of options, we decided to limit ourselves to the options above. In the next section we introduce how to query these graphs
A.2 Basic Approximate Graph Query Answering
Until now, we have assumed that our KG is complete, i.e., it is possible to exactly answer the queries. However, we are interested in the setting where we do not have the complete graph. The situation can be described as follows: Given a knowledge graph & (subset of complete, but not observable graph 9) and a basic graph query Q. Basic Approximate Graph Query Answering is the task of answering Q, without having access to G. Depending on the setting, an approach to this could have access to G, or to set of example (query, answer) pairs, which can be used to produce the answers (see also Section 7.3). In the example from
Both RDF and RDF-star also allow blank nodes used indicate entities without a specified identity in the subject and object position Brickley al. (2014). Besides, they also have support for named graphs (and in some cases for quadruples). We do not support these explicitly in our formalism, but all of these can be modeled using hyper-relational graphs.
57

---

Published in Transactions on Machine Learning Research (11/2024)
Fig. 1, several edges are drawn with dashes; these are true edges, but only there in the non-observable part of the graph G.
The goal is to find the answer set as if 9 was known. In this case, the complete answer set becomes {ui, {(pperson, Bengio). ( Funni U (e)u))),,,Leuun,, (Sumi, NYU))}, which includes the answer μ4 of the non-approximate version.
The query which includes the negation would have the following answers if our graph was complete: {[(ppesson, Bengio), ( (?uns, UdeM)), ((pperson,LeCae (Puni, NYU)),, which does not include μı.
Approximate Query Answering Systems provide a score E R for every possible mapping". Hence, the answer provided by these systems is a function from mappings (d.e., a μ)) to their corresponding score in R.
Definition A.4 (Basic Approximate Graph Query Answering) Given knowledge graph 9 (sub- graph of a complete, but not observable knowledge graph 9), a basic graph query Q, and the scoring domain R, a basic approximate graph query answer to the query Q is a function f which maps every possible mapping (p: Varq - Con) to R.
The objective is to make it such that the correct answers according to the graph 9 get a better score (are ranked higher, have a higher probability, have a higher truth value) than those which are not correct answers. However, it not guaranteed that answers which are in the observable graph G will get high score.
Table 15: Ordered scored map- pings for the example query. The
two wrong mappings are in red.
?person
?uni
score
For our example, possible mapping is visualized in Table 15. Each row in the table corresponds to one mapping μa. Ideally, all correct mappings should be ranked on top, and all others below. However, in this example we see several correct answers ranked high, but also two which are wrong.
Hinton
CofT
40
Bengio
UdeM
35
Welling
Cof
34
UdeM
Hinton
33
LeCun
NYU
32
A.3 Graph Query Answering
In the previous sections, we introduced the basic graph query and how it can be answered either exactly, or in an approximate graph querying setting. However, there is variation in what types of queries methods can answer; some only support a subset of our basic graph queries, while others support more complicated queries. In this section we will again focus on ezact thon-approzimate) query answering and look at some possible restrictions and then at extensions.
Definition A.5 (Graph Query Answering) Given a knowledge graph 9, a query formalism, and a graph query Q according to that formalism. An onswer to the query any mapping μ VVrq - Con such that the requirements of the query formalism are met. The set of all answers is the set of all such mappings.
For our basic graph queries introduced in Definition 2.4, the query formalism sets requirements as to what edges must and must not exist in the graph (Definition 2.5). In that context we already mentioned conjunctive queries, which exist either with (CQueg) without (CQ) negation. If the conditions for writing our graphs using first order logic (FOL) hold, we can equivalently write our basic graph queries in first order logic. Each variable in the query becomes existentially quantified, and the formula becomes a conjunction of 1) the terms formed from the triples in 5", and 2) the negation of the terms formed from the triples in S" Tf there are variables on the edges of the query graph, then we can rewrite the second order formula in first order logic, by interpreting them as a disjunction over all possible predicates from the finite number of options. Our example query from above becomes the following FOL sentence.
q 3pperson, Puni: win (nrrringg,ard,,
(person)) Peerson, Funi)
The answer to the query is the variable assignment function. For several of the more restrictive fragments, it is useful to formulate the queries using this FOL syntax.
9This score can indicate the rank of the mapping, a likellhood truth value, or binary indicating value. In some rases, only a partial mapping is provided. Anything not in this mapping has an implicit (xero or false) value.
58

---

Published in Transactions on Machine Learning Research (11/2024)
Cyclic Queries
DAG Queries
Tree Queries
Path Querles
C-0 D
O-0-0.0 0+0
0
constont
Figure 22: A space of query patterns and their relative expressiveness. Multi-hop reasoning systems tackle the simplest Palh queries. Existing complex query answering systems support Tree queries whereas DAG and Cyclic queries remain unanswerable by current neural models.
Restrictions The first restriction one can introduce are multi-hop queries, known in the NLP and KG literature for a long time (Guu et al., 2015; Das et al., 2017; Asai et al., 2020) mostly in the context of question answering. Formally, multi-hop queries (or path queries) are CQ which form a chain, where the tail of one projection head of the following projection, i.e.,
9path V&, 3V ..... Va-1 ril: V1) (2 V2) Ar-AAR Vi.
where v E E, Vi E [1,A] :, E R, E Var and all Vi are existentially quantified variables. In other words, path queries do not contain branch intersections and can be solved iteratively by fetching the neighbors of the nodes. One could also define multi-hop queries which allow negation.
Other ways of restricting CQ and CQneg: resulting in more expressive queries than the multi-hop ones exist. One can define families of logical queries shaped as Tree, DAG, and allowing cyelic parts. Illustrated in Fig. 22, path (multi-hop) queries form the least expressive set of logical queries. Tree queries add more reasoning branches connected by intersection operators, DAG queries drop the query tree requirement and allow queries to be directed acyclic graphs, and, finally, cyclic queries further drop the acyelic requirement. Note that these queries do not allow variables in the predicate position. Besides, all entities (in this context referred to as anchors) must occur before all variables in the topological ordering.
We claborate more on those query types in Section 6.2 and note that the majority of surveyod neural CLQA methods in Section 5 are still limited to Tree-like queries, falling behind the expressiveness of many graph database query languages. Bridging this gap is important avenue for future work.
Extensions
The first extension introduce is the union.
Definition A.6 (Union of Sets of Mappings) Given two sets of mappings (like p. from Definition 2.5), we create new set of mappings by taking their union. This union operator is commutative and asso- ciotive, we can hence also talk about the union of three or more mappings. It is permissible that the domains of the mappings in the input sets are not the same.
We can define new type of query by applying the union operation on the outcomes of two or more underlying queries. If these underlying queries are basic graph queries, we will call this new type of queries Unions of Conjunctive Queries with negation (UCQneg) and if the basic queries did not include negation, as Union of Conjunctive Queries (UCQ). These classes are also familiar from FOL, and indeed correspond to disjunction of conjunctions.
59

---

Published in Transactions on Machine Learning Research (11/2024)
As example, the following query is in UCQueg because it is a disjunction of conjunctive terms which consist of atoms or that are relation projections their negations:
= u. Ue Un
ri (1) 01) A (2)( V (Ta(()))s)) V v... V Th (Unn 2r)
43
Morcover, there are FOL fragments that are equivalent to these fragments. Specifically, all queries in EPFO, which are Existential Positive First Order sentences, have an equivalent query in LCQ, and all queries in EFO, Existential First Order sentences, have an equivalent query in UCQuee. The reason is that EPFO and EFO sentences can be written the Disjunctive Normal Form (DNF) as a union of conjunctive terms.
Some query languages, like SPARQL, allow an optional part to a query. In our formalism, we can define the optional part using the union operator. Assuming there are n optional parts in the query, create 2" different queries, in which other combinations of optional parts are removed. The answer to the query is then the union of the answers to all those queries. If the query language already allowed unions, then optionals do not make it more expressive.
Beyond these extensions, one could extend further to all queries one could express with FOL, which requires either universal quantification, or negation of conjunctions. These are, however, still not all possible graph queries. An example of interesting queries, which are not in FOL, are conjunctive regular path queries. These are akin to the path queries we discussed above, but without specified length.
Definition A.7 (Regular Path Query) A regular path query is a S-tuple (s, R), where s E Term the starting lerm of the path, Re E Term the relation term of the palh, and L E Term the ending lerm of the palh. The query represents a path starting in s, traversing an arbitrary number of edges of type R ending in t.
Because this kind of query is a conjunction of an arbitrary length, it cannot be represented in FOL. If one wants express paths with a fixed length, this would be multi-hop path like the one described above. If one wants to express maximum length, then this could be done using a union of all allowed lengths. For the two latter cases, the query can still be expressed in EPFO
Definition A.8 (Regular Path Query Answering) Given a knowledge graph G and a regular path query Q= (s, R, t). An answer to the query is any mapping p Varq + Con such that if we replace all variables in Q with p(v), oblaining (8, R. I), there exists path in the graph that slarts at node 8, then tranerses one or more edges of type Rg and ends in f. The set of all answers to the query is the set of all such mappings.
There exist several variations on regular path queries and they can also be combined with the above query types to form new ones. In Fig. 23 we illustrate how the fragments relate to other query classes. Most methods fall strictly within the EFO fragment, i.e., they only support a subset with restrictions as we discussed above. We will discuss further limitations of these methods in Section 6.
The two final aspects we want to highlight here are projections and joins.
Definition A.9 (Projection of a Query Answer) Given a query answer μ. and a set of variables V e Var. The projection of the query answer on the variables V is {waar, (al)) E μ,, var E V}.
In other words, it is the answer but restricted to a specific set of variables. The query forms introduced above can all be augmented with a projection to only obtain values for specific variables. This corresponds to the SELECT ?var clause in SPARQL. Alternatively, it is possible to project all variables in V which is equivalent to the SELECT * clause. A query without any projected variable is a Boolean subgraph matching problem equivalent to the ASK query in SPARQL.
A join is used to combine the results of two separate queries into one. Specifically,
Definition A.10 (Join of Query Answers) Given two query answers HA and μB, and Var and Varg the variables occurring in μa and PB, respectively. The join of these two onswers only crists in case they have the same value for all voriables they have in common, i.e., Year Var Varg : (a(var) = po(var). In that case, join(uA, uB) = PA U pn-
60

---

Published in Transactions on Machine Learning Research (11/2024)
Regular Path Queries
SPARQL, SPARQL* *
All Graph Queries
/PFO/
EFO UCQ
FOL
UCQ
Cypher
Figure 23: Current query answering models cover Existential Positive First Order (EPFO) and Existential First Order (EFO) logic fragments (marked a red rectangle). EPFO and EFO are equivalent to unions of conjunctions (UCQ), and those with atomic negation (UCQneg), respectively. These, in turn, are a subset of first order logic (FOL). FOL queries, in turn, are only subset of queries answerable by graph database languages. For example regular path queries cannot be expressed in FOL. Languages like SPARQL, SPARQL*, Cypher, encompass all the query types and more.
Given two sets of answers, their join is defined as follows.
Definition A.11 (Join of Query Answer Sets) Given two sets of query onswers and B, the join of these two is new set join(A, B) (join(a, b)la e A,b E B, and join(a, b) exists).
This operation enables us to combine multiple underlying queries, potentially of multiple types into a single one. For example, given the sot of answers from our example basic graph query above:
A ([erpeoo Hinton), (fumi, Uo {{ (pperson, Bengio), (Pumi, UdeM)), {{ ((pperson, LeCun), ( (Suni, NYU)) and another set of answers
[[pperson, Hinton), (Sborn, 1947)), ((Pperson, Bengio), ( (bbrrn, 1964)), {(yperson, Welling), (fborn, 1968)
The join of these becomes:
join(A, B) {[( ((pperoon, Hinton), (Purú, UofT), ( (bborn, 1947)}, {(pperson, (engrosn,,Bnngio) (?uni, UdeM), (?born, 1964))}
We will discuss joins further Section 6.1, where we will use these basic building blocks to define a broader set of query operators, aiming cover all operations that exist in SPARQL. This includes Kleene plus/star (+/*) for building property paths, FILTER, OPTIONAL, and different aggregation functions.
A.4 Triangular Norms and Conorms
Answering logical queries implies execution of logical operators. Approximate query answering, in turn, implies contimuous vector inputs and output truth values that are not necessarily binary. Besides, the methods often require that the logical operators are smooth and differentiable. Triangular norms (T-norms) and triangular conorms (T-conorms) define functions that generalize logical conjunction and disjunction, respcctively, to the continuous space of truth values and implement fuzzy logical operations.
T-norm defines continuous function T [0, 1] [0,
[0, with the following properties T(x,y) xy, (commutativity), T(x, =),,)) T(T (z, 2) (associativity), and
T(x,y) < T(z, 2) (monotonicity). Also, the identity element for T is 1, ie., T(x, x. The goal of t-norms is to generalize logical conjunction with a continuous function. The T-conorm can be seen as a duality of a t-norm that similarly defines a function 1 with the same domain and range 1 [0, x [0, + [o, 1]. T-conorms use the continuous function 1 to generalize disjunction to fuzzy logic. The function satisfics the same commutativity, associativity, and monotonicity properties as T, but with 0 the identity element, i.e.,
1. (xr, x.
61

---

Published in Transactions on Machine Learning Research (11/2024)
There exist many triangular norms, conorms, and fuzzy negations (Klement et al., 2013; van Kricken et al., 2022) that stem from corresponding logical formalisms, e.g., (1) Gödel logic defines t-norm: T (x; y)
min(a, y), t-conorm: -max = max(æ, y); (2) Product logic with t-norm: Tro y) = x t-
conorm: (x, 3) = x + ---- x yi (3) in the Lukasiewicz logic t-norm: TLuk(Z, y) = max(2 + y 1,0),
1-conorm:
Luk Lukk(r)))) (r,y) min(æ + y. 1). Using fuzay negation, N(x) = 1 2; one can verily that
_(x, v) = N(T) (De Morgan's laws) naturally obtaining a pair of (T,
A.5 Graph Representation Learning
Graph Reprosentation Learning (GRL) is a subfield of machine learning aiming at learning low-dimensional vector representations of graphs or their elements such as single nodes (Hamilton, 2020). For example, he E IRd denotes a d-dimensional vector associated with a node v. Conceptually, we want nodes that share certain structural or semantic fcatures in the graph to have similar vector represcntations (where similarity is often measured by distance function).
Shallow Embeddings The first GRL approaches focused on learning shallow node embeddings, that is, learning a unique vector per node directly used in the optimization task. For homogeneous (single-relation) graphs Deep Walk (Perozzi et al., 2014) and node2vec (Grover & Leskovee, 2016) trained node embeddings on the task of predicting walks in the graph whereas in multi-relational graphs TransE (Bordes et al., 2013) trained node and edge type embeddings in the autoencoder fashion by reconstructing the adjacency matrix.
Graph Neural Networks The idea of graph neural networks (GNNs) (Scarselli et al., 2008) implies learning a wetk encoder with shared parameters on top of given (or learnable) node features by performing neighborhood aggregation. This framework can be generalized to message passing (Gilmer et al., 2017) where at each layer / a node v receives messages from its neighbors (possibly adding edge and graph features), aggregates the messages in permutationninvariant way, and updates the representation:
h UPDATE h(--1,, AGGREGATEEENNN (MESSAAGE (MESSAGE(H(-)) h(-1), ewvll)
Here, hy is a feature of the neighboring node u, Cur is the edge feature, the MESSAGE function builds a message from node u node v and can be parameterized with neural network. As the set of neighbors N(v) is unordered, AcCREGATE is often a permutation-invarian function like sum or mean. The UPDATE function takes the previous node state and aggregated messages of the neighbors to produce the final state of the node v at layer t and can be parameterized with a neural network as well.
Classical GNN architectures like GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2018), and GIN (Xu et al., 2019) were designed to work with homogeneous, single-relation graphs. Later, several works have developed GNN architectures that work on heterogeneous graphs with multiple relations (Schlichtkrull al., 2018; Vashishth et al., 2020; Zhu et al., 2021). GNNs and message passing paved the way for Geometric Deep Learning (Bronstein et al., 2021) that leverages symmetries and invariances in the input data inductive bias for building deep learning models.
B CLQA vs KGQA
KG-based question answering (KGQA) (Chakraborty al., 2021) is the adjacent sub-field tackling natural language questions and multi-hop reasoning over structured data. The input of a typical KGQA model is a question posed in natural language, and, given background graph, the output is set of possible answer entitios. While CLQA and KGQA are similar in terms of tackling complex multi-hop questions (and perhaps spanning over several modalities), KGQA approaches are rather different for the following reasons:
Most often, the graphs in KGQA tasks are assumed be complete and do not require predicting any missing links at inference time. This assumption significantly simplifies the prediction task and
62

---

Published in Transactions on Machine Learning Research (11/2024)
enables two main branches of KGQA models, i.e., (1) semantic parsing from natural language question to a SPARQI. query (Keysers et al., 2020) where the main challenge is compositional generalization to unseen combinations of relations; (2) retrieval-based LLM approaches (Yasunaga et al., 2021; Back et al., 2023; Hc et al., 2024) where the main challenge is to maximize the recall of extracted candidate subgraphs and re-rank those to predict the answers. Some approaches that support predicting missing links on the fly rely on pre-trained shallow KG embeddings (Saxena et al., 2020) which, essentially, perform 1p relation projection step. As retrieval-based techniques are better amenable to other modalities, extending KGQA to support images and scene graphs is also possible (Wang et al., 2023c).
The majority of KGQA benchmarks include only projection (such as 2p) and intersection queries (æi / /i) thus missing out on unions and negations.
Since the query is posed in natural language, KGQA pipelines often rely on entity linking modules tailored a specific graph (to map a string to an entity ID in the graph). Besides being an external component with possible error propagation, it hampers generalization capabilities of the models, e.g., a KGQA pipeline with a tailored entity linker cannot generalize to unseen graphs. In contrast, the languago-agnostic nature of CLQA allows to train graph reasoning models that generalize lo complex queries over completely unseen KGs at inference time (Galkin et al., 2024).
We believe that the synergy between CLQA and KGQA achievable by combining the best from the both worlds, e-g,, inductive and generalizable reasoning over complex queries while predicting missing links (from CLQA), and deriving logical forms from the questions along with efficient retricval mechanisms for faster scoring of relation projections (from KGQA).
63


Reviews:
[{"review_id": "FshoXA36AP", "reviewer": "Reviewer_qV59", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- I can see this work as a go to survey paper for neural graph research. The literature review is extensive and I was pleased to see that the authors kept it up to date from their previous submission.\n\n- The paper is well written and structured. I really enjoyed seeing the delineation of the related work given the different axes. I also appreciated the authors' effort to provide a comprehensive background section with definitions for neural graph and graph query answering.\n\n- The open challenges section at the end was clear and a valuable to any researchers wanting to jump into this field.\n\n**Weaknesses**\n- I would have appreciated to see some concrete performance results to see which methods are better than others in the different settings. For instance, if I have a particular setting in mind, I wouldn't know which methods to consider in the first place. That said, I understand that this is a survey paper, and the authors might have chosen to focus on the literature review. I can only hope for a follow up paper that would provide such results (maybe a benchmark? that would be a great contribution).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presents a comprehensive survey of query reasoning methods over graph databases. The survey delineates existing works (~50 papers) along three main axes: Graphs (e.g., underlying structure), Modeling (e.g., query/graph encoders, decoding strategies), and Queries (e.g., operators' expressiveness, patterns complexity). The paper also touches on the evaluation metrics commonly used and ends on what are the open challenges for each of presented axes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Irrespective of the highlighted weakness, I like the current version of the submission. Here is two minor changes the authors might wish to consider: \n- I'm not sure I understand the purpose of Table 16. It seems to be all the information are already present in Table 15?\n- In section 2, binary sets are defined according to other sets instead of their cardinality. Maybe it is a valid notation that I'm unaware of? For instance,\n  - p.5: $\\mathfrak{Q}=2^{(\\mathcal{R}\\times \\mathcal{E})}$ vs. $\\mathfrak{Q}=2^{|\\mathcal{R}\\times \\mathcal{E}|}$\n\nAlso, here are some typos:\n- p.5: \"which gives is the same\" -> \"which gives the same\"\n- p.5: \"This means that is a triple\" -> \"This means that a triple\"\n- p.8: Just before Definition 2.10, \"to FOL fragments\". FOL is only defined two paragraphs later.\n- p.9: \"restricting CQ and on CQ_neg\" ->  \"... and CQ_neg\" ?\n- p.12: \"the identity element for T is 1, i.e., T(x,1)=1\" -> T(x,1)=x ?\n- p.12: \"on can verify\" -> \"one can verify\"\n- p.21: \"... Section 7.3) However...\" <- missing point.\n- p.34, Footnote 7: Missing end of sentence.\n- p.35: \"strong closture\" -> closure\n- p.37: Unbalanced parenthesis in \"the clause COUNT (?book) as ?n)\"\n- p.45: \"from the Inferece\" -> Inference\n- p.48: \"open challenges Adhering\" <- missing point\n- p.49: Unbalanced parenthesis in \"... negations (UCQ and UCQ_neg and aiming ...\"", "broader_impact_concerns": "I don't see any particular concerns on the ethical implications of this survey paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rzwS8ruNnh", "reviewer": "Reviewer_9uMg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe paper is comprehensive from graph ML perspective. It discusses literature on different types of graphs, different modeling focuses (e.g., encoding, decoding), different types of queries, and different benchmarks and metrics. The papers discussed in the survey are up-to-date. \n\nThe paper is generally well-written. The technical discussion is often accompanied with clear visualization. \n\nWeaknesses \n\nMulti-hop reasoning is also a popular and long-standing (not \"emerging\") topic in NLP. But this connection is not discussed. Arguably, the \"graphs\" in NLP are largely unstructured or less-structured (e.g., wikipedia articles connected by hyperlinks or lexical matches), so it is not at the core of this survey area, but it is highly related. \n\nThe discussion of future research directions are vague and generic. It merely lists some possible tasks / problems that past work has not covered yet, without providing insights about why it is not covered, or why it is a meaningful future direction. E.g., one future direction is to consider \"hypergraphs\", but section 2.1 implies that this formalism is restricted (and thus not very useful?), making me wonder if this direction is actually meaningful. This concern applies to other items in this section.  \n\nThe writing has some grammatical errors. E.g., in page-5, \"This means that is a triple is used in two places\"...", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a comprehensive survey on complex logical query answering (CLQA), a task of graph machine learning that goes beyond one-hop link prediction to multi-hop logical reasoning over large-scale and potentially incomplete graphs. This paper discusses literature in this area from different perspectives, including graph formalism, modeling focuses, types of queries, data and metrics, and applications. The final section points out several directions for future research.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would recommend that the authors \n- discuss multi-hop reasoning work in NLP and their relations / differences with the main focus of this survey\n- be more specific and provide technical insights for meaningful future directions\n- fix their grammatical errors", "broader_impact_concerns": "No concerns for broad impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DnCB8GRsFr", "reviewer": "Reviewer_dRok", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I'll briefly state the strengths/weaknesses of this survey, and will then focus\nmore on areas that I feel require work.\n\nS1. Comprehensive: captures the quite large amount of recent work in this area\n\nS2. Timely: this is a highly active reserach field at the moment\n\nS3. In need: there is no such survey, as far as I know\n\nS4. Useful taxonomy\n\nS5. Many useful overview tables\n\nW1. Presentation: let down by suboptimal structure/focus and, partly, lack of intuition\n\nW2. Discussion: rarely provides thoughtful discussion or criticism\n\nW3. Related areas ignored\n\nOn W1. There are three main issues with the presentation.\n\n(i) The survey lacks focus. Most notably, there is a more than 15-page long disucssion on preliminaries, which is largely not needed (and especially in this level of formality) for the later chapters. In contrast, the discussion of the key techniques (Ch. 5) and training (Ch. 7.3) falls short. The amount of space allocated to a topic should match its relevance for this survey.\n\n(ii) The structure of the presentation is not optimal. The presentation is strictly sequential (first all kinds of graph models, then all kinds of neural models, then all kinds of query models, then training/evaluation). While this may make sense at first glance, this makes the survey quite painful to read and quite repetitive. For example, when discussing neural methods in Ch. 5, the dicussion is very hard to follow without some of the notions introduced in Ch. 6 (e.g., that the models represent partial query results as embeddings). I feel that the discussion makes sense when the key points are already known, but it otherwise quite inaccessible. I feel that Ch. 2 can mostly go and Ch. 4--7 need to be more tightly integrated (and hence rewritten). It may help to start with plain KGs + tree-graphs and then expand from there, for example, or to start off with a much higher-level discussion of the key points for neural query processing before delving into details (e.g., in a new overview chapter with forward pointers).\n\n(iii) Intuition party lacking. The paper quite often describes what is done, but does not convery the intuition behind the approaches or why certain things are done in certain ways. Although this is often clear to me (as I know some of the literature), it is not cleary exposed in the paper. As a simple example: why are relations translated by addition? Why does Query2Box use boxes and what do these boxes represent?\n\nOn W2. Many of the methods are presented in a descriptive style, but there is little comparitive discussion and little criticism and unclear takeways. After reading the survey, one wonders how all the methods compare to each other, what their respective strengths and weaknesses are, and where the general limitations lie. I understand that this is immensely difficult to do, but I do feel that a survey should strive for at least some insightful dicussion or identify limitations.\n\nOn W3. This work is related to KGQA (knowledge graph question answering, in particular, textual queries/features) and link prediction (single-hop queries). Many of the issues raised in this work also appear in these related areas (e.g., handling unseen entities or textual features such as entity names/descriptions). It's clear that this survey does (and needs to) focus on CQA, but it still should work out connections to these related lines of work.\n\nDetailed comments:\n\nD1. In principle, single-hop and rule-based methods can be used to \"complete\" the graph and perform CQA then. Clearly, this is limited but should be mentioned / related to CQA.\n\nD2. The description of graphs is overly formal. That's not at all needed for the purpose of this survey.\n\nD3. Hyper-Relational KGs and Hypergraph KGs are quite esoteric, as the tables of works that use them given in the survey also show. They have way too much focus in the presentation. (Also, I wonder about the concept of a \"main relation\" instead of simply using k-ary relations.)\n\nD4. I suggest to always present intuition/high-level ideas before the details. E.g., for Def 2.7., first say that a query is a positive pattern and a negative pattern, then give the definition.\n\nD5. Var_Q as defined on p. 7 does not contain the variables in the relation slots.\n\nD6. The discusson of query expressiveness/types is scattered throughout chapter 2, but then also arises later on again. I feel that it would help to define the noteion of a query answer (exact, approximate) ONCE and generally; right now it's defined multiple times (e.g., Def 2.9 and 2.17) and answer and query types are mingled together.\n\nD7. The answer semantics seems to use the CWA assumption, but it's not mentioend discussed. This matter in particular since the assumption is then broken later on.\n\nD8. The query processing problem is not really well defined. Especially, G and Ghat clearly need to be related in some way. This is even more relevant when queries have negations, since Ghat can invalidate any query result on G.\n\nD9. There is no diucssion around why approximate methods procude scores. Also, some methods may not; e.g., certain generative methods, and the practical implications of this choice ar not discussed. (It's clear that this is how the methods currently work, but a survey should provide context and point out potential limitations.)\n\nD10. The mix of query languages (SPARQL, FOL, relation projections later on) is quite confusing.\n\nD11. Approximate query answering raises all kind of questions around semantics and consistency. I think a key point is that there is often no well-defined semantics and answers can be inconsistent across queries, the methods just procude scores along Def. 2.17. This is very different to, say, probabilistic databases.\n\nD12. The t-norm discusison is only used once much later, and would be better placed there.\n\nD13. Multi-modal QA has been addressed in, say, the NLP and CV communities. It's weird that this field is empty in Tab. 2.\n\nD14. TAb 2/3/4 do not feel particularly insightful, as few methods actually do this. The discussion around these tables feels more like a side note, but is placed very prominently before the actual neural methods are discussed. I'd prefer a survey that puts key points first and potential extensions/directions later.\n\nD15. Fig 11: use subfigures, the boxes are hard to spot.\n\nD16. The difference between \"shallow embedding\" and \"transductive encoder\" is unclear to me.\n\nD17. Generally, it does not become sufficently clear in Fig. 11/Sec. 5.1 what the output of the encoder actually is (or can be). This relates to point W1(ii).\n\nD18. Tables like Tab 5 are hard to read. I'd find it more insightful if rows were methods and columns properties. This way, multiple tables (e.g., Tab 5 and Tab 6) could be integrated and provide a more holistic overview of the considered methods.\n\nD19. More generaelly, the methods are often mentioned \"in passing\", but there is no accessible general overview.\n\nD20. Downside (1) of shallow methods is unclear to me.\n\nD21. The distinction between neural and neural-symbolic processors is not clear to me.\n\nD22. Tables on top, not in text, improve readability.\n\nD23. The survey argues that union and negation are not well-defiend in latent space, hence many methods only support relation projection and intersection. But are those well-defined in latent space? How?\n\nD24. Fig 12 (esp. left) is confusing and not sufficiently discussed in text.\n\nD25. When talking about neural processors, relation projection and, say, conversion to DNF have not been discussed yet, but are already used throughout. This is an example of suboptimal structure.\n\nD26. Tab 7, DistMult-m/ComplEx-m -- relation projection correct? (L2Norm would destroy the embedding and produce a single real)\n\nD27. In Tab 7, cklickable refs + conference would be helpful.\n\nD28. Before discussion geometric/probaiblistic processors, the notion of representing possible values of a variable needs to be present, but that's (again) discussed only later.\n\nD29. Unclear to me: \"probabilitic processors are similar to geometric processors\"\n\nD30. Ch. 5.3 uses the word \"non-parametric\" in a non-standard fashion. What is meant is \"learned/pre-defined\" instead of \"paramteric/non-parameteric\".\n\nD31. At the end of Ch. 5, I wondered: so what? There is no discussion about the expressibity/quality/cost of these methods.\n\nD32. For discustions, the theorem of Ren et al should be paraphrased to be self-contained. Also, what is M? (Defined in Ren et al., but not here.)\n\nD33. Footnote 7 is incomplete.\n\nD34. In principle, regular path queries (i.e., a single relation type) can be handled by all methods by adding a relation R+ for the transitive closure of R.\n\nD35. Fig 19 has the right level of detail/formalism required for query types.\n\nD36. It's stated that neural methods \"assume that the underlying graph is incomplete and queries may have some missing answers\". I am not sure I'd agree: It appears that quite some of these methods are trained with CWA, but have limited capacity and hence can generalize.\n\nD37. Fig 19/20/21 can be merged.\n\nD38. The common term for \"zero projected variabels\" is Boolean queries. Also, at least in principle, all other quries can be reduced to Boolean queries by \"trying\" all possible answers.\n\nD39. Ch. 7 introduces a new notation for answers. Why not use this before?\n\nD40. Training comes very hort, just a paragraph. Isn't there more to say? Are there differences in training methods other than loss (e.g., query sampling stategies, negative sampling) and what's the general cost?\n\nD41. Inductive (superset) / inductive (disjoint) is termed semi-inductive / fully-inductive in the literature.\n\nD42. Tab 15 is a useful overview of datasets. An overview like this for methods would be great (see comment D18).\n\nD43. Tab 16 appears incomplete. For example, there are methods to handle unseen entities in KGQA/single-hop methods.\n\nD44. The application section is disappointing. The methods are claerly not used so far. That's ok, but: why not? what's missing?\n\nD45. Likewise, the summary/conclusion falls short. It list mainly features that would be nice to have, but does not work out / ask to address key weaknesses of current methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper surveys recent work on neural methods for complex query answering. It\ncaptures the main aspects of (i) graph / data models, (ii) neural query\nprocessing, (iii) query types, (iv) evaluation.\n\nGenerally, the survey is comprehensive and fills a gap in the literature. I feel\nthat such a survey is a valueable contribution to TMLR, and I'd ultimately would\nlike to see it accepted. At present, however, I feel that the survey needs\nrevision in two key directions: (W1) presentation and (W2) discussion.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Address W1; W2+W3 to the extent feasible", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: - The paper is comprehensive and timely, capturing a large amount of recent work in the field.

- It provides a useful taxonomy and many overview tables.

- It is well-written and structured, with clear visualizations.

- It is considered a go-to survey for neural graph research

All the reviewers are positive about the paper. I recommend acceptance.
Decision: Accept (poster)