A Vectorized Relational Graph Convolutional Network for Multi-Relational Network Alignment

1 Introduction

Network alignment has recently attracted special attention from both industry and academia. It aims at finding the corresponding network elements (referred to as anchors thereafter), such as nodes or relations, in different networks if they refer to the same entity/relationship. The alignment of networks, such as aligning multi-lingual knowledge graphs, helps to construct more complete and compact networks, thus increasing the accuracy and robustness for applications like knowledge inference and cross-domain recommendation.

Embedding-based models are promising and efficient solutions for network alignment tasks because they are capable of representing and preserving the structures of networks in low-dimensional subspaces. Thereafter, the alignment can be achieved in the embedding spaces by sharing or transforming the embeddings of anchors.

∗Xin Li is the corresponding author. This work has been partially supported by National Key R&D Program of China under Grant No. 2017YFB0803300, NSFC under Grant No. 61772074.

Recent research in embedding models focuses on developing representation learning algorithms to acquire numerical representations of networks. Single-relational networks, in which all edges are of the same type, require to embed only nodes by representing each node i as a vector ui ∈ Rd . In comparison, multi-relational networks, in which the vertices are connected by various types of edges or relations, require to embed both nodes and relations as low-dimensional vectors to preserve the network structure.

In general, two categories of embedding models can be summarized based on whether considering the embedding of relations. For example, DeepWalk [Perozzi et al., 2014], and Node2Vec [Grover and Leskovec, 2016] target at singlerelational networks and belong to "embedding without relations". In comparison, TransE [Bordes et al., 2013] and its extensions [Wang et al., 2014] model relations as translating operations on the low-dimensional embedding of the entities. That is, if there is an edge (h, r, t), in which a relation r links the head entity h and the tail entity t, then the equation h + r = t should be preserved in the embedded space. They belong to "embedding with relations".

Motivated by the success of deep learning, increasing interests have emerged to apply task-driven deep network embedding for graph data [Bruna et al., 2013; Defferrard et al., 2016]. [Kipf and Welling, 2016] utilized a two-layer graph convolutional network (GCN) to achieve semi-supervised classification of graph nodes. With the integration of random walk or attention mechanism, [Niepert et al., 2016] and [Ying et al., 2018] proposed more dedicated GCN models for single-relational network embedding. However, the conventional spectral-based GCN and its variants can only process undirected single-relational networks because they require normalized graph Laplacian to be real symmetric positive semidefinite to facilitate graph Fourier transform, indicating that the adjacency matrix must be symmetric, and the 2-D adjacency matrix also restricts edges to be the same type.

To deal with multiple relation types, R-GCN [Schlichtkrull et al., 2017] utilizes more representative node embeddings with the consideration of the effects of different relation types by iteratively accumulating weighted neighbor entities. However, it has no relation representations involved.

In summary, existing GCN-based models belong to "embedding without relations". It is evident that relations in networks also carry rich semantic information as nodes, and the incorporation of relation embeddings would help to boost the effectiveness of relevant applications, such as knowledge base completion and multi-lingual knowledge graph alignment. Therefore, conventional GCNs and R-GCN cannot be applied for multi-relational network alignment tasks.

Addressing this issue, in this paper, we propose a vectorized relational graph convolutional network (VR-GCN), which generates both entity embeddings and relation embeddings simultaneously, to enable the incorporation of GCN and multi-relational networks. The design of its convolution function should consider the following three criterions:

1. Explicit relation embedding: VR-GCN should explicitly include the vectorized relation, and the relation embeddings will affect the learning of the entity embeddings.
2. Role discrimination: VR-GCN should be capable of performing different convolution operations on an entity according to its role. Generally, the same entity may take the role of being a head role in one triplet but of a tail in another. This requirement becomes indispensable for directed graphs.
3. Translation adoption: VR-GCN should conform to the translation operation h+r ≈ t to imply the network edge which has two entities h and t connected by a specific relation r.

Based on the network embedding, graph alignment can be achieved in the subspaces. Graph alignment, in fact, consists of entity alignment and relation alignment. However, most existing models for multi-relational network alignment, no matter they include relation embedding or not, either ignore the needs of relation alignment or assume all relations are previously aligned. Therefore, we propose an alignment framework, with VR-GCN as the network embedding model, to support both entity alignment and relation alignment. Experiments demonstrate that the inclusion of relation alignment, in turn, improves the outcomes of entity alignment.

