Robust Embedding with Multi-Level Structures for Link Prediction

1 Introduction

Recently, there has been a surge of interest in knowledge graph construction, with projects such as DBpedia [Auer et al., 2007] and Google's Knowledge Vault [Dong et al., 2014]. KGs present data as multi-relational graphs composed of entities as nodes and relations as different types of edges. The edges (triples) are represented as a triple of the form (s, r, o) (e.g. s = John, r = IsBornIn, o = Athens). These knowledge graphs can store rich factual knowledge and have proven useful for many NLP tasks, including question answering [Bordes et al., 2015], information retrieval [Xiong and Callan,

∗Corresponding Author

2015]. Meanwhile, the incompleteness of these KGs stimulates more attention to predicting missing triples, which is the aim of link prediction task.

One of the most crucial techniques for link prediction task is knowledge graph embedding. Its key idea is to encode entities and relations into continuous low dimensional vector spaces, i.e., embeddings. And then these embeddings are inputted to scoring models for predicting new relations. Finally, entity and relation embeddings are obtained by maximizing the total likelihood of observed triples. With the translational assumption of es+er ≈ eo, early works, such as TransE [Bordes et al., 2013], mapped entities and relations into the same vector space. TransH [Wang et al., 2014], TransR [Lin et al., 2015] are then proposed by introducing more complicated relational translation constraints. Besides, DistMult [Chang et al., 2014], ComplEx [Trouillon et al., 2016] utilize multiplicative score functions for calculating probability of triples.

Despite the success of embedding methods, link prediction is, in fact, an inherently graph-formulated task. Embedding methods ignore the neighbor structure of the knowledge graph, where many missing pieces of information reside. In contrast, graph neural network (GNN) can effectively learn node embeddings by recursively aggregating and transforming embeddings of neighbor nodes. To combine the strengths of both methods into a single model, [Schlichtkrull et al., 2018] proposed an encoder-decoder framework (R-GCN). RGCN contains an encoder of a GNN and a decoder of a tensor factorization embedding method, DistMult. By explicit modeling neighborhood structures, R-GCN recovers missing facts and significantly outperforms the direct optimization of the factorization model.

However, R-GCN model still faces 3 challenges: 1) Low representational power: R-GCN uses mean aggregator on the embeddings of the neighbor nodes. This kind of aggregation scheme is not injective, and easily confused by structures with repeating features. Consider the central node v1 and v2, where v1 and v2 have the same set of neighbors with distinct feature vectors, but v1 contains multiple copies of the neighbor set of v2. The mean aggregator takes averages over distinct feature vectors, and maps v1 and v2 to the same embeddings. 2) Stacking in a flat way: R-GCN model is inherently flat since it can only propagate information along the edges. Thus, it is limited to the 1-hop or 2-hop local neighbors, and not able to model the multi-level structure of the original graph. 3) Poor robustness to noise: For a given central node, R-GCN weighs information from every neighbor node equally and then performs element-wise mean pooling on the aggregated information embeddings. However, the importance of different neighbors is not the same, and information from unimportant or unreliable neighbors may severely mislead embedding learning, especially in noisy and sparse real-world knowledge graphs.

In this paper, we propose a Multi-level Graph Neural Network (M-GNN) framework for link prediction. M-GNN framework consists of an encoder of a multi-level graph neural network, and a decoder of an embedding method (e.g. DisMult, ComplEx). To improve the representational power of GNN layers, we first identify the structures confusing R-GCN and then define an injective aggregate scheme using multi-layer perceptrons (MLPs). On this basis, we develop graph coarsening schemes for relations with different mapping properties, and then stack multiple GNNs on these graphs so as to model multi-level structures of the original graph. Furthermore, to perform predictions on the noisy knowledge graphs, attention mechanisms are adopted so that M-GNN can learn the neighbor information adaptively. We show that M-GNN significantly outperforms the standard baselines on the WN18 and FB15k datasets. Meanwhile, the extensive analysis demonstrates that M-GNN maintains robustness even on noisy and sparse datasets.

Our contributions are summarized as follows:

• We point out the graph structures that cannot be distinguished by R-GCN, and define powerful GNN layers with an injective aggregation scheme.
• We develop a graph coarsening scheme and stack multiple GNN layers on a series of coarsened graphs, which helps to learn the multi-level structural information of the original KG.
• We demonstrate the effectiveness of our proposed MGNN on the standard WN18 and FB15k datasets. Furthermore, experiments on the noisy knowledge graph suggest that our approach is highly robust to noise and sparsity.

2 RelatedWork

