MR-GCN: Multi-Relational Graph Convolutional Networks based on Generalized Tensor Product

1 Introduction

In recent years, Graph Convolutional Networks (GCNs) have been extensively studied, which can be applied to many graph applications, such as node classification [Kipf and Welling, 2016; Hamilton et al., 2017], link prediction [Schlichtkrull et al., 2018] and personalized recommendation [Ying et al., 2018]. In terms of convolution operation manners, there are two types of GCNs, namely spatial methods [Hamilton et al., 2017; Jørgensen et al., 2018] and spectral methods [Henaff et al., 2015; Defferrard et al., 2016; Kipf and Welling, 2016]. Despite of extensive literatures, most of them work merely on homogenous graphs with a single type of relation and cannot tackle multi-relational graphs.

∗Corresponding authors.

Recently, some remedies are put forward to address the problem, which fall into two lines in terms of their strategies. The first line conducts GCN on each single relation and then integrates the results with multi-view learning [Schlichtkrull et al., 2018; Ma et al., 2019; Sun et al., 2019]. In such methods, relation correlations are not effectively exploited as GCN basis is independently constructed on each graph. Another line is aggregating the multi-relational graph into a homogeneous graph [Khan and Blumenstock, 2019; Yun et al., 2019]. For example, Multi-GCN [Khan and Blumenstock, 2019] adopts manifold ranking to achieve the aggregation, and then applies a standard GCN on the aggregated graph. The type of methods may result in information loss or noises. Hence, both strategies are sub-optimal. The reason roots at that the convolution operation on multi-relational graphs is not defined and existing studies bypass the issue.

In this paper, we propose to define the convolution operator in multi-relational graphs, upon which a neural network framework, termed as Multi-Relational Graph Convolutional Network (MR-GCN), can be established. Specifically, a Laplacian tensor is first constructed for a given multirelational graph. The tensor based eigenvalue decomposition is formulated, which offers the basis to develop multirelational graph convolution operators (MR-GCO). As the tensor eigen-decomposition can be defined with a generalized tensor product, the basis of MR-GCO can be any unitary transform, e.g., Haar, Discrete Cosine transform (DCT), instead of limited merely to Fourier transform. To validate the effectiveness of the proposed MR-GCN framework, we empirically evaluate the performance on node classification task in multi-relational graphs. The main contributions of the paper can be summarized as follows:

• We define the convolution operator in multi-relational graphs based on the eigen-decomposition of Laplacian tensors. Upon the convolution operator, a neural network framework, namely MR-GCN, is established for node classification. To the best of our knowledge, we are the first to extend GCNs spectral graph theory by considering tensor eigen-decomposition.
• Different from conventional GCNs, which perform convolutions in the spectral domain with discrete Fourier transform (DFT), our MR-GCN is established on the eigen-decomposition defined by generalized tensor

product. Hence, the spectral domain can be any unitary transform, e.g., Haar, DCT, etc, instead of limited to DFT.

• Comprehensive experimental evaluations have been conducted on four real-world multi-relational graphs, and the results show that the developed MR-GCN framework outperforms state-of-the-art competitors.

2 RelatedWork

2.1 Graph Convolutional Networks

GCNs are increasingly developed for a wide range of tasks. According to convolution operation manners, they can be roughly categorized into two types, namely spectral methods [Bruna et al., 2013; Henaff et al., 2015; Defferrard et al., 2016; Kipf and Welling, 2016] and spatial methods [Hamilton et al., 2017; Monti et al., 2017; Jørgensen et al., 2018]. [Bruna et al., 2013] introduce a graph based convolution operator in spectral domain based on Fourier basis. Then, [Kipf and Welling, 2016] simplify the convolution via a localized first-order approximation. In contrast, spatial approaches utilize spatially close neighbors to define convolution operations. For instance, [Hamilton et al., 2017] introduce a learnable aggregating function to summarize neighbors' information for node representations.

However, most of previous GCN methods are designed for single relational graphs and cannot tackle multi-relational ones. Though several multi-relational version of GCNs appear in recent studies [Schlichtkrull et al., 2018; Ma et al., 2019; Sun et al., 2019; Khan and Blumenstock, 2019; Yun et al., 2019], their solutions are still conventional GCN in essence. The key obstacle stands in between GCN and multi-relational graphs is that a multi-graph convolution operator remains undefined, which is our focus in this paper.

2.2 Tensor Product