The main contributions of this paper include:

1. We proposed VR-GCN for the embedding of multirelational networks, in which both entity embeddings and relation embeddings are explicitly supported. VRGCN combines the strength of both convolutional and translational properties for multi-relational networks.
2. We proposed AVR-GCN, the alignment framework based on VR-GCN, to support both entity alignment and relation alignment for multi-relational networks. Optimization techniques are designed to improve the effectiveness of the alignment results.
3. We evaluated the proposed alignment framework with entity alignment, relation alignment, and link prediction tasks on knowledge graphs. The results demonstrate that our method constantly outperforms other state-of-the-art approaches for various tasks, and prove that the inclusion of relation alignment can improve the outcomes of entity alignment.

2 RelatedWork

Our work is mainly related to two lines of research: network embedding and knowledge graph alignment.

2.1 Network Embedding

Network embedding refers to learning representations of nodes/edges in networks, which has demonstrated its effectiveness in many application scenarios. For single-relational networks, DeepWalk and Node2vec extend the skip-gram model in natural language processing to the representation learning of networks. LINE attempts to generate the representations of nodes by retaining the "first-order proximity" and/or "second-order proximity" of local structures. For multi-relational networks, TransX [Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015] interprets relations as translating operations between head and tail nodes, which can be denoted as h + r ≈ t.

Motivated by the powerful feature extraction capability and remarkable success of deep neural networks, [Defferrard et al., 2016] proposed a spectral graph theoretical formulation of CNNs on graphs and a convolutional network extending the conventional CNNs to non-Euclidean space. [Kipf and Welling, 2016] further extended this idea and proposed graph convolutional neural networks (GCNs) to integrate the connectivity patterns and feature attributes of graph-structured data, and achieved remarkable results in semi-supervised classification. Thereafter, a series of improvements and extensions were proposed based on GCN. GAT [Velickovic et al., 2017] employs the attention mechanism to GCNs, in which each node gets an importance score based on its neighborhood, thus providing more expressive representations for nodes. R-GCN is a relation-aware node embedding model based on GCN for knowledge graphs. The convolution of RGCN is a relation-specific transformation in which the impact weights between different nodes depend on the relation types.

Although R-GCN applies the relation information as the weights to induce node embedding, it does not support the representations of relations themselves. In fact, the vector representations of relations are critical in tasks like relation alignment of Knowledge graphs. Moreover, the proper representation learning of relations may help to improve the quality of node representations.

2.2 Knowledge Graph Alignment

The alignment of multi-relational networks centers on aligning knowledge graphs. It is generally accomplished by using network embeddings to identify the linkage between networks via the structural and anchor information.

MTransE [Chen et al., 2017] embeds entities and relations of each knowledge graph in a separate space with TransE, and then provides five different variants of transformation functions to project the embedded vectors from one subspace to another. The candidate set of one node's correspondence in the other network can be obtained by ranking the distance between them in the transformed space. In contrast, ITransE [Zhu et al., 2017] utilizes TransE to learn one common low-dimensional subspace for all knowledge graphs, with the constraint that the observed anchor seeds from different knowledge graphs share the same vector representation in the subspace. Furthermore, ITransE iteratively updates the embeddings of entities and relations to perform the alignment when the "confidence" of a newly discovered anchor pair is larger than an empirical threshold. AlignE [Sun et al., 2018] also adopts TransE to learn network embeddings, and applies parameter swapping to encode networks into a unified space. Instead of using TransX to direct the representation learning of knowledge graph, NTAM [Li et al., 2018] employs a probabilistic embedding model [Liu et al., 2017] to learn the node embeddings for alignment tasks. It claims to retain the triangular structures in networks that TransX fails. GCN(SE) [Wang et al., 2018] levers on the conventional GCN to encode the entities from multiple knowledge graphs into a unified embedding space to perform the alignment. It views the relations as influential weights on entities in proportion to the number of entities connected with different types of relations.

However, the aforementioned alignment approaches focus on entity alignment across networks without explicit relation representations [Wang et al., 2018] or assuming the relations are previously fully aligned [Zhu et al., 2017]. Therefore, they are inherently insufficient or incapable of relation alignment tasks, which we argue is also an important task as illustrated in Sec. 1. In comparison, we propose a vectorized relational GCN (VR-GCN) to learn the embeddings of both nodes and relations explicitly for knowledge graphs. With both entity and relation representations learned, the alignment framework could be optimized by minimizing the "entity loss" as well as "relation loss", which is semi-supervised by the observed entity anchor pairs and relation anchor pairs.

