Relation Embedding with Dihedral Group in Knowledge Graph

Introduction

Large-scale knowledge graphs (KG) play a critical role in the downstream tasks such as semantic search, dialog management, and question answering. In most cases, despite its large scale, a KG is not complete due to the difficulty to enumerate all facts in the real world. The capability of predicting the missing links based on existing dataset has been one of the most important research topics for years. A common representation of a KG is a set of triples (head, relation, tail), and the problem of link prediction can be viewed as predicting new triples from the existing set. A popular approach is KG embeddings, which maps both entities and relations in the KG to a vector space, such that the scoring function of entities and relations for ground truth distinguishes from false facts.

The standard task for link prediction is to answer queries (h,r,?) or (?r,t). In this context, recent works on KG embedding focusing on bilinear form methods are known to perform reasonably well. The success of this pack of models resides in the fact they are able to model relation (skew-) symmetries. Furthermore, when serving for downstream tasks such as learning first-order logic rule and reasoning over the KG, the learned relation representation is expected to discover relation composition by itself. One key property of relation composition is that in many cases, it can be non-commutative. For example, exchanging the order between parent_of and spouse_of will result in completely different relation (parent_of as opposed to parent_in_law_of). We argue that, in order to learn relation composition within the link prediction task, this non-commutative property should be explicitly modeled.

Applied researchers from eBay recently published a long paper in Association for Computational Linguistics (ACL) 2019 to tackle this problem. In this paper, the researchers proposed DihEdral to model the relation in KG with the representation of dihedral group. The elements in a dihedral group are constructed by rotation and reflection operations over a 2D symmetric polygon. As the matrix representations of dihedral group can be symmetric or skew-symmetric, and the multiplication of the group elements can be Abelian or non-Abelian, it is a good candidate to model the relations with all the corresponding properties desired. Details of the paper can be found in here.

Dihedral Group for Relation Embedding

A dihedral group is a finite group that supports symmetric operations of a regular polygon in two dimensional space. Here, the symmetric operations refer to the operator preserving the polygon. For a K-side (K∈Z+) polygon, the corresponding dihedral group is denoted as DK that consists of 2K elements, within which there are K rotation operators and K reflection operators. A rotation operator Ok rotates the polygon anti-clockwise around the center by a degree of (2πm/K), and a reflection operator Fk mirrors the rotation Ok vertically.  The element in the dihedral group DK can be represented as 2D orthogonal matrices:

OK(m)=[cos⁡(2πmK)−sin⁡(2πmK)sin⁡(2πmK)cos⁡(2πmK)]FK(m)=[cos⁡(2πmK)sin⁡(2πmK)sin⁡(2πmK)−cos⁡(2πmK)],

where m∈{0,1,⋯,K}. The elements of D4 is visualized in the following figure, with each subplot representing the result after applying the corresponding operator to the square of ‘ACL’ on the upper left corner.

We propose to model the relations by the group elements in DK. We assume an even number of latent dimensions 2L. More specifically, the relation matrix takes a block diagonal form R=diag[R(1),R(2),···,R(L)], where R(l)∈DK for l∈{1,2,⋯,L}. As a result, the score for a triple (h,r,t) in bilinear form can be written as a sum of these L components h⊤Rt=∑l=1Lh(l)⊤R(l)t(l).

This model is able to learn the following properties for a KG:

1. Relation symmetry and skew symmetry. A relation R is symmetric if (t,R,h) is true when (h,R,t) is true. A relation R is skew-symmetric if (t,R,h) is false when (h,R,t) is true.
2. Relation inversion. R1 is the inverse of R2 if (t,R2,h) is true when (h,R1,t) is true.
3. Relation composition. If R3 is the composition of R1 and R2, then when both (h,R1,t1)  and (t1,R2,t2) are true then (h,R3,t3) is also true. That means, R3=R1R2. Moreover, dihedral group is able to learn a non-Abelian relation composition, which means it can distinguish the order of the composition for R1 and R2.

To train the relation embedding with dihedral group, we proposed two optimization methods. The first one utilizes the commonly used Gumbel-softmax trick to train discrete values. This model is called Dk-Gumbel. The second one parametrizes the group elements by binary variables, which are optimized by a straight-through estimator, and the model is named as Dk-STE.

Experiments

We performed experimental studies on 5 public KG datasets: WN18, WN18RR, FB15K, FB17K-237 and YAGO3-10. Here's the result:

We observe that the proposed model performs similarly to or better than the state-of-the-art models.

Conclusions

We proposed a method for KG relation embedding using dihedral group. By leveraging the desired properties of dihedral group, relation (skew-) symmetry, inversion, and (non-) Abelian compositions are all supported. Our experimental results on benchmark KGs showed that the model outperforms existing bilinear form models and even deep learning methods.

To see more details, please read our paper.