Regex Queries over Incomplete Knowledge Bases
Year: 2021

Abstract:
We propose the novel task of answering regular expression queries (containing disjunction (∨) and Kleene plus (+) operators) over incomplete KBs. The answer set of these queries potentially has a large number of entities, hence previous works for single-hop queries in KBC that model a query as a point in high-dimensional space are not as effective. In response, we develop RotatE-Box – a novel combination of RotatE and box embeddings. It can model more relational inference patterns compared to existing embedding based models. Furthermore, we define baseline approaches for embedding based KBC models to handle regex operators. We demonstrate performance of RotatE-Box on two new regex-query datasets introduced in this paper, including one where the queries are harvested based on actual user query logs. We find that our final RotatE-Box model significantly outperforms models based on just RotatE and just box embeddings.

heading: 1. Introduction
text: Knowledge Base Completion (KBC) predicts unseen facts by reasoning over known facts in an incomplete KB. Embedding-based models are a popular approach for the task – they embed entities and relations in a vector space, and use a scoring function to evaluate validity of any potential fact. KBC models are typically evaluated using single-hop queries, example, “Who founded Microsoft?”, which is equivalent to the query (Microsoft→ founded by → ?). A natural extension [Guu et al., 2015] poses multi-hop queries, such as (Microsoft → founded by → · → lives in→?), which represents “Where do founders of Microsoft live?”. Recent works have also studied subsets of first-order logic queries with conjunction (∧), disjunction(∨) and existential quantifiers (∃) [Hamilton et al., 2018, Ren et al., 2020].
We analyzed real-world query logs1 over the publicly available Wikidata KB2 and extract its distribution of queries. We found (see Table 1) that while the single hop queries are indeed most frequent (87%), multi-hop queries comprise only 1% of all queries. A substantial fraction of queries (12%) are queries using regular expression operators (regex), which use disjunction (∨) or Kleene plus (+) operators. In response, we pose the novel problem of answering regex queries using embedding-based KBC models.
∗Work done as a research intern at IIT Delhi 1https://iccl.inf.tu-dresden.de/web/Wikidata_SPARQL_Logs/en 2https://www.wikidata.org/wiki/Wikidata:Main_Page
Regex queries have a potentially large set of correct answers, due to which typical embedding models that model both queries and entities as points are not very effective. We build on one such model RotatE, which models a relation as a rotation of entity vectors – it can model all relation patterns gen-
erally observed in a KB except hierarchy and has not been extended to queries beyond single-hop. There also exists Query2Box [Hamilton et al., 2018], a box embedding method which models a query as a high-dimensional axis-aligned box. This can better handle larger answer spaces, but it cannot model symmetric relations (e.g. friend of ).
To answer the full repertoire of regex queries over incomplete KBs, we propose a new baseline, RotatEBox – a RotatE model augmented with box embeddings. In our model, a regex query is an axis-aligned box. Application of a relation or regex expression rotates the center (vector) of the box, and enlarges/shrinks the box. Application of a regex operator is handled using two approaches: (1) learned operators over boxes, or
(2) introducing separate embeddings for Kleene plus of a relation, and expanding a disjunction into multiple non-disjunctive queries. RotatE-Box can capture all typical relation patterns – symmetry, antisymmetry, inversion, composition, intersection, mutual exclusion and hierarchy, along with effectively handling a large number of correct answers.
We also contribute two new datasets for our task. Our first dataset, called FB15K-Regex, is an extension of the popular FB15K dataset [Bordes et al., 2013], and is constructed using random walks on the FB15K graph. Our second dataset is built over a dense subset of Wikidata (which we name Wiki100) and is based on the real queries from existing query logs. Table 2 lists example queries in the datasets. We find that models based on RotatEBox outperform all other baselines, including strong models based on just RotatE and just Query2Box on these two datasets. In summary, our work presents a novel regex query answering task, two new datasets and a strong baseline for our task. We will release all resources for further research3.

