Title: COMPOSITION-BASED MULTI-RELATIONAL GRAPH CONVOLUTIONAL NETWORKS

Abstract: Graph Convolutional Networks (GCNs) have recently been shown to be quite successful in modeling graph-structured data. However, the primary focus has been on handling simple undirected graphs. Multi-relational graphs are a more general and prevalent form of graphs where each edge has a label and direction associated with it. Most of the existing approaches to handle such graphs suffer from over-parameterization and are restricted to learning representations of nodes only. In this paper, we propose COMPGCN, a novel Graph Convolutional framework which jointly embeds both nodes and relations in a relational graph. COMPGCN leverages a variety of entity-relation composition operations from Knowledge Graph Embedding techniques and scales with the number of relations. It also generalizes several of the existing multi-relational GCN methods. We evaluate our proposed method on multiple tasks such as node classification, link prediction, and graph classification, and achieve demonstrably superior results. We make the source code of COMPGCN available to foster reproducible research.

1. INTRODUCTION:

Graphs are one of the most expressive data-structures which have been used to model a variety of problems. Traditional neural network architectures like Convolutional Neural Networks (Krizhevsky et al., 2012) and Recurrent Neural Networks (Hochreiter & Schmidhuber, 1997) are constrained to handle only Euclidean data. Recently, Graph Convolutional Networks (GCNs) (Bruna et al., 2013; Defferrard et al., 2016) have been proposed to address this shortcoming, and have been successfully applied to several domains such as social networks (Hamilton et al., 2017) , knowledge graphs (Schlichtkrull et al., 2017; Shang et al., 2019) , natural language processing (Marcheggiani & Titov, 2017; Vashishth et al., 2018a; b; 2019) , drug discovery (Ramsundar et al., 2019) , crystal property prediction (Sanyal et al., 2018) , and natural sciences (Fout et al., 2017) .

However, most of the existing research on GCNs (Kipf & Welling, 2016; Hamilton et al., 2017; Veličković et al., 2018) have focused on learning representations of nodes in simple undirected graphs. A more general and pervasive class of graphs are multi-relational graphs 1 . A notable example of such graphs is knowledge graphs. Most of the existing GCN based approaches for handling relational graphs (Marcheggiani & Titov, 2017; Schlichtkrull et al., 2017) suffer from overparameterization and are limited to learning only node representations. Hence, such methods are not directly applicable for tasks such as link prediction which require relation embedding vectors. Initial attempts at learning representations for relations in graphs (Monti et al., 2018; Beck et al., 2018) have shown some performance gains on tasks like node classification and neural machine translation.

There has been extensive research on embedding Knowledge Graphs (KG) (Nickel et al., 2016; Wang et al., 2017) where representations of both nodes and relations are jointly learned. These methods are restricted to learning embeddings using link prediction objective. Even though GCNs can 1. We propose COMPGCN, a novel framework for incorporating multi-relational information in Graph Convolutional Networks which leverages a variety of composition operations from knowledge graph embedding techniques to jointly embed both nodes and relations in a graph. 2. We demonstrate that COMPGCN framework generalizes several existing multi-relational GCN methods (Proposition 4.1) and also scales with the increase in number of relations in the graph (Section 6.3). 3. Through extensive experiments on tasks such as node classification, link prediction, and graph classification, we demonstrate the effectiveness of our proposed method.

The source code of COMPGCN and datasets used in the paper have been made available at http: //github.com/malllabiisc/CompGCN.

GCNs for Multi-Relational Graph: An extension of GCNs for relational graphs is proposed by Marcheggiani & Titov (2017) . However, they only consider direction-specific filters and ignore relations due to over-parameterization. Schlichtkrull et al. (2017) address this shortcoming by proposing basis and block-diagonal decomposition of relation specific filters. Weighted Graph Convolutional Network (Shang et al., 2019) utilizes learnable relational specific scalar weights during GCN aggregation. While these methods show performance gains on node classification and link prediction, they are limited to embedding only the nodes of the graph. Contemporary to our work, Ye et al. (2019) have also proposed an extension of GCNs for embedding both nodes and relations in multirelational graphs. However, our proposed method is a more generic framework which can leverage any KG composition operator. We compare against their method in Section 6.1.

Knowledge Graph Embedding: Knowledge graph (KG) embedding is a widely studied field (Nickel et al., 2016; Wang et al., 2017) with application in tasks like link prediction and question answering (Bordes et al., 2014) . Most of KG embedding approaches define a score function and train node and relation embeddings such that valid triples are assigned a higher score than the invalid ones. Based on the type of score function, KG embedding method are classified as translational (Bordes et al., 2013; Wang et al., 2014b) , semantic matching based (Yang et al., 2014; Nickel et al., 2016) and neural network based (Socher et al., 2013; Dettmers et al., 2018; Vashishth et al., 2019) . In our work, we evaluate the performance of COMPGCN on link prediction with methods of all three types.

