Subgraph Neighboring Relations Infomax for Inductive Link Prediction on Knowledge Graphs

1 Introduction

Knowledge graphs (KGs) are collections of structured knowledge represented by factual triples (entity, relation, entity), which are essential for many applications, such as question answering [Huang et al., 2019], recommendation systems [Wang et al., 2018]. However, even state-of-the-art KGs suffer from incompleteness issue, e.g. FreeBase [Bollacker et al., 2008], and WikiData [Vrandecic, 2012]. To complete KGs, link prediction task aims at inferring missing links between entities on original KGs. But in fact, there are many newly emerging entities added into real-world KGs constantly over time [Trivedi et al., 2017], e.g., new user added into e-commerce database or new molecules in biomedical KGs. In order to predict links between brand-new entities, inductive link prediction task has been an active area of research, which requires model with the inductive ability for reasoning on graphs consisting of unseen nodes.

∗Contact Author

Whereas inductive link prediction is a difficult task as it requires generalization from training entities to unseen entities. Most previous link prediction methods [Bordes et al., 2013; Yang et al., 2015] learn specific embedding for each entity, which are hard to generalize to unseen entities. Recently, motivated by graph neural network (GNN) with the ability of aggregating local information, several inductive models based on GNN have been proposed. GraIL [Teru et al., 2020] models enclosing subgraph of target triple to capture topological structure (see Test graph A in Figure 1), which owns inductive ability. On the basis of GraIL, several works [Chen et al., 2021; Mai et al., 2021] further utilize enclosing subgraph structure to predict links inductively. However, all above methods only consider the enclosing part of subgraph without complete neighboring relations, which leads to two challenging issues. First, they lose partial neighboring relations due to the nature of enclosing subgraph. But all neighboring relations contain valuable information to characterize entities (called neighboring relational feature). For example, in Figure 1, part of relations mother of and born in around node Messi are excluded from enclosing subgraph (red paths in Train graph), but they characterize the "human" attribution of Messi. Second, enclosing subgraph may be empty or sparse, and all above methods cannot work well in this case, e.g. no usable connecting path existing between LeBron and L.A. in Test graph B. In this case, all above methods cannot work without enclosing subgraph. In fact, we can still reason inductively by some relational paths across target nodes (called neighboring relational path), e.g. the relational path (gender, lives in, located in) in Train graph (green paths).

Based on the above observations, we propose a novel inductive reasoning model, called Neighboring Relational Path Infomax, SNRI, which can effectively exploit complete neighboring information in subgraphs and model neighboring relational paths in a global way by MI maximization. Specifically, SNRI models complete neighboring relations in two aspects: neighboring relational feature for node initializing and neighboring relational path for sparse subgraph modeling. In contrast to previous works [Teru et al., 2020], we first extract enclosing subgraph for each triple but reserve complete neighboring relations for each entity. These neighboring relations are then aggregated in an attentive manner to represent entities feature. After that, we utilize neighboring relations of target triples again to build neighboring relational paths in a global way by MI maximization mechanism and apply a joint strategy for training. In this way, SNRI can effectively incorporate complete relational information into enclosing subgraph and model neighboring relational paths, thus improving the performance of inductive link prediction.

Our key contributions are summarized as follows: 1) We propose a novel inductive reasoning model, SNRI, which effectively integrates complete neighboring relations into the enclosing subgraph from two aspects: neighboring relational feature and neighboring relational path. 2) We innovatively apply MI maximization to inductive link prediction by maximizing local and global representation to model subgraph and neighboring relational paths in a global way. 3) Experiments conducted on benchmark datasets show that our work outperforms existing inductive reasoning by a large margin and demonstrate the effectiveness of characterizing entities and modeling sparse subgraphs.

2 RelatedWork

2.1 Link PredictionMethods

