Low-dimensional Knowledge Graph Embedding based on Extended Poincare Ball: Preliminary Results ?

Abstract

Most existing knowledge graph embedding (KGE) methods are built on Euclidean space, which are di cult to handle hierarchical structures. While hyperbolic embedding methods have shown the promise of high delity and concise representation for hierarchical data, logical patterns in knowledge graphs (KGs) are not considered well in current methods. To address this problem, we propose a novel KGE model with extended Poincare Ball and polar coordinate system to capture hierarchical structures. It rst uses the tangent space and exponential transformation to initialize and map the corresponding vectors to the Poincare Ball in hyperbolic space. Then, to solve the boundary conditions, the Poincare Ball boundary is stretched and zoomed by expanding the modulus length. Moreover, it is optimized by using polar coordinate and changing operators in the extended Poincare Ball. Experimental results of link prediction on WN18RR and FB15k-237 datasets show that our model outperforms state-of-the-art baselines.

Keywords

• Knowledge graph embedding
• Extended Poincare Ball
• Hyperbolic space

-

Since knowledge graphs (KGs) are usually incomplete, predicting missing links in KGs via knowledge graph embedding (KGE) into vector spaces becomes more and more important. Hierarchical structures are common in KGs and used to manage the relations and concepts. However, existing KGE methods often encounter challenges dealing with hierarchical structures, because it is notably di cult for models built on Euclidean space to preserve hierarchical structures.

Recent works proposed hyperbolic representation learning [ 2, 6 ]. In KGs, hierarchical relationships between entities can be approximated as a tree structure, while the number of entities in each layer increases exponentially with depth of tree increasing. Such a knowledge structure can be well represented with the Poincare Ball [ 9 ]. However, even most hyperbolic KGE models employ Poincare Ball to embed the structures, they still su er from limitations of restricted capacity and oating-point precision when majority of entities are embedded near by the boundary of Poincare Ball due to long-tail distribution.

To address these issues, we propose a novel hyperbolic knowledge embedding method, which employs the extended Poincare Ball for KGE and captures hierarchical structures with polar coordinate system [ 5 ]. 2

Model

The principle of our model is shown in Fig. 1. In order to learn hierarchical hyperbolic embeddings to represent logical patterns such as symmetry and antisymmetry while preserving latent hierarchies, our model uses polar coordinate to encode logical patterns with hierarchies in hyperbolic space as shown in Fig. 1(a). Due to the advantages of Poincare Ball for gradient optimization [ 1 ], our model rst initials embedding in Poincare Ball. However, the capacity of Poincare Ball model is restricted by oating-point precision when majority of points locate near the boundary due to long-tail distribution. To release this limitation, our method expands the boundary into in nite to increase capacity of model and adjust some operators to align with Euclidean geometry, which rede nes the distance dB(u; v) and can be shown in Fig. 1(b). v1 v'1 v2

v'2

PoincaréBall Extended PoincaréBall

N T

B v1 v2 Tangent Space Hyperbolic Space v1 v'1 v2

v'2

PoincaréBall Extended PoincaréBall

N T

B v1 v2 Tangent Space Hyperbolic Space (a) Hyperbolic Space.

(b) Extended Poincare Ball.

In Poincare Ball, the whole space is symmetric along the center but the apparent Euclidean distance from the origin to any point is not equal to the hyperbolic distance [ 5 ]. To make the apparent distance consistent with the actual hyperbolic distance, we establish a new model called the extended Poincare Ball to ensure the distance from any point to the center is equal to which in hyperbolic space. Suppose that the polar coordinates of any point in the original coordinate system (Poincare disk) is(r; ), and that in the new space is (2tanh 1r; ). In this way, the radius of ball space is in nite. Therefore, points near the boundary are extremely compressed in Poincare Ball while there is no such problem in the extended one. Meanwhile, it can be proved that Hyperbolic Cosine Theorem still holds for the operators in extended Poincare Ball: cosh(c) = cosh(a)cosh(b) sinh(a)sinh(b) cos (a; b; c stand for the geodesic distance of triangle and stands for the angle between a; b). Extended Poincare Ball and Poincare Ball share the same distance form when calculated by cosine theorem as well.

Furthermore, inspired by the Hyperbolic Cosine Theorem, in which the hyperbolic distance can be composed of modulus and angle, we use polar coordinates to embed KGs into the extended Poincare Ball. The score function can be formed as two parts: polar radius (h; r; t) and polar angle ( h; r; t) as follow: (1) (3) drB = k2 tanh-1((R c h) c (r c t))k2 (2) where h; r; t stand for hyperbolic embeddings of head entity, relation, and tail entity, respectively. R stands for relation matrix in hyperbolic space inspired by MuRP [ 2 ]. As stated in the property of extended Poincare Ball, we classify the embedding levels of di erent entities by Euclidean Norm.

