Query2Box

Definition

Query2Box is a model for calculating path-based queries over an incomplete Knowledge Graph. It represents queries as boxes in a vector space. To answer a query, the model computes the final query box and ranks entities based on their distance to the box.

Architecture

Box Embedding

In the Query2Box model, queries are represented as boxes in a vector space, and entities are represented as points (zero-size box) in the space. The box embedding allows for modeling uncertainty and capturing a set of possible answers.

Query box in ${\mathbb{R}}^d$ is defined as $\mathbf{q}=({\mathrm{Cen}}_{\mathbf{q}},{\text{Off}}_{\mathbf{q}})\in {\mathbb{R}}^{2d}$ where ${\mathrm{Center}}_{\mathbf{q}}\in {\mathbb{R}}^d$ is the center of the box, and ${\mathrm{Offset}}_{\mathbf{q}}\in {\mathbb{R}}_{\ge 0}^d$ is the offset of the box.

The embedding box is defined using the query box. ${\mathrm{Box}}_{\mathbf{q}}=\{\mathbf{v}\in {\mathbb{R}}^d|{\mathrm{Cen}}_{\mathbf{q}}-{\mathrm{Off}}_{\mathbf{q}}⪯\mathbf{v}⪯{\mathrm{Cen}}_{\mathbf{q}}+{\mathrm{Off}}_{\mathbf{q}}\}$ where $⪯$ is element-wise inequality.

Query Operations

Query2Box consists of the two operations: projection, and intersection.

Projection Operation

The projection operation expands the box to include related entities. ${\mathrm{Cen}}_{{\mathbf{q}}^{\prime }}={\mathrm{Cen}}_{\mathbf{q}}+{\mathrm{Cen}}_{\mathbf{r}}{\mathrm{Off}}_{{\mathbf{q}}^{\prime }}={\mathrm{off}}_{\mathbf{q}}+{\mathrm{Off}}_{\mathbf{r}}$

Intersection Operation

The intersection operation combines information from multiple sub-queries by intersecting their boxes. Instead of directly applying intersection over a set of box embeddings, the intersection in calculated using the Attention-like operation.

The center is calculated as ${\mathrm{Cen}}_{{\mathbf{q}}_{\text{inter}}}=\sum _i{\mathbf{w}}_i\odot {\mathrm{Cen}}_{{\mathbf{q}}_i}$ where ${\mathbf{w}}_i=\frac{\exp (\mathrm{MLP}({\mathbf{q}}_i))}{{\sum }_j\exp (\mathrm{MLP}({\mathbf{q}}_j))}$

The offset is calculated as ${\mathrm{Off}}_{{\mathbf{q}}_{\text{inter}}}=\min (\{{\mathrm{Off}}_{{\mathbf{q}}_i}|i=1,\dots ,n\})\odot \sigma (f_{\text{off}}(\{{\mathbf{q}}_i|i=1,\dots ,n\}))$ where $\sigma$ is a Sigmoid Function, and $f_{\text{off}}(\{{\mathbf{q}}_i|i=1,\dots ,n\})=\mathrm{MLP}\left(\frac{1}{N}\sum _{i=1}^N\mathrm{MLP}({\mathbf{q}}_i)\right)$

Entity-to-Box Distance

Given a query box $\mathbf{q}$ and an entity vector $\mathbf{v}$, the distance between them is defined as ${\mathrm{dist}}_{\text{box}}(\mathbf{v};\mathbf{q})={\mathrm{dist}}_{\text{outside}}(\mathbf{v};\mathbf{q})+\alpha {\mathrm{dist}}_{\text{inside}}(\mathbf{v};\mathbf{q})$ where $0<\alpha <1$ is a fixed scalar that downweights the distance inside the box.