heading: 2. Related Work
text: A KB G is a set of triples (e1, r, e2), where e1, e2 ∈ E (the set of entities) and r ∈ R (the set of relations). For a KBC task, all triples are split into train/dev/test, resulting in graphs Gtrain, Gdev, and Gtest. The standard KBC task requires answering single-hop queries of the form (e1, r, ?) with the answer e ∗ 2 if (e1, r, e ∗ 2) ∈ Gtest. While many kinds of solutions exist for this problem, we build on the vast literature in embedding-based approaches [Bordes
3https://github.com/dair-iitd/kbi-regex
et al., 2013, Socher et al., 2013, Yang et al., 2014, Trouillon et al., 2016, Jain et al., 2018, Sun et al., 2019, Jain et al., 2020]. These methods embed each entity and relation in a latent embedding space, and use various tensor factorization scoring functions to estimate the validity of a triple. Our work builds on RotatE, which defines relation as a rotation in a complex vector space. The distance of target entity from the query constitutes the scoring function. RotatE has shown high KBC performance and can model many relation patterns (see Section 2.1).
The first work on answering complex queries over incomplete KBs extends single-hop queries to path queries (or multi–hop queries) of the type (e1, r1, r2, . . . , rn, ?). Guu et al. [2015] construct datasets for the task using random walks on FB13 and WN11 KBs. Models for the task include compositional training of existing KBC scoring functions and models based on variants of RNNs [Yin et al., 2018, Das et al., 2017]. Recent work has started exploring subsets of first-order logic queries. Hamilton et al. [2018] explore conjunctive queries with conjunction (∧) and existential quantification (∃). They propose DeepSets [Zaheer et al., 2017] to model conjunction as a learned geometric operation. MPQE [Daza and Cochez, 2020] and BIQE [Kotnis et al., 2021] extend this work by constructing a query representation using a graph neural network and transformer encoder respectively.
Probably closest to our work is that of answering Existential Positive First-order (EPFO) logical queries [Ren et al., 2020] – queries that include ∧, ∨, and ∃. They propose Query2Box, which represents a query as a box (center, offset) and each entity as point in a highdimensional space. The points closer to the center are scored higher for the query, especially if they are inside the box. The strength of Query2Box is that it can naturally handle large answer spaces, and also model many relation patterns (see Section 2.1). [Ren and Leskovec, 2020] extend EPFO to complete set of first-order logical operations, by handling negation (¬) with their proposed model, BetaE. They propose high-dimensional Beta distributions as embeddings of queries and entities. The KL divergence between query and entity serves as a scoring function.
There are also other works that work with probabilistic databases for answering EPFO queries [Friedman and Van den Broeck, 2020], but, to the best of our knowledge, there has been no work on answering regex queries over incomplete knowledge bases. In particular, regular expressions that contain the Kleene plus operator, are not included in path queries or first-order logic queries.

heading: 2.1 Relation Patterns in a KB
text: Embedding models can be critiqued based on their representation power [Toutanova and Chen, 2015, Guu et al., 2015, Trouillon et al., 2016, Sun et al., 2019] in modeling commonly occuring relation patterns (relationships amongst relations). We summarize the common patterns and model capabilities in Table 3. Broadly, translation-based methods (that add and subtract embedding vectors) like TransE and Query2Box can model all patterns but cannot model symmetry ((e1, r1, e2) ⇒ (e2, r1, e1)), such as for the relation friend of. Rotation-based models such as RotatE can model all inference patterns except for hierarchy: (e1, r1, e2)⇒ (e1, r2, e2). Other models have other weaknesses, like similaritybased methods (that use dot products between embeddings) such as DistMult and ComplEx
are incapable of handling composition and intersection. Our proposed model combines the power of Query2Box and RotatE and can express all seven common relation patterns.

heading: 3. Task
text: We now formally define the task of answering regular expressions (regex) queries on a KB. Regular expressions are primarily used to express navigational paths on a KB in a more succinct way and to extend matching to arbitrary length paths. Any regex c in a KB is an expression over R ∪ {+, /,∨}, generated from the grammar: c ::= r | c1 ∨ c2 | c1/c2 | c+, where r ∈ R represents a relation in the KB and c1 and c2 represent regular expressions. / denotes followed by, ∨ denotes disjunction, and + is a Kleene Plus operator denoting one or more occurrences. We use l(c) to denote the set of paths (sequence of relations) compatible with regex c. As an example, for c = r1/r + 2 , l(c) will have paths like r1/r2, r1/r2/r2, r1/r2/r2/r2 and so on. Their path lengths will be 2, 3 and 4 respectively.
A regex query q over a KB is defined as a pair of head entity e1 and a regular expression c. For query q = (e1, c, ?), we define the answer set JqK as the union of entities reachable from e1 in G, by following the paths in l(c): JqK = ⋃ p∈l(c)J(e1, p, ?)K. The goal of the task is to, given a query q, rank entities in JqK higher than other entities.