Transductive methods. Transductive methods learn an entity-specific embedding for each node, such as 1) translation-based TransE [Bordes et al., 2013] and TransH [Wang et al., 2014]; 2) factorization-based RESCAL [Nickel et al., 2012], and 3) GNN-based R-GCN [Schlichtkrull et al., 2018] and CompGCN [Vashishth et al., 2020]. The major differences among them are the scoring function and whether utilize structure information. However, all above models have one thing in common: reasoning over original KGs, and thus difficult to predict missing links between unseen nodes.

Inductive methods. Inductive models have generalizing ability for reasoning on unseen nodes. They are categorized into rule-based and graph-based methods. Rulebased methods explicitly learn logical rules for reasoning, which is independent to entities and thus inductive. Some differentiable methods, NeuralLP [Yang et al., 2017] and DRUM [Sadeghian et al., 2019], learn logical rules and ruleconfidence simultaneously in an end-to-end differentiable manner. However, they ignore the structure around the target triple, leading to a low expressive ability. In recent years, graph neural network (GNN) has been a powerful tool in link prediction. Some graph-based methods, such as LAN [Wang et al., 2019], aggregate neighboring node embeddings to obtain embeddings of unseen nodes, but they have limitation that unseen nodes have to be surrounded by known neighboring nodes. For reasoning inductively by structure information, GraIL [Teru et al., 2020] is the first method proposed to model enclosing subgraph structure around the target triple. Inspired by GraIL, CoMPILE [Mai et al., 2021] proposes a communicative message passing network to strengthen the message interactions between edges and entitles, thus enables a sufficient flow of relation information. However, all these models based on enclosing subgraph suffer two problems: 1) partial neighboring relations are neglected when extracting the enclosing subgraph, and 2) when enclosing subgraph is sparse or even empty, they are hard to reason inductively. In contrast, our work keeps integrated neighboring relations and builds neighboring relational paths to handle sparse subgraphs, which has a better ability for reasoning.

2.2 Contrastive Learning

Contrastive learning is an important approach of selfsupervised learning, which trains an encoder to be contrastive between representations that captures statistical dependencies of interest and those that do not [Velickovic et al., 2019]. Contrastive Learning has shown great superiority in many downstream applications [Devlin et al., 2019; He et al., 2020]. Recently, many works [Qiu et al., 2020; Velickovic et al., 2019] apply contrastive Learning for GNN. DGI [Velickovic et al., 2019] maximizes mutual information (MI) between local representation and global representation of graph to capture more common local features from both local and global perspectives. However, DGI only applies MI to unweighted graph with simple relations. Motivated by DGI, DRGI [Liang et al., 2021] introduces MI to knowledge graphs to handle multi-relational graphs, but it is still a transductive model. For catching neighboring relations in a global way, we innovatively apply MI into the inductive link prediction task by maximizing MI of subgraph and graph representations.

3 Methods

In this section, we introduce our proposed method SNRI in detail. The overall task is to score a triple (u, rt, v) in a KG G = |V,R| inductively, i.e. to predict the likelihood of the target relation rt between the unseen target nodes u and v, where V and R are sets of nodes and relations. An overview of our proposed SNRI is shown in Figure 2. SNRI mainly consists of four parts: 1) subgraph extraction and neighboring relational feature module to initialize node features, 2) subgraph neural network to learn representations of subgraphs, 3) self-supervised mutual information mechanism to model neighboring relations in a global way, and 4) a joint training strategy to optimize model.

3.1 Neighboring Relational Feature Module

Subgraph extraction. We first extract enclosing subgraph G(u, rt, v) around target triple (u, rt, v) following GraIL [Teru et al., 2020]. There are three steps for subgraph extraction. First, we obtain node sets of k-hop neighborhood, Nk(u) and Nk(v), of two target nodes u and v respectively. Then, we obtain the enclosing subgraph by taking intersection of Nk(u) ∩ Nk(v). In the end, we filter out nodes that are isolated or at a distance greater than k from either of the target nodes. But different from GraIL, we reserve complete neighboring relations N r (u) of each node, which contains relations partially omitted by enclosing subgraph.

