Query Embedding on Hyper-Relational Knowledge Graphs
Authors: Dimitrios Alivanistos
Max Berrendorf
Michael Cochez
Mikhail Galkin
Venue: ICLR 2022 Poster (2022)
Keywords: Query embedding
Approximate Query Answering
Graph Neural Network
Hyper-relational Graph
Knowledge Graph

Abstract: Multi-hop logical reasoning is an established problem in the field of representation learning on knowledge graphs (KGs). It subsumes both one-hop link prediction as well as other more complex types of logical queries. Existing algorithms operate only on classical, triple-based graphs, whereas modern KGs often employ a hyper-relational modeling paradigm. In this paradigm, typed edges may have several key-value pairs known as qualifiers that provide fine-grained context for facts. In queries, this context modifies the meaning of relations, and usually reduces the answer set. Hyper-relational queries are often observed in real-world KG applications, and existing approaches for approximate query answering cannot make use of qualifier pairs. In this work, we bridge this gap and extend the multi-hop reasoning problem to hyper-relational KGs allowing to tackle this new type of complex queries. Building upon recent advancements in Graph Neural Networks and query embedding techniques, we study how to embed and answer hyper-relational conjunctive queries. Besides that, we propose a method to answer such queries and demonstrate in our experiments that qualifiers improve query answering on a diverse set of query patterns.

Published as a conference paper at ICLR 2022
QUERY EMBEDDING
ON HYPER-RELATIONAL KNOWLEDGE GRAPHS
Dimitrios Alivanistos Max Berrendorf, Michael Cochez! and Mikhail Galkin Vrije Universiteit Amsterdam, "LU Munich, Mila, McGill University,
4 Discovery Lab, Elsevier
d. al wwliiaanistssvu...m n1, berrendorf@dss ifi 1mu. de,
m. wwcheeevu. minkhhi mikhail. galkin@miaal le queeue
ABSTRACT
Multi-hop logical reasoning is an established problem in the field representatinn learning on knowledge graphs (KGs). It subsumes both one-hop link prediction as well as other more complex types of logical queries. However, existing algo- rithms operate only classical, triple-based graphs, whereas modern KGs often employ a hyper-relational modeling paradigm. In this paradigm, typed edges may have several key-value pairs known as qualifiers that provide fine-grained context for facts. In queries, this context modifies the meaning of relations, and usually reduces the answer set. Hyper-relational queries are often observed in real-world KG applications, and existing approaches for approximate query answering (QA) cannot make use of qualifier pairs. In this work, we bridge this gap and extend the multi-hop reasoning problem to hyper-relational KGs allowing to tackle this new type of complex queries. Building upon recent advancements in Graph Neural Networks and query embedding techniques, we study how to embed and answer hyper-relations conjunctive queries. Besides that, we propose a method to answer such queries and demonstrate in experiments that qualifiers improve QA on diverse set of query patterns.
INTRODUCTION
Query embedding (QE) on knowledge graphs (KGs) aims to answer logical queries using neural reasoners instead of traditional databases and query languages. Traditionally, KG is initially loaded into a database that understands a particular query language, c.g., SPARQL. The logic of query is encoded into conjunctive graph patterns, variables, and common operators such as joins or unions.
On the other hand, QE bypasses the need for a database or query engine and performs reasoning directly in a latent space by computing a similarity score between the query representation and entity representations]] A query representation is obtained by processing its equivalent logical formula where joins become intersections (A). and variables are existentially quantified (E). A flurry of
recent QE approaches (Hamilton et al. 2018 Ren et al. 2020 Ren & Leskovec) 2020 Kotnis et al.)
2020 Arakelyan et al. 2021) expand the range of supported logical operators and graph patterns.
However, all existing QE models work only on classical, triple-based KGs. In contrast, an increas- ing amount of publicly available (Vrandečić & Krötzsch 2014] Suchanek et al. (007)) and industrial KGs adopt hyper-relational modeling paradigm where typed edges may have additional attributes, in the form of key-value pairs, known as qualifiers. Several standardization efforts embody this paradigm, i.e., RDF* (Hartig) 2017) and Labeled Property Graphs (LPG with their query lan- guages SPARQL* and GQL, respectively. Such hyper-relational queries involving qualifiers are instances of higher-order logical queries, and far, there has been attempt bring neural rea- soners to this domain.
In this work, we bridge this gap and propose neural framework to extend the QE problem to hyper-relational KGs enabling answering more complex queries. Specifically, we focus on logical
"xiisting @p operate only on the entity level and cannot have relations as variables https: www. iso wtt..i.///taanarr.oo.o/o// html

---

Published as a conference paper at ICLR 2022
university where the who discovered of the photoelectrii effect got cslucaved?"
"What universitt one discovered of the photoelestric effect & ge hicher BSc, degree?
POL.
W a.Pasccoerrdd P) educated (t(PU)
T 3..dsccovered by(L, educated at ((eggrees))))) (P.C)
Quary Spare
Segracttiee
Anower
Answer
photoelectrs effees
VAR,
Tnrger
photocloc
VAR
Thrget
diconenol by
educated
disovereed by
daacrrl at
Zuka
ETH Zunich
Embeddding Space
Uzivessiy Zuzidy
ETH Zurich
Zurich
QE
oarich
University
University of Zurich
Zuric
Figure Triple-based (left) and hyper-relational (right) queries. The answer set of the hyper- relational query is reduced with the addition of qualifier pair, and the final query representation moves closer to the narrowed down answer.
queries that use conjunctions (A) and existential quantifiers (3), where the function symbols parameterized with the qualifiers of the relation. This parameterization enables us (cf. Fig. D to answer queries like What the university U where the one who discovered the law of the photoelec- tric effect L got his/her BSc. degree?, which can be written as ?U LP A educated at ((aggre::BSc)) UP.
Our contributions towards this problem are four-fold. First, as higher-order queries are intractable practical scale, we show how express such queries terms of a subset of first-order logic (FOL) well-explored in the literature. Second, we build upon recent advancements in Graph Neural Networks (GNNs) and propose method to answer conjunctive hyper-relational queries in latent space. Then, we validate our approach by demonstrating empirically that qualifiers significantly improve query answering (QA) accuracy on a diverse set of query patterns. Finally, we show the robustness of our hyper-relational QA model to reification mechanism commonly used in graph databases to store such graphs on a physical level.
2 RELATED WORK
Query Embedding. The foundations of neural query answering and query embeddings laid in GQE (Hamilton et al. 2018) considered conjunctive (^) queries with existential (E) quantifiers modeled as geometrie operators based on Deep Sets (Zaheer al. 2017). Its further extension, QUERY2BOX (Ren et al. 2020), proposed to represent queries as hyper-rectangles instead of points in latent space. Geometrical operations
those rectangles allowed to answer queries with dis- junction (V) re-written in the Disjunctive Normal Form (DNF). Changing the query representation form to beta distributions enabled BETAE (Ren & Leskoved 2020) to tackle queries with negation (-), Another improvement over QUERY2BOX as to answering entailment queries was suggested in EMQL (Sun al. 2020) by using count-min min sketches.
The other family of approaches represents queries as Directed Acyelic Graphs (DAGs). MPQE (Daza & Cochez 2020) assumes variables and targets as nodes in a query graph and ap- plies an R-GCN (Schlichtkrull et al.) 2018) encoder over it. It was shown that message passing demonstrates promising generalization capabilities (i.e., when training only on 1-hop queries and evaluating more complex patterns). Additional gains are brought when the number of R-GCN layers is equal to the graph diameter. Treating the query DAG as a fully-connected (clique) graph, BIQE (Kotiis al. 2020) applied Transformer encoder (Vaswani et al. 2017) and allowed to answer queries with multiple targets at different positions a graph.
Finally, CQD (Arakelyan al. 2021) showed that is possible to answer complex queries without an explicit query representation. Instead, CQD decomposes a query in sequence of reasoning steps and performs beam search in latent space of KG embeddings models pre-trained simple 1-
2

---