heading: 4. Model
text: We now describe RotatE-Box – a model that combines the strengths of RotatE and Query2Box. Following Query2Box, the relations and queries are modeled as boxes, and entities as points in a high-dimensional space. However, unlike Query2Box, all points (and boxes) are in a complex vector space Ck, instead of a real space.
We first describe the model for single-hop queries. RotatE-Box embeds each entity e as a point e ∈ Ck and each relation r as a box r, represented as (Cen(r),Off(r)) ∈ C2k. Here Cen(r) ∈ Ck is the center of the box such that its modulus in each of the k dimensions is one, i.e., ∀j ∈ [1, k], |Cen(rj)| = 1, Cen(rj) ∈ C. By doing so, Cen(rj) can be re-written as eiθr,j using Euler’s formula (here, e is Euler’s number). This corresponds to rotation by angle θr,j in the jth dimension of complex vector space. In vectorized form, Cen(r) = eiθr . Off(r) is a positive offset, i.e., Re(Off(r)) ∈ Rk≥0 and Im(Off(r)) ∈ Rk≥0. Any box that satisfies these constraints on its center and offset is termed as a rotation box. A point v ∈ Ck is considered
inside a box if it satisfies:
Re(rmin) ≤ Re(v) ≤ Re(rmax) and Im(rmin) ≤ Im(v) ≤ Im(rmax) (1)
Here, rmax = Cen(r) + Off(r) ∈ Ck, and rmin = Cen(r) − Off(r) ∈ Ck. The inequalities represent element-wise inequality of vectors. A single-hop query q = (e1, r, ?) has a rotation box representation q given by (e1 Cen(r),Off(r)). Here is the Hadamard product (element-wise multiplication). Since Cen(r) = eiθr , e1 is rotated by an angle θr ∈ Rk. Specifically ej is rotated by angle θr,j in the j
th dimension. Given a query q associated with a box q, RotatE-Box ranks entities e in the order of the distance of e from q, defined as:
dist(e;q) = distout(e;q) + α · distin(e;q) (2)
where α ∈ (0, 1) is a constant to downweigh the distance inside the query box, and
distout(e;q) = ‖Re(Max(e− qmax,0) + Max(qmin − e,0))‖1 + ‖Im(Max(e− qmax,0) + Max(qmin − e,0))‖1
distin(e;q) = ‖Re(Cen(q)−Min(qmax,Max(qmin, e)))‖1 + ‖Im(Cen(q)−Min(qmax,Max(qmin, e)))‖1
Here qmax and qmin are defined analogously to rmax and rmin above. This completes the description of RotatE-Box for single-hop queries. As RotatE is a special case of RotatE-Box (by modeling Off(r) = 0,∀r ∈ R), RotatE-Box can model all the relation patterns modeled by RotatE: symmetry, anti-symmetry, inversion, composition, intersection and mutual exclusion. Additionally, boxes enable modeling hierarchy.
Theorem 1. RotatE-Box can model hierarchical relation pattern. (Proof in Appendix A.1)

heading: 4.1 Relation Paths
text: We now define RotatE-Box operations for a path query, e.g., q = (e1, r1/r2/ . . . /rn, ?). It first initializes the rotation box embedding for relation path as r1 (denoted by p1). Given pi, to continue the path with ri+1, it rotates the center of pi, and adds the offsets:
Cen(pi+1) = Cen(pi) Cen(ri+1) Off(pi+1) = Off(pi) + Off(ri+1) (3)
The final rotation box embedding p of r1/r2/ . . . /rn is pn as computed above. It computes query embedding q as described earlier – rotating e1 by Cen(p) and keeping the offset as Off(p). Ranking of answers for the query follows similar approach as specified in Eq 2.

heading: 4.2 Kleene Plus
text: To extend path embeddings to general regex expression c, we follow the same representation: for a regex query (e1, c, ?), c is embedded as a rotation box, c, in complex space C2k. We first describe our formulation for the Kleene Plus (+) operator. We use two methods for this.
Projection: Kleene Plus (+) operator may apply compositionally and recursively to any regular expression. An approach to materialize this is to define it as a geometric operator
[Hamilton et al., 2018], which takes input a rotation box representation c (corresponding to rotation by θc), applies a function kp to output a new rotation box embedding c
′ that represents c+. RotatE-Box uses the function kp(c) = c′ = (eiθc′ ,KoffOff(c)), where θc′ = Kcenθc. Here, Kcen ∈ Rk×k,Koff ∈ Ck×k are trainable parameter matrices. Free parameter: A strength of the geometric operator is that it can be applied compositionally, whereas a weakness is that its expressive power may be limited, since the two K matrices apply on all occurrences of Kleene plus. As an alternative, for every relation r, we define free parameter rotation box embeddings of r+ denoted by r+. The query q = (e1, r
+, ?) is then represented as (e1 Cen(r+),Off(r+)). Such a formulation cannot handle compositional queries like (e1, (r1 ∨ r2)+, ?) or (e1, (r1/r2)+, ?). However, the motivation behind this formulation is that most of the Kleene plus queries in user query logs of Wikidata do not require Kleene plus operator to be compositional (Table 9).