In recent years, knowledge graph embedding has obtained a surge of attention, and become one of the most crucial techniques in link prediction task. Its key idea is to embed the entities and relations of a KG into continuous vector spaces, in order to simplify manipulation while preserving the inherent structure. With the translational assumption of es + er ≈ eo, early works, such as TransE [Bordes et al., 2013], mapped entities and relations into the same vector space. TransH [Wang et al., 2014], TransR [Lin et al., 2015] further extended TransE by introducing more complicate relational translation constraints and projecting entities and relations into different continuous spaces. These models based on translational constraints are also called additive models or translational distance models. Besides, DistMult [Yang et al., 2015] and ComplEx [Trouillon et al., 2016] utilize multiplicative score functions for calculating plausibility of triples, which are known as multiplicative models or tensor factorization models.

Despite the huge success in embedding methods for making predictions of new facts, link prediction is an inherently graph-formulated task, where connectivity structures are also important. Our proposed model (M-GNN) incorporate previous embedding methods with those neighbor structures by assigning an extension of graph neural network (GNN) as the encoder and an embedding method as the decoder.

GNNs were proposed to efficiently ingest graph structure and perform predictions. Recent attempts to extend GNN can be divided into two classes of approaches. The spectral approaches [Henaff et al., 2015; Defferrard et al., 2016] learn convolution filter using the eigendecomposition of the graph Laplacian. The second class of methods, known as spatial approaches, define convolutions directly on the graph. These approaches maintain the effective parameter-sharing, while are invariant to edge order and node degree, such as learning adaptive weights for different node degrees [Duvenaud et al., 2015], or formulating the problem as message passing [Gilmer et al., 2017].

The most relevant work to ours is R-GCN [Schlichtkrull et al., 2018], which enforces connectivity structures in embedding methods with an encoder of GNN module. However, RGCN is easily affected by noise since it aggregates all kinds of information from neighbors, cannot distinguish some simple structures due to non-injective aggregation scheme, and ignore the hierarchical structural information in the graph. GCNN [Neil et al., 2018] is a simple extension of R-GCN with a regularized attention mechanism that slightly improves the performances, but still suffers from low representational power, flat network structure and poor robustness problems. In contrast, our proposed approach weighs neighbor structural information adaptively, identifies an injective aggregator using MLPs and stacks multiple GNN layers in a multi-level way to obtain further improvements.

3 Method

We first introduce the following definitions of the knowledge graph (KG): we denote the knowledge graph as a directed and multi-labeled graph G = (V, E,R), where vi ∈ V is a node, ri ∈ R is a relation type and (vi, rj , vk) ∈ E is a labeled edge (or a triple).

In this section, we present our approach in detail. We first introduce a basic graph neural network for link prediction (§ 3.1). Then we detail the GNN layers (§ 3.2) with high representational power and multi-level GNN (§ 3.3) with Graph Coarsening.

3.1 A Basic GNNModel

We first begin with a basic GNN framework for link prediction. Following [Xu et al., 2018; Schlichtkrull et al., 2018], an end-to-end GNN link prediction model comprises two components: a GNN-based encoder for embedding entities, and a decoder for calculating the probability of edges.

Encoder

A GNN-based encoder collects information from the neighborhood structure and then map entities (nodes) to embeddings. Modern GNNs follow the neighbor aggregation strategy [Xu et al., 2018], updating the representation of a node by aggregating representations of its neighbors repeatedly. The k - th layer of a GNN can be formulated as follow:

where hkv is the feature vector of node v at the k-th layer and N(v) is the set of nodes adjacent to node v.

In a relational multi-graph (such as KG), we can naturally extend the above framework as follow:

where h(k) r,u : u ∈ N r v denotes the message passing from the neighbor node u under relation r at the k-th layer, and h(k) r0,v denotes the self-connection message.

R-GCN and R-GCN+ [Schlichtkrull et al., 2018] set hr,u = Wrhu, AGGREGATE(·) = MEAN(·), and define the following propagation model for the forward-pass update of the entity embeddings:

where N r i denotes the set of neighbor indices of node i under relation r ∈ R. ci,r is a normalization constant (ci,r = |N r i |). In [Neil et al., 2018], attention mechanisms are adopted and ci,r is trainable.

Decoder

Link prediction deals with the prediction of new facts (triples), given an incomplete subset of the knowledge graph. The task is to assign scores in order to determine how likely those unseen edges belong to E.

To address the problem, the decoder needs to reconstruct edges of the knowledge graph using the entity embeddings from the encoder, i.e., ev = h(K) v , for v ∈ V . A variety of algorithms can be adopted, since the choice of decoder is independent of the encoder. R-GCN [Schlichtkrull et al., 2018] mainly focuses on the DisMult decoder:

where es, eo are the subject and object embeddings and Rr is a diagonal relaton matrix. In our work, we also consider ComplEX decoder [Trouillon et al., 2016].

In the following sections, we mainly focus on the GNN based encoder, designing GNN layers with high representational power, and extending flat GNN layers to the multi-level form.

3.2 AGNN Layer with High Representational Power

The choice of AGGREGATE(·) and COMBINE(·) in Eq. 2 is crucial to the representation power of the GNN layer. In the previous studies, R-GCN and R-GCN+ [Schlichtkrull et al., 2018] utilize mean pooling as their aggregator. However, as Figure 1 shows, such kind GNN can be even confused by some simple graphs. In Figure 1, nodes with different colors have different embeddings. In Figure 1(a), when conducting neighborhood aggregation, the mean aggregator fails to distinguish the structures and obtains the same information, since 12 (2 · hr1blue) = 1 3 (3 · hr1blue). Similarlly, the mean aggregator fails in Figure 1(b) since 12 (hr1blue + hr1yellow) = 1 4 (2 · hr1blue +2 · hr1yellow). Intuitively, a powerful GNN layer maps two entities to the same location only if they have identical neighborhood structures with identical embeddings on the corresponding entities. This means its aggregation scheme is injective, i.e., for each pair ((r0, v), {(r, u) : u ∈ N r v }), hv = GNN((r0, v), {(r, u) : u ∈ N r v }) is unique. According to Corollary 6 in [Xu et al., 2018], we can decomposed any injective GNN(·) as GNN(·) = φ((1 + ϵ) · f(r0, v) + ∑u∈N r v f(r, u)) for some function f, φ, and constant ϵ. In practice, we can use multilayer perceptrons (MLPs) to model f and φ, according to the universal approximation theorem [Hornik et al., 1989]:

where ϵ(k) can be a learnable parameter or a fixed scalar. Strictly, we should set hr,v = MLPr(hv) for every r ∈ R ∪ {r0} to make aggregation scheme injective. To reduce complexity, we simply employ the linear transformation here: hr,v = Wrhv.

3.3 Multi-Level GNN Layers with Graph Coarsening

In the previous studies [Schlichtkrull et al., 2018; Neil et al., 2018], the GNN method is inherently flat, i.e., they can only

Algorithm 1 Graph Coarsening.

Require:

Knowledge graph KG = (V, E, R);

Ensure:

Coarsened graph G0, G1, ..., Gk;

• 1: m← 0
• 2: G0 ←KG
• 3: while |Em| ≥ threshold do
• 4: m←m+1;
• 5: Gm ←EdgeCoarsen(NeighborCoarsen(Gm-1))
• 6: end while
• 7: return G0,G1, ...,Gk;

propagate information across edges. These methods are unable to aggregate information of different granularities. As Figure 2 shows, our goal is to stack multiple GNN layer in a multi-level way: we first define a strategy to output a series of coarsened graphs, and then we can build a multi-level GNN operating on these graphs with different scales.

Graph Coarsening

To develop a graph coarsening scheme that preserves structural information at different scales, we consider four types of relations in KGs [Lin et al., 2015]: 1-to-1, 1-to-N, N-to-1 and N-to-N. And each type of relation may contain different structures:

• 1-to-1 relations: only contain the 1-to-1 structure.
• 1-to-n/n-to-1 relations: may contain 1-to-1 and 1-to-n/nto-1 structures.
• n-to-n relations: may contain 1-to-1, 1-to-n and n-to-1 structures.

Here, n-to-n structure is not taken into consideration since it can be divided into multiple 1-to-n and n-to-1 structures. For 1-to-1 structure, we propose a simple coarsening scheme, namely edge coarsening. It first selects a subset E ′ ⊂ E, in which no two edges are incident to the same node. And then, as Figure 3(a) shows, for each (vi, r, ui) ∈ E ′ , it merges (vi, r, ui) into a supernode. For 1-to-n/n-to-1 structure, considering the similarity of nodes that share the same neighborhood, we develop the neighbor coarsening scheme. As Figure 3(b) and Figure 3(c) shows, (e1, e6), (e2, e3), (e4, e5) are merged into supernodes since they share same neighbor e7. The orders for both coarsening schemes are arbitrary since we obtain similar node embeddings with different coarsening orders.

To combine edge and neighbor coarsening scheme, as algorithm 1 shows, in each coarsening step, we first compress the input graph with neighbor coarsening, and then adopt edge coarsening to output a new coarser graph.