Node initialization. Since inductive reasoning demands node attributes cannot be used, and GNN requires a node feature matrix X as input [Gilmer et al., 2017], our work initialize the node feature h0i for node i by combining positional feature hpos i and neighboring relational feature hrel i (see lower left of Figure 1). First, we obtain the positional feature hpos i ∈ Rdp by double radius vertex labeling [Zhang and Chen, 2018] scheme :

where d(i, u) and d(i, v) denote the shortest distance from node i to target head node u and target tail node v; ⊕ represents the concatenation operation; Second, we propose the following message passing for node i in an attentive manner to capture neighboring relational feature hrel i ∈ Rd :

where er and ert are relation embeddings of neighboring relation r and target relation rt, and αr reflects the importance of relation r to node i under target relation rt. In the end, we represent feature hi ∈ Rd of node i by concatenation of hrel i and hpos i , and project node embeddings to the same embeddings space as relations byW0 ∈ R(d+dp)×d :

We argue that the feature of nodes with complete neighboring relational semantics are more expressive and robust.

3.2 Subgraph Neural Network

With the initial feature of nodes, we input sampled subgraphs to subgraph neural network in SNRI (see lower right of Figure 2). As the main component of SNRI, the subgraph neural network models subgraph by two steps: 1) obtain representation of enclosing subgraph by GNN; 2) extract and model neighboring relational paths across target triple.

Enclosing Subgraph Module

We first input the subgraph G(u, rt, v) of target triple (u, rt, v) to GNN to learn representation of enclosing subgraph. For sufficiently modeling correlations between relations, our GNN model considers the interaction between nodes and relations. We define our nodes' updating function in k-th layer as:

where Nr(i) denotes the immediate outgoing neighbors of node i under relation r; Wk r is the transformation matrix for relation r for propagating messages; σ1, σ2 are Sigmoid function; αi,r is the attention weight of edge (i, r, j); φ(ek-1 r , hk-1 j ) is a fusion operation to share hidden feature of nodes and relations. Inspired by [Vashishth et al., 2020], we set the default fusion operation as subtraction φ(e, h) = e-h to discriminate direction of relation. In addition, to keep nodes and relations the same embedding space, relation embeddings are also transformed as follows:

Finally, to obtain the representation hG of subgraph G, we use an average readout function:

where VG denotes the set of nodes in subgraph G.

Neighboring Relational Path Module

To solve the issue of sparse subgraph, we propose to explore neighboring relations to model neighboring relational paths. This procedure can be seen in Figure 2. Specifically, a neighboring relational path is a relational sequence across the target nodes, i.e. p = (ru, rt, rv), where ru ∈ N rel (u) and rv ∈ N rel (v) are relations around target nodes u and v. We denote P(u,v) as the set of all neighboring relational paths across u and v in subgraph.

For each neighboring relational path p, we first model it with Gated Recurrent Network (GRU) [Cho et al., 2014] as follows:

Then, we aggregate all path representations with attention to obtain the subgraph path representation pG:

Supervised Learning

To organize above two modules in a unified framework, we combine the enclosing subgraph information hG and neighboring relational path information pG as the final representation of subgraph sG :

and assign score with embeddings of target triple (u, rt, v):

where hLu , hLu , and eLrt denote the embedding of target nodes u, v and target relation r in L-th layer of GNN respectively. Finally, for supervised learning, we construct a margin-based loss function with equal negative triples by replacing heads or tails:

where(u, rt, v) and (u′ , r′t , v′ ) refer to positive and negative samples, and γ is the margin hyperparameter.

3.3 MI Maximization in SNRI

To avoid the subgraph neural network in SNRI overemphasizing local structure, we further model neighboring relations in a global way by maximizing local-global (i.e. subgraph-graph) mutual information (MI), that is, we seek to enable neighboring relational features and paths to capture global information of entire KG.

To obtain global representation sG for G, we use a readout function to summarize the obtained subgraph representations:

where N is the number of triples in knowledge graph G; Gi ∈ G is the subgraph of i-th triple. Then, we utilize the Jensen-Shannon (JS) MI estimator [Sun et al., 2021] to maximize the estimated MI over subgraph and graph representations. Specifically, a discriminator D(sG, sG) is employed, which assign the probability score to subgraph-graph pair. Note that D should be higher for subgraphs contained within the graph. Following DGI [Velickovic et al., 2019], we heuristically apply a bilinear function as the discriminator:

where σ is the sigmoid function and WMI is a learnable scoring matrix. Since self-supervised MI mechanism is contrastive, negative graph G( ˜X, ˜A) is constructed by a corruption function C :

where X is the initial feature of nodes described in section 3.2, and A is the adjacency matrix of G. The corruption function C(·) preserves original structure but corrupts nodes feature by row-wise shuffling of X.

The MI objective for knowledge graph is realized by contrasting positive and negative subgraph-graph pairs:

where N, M denote the number of positive and negative samples; ˜sG refers to the representation of negative subgraph sampled from ˜G.

3.4 Joint Training Strategy

The final learning objective of our work is defined as the combination of the supervised loss in Eq. 15 and MI loss in Eq. 19:

where λ controls the contribution of the self-supervised MI mechanism. By this joint training strategy, our model is capable of modeling subgraph with complete relations while capturing neighboring relations aware of both local and global structural properties.

4 Experiments

4.1 Experimental Configurations

Datasets. WN18RR [Dettmers et al., 2018] and FB15k-237 [Toutanova et al., 2015] are common datasets used in transductive link prediction. For inductive link prediction task, we use the variants of WN18RR and FB15k-237 proposed by GraIL [Teru et al., 2020], where entities in test set are not contained in train set and each dataset generate four versions datasets with increasing size. The statistics of the datasets is shown in Table 2.

Evaluation protocol. To compare fairly with the prior methods, we use the same evaluation protocol as [Teru et al., 2020]: AUC-PR for classification metrics and Hits@10 for ranking metrics. AUC-PR is an indicator for classification task by computing the area under the precision-recall curve. To compute AUC-PR, along with all positive triples in test set, we score an equal number of negative triples sampled by corrupting head or tail with a random entity. Hits@10 is the proportion of correct entities ranked in top 10 of candidate entities. For calculating Hits@10, we compare positive triples with sampled negative triples by assigning scores, to see whether the true triple can rank top 10. Each result is obtained by averaging over 5 runs for accurate evaluation.

Hyperparameter settings. For subgraph extraction, we extract enclosing subgraph with 3 hops. In training process, we manually specify the hyperparameters as follows: learning rate to 0.001, dropout rate to 0.5, embedding dimension to 32. The margin γ in supervised loss function is set to 10, and coefficient λ in joint loss function is set to 5. The maximum number of training epochs is set to 30. We use Adam [Kingma and Ba, 2015] as optimizer to train our model. All experiments are implemented by PyTorch and run on NVIDIA RTX TITAN.

Baselines. We compare our model to several state-of-theart methods, including Neural-LP [Yang et al., 2015], DRUM [Sadeghian et al., 2019], GraIL [Teru et al., 2020], and CoMPILE [Mai et al., 2021]. Neural-LP and DRUM are rulebased models learning logical rules and rule-confidence simultaneously in an end-to-end differentiable manner. GraIL and CoMPILE are graph-based models reasoning inductively by enclosing subgraph.

4.2 Main Results

Comparison with baselines. The results comparing with baseline models are shown in Table 1. The results show that our proposed model SNRI significantly outperforms baselines on the majority of datasets in terms of both AUC-PR and Hits@10 evaluation protocol, which demonstrates the effectiveness of our proposed model. Specifically, the average boosts of SNRI on WN18RR and FB15k-237 in Hits@10 reach up to 5.34% and 3.64% respectively compared with SOTA model CoMPILE, and it can be seen that the performance on WN18RR is more significant. This is because all previous works based on enclosing subgraph are hard to do reasoning when subgraph is sparse. As presented in Table 2 WN18RR has a lower ratio of #T to #E than FB15k-237, which means that subgraphs in WN18RR are more likely to be sparse, and thus scant of structure information for reasoning. In contrast, our model can deal with sparse subgraph powerfully by modeling neighboring relational features and neighboring relational paths to exploit complete neighboring relations sufficiently. But for FB15k-237, the improvement is less significant, which may be because subgraphs in FB15k237 have very high density so that it is much easier for baselines to handle.