heading: 4.3 Disjunction
text: We follow two approaches for modeling disjunction (∨). In one case, we split a disjunction into independent non-disjunctive regexes. In the second case, we train a disjunction operator.
Aggregation: This approach follows Ren et al. [2020], who proposed transforming EPFO queries to Disjunctive Normal Form (DNF), moving disjunction operator (∨) to the last step of computation graph. While all regex expressions cannot be transformed to a DNF form, a significant fraction (75%) of regex queries in our dataset formed from Wikidata user query logs (Section 5) can be expressed as a disjunction of a tractable number of nondisjunctive constituent queries q = q1 ∨ q2 ∨ . . .∨ qN . For example, q = (e1, r1/(r+2 ∨ r + 3 ), ?) can be expressed as q1 ∨ q2 where q1 = (e1, r1/r+2 , ?) and q2 = (e1, r1/r + 3 , ?). For such queries, following Ren et al. [2020], we compute scores independently for each query, and aggregate them based on the minimum distance to the closest query box, i.e. dist(e;q) = Min({dist(e;q1),dist(e;q2), . . . ,dist(e;qN )}). Notice that this approach is not applicable if such a query decomposition is not feasible, such as for (r1 ∨ r2)+. DeepSets: Zaheer et al. [2017] introduce a general architecture called DeepSets for functions where the inputs are permutation invariant sets. As disjunction (∨) is permutation invariant, we use DeepSets to model it. We define an operator D which takes the rotation box embeddings c1, c2, . . . , cN of regular expressions c1, c2, . . . , cN (corresponding to rotation angles θc1 , θc2 , . . . , θcN ), and returns the embedding of c = c1 ∨ c2 ∨ . . . ∨ cN , denoted by c. RotatE-Box defines D(c1, c2, . . . , cN ) = (eiθc ,Off(c)) as follows:
θc = Wcen ·Ψ(MLPcen(θc1),MLPcen(θc2), . . . ,MLPcen(θcN )) Off(c) = Woff ·Ψ(MLPoff(Off(c1)),MLPoff(Off(c2)), . . . ,MLPoff(Off(cN )))
where MLPcen, MLPoff are Multi-Layer Perceptron networks, Ψ is a permutation-invariant vector function (element-wise min, max or mean), and Wcen, Woff are trainable matrices.

heading: 4.4 Training objective
text: Following the previous work [Sun et al., 2019, Ren et al., 2020], we optimize a negative sampling loss to train RotatE-Box. Let γ be a constant scalar margin. For a query q with
answer entity e, and a negative entity not in answer set e′i, the loss is defined as:
L = −logσ(γ − dist(e;q))− n∑ i=1 1 n logσ(dist(e′i,q)− γ) (4)