Considering convergence and e ciency, we can simplify and obtain the polar angle as: = j j 0jj. Consequently, a point xB in polar coordinate system can be calculated in TransE form [ 4 ] as: dB =

drB + d B where ; is the weights to be learned. The whole function shares the similar way as works proposed by Federico [ 7 ] which does not satisfy Cauchy inequality.

It is worth noting that the radius part plays an essential role in levels of entities in extended Poincare Ball, and the angle aims to distinguish entities in the same level. Therefore, we formulate the polar radius with Mobius addition and multiplication as follow: d B = k( h + r t)mod2 k

From another perspective, angle parts can be replaced with radius parts by Cosine Theorem in hyperbolic space. However, to better capture complex relation such as symmetry, anti-symmetry, inversion and composition, it is necessary to utilize extra angle part for downstream tasks like link predictions. On the other hand, the introduction of angle part can simulate the rotation in RotatE [ 8 ]. Theoretically, any algebraic system hold the fundamental properties of congruence can be used as angle part in the model when embedding complex relations. Take angles as an example, suppose that a relation r 2 [0; 2 ) is close to , then a symmetric relation can be formed as ( h + r + r) mod 2 = h mod 2 with arbitrary h and 6= for asymmetric relations.

Since the Poincare Ball has a Riemannian manifold structure, we optimize radius parameters with stochastic Riemannian optimization methods such as RSGD or RSVRG [ 3 ]. Let rE denote the Euclidean gradient of L(P ). Using RSGD, the Riemannian gradient can be computed as rR = summary, the full update for a single embedding is calculated by: P t+1 = P t t 1 kP tk 4 where p is the probability distribution of sampling negative triples, and temperature of sampling. 3

Experiments

To evaluate our approach, we choose the widely used KG datasets: WN18RR and FB15K-237. The evaluation metrics are: (1) mean reciprocal rank (MRR), which measures the mean of inverse ranks assigned to correct entities; and (2) hits at K (H@K, K 2 1, 10), which measures the proportion of correct triples among the top-K predicted triples. Table 1 summarizes the experimental results of di erent models on the task of KG link prediction. It can be seen that our method achieves the state-of-the-art results on both datasets, which demonstrates the e ciency of our model. (4) (5) (6) is the

References

1. Abramowicz , M.A. , Bengtsson , I. , Karas , V. , Rosquist , K. : Poincare ball embeddings of the optical geometry . Classical and Quantum Gravity 19 ( 15 ), 3963 ( 2002 )

2. Balazevic , I. , Allen , C. , M. Hospedales , T.: Multi-relational poincare graph embeddings . In: Proceedings of the 33rd NIPS . pp. 4463 { 4473 ( 2019 )

3. Bonnabel , S. : Stochastic gradient descent on riemannian manifolds . IEEE Transactions on Automatic Control 58 ( 9 ), 2217 { 2229 ( 2013 )

4. Bordes , A. , Usunier , N. , Garcia-Duran , A. , et al: Translating embeddings for modeling multi-relational data . In: Proceedings of the 26th NIPS . pp. 1 { 9 ( 2013 )

5. Chami , I. , Ying , Z. , Re , C. , et al: Hyperbolic graph convolutional neural networks . In: Proceedings of the 33rd NIPS . pp. 4869 { 4880 ( 2019 )

6. Kolyvakis , P. , Kalousis , A. , Kiritsis , D. : Hyperkg: Hyperbolic knowledge graph embeddings for knowledge base completion . CoRR abs/ 1908 .04895 ( 2019 )

7. Lopez , F. , Heinzerling , B. , Strube , M. : Fine-grained entity typing in hyperbolic space . In: Proceedings of the 4th RepL4NLP . pp. 169 { 180 ( 2019 )

8. Sun , Z. , Deng , Z. , Nie , J. , et al: Rotate: Knowledge graph embedding by relational rotation in complex space . In: Proceedings of the 7th ICLR ( 2019 )

9. Ungar , A.A. : Hyperbolic trigonometry and its application in the poincare ball model of hyperbolic geometry . Computers and Mathematics with Applications 41 ( 1 ), 135 { 147 ( 2001 )

10. Yang , B. , Yih , W.t., He , X. , et al: Embedding entities and relations for learning and inference in knowledge bases . In: Proceedings of the 3rd ICLR ( 2015 )