3. BACKGROUND:

In this section, we give a brief overview of Graph Convolutional Networks (GCNs) for undirected graphs and its extension to directed relational graphs.

GCN on Undirected Graphs: Given a graph G = (V, E, X ), where V denotes the set of vertices, E is the set of edges, and X ∈ R |V|×d0 represents d 0 -dimensional input features of each node.

The node representation obtained from a single GCN layer is defined as:

H = f ( ÂX W ).

Here, Â = D -1 2 (A + I) D -1 2 is the normalized adjacency matrix with added self-connections and D is defined as D ii = j (A + I) ij . The model parameter is denoted by W ∈ R d0×d1 and f is some activation function. The GCN representation H encodes the immediate neighborhood of each node in the graph. For capturing multi-hop dependencies in the graph, several GCN layers can be stacked, one on the top of another as follows:

H k+1 = f ( ÂH k W k ),

where k denotes the number of layers, W k ∈ R d k ×d k+1 is layer-specific parameter and H 0 = X .

GCN on Multi-Relational Graphs: For a multi-relational graph G = (V, R, E, X ), where R denotes the set of relations, and each edge (u, v, r) represents that the relation r ∈ R exist from node u to v. The GCN formulation as devised by Marcheggiani & Titov (2017) is based on the assumption that information in a directed edge flows along both directions. Hence, for each edge (u, v, r) ∈ E, an inverse edge (v, u, r -1 ) is included in G. The representations obtained after k layers of directed GCN is given by

EQUATION

Here, W k r denotes the relation specific parameters of the model. However, the above formulation leads to over-parameterization with an increase in the number of relations and hence, Marcheggiani & Titov (2017) use direction-specific weight matrices. Schlichtkrull et al. (2017) address overparameterization by proposing basis and block-diagonal decomposition of W k r .

4. COMPGCN DETAILS:

In this section, we provide a detailed description of our proposed method, COMPGCN. The overall architecture is shown in Figure 1 . We represent a multi-relational graph by G = (V, R, E, X , Z) as defined in Section 3 where Z ∈ R |R|×d0 denotes the initial relation features. Our model is motivated by the first-order approximation of GCNs using Chebyshev polynomials (Kipf & Welling, 2016) . Following Marcheggiani & Titov (2017) , we also allow the information in a directed edge to flow along both directions. Hence, we extend E and R with corresponding inverse edges and GCN Marcheggiani & Titov (2017) O(Kd 2 ) Weighted- GCN Shang et al. (2019) O(Kd 2 + K|R|) Relational- GCN Schlichtkrull et al. (2017) O(BKd 2 + BK|R|) 

COMPGCN (Proposed Method) O(Kd 2 + Bd + B|R|)

E = E ∪ {(v, u, r -1 ) | (u, v, r) ∈ E} ∪ {(u, u, ) | u ∈ V)},

and R = R ∪ R inv ∪ { }, where R inv = {r -1 | r ∈ R} denotes the inverse relations and indicates the self loop.

4.1. RELATION-BASED COMPOSITION:

Unlike most of the existing methods which embed only nodes in the graph, COMPGCN learns a

d-dimensional representation h r ∈ R d , ∀r ∈ R along with node embeddings h v ∈ R d , ∀v ∈ V.

Representing relations as vectors alleviates the problem of over-parameterization while applying GCNs on relational graphs. Further, it allows COMPGCN to exploit any available relation features (Z) as initial representations. To incorporate relation embeddings into the GCN formulation, we leverage the entity-relation composition operations used in Knowledge Graph embedding approaches (Bordes et al., 2013; Nickel et al., 2016) , which are of the form

e o = φ(e s , e r ).

Here, φ : R d × R d → R d is a composition operator, s, r, and o denote subject, relation and object in the knowledge graph and e (•) ∈ R d denotes their corresponding embeddings. In this paper, we restrict ourselves to non-parameterized operations like subtraction (Bordes et al., 2013) , multiplication (Yang et al., 2014) and circular-correlation (Nickel et al., 2016) . However, COMPGCN can be extended to parameterized operations like Neural Tensor Networks (NTN) (Socher et al., 2013) and ConvE (Dettmers et al., 2018) . We defer their analysis as future work.

As we show in Section 6, the choice of composition operation is important in deciding the quality of the learned embeddings. Hence, superior composition operations for Knowledge Graphs developed in future can be adopted to improve COMPGCN's performance further.