heading: 5. Dataset
text: We contribute two new regex query datasets for our task – the first is based on Wikidata4 [Vrandečić and Krötzsch, 2014a], a large popular open-access knowledge base, and the second is based on FB15K [Bordes et al., 2013], a subset of the Freebase KB commonly used in KBC tasks. For both datasets, we first split facts in original KB G into three subsets to construct Gtrain, Gdev, and Gtest (using existing splits for FB15K). These are used to split regex queries into train, dev and test sets.
Wiki100-Regex: The Wikidata KB contains over 69 million entities, which makes it difficult to experiment with directly. We first construct a dense subset based on English Wikidata, with 100 relations and 41,291 entities, and name it Wiki100. This knowledge base contains 443,904 triples (Appendix B.1 has more details on Wiki100 construction).
Existing work on KBC with complex queries uses datasets built using random walks over KB [Guu et al., 2015, Kotnis et al., 2021] or uniform sampling over query DAG structure [Hamilton et al., 2018, Ren et al., 2020]. The availability of a large-volume of query (SPARQL) logs over Wikidata, offers us a unique opportunity to use real-world user queries for Wiki100-Regex. On studying the query logs, we find that 99% of regex queries (excluding single-hop queries) are of five types – (e1, r + 1 , ?), (e1, r + 1 /r + 2 , ?), (e1, r1/r + 2 , ?), (e1, r1∨r2, ?), and (e1, (r1∨r2)+, ?). We retain all regex queries from these types as the final set of queries. To split the user queries into train/dev/test, we traverse each user query (e1, c, ?) up to depth 5, where c is the regex expression. For every answer entity e2 reachable from e1 following c in Gtrain, we place (e1, c, e2) in train split. If e2 is not reachable in Gtrain, but reachable in Gtrain ∪ Gdev, we place (e1, c, e2) in dev split, else in test split. We further augment the training split with random walks on Gtrain for these 5 query types. The final regex query type distribution is given in Table 9 in Appendix B.2.
FB15K-Regex: This dataset is constructed with the goal of testing our models on a higher diversity of regex queries than Wiki100-Regex. We identify 21 different types of regex expressions, using up to three different FB15K relations along with Kleene plus (+) and/or disjunction (∨) operators. For each regex expression type c, we enumerate a set of compatible relations paths
l(c), up to length 5. For a random source entity e1, the answer set of regex query q = (e1, c, ?) is formed by aggregating the answer sets of compatible relations path queries, i.e. JqK = ⋃ p∈l(c),len(p)<=5J(e1, p, ?)K. We discard generic queries that have answer set size
4https://www.wikidata.org/
of over 50 entities. This procedure results in a highly skewed dataset, with 3 query types accounting for more than 80% of the regex queries. We reduce the skew in the query distribution by undersampling frequent query types. The final dataset statistics for each regex query type are summarized in Table 8 in Appendix B.2. The split into train/dev/test sets follows a procedure similar to one used when constructing Wiki100-Regex data. The dataset statistics of both the datasets are summarized in Table 4.

heading: 6. Experiments
text: In this section, we run experiments on the two datasets introduced in Section 5. We compare our RotatE-Box model with two competitive methods for complex query answering – Query2Box and BetaE, along with a close baseline, RotatE. We also wish to find out the performance difference between compositional and non-compositional variants to handle disjunction and Kleene plus.

heading: 6.1 Experimental Setup
text: Baselines and model variants: We note that regex variants of distribution-based models like BetaE and distance-based models like Query2Box and RotatE can also be created by applying similar ideas as in Sections 4.1-4.3 (Appendix A.2). For each of the three models, we experiment with all possible combination of operators: • KBC + Aggregation (BASELINE): In this variant, we only train on single hop queries (link prediction), (e1, r, ?), and evaluate the model on regex queries by treating r
+ as r, and using Aggregation operator for handling disjunction.
• Free parameter + Aggregation: In this variant, Kleene plus is modeled as a free parameter for every relation and disjunction is handled via Aggregation.
• Free parameter + DeepSets: In this variant, Kleene plus is modeled as a free parameter and disjunction is handled via DeepSets.
• Projection + Aggregation: In this variant, we use Projection for Kleene plus and aggregation for disjunction.
• Projection + DeepSets (COMP): In this variant, we use Projection for Kleene plus and DeepSets for disjunction. Unlike other variants, both the operations are compositional and hence, can be applied to any arbitrary regex query.
Apart from Projection + DeepSets (COMP), none of the other variants listed above can answer every query type, due to the presence of non-compositional operators for regex. For example, the query type (e1, (r1/r2)
+, ?) cannot be answered by these variants. In such cases, the query is not evaluated and the rank of correct entity is simply returned as ∞. Evaluation metrics: Given a regex query q = (e1, c, ?), we evaluate validity of e2 as an answer of the query by ranking all entities, while filtering out other entities from the answer set JqK [Bordes et al., 2013]. The candidate set for query q, C(q), can then be defined as C(q) = {e2} ∪ {E − JqK}. We calculate the rank of e2 amongst C(q) and compute ranking metrics such as Mean Reciprocal Rank (MRR) and Hits at K (HITS@K).
Implementation details: An embedding in complex vector space has two trainable parameters per dimension (real and imaginary part) whereas a real valued embedding has
only one. Therefore, to keep the number of trainable parameters comparable, we use k = 400 for complex embedding based models (RotatE and RotatE-Box) and k = 800 for real embedding based models (Query2Box). Relation and entity embeddings of all the models are first trained on single-hop queries (e1, r, ?), and then optimized for regex queries along with other trainable parameters of regex operators. For Kleene plus operator (free parameter variant), r+ is initialized as r. We use element-wise minimum function for Ψ. Other training specific details and hyperparameter selection are in Appendix C.1.