3 Model

A Knowledge Graph KG = (E, R, T ) is a directed network, where E, R and T denote the set of entities, relations and triplets respectively. A triplet (h, r, t) represents a tail entity t is connected to the head entity h by the relation r. Knowledge Graph Alignment finds the aligned entities and relations between KGi = (Ei, Ri, Ti) and KGj = (Ej , Rj , Tj). The prior knowledge of the aligned entities/relations are observed anchors. They are denoted as the set of anchor entity pairs Ea = {(ei, ej)|ei ∈ Ei, ej ∈ Ej} and the set of anchor relation pairs Ra = {(ri, rj)|ri ∈ Ri, rj ∈ Rj} respectively.

3.1 VR-GCN Framework

In comparison with existing GCNs, VR-GCN is capable of learning the vectorized embedding of relations, in addition to that of entities, in the convolution process.

VR-GCN integrates the strength of GCN and the translational property in knowledge graphs [Bordes et al., 2013] (h + r ≈ t) to design the new propagation model. Eq.(1) defines the update rule for the entity and relation embeddings:

where Nr denotes the set of relations connecting the entity i. N r t denotes the set of tail entities connected with the entity i by the relation r. N r h denotes the set of head entities connected with the entity i by the relation r. hlh ∈ Rd(l) , hlr ∈ Rd(l) , and hlt ∈ Rd(l) denote the lth layer embedding of the head entity, relation, and tail entity respectively in the neural network, and d(l) is the dimensionality of this layer's representation. σ is the activation function, such as Sigmoid and Relu. c(·, ·) is the function to describe the relationship between hlt and hlr , and ˆ c(·, ·) describes the relationship between hlh and hlr . W l is the weight matrix of the lth layer.

Eq.(1) features the role discrimination (Section 1) criterion to identify if entity i in the knowledge graph takes the role of head or tail entity regarding a specific relation r. It performs different convolution operations for them: if i has the head entity role, its embedding is calculated by combining the related tail entity hlt and relation hlr ; Otherwise, its embedding is calculated with the related head entity hlh and relation hlr . Thereafter, all occurrences of head roles and tail roles of i are added, together with a single self-connection representation hli , to infer the l + 1 representation of the entity i.

The design of function c and ˆ c features the translation adoption criterion which is h + r ≈ t for a triplet (h, r, t) in the graph. Alternatively, the translational property can be transformed into h ≈ t - r and t ≈ h + r. Therefore, let

Apply them to Eq.(1), the convolutional function becomes:

where di is the normalization coefficient which equals to the degree of the entity i, including its outdegree and indegree.

Fig.1 illustrates the embedding process defined by Eq.(3). It updates the embedding of an entity by accumulating the embeddings of its neighboring entities and relations, and updates the embedding of a relation by integrating embeddings of its head and tail entities. It can be applied to a neural network to update embeddings of entities and relations, and multiple layers can acquire more flexible structure information.

The proposed convolutional function is capable of distinguishing different roles of entities and utilizing the translational property in knowledge graphs to learn the embeddings of both entities and relations, which in fact helps to retain the structural information of the graphs. In comparison with existing GCNs, the vectorized representations of relations have better support for knowledge graph alignment tasks.

3.2 VR-GCN-based Knowledge Graph Alignment

This section introduces AVR-GCN, a knowledge graph alignment framework based on VR-GCN.

As illustrated in Fig.2, given two knowledge graphs KGX and KGY , each of them learns its embedding representation based on VR-GCN first to capture the structural information of each graph. Denote their embeddings as VR-GCNX and VR-GCNY respectively. Since each graph has a unique embedding space, the weight sharing mechanism [Wang et al., 2018] is utilized to join them into a unified space for alignment. By sharing the weight matrices W (X) and W (Y ) , the problem of estimating the probability of entities/relations alignment is converted into measuring the distance between entities/relations in the unified embedding space.

Anchors are the knowledge about the aligned entity or relation pairs from different graphs. In this framework, anchor information is applied in two ways to enhance the alignment performance. It is first utilized to define the objective function for the alignment. In the shared embedding space, the distances between aligned entities/relations should be minimized and those of unaligned entities/relations should be maximized. Therefore, the objective function is:

where (ex, ey) and (rx, ry) denote a pair of aligned entities and relations respectively, and (e′x , e′y ) and (r′x , r′y ) denote its corresponding unaligned (negative) pair of entities and relations. Boldfaced ex, ey, rx, ry, e′x, e′y , r′x, r′y represent the corresponding vectorized embeddings acquired by VR-GCN for aforementioned graph elements. d(x, y) = ‖x-y‖1 . ξ is a margin hyper-parameter separating positive and negative alignments, and α is also a hyper-parameter balancing the importance of the entity and relation alignment.

The second way is to use existing entity anchors to generate new cross-network triplets to build a bridge between different knowledge graphs at the level of triplet. Let Tx and Ty be the triplet sets for knowledge graph KGX and KGY respectively. Following [Sun et al., 2018], we generate the supervised triplets as:

After injecting the generated triplet set Ta into both graphs, KGX and KGY are expanded to have more shared edges. Consequently, their embeddings would be closer to each other, which will help to improve the alignment performance.

Putting them together, the following strategy is adopted:

1. Randomly select a subset of anchors to generate Ta. Then, inject Ta to graphs before learning their embeddings with VR-GCN.
2. With the learned embeddings, use the remaining anchors to minimize Eq.(4).

4 Experiment

We first evaluated AVR-GCN framework on cross-lingual entity alignment and relation alignment tasks to testify its effectiveness on multi-relational network alignment. In addition, VR-GCN model was experimented with link prediction task for its effectiveness on multi-relational network embedding.

4.1 Knowledge graph alignment

The experiments consist of cross-lingual entity alignment and relation alignment on the trilingual datasets, which were extracted from the real knowledge graph DBpedia containing multilingual versions of DBPZH-EN (Chinese to English), DBPJA-EN (Japanese to English) and DBPFR-EN (French to English). Table 1 lists their statistical summaries.

Evaluation Metrics. Standard metrics, Hits@k and mean reciprocal rank (MMR), were used to evaluate the performance of knowledge graph alignment. Hits@k measures the proportion of correct items in top-k ranked candidates and MMR measures the mean reciprocal rank of correct entities and relations. Regarding the bi-directional feature of network alignment, which means the alignment may start with either network as the source, Hits@k in this paper is computed as the average of iterating each network as the source.

Baselines and Settings. For the model configuration, the input feature vectors of entities and relations were randomly initialized, and then fed to the 2-layer VR-GCN to update the embeddings. In the experiments, d = 300, ξ = 3, α = 1,and the ratio of anchors for new triplet generation was 0.5.

The following state-of-the-art approaches were included in the comparison for the graph alignment task:

• MTransE uses linear transformations between two vector spaces which are built by TransE.
• ITransE embeds entities from different graphs into a unified vector space and uses the predicted anchors iteratively to improve performance.
• NTAM utilizes a probabilistic model to obtain network embeddings to accomplish the alignment task.
• AlignE takes ε-truncated uniform negative sampling and parameter swapping to implement KG embedding. It is a variant of BootEA without bootstrapping.
• GCN(SE) uses structural information to align entities based on the entity embeddings learned by GCNs.
• GCN(SE)∗ is an extension to GCN(SE) by running GCN(SE) on the alignment framework proposed in this paper. We provided GCN(SE)∗ for a fair comparison.
• AVR-GCN(rl.exl.) is a variant of AVR-GCN but with the relation component in the objective function ex-

cluded. It serves as a baseline to differentiate the impact of relation alignment on entity alignment.

Entity Alignment

Each dataset was split into training and test sets as 30-70 which used less prior anchor information for the learning process. Moreover, for a given entity, the lookup scope for aligning candidates should include the entire network. Otherwise, if only known anchor entities are included in the lookup process, which was used in some existing models, the results may not be practical because of its implicit assumption that all anchors are known and accurate.

Table 2 reports the results, showing that AVR-GCN outperforms all other methods on all trilingual datasets. Specifically,

• AVR-GCN is significantly better than most translationbased methods, such as MTransE and ITransE. It proves that VR-GCN has better support for capturing the complex structure information in multi-relational networks than translation-based models. Besides, NTAM, which utilizes a probabilistic embedding space, also performs better than MTransE and ITransE, supporting the argument that TransX is inefficient in capturing complex network information.
• GCN(SE)∗ performs better than GCN(SE), showing that the proposed alignment framework is beneficial for graph alignment tasks.
• AVR-GCN(rl.exl.) outperforms other baselines even though no relation anchor information is applied in the alignment stage, indicating that the explicit consideration of relation embedding helps to improve entity alignment. Meanwhile, AVR-GCN is better than AVRGCN(rl.exl.). The only difference between them is the

inclusion of relation anchors in the alignment stage. Therefore, it is evident that the aligned relation information can boost the alignment performance.

• Finally, in comparison with GCN(SE)∗ which likewise utilizes GCN and the same alignment framework, VRGCN boosts the performance by up to 22%, proving that the vectorized relation representations or relation embeddings are valuable for alignment tasks.

To evaluate the correlation between entity alignment and relation alignment, we incrementally increased the ratio of known aligned relations in the training process on the oneside ZH-EN dataset. It actually demonstrates the changes when we evolve from AVR-GCN(rl.exl.), which includes no relation alignment, to AVR-GCN, which has all relation alignment. Table 3 shows that the more previously known aligned relations included, the better performance for entity alignment. The observation validates the importance of relation alignment which has not attracted enough attention. In other words, AVR-GCN is capable of levering on the relation alignment to not only support relation alignment tasks, but also improve the performance of entity alignment.

Relation Alignment

Fig.3 depicts the results of relation alignments, showing that AVR-GCN consistently outperforms other methods on all baselines. Only Hits@1 -Hits@5 are shown in the graph because the datasets have insufficient numbers of relations tagged. It should be noted that conventional GCNs are not capable of performing relation alignment due to their lack of support for relation embeddings. Therefore, they are not included. In comparison with translation-based models and NTAM, AVR-GCN benefits from its modeling of interactions between entity and relation in the process of convolution.

4.2 Link Prediction

Link prediction, which is widely used to evaluate the effectiveness of network embedding models, does training and testing with a single network. It targets at predicting the missing h or t for a triplet (h, r, t) in a given KG to improve the completeness of the network.

Following R-GCN, we adopt the graph auto-encoder model, which consists of an entity-relation encoder and a scoring function (decoder). VR-GCN acts as an encoder to map each entity and relation to the real-valued vector. For the scoring function needs to support the non-linear and translational properties in convolution process, we utilized h+r and t - r to replace t and h in the scoring function proposed in DistMult [Yang et al., 2014], then:

The triplets (h, r, t) appeared in the dataset were taken as the positive samples, and negative samples were generated by randomly corrupting each triplet (h, r, t) with head h or tail t replaced. The cross-entropy was utilized to restrict that positive samples have higher scores than negative ones.

Datasets and Baselines. The experiments were based on two well-known benchmark datasets, WN18 and FB15k-237 1 which were extracted from the relational database WordNet and Freebase respectively. The State-of-the-art models included for comparison are TransE, DisMult, and R-GCN.

Result. Table 4 shows the results of link prediction by baselines and VR-GCN on two individual networks. VR-GCN has consistent improvements on both datasets. VR-GCN and RGCN both perform better than TransE, indicating that deep model has a stronger capability of acquiring the structure information than TransX. VR-GCN outperforms the baseline DistMult, showing the effectiveness of the VR-GCN encoder. VR-GCN also performs better than R-GCN favorably, which highlights the significance of vectorized relation embedding.

5 Conclusion

This paper proposes a vectorized relational graph convolutional network (VR-GCN) to learn the embeddings of both graph entities and relations simultaneously for multirelational networks. The role discrimination and translation property of knowledge graphs are adopted in the convolutional process. Thereafter, AVR-GCN, the alignment framework based on VR-GCN, is developed for multi-relational network alignment tasks. The weight sharing mechanism is utilized to join the embeddings of graphs into a unified space for alignment. Anchors are used to supervise the objective function which aims at minimizing the distances between anchors. Moreover, anchors are also used to generate crossnetwork triplets to build a bridge between knowledge graphs at the level of triplet to improve the performance of alignment. The experimental results on the real-world datasets show that the proposed solutions outperform the state-of-theart methods in network embedding, entity alignment, and relation alignment. For future work, we plan to integrate the attention mechanism and semantic information into the model.

1 FB15k-237 is a version of FB15k with problematic inverse relation pairs removed.