4.2. COMPGCN UPDATE EQUATION:

The GCN update equation (Eq. 1) defined in Section 3 can be re-written as

h v = f (u,r)∈N (v) W r h u ,

where N (v) is a set of immediate neighbors of v for its outgoing edges. Since this formulation suffers from over-parameterization, in COMPGCN we perform composition (φ) of a neighboring node u with respect to its relation r as defined above. This allows our model to be relation aware while being linear (O(|R|d)) in the number of feature dimensions. Moreover, for treating original, inverse, and self edges differently, we define separate filters for each of them. The update equation of COMPGCN is given as: where x u , z r denotes initial features for node u and relation r respectively, h v denotes the updated representation of node v, and W λ(r) ∈ R d1×d0 is a relation-type specific parameter. In COMPGCN, we use direction specific weights, i.e., λ(r) = dir(r), given as:

EQUATION

Methods W k λ(r) φ(h k u , h k r ) Kipf-GCN (Kipf & Welling, 2016) W k h k u Relational-GCN (Schlichtkrull et al., 2017) W k r h k u Directed-GCN (Marcheggiani & Titov, 2017) W k dir(r) h k u Weighted-GCN (Shang et al., 2019) W k α k r h k u

W dir(r) =    W O , r ∈ R W I , r ∈ R inv W S , r = (self-loop) (3)

Further, in COMPGCN, after the node embedding update defined in Eq. 2, the relation embeddings are also transformed as follows:

EQUATION

where W rel ∈ R d1×d0 is a learnable transformation matrix which projects all the relations to the same embedding space as nodes and allows them to be utilized in the next COMPGCN layer. In Table 1 , we present a contrast between COMPGCN and other existing methods in terms of their features and parameter complexity.

Scaling with Increasing Number of Relations:

To ensure that COMPGCN scales with the increasing number of relations, we use a variant of the basis formulations proposed in Schlichtkrull et al. (2017) . Instead of independently defining an embedding for each relation, they are expressed as a linear combination of a set of basis vectors. Formally, let {v 1 , v 2 , ..., v B } be a set of learnable basis vectors. Then, initial relation representation is given as:

z r = B b=1 α br v b .

Here, α br ∈ R is relation and basis specific learnable scalar weight.

On Comparison with Relational-GCN Note that this is different from the basis formulation in Schlichtkrull et al. (2017) , where a separate set of basis matrices is defined for each GCN layer. In contrast, COMPGCN uses embedding vectors instead of matrices, and defines basis vectors only for the first layer. The later layers share the relations through transformations according to Equation 4. This makes our model more parameter efficient than Relational-GCN.

We can extend the formulation of Equation 2 to the case where we have k-stacked COMPGCN layers. Let h k+1 v denote the representation of a node v obtained after k layers which is defined as

EQUATION

Similarly, let h k+1 r denote the representation of a relation r after k layers. Then,

h k+1 r = W k rel h k r .

Here, h 0 v and h 0 r are the initial node (x v ) and relation (z r ) features respectively.

Proposition 4.1. COMPGCN generalizes the following Graph Convolutional based methods: Kipf-GCN (Kipf & Welling, 2016) , Relational GCN (Schlichtkrull et al., 2017) , Directed GCN (Marcheggiani & Titov, 2017), and Weighted GCN (Shang et al., 2019) .

Proof. For Kipf-GCN, this can be trivially obtained by making weights (W λ(r) ) and composition function (φ) relation agnostic in Equation 5, i.e., W λ(r) = W and φ(h u , h r ) = h u . Similar reductions can be obtained for other methods as shown in Table 2 .

5. EXPERIMENTAL SETUP:



5.1. EVALUATION TASKS:

In our experiments, we evaluate COMPGCN on the below-mentioned tasks.

• Link Prediction is the task of inferring missing facts based on the known facts in Knowledge Graphs. In our experiments, we utilize FB15k-237 (Toutanova & Chen, 2015) and WN18RR (Dettmers et al., 2018) datasets for evaluation. Following Bordes et al. (2013) , we use filtered setting for evaluation and report Mean Reciprocal Rank (MRR), Mean Rank (MR) and Hits@N. • Node Classification is the task of predicting the labels of nodes in a graph based on node features and their connections. Similar to Schlichtkrull et al. (2017) , we evaluate COMPGCN on MUTAG (Node) and AM (Ristoski & Paulheim, 2016) datasets. • Graph Classification, where, given a set of graphs and their corresponding labels, the goal is to learn a representation for each graph which is fed to a classifier for prediction. We evaluate on 2 bioinformatics dataset: MUTAG (Graph) and PTC (Yanardag & Vishwanathan, 2015) .

