Abstract
We propose the novel task of answering regular expression queries (containing disjunction ($\vee$) and Kleene plus ($+$) operators) over incomplete Knowledge Bases (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.
Introduction: The Need for Complex Querying
Knowledge Bases (KBs) such as Wikidata and Freebase serve as the backbone for many AI applications, yet they are inherently incomplete. While traditional Knowledge Base Completion (KBC) focuses on predicting missing links for simple "single-hop" queries (e.g., Who is the author of '1984'?), real-world information needs are often more complex.
An analysis of actual Wikidata query logs reveals a significant gap in current research: while single-hop queries dominate, approximately 12% of user queries involve regular expression (regex) operators, such as disjunctions (OR) and Kleene plus (one or more repetitions of a relation).
Existing KBC models struggle with these queries for two main reasons. First, "point-based" models represent queries as single coordinates, making it difficult to capture the large and diverse sets of entities that satisfy a regex path. Second, while "box-based" models can represent volumes of potential answers, they often fail to capture fundamental relational patterns like symmetry or inversion.
Methodology: RotatE-Box
To address these limitations, we introduce RotatE-Box, a hybrid architecture that combines the strengths of rotational and box embeddings. By treating entities as points in a complex vector space and queries as axis-aligned "boxes," the model gains the ability to represent both relational logic and answer set volume.
Modeling Relational Patterns
RotatE-Box leverages the geometric properties of RotatE to handle complex relational patterns by treating relations as rotations in a complex space. This allows the model to satisfy a wider range of logical constraints than previous state-of-the-art methods.
Handling Regex Operators
To process regex queries, we developed specific geometric transformations:
- Path Traversal: Moving through a relation rotates the center of the query box and adjusts its size (offset) to account for uncertainty.
- Kleene Plus ($+$): We evaluated two approaches: a learned "Projection" operator and "Free Parameters" that learn specific embeddings for repeated relations.
- Disjunction ($\vee$): We utilized "Aggregation" (taking the minimum distance to any box in the OR statement) and "DeepSets" to merge multiple potential answer boxes into a single representation.
Experimental Setup and Results
We benchmarked RotatE-Box using two datasets: FB15K-Regex (a synthetic extension of FB15K) and Wiki100-Regex. The latter is particularly significant as it was harvested from actual user SPARQL logs, ensuring the evaluation reflects real-world human curiosity.
Our results demonstrate that RotatE-Box consistently outperforms standalone models. On the Wiki100-Regex dataset, RotatE-Box achieved a Mean Reciprocal Rank (MRR) of 49.29, significantly surpassing RotatE (45.58) and Query2Box (37.12). The performance gap was most pronounced on the natural user-log queries, suggesting that the hybrid architecture is uniquely suited to the types of complex questions users actually ask.
Conclusion
RotatE-Box represents a significant step forward in KBC by enabling effective regex querying. By combining the relational expressiveness of rotations with the volumetric representation of boxes, we can model complex logical paths and large answer sets simultaneously. Future work will focus on refining the Kleene plus operator to better respect logical properties like idempotency, further bridging the gap between neural embeddings and formal logic.
Summary updated