Tensor, also known as n-way or n-mode array, refers to a multi-dimensional array of numbers. It is a powerful tool to represent and analyze multi-dimensional data [Ng et al., 2011; Li et al., 2013; Li et al., 2017]. Conventional tensor product means mode-n multiplication. However, in this definition, the eigen-decomposition of a tensor cannot be well defined. In [Kilmer and Martin, 2011], a novel tensor product, termed as t-product is introduced, which is indeed a generalized matrix multiplication, where each element denotes a tube and Fourier convolution is adopted because each element is a vector rather than a scalar in conventional matrix. Based on the product, a tensor singular value decomposition (t-svd) is formulated. Very recently, [Song et al., 2019] further generalize the t-product by relaxing the DFT into any unitary transform. In this paper, we aim to define convolution operator in multi-relational graphs with the generalized tensor product.

3 Proposed Framework

In this section, we introduce the proposed MR-GCN framework. First, we revisit the basic concepts of graph convolutions and some essential definitions of generalized tensor product (GTP) as preliminaries. Then we present how the MR-GCN operator is developed and finally discuss to build the semi-supervised node classifier upon the operator.

3.1 Preliminaries

Notations

In this paper, we define the fields of real and complex number with respect to R and C. Tensors and matrices are symbolized by Euler and boldface capital letters, respectively. Let A ∈ Rn1×n2×n3 be a third-order tensor, we represent its (i, j, k)-th entry as Aijk and employ matlab notations A(i, :, :), A(:, i, :) and A(:, :, i) to denote the i-th horizontal, lateral and frontal slices, respectively. For simplicity, we also denote the frontal slice A(:, :, i) as A(i) .

Graph Convolution Operator

The core idea of GCN is to define convolution operator based on graph structures. To this end, the graph Fourier transform is first formulated by replacing the eigen basis of continuous Laplacian in Fourier transform with that of graph Laplacian. Then, the convolution operator on the graph can be easily defined following the convolution theorem. Given a graph G with an adjacency matrix A ∈ RN×N , we calculate its normalized graph Laplacian as L = I-D- 12 AD- 1 2 , where I is the identity matrix and D represents a diagonal degree matrix with entries Dii = ∑j Aij. Then the convolution of a input signal x∈RN with a filter g∈RN on G is defined as:

where ⋆G denotes the graph convolution operator, ⊙ indicates the Hadamard product which is element-wise multiplication and U refers to the matrix of row-wise eigenvectors of the normalized graph Laplacian, which is obtained by its eigenvalue decomposition L=UT ΛU. Ux and Ug are the graph Fourier transforms of x and g.

Generalized Tensor Product

To well define the eigen-decomposition of tensors, t-product is formulated in [Kilmer and Martin, 2011]. In the product, third-order tensors are considered as a matrix with each element to be a vector, instead of a scalar. By analogue with matrix multiplication, t-product is defined and vectorvector interaction is achieved by circular convolution, which corresponds to DFT. In [Song et al., 2019], DFT is further extended to any unitary transform and a generalized tensor product (GTP), i.e., Φ-product, is introduced. Next, we briefly introduce the GTP.

Let A∈Cn1×n2×n3 be a third-order tensor, and Φ∈Cn3×n3 be the unitary transformmatrix, i.e., ΦΦH =ΦH Φ=I. Here ΦH denotes the Hermitian transpose of Φ. We let Φ[A] represent the transformed tensor (also denoted as ˆ AΦ), which is obtained by applying the transform Φ to each tube along the third dimension. That is, we have vec ( ˆ AΦ (i, j, :)) = Φ[vec (A(i, j, :))], where vec(·) refers to mapping the tensor tube to a vector. Thanks to the unitary property of Φ, we have A=ΦH Φ[A] =ΦH [ ˆ AΦ]. Let blockdiag(A) be a n1n3-by-n2n3 block diagonal matrix, obtained by putting the frontal slices of A into the diagonal, and fold indicate its inverse operator, namely A= fold (blockdiag (A)). With the notations, the conjugate transpose of A is defined as:

Given two third-order tensors A ∈ Cn1×n2×n3 , B ∈ Cn2×n4×n3 , the Φ-product between them is defined as follow:

where ⋄Φ represents the generalized tensor product, × is the standard matrix product and its result is C∈Cn1×n4×n3 .

3.2 Multi-Relational Graph Convolution Operator

Let MG be an undirected multi-relational graph and its topology is characterized by an adjacency tensor A ∈ RN×N×R, where N and R represent the numbers of nodes and relations, respectively. We construct a diagonal degree tensor D∈RN×N×R, where Diik = ∑j Aijk and Dijk =0 for ∀i ̸=j. Then, a normalized Laplacian tensor L ∈ RN×N×R is constructed and each of its frontal slice L(i) is computed as:

where I∈ RN×N is the identity matrix.

To extend the graph convolution theory into the multirelational case, we need perform eigen-decomposition on the Laplacian tensor L. Unlike the matrix, which has a standard eigen-decomposition, tensors require to know product definitions in advance. Here we adopt the Φ-product presented in preliminaries. The choice has two important advantages. First, it can nicely exploit the inherent correlations across relations. To understand this point, we revisit the GTP and reveal its essence. Figure 1 presents an example of GTP computation. We can see that the product of two tensors A and B is computed as the following three steps: (i) converting the tensors into Φ space (i.e., ˆ AΦ and ˆ BΦ); (ii) performing slice-by-slice matrix multiplication; (iii) transforming the result back to the original space with ΦH . The steps follow the definition in Eq. 3. By convolution theorem, the process suggests that the product can be written as:

Algorithm 1 Tensor Based Eigenvalue Decomposition

Input: L∈CN×N×R, Φ∈CR×R.

• 1: ˆ LΦ =Φ[L]
• 2: for i = 1, ...,R do
• 3: [U, S] = EVD( ˆ L(i) Φ );
• 4: ˆ U (i) Φ =U, ˆ S (i) Φ =S;
• 5: end for
• 6: U=ΦH [ ˆ UΦ], S=ΦH [ ˆ SΦ]

Output: U∈CN×N×R, S∈CN×N×R.

Here ◦Φ denotes a convolution defined by Φ. For example, when considering t-product, Φ is the DFT and ◦Φ corresponds to the circular convolution. Thanks to the convolution along the relation dimension, the eigentensor of L defined on Φ-product can nicely model the relation correlations. Second, Φ-product can correspond to any unitary transform (e.g., DCT, Haar, etc), not limited to DFT as t-product. Next, we introduce how to perform tensor based eigenvalue decomposition (TEVD) for the Laplacian tensor L.

Theorem 1. Let L∈CN×N×R be a third-order Laplacian tensor, where each frontal slice is symmetric and semi-definite. We define TEVD along the third dimension with respect to Φ-product and factorize L as follow:

Here U ∈ CN×N×R denotes the eigentensor and U ⋄ΦU H = U H⋄ΦU =IΦ, where Φ[IΦ] is a tensor with each frontal slice being the N×N identity matrix. S ∈CN×N×R is a diagonal tensor with eigenvalues.

The TEVD computation is summarized in Algorithm 1, which is very simple. Its main idea is to convert each frontal slice of tensor L into Φ-space, perform eigen-decomposition, fold them into tensors ˆ UΦ and ˆ SΦ and then transform the two tensors back into the original space.

Definition 1. Given a normalized Laplacian tensor L ∈ RN×N×R of an undirected multi-relational graph MG, a convolution operator of the input signal x∈RN×R with the filter g∈RN×R on MG can be defined as follow:

where ⋆MG denotes the multi-relational graph convolution operator (MR-GCO), ⊙ refers to the element-wise Hadamard product. And U ⋄Φx and U ⋄Φg represent the transformed tensors based on U , which is the row eigentensor of Laplacian tensor L with Φ.

To better understand the MR-GCO definition, we illustrate its computation process in Figure 2. Given a graph with adjacency tensor A, we construct its normalized Laplacian tensor L and compute the corresponding eigenvalue decomposition by Algorithm 1. As a result, we obtain the eigentensor U as the transform basis. According to the GTP definition in Eq. 3, the signal x and filter g are transformed into a new space by U, and then their Hadamard product result is obtained. With Eq. 2, we compute U H , which is the conjugate transpose tensor of U. Finally, the Hadamard product result is transformed back by U H . The MR-GCO can better model the relation correlations than multi-view GCNs, e.g., R-GCN [Schlichtkrull et al., 2018], because (i) the eigentensor basis is not computed independently for each view, but as a whole (See Eq. 6); (ii) the signal x is convolved with filter g based on the whole eigentensor basis (See Eq. 7), instead of on each view basis as multi-view GCNs.

3.3 Semi-supervised Learning withMR-GCN

The developed MR-GCO can be utilized in any multirelational graph tasks. In this paper, we adopt it to build a semi-supervised node classifier. The architecture of the classifier is shown as in Figure 3. We can see that it consists of three key components, which are conventional GCN layers, MR-GCO layers and fully connected layers. Let us elaborate the three components, respectively. Given a multi-relational graph A ∈ RN×N×R, we let a matrix X ∈ RN×F denote its node features, where F is the feature size. As the input signal X has an inappropriate size for MR-GCO, we apply two-layer GCN [Kipf and Welling, 2016] in each relational graph with d-dimensional output as:

where ˜A=A+I is the adjacency matrix A of the graph G with added self-connections, ˜D is the diagonal degree matrix of ˜A and W(l) is the matrix of filter parameters. We note the layers can be in any form, not necessary to be GCN. By folding the its outputs, we obtain a tensor signal X ∈RN×d×R and feed it into the second component. After several layers of MR-GCO, the tensor signal is further transformed but its size does not change. Finally, in the third component, the tensor signal is flattened into a matrix and a simple multi-layer perceptron (MLP) as well as a softmax layer is appended. In the task, we adopt the cross-entropy loss.

4 Experiments

4.1 Experimental Setup

Datasets

In this paper, we adopt node classification to evaluate the performance. The following four real-world multi-relational graphs are utilized and Table 1 summarizes the statistics of them.

• ACM 1 is an academic multi-relational graph. In the graph, each node is a paper and two types of connections are considered, namely paper coauthor edge and paper subject edge. Bag-of-word representation of each paper is given as its node attribute, and its category is regarded as node label. We follow the settings of the raw dataset for training, validation and test separation.
• IMDB 1 is a multi-relational graph from movie dataset, which also includes two types of relations. Each movie is a node and its description is also changed into bag-ofword representation. The movie genre is the node label. Similarly, the raw dataset provides the training, validation and test sets.
• Amazon 2 is a multi-relational graph from Amazon purchase record. We employ the metadata of Electronics category and construct two types of connections between products, namely co-viewed or co-purchased. Node feature is composed one-hot encoding of its category list and its price information. The main category of each product is treated as node label. We randomly select 20 products from each category as our training set, and validation and test sets consist of 500 and 1,000 instances, respectively.
• Reuters 3 is a graph constructed from a multilingual dataset. The dataset contains 1,200 documents over six labels and is described by five views of 2,000 words. In the graph, each document is a node. We treat its English view as node attribute and construct four connections based on the other views. Specifically, two document nodes are connected in a view if their normalized text similarity is larger than 0.5. We follow the similar way on Amazon to construct the training, validation and test sets.

1 https://drive.google.com/file/d/

1qOZ3QjqWMIIvWjzrIdRe3EA4iKzPi6S5/view

2 http://deepyeti.ucsd.edu/jianmo/amazon/index.html

3 http://lig-membres.imag.fr/grimal/data.html (Sample 1 is used)

As our MR-GCN can be equipped with any unitary transform, we select six well-known transforms to validate its effectiveness, which are discrete Cosine, Walsh-Hadamard, Fourier, Hartely, Haar and Slant [Jain, 1979].

4.2 Results and Discussions Main Results

Tables 2 and 3 report the classification performance. As if there are only two types of relations, the six unitary transform matrices are exactly the same. Hence, Table 2 shows the results on ACM, IMDB and Amazon which include two relations and Table 3 summarizes the results on Reuters that has four relations.

According to Table 2, we make following conclusions: (i) Our MR-GCN yields the best performance on the three two-relational graphs. This is attributed to our developed multi-relational convolution operator. In the operator, the tensor based eigenvalue decomposition is conducted to construct the transform basis, which nicely exploits the inherent correlations across relations. (ii) For all the single relational graph embedding methods, namely LINE, DeepWalk, Node2Vec, Planetoid and GCN, we find that their results on union graph structures are better than those on single relational graphs in general. The observation implies the usefulness of multi-relational topology, which validates our motivation. (iii) GCN and Planetoid always beat LINE, DeepWalk and Node2Vec, because they are semi-supervised approaches while the other methods are unsupervised. (iv) We observe

Baselines

To test the performance of the proposed MR-GCN, we compare it with graph embedding and state-of-the-art GCN approaches. Specifically, three graph embedding methods are adopted as baselines (i.e., LINE [Tang et al., 2015], DeepWalk [Perozzi et al., 2014] and Node2Vec [Grover and Leskovec, 2016]). As the three methods are all unsupervised, we also consider a semi-supervised attributed graph embedding method, namely Planetoid [Yang et al., 2016], and its inductive version is leveraged. GCN [Kipf and Welling, 2016] is a robust and popular approach, we include it as a baseline as well. We note that all the above graph embedding and GCN approaches are developed for single relational graphs. To compare with them, we report their performance on each single relational graph and a union graph whose adjacency matrix is an addition of all the adjacency matrices of relations. Very recently, two new graph neural network (GNN) approaches, heterogeneous graph attention network (HAN) [Wang et al., 2019] and graph transformer network (GTN) [Yun et al., 2019], are proposed for multi-relational graphs. They both generate new graph structures based on meta-paths, where HAN learns the importance of fixed metapaths via an attentional graph neural network and GTN automatically learns meta-paths. We also adopt the two approaches as baseline methods.