Published as a conference paper at ICLR 2022
hop link prediction task. A particular novelty of this approach is that no end-to-end training complex queries is required, and any trained embedding model of the existing abundance (Ali et al. 2020
et al. 2020) can be employed is.
Still, all of the described approaches are limited to triple-based KGs while we extend the QE problem to the domain of hyper-relational KGs. As our approach is based query graphs, we investigate some of MPQE observations as to query diameter and generalization (see also Appendix (
Hyper-relational KG Embedding. Due to its novelty, embedding hyper-relational KG is field of ongoing research. Most of the few existing models are end-to-end decoder-only CNNs (Rosso et al., 2020 Guan et al. 2020) limited 1-hop link prediction, i.e., embeddings of entities and relations are stacked and passed through a CNN to score a statement. On the encoder side, we are only aware of STARE (Galkin et 2020) work in the hyper-relational setting. STARE extends the message passing framework of CompGCN (Vashishth et al. 2020) by composing qualifiers and aggregating their representations with the primary relation of statement.
Inspired by the analysis of (Rosso et al.) 2020), we take closer look at comparing hyper-relational queries against their reified counterparts (transformed into a triple-only form). We also adopt STARE (Galkin et al., (020) as a basic query graph encoder and further extend it with attentional aggregators akin to GAT (Veličković al. 2018).
HYPER-RESE RELATIRELAI KNOWLEDGE GRAPHS AND QUERIES
Definition 3.1 (Hyper-relational Knowledge Graph), Given a finite set of entities &, and a set of relations R, let Q = 2(xxE), Then, we define a hyper-relational knowledge graph as 9 = (E,R,
where S C (E R x x Q2) is a set of (qualified) statements.
For a single statement s = (h, r, t, qp), we call h, t E E the head and tail entity, and r E R the (main) relation. This also indicates the direction of the relation from head to tail. The triple (h, r, also called the main triple. q = {q = { pairs, where (gri,qr2,... are the qualifier relations and (ge1, gec,,-ee.--- the qualifier values.
C R. x E is the set of qualifier
Hyper-relational KGs extend traditional KGs by enabling to qualify triples. In this work, we solely use hyper-relational KGs and hence use "KG" to denote this variant. The qualifier pair set provides additional information for the semantic interpretation of the main triple (h, (). For in- stance, consider the statement (AlbertEinstein, educated_at, ETHZurich, {ddegree, BSc))): ) Here, the qualifier pair (degree, BSc) gives additional context on the base triple (AlbertEinstein. educated at, ETHZurich) (also illustrated on Fig. [T.
Note that this statement can cquivalently be written in first order logic (FOL). Specifically, we can write it as statement with a parameterized predicate ETHZurich). Then, we note that Q is finite
educated at ((dggree:Bc)) (Allereeee))lleeerinnnnttee (AlbertEinstein set, meaning that also the number of different parameterizations for the predicate is finite, which means that this becomes a first order logic statement. In this formalism, the KG is the conjunction of all FOL statements. Possible monotonicity concerns are discussed in Appendix
We define hyper-relational query hyper-rclational KG as follows
Definition 3.2 (Hyper-relational Query). Let V be set of variable symbols, and TAR E V a special variable denoting the target of the query. Let g+ = VV.. Then, any subset Q of x x g+ x Q) a valid query if induced graph 1) is a directed acyelic graph, 2) has a topological ordering in which all entities (in this context referred to as anchors) occur before all variables, and 3) TAR must be last in the topological orderings!"
The answers (Q) to the query Q are the entities e e E that can be assigned to TAR, for which there exist variable assignment for all other variables occurring in the query graph, such that the instantiated query graph is a subgraph of the complete graph G.
3 TThe queries considered here are a subset SPARQL basic graph pattern queries.
'These requirements common in the literature, and usually stated with formal logic, but not striet requirement for approach. See Appendix F for more information.
3

---

Published as a conference paper at ICLR 2022
BSc
9
Photo electric effect
?var
?target
B.y (x(t:
W
mi -try
Figure 2: StarE layer intuition: (1) aggregation "y of qualifiers into a single vector; (2) aggregation 6, of a main relation with qualifiers vector; (3) composition of an enriched relation with the head entity; (4) final message to the tail node.
Problem Definition, Given the incomplete KG G (part of the not observable complete KG 9) and a query Q Rank all entities in G such that answers to the query, if were asked in the context of the complete KG 9, are at the top of the ranking.
Since the given KG is not complete, we cannot solve this problem directly as a graph matching problem as usually done databases. Instead, we compute latent representation of the query. such that it is close to the embeddings of entities which are the correct answers to the query.
4 MODEL DESCRIPTION
Our model is not trained directly on the KG, but rather with a set of queries sampled from (see Sec- 5.11. Hence, to describe our model, we consider query Q C (3+ x R x E x 12). and describe how we learn to represent it. Our model can be seen as a combination of MPQE (Daza & Cochez 2020 and StarE (Galkin et al. 2020) with CompGCN (Vashishth al. 2020) architecture.
Our model learns representations for entities and the special symbols ((VAR, TARJ), E [(((+))xx and relation representations R E | where d is hyper-parameter indicat- ing the embedding dimension. There are two representations for each relation. For a statement (h, qp) Q, one is used for computing "forward" messages from h + t, and the other one to compute "backward" messages from h + t, ie., inverse relation !_
We encode the query graph using a sequence of STARE layers (Galkin et al. 2020). First, select from É the necessary embeddings. These correspond to the ones for all entities in the query, VAR if the query has internal variables, and TAR for targets. The embeddings are then put in E, which also contains one copy of VAR for each unique variable encountered in Q.
A layer enriches the entity and relation representations E, R to E', as follows: For each query statement (h, r, t, qp) Q, we compute messages mp-t.r.qp and m t. For brevity, we only describe ma-st.r.qp- the other direction works analogously.
Qualifier Representation. We begin by composing the representations of the components of each qualifier pair 9: (gr;, E qp into single representation: hg 7g (E[ge, R(gr,]), where Yo denotes composition function (Vashishth al. 2020), e.g., g., the Hadamard product, and we use X(y) to indicate the representation of entity y projected in vector space X e.g qe; in E. Next, aggregate all qualifier pair representations for qp, as well as the representation of the main relation r into qualified relation representation using an aggregation function o,: h hr.qp or (R(r), (bq, e..))) For o, we experiment with a simple sum aggregation, and an attention mechanism.
The Bassage-Passing Step. To obtain a message mh-st.rqp. the qualified relation representa- tion is further composed with the source entity representation Ejhj using another composition function 7r. The result gets linearly transformed by W layer specific trainable parameter: mp-st.r.pp W V.,,, h), g... For inverse relations, we use a separate weight W.. Next, aggregate all incoming messages at,, (m((mm) (mp-st...gp (h, (p) Q, ('))
4

---

Published as a conference paper at ICLR 2022
hr-Ip
hn-2p
hr-3p
hr-21
hr-3i
hr 21-1p
hr- hr-Ip-21
Ancher
Varishle
Torget
Qualifier pairs
Relatins
Hypes Relatins
Figure 3: The hyper-relational formulas and their graphical structures. The qualifier pairs attached to each edge may vary O..n; for brevity we represent them as a single pair. We also allow qualifiers to exist only on certain edges of query, i.e., not all edges necessarily contain them.
ing message aggregation function oi, e.g. (weighted) sum. Besides computing these mes- sage aggregates each direction, we also compute a self-loop update a,, W (e, ro), where Wo, To To are trainable parameters. The updated entity representation is then obtained as the average over both directions and the self loop, with an additional activation a applied to it: E'(e] (3 (ae.o ae.+ + ae,+)) Finally, the relation representations are updated by linear transformation R' [r] W.R(rr. where W, is layer specific trainable weight.
Query Representation. After applying multiple STARE layers, we obtain enriched node rep- resentations Ex for all nodes in the query graph. As final query representation XQ. we aggre- gate all node representations of the query graph, xq = (e((E"(e] e E+ A ((e, r, E Q V (h, e, qp) E Q)}), with d, denoting an aggregation function, e.g., the sum. Alternatively, we only select the final representation of the unique target node, xQ = E [TAR]. To score answer entity candidates,
the similarity of the query representation and the entity representation, i.e., score(Q, = sxm [e)), such as the dot product, or cosine similarity.
We designate the described model STARQE (Query Embedding for RDF Star Graphs) since RDF is one of the most widely adopted standards for hyper-relational KGs.
5 EXPERIMENTS
In this section, we empirically evaluate the performance of QA over hyper-relational KGs. We design experiments tackle the following research questions: RQ1) Does QA performance benefit from the use of qualifiers? RQ2) What are the generalization capabilities our hyper-relational QA approach? RQ3) Does QA performance depend the physical representation of hyper-relational KG, i.e. reification?
5.1 DATASET
Existing QE datasets based Freebase (Toutanova Chen 2015) and NELL (Carlson al. 2010) are not applicable in our case since their underlying KGs are strictly triple-based. Thus, we design a new hyper-relational QE dataset based on WDS0K (Galkin et 2020 comprised of Wikidata statements, with varying numbers of qualifiers.
WD50K-QE. We introduce hyper-relational variants of query patterns commonly used in the related work (Hamilton et al.) 2018 Ren et al.) 2020. [Sun et al. 2020; Arakelyan et al. 2021) where each edge can have [0, n qualitier pairs. The patterns contain projection queries (designated with -P), intersection queries (designated with -i), and their combinations (cf. Fig. B}. Note that the simplest 1p pattern corresponds to a well-studied link prediction task. Qualifiers allow more flexibility in query construction, i.., further modify formulas by conditioning the existence of qualifiers and their amount over a particular edge. We include dataset statistics and further details as to dataset construction in Appendices B and
These patterns are then translated to the SPARQL* format (Hartig 2017) and used to retrieve ma- terialized query graphs from specific graph splits. Following existing work, make that validation and test queries contain at least one edge unseen in the training queries, such that evalu- ated models have to predict new links in addition to QA. As we the transductive setup where
Thhis datasct is available under CC BY 4.0.
5

---

Published as a conference paper at ICLR 2022
ohouutjct bil peedicass
Anchor modes
Targets
Dlank nodes
Relations
Relations
Qualifier
Qualifier entities
Figure 4: Example of a reification process: An original ar-2p query pattern (left) is reified through standard RDF reification (right). Note the change of the graph topology: the reified variant has two blank nodes, three new pre-defined relation types, and original edge types became nodes connected via the rdf predi cate edge. The distance between the anchor and target increased, too.
all entities and relation types have be seen in training, we also ensure this for all entity and relation types appearing in qualifiers.
Due to the (current) lack of standardized data storage format for hyper-relational (RDF*) graphs in graph databases, particular implementations of RDFR employ reification, i.e, transformation of hyper-relational statements as defined in Section B to plain triples. Reification approaches (Frey iet al., (2099) introduce auxiliary virtual nodes, new relation types, turn relations into nodes, and might dramatically change the original graph topology. An example of standard RDF reifica- tion (Briklley et al.) (2144) in Fig. transforms an original hr-2p query with three nodes, two edges, and two qualifier pairs into new graph with nine nodes and eight edges with rigidly defined edge types. However, the logical interpretation of query remains the same. Therefore, we want hyper-relational QE models to be robust to the underlying graph topology. For this reason, we ship dataset queries in both formats, i.c., hyper-relational RDF and reified with triples, and study the performance difference a dedicated experiment.
5.2 EVALUATION PROTOCOT.
In all experiments, we evaluate the model in the rank-based evaluation setting. Each query is en- coded into a query embedding vector Xq E R. We compute similarity score sim E(e]) be- tween the query embedding and the entity representation for each entity e E The rank N+ of an entity is its position in the list of entities sorted decreasingly by score. We compute filtered ranks (Bordes al.) 2013), i.e., while computing the rank of correct entity, we ignore the scores of other correct entities. We resolve exactly equal scores using the realistic rank (Berrendorf et al.) 2020), i.e., all entities with equal score obtain the rank of the average the first and last position.
Given set of individual ranks {r=) we aggregate them into a single-fiurre measure using several different aggregation measures: The Hits @k k (H@k) metric measures the frequency of ranks at most A E N+ i.c., H @K A. Σi[r; A:], with I denoting the indicator function. H@k lies between zero and one, with larger values showing better performance. The Mean Reciprocal Rank (MRR) is the (arithmetic) mean over the reciprocal ranks, i.e., MRR Σ r with a value range of (0, 1), and larger values indicating better results. It can be equivalently interpreted as the inverse harmonic mean over all ranks, and thus is stronger influenced by smaller ranks.
Since the size of the answer set of queries varies greatly queries with large answer sets would strongly influence the overall score compared to very specific queries with single entity swer. In contrast to rank- evaluation in existing QE work, we propose to weight each rank in the aforementioned averages by the inverse cardinality of the answer set compensate for their imbalance. Thereby, each query contributes an equal proportion to the final score.
5.3 HYPER-REES RELATIONAL QA
As we are the first to introduce the problem of available at the time of writing. Hence, compare our method to several alternative approaches.
QA, there is no established baseline
For, e.g., hr-2p we observe maximum answer set cardinality of 1,351, while the upper quartile 3.

---

1p-2i Published as a conference paper at ICLR 2022
Table 1: QA performance of STARQE and the baselines when training all hyper-relational query patterns, We omit the hr- prefix for brevity. Best results (excluding the Oracle) are marked in bold.
Pattern 1p
2p
3p
3i
2i-1p
Hits 10 (%)
StarQE
51.72
51.20
65.50
77.78
92.64
61.81
81.60
Triple-Only
45.04
12.76
24.66
69.74
91.74
16.77
40.67
Reification
55.17
50.86
63.65
81.25
95.31
61.05
80.49
Zero Layers
44.93
29.94
38.45
67.79
90.66
35.48
47.85
Oracle
81.03
24.11
38.47
95.54
99.67
32.74
76.96
MRR (%)
StarQE
30.98
44.13
52.96
63. 14
83.78
55.20
71.52
Triple-Only
22.25
6.73
14.05
48.01
74.52
8.16
22.23
Reification
34.78
43.42
50.77
61.01
85.17
49.09
64.21
Zero Layers
27.55
19.10
21.25
50.27
80.62
24.49
30.04
Oracle
79.16
18.40
23.72
90.43
97.91
21.10
54.74
Implementation. We implement STARQU and other baselines in PyTorch (Paszke al. 2019) (MIT License). We run hyperparameter optimization (HPO) pipeline on a validation set for each model and report the best setup in the Appendix J All experiments are executed on machines with single GTX 1080 Ti or RTX 2080 Ti GPU and 12 or 32 CPUs.
Triple-Only For the first experiment, we remove all qualifiers from the hyper-relational statements in the query graph leaving the base triples (h, t). Thus, we isolate the effect of qualifiers in answering the queries correctly. Note that in effect, this similar to the MPQE approach, but with better GNN and aggregation. To do this, we have retain the same queries as in other experiments, but remove the qualifiers upon loading. The set of targets for these queries remains unchanged, e.g., in the hyper-relational query from Fig. we would drop the (degree: BSc) qualifier but still have only ETHzuri ch as a correct answer.
Reification. For the second setting, convert the hyper-relational query graph to plain triples via reification (see Section (.T]. The effects of such transformation include the addition of two extra nodes per triple in the query, represent blank nodes and predicates (more details in Appendix (A]. Here, we investigate whether STARQE is able to produce the same semantic interpretation a topo- logically different query. Note that, while conceptually the default relation enrichment mechanism of STARQE resembles singleton property reification (Frey et al. 2019), its semantic interpretation equivalent standard RDF reification.
Zero Lavers. To measure the effect of message passing, we consider model akin to bag-of-words, which trains entity and relation embeddings without message passing before graph aggregation.
Oracle. If we take away the qualifier information, we could compare with several QE approaches (e.g. GQE, MPQE, Query2box, BetaE, EmQL, and CQD). The Oracle setup, is not just an upper bound to these, but to all possible, non-hyper-relational QE models. It simulates the best possible QE model that has perfect link prediction and ranking capabilities, but without the ability use qualifier information. Using this setting we investigate the impact of qualifier information our queries. More details are Appendix
Discussion.
The results shown in Table 1 indicate that STARQE is able to tackle hyper-relational queries of varying complexity. That is, the performance on complex intersection and projection queries is often higher than that of simple link prediction (hr-lp). Particularly, queries with intersections (-i) demonstrate outstanding accuracy, but it should noted here that also the Oracle setting performs very well in this case. Importantly, MRR values relatively close Hits 10 which means that more precise measures like Hits@3 and Hits retain good performance (we provide detailed breakdown in Appendix
"SaA QF http:/mmwnn.tggp...///...b..///t

---

Published as a conference paper at ICLR 2022
Results for the generalization experiment. Colored cells denote training query patterns for each style, e.g., in the EMQL-style we train only on 1p and 2i patterns and evaluate on all. The hr- prefix omitted for brevity.
Table 2:
Evaluation Style
1p
2p
3p
2i
3i
2i-1p
1p-2i
Hits @ 10 (%)
StarQE-like
51.72
51.20
65.50
77.78
92.64
61.81
81.60
Q2B-like
55.44
51.10
66.39
78.79
94.20
57.49
80.49
EmQL-like
50.10
16.45
44.36
75.86
93.55
6.79
62.80
MPQE-like
48.48
12.57
34.19
83.04
96.32
14.75
61.02
MPQE-like + Reif
58.43
12.02
31.14
83.77
97.22
13.50
50.92
MRR (%)
StarQE-like
30.98
44.13
52.96
63.14
83.78
55.20 20
71.52
Q2B-like
33.04
41.99
51.71
61.72
83.49
44.24
67.04
EmQL-like
32.01
10.09
27.94
61.45
86.28
3.73
53.58
MPQE-like
26.83
6.79
19.72
56.16
74.35
9.62
39.81
MPQE-like + Reif
36.36
6.12
17.11
56.81
77.29
8.32
29.25
To investigate if this performance could be attributed to the impact of qualifiers, we run Triple- Only and Oracle setup. These experiments show that for some query patterns, qualifiers play an important role. Without them, would not be able get good results for the 2p. 3p, 2i- 1p and 1p-21 queries. The reason that the Oracle cannot answer these well is that despite its access to the test set, the mistakes makes accumulate when there more hops akin to beam search (recall that the Oracle does not have access to qualifiers and considers all edges with a given relation). For queries that only involve one reasoning step, notice that the Oracle can, and hence normal link predictor might be able, to perform very well. When more paths intersect (2 and 3i), the chance of making mistake goes down. This observation similar what can be seen in e.g., CQD (Arakelyan et al. 2021), and can be ascribed to each of the different paths constraining the possible answer set, while cancelling out mistakes. More experiments on qualifiers impact are reported Appendix [H]
We observe comparative performance running the Reification baseline. It suggests that our QE framework robust the underlying graph topology retaining the same logical interpretation of complex query. We believe it is promising sign of enabling hyper-relational QA on wide range of physical graph implementations.
Finally, we find that message passing layers are essential for maintaining high accuracy the Zero Layers baseline lags far behind GNN-enabled models. One explanation for this observation can be that without message passing, variable nodes do not receive any updates and are thus not "re- solved" properly. To some extent counter-intuitvelly, we also observed that does not make large difference whether relation embeddings are included in the aggregation performance on 1p, 21, 31 queries can be explained by their very specific star-shaped query pattern which is essentially 1-hop with multiple branches joining at the center node.
not. Relatively high
5.4 GENERALIZATION
Following the related work, we experiment with how well our approach can generalize to complex query patterns if trained simple ones. Note that below understand all query patterns as hyper- relational, i.c., having the hr- prefix. There exist several styles for measuring generalization in the literature that include in the experiment:
Q2B-like. The style used by QUERY2BOX (Ren et al. 2020) and assumes training only on 1p, 2p, 3p, 21, 3i queries while evaluating two additional patterns 2i-1p, 1p-21.
EmQL-like. The other approach proposed by EMQL (Sun et al. 2020 employs only 1p, 2i patterns for training, using five more complex ones for evaluation.
8

---

Published as a conference paper at ICLR 2022
MPQE-like. The hardest generalization setup used in MPQE (Dza & Cochez 2020) allows train- ing only on 1p queries, i.e, vanilla link prediction, while all evaluation queries include unseen intersections and projections.
MPQE-like + Reif. To measure the impact of reification on generalization, we also run the exper- iment reified versions of all query patterns. Similarly to MPQE-like, this setup allows training only on 1p reified pattern and evaluates the performance on other, more complex reified patterns.
Discussion. Table 2 summarizes the generalization results. As reference, include the STARQE results in the no- no-generaliization setup when training and evaluating on all query patterns. Generally, observe that all setups generalise well on intersection queries (-i) even when training in the most restricted (Ip) mode. The Q2B-lik regime demonstrates appealing generalization capabilities on (2i-1p, 2p-1i), indicating that it is not necessary to train on all query types. However, moving to fine-grained study of most impactful patterns, we find that projection (-p) patterns are rather important for generalization, as both EmQL. and MPQE styles dramatically fall behind in accuracy, especially in the MRR metric indicating that higher precision results are impaired the most.
The MPQE style is clearly the hardest when having only one training pattern. The higher results on intersection (-i) patterns can be explained by small cardinality of the answer set, i.e., quali- fiers make query very selective with very few possible answers. Finally, appears that reification (MPQE+ Reif) impedes generalization capabilities and overall accuracy according to the MRR sults. This can be explained by the graph topologies produced when reifying complex queries, and training only 1p not sufficient.
LIMITATIONS & FUTURE WORK
In this section, discuss limitations of the current work, and future research directions. The first limitation of our work that we do not allow literal values like numbers, text, and time in our graph. This means that cannot, for example, handle queries asking for people born in the year 1980. These and more complex values can be incorporated as node features (Wilcke et al., 2020).
Secondly, more logical operators, such as negation (which could be included qualifier), disjunc- tions, cardinality constraints, etc. can be considered. In this work, we only allow variables in the head and tail positions. Nonetheless, one can also formulate queries with variables in more diverse positions, e.g., qualifier value or main relation.
Moreover, the current work allows for different query shapes compared to prior work because queries are not limited to DAGs (see Appendix F for details). However, our work does not allow all shapes. Specifically,, is currently unclear how queries with cycles would behave.
Another future direction can be found in the many operators which query languages like SPARQL have. For example, queries including paths, aggregations, sub-queries, filters on literals, etc. Further research work is required towards explainability. Currently, our system does not provide explana- tions to the answers. An initial direction is to analyse the intermediate values in variable positions which can be used as explanations, but likely need to be explicitly trained to behave that way. Fi- nally, an interesting research direction is the use our approach for the creation of query plans.
7 CONCLUSION
In this work, we have studied and addressed the extension of the multi-hop moott--hoplogicall reasoning problem to hyper-relational KGs. We addressed the theoretical considerations of having qualifiers in the context of QA and discussed the effects it can have on it, such as cardinality of the answer set. We proposed the first hyper-relational QE model, STARQE, based this new setup. We introduced new dataset, WDS0K-QP -EE, with hyper-relational variants of 7 well studied query patterns and analysed the performance of our model on each of them. Our results suggest that qualifiers help in obtaining more accurate answers compared to triple-only graphs. We also demonstrate the robustness of our approach to structural changes involved in the process of reification. Finally, we evaluate the generalisation capabilities of our model in all settings and find that it is able to accurately answer unseen patterns.
GNN encoder to work in

---

Published as a conference paper at ICLR 2022
Reproducibility Statement. The experimental setup and implementation details described in S We elaborate on the dataset construction process in Appendices and All hyperparam- eters are listed in Table 6 The complete source code is available for reviewers in the supplementary material, and will be made available open source. More experimental evidence is provided in Ap- pendix and more detailed metrics per query pattern are listed in Appendix [
Ethics Statement. The assumption of our approach as well as related techniques is that the data used for training solely contains true facts. If this data is (intentionally) biased or erroneous to start with, further biased or wrong information will be derived, which could lead to harmful conclusions and decisions. Besides, even if the imput data to the system correct, the system could due to its imperfections still derive incorrect answers to queries, which might, again lead to wrong conclu- sions. Hence, users of this technology must be made aware that answers to their queries are always approximate, and this technology ought not to be used in a process where correctness is critical.
Acknowledgements. This work has been funded by the Elsevier Discovery Lab and the German Federal Ministry of Education and Research (BMBF) under Grant No. 01IS18036 1036A. The authors of this work take full responsibilities for its content. For performing the experiments the authors made use of the LISA system provided by SurfSara and the DAS cluster (Bal et 2016).
REFERENCES
Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Shar- ifzadeh, 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. CoRR, abs/2006. 1000006613366 13365, 2020.
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2021. URL
https: fttt:s://cpenrrevieee
net Forum do 9F 9kDwkz
H. Bal, D. Epema, C. de Laat, van Nieuwpoort, Romein, F. Seinstra, C. Snoek, and H. Wijshoff. A medium-scale distributed system for computer science research: Infrastructure for the long term. Computer, 49(05):54 63, may 2016. ISSN 1558-0814. doi: 10.1109/MC2201..22,.
Claude Berge. Hypergraphs: combinatorics of finite sets, volume 45. Elsevier, 1984.
Max Berrendorf, Evgeniy Faerman, Laurent Vermue, and Volker Tresp. Interpretable and fair comparison of link prediction or entity alignment methods with adjusted mean rank. CoRR, abs/2002.0691 14, 2020. URL httlhhhtss//ll /ttp::://axxvvvvor/ abs 2002.00022202 06914
Antoine Bordes, Nicolas Usunier, Alberto Gareía-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Christopher J. C. Burges, Léon Bottou. Zoubin Ghahramani, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp- 2787-2795, 2013.
Dan Brickley, Ramanathan V Guha, and Brian McBride. RDF schema 1.1. W3C recommendation, 25:2004-2014, 2014.
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka Jr., and Tom M. Mitchell. Toward an architecture for never-ending language learning. In Maria Fox and David Poole (eds.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010.
Daniel Daza and Michael Cochez. Message passing query embedding. In ICML Workshop Graph Representation Learning and Beyond, 2020. URL hhtps::/ .rg/ abs/ 2002.02405
Fredo Erxleben, Michael Günther, Markus Krötzsch, Julian Mendez, and Denny Vrandecic. In- troducing wikidata to the linked data web. In Peter Mika, Tania Tudorache, Abraham Bern- stein, Chris Welty, Craig A. Knoblock, Denny Vrandecic, Paul Groth, Natasha F. Noy, Krzysztof
10

---

Published as a conference paper at ICLR 2022
Janowicz, and Carole A. Goble (eds.), The Semantic Web ISWC 2014 13th International Se- mantic Web Conference, Riva del Garda, Itly, October 19-23, 2014. Proceedings, Part 1, vol- ume 8796 of Lecture Notes in Computer Science. pp. 50 50-65. Springer, 2014. doi: 10.1007/ 978-3-319-11966 199-1-99999-99 4. URR.http::/doot org 1 1007/98 ----9-788-3-3100 3- 9- 1111999196-999
Johannes Frey, Kay Müller, Sebastian Hellmann, Erhard Rahm, and Maria-Esther Vidal. Evaluation of metadata representations in RDF stores. Semantic Web, 10(2):205-22) 229,, 2019.
Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, and Jens Lehmann. Mes- sage passing for hyper-relational knowledge graphs. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.). Proceedings of the 2020 Conference on Empirical Methods Natural Lan- guage Processing. EMNLP 2020, Online, November 16-20, 2020, pp. for Computational Linguistics, 2020.
Association
Saiping Guan, Xiaolong Jin, Jiafeng Guo, Yuanzhuo Wang, and Xueqi Cheng. Neuinfer: Knowl- edge inference on n-ary facts. In Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, pp. 6141-6151, 2020.
William L. Hamilton, Payal Bajaj. Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries knowledge graphs In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Informa- tion Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 2030-2041, 2018.
Olaf Hartig. Foundations of RDF and SPARQL *:(an alternative approach to statement-level meta- data in RDF). In AMW 2017 11th Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, Montevideo, Uruguay, June 7-9, 2017., volume 1912. Juan Reutter, Divesh Srivastava, 2017.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. A survey on knowledge graphs: Representation, acquisition and applications. CoRR, abs/2002.00388, 2020.
Bhushan Kotnis, Carolin Lawrence, and Mathias Niepert. Answering complex queries in knowledge graphs with bidirectional sequence encoders. CoRR, abs/2004.02596, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary De Vito,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32: Annual Con- ference on Neurul Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8024-8035, 2019.
Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Eisuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In 8th International Conference on Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
https: //tp:ev//ppeeevieww net. wtt.://wwwwwwetettteeeooooo www.oooddonmoureeeeooooo
Paolo Rosso, Dingqi Yang, and Philippe Cudré-Mauroux, Beyond triplets: hyper-relational knowl- edge graph embedding for link prediction. In Proceedings of The Web Conference 2020, pp. 1885-1896, 2020.
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 semantic web conference, pp. 593-607. Springer, 2018.
11

---

Published as a conference paper at ICLR 2022
Fabian M Suchanek, Gjergii Kasneci, and Gerhard Weikum. Yago: core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pp. 697-706, 2007.
Haitian Sun, Andrew O. Arold, Tania Bedrax- Weiss, Fernando Pereira, and William W. Cohen. Faithful embeddings for knowledge base queries. In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020,
NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality. pp. 57-66, Beijing, China, July 2015. Association for Computational Lin- guistics. doi: 10.18653/11/115440000 URL https: wwwww//wwwwwww...... www.wb. http://wwww....///tt/oooogg.ggo. 015-4007
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha P. Talukdar. Composition-basee multi- relational graph convolutional networks. In 8th International Conference on Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018. htttta/://penneee.e...eeeeeeeeee
Denny Vrandečić and Markus Krötzsch. Wikidata: a free collaborative knowledgebase. Communi- cations of the ACM, 57(1)):78 85, 2014.
W. X. Wilcke, P. Bloem, V. de Boer, R. H. van t Veer, and F. A. H. van Harmelen. End-to-end entity classification on multimodal knowledge graphs, 2020.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 3391-3401, Curran Associates, Inc., 2017. URL http: //tp:e//pppeeae/e nips. cc/paper/ 6931 -eep- sests.pdf.
APPENDIX
A TYPES OF GRAPHS
In this section, we discuss in further detail the different approaches to break free from the restriction of pairwise relations. The intuition how those approaches are different is presented in Fig. 5
Hyper-relational Graphs KGs used in our work are a subset of hyper-relational graphs. In gen- eral, hyper-relational graphs can also contain literal values, like integers and string values as qualifier values. Labeled property graphs are another example of subset of hyper-relation graphs, but they typically only allow literals as qualifier values. The Wikidata model (Erxleben et al.) 2014) and RDF* (Hartig. 2017) allows for both literals and entities as values. Many implementations of RDF* do make the monotonicity assumption, which statements in case they have the same main triple. The resulting statement will have the same main triple, but as qualifier information, the union of the sets of qualifier pairs of the original statements.
also made in the paper. Some will also merge
12

---

Published as a conference paper at ICLR 2022
Hyper Graph
Hyper Gruph
Graph
edFegeddicat
edippedicne:
satiea
abtabjest
adjeet
Anchor mode Blank modes
Relations
Target node
Qualifier relations as eniities
Qualifer Relation
Variable mode
Qualiffir entitics
Hyperedge
The same query expressed in three different approaches. Hyper-relational (left), hyper- graph (middle), and reified (right) graphs.
Figure 5:
Hypergraphs Hypergraphs another type of graphs, initially proposed by Berge (Berge 1984), where hyperedges link one or more vertices. These hyperedges group together sets of nodes in relation, but lose information of the particular roles that entities play in this relation. Besides, each different composition of elements in the relation introduces new hyperedge type, causing combinatorial explosion of these types.
Reified Graphs Hyper-relational and reified graphs have equivalent expressive power compared labelled directed graphs. The reason is that we can define a bijection between these graphs. However, depending on the use case, the different graph types have benefits.
When we convert hyper-relational graph to an RDF graph, we end up with what is called the reified graph. There are multiple approaches how to perform this conversion. In our work, use Standard RDF Reification It introduces new, so called blank nodes represent statements with all parts of statement attached. This allows for all information to exist on the same level. One of the disadvantages to this approach the addition auxiliary nodes, which heavily affect the structure of the graph and quickly inflate the graph size.
B THE WD50K-QE DATASET
In this section, we describe the generation of the hyper-relational queries that we use for train- ing, validation and testing of our models. We start with WD50K (Galkin al.) (2020), which is WikiData-basee dataset created for hyper-relational link prediction. This dataset already provides with train, validation and test splits, each containing a selection of hyper-relational triples. It publicly available by the authors, in CSV format. In order to utilise it for our work, we converted it from CSV to RDF*
The overall pipeline is presented on Fig. 6 To generate the queries, we hosted the converted dataset on graph database with support for hyper-relational data. For our use-case, we use anzograpt We utilize 3 named graph. [0) triple_train, triple rriplevalidatton. and triple_esst, to prevent validation and test set leakage. In the evaluation of approximate QA, it common to have queries with at least unseen edge from the test set, which is also applied upon query generation process. We ensure that:
For the training set, all statements query come from the triple_train (only).
For the validation set, one statement comes from the triple. and
and the other edge(s)
come from either triple train train
13

---

Published as a conference paper at ICLR 2022
WD50K
HR FuR-Query
Patterns
Train Graph
HR-Query Generator
Query Graphs
Validation Graph
Test Gmph
RDF* TripleStore
Figure 6: diagram of the query generation process. On the far left, the chosen dataset (WD50K) uploaded in the RDF*-compatib triplestore (AnzoGraph). As follow up, we translated the hyper-relational query patterns to SPARQL* * and executed them against the triplestore to retrieve the desired splits.
Pattern
1p
2p
3p
21
31
2i-1p
1p-21
train
24, 819
313, 088
5, 9500, 990
48, 513
318, 735
306, 022
1, 088, 539
validation
100
100, 706
2, 1.968,33 315
15, 648
169, 195
169, 438
569, 957
716
202, 045
5,,33, 476
38,201 207
547, 272
272
445, 007
267, 452
Table 3: The amount of queries for each of the different query patterns. We notice that for some patterns there are many more queries than for others, which also why we report results for the patterns separately.
For the test set, one statement comes from triple and the other statement from any of triple Jrain, triple.validation, and triple
In order generate the query data splits, we constructed SPARQL* queries that correspond specific pattern. We call these higher order queries formulas. Using these formulas to generate queries has several advantages compared other approaches found in related work. In the related work, we encounter sampling using techniques such as random walks to create queries which have the shape according to the pattern. With our approach, we have more control over what the samples are, and thus finer control of the inputs to our experiments.
Moreover, we can also ensure that we do not sample with replacement, we are not biased towards specific high degree nodes, and at the same time guarantee that we do not sample queries that are isomorphic with each other. A final benefit that with our approach, we can immediately retrieve all answers for a query, instead of only one.
One final issue we encountered had to do with the nodes that have high in-degree in our dataset. Their existence causes skewing of the distribution of correct answers to queries, and has to be resolved. Appendix C we describe this issue and explain our approach to overcome it.
As result of this procedure, we obtain all queries of the given shapes, and are guaranteed that there are no duplicates nor isomorphism among the queries. The queries used in this paper are such that every edge in the query has one qualifier, which means that, in the knowledge graph, the same edge has at least one, but possibly more qualifiers. The amount of queries for the different patterns can be found in Table
14

---

Published as a conference paper at ICLR 2022
C ISSUES SAMPLING QUERIES WITH JOINS IN A GRAPH WITH HIGH DEGREE NODES
In our query generation step, we exclude high in-degree nodes as a target for specific queries. In this section, we explain why that choice was made. We will focus on the 3 pattern. The same argument holds for other patterns with joins, like 21, 2i-1p, 1p-2i.
The queries randomly sampled from all possible queries that can be formed by matching the pattern with the data graph. For the 3 pattern, a node with an in-degree of n, results in (2)) different queries, with that node as target.
The problem that if we randomly sample our queries, the answer would usually be one of the highest degree nodes. Concretely, in our graph data, the highest observed in-degree is 4,424, which would result in 14,421,138,422 possible queries with the corresponding node as an answer. If we generated all possible queries, we would end up with 38,01 1, 1148,664 different ones. So, the node with the highest in-degree is already responsible for 38% of the queries, meaning that system an- swering 3-i queries that are randomly sampled, would get 38% correct by always giving that answer. Moreover, if we look at the @its@ 10 metric, we would score 93%, by always predicting the same ranking (the top 10 descending frequency). Note that existing query embedding models have been evaluated like this in the past, ignoring this data issue.
Hence, we decided to make the task harder by removing these high degree nodes for queries with joins. That is, by putting the threshold at an in-degree of 50, remove the 623 nodes with the highest in-degree which would have represented 99.9% of the possible answers for the 3i queries without this modification. After filtering, the baseline of always predicting the same ranking for the randomly sampled queries, will result in a Hits @ 10 of 3% the best case.
For other query shapes where a join is involved, the situation is similar, but less pronounced.
D SIZE OF THE ANSWER SET OF QUERY WITH MORE QUALIFIERS
When have query with without qualifiers, and we add more qualifiers, the number of answers to this query can only become smaller. Intuitively, this happens because the query becomes more specific. In this section we prove this intuition correct. Note that proving this requires monotonicity, as we defined in the paper. Without this assumption for example allowing non-monotonic qualifier relations would result in losing the guarantee that the answer set becomes smaller.
Given query Q, and query Q that is the same, except for one set of qualifier pairs of Q which can have extra pairs, then the answers to Q are subset of the answers Q.
Formally:
Theorem D.I. Given KG G (E, S), where S C ( x R x E x Q)) a query Q = {11,, (11............................. (hn, Tas bnx {pn)). and a second query Q = (1h1,ri,4 11, (,, ... (ka, Tn, In; (Pn)), where 3ik: : qpk C TPE and Va((s E [l,... n) Ax +
k) - M. = ).x). Then, Ag( C Ac(Q).
Proof. Assuming symbols as defined in the thcorem, we show that Va aa Ag( a E AQ( a is an answer to Q then its associated variable substitution is such that (v(h)), v(tx), (PK) E G. From monotonicty (see Appendix E and given qp: S qpk we then know that (((h), Tk. o(tx),.pa) E G. And hence, using the same variable substitution, a is an answer for Q.
Corollary D.1. By induction, given a query Q, and a query Q that is the same, except for any set of qualifier pairs of Q which can have extra pairs, then the answers Q are a subset of the answers to Q.
Corollary D.2. As special case, given query Q, and query Q that is the same, except that Q does not have qualifiers, while Q can have qualifier pairs on its statements, then the answers to Q subset of the answers Q.
15

---

Published as a conference paper at ICLR 2022
T2
T3
T1
TAR
VAR1
C3
-1
T3
2
Figure 7: Visualization for Appendix Original query (black and red) violating the original defi- nition of a valid query graph, and equivalently transformed query (black and blue) which fulfils the properties becoming 1--2i query.
ON MONOTONICITY
In this work, we restrict the qualifiers to respect monotonicity in the KG in the following sense:
(h, r,r, gp) E G A qp' S qp = (h, qp') e g
This implies that if qualified statement in the KG has set of qualifier pairs, then the KG also contains the qualified statement with any subset thereof. As a result, some types of qualifying information cannot used, e.g.. qualifier indicating that a relation does not hold (i.e., negation). This breaks monotonicity since the existence of such statement would further imply the existence of that statement without the qualifier, leading to contradiction.
F RELAXING THE REQUIREMENTS ON QUERIES
In the paper, we limited our queries with the same limitations as done in prior work. Here we will discuss why all of these restrictions needed for work, and how evaluation already includes some of these more general cases.
As reminder the definition of our queries is follows:
Definition F.1 (Hyper-re relational Query). Let V be set of variable symbols, and TAR E V a special variable denoting the target of the query. Let E EVV. Then, any subset Q of x x x valid query if its induced graph
1) is directed acyclic graph,
2) has a topological ordering in which all entities (in this context referred as anchors) occur before all variables, and
3) TAR must be last in the topological orderings.
The main reason why we deal with more general queries is because our query encoder learns rep- resentation for both normal and inverse relations. We use - indicate the inverse of relation r. When encoding query with a (normal) relation then both representations R/r] and R(r- are used simultaneously. If we encounter query using the inverse relation r -- we can use that inverse relation R|r- and the inverse of the inverse (((r-1) relation representation
R(r), or in other words the normal This means that even if we only ever train with the normal relation, have the ability to invert relations, and hence we can lift some limitations.
For example, let look the query
Onew_patten new_patterm
{(e1, ri, TAR, ()), (TAR, r2, VARI, 0), (VARi, ()},
shown in Fig. 7 This query breaks of the requirements. It has entity e3 occurring after variables VAR, and TAR in the topological ordering. And, TAR is not in the last position.
However, using inverse relations, we can convert this query into:
Q Qknown_pattem {(e 71, TAR, 0), (VARI, 12 TAR, 0), (ea, r3 VARI, 0))
16

---

Published as a conference paper at ICLR 2022
This transformation converts the query into 1p-2i query, which is pattern among the evaluated patterns in the paper. Because of this transformation, the pattern of Qnew pateen is indistinguishable from the pattern of known patter from the perspective of the model. Besides the example illustrated above, many other graphs can be converted into one of the patterns in the paper. Since we can perform the conversion in both directions, all these possible patterns also implicitly included in our used datasets.
In principle, the encoder does also not assume that there are no cycles in the query graph. However, the effect of cycles requires further investigation.
G NUMBER OF MESSAGE PASSING STEPS EQUAL TO THE DIAMETER
In Daza & Cochez 2020). the authors find that the best results are achieved when making the number of message passing steps equal the diameter of the query, defined as the longest shortest path between 2 nodes in it. After these steps, they use the embedding of the target variable as the embedding of the complete graph. Accordingly, we performed additional experiments with this dynamic query embedding setting. and with a variant which uses an extra message passing step. From these experiments we concluded that this approach did not lead to better results, which contradicts with the findings in Daza & Cochez (2020).
H QUALIFIER IMPACT ON PERFORMANCE
For a more fine-grained analysis of qualifiers impact on query answering performance, for each query pattern we ran an experiment measuring relative performance change the presence and absence of given qualifier relation in query. That is, the main results of StarQE in Table Jssumm all qualifiers are enabled. Then, for each qualifier relation, we remove qualifier pairs containing this relation from all queries in given pattern and run a model forward pass to obtain new predictions. We run such experiments 5 times for each relation, each metric, and each pattern to get an average value with standard deviations. Finally, for each metric, sort relations in the ascending order of their performance increase.
Trepors t worst (i.e., first 3 relations in the sorted list) and top-3 best (last 3 relations in the sorted list) qualifier relations that have the most impact along the metrics. For example, P1686 (for work), common qualifier of relation awa rd recei ved, increases Hits @ 10 performance in 1p- 2i queries by a large margin of 62% and MRR by 57% compared to queries without this qualifier. The gains are consistent, although on smaller scale, in other patterns, too. On the other hand, P453 (character role), a qualifier of cast member, seems to be the most confusing qualifier in 2p queries leading to lower scores across all metrics.
We note, however, that on bigger picture (Fig. (), where impact for all qualifier relations is visual- ized, total gains of having qualifiers outweigh negative effects from some of them.
meric
50%
20%-
-20%
-8%6
-30%
2200
2110:2
2-1hop
2010
shop
1hap-21
2010
20-hhop
200p
1h0p
2000-2
20ep
201/op
20op
Figure 8: A general overview of qualifiers impact on AMRI, Hits@ 10, and MRR. In all metrics, higher deltas correspond to better prediction performance. Having qualifiers does, on average, lead to better predictions.
17

---

Published as a conference paper at ICLR 2022
AMRI
t&
MRR
relation
improvement
relation
improvement
relation
PS18
0.24
2.09
P1364
3.64
1.50
P18
2.88
D.96
0.42
4.47
1.23
2.42 + 2.58
PTOND
+33.70
1.19
20
11.17
2:30
P17
2.03 + 3.02
PTEN
+24.04
3.87
P1340
27.78 +
4.01
4.26
P453
-64.91
1. 40.79
11.9
5.74 + 2.76
P453
2.05
5.57
50.67
0.65
PTO2
7.14
23.57
1001
4.55
24.48
P132
0.01
0.59
11,56
+ 2.26
15.00 = 0.00
1007
+ 58.38 + 7.57
13.35
32.37
47.49
+
4.53
P155
2.75
0.16
0.32
0.30
0.46
P224
2.65
12:77
P057
0.00 = 0.00
P7441
0.02
0.04
P2957
14.16
21.84
50.044
11.27
P1310
60.64
7.14
17.95
2.53
72.86
42.07
76.71
1.65
P433
0.85
3.90
0.00 = 0.00
F291
0.06
0.09
1100
0.67 1:
2.06
2261
0.00 = 0.00
1139
0.09 1 1.11
4.00
5.46
+29.49
2.32
+34.53
16.82
34.56
5.43
P906
+34.64
2.82
P805
+35.19
1.50
2.18 +
4.01
P224
3.44 + 4-47
P2241
8.03
5.50
1.37 + 5.09
1510
0.33 + 1.73
0.01
0.27
31
P4
0.77
1.09
0.33 + 1.13
P291
0.00
0.00
14.13
+17.49
2.35
28.26
2.68
P2842
42.44
36.23
PSTX
21.94
1.42
P726
32.88
26.04
P2241
5.29
+ 4.07
P1346
0.53 + 0.11
P2680
0.32
0:31
21-1p
19339
1988
0.01
1.81
+ 7.30
0.02
P500
22433
0.00
0.05 + 0.11
0.00
2255
0.40
0.03 +
1.20
0.43
+51.11
10.37
5.57
Ples
+56.63
0.73
P39
+55.05
23.43
71880
24.58 +
6.44
+62.98 = 27.55
+22.67
2.60
P2241
3.56 + 6.66
P4.00
6.63 14.51
P7241
8.57
7.45
P17
3.30
+ 4.91
14077
6.34 + 14.91
P1699
3.33
6.94
19-24
PTITS
24.53
21.48
+99.04
12.18
+57.30
1.64
P854
31.24
+ 46.20
PTRN6
+61 .66
2.20
P50N
+57.36 -
0.98
-77.99
4 10.23
P905
+63.10
0.38
+7..11 1
3.91
Table Top worst and top best impacting qualifier relations per pattern. In all metrics (AMRI, H@ 10. MRR), positive value corresponds to better predictions. For some metrics, and given pat- terns we only see improvements in cases where qualifiers are included. The qualifier relation P453 (specific role played or filled by subject
"cast member" or "voice acior") seems to confuse the model the most. On the other hand PS05 (referring to an item that describes the relation identi- fied in the statement) often leads to the biggest improvements in the metrics. All relation names clickable links to their Wikidata pages.
18

---

Published as a conference paper at ICLR 2022
1 THE ORACLE SETUP
There are several QE methods we could compare our work with. However, these methods are only able to answer queries utilising triple and not qualifier information. Besides, methods are introduced regularly, each outperforming the previous method. Hence, we employ an Oracle approach to compute the upper bound that triple only QE models achieve WD50K- QE This Oracle simulating perfect link prediction and ranking capabilities but does not have access to qualifier information.
that new
To achieve this, the Oracle system has access to training, validation, as well as test data. Given the access the totality of the data, the system will return optimal ordering, i.e., one that maximizes our reported metrics. However, since the system cannot process qualifier information, the ordering of the result set can only be based on the entities and relations in the query. This means that queries that are the same when ignoring the qualifier information, will get the same list of answers. In effect, the oracle will, despite its perfect information for a setting without qualifiers, not answer perfectly. Using this setting we can hence investigate how much difference qualifier information makes for our queries.
Finally, note that because multiple ordering can be considered optimal from the information the Oracle has available, we report the expected value for these metrics.
J DETAILED RESULTS
We provide our chosen hyper-parametee parameters after performing hyper-parameter optimisation in Table 6 and detailed results including standard deviation across five runs with different random seeds in Ta- bles 7 and 8 We report Hits@k for & 1.3, 10, mean reciprocal rank (MRR), and adjusted mean rank index (AMRI) (Berrendorf et al., 2020). For all metrics, larger values indicate better perfor- mance. We highlight the best result per column and metric in bold font.
For the Hits @k metric, we observe StarQE performing best across patterns, except for the most simple ones, 1p (equivalent to plain link prediction), and 3i. Standard deviations are usually small (around point). The base triples baseline sometimes exhibits larger variances across multiple random seeds. For MRR make similar observations as for Hits k, which is intuitive since it can be seen as a soft version of H@k.
For AMRI, the picture differs slightly. AMRI is a linear transformation of the mean rank, which normalizes the scores such that 0 corresponds to the performance of a random scoring model and 100% to the perfect score. Besides, AMRI preserves the linearity of mean rank, i.e., it is equally influenced by improvements on any rank, not just at the top of the ranking. Across the board, we observe values far beyond 50%, usually exceeding 90%. The general tendency of some patterns being more difficult than others persists and is coherent with the other metrics. Comparing different models, we can see that StarQE falls behind, e.g., reification and more simple baselines such as zero- layers, which do not use the graph structure. Since this behavior was not observed for the metrics more focused on the top positions in ranking, the decrease in performance this metric has to be caused by entities that received large ranks in the first place.
Zooming in on the Oracle setup. we make several observations. First, it becomes increasingly harder for the Oracle to produce good results for smaller values of & in the Hits metrics. Since this is an upper bound to the Base triple setup, also that model shows similar behavior. The observation that the intersection queries can still perform well is also visible in the more detailed results.
The very high AMRI for the Oracle is also expected. Since this model is designed as the best possible ranking model, it will place all correct answers for the query (while ignoring qualifiers) at the top of the ranking. This set of answers is a super set of the correct answers to the qualified query (see Appendix DJ. Now, that set of answers is nearly always very small compared to the 50K candidate entities in our dataset. So. relatively speaking the correct answers are still nearly always ranked high, and hence we obtain high AMRI score.
19

---

Published as a conference paper at ICLR 2022
K EVALUATING FAITHFULNESS
Following the idea of EmQL (Sun et al. 2020): we evaluate faithfulness of our hyper-relational approach by evaluating its performance on the training set, that is, an ability correctly answer already seen queries. Evaluation on the training set is a suitable proxy for faithfulness since even the union of training, validation and test queries (as done in the original work) is highly incomplete considering the whole background graph (be in Freebase or Wikidata). To this end, we evaluate the model trained in two regimes: StarQE- like trained on all query types and MPQE-lik -like trained in the hardest setting on only Ip link prediction queries. The results presented in Table 5 show that the StarQF-like model exhibits faithfulness saturating performance metrics almost perfect results. As expected, training the model only on one query type inhibits faithfulness qualities.
Table 5: Full results for the faithfulness experiments, including standard deviation across five runs with different random seeds. We report Hits@k for 1,3, 10, mean reciprocal rank (MRR), and adjusted mean rank index (AMRI) Berrendort al. (020). For all metrics, larger values indicate better performance.
Pattern
1p
2p
3p
21
31
21-1p
1p-21
@its@1
StarQE: like
74.27
5.30
94.58 à: 1.81
89.93 1: 2.29
94.29
1.67
99.34 1: 0.24
96.02 1.45
99.05
0.46
MPQB-like
90.43
2.10
8.00
0.85
19.99 4: 2.05
87.88 1.53
92.44 + 1.56
13:68 + 0.97
65.51
2.60
69 (%%
StarQE-like MPQE-like
81.06
1.61
98.12
0.19
96.56
97.48 1.15
99.81 0.11
98.78 0.51
0.09
96.18
1.10
14.19 1.18
32.12 +: 2.59
97.17 = 0.62
99.46 1 0.16
18.64 = 1.43
85.42 1.24
@its (5%
StarQE-like MPQE-like
98.98
0.67
98.75 0.41
22.62
1.56
47.09 + 3.14
99.46 0.18
99.94 + 0.02
23.98 + 1.70
94,90 0.35
MRR (56)
StarQE-like MPQE-like
80.23
4.85
96.51
1.09
93.50 +
96.09 1.32
99.59 + 0.17
97.47 0.95
99.45 0.27
93.58 1.52
12.88
1.06
28.88 +: 2.36
92.79 0.94
95.93 + 0.81
17.36 =: 1.23
76.51 1.74
AMRI (%)
StarQE-lika
99.97 0.03
99.99
0.00
99.99 1: 0.00
100.00
0.00
100.00 1: 0.00
100.00 0.00
100.00 0.00
MPQE-like
100.00
91.77
2.29
91.61
100.00
100.00
93.97 2.09
0.00
20

---

Published as a conference paper at ICLR 2022
negativepoowemmon
multiplication
Q2B- like
leakyrelu
0,002075
attention
adam
32
sum
Thme
224
0.1
targetpooling symmetric dotproduct
multiplication
EmQL like
leakyrelu adam 0.007253
False
128
256
0.3
MPQE-like Reif
targetpooling symmetric
multiplication
0.0001414
dotproduct
Table 6: Best hy per- parameter as chosen after hy pyper- hyper-paraneen parameter optimization
False
relu
32
96
0.2
targetpooling
multiplication
prelu MPQE-like
0.0005256
atlention dolproduct
False
128
128
0.5
negativepowernorm
multiplication
Zero Layers
D.0008733
symmetric
relu
adam
sum
False
160
0.3
64
negativepowemorm
multiplication
Base Triple
0.007253
attention
relu adam
32
sum
True
224
0.3
negativepowemorm
multiplication
Reification
0,003768
attention
relu
adam
32
sum
True
224
0.3
targetpooling attention dosproduct
multiplication
0.0007741 64
leakyrelu adam
StarQE
True
192
0.5
ssage- weighting
embedding dim
graph ppoling
learning-rate rate
Experiment
activation
optimiser
batch-size
similarity
num-lar layers
use- bias
dropout
composition
21

---

Published as a conference paper at ICLR 2022
Table 7: Full results for baseline experiments, including standard deviation across five runs with different random seeds, We report Hits@k for & = 1, 10. mean
reciprocal rank (MRR), and adjusted mean rank index (AMRI) ( Berrendorf et et al. (2020) For all metrics, larger values indicate better performance. We highlight the best result per column and metric (excluding the Oracle) in bold font.
65.77 + 1.87
13.00 + 1.07
55.05 + 1.11
19.51 1 0.22
75.35 + 1.02 32.61
23.56 + 1.49
70.26 + 0.83
35.67 + 0.28
81.60 + 0.80
40.67 + 1.31
80.49 + 0.81
47.85 0.43
71.52 + 1.37
22.23 1.21
64.21 + 0.86
30.04 + 0.21
0.61
98.91 + 0.11
99.10 + 0.12
98.55 + 0.10
1p-21 2--21
53.94
76.96
47.00
88.76
99.97
51.77 1
3.33 + 0.33
42.39 + 0.68
18.17 0.25
56.89 06.89 0.47
7.40 1 0.67
51. 33 0
25.75 0.26
61.81 4
16.77 = 1.44
61 61.05 F 0.92
48 0.31
55.20 +.0+0.555 0.52
8.16 1 0.62
49.09 09 0.63
24.49 0.22
73.14 + 2.39
83.44 33.44 + 0.95
85.46 1 0.82
86.18 + 0.60
2i 2i-1p 1p
7.02
15.20
35. 35.48
32.74
15.84
99. 88
78.58 1 1.44
6.97 64.72
78.93 + 3.20
74.27 0.32
+.77
81 11.55 1 4.70
89.84 + 1 1.90
85. 15.43 + 0.37
02.64 0.65
91.74 1.83
95.31 + 0.78
90.66 0.22
83.78 + 1.00
74.52 1 5.35
85.17 + 2.33 33
80.62 0.28 0.288
98. 98.65 65 4 0.33
99. 95.95 + 0.01
99 $9.96 + 0.01
98. 18.37711 0.13
31
94.07
87.56
98.36
92.64
99.67
96.34
100.00
Hits (%)
55.11 1 1.26
36.8 87 = 2.22
49.67 + 1.86
40.35 0.82
Hits (%)
67.98 = 0.93
53.45 - 2.60
68.31 0.77
55.83 - 0.42
Hits 10 (%)
0.53
69.74 1 1.43
81 25 0.45
67.79 0.42
MRR (%)
63.14 = 0.97
48.01 + 2.13
61.01 = 1.17
50.27 + 0.57
AMRI (%)
93.63 + 0.81
98 = 0.12
99 99.24 = 0.10
96.34 + 0.30
2i
75.67
88. 12
77.78
95.54
83.00
99.99 .9
68
45.85 1 0.81
7.57 + 1.59
42.80 + 0.50
11.53 0.13
5 0.58
15.44 + 1.56
1.56
15.45 0.88
25.24 + 0.27
65.50 + 0.39
24.66 + 2.15
63.65 + 0.60
38.45 0.18
52.96 + 0.61
14.05 + 1.72
50.77 0.54
21.25 + 0.14
+ 2.94
95.92 0.11
96.00 + 0.28
95.79 0.20
3p
13.86
55. 45
21.74
38.47
22.65
74.62
99.88 99.83
39.98 + 0.27
2.97 + 0.21
38.82 + 0.41
12.92 1 0.25
46.4 + 0.32
6.38 + 0.32
45. 45.58 + 0.74
21.34 + 0.34
50 + 0.44
12.76 0.92
50. 50.86 + 0.39
29.94 0.35
44.13 1.3::.224 0.28
6.73 + 0.28
43 43.42 42 + 0.48
19.10 19.10 0.27
68. 15.11 + 2.52
81 25 0.46
86.63 + 1.41
90.56 + 0.47
2p
7.19
13.06
24.11
13.44
99.77
20.91 1.11
11.62 + 0.68
24.26 +: 0.88
18.30 30 0.31
35.58 + 0.82
25.54 + 0.28
40.12 + 1.37
31.98 + 0.23
51.72 1 0.66
45.04 + 1.18
55.17 1 1.00
44 93 0.35
30.98 + 0.91
22.25 4 0.25
34.78 1.07
27.55 + 0.19
78.44 78.44 1.78
08.14 0.21
88 88.03 03 + 0.22
1p
37.87
61.65
81.03
52.64
99.97
Base Triple
Reification
Zero Layers
Base Triple
Relfication
Zero Layers
Base Triple
Reification
Zero Layers
Base Triple
Reification
Zero Layers
Base Triple
Reification
Zero Layers
Pattern
StarQE
Oracle
StarQE
Oracle
StarQE
Oracle
StarQE
Oracle
StarQE
Oracle
22

---

Published as a conference paper at ICLR 2022
Table 8: Full results for the generalization experiments. including standard deviation across five runs with different random seeds. We report Hits for
k = 1, 10, mean reciprocal rank (MRR), and adjusted mean rank index (AMRI) Berrendorf al. 2020). For all metrics, larger values indicate better performance.
65. 65.77 77 + 1.87
59.74 3.29
48 48.54 + 5.09
28. + 1.40
18.75 1 1.55
75.35 - 1.02
71.20 = 2.45
55.96 + 5.31
44.88 1.30
32.31 2.60
81 60 = 0.60
80.49 1.92
62.80 + 5.26
61.02 = 0.70
50.92 + 3.44
71.52 + 1.37
67.04 1 2.70
53, 23.58 + 5.03
39.81 1.20
29 29.25 + 2.05
0.61
98.49 0.40
82.59 1 8.45
99.04 + 0.16
99 25 = 0.06
1p-21 2--21
88.76
1
37.59 + 2.88
2.17 1 0.87
6.84 0.58
5.59 5.59 0.72
56.89 + 0.47
46.99 + 3.04
3 3.80 + 1.05
10.08 + 1.08
8.56 0.59
61.81 1 0.37
57.49 + 2.26
6.79 1.79
14.75 1.42
13.50 0.81
55.20 + 0.52
41.24 1 2.73
3.73 + 0.94
9.62 + 0.85
8.32 - 0.52
73.14 1 2.39
83.24 + 1.08
37.80 + 22.89
85.61 + 2.86
86 54 114:111 1.56
2i-1p
51.77
13.50
78.58 + 1.44
77.36 + 1.46
81 2 3.63
60.67 2.23
63.93 1.336
87.97 + 1.23
89.91 2.87
86.17
0.58
0.65
94.20 +
93.55 + 1.93
96.32 +
97.22 1 0.14
1.00
83.49 1 1.24
3.11
74.35 1.70
77.29 + 0.86
0.33
99.93 + 0.03
99.96 09.96 + 0.01
99 99.97 .7 + 0.00
87.56
92.64 12.640.00
+
31
90.07
83.78
86.28
98.65
Hits (%
1 1 1.26
52. 49 + 1.45
53.36 + 3.46
41.01 = 1.49
41 41.36 1 0.59
Hits (%)
67.98 = 0.93
1 1.24
3.18
1 1:21
14 - 0.97
Hits 10 (%)
77.78 1 0.53
78.79 + 1.04
75.86 2.45
83.04 1.01
83. 83.77 + 0.47
MRR (%)
63. 13.145 13.14 + 0.97
61.72 1 1.18
61.45 3.13
1.30
56.81 0.69
AMRI (%)
93.63 1 0.81
99.01 + 0.20
90.68 1 5.62
99. 49 - 0.05
57 + 0.02
21
55.11
67.02
66.56
66.87
56.16
99. 99.57
68.
45.85 + 0.81
43.8 0.98
19.86 4
12. 1.59
10.52 1 2.09
57.34 = 0.58
1 1.21
4 6.37
2.58
2.58
2.69
0.39
1.72
4.96
34.19 3.78
0.61
51.71 1.18
19.72 2.23
2
2.94
95.60 + 0.58
74.93 + 10.70
92.00 3.04
92.08 1.43
31.14
27.94
3p
55.41
30.47
21.48
18.25
65.50
66.39
44.36
52.96
74.62
We highlight the best result per column and metric in bold font.
39.98 + 0.27
37.15 0.65
6.78 - 2.24
3.81 = 03.8
3.24 1 0.62
0.32
43.75 = 0.98
3.23
7.15 7.15 0.65
6.34 0.82
+ 0.44
51.10 + 1.40
16.45 = 3.56
12.57 0.96
12.02 # 1.12
44.13 0.28
41.99 + 0.88
10.09 2.70
6.79 6.79 0.56
0.74
68.11 1 2.52
5171 13.25
83. 83.25 25 2.61
82.93 1.83
$7.17
2p
46.41
10.73
51.20
20.91 + 1.11
21.63 = 0.70
23.06 + 1.12
16.53 + 0.48
25.52 1 0.36
35.58 = 0.82
38.79 + 0.92
36. + 1.11
30.82 + 0.75
41 41.26 0.65
51.72 1 0.66
55.44 + 1.35
50.10 + 1.34
48.48 48 + 0.59
58.43 + 0.29
30.98 + 0.91
33.04 + 0.84
32.01 + 1.00
26.83 + 0.53
36 36.36 38
78.44 + 1.78
88. + 0.45
73.20 + 11.74
93.77 + 0.09
95 68 + 0.09
1p
MPQE-like + Reif
MPQE-like + Reif
MPQE-like + Reif
MPQE-liKe like + Reif
MPQE-like like + Reif
StarE-like
Q2B-like like
em Like
like
MPQE-like like
StarE-like
22B-like
emQL-lik, like
MPQE- like
StarE-like
Q2B-like
emQL like like
MPQE-liK like
StarE-liike
Q2B-like
emQL like
like
MPQE- like
StarE-like
Q2B-like
like
emQL- like
MPQE-lik
Pattern
23


Reviews:
[{"review_id": "yPcPEbXdeR", "reviewer": "Reviewer_Bute", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strengths.\n- S1. They proposed the first query embedding approach for a graph with qualifiers.\n- S2. The proposed approach is compared with three baselines including the reification baseline.\n- S3. A new evaluation dataset is proposed.\n\nWeaknesses.\n- W1. Some of important information had to go to Appendix due to space. For example, I think the best hyperparameters used in the experiment can stay in the main paper.\n- W2. The proposed approach performs worse than the reification baseline when the problem is easier and the answer can be narrow down with traditional conjunctions.\n- W3. Another baseline of embedding the entire edge-qualifiers pair as a unit rather than representing the qualifiers as separate nodes is not considered. It can be predicted that this baseline is not suitable for a large number of possible qualifier values, but can be easily applicable to the suggested example by considering three atomic relations instead of qualifiers: educatedAt-BSc, educatedAt-MS, educatedAT-PhD.", "summary_of_the_paper": "This paper proposes a novel problem to embed query graphs with edge qualifiers to query a hyper-relational knowledge graph, and a solution extending an existing approach for a non-hyper-relational knowledge graph. Due to the lack of evaluation datasets, they propose to use a hyper-relational knowledge graph extracted from Wikidata. They also consider three baselines that can show the characteristics of the proposed approach, including reification baseline that transforms qualifiers to nodes. The overall performance shows the proposed approach shows benefit over the baselines, and usefulness when edge qualifiers are available.", "summary_of_the_review": "I think this is a solid piece of work extending the problem space solved by modern embedding techniques. The presentation is mostly solid, and easy to read and understand. There is some very minor presentation issues that can be improved such as adding the best hyperparameters in the main paper, or adding the missing node color in the legend in Figure 4 or maybe using \"Oracle-\" instead of just \"Oracle\" which can be a bit misleading. But otherwise, this paper is well written with a clear goal and contributions, and evaluations. Since in case of limited set of qualifier values, the edge+qualifiers can be easily represented and embedded as altogether, it would be interesting to see the comparison with such a baseline. But I don't think this is necessary to show the value of this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nAobUssFsFL", "reviewer": "Reviewer_GQAR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The challenge of multi-hop logical reasoning is not clearly stated. I suggest that the author should discuss the challenge in detail.\n\nIn the MODELDESCRIPTION section, the author should first explain the challenges of solving the problem and how the proposed method is solved.I suggest the author introduce it in detail.\n\nIn the introduction of related work, the author did not analyze the advantages and disadvantages, and did not discuss the proposed method, which could not prove the innovation of the proposed method \n\nThere is little description of Query Embedding in this paper.Suggeest the author to add more space to introduce it.\n\nThe abstract of the experimental results is not specific enough.\n\nThere is only few references in the past 3 years. It is recommended to ensure the latestness of the literature when investigating related work, otherwise it is difficult to persuade the work to be novel.", "summary_of_the_paper": "This paper studies how to embed and answer hyper-relational conjunctive queries based on recent advancements in Graph Neural Networks and query embedding techniques. And propose a method to answer such queries and demonstrate in their experiments that qualifiers improve QA on a diverse set of query patterns. This paper has a certain novelty.", "summary_of_the_review": "This paper propose a method to answer such queries and demonstrate in their experiments that qualifiers improve QA on a diverse set of query patterns. The logic is clear. The argument is complete and the grammatical expression is very standard. However, in the process of demonstration, there is a lack of description of the challenge and thinking about how to solve the problem. I think the authors needs to improve the writing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kAKfkh8ydL2", "reviewer": "Reviewer_iDXR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This paper proposed StarQE for question answering over hyper-relational knowledge graphs. Overall, the motivation is strong, and the method is technically sound. \n#####Pros#####\n1. The task is well-motivated and interesting. It can deal with the question-answering task with qualifier pairs (Yet, some contextual information is not allowed).\n2. The proposed model is simple but performs well on certain types of queries. And it has a certain generalization capability.\n3. A new dataset is constructed in order to verify the model efficacy. \n4. The paper is well-written and easy to follow.\n\n#####Cons#####\n1. The experiments could be more convincing by using more datasets. Currently, only one dataset is used. It is not sure that if this method can also be used on other datasets or domains. Also, since the model can handle triple-only scenarios, I suggest the authors also consider reporting the performances on Freebase and Nell as done in query2box, as such, we can see whether or not this model can deal with more basic cases. \n2. The novelty is limited. The model is just a combination of two existing approaches. \n3. It cannot handle queries about numbers, text, and time. While some existing methods [a][b][c] can handle such information in knowledge graph embeddings.  Those important references are missing and should be used as baselines especially on 1p queries. \n4. Important reasoning operators such as negation, disjunctions are not considered, making the approach less attractive. I guess we can draw some insights from betaE for this type of operator.\n5. I suggest the authors add some baselines in Table 2 so that we can know the differences between StarQE and baselines in generalization capability.\n\n#####Question#####\nCan the model benefit from nonlinear layers (transformations)?\n\n[a] Knowledge Graph Embedding with Numeric Attributes of Entities, ACL 2018\n[b] Incorporating Literals into Knowledge Graph Embeddings, ISWC 2019\n[c] Beyond Triplets: Hyper-Relational Knowledge Graph Embedding for Link Prediction, WWW 2020\n", "summary_of_the_paper": "This paper studies the multi-hop logical reasoning problem with hyper-relational knowledge graphs. In hyper relational knowledge graphs, edges are associated with some key-value pairs used for describing the contextual information. The goal of this paper is to incorporate such information in order to provide more fine-grained question answering. Specifically, StarQE, a combination of MPQEand StarE, is proposed to achieve this goal. The authors constructed a new dataset, WD50K-QE, and the experimental results show that StarQE can effectively model the qualifiers in the dataset.", "summary_of_the_review": "The current version of this paper is marginally below the acceptance threshold. I believe some improvements can be made to strengthen the paper.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SoYgezNkLlK", "reviewer": "Reviewer_frRt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper is well written and is an important step in the direction of handling multiple representations of knowledge graphs. Most existing approaches are focused on triple based techniques, however ignoring complex but more expressive representations such as reification and/or qualifiers. Therefore, in terms of novelty of the problem, this work clearly seems to be taking the next step in query embeddings. The approach is an interesting and valid combination of other approaches to solve the problem. The evaluation of the dataset clearly shows that the approach works.\n\nMy main concerns of this work is as follows:\n1. The aspect of entering a new territory should also be backward compatible with older representations. This raises the question of the performance of the system on Freebase datasets primarily evaluated by other state of the art approaches such as BetaE, Query2Box, EmQL etc. \n2. EmQL evaluates faithfulness of the overall approach. It is also important to measure how well the work performs on complete knowledge graphs and not only incomplete ones. Have the authors tried to do this?\n3. The change from Query2Box, EMQL to Beta Embeddings was its way of handling negation and disjunction operators. How does this work compare in terms of handling the operators of EFOL? \n4. Why does Oracle's performance drop for 3p queries and how does the proposed approach handle them better? If there are qualitative analysis on this it would be great. \n5. Can you please elaborate on StarE-like row in Table 2? I am not convinced that it is an apples to apples comparison to the other rows in the table. \n ", "summary_of_the_paper": "The paper presents an approach for embeddings queries over hyper relation graphs. Hyper-relational graphs, specifically those that have context are usually represented and encoded as regular triples by the existing approaches. To do so, the work represent the hyper-relational graphs as FOL with parameterizing the predicate to include context. The model is a combination of three architectures where firstly encodes the query graph using StarE, then CompGCN to aggregate for representing qualifiers, and MPQE for learning the query embeddings. In order to evaluate this approach, the work defines a new dataset on Wikidata because of reified triples/qualifiers. ", "summary_of_the_review": "The paper is well written and addresses an important direction is handling more complex representations of knowledge graphs. The work seems solid however lacks some aspects of evaluation. It is unable to justify that it is backward compatible to the original datasets which would be of great value even though not being at par with the state of the art approaches. In other words, it is ok to show drop in performance on Freebase datasets but claim generalizability over both traditional representations and KGs with reification. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2oXVs_1mI3", "reviewer": "Reviewer_wJVm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strength:\n- The paper is well-motivated, and the authors propose a reasonable solution to the hyper-relational KG QE problem.\n- Experiments show that the proposed problem outperforms most of the previous methods that only use triple-only graphs.\n- The authors prepare a new dataset for the hyper-relational KG QE problem.\n\n\nWeakness:\n- The description of their proposed method is not very clear. For example, \"we use X[y] to indicate the representation of y in X\" in the Qualifier Representation paragraph of Sec 4. Readers may be confused about the meaning of “X”. The authors should explain that “X” can be E, R, etc.\n- In table 1, compared with Reification, the performance improvement of StarQE is not very obvious.\n \n\nQuestions:\n- Could you clarify whether “StarE-like” in table 2 is the same as “StarQE” in table 1? It is better to use a more consistent name or explain their relation more clearly in Table 2 caption.\n", "summary_of_the_paper": "In this paper, the authors propose a framework to learn the query embeddings for hyper-relational KGs, which allows QA over hyper-relational KGs with more complex questions and makes use of the qualifiers. They also introduce a new hyper-relational KG QA dataset, WD50K-QE, for the evaluation of their proposed method. Experiments show that qualifiers help their framework achieve more accurate results in general compared with the baselines that use information from triple-only graphs.\n", "summary_of_the_review": "   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a query embedding approach for answering multi-hop queries over a hyper-relational knowledge graph (KG). The main contributions are a new dataset (WD50K-QE) for this task and a simple but sensible extension to an existing model for query embeddings to also handle relation qualifiers. Reviewers wJVm and Bute note that the reification and StarQE models perform similarly. While this is not a negative result, as the authors note, it does raise the question of the relative pros and cons of the two methods. I hope the authors can add a discussion of when one might prefer StarQE over the conceptually simpler reification method in the final version. The authors addressed Reviewer frRt’s concerns about faithfulness and backwards compatibility (though more evidence on purely triple-based tasks would be nice here). Reviewer GQAR also raised some concerns about writing, but the other reviewers mostly found the paper to be well written and well motivated and I tend to agree. Overall, while there are some very good suggestions on how the paper can be extended and improved, I find the current contributions to be substantial enough to warrant a publication.
Decision: Accept (Poster)