Multi-Hop Relation Aware Representations for Inductive Knowledge Graphs (2023)

Abstract: Recent knowledge graph (KG) embedding methods explore parameter-efficient representations for large-scale KGs. These techniques learn entity representation using a fixed size vocabulary. Such a vocabulary consists of all the relations and a small subset of the full entity set, referred to as anchors. An entity is hence expressed as a function of reachable anchors and immediate relations. The performance of these methods is, therefore, largely dependent on the entity tokenization strategy. Especially in inductive settings, the representation capacity of these embeddings is limited due to the absence of anchor entities, as unseen entities have no connection with training graph entities. In this work, we propose a novel entity tokenization strategy that tokenizes an entity into a set of anchors based on relation similarity and relational paths. Our model MH-RARe overcomes the challenge of unseen entities not being directly connected to the anchors by selecting informative anchors from the training graph using relation similarity. Experiment results show that our model outperforms the baselines on multiple datasets for inductive knowledge graph completion task, attaining upto 5% improvement, while maintaining parameter efficiency.

## introduction knowledge graphs (kgs) are powerful structures that consist of a vast collection of interconnected facts, presented in the form of a graph. each fact is represented as a triplet in the form ⟨subject, relation, object⟩. to effectively utilize kgs, representation learning plays a crucial role. in this context, representation learning involves learning a d-dimensional vector representation for every entity and relation in kg. typically, these representations are learned through a link * both authors contributed equally to this work. traditional kg embedding methods employ shallow embedding techniques, wherein entities and relations are mapped onto a lower-dimensional vector space. these methods rely on an embedding lookup function that ensures each entity and relation is uniquely associated with a d-dimensional vector. however, these methods encounter challenges when dealing with large-scale knowledge graphs, as the number of parameters required scales linearly with the size of the entity set. also, these methods are applicable only to transductive settings, where the set of entities remains fixed. nevertheless, real world kgs evolve as new entities get added to the graph over time. link prediction on these graphs requires the ability to generalize to these unseen entities. inductive link prediction is the task of inferring missing links in such graphs. recently, motivated by the compositional models to represent words such as wordpiece @xcite , nodepiece @xcite proposes a framework to limit the vocabulary size in kgs. this is done by limiting the vocabulary to a fixed set of entities (called as anchors) and relations in the kg. an entity in the kg is then tokenized into it's nearest anchors and immediate relations. while anchors are available for seen entities, unseen entities are represented just using immediate relations as the entities in the anchor set are disconnected from these unseen entities. this limits the expressive ability of the unseen entities. in this work we address this limitation and propose a novel anchor selection strategy for unseen entities in an inductive kg. as shown by previous work gake @xcite , immediate relations of an entity in a kg, can reveal the nature of an entity. we use this result to draw m relationally similar anchor nodes to a given unseen entity from the training graph. our hypothesis is that, such relationally similar nodes may contain some valuable information that will aid in better link prediction. furthermore, rather than looking at 1-hop immediate relations, we tokenize an entity based on n relation paths originating from that entity which helps in building a richer relational context for an entity. our experiment results provide substantial evidence to support our hypothesis, indicating such a tokenization strategy can improve link prediction performance in inductive link prediction tasks. ## related work conventional embedding based methods: traditional approaches to embedding methods for link prediction in knowledge graphs have been widely explored in the literature. these techniques aim to capture the inherent semantic relationships and structural patterns in the graph data to predict missing links between entities. approaches like transe @xcite , transh @xcite and transr @xcite assume that the embeddings of entities and relations follow some geometric rules in vector space. other approaches use bilinear forms or complex-valued operations to model the interactions between entity and relation embeddings. ex. distmult @xcite uses simple dot product between entities and relations to calculate plausibility of the triple. complex @xcite uses hermitian dot product to calculate plausibility of a true triple as it represents relations as complex-valued vectors. these embedding methods provide effective means for link prediction in transductive setting but they can not generalize to unseen entities, so we cannot use them in inductive setting. inductive embeddings based methods: some recent works have shown how to create embeddings for nodes that are not seen before, but they have some limitations. graphsage @xcite and graph2gauss (bojchevski and günnemann, 2018) depend on having node features that are often missing in many kgs. lan @xcite and @xcite produce embeddings for new nodes by combining the embeddings of nearby nodes using gnns. however, both of these methods require the new nodes to have known nodes around them and cannot deal with completely new graphs. rule-induction based methods: these methods are different from embedding-based methods because they infer probabilistic logical-rules from the knowledge graph by finding statistical patterns and regularities in it, like @xcite and @xcite . these methods can naturally handle unseen nodes because the rules do not depend on specific node identities, but they have problems with scalability and expressiveness due to their reliance on rules. inspired by these statistical rule-induction methods, the neurallp model @xcite uses tensorlog @xcite operators to learn logical rules from kgs in a way that is fully differentiable. @xcite improved on neurallp and proposed drum, which learns more precise rules. we compare our methods with this group of methods in the inductive setting. gnn based link prediction: some recent methods have proposed to use graph neural network based models for link prediction task. they first take out a subgraph around each target link based on the k-hop neighbourhood of the target entities, encode the subgraphs using a graph neural network (gnn), then learn a function that maps subgraph structural patterns to link existence. for instance, r-gcn @xcite employed relational graph convolutional layers to col-lect information from neighboring nodes and edges. compgcn @xcite utilized composition functions to merge entity and relation embeddings prior to aggregation. however, these methods are applicable to only transductive settings. some recent methods such as grail (teru et al., 2020), tact @xcite , compile @xcite , conglr @xcite utilize gnns for inductive link prediction. grail first encodes the subgraph around a link using the double radius node labelling scheme and then applies a rgcn based gnn to predict the plausibility of the link. tact extends grail by adding topological patterns while compile improves the message passing between entities through a communicative kernel. along with the context graphs, conglr uses logical reasoning to improve inductive link prediction performance. although these methods have achieved good performance on inductive link prediction, they do not fully consider the global context of the kg, which could provide valuable insights for link prediction. parameter efficient link prediction: conventional kg embedding methods store embeddings for all entities and relations. however, nodepiece @xcite introduced a unique approach by leveraging word tokenization techniques and applying them to knowledge graphs for node tokenization. in our work, we build upon the foundations of nodepiece and further enhance it for inductive link prediction tasks. while nodepiece does not utilize anchors in the inductive setting, we propose a novel approach that incorporates anchors for unseen entities by considering the outgoing relations from the entity. ## proposed method we denote a graph g as @xmath0, r, t ), where e is the set of entities, r is the set of relations and t is the set of observed triples @xmath1, r, t) | (h, r, t) ∈ e × r × e}. given a training graph g @xmath2, r train , t train ), the task of inductive inference is to infer missing links in test graph g @xmath3, r test , t test ), where, the train and test graphs are disjoint e train ∩ e @xmath4, and relations in the test graph is a subset of relations in the training graph r test ⊆ r train . we augment train and test graphs with inverse relations to ensure connectivity from each node. algorithm 1: anchor selection algorithm input :training graph g @xmath5, r train , t train ), number of anchors m output :anchor set a 1 @xmath6, r, t) ∈ t train do 6 e2r[h].add(r) 7 r2e[r].add(h) 8 end for 9 while | a |< m do 10 e2r count .clear() 11 for @xmath7.keys() do 12 if e / ∈ a then 13 e2r count [e] = -len(e2r[e]) 14 end if 15 end for 16 r @xmath8, r @xmath9.popitem() 23 if r @xmath10. typically in kgs the number of entities far exceeds the number of relations. therefore we form our vocabulary with a smaller subset of entities called as the anchor set a. our objective here is to learn an encoder function f ({a i } m , {p j } n ) for any entity @xmath11, ## conlusion & future work in this paper we have introduced an entity tokenization strategy that tokenizes an entity into anchors and relational paths for inductive kgs. in spite of test graph being disconnected to the training graph, our approach is able to select informative anchors for an unseen entity. we show that while anchors are more effective in relation rich graphs, relational paths can compensate for it's performance in sparser graphs. overall, addition of anchors leads to an increase in parameter budget, but the number of parameters only grows sub-linearly as the anchor set contains only a small set of representative entities derived from the full entity set. an interesting direction for future research would be to explore anchor selection in relationally sparse kgs.