Hyperbolic Hierarchy-Aware Knowledge Graph Embedding for Link Prediction (2021)

Abstract: Knowledge graph embedding (KGE) using low-dimensional representations to predict missing information is widely applied in knowledge completion. Existing embedding methods are mostly built on Euclidean space, which are difficult to handle hierarchical structures. Hyperbolic embedding methods have shown the promise of high fidelity and concise representation for hierarchical data. However, the logical patterns in knowledge graphs are not considered well in these methods. To address this problem, we propose a novel KGE model with extended Poincaré Ball and polar coordinate system to capture hierarchical structures. We use the tangent space and exponential transformation to initialize and map the corresponding vectors to the Poincaré Ball in hyperbolic space. To solve the boundary conditions, the boundary is stretched and zoomed by expanding the modulus length in the Poincaré Ball. We optimize our model using polar coordinate and changing operators in the extended Poincaré Ball. Experiments achieve new state-of-the-art results on part of link prediction tasks, which demonstrates the effectiveness of our method.

## introduction knowledge graphs (kgs) @xcite , consisting of (subject, relation, object) triples, are essential for question answering, information extraction and recommendation systems. in real-world, kgs are usually incomplete @xcite , so 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, typically forming hierarchical data. however, existing kge methods often encounter challenges when dealing with hierarchical structures, because it is particularly difficult * corresponding author. for models which are built on euclidean space to preserve hierarchical structures @xcite . recent works proposed hyperbolic representation learning represented by poincaré ball @xcite . figure 1 shows part of knowledge in the nell kg @xcite , in which the entities show a long-tailed distribution with distance from the the united states. namely, the 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 poincaré ball (ungar, 2001), which is a type of hyperbolic space suitable for embedding the hierarchical structures and entities in kgs. even most hyperbolic kge models choose poincaré ball model to embed the structures, they still suffer from the problems of restricted capacity and floating-point precision when majority of points are embedded near by the boundary of poincaré ball due to long-tail distribution. to tackle these challenges, this paper proposes a novel hyperbolic knowledge embedding method named hbe (hyperbolic extended poincaré ball embedding), which employs a extended poincaré ball for kg embedding and captures hierarchical structures with polar coordinate system in a hyperbolic transformation @xcite . first, hbe uses tangent space to initialize the entity and relation vectors in conventional euclidean space. then, it projects embedded entities into polar coordinate to gain hierarchical information and takes embeddings into radius and angle parts to absorb hyperbolic information. the boundary is stretched and zoomed via expanding the modulus length in the poincaré ball. at the same time, the addition rule in the extended poincaré ball are changed accordingly, so that the model can be optimized in the extended poincaré ball. the overall training process adopts the idea of transe, that is, through the transformation of positive and negative examples, the measurement distance between the result of the head entity and the relationship and the tail entity is as small as possible. in summary, the main contributions of this paper are three-fold: (1) we propose a novel hyperbolic knowledge embedding method, hbe, to apply extended poincaré ball for kge and captures hierarchical structures. (2) in order to enable the model to be optimized in extended poincaré ball, we finetune the operator and fix model in polar coordinate system to embed entities and relations. (3) experiments show that hbe outperforms state-of-the-art methods on link prediction tasks at a moderate dimension. ## hyperbolic geometry the hyperbolic space is one of the three kinds of isotropic spaces, which includes euclidean (flat), spherical (positively curved) and hyperbolic (negatively curved) spaces @xcite . compared with the euclidean and spherical spaces, the amount of space covered by a hyperbolic geometry increases exponentially rather than polynomially @xcite . this property allows us to capture kg structures with hyperbolic space and suits those forming hierarchies. for the hyperbolic geometry, there are several important isometric models including the hyperbolic model, klein disk model and poincaré ball model. this paper chooses the extended poincaré ball model due to its feasibility for gradient optimization @xcite and its infinite boundary. we hereby introduce some basic operations of hyperbolic geometry and poincaré ball, and then address the way to ex-tend poincaré ball and modify some operators in extended one. specifically, a d-dimensional poincaré ball with a negative curvature -c (@xmath0, g x (ungar, 2001). the geodesic distance (or hyperbolic distance) d(u, v) between vectors u and v in the poincaré ball with @xmath1, 2001): the vector translation in the poincaré ball is defined by the möbius addition (ungar, 2001): previous work defines the matrix-vector multiplication between poincaré balls using the exponential and logarithmic maps @xcite . the hyperbolic vectors are first projected into the tangent space at 0 using the logarithmic map (log 0 ) then multiplied the transformation matrix like what in the euclidean space, and finally projected back on the manifold with the exponential map (exp 0 ) @xcite . specifically, the two projections on vector @xmath2: through such projections, we can apply any euclidean counterpart operations on hyperbolic vectors. the transformation can be done using the möbius version of matrix-vector multiplication: möbius scalar multiplication can be obtained in the same way as: poincaré ball model can suit hierarchical structure of kgs, in which entities can form different hierarchies under different relations. for example, in wordnet @xcite the chair is a parent node to different chair types (e.g. f olding_chair, armchair) under the relation hypernym. and both chair and their types are parent nodes to parts of a typical chair (e.g. backrest, leg) under the relation has_part. the parent node chair would be embedded closer to the origin and node backrest would be farther to origin. an ideal embedding model should capture all hierarchies simultaneously. take bilinear models @xcite as an example, they can measure similarity between the subject entity embedding and an object entity embedding using the euclidean inner product. however, a clear correspondence to the euclidean inner product does not exist in hyperbolic space. the euclidean inner product can be expressed as a function of euclidean distance and norms. noting this, poincaré glove @xcite absorbed the squared norms of the embeddings into the biases by replacing the euclidean with the poincaré distance d b (u, v) to obtain the hyperbolic version of glove. meanwhile, the capacity of poincaré ball model is restricted by floating-point precision when majority of points locate near by the boundary due to long-tail distribution. to tackle this problem, we utilize an extended poincaré ball to expand the border into infinity and adjust some operators to align with euclidean geometry, which redefines the distance d b (u, v). ## experiments to evaluate our approach, we choose the widely used kg datasets wn18rr @xcite and fb15k-237 @xcite . wn18rr is a subset of wordnet, a hierarchical collection of relations between words, created from wn18 by removing the inverse of many relations from validation and test sets to make the dataset more challenging, containing 40,943 entities and 11 relations. fb15k-237 is a subset of freebase, a collection of real world facts, created from fb15k in the same way as wn18rr. fb15k-237 contains 14,541 entities and 237 relations. the statistics of datasets are shown in we evaluate hbe on the task of kg link prediction, which is critical for practical applications. we use the scoring function to rank the correct tail or head entity against all possible entities for link prediction tasks in kgs. 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, @xmath3, 3, 10), which measures the proportion of correct triples among the top-k predicted triples. ## conclusion we introduce a novel translational method for embedding hierarchical kgs in extended poincaré ball of hyperbolic geometry. our model learns hierarchy-specific parameters with polar coordinate by möbius multiplication and möbius addition. we show that hbe outperforms on the link prediction task on some hierarchical kg dataset. is much more irregular than hierarchical ones in _hypernym. in other words, angle parts are in a leading position when representing this kinds of symmetric relations. furthermore, this happens on relation /celebrities/f riendship/f riend in fb15k-237. furthermore, we can calculate the kl divergence of several head-tail distribution mentioned above for further analysis. on the other hand, it is apparent that _hypernym has more hierarchical structure than /f ilm/f ilm/genre when comparing 0.084 with 0.078 in radius part, which can be inferred in