Multi-Level GNN

The outputs of the graph coarsening scheme are a series of coarsened graphs, G1, ..., GK, where G1 is the coarsest graph and GK is the original graph. As Figure 2 shows, our goal here is to stack K GNN layers aggregating structural information from the coarsest graph to the original graph. We denote S(k) ∈ Rnk×nk+1 as the cluster assignment matrix at layer k. Each column of S(k) refers to one of the nk+1 nodes at layer k + 1, and each row refers to one of the nk supernodes (clusters) at layer k. S(k) provides the assignment of each node in graph Gk+1 to the supernode in the coarsened graph Gk. After the embedding matrix H(k-1) for the graph Gk-1 is learned, we extend it as the initial representations for the graph Gk by S(k-1) T H(k-1) . Now we can define k - th layer of our proposed multi-level GNN by extending Eq. 5 as follow (on the graph Gk):

where H′(k) is a embedding matrix mapped from the embedding matrix H(k) through assignment matrix S(k) and we randomly initialize the embedding matrix H(0) . Following the previous work [Schlichtkrull et al., 2018; Neil et al., 2018], we optimize our model with cross-entropy loss and negative sampling.

4 Experiments

In this section, we present our experimental settings and results. We first introdue the datasets and baselines in our experiment (§ 4.1 and § 4.2). Then, we first evaluate our approach in the standard link prediction task (§ 4.3). After that, by constructing noisy knowledge graphs, we conduct extensive analysis on the robustness of our approach (§ 4.4).

4.1 Datasets

We evaluate our link prediction algorithm on two commonly used datasets: FB15k, a subset of the multi-label knowledge base Freebase and WN18, a subset of WordNet featuring lexical relations between words. Both datasets are released by [Bordes et al., 2013].

As [Toutanova and Chen, 2015] shows, inverse triplet pairs t = (e1, r, e2) and t′ = (e2, r-1 , e1) appears in both datasets with t in the training set and t′ in the test set. This inverse triplet pair flaw simplifies a large part of link prediction task for the memorization of inverse triplet pairs. To address this problem, [Toutanova and Chen, 2015] release the dataset FB15k-237 removing all inverse triplet pairs. Thus, We use FB15k-237 dataset for our extensive experiments. Table 1 further summarizes the statistics of the datasets.

All the datasets only provide positive triples. Following [Bordes et al., 2013], we adopt the local closed world assumption to generate negatives. Specifically, given a triple, we randomly corrupt the subject or the object to generate a negative example.

4.2 Baselines

DistMult [Yang et al., 2015] and ComplEx [Trouillon et al., 2016] are the common baselines. These factorization methods not only perform well on standard datasets, but are the decoders of our proposed model. Besides, we also consider R-GCN and R-GCN+ [Schlichtkrull et al., 2018], the current GNN-based methods for link prediction, and GCNN [Neil et al., 2018], which is an extension of R-GCN in a way that weighs the different connections of a central node adaptively. We further compare with the classic algorithm TransE [Bordes et al., 2013].

4.3 Link Prediction Task

In this section, we combine our multi-level GNN model with decoders to predict new facts in knowledge graphs. Multiple decoders are adopted including DistMult [Yang et al., 2015] and ComplEx [Trouillon et al., 2016]. We select commonly used WN18 and FB15k for evaluating our link prediction algorithms.

Results

For the evaluation of link prediction results, we measure the quality of every test triple among all possible subjects and objects substitution. In our experiment, we use two widely used evaluation metrics for link prediction: mean reciprocal rank (MRR) and Hits at n (Hits@n). We report both filtered and rawMRR (following [Bordes et al., 2013]), and filtered Hits at 1, 3 and 10.

In addition to baselines, we evaluate several variants of our model: M-GNN(MLP) employs Eq.5 without graph coarsening scheme; M-GNN(MLP, Multi) uses both MLPs and graph coarsening scheme, i.e., Eq.6. Considering complementarity between models, we also employ ensemble scheme as [Schlichtkrull et al., 2018], which we refer to as MGNN+(MLP, Multi). To avoid the influence of the choices of decoders, we consider both DistMult (with "*") and ComplEx (with "**") decoders for both M-GNN and R-GCN.

The hyperparameters in M-GNN are determined by the grid search on the validation set. The ranges of the hyperparameters are manually set as follow: learning rate {0.01, 0.005, 0.003, 0.001}, dropout rate {0, 0.1, 0.2, 0.3,...,0.9}, embeddings size {100, 150, 200, 300}, regularization coefficient {0.01,0.05,0.1,0.5,1.0}, the number of negative samples {1,3,5,10} and ϵ = 0. For both FB15k and WN18 datasets, we use M-GNN with three GNN layers and all MLPs have two layers with the hidden unit number ∈ {10,50,100,200}. For the ComplEx encoder, we treat complex vector C d as real vector Rd×2 in the encoder. We train the models with Adam optimizer [Kingma and Ba, 2015].