A summary statistics of the datasets used is provided in Appendix A.2

5.2. BASELINES:

Across all tasks, we compare against the following GCN methods for relational graphs: (1) Relational-GCN (R-GCN) (Schlichtkrull et al., 2017) which uses relation-specific weight matrices that are defined as a linear combinations of a set of basis matrices.

(2) Directed-GCN (D-GCN) (Marcheggiani & Titov, 2017) has separate weight matrices for incoming edges, outgoing edges, and self-loops. It also has relation-specific biases.

(3) Weighted-GCN (W-GCN) (Shang et al., 2019) assigns a learnable scalar weight to each relation and multiplies an incoming "message" by this weight. Apart from this, we also compare with several task-specific baselines mentioned below.

Link prediction: For evaluating COMPGCN, we compare against several non-neural and neural baselines: TransE Bordes et al. (2013) , DistMult (Yang et al., 2014) , ComplEx (Trouillon et al., 2016) , R-GCN (Schlichtkrull et al., 2017) , KBGAN (Cai & Wang, 2018) , ConvE (Dettmers et al., 2018) , ConvKB (Nguyen et al., 2018) , SACN (Shang et al., 2019) , HypER (Balažević et al., 2019) , RotatE (Sun et al., 2019) , ConvR (Jiang et al., 2019) , and VR-GCN (Ye et al., 2019) .

Node and Graph Classification: For node classification, following Schlichtkrull et al. (2017) , we compare with Feat (Paulheim & Fümkranz, 2012) , WL (Shervashidze et al., 2011) , and RDF2Vec (Ristoski & Paulheim, 2016) . Finally, for graph classification, we evaluate against PACHYSAN (Niepert et al., 2016) , Deep Graph CNN (DGCNN) (Zhang et al., 2018) , and Graph Isomorphism Network (GIN) (Xu et al., 2019) .

6. RESULTS:

In this section, we attempt to answer the following questions.

Q1. How does COMPGCN perform on link prediction compared to existing methods? (6.1) Q2. What is the effect of using different GCN encoders and choice of the compositional operator in COMPGCN on link prediction performance? (6.1) Q3. Does COMPGCN scale with the number of relations in the graph? (6.3) Q4. How does COMPGCN perform on node and graph classification tasks? (6.4)

FB15k-237 WN18RR:

MRR MR H@10 H@3 H@1 MRR MR H@10 H@3 H@1 TransE (Bordes et al., 2013) . datasets. The results of all the baseline methods are taken directly from the previous papers ('-' indicates missing values). We find that COMPGCN outperforms all the existing methods on 4 out of 5 metrics on FB15k-237 and 3 out of 5 metrics on WN18RR. Please refer to Section 6.1 for more details.

6.1. PERFORMANCE COMPARISON ON LINK PREDICTION:

In this section, we evaluate the performance of COMPGCN and the baseline methods listed in Section 5.2 on link prediction task. The results on FB15k-237 and WN18RR datasets are presented in Table 3 . The scores of baseline methods are taken directly from the previous papers (Sun et al., 2019; Cai & Wang, 2018; Shang et al., 2019; Balažević et al., 2019; Jiang et al., 2019; Ye et al., 2019) . However, for ConvKB, we generate the results using the corrected evaluation code (Sun et al., 2019) . Overall, we find that COMPGCN outperforms all the existing methods in 4 out of 5 metrics on FB15k-237 and in 3 out of 5 metrics on WN18RR dataset. We note that the best performing baseline RotatE uses rotation operation in complex domain. The same operation can be utilized in a complex variant of our proposed method to improve its performance further. We defer this as future work.

6.2. COMPARISON OF DIFFERENT GCN ENCODERS ON LINK PREDICTION PERFORMANCE:

Next, we evaluate the effect of using different GCN methods as an encoder along with a representative score function (shown in Figure 2 ) from each category: TransE (translational), DistMult (semantic-based), and ConvE (neural network-based). In our results, X + M (Y) denotes that method M is used for obtaining entity embeddings (and relation embeddings in the case of COMPGCN) with X as the score function as depicted in Figure 2 . Y denotes the composition operator in the case of COMPGCN. We evaluate COMPGCN on three non-parametric composition operators inspired from TransE (Bordes et al., 2013) , DistMult (Yang et al., 2014) , and HolE (Nickel et al., 2016) defined as

• Subtraction (Sub): φ(e s , e r ) = e s -e r .

• Multiplication (Mult): φ(e s , e r ) = e s * e r .

• Circular-correlation (Corr): φ(e s , e r )=e s e r

