Abstract
We propose the novel task of answering regular expression queries (containing disjunction ($\vee$) 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 the 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.
What Problem Does This Paper Address?
Knowledge Bases (KBs) like Wikidata or Freebase are massive repositories of facts, but they are notoriously incomplete. Knowledge Base Completion (KBC) aims to predict these missing links. Traditionally, KBC models focus on "single-hop" queries (e.g., Who founded Microsoft?).
However, real-world users often ask much more complex questions involving paths, choices, and repetitions. Analysis of Wikidata query logs reveals that while single-hop queries are the majority, a significant portion—roughly 12% of queries—involve regular expression (regex) operators like disjunction ($\vee$, "OR") and the Kleene plus ($+$, "one or more repetitions").
Existing models struggle here for two primary reasons:
- Large Answer Sets: A regex query like "descendants of" might return hundreds of entities. Modeling a query as a single point in space (the standard approach) is mathematically ill-equipped to represent a large set of answers.
- Complex Relational Patterns: Models need to understand symmetry (if A is a peer of B, B is a peer of A) and hierarchy (if A is a city, it is also a location). Most models can do one or the other, but rarely both.
Methods: Introducing RotatE-Box
The authors introduce RotatE-Box, which merges two powerful ideas to handle the complexity of regex queries:
- RotatE: Models relations as rotations in a complex vector space. This is excellent at capturing patterns like symmetry, inversion, and composition.
- Query2Box: Models queries as axis-aligned "boxes" rather than points. This allows the model to "contain" a large number of entity points, naturally representing large answer sets.
RotatE-Box represents entities as points and relations/queries as boxes in complex space. This hybrid approach allows the model to handle a wider variety of logical patterns than its predecessors.
Handling Regex Operators
- Relational Paths: Applying a relation rotates the box's center and expands or shrinks its boundaries.
- Kleene Plus ($+$): Handled via a "Projection" operator (a learned geometric transformation) or by treating the repeated relation as a "Free Parameter" embedding.
- Disjunction ($\vee$): Handled via "Aggregation" (taking the minimum distance to multiple boxes) or "DeepSets" (a neural network that merges multiple box embeddings into one).
Datasets
The researchers introduced two new benchmarks to test these capabilities:
- FB15K-Regex: A synthetic dataset created by performing random walks on the well-known FB15K graph to generate 21 different types of regex queries.
- Wiki100-Regex: A more realistic dataset built from a dense subset of Wikidata. Crucially, the queries here are harvested from actual user SPARQL query logs, making it a "wild" test of how people actually interact with KBs.
Key Insights and Results
- The Power of Complex Boxes: Moving box embeddings from real space to complex space allows the model to inherit RotatE’s ability to model nearly all logical relation patterns (symmetry, antisymmetry, etc.) while keeping the box's ability to model hierarchy and large sets.
- Compositionality Matters: The "COMP" variants of the models—which use geometric operators that can be applied recursively—generally performed better than non-compositional baselines. This suggests that the geometry of the embedding space successfully mirrors the logic of the regex.
- Performance Gains: RotatE-Box emerged as the clear winner. On the real-world Wiki100-Regex dataset, RotatE-Box (COMP) achieved a Mean Reciprocal Rank (MRR) of 49.29, significantly outperforming previous state-of-the-art models like BetaE (41.93) and Query2Box (37.12).
Limitations and Future Work
While RotatE-Box represents a significant step forward, challenges remain. The Kleene plus operator is particularly difficult to approximate with a single geometric transformation, as it represents an infinite union of paths in formal logic. Additionally, the authors observed a slight performance dip in simple single-hop queries after training for regex queries, suggesting a trade-off between "point-to-point" and "point-to-box" logic that future research must address. Finally, scaling these complex geometric operations to the full Wikidata (millions of entities) remains a significant engineering challenge.
Summary updated