Results are shown in Table 2. We first compare our model M-GNN with the first five baselines. M-GNN consistently outperforms those methods without graph neural network. Thus, we can conclude that GNN takes the neighborhood structures into consideration, which significantly facilitates the learning process of entity and relation embeddings.

Then, we compare M-GNN to R-GCN with the same decoder DistMult or ComplEx. M-GNN(MLP) consistently outperforms R-GCN, while M-GNN(MLP, Multi) consistently outperforms both M-GNN(MLP) and R-GCN. It demonstrates that MLP layers and multi-level structural information are both beneficial for link prediction. Additionally, we show the cross-entropy loss on training sets in Figure 4. We observe that our approach can fit the training sets better and its convergence process is significantly faster, which contributes to high representational power and multi-level structural information.

Finally, we compare M-GNN** with M-GNN* and RGCN. M-GNN** significantly outperforms M-GNN* and RGCN for the most of situations. This suggests that combined with the decoder that achieves higher results, M-GNN can predict new facts more accurately.

In summary, our proposed model M-GNN can accurately predict new facts, and each component of our model is helpful for entity and relation representation learning.

4.4 Extensive Analysis on the Robustness

In the previous sections, we can conclude that our proposed method is effective for the standard link prediction task. To further analyze the robustness to noise and sparsity, we adopt experimental settings in [Neil et al., 2018] on the FB15k-237 dataset, and four different training conditions are taken into consideration.

Results

Following [Neil et al., 2018], the training set is split evenly so that half of the triples are in gtrue and half in gadd. First, to establish a baseline, methods are trained normally on the full datasets (gtrue ∪ gadd), which refers to "100%" condition. To explore the impact of sparsity, we establish "50%" condition, which refers to training only on gtrue. To generate noisy triples, we follow [Pujara et al., 2017] and corrupt one of a subject, relation, or object entry for the triples in gadd with equal probability, such that |gnoise| = |gadd|. For "Skip" condition, the adjacency matrix of the GNN model contains all the edges from gall = gtrue ∪ gadd ∪ gnoise, while only edges in ggold are used for training. For "Noised" condition, methods are trained upon gall.

For predicting new facts on the noisy graphs, we follow [Neil et al., 2018] and adopt the attention mechanism on our proposed GNN layer: h(k) v = MLP (k) ((1 + ϵ(k) ) · h(k-1) r0,v + ∑u∈N r,(k) v αv,r,uh(k-1) r,u ), where αv,r,u ∈ [0, 1] is trainable. For the FB15k-237 datasets of the four training settings, we use M-GNN with two GNN layers and all MLPs have two layers. Other ranges of hyperparameters are the same in the link prediction task. Note that since M-GNN+ and M-GNN show very similar results, we only report the results of the M-GNN model here.

In the experiment, we evaluate link prediction results and report filtered MRR and Hits@10. The results are shown in Table 3. The results of baselines are taken from [Neil et al., 2018], which compare favorably with those reported in [Schlichtkrull et al., 2018]. For the "100%" training condition, our model consistently outperforms other baselines including R-GCN (MRR:0.158, Hits@10:0.414) and R-GCN+ (MRR:0.156,Hits@10:0.417). For the noisy or sparse knowledge graph, all the performances are dramatically reduced, while M-GNN can still achieve the best results. Thus, GNN layers with higher representational power and multi-level structural information are more robust to sparsity and noise.

5 Conclusions

In this paper, we proposed a novel multi-level GNN-based framework (M-GNN) with high representational power and demonstrated its effectiveness and robustness on multiple datasets under various training conditions. We first pointed out the examples that confused mean aggregator, which was widely used by the previous GNN-based models. Then, we identified an injective aggregation scheme, and further designed a powerful GNN layer using MLPs. On the basis of that, we coarsened the knowledge graph into a series of graphs and stacked GNN layers in a multi-level way, to uncover hierarchical structure information. Experimental results show that our approach is both effective for identifying new facts and robust to noise and sparsity.

Acknowledgements

The research work is supported by the National Key R&D Program with No.2016QY03D0503,2016YFB081304, Strategic Priority Research Program of Chinese Academy of Sciences, Grant No.XDC02040400, National Natural Science Foundation of China (No.61602474, No.61602467, No.61702552).