The overall results are summarized in Effect of composition Operator: The results on link prediction with different composition operators are presented in Table 4 . We find that with DistMult score function, multiplication operator (Mult) gives the best performance while with ConvE, circular-correlation surpasses all other operators. Overall, we observe that more complex operators like circular-correlation outperform or perform comparably to simpler operators such as subtraction.

6.3. SCALABILITY OF COMPGCN:

In this section, we analyze the scalability of COMPGCN with varying numbers of relations and basis vectors. For analysis with changing number of relations, we create multiple subsets of FB15k-237 dataset by retaining triples corresponding to top-m most frequent relations, where m = {10, 25, 50, 100, 237}. For all the experiments, we use our best performing model (ConvE + COMPGCN (Corr)).

Effect of Varying Relation Basis:

Vectors: Here, we analyze the performance of COMPGCN on changing the number of relation basis vectors (B) as defined in Section 4. The results are summarized in Figure 3 . We find that our model performance improves with the increasing number of basis vectors. We note that with B = 100, the performance of the model becomes comparable to the case where all relations have their individual embeddings. In Table 4 , we report the results for the best performing model across all score function with B set to 50. We note that the parameter-efficient variant also gives a comparable performance and outperforms the baselines in all settings. Effect of Number of Relations: Next, we report the relative performance of COMPGCN using 5 relation basis vectors (B = 5) against COMPGCN, which utilizes a separate vector for each relation in the dataset. The results are presented in Figure 5 . Overall, we find that across all different numbers of relations, COMPGCN, with a limited basis, gives comparable performance to the full model. The results show that a parameter-efficient variant of COMPGCN scales with the increasing number of relations.

Comparison with R-GCN: Here, we perform a comparison of a parameter-efficient variant of COMPGCN (B = 5) against R-GCN on different number of relations. The results are depicted in Figure 4 . We observe that COMPGCN with limited parameters consistently outperforms R-GCN across all settings. Thus, COMPGCN is parameter-efficient and more effective at encoding multirelational graphs than R-GCN.

6.4. EVALUATION ON NODE AND GRAPH CLASSIFICATION:

In this section, we evaluate COMPGCN on node and graph classification tasks on datasets as described in Section 5.1. The experimental results are presented in Table 5 . For node classification task, we report accuracy on test split provided by Ristoski et al. (2016) , whereas for graph classification, following Yanardag & Vishwanathan (2015) and Xu et al. (2019) , we report the average and standard deviation of validation accuracies across the 10 folds cross-validation. Overall, we find that COMPGCN outperforms all the baseline methods on node classification and gives a comparable performance on graph classification task. This demonstrates the effectiveness of incorporating relations using COMPGCN over the existing GCN based models. On node classification, compared to the best performing baseline, we obtain an average improvement of 3% across both datasets while on graph classification, we obtain an improvement of 3% on PTC dataset.

7. CONCLUSION:

In this paper, we proposed COMPGCN, a novel Graph Convolutional based framework for multirelational graphs which leverages a variety of composition operators from Knowledge Graph embedding techniques to jointly embed nodes and relations in a graph. Our method generalizes several existing multi-relational GCN methods. Moreover, our method alleviates the problem of over-parameterization by sharing relation embeddings across layers and using basis decomposition.

Through extensive experiments on knowledge graph link prediction, node classification, and graph classification tasks, we showed the effectiveness of COMPGCN over existing GCN based methods and demonstrated its scalability with increasing number of relations.

A APPENDIX:

A.1 EVALUATION BY RELATION CATEGORY

In this section, we investigate the performance of COMPGCN on link prediction for different relation categories on FB15k-237 dataset. Following Wang et al. (2014a) ; Sun et al. (2019) , based on the average number of tails per head and heads per tail, we divide the relations into four categories: one-to-one, one-to-many, many-to-one and many-to-many. The results are summarized in Table 6 . We observe that using GCN based encoders for obtaining entity and relation embeddings helps to improve performance on all types of relations. In the case of one-to-one relations, COMPGCN gives an average improvement of around 10% on MRR compared to the best performing baseline (ConvE + W-GCN). For one-to-many, many-to-one, and many-to-many the corresponding improvements are 10.5%, 7.5%, and 4%. These results show that COMPGCN is effective at handling both simple and complex relations. (2014a) , the relations are divided into four categories: one-to-one (1-1), one-to-many (1-N), manyto-one (N-1), and many-to-many (N-N). We find that COMPGCN helps to improve performance on all types of relations compared to existing methods. Please refer to Section A.1 for more details.

A.2 DATASET DETAILS:

In this section, we provide the details of the different datasets used in the experiments. For link prediction, we use the following two datasets:

• FB15k-237 (Toutanova & Chen, 2015 ) is a pruned version of FB15k (Bordes et al., 2013) dataset with inverse relations removed to prevent direct inference. • WN18RR (Dettmers et al., 2018) , similar to FB15k-237, is a subset from WN18 (Bordes et al., 2013) dataset which is derived from WordNet (Miller, 1995) .

For node classification, similar to Schlichtkrull et al. (2017) , we evaluate on the following two datasets:

• MUTAG (Node) is a dataset from DL-Learner toolkit3 . It contains relationship between complex molecules and the task is to identify whether a molecule is carcinogenic or not. • AM dataset contains relationship between different artifacts in Amsterdam Museum (de Boer et al., 2012) . The goal is to predict the category of a given artifact based on its links and other attributes.

Finally, for graph classification, similar to Xu et al. (2019) , we evaluate on the following datasets:

• MUTAG (Graph) Debnath et al. ( 1991) is a bioinformatics dataset of 188 mutagenic aromatic and nitro compounds. The graphs need to be categorized into two classes based on their mutagenic effect on a bacterium.

:

We further analyze the best performing method for different relation categories in Appendix A.1.

http://www.dl-learner.org

Figures and Tables:

Figure 2: Knowledge Graph link prediction with COMPGCN and other methods. COMPGCN generates both entity and relation embedding as opposed to just entity embeddings for other models. For more details, please refer to Section 6.2



Table content: <table><tr><td>: Comparison of our proposed method, COMPGCN with other Graph Convolutional meth-</td></tr><tr><td>ods. Here, K denotes the number of layers in the model, d is the embedding dimension, B rep-</td></tr><tr><td>resents the number of bases and |R| indicates the total number of relations in the graph. Overall,</td></tr><tr><td>COMPGCN is most comprehensive and is more parameter efficient than methods which encode</td></tr><tr><td>relation and direction information.</td></tr><tr><td>relations, i.e.,</td></tr></table>

Reduction of COMPGCN to several existing Graph Convolutional methods. Here, α k r is a relation specific scalar, W k r denotes a separate weight for each relation, and W k dir(r) is as defined in Equation 3. Please refer to Proposition 4.1 for more details.

Table content: <table/>

Link prediction performance of COMPGCN and several recent models on FB15k-237 and WN18RR

Table content: <table><tr><td/><td>294</td><td>357</td><td>.465</td><td>-</td><td>-</td><td>.226</td><td>3384</td><td>.501</td><td>-</td><td>-</td></tr><tr><td>DistMult (Yang et al., 2014)</td><td>.241</td><td>254</td><td>.419</td><td>.263</td><td>.155</td><td>.43</td><td>5110</td><td>.49</td><td>.44</td><td>.39</td></tr><tr><td>ComplEx (Trouillon et al., 2016)</td><td>.247</td><td>339</td><td>.428</td><td>.275</td><td>.158</td><td>.44</td><td>5261</td><td>.51</td><td>.46</td><td>.41</td></tr><tr><td>R-GCN (Schlichtkrull et al., 2017)</td><td>.248</td><td>-</td><td>.417</td><td/><td>.151</td><td>-</td><td>-</td><td>-</td><td/><td>-</td></tr><tr><td>KBGAN (Cai &amp; Wang, 2018)</td><td>.278</td><td>-</td><td>.458</td><td/><td>-</td><td>.214</td><td>-</td><td>.472</td><td>-</td><td>-</td></tr><tr><td>ConvE (Dettmers et al., 2018)</td><td>.325</td><td>244</td><td>.501</td><td>.356</td><td>.237</td><td>.43</td><td>4187</td><td>.52</td><td>.44</td><td>.40</td></tr><tr><td>ConvKB (Nguyen et al., 2018)</td><td>.243</td><td>311</td><td>.421</td><td>.371</td><td>.155</td><td>.249</td><td>3324</td><td>.524</td><td>.417</td><td>.057</td></tr><tr><td>SACN (Shang et al., 2019)</td><td>.35</td><td>-</td><td>.54</td><td>.39</td><td>.26</td><td>.47</td><td>-</td><td>.54</td><td>.48</td><td>.43</td></tr><tr><td>HypER (Balažević et al., 2019)</td><td>.341</td><td>250</td><td>.520</td><td>.376</td><td>.252</td><td>.465</td><td>5798</td><td>.522</td><td>.477</td><td>.436</td></tr><tr><td>RotatE (Sun et al., 2019)</td><td>.338</td><td>177</td><td>.533</td><td>.375</td><td>.241</td><td>.476</td><td>3340</td><td>.571</td><td>.492</td><td>.428</td></tr><tr><td>ConvR (Jiang et al., 2019)</td><td>.350</td><td>-</td><td>.528</td><td>.385</td><td>.261</td><td>.475</td><td>-</td><td>.537</td><td>.489</td><td>.443</td></tr><tr><td>VR-GCN (Ye et al., 2019)</td><td>.248</td><td>-</td><td>.432</td><td>.272</td><td>.159</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>COMPGCN (Proposed Method)</td><td>.355</td><td>197</td><td>.535</td><td>.390</td><td>.264</td><td>.479</td><td>3533</td><td>.546</td><td>.494</td><td>.443</td></tr></table>