heading: 6.2 Results and Discussions
text: Table 5 shows the main results of different embedding based models with different variants for Kleene plus and disjunction on both datasets. Overall, we observe that the compositional variants of all models outperform non-compositional ones. RotatE-Box obtains significant improvements over other distance-based methods – RotatE and Query2Box (correspondingly for all variants). RotatE-Box variants also perform comparably to BetaE models for FB15K-Regex, and significantly outperform them for Wiki100-Regex. Comparing best and second best results, RotatE-Box(COMP) achieves 0.65 points MRR over BetaE(COMP) for FB15K-Regex, and over 3.7 points MRR over RotatE(COMP) for Wiki100-Regex. The massive improvement of both COMP and other variants over BASELINE highlights the necessity of training KBC models beyond single-hop queries.
Recall that for each model, all variants except COMP contain only non-compositional regex operators, hence, a portion of queries are not evaluated, and the score for those queries is returned as 0. To get better insights into operators, we look at the subset of regex queries that are answerable by all variants. In our experiments, this subset includes all regex query types except (e1, (r1 ∨ r2)+, ?). The results of this ablation study are presented in Table 6. While RotatE-Box maintains its superior performance over other models on
this subset of regex queries, both the formulations of Kleene plus operator – Projection and Free parameter, have almost similar performance, with Free parameter variant showing marginally higher MRR and HITS@1 in most cases. In particular, (Free parameter + DeepSets) for RotatE-Box on Wiki100-Regex is better than (COMP) by more than 1.3 points MRR. This suggests that the simple Projection operator does not always achieve quite the same expressiveness as free parameters. We leave the study of deeper trainable projection operators for future work.

heading: 6.2.1 Impact of regex training on single-hop queries
text: The regex query training is initialized with entity and relation embeddings trained on single– hop queries. However, when the model is optimized on regex queries, the performance on
single–hop queries drops dramatically for both COMP and (Free parameter + Aggregation) variants. Similar trend is observed in other variants as well. The results are summarized in Table 7.
We believe this could the the result of entity embeddings being optimized for two conflicting objectives. Consider the following example. Let q1 represent the query (e1, r, ?) and let e2 be an answer to q1. Similarly, let q2 = (e2, r, ?) and e3 be an answer for q2. In theory, from KBC training we get q1 − e2 = q2 − e3 = 0, i.e. e3 − e2 = q2 − q1 6= 0 for any distance-based model. However, for regex query q′ = (e1, r
+, ?), for which e2 and e3 are both answers, e3 − e2 = q′ − q′ = 0. Hence, distance-based embedding models cannot simultaneously model both KBC and regex queries. This hypothesis can also be extended to distribution-based models like BetaE, which models distance between entity and query as KL divergence between their respective distributions. Similar phenomenon has been observed in previous works on complex queries [Ren et al., 2020]. We leave it to future work to optimize for complex queries without losing performance on single–hop queries. We also observe that on Wiki100, RotatE-Box has a higher performance than RotatE, suggesting that RotatE-Box may have some value for pure KBC tasks also.

heading: 7. Conclusion
text: In this work we present the novel task of answering regex queries over incomplete knowledge bases. We provide two datasets and query workloads for the task and provide baselines for training regex operators. Of the two datasets we present, Wiki100-Regex is a novel challenging benchmark based entirely on a real-world KB and query logs. We also provide a new model RotatE-Box, which models more relational inference patterns than other approaches. Our code and data is available at https://github.com/dair-iitd/kbi-regex.
While the baselines of this work are the first step in modeling regex operators, there is a lot of scope for future research. Particularly, Kleene Plus poses novel modeling challenges – it is an idempotent unary operator ((r+)+ = r+) and an infinite union of path queries (r+ = r∨(r/r)∨(r/r/r) . . .). In the future, we plan to work on constructing parameterized operator functions, which honor these properties of the operator, and can be applied compositionally and recursively, while being sufficiently expressive.

heading: Acknowledgments
text: This work was supported by an IBM AI Horizons Network (AIHN) grant, grants by Google, Bloomberg and 1MG, a Visvesvaraya faculty award by Govt. of India, and a Jai Gupta Chair fellowship to Mausam. Srikanta Bedathur was partially supported by a DS Chair of AI fellowship. We thank the IITD HPC facility for compute resources.

