Regex Queries over Incomplete Knowledge Bases

Vaibhav Adlakha, Parth Shah, Srikanta J. Bedathur, Mausam .

TL;DR

Real-world knowledge base users frequently pose regular expression (regex) queries—such as multi-step traversals and alternatives—which existing embedding models struggle to handle due to massive answer sets and expressive relation patterns. The authors introduce RotatE-Box, a model operating in complex vector space that unifies rotational transformations with box embeddings to capture all seven primary relational inference patterns. Evaluated on two new benchmark datasets (including one extracted directly from Wikidata query logs), RotatE-Box significantly outperforms existing point-, box-, and distribution-based baselines.

What Problem Does This Paper Address?

Knowledge Base Completion (KBC) typically focuses on predicting missing single-hop links (e.g., “Who founded Microsoft?”) or multi-hop path queries. However, analysis of real-world Wikidata SPARQL logs reveals that while multi-hop paths make up only ~1% of queries, regular expression queries—which feature disjunction ($\vee$) and the Kleene plus ($+$) operator—account for roughly 12%.

Answering regex queries over incomplete knowledge graphs presents two major challenges:

  1. Large Answer Sets: A regex query like $(e_1, r^+, ?)$ can match dozens or hundreds of entities. Traditional models represent queries as single points in latent space, which cannot naturally cover broad, dispersed answer sets.
  2. Relational Inference Patterns: Prior complex-query architectures have structural blind spots. For instance, translation-based box embeddings (like Query2Box) cannot model symmetric relations (e.g., friend of), whereas rotation-based point embeddings (like RotatE) cannot model hierarchical relations (e.g., hypernymy).

Methods

The authors introduce RotatE-Box, an embedding model that represents entities as points in complex vector space $\mathbb{C}^k$ and queries/relations as axis-aligned "rotation boxes" characterized by a center and positive offset $(\text{Cen}, \text{Off}) \in \mathbb{C}^{2k}$.

  • Rotational Box Geometry: The center vector is constrained to unit modulus ($\text{Cen}(r)_j = e^{i\theta_{r,j}}$), acting as a rotation in the complex plane, while offsets define the box boundaries. To traverse a relation or path, the query center rotates by multiplying element-wise with the relation center, while relation offsets accumulate additively.
  • All Seven Relation Patterns: Because RotatE-Box generalizes RotatE (when offset is zero) and incorporates bounding boxes, it is theoretically proven to capture symmetry, antisymmetry, inversion, composition, intersection, mutual exclusion, and hierarchy.
  • Handling Regex Operators:
  • Kleene Plus ($+$): Modeled either as a non-compositional Free Parameter (learning a dedicated box embedding $r^+$ per relation) or as a compositional Projection operator (using linear transformations on rotation angles and box offsets).
  • Disjunction ($\vee$): Handled via Aggregation (splitting into Disjunctive Normal Form constituent queries and taking the minimum distance to the closest box) or DeepSets (a permutation-invariant neural operator using MLPs and pooling).

The fully compositional variant, RotatE-Box (COMP), pairs Projection with DeepSets to support arbitrary, nested regex queries (such as $(r_1 \vee r_2)^+$).

Datasets

The authors introduce two new benchmark datasets:

  1. Wiki100-Regex: A dense subgraph of English Wikidata (100 relations, 41,291 entities, 443,904 triples). Regex queries were harvested and filtered directly from actual Wikidata SPARQL user logs across 5 prevalent patterns.
  2. FB15K-Regex: Constructed over the standard Freebase FB15K graph using random walks, covering 21 distinct regex expression types combining up to three relations with $+$ and $\vee$.

Key Insights and Ideas

  • Regex is common in the wild: Regex querying is an order of magnitude more frequent than simple multi-hop chains in actual user logs, making it a critical practical benchmark.
  • The expressiveness trade-off: While the compositional Projection operator can generalize to arbitrarily nested expressions, the non-compositional Free Parameter variant often achieves slightly higher precision on simpler regex queries. This indicates that simple linear projection lacks the full capacity needed to represent recursive transitive closures.
  • Objective Conflict ("Catastrophic Forgetting"): Fine-tuning models on regex queries causes a sharp performance drop on basic single-hop queries. In single-hop prediction, distinct entities along a path must occupy distinct positions ($q_1 - e_2 = 0$ while $q_2 - e_3 = 0$), but a Kleene-plus query ($r^+$) pulls both $e_2$ and $e_3$ into the exact same region, creating competing geometric constraints.

Key Results

  • Overall Regex Answering: RotatE-Box (COMP) achieved the highest overall performance on both benchmarks:
  • FB15K-Regex: RotatE-Box reached 26.55 MRR and 43.56 Hits@10, outperforming BetaE (25.90 MRR), Query2Box (24.05 MRR), and RotatE (22.87 MRR).
  • Wiki100-Regex: RotatE-Box achieved 49.29 MRR and 70.95 Hits@10, beating RotatE (45.58 MRR), BetaE (41.93 MRR), and Query2Box (37.12 MRR).
  • Compositional vs. Baselines: Training on regex patterns provided massive gains over the standard single-hop KBC baseline (which only scored 10.73 MRR on FB15K-Regex and 4.63 MRR on Wiki100-Regex).

Limitations and Future Work

  • Degraded Single-Hop Performance: As noted above, training on regex queries causes single-hop link prediction metrics to deteriorate significantly. Developing training objectives that retain single-hop precision while learning broad closures remains an open problem.
  • Operator Expressiveness: The simple linear projection operator struggled to match the representation power of dedicated free parameters.
  • Mathematical Properties of Kleene Plus: The authors highlight the need for deeper, parameterized geometric operators that mathematically enforce intrinsic algebraic properties of Kleene plus, such as idempotence ($(r^+)^+ = r^+$) and infinite path union expansion.

Summary updated

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 models significantly outperform models based on just Rotate and just box embeddings.
BibTeX
@inproceedings{adlakha2021regex,
  author = {Vaibhav Adlakha and Parth Shah and Srikanta J. Bedathur and Mausam .},
  title = {{Regex Queries over Incomplete Knowledge Bases}},
  booktitle = {AKBC},
  year = {2021},
  url = {https://openreview.net/forum?id=4YQVfA5vEJS},
}

Loading related content...

Figure