Similar toSchlichtkrull et al. (2017), we find that utilizing Graph Convolutional based method as encoder gives a substantial improvement in performance for most types of score functions. We observe that although all the baseline GCN methods lead to some degradation with TransE score function, no such behavior is observed for COMPGCN. On average, COMPGCN obtains around 6%, 4% and 3% relative increase in MRR with TransE,

Table content: <table><tr><td>Scoring Function (=X) →</td><td>TransE</td><td/><td>DistMult</td><td/><td>ConvE</td><td/></tr><tr><td>Methods ↓</td><td colspan="2">MRR MR H@10</td><td>MRR MR H@10</td><td>MRR</td><td>MR</td><td>H@10</td></tr><tr><td>X</td><td>0.294 357</td><td>0.465</td><td>0.241 354 0.419</td><td>0.325</td><td>244</td><td>0.501</td></tr><tr><td>X + D-GCN</td><td>0.299 351</td><td>0.469</td><td>0.321 225 0.497</td><td>0.344</td><td>200</td><td>0.524</td></tr><tr><td>X + R-GCN</td><td>0.281 325</td><td>0.443</td><td>0.324 230 0.499</td><td>0.342</td><td>197</td><td>0.524</td></tr><tr><td>X + W-GCN</td><td colspan="2">0.267 1520 0.444</td><td>0.324 229 0.504</td><td>0.344</td><td>201</td><td>0.525</td></tr><tr><td>X + COMPGCN (Sub)</td><td>0.335 194</td><td>0.514</td><td>0.336 231 0.513</td><td>0.352</td><td>199</td><td>0.530</td></tr><tr><td>X + COMPGCN (Mult)</td><td>0.337 233</td><td>0.515</td><td>0.338 200 0.518</td><td>0.353</td><td>216</td><td>0.532</td></tr><tr><td>X + COMPGCN (Corr)</td><td>0.336 214</td><td>0.518</td><td>0.335 227 0.514</td><td>0.355</td><td>197</td><td>0.535</td></tr><tr><td>X + COMPGCN (B = 50)</td><td>0.330 203</td><td>0.502</td><td>0.333 210 0.512</td><td>0.350</td><td>193</td><td>0.530</td></tr></table>

Performance on link prediction task evaluated on FB15k-237 dataset. X + M (Y) denotes that

Table content: <table/>

Performance comparison on node classification (Left) and graph classification (Right) tasks. * and † indicate that results are directly taken from Schlichtkrull et al. (2017) and Xu et al. (2019) respectively. Overall, we find that COMPGCN either outperforms or performs comparably compared to the existing methods. Please refer to Section 6.4 for more details.

Table content: <table><tr><td/><td/><td/><td/><td/><td>0.345</td><td/></tr><tr><td/><td>All</td><td/><td/><td/><td>0.342</td><td/><td>All</td><td>97.2</td></tr><tr><td>Number of Relations</td><td>100 50 25</td><td/><td>0.308</td><td colspan="2">0.316 0.321 0.325 0.316 0.331</td><td/><td>Number of Relations</td><td>100 50 25</td><td>100.0 100.0 99.4</td></tr><tr><td/><td>10</td><td>0.265 0.269</td><td/><td/><td colspan="2">R-GCN CompGCN (B=5)</td><td>5</td><td>99.3</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>0</td><td>25</td><td>50</td><td>75</td><td>100</td></tr><tr><td/><td>0.250</td><td>0.275</td><td>0.300</td><td/><td>0.325</td><td>0.350</td></tr><tr><td/><td/><td/><td colspan="2">Mean Reciprocal Rank</td><td/><td/><td>Relative MRR</td></tr><tr><td colspan="7">Figure 4: Comparison of COMPGCN (B = 5) with R-GCN for pruned versions of Fb15k-237 dataset containing different number of relations. COMPGCN with 5 relation basis vectors outperforms R-GCN across all setups. For more details, please refer to Sec-tion 6.3</td><td>Figure 5: Performance of COMPGCN with differ-ent number of relations on link prediction task. We report the relative change in MRR on pruned ver-sions of FB15k-237 dataset. Overall, COMPGCN gives comparable performance even with limited pa-rameters. Refer to Section 6.3 for details.</td></tr><tr><td/><td/><td colspan="3">MUTAG (Node)</td><td>AM</td><td/><td>MUTAG (Graph)</td><td>PTC</td></tr><tr><td/><td>Feat  *</td><td/><td>77.9</td><td/><td>66.7</td><td/><td>PACHYSAN  †</td><td>92.6 ± 4.2</td><td>60.0 ± 4.8</td></tr><tr><td/><td colspan="2">WL  *  RDF2Vec  *  R-GCN  *</td><td>80.9 67.2 73.2</td><td/><td>87.4 88.3 89.3</td><td/><td>DGCNN  † GIN  † R-GCN</td><td>85.8 89.4 ± 4.7 82.3 ± 9.2</td><td>58.6 64.6 ± 7.0 67.8 ± 13.2</td></tr><tr><td/><td colspan="2">SynGCN</td><td>74.8 ± 5.5</td><td/><td>86.2 ± 1.9</td><td/><td>SynGCN</td><td>79.3 ± 10.3</td><td>69.4 ± 11.5</td></tr><tr><td/><td colspan="2">WGCN</td><td>77.9 ± 3.2</td><td/><td>90.2 ± 0.9</td><td/><td>WGCN</td><td>78.9 ± 12.0</td><td>67.3 ± 12.0</td></tr><tr><td/><td colspan="2">COMPGCN</td><td>85.3 ± 1.2</td><td/><td>90.6 ± 0.2</td><td/><td>COMPGCN</td><td>89.0 ± 11.1</td><td>71.6 ± 12.0</td></tr></table>