Implementation Details

To make a fair comparison, we set the embedding dimension as 64 and adopt Adam optimizer for all approaches. The implementations of LINE, DeepWalk and Node2Vec are obtained from OpenNE 4 and the ones of all the other baselines are provided by their authors. For HAN and GTN, we adopt the meta-path setting as [Yun et al., 2019] on ACM and IMDB, and initialize meta-paths for the other datasets with adjacency matrices. We tune all the baseline methods based on the validation sets.

In the proposed MR-GCN, we set the maximum of epochs to be 500 and employ the early stop strategy. The window size and dropout rate are set as 10 and 0.5, respectively. The other hyperparameters, learning rate from {0.01, 0.005, 0.0025, 0.001}, layer numbers from {1, 2, 3, 4, 5}, l2 loss weight decay parameter from {5e-2, 5e-4, 1e-8}, are tuned based on validation sets. Finally, we set the learning rate as 0.001 on ACM and Reuters, 0.0025 on IMDB and 0.005 on Amazon. We adopt 1 layer MR-GCO on Amazon and IMDB, 2 layer MR-GCO on Reuters and 4 layer MR-GCO on ACM. The best optimal l2 loss weight decay parameters are 5e-4 on ACM and Reuters, 1e-8 on IMDB and 5e-2 on Amazon.

4 https://github.com/thunlp/OpenNE

that GNN based approaches, namely GCN (union), HAN, GTN and the proposed MR-GCN significantly outperforms Planetoid (union), except for the Amazon dataset where HAN is worse due to no-well-fixed meta-paths available. The fact implies the necessity to develop graph convolution operators to tackle graph related problems, which also validates our motivation to build convolution operators for multi-relational graphs.

In Table 3, similar observations and conclusions can be made. Moreover, among the six transforms, we find that Cosine, Hadamard and Haar deliver the best results, followed by Hartely and Slant. Fourier is less competitive than the other five transforms. The reason may be that the circular correlation (corresponding to Fourier), which makes periodic assumptions on signals, is not very suitable to model the graph relations.

Ablation Studies

Revisiting Figure 3, it can be seen that our framework contains two key components: (i) constructing input tensor with a fold of the GCN result on each single relation; (ii) multirelational graph convolution operator. To examine the effectiveness of the two components, we conduct experiments on two variants, namely '-w/o GCN' which utilizes random initializations instead of GCNs, and '-w/o MR-GCO' which removes the multi-relational graph convolution operators. Table 4 shows the results, from which we can conclude that both components are very useful in our MR-GCN.

4.3 Parameter Sensitivity Study

Impact of layer numbers. Here we investigate how the number of MR-GCO layers affects the performance. Figure 4 shows the results on the four datasets, where the layer number is increased from 1 to 5. It can be observed that the parameter is more sensitive on IMDB and Reuters than on ACM and Amazon. The reason may be that the distributions of node representations learned by different MR-GCO layers sensitively affect the margins of classifiers on the two datasets.

Convergence and impact of training set sizes. In this part, we test the convergence and the impact of training set sizes. Here we adopt the Cosine transform and show the results on Reuters (Results on other datasets are similar). We can see from Figure 5(a) that the test loss and accuracy tend to level off after 250 epochs, indicating a fast convergence. From Figure 5(b), we find that the performance of GCN (union), HAN, GTN and the proposed MR-GCN all improve as the training sample ratio is increased from 10% to 50%, which is not surprising as the methods obtain more supervision information. Moreover, we observe that MR-GCN consistently outperforms GCN (union), HAN and GTN, which again validates the superiority of the proposed method.

5 Conclusion

In this paper, we study the multi-relational graph learning problem and extend the notion of GCN by developing a novel multi-relational graph convolution operator. The operator is defined upon the eigenvalue decomposition of the Laplacian tensor. As we consider generalized tensor product, the decomposition can correspond to any unitary transform. Extensive experiments on four real-world datasets have been conducted, and the results show the effectiveness of the proposed method.

Acknowledgments

This research was supported in part by the National Key R&D Program of China, 2018YFB2101100, 2018YFB2101101 and NSFC under Grant Nos. 61972111, U1836107, 61602132 and 61572158.