heading: Appendix A. Model
text: A.1 Proof of Theorem 1
Proof. Consider a relation r1 represented by (Cen(r1),Off(r1)) ∈ Ck. The query representation of q1 = (e1, r1, ?) will be
Cen(q1) = Cen(e1) Cen(r1) Off(q1) = Off(r1))
If an entity e2 is in the answer set of q1, then it must be inside the query box of q1, i.e:
Re(Cen(q1)−Off(q1)) ≤ Re(Cen(e2)) ≤ Re(Cen(q1) + Off(q1)) Im(Cen(q1)−Off(q1)) ≤ Im(Cen(e2)) ≤ Im(Cen(q1) + Off(q1))
Now consider a relation r2 such that Cen(r2) = Cen(r1), Re(Off(r2)) ≥ Re(Off(r1)) and Im(Off(r2)) ≥ Im(Off(r1)). Hence, for query q2 = (e1, r2, ?) represented by:
Cen(q2) = Cen(e1) Cen(r2) Off(q2) = Off(r2))
the following is true:
Re(Cen(q2)−Off(q2)) ≤ Re(Cen(e2)) ≤ Re(Cen(q2) + Off(q2)) Im(Cen(q2)−Off(q2)) ≤ Im(Cen(e2)) ≤ Im(Cen(q2) + Off(q2))
Hence, the entity e2 is inside the query box of q2. Therefore, r1(e1, e2) implies r2(e1, e2). Thus, RotatE-Box can model hierarchy.
A.2 Regex Variants of Baseline Models
In this section we describe how the formulations of regex operators (Section 4.1- 4.3) apply to Query2box and RotatE. Similar ideas can be easily extended to BetaE as well.
Query2Box: Each entity e is modeled as a point e ∈ Rk and each relation r is modeled as a box r, represented as (Cen(r),Off(r)) ∈ R2k. Unlike RotatE-Box, the modulus of Cen(r) is not constrained. The representation of a single-hop query q = (e1, r, ?) is constructed by translating the center and adding the offset, i.e. q = (e1 + Cen(r),Off(r)). Generalizing this to path queries, the path embedding pn for relation path r1/r2/ . . . /rn is computed as follows:
Cen(pi+1) = Cen(pi) + Cen(ri+1) Off(pi+1) = Off(pi) + Off(ri+1) (5)
Here, p1 = r1. Query q = (e1, r1/r2/ . . . /rn, ?) is represented as q = (e1+Cen(pn),Off(pn)).
Modeling Kleene plus as Projection follows from Section 4.2, however, for Query2Box, the projection matrices are applied to actual embeddings, rather rather rotation angles. Given representation c for a regex expression c, c+ is modeled as kp(c) = c′ = Kc, K ∈ Rk×k While modeling Kleene plus as a Free parameter, the query q = (e1, r
+, ?) is represented as (e1 + Cen(r
+),Off(r+)). We follow the original implementation of Query2Box [Ren et al., 2020] for modeling Disjunction as aggregation. When modeling disjunction with DeepSets, c = c1∨c2∨ . . .∨cN is represented as:
Cen(c) = Wcen ·Ψ(MLPcen(Cen(c1)),MLPcen(Cen(c2)), . . . ,MLPcen(Cen(cN ))) Off(c) = Woff ·Ψ(MLPoff(Off(c1)),MLPoff(Off(c2)), . . . ,MLPoff(Off(cN )))
RotatE: For RotatE, entities and relations are modeled as points in the complex space, i.e. e ∈ Ck and r ∈ Ck. The modulus of r is constrained to be 1 in every dimension (r = eiθr). The single-hop query q = (e1, r, ?) is constructed by rotating the entity embedding (q = e1 r). The target entity is scored by its distance from the query embedding dist(e;q) = |q − e|. Computation of the relation path follows Section 4.1, but ignoring the offset term. Therefore, q = (e1, r1/r2/ . . . /rn, ?) is represented as q = e1 pn, where pn = r1 r2 . . . rn.
Given representation c (corresponding to rotation by angle θc) for a regex expression c, c+ is modeled as kp(c) = c′ = eiθc′ , where θc′ = Kθc, K ∈ Rk×k, when using Projection for Kleene plus. The free parameter embeddings of r+ is denoted by r+. For RotatE, The query q = (e1, r
+, ?) is then represented as q = e1 r+. Modeling disjunction as aggregation is similar to that described in Section 4.3, using dist(e;q) as defined above. For DeepSets, given the embeddings c1, c2, . . . , cN (corresponding to rotation angles θc1 , θc2 , . . . , θcN ) of regular expressions c1, c2, . . . , cN , c = c1 ∨ c2 ∨ . . . ∨ cN is represented as: c = eiθc , θc = W ·Ψ(MLP(θc1),MLP(θc2), . . . ,MLP(θcN )) where MLP is a Multi-Layer Perceptron network, Ψ is a permutation-invariant vector function, and W is a trainable matrix.