Effective modeling of sparse subgraph. In this section, we tend to further verify that our proposed SNRI is capable of modeling complete neighboring relations to handle sparse subgraphs. We evaluate the ranking performance of CoMPILE and our proposed SNRI on subgraphs with different densities in WN18RR v1 and v4. Concretely, we divide subgraphs into three ranges according to the number of nodes in subgraph and then calculate Hits@10 of each range. As presented in Figure 3, SNRI performs better on WN18RR v1 and v4 across all ranges, especially for the range with low subgraph density. This result shows that SNRI possesses a better inductive ability for sparse subgraphs, and proves the necessity of capturing complete neighboring relations.

4.3 Ablation Study

In this section, we perform ablation study on WN18RR v1 and v4 to investigate the impact of each component in SNRI, namely, 1) neighboring relational feature (called SNRI w/o NRF), 2) neighboring relational paths (called SNRI w/o NRP), and 3) MI maximization (called SNRI w/o MI), by removing them respectively. Table 3 shows the results of ablation studies. We can find that all variants of SNRI perform worse than the original SNRI, which demonstrates the effectiveness of each component.

SNRI w/o NRF. After removing the neighboring relational feature, the Hits@10 value averagely reduces by 0.7%. The reason may be that nodes feature with only positional information are less expressive, which cannot characterize the node effectively, and when nodes in subgraph are plentiful the positional feature is unstable and less robust. In contrast, complete neighboring relations are more effective and robust to characterize node features.

SNRI w/o NRP. From the result of SNRI w/o NRP, we can notice that performance drops a lot when neighboring relational paths are omitted. Associated with the result of section 4.2, this result demonstrates neighboring relational paths are effective in handling sparse subgraphs. SNRI w/o NRF together with SNRI w/o NRP demonstrates the effectiveness of utilizing complete neighboring relations which are omitted by enclosing subgraph.

SNRI w/o MI. Additionally, removing MI maximization results in an average reduction of 1.7%. This result implies global information is helpful to model neighboring relations better. We can observe that complete neighboring relations play a greater role in SNRI than MI maximization, but better performance can be obtained by considering complete neighboring relations and MI maximization simultaneously.

4.4 Case Study

FromWN18RR and FB15k-237, We select some target relations and then display the top 2 important neighboring relational paths in Table 4. The result shows that SNRI can learn correct neighboring relational paths and tend to assign a high score for the path with multiple relational types, indicating that SNRI prefers more informative neighboring relational paths to reason inductively. For example, considering target relation related form, the path (related form, related form, also see) gets a larger importance weight than (related form, related form, related form) with single relational type.

5 Conclusion

In this paper, we propose a novel model called SNRI for inductive link prediction on knowledge graph, which can effectively exploit complete neighboring relations and learn global structure information. SNRI utilizes complete neighboring relations to characterize neighboring relational features of nodes in a more expressive manner, and then models neighboring relational path in a global way by MI maximization. The experiments on two benchmark datasets demonstrate our proposed SNRI significantly outperforms several existing state-of-the-art methods for the inductive link prediction task, and verify the effectiveness of modeling complete neighboring relations in a global way to characterize node features and reason on sparse subgraphs.

Acknowledgements

The authors gratefully acknowledge the support of the National Natural Science Foundation of China (Grant No. 61876223, No. 61832004), Youth Innovation Promotion Association,Chinese Academy of Sciences (No.2020163), and International Cooperation and Exchanges NSFC (Grant No. 62061136006).