Results on link prediction by relation category on FB15k-237 dataset. FollowingWang et al.

Table content: <table><tr><td/><td/><td>ConvE</td><td/><td colspan="2">ConvE + W-GCN</td><td colspan="2">ConvE + COMPGCN (Corr)</td></tr><tr><td/><td/><td colspan="2">MRR MR H@10</td><td colspan="2">MRR MR H@10</td><td>MRR MR</td><td>H@10</td></tr><tr><td>Head Pred</td><td>1-1 1-N N-1 N-N</td><td>0.193 459 0.068 922 0.438 123 0.246 189</td><td>0.385 0.116 0.638 0.436</td><td>0.422 238 0.093 612 0.454 101 0.261 169</td><td>0.547 0.187 0.647 0.459</td><td>0.457 150 0.112 604 0.471 99 0.275 179</td><td>0.604 0.190 0.656 0.474</td></tr><tr><td>Tail Pred</td><td>1-1 1-N N-1 N-N</td><td>0.177 402 0.756 66 0.049 783 0.369 119</td><td>0.391 0.867 0.09 0.587</td><td>0.406 319 0.771 43 0.068 747 0.385 107</td><td>0.531 0.875 0.139 0.607</td><td>0.453 193 0.779 34 0.076 792 0.395 102</td><td>0.589 0.885 0.151 0.616</td></tr></table>

Peer review (iclr2020):
In this paper, the authors developed GCN on multi-relational graphs and proposed CompGCN. In comparison with existing multi-relational GCN, CompGCN leverages insights from knowledge graph embedding and learns representations of both nodes and relations, with the aim to alleviate the problem of over-parameterization. Moreover, to improve the scalability w.r.t. the number of relations, the initial relation representations are expressed as a linear combination of a fixed number of basis vectors. In contrast to existing works, the basis vectors are only defined for initialization but not for every GCN layer. The authors also compared the proposed CompGCN with other existing GCN variants and summarized the relationships between CompGCN and other models. In the experiments, three tasks including link prediction, node classification and graph classification were performed to evaluate the performance of the proposed method. By comparing with existing methods, the effectiveness of the proposed method was demonstrated. There are several concerns on this paper. First, this work is somewhat incremental on R-GCN (*Modeling relational data with graph convolutional networks*). Although the differences were highlighted, the overall technical contribution is limited. In this paper, relation representations are learned jointly with node representations, but it is not clear on what are the benefits by doing so, or how significant the over-parameterization problem can be alleviated in this manner. Second, the experimental setup is unclear. As for the datasets, some more descriptions about the meaning of relationships and labels should be provided. As for the three different tasks, what loss functions were used for model training, how to obtain graph-level representations from node-level representations for graph classification, should be clarified. Third, in Table 2, there are some missing values of some compared methods, but it is not clear on their absence. Finally, from the results of Figure 3, it is hard to see the scalability of the proposed method w.r.t. the increasing number of relations since the variable is the number of basis. It is suggested to provide some more results to show the insights of advantages of the proposed method, such as the accuracy change w.r.t. increasing number of relations and the corresponding running time, in comparison with other methods.