heading: Appendix B. Dataset
text: B.1 Wiki100 Knowledge Base
Wikidata is a collaboratively edited multilingual knowledge base that manages factual data in Wikipedia [Vrandečić and Krötzsch, 2014b]. It contains more than 69 million entities which makes it difficult to experiment with directly. We construct a dense subset based on English Wikidata as follows: we first selected entities and relations which have at least 100 instances in Wikidata and selected triples mentioning only the top-100 frequent relations. The resulting dataset had highly skewed distribution of relations with 6 relations accounting for more than 95% of all triples. In order to smooth this distribution and to include a significant number of all relations, we undersample facts containing these 6 relations, and oversample others. Finally, we recursively filtered sparse entities mentioned less than n times (decreasing n from 10 to 1) to obtain a knowledge base which we call as Wiki100, with 443, 904 triples over 41, 291 entities and 100 unique relations, which we randomly split into train/dev/test.
B.2 Regex Query Distribution

heading: Appendix C. Experiments
text: All the models are implemented in Pytorch-Lightning framework. We used NVIDIA V100 (16GB) GPUs from training the models. For all models, we use 2 GPUs when training on FB15K-Regex, and 4 GPUs when training on Wiki100-Regex.
C.1 Hyperparameters
Model-specific hyperparameters such as margin γ and down-weighting constant α are first tuned on single-hop query pre-training. Apart from learning rate lr, the same hyperparameters are used in regex query training. The ranges of hyperparameter grid search used for all our models are: γ ∈ {4.0, 8.0, 12.0, . . . , 28.0, 32.0}, α ∈
{0.2, 0.4, 0.6, 0.8, 1.0}, learning rate lr = {10−1, 10−2, 10−3, 10−4, 10−5}. For a particular dataset, we found the same set of hyperparameters to perform best for all three models. The final values are reported in Table 10. All the models are optimized using Adam optimizer [Kingma and Ba, 2015]. For FB15K, learning rate is set to 10−4 for single hop as well as regex queries. For Wiki100, it is 10−3 when training on single hop queries and 10−4 when training on regex queries. We use a batch size of 1024 and sample 256 negative entities for each training query. The negative entities e′i are sampled uniformly for regex query training and adversarially while training RotatE and RotatE-Box on single–hop queries (as per [Sun et al., 2019]). For both datasets across all models, we train for 1000 epochs for single-hop queries, and 500 for regex queries, using early stopping on dev split MRR.

Review summaries:
This paper combined two knowledge base completion models, RotatE and the Query2Box model, to form the proposed model RotatE-Box model. The proposed model is evaluated on a new task, knowledge base completion on regex queries. The authors also provided two new evaluation datasets for the regex queries. The proposed model achieved better performance on the regex query task compared to the two base models. But they did not compare it with enough baselines such as Beta Embeddings, and so on. And the proposed model performed much worse than the original model in the original knowledge base completion task.

The paper introduces a new task of solving queries consisting of disjunction and Kleene plus operators. They evaluate a previous model query2box on this task as well as propose a new model that combines query2box with a popular complex embedding model, RotatE. They show that the combination, termed RotatE-Box, is superior to using just RotatE or just Query2Box.

This work is on the topic of answering complex queries over incomplete Knowledge Bases (KBs). A KB is a set of triples/edges of the form (e1, r, e2) where ei's are entities/nodes and r is a relation/edge-label. Given a start entity e1 & an ordered sequence of relations r1 / r2 / ....rk one has to return all entities at the end of the paths consistent with the relational path r1 / r2 / ....rk. Importantly, a fraction of the edges are removed during training. Authors consider a novel problem in which one is allowed to represent *multiple* relational paths using a *single* regular-expression possibly containing disjunction ($\lor$) and Kleene plus (+) operators. For a regular-expression c, c+ denotes the infinite set of expressions {c, c/c, c/c/c ...}.