# Relational Graph Convolutional Networks: A Closer Look

Thiviyan Thanapalasingam Lucas van Berkel∗ Peter Bloem Paul Groth∗ Informatics
Institute, University of Amsterdam, 1098XH Amsterdam,The NetherlandsVrije
Universiteit Amsterdam, 1081HV Amsterdam, The Netherlands

###### Abstract

In this paper, we describe a reproduction of the Relational Graph
Convolutional Network (RGCN). Using our reproduction, we explain the intuition
behind the model. Our reproduction results empirically validate the
correctness of our implementations using benchmark Knowledge Graph datasets on
node classification and link prediction tasks. Our explanation provides a
friendly understanding of the different components of the RGCN for both users
and researchers extending the RGCN approach. Furthermore, we introduce two new
configurations of the RGCN that are more parameter efficient. The code and
datasets are available at https://github.com/thiviyanT/torch-rgcn.

##  1 Introduction

Knowledge Graphs are graph-structured knowledge bases, representing entities
and relations between pairs of entities [NMTG15]. They have become critical
for large-scale information systems for tasks ranging from question answering
to search [NGJ+19]. The ability to perform statistical relational learning
over such data enables new links, properties, and types to be inferred
[NMTG15], and performing this at a large scale is fundamental for the
advancement of the Semantic Web. Additionally, models that can be applied to
Knowledge Graphs can also be applied to Relational Database Management
Systems, because there is a one-to-one mapping between the two [BDK+13].

Relational Graph Convolution Networks (RGCNs) [SKB+18] are message passing
frameworks for learning valuable latent features of relational graphs. RGCNs
[SKB+18] have become been widely adopted for combining Knowledge Graphs with
machine learning applications111The original paper has received over 1200
citations. for their uses include Knowledge Graph refinement [Pau17], soft-
query answering [DC20], and logical reasoning [SSPH20]. The original reference
code for the RGCN is built on older platforms that are no longer supported.
Furthermore, other reproductions [WZY+19, FL19] are incomplete.222At the time
of writing, we are aware of additional implementations in PyTorch Geometric
[FL19], which reproduces only the RGCN layer, and in Deep Graph Library
[WZY+19], which provides the node classification and link prediction model.
However, they are not focused on scientific reproducibility. Existing
descriptions of the model are are mathematically dense, with little
exposition, and assume prior knowledge about geometric deep learning.

We reproduced the model in PyTorch, a widely-used framework for deep learning
[PGM+19]. Using our reproduction, we provide a thorough and friendly
description for a wider audience. The contributions of this paper are as
follows:

  1. 1.

A _reproduction of the experiments_ as described in the original paper by
Schlichtkrull _et al._ [SKB+18];

  2. 2.

A new publicly available PyTorch implementation of the model called _Torch-
RGCN_ ;

  3. 3.

A description of the _subtleties of the RGCN_ that are crucial for its
understanding, use and efficient implementation;

  4. 4.

_New configurations_ of the model that are parameter efficient.

The rest of the paper is organized as follows. We begin with an overview of
the related work in Section 2. Then, we introduce the RGCN in Section 3,
followed by a description of our reimplementation (Section 4). We then proceed
to describe the reproduction of node classification (Section 5) and link
prediction models with associated experiments (Section 6). These sections
include the model variants mentioned above. In Section 7, we discuss the
lessons learned from reproducing the original paper and the implications of
our findings. Finally, we discuss our results and conclude.

##  2 Related Work

Machine learning over Knowledge Graphs involves learning low-dimensional
continuous vector representations, called Knowledge Graph Embeddings. Here, we
briefly review relevant works in the literature.

Commonly, Knowledge Graph Embedding (KGE) models are developed and tested on
link prediction tasks. Two key examples of KGEs are TransE [BUGD+13], in which
relations are translational operations used learned to entities as low-
dimensional vectors, and DistMult [YYH+14] where the likelihood of a triple is
quantified by a multiplicative scoring function. Ruffinelli _et al._ [RBG19]
provide an overview of the most popular KGE methods and their relative
performance. The RGCN is a type of Knowledge Graphs Embedding model. However,
RGCNs are different from traditional link predictors, such as TransE and
DistMult, because RGCNs explicitly uses nodes’ neighborhood information for
learning vector representations for downstream tasks [BHB+18].

Besides RGCNs, there are other graph embedding models for relational data.
Relational Graph Attention Networks uses self-attention layers to learn
attention weights of edges in relational graphs but yields similar, or in some
cases poor, performance when compared to the RGCN. [BSCH19]. Heterogenous
Information Network (HIN) exploit meta-paths (a sequence consisting of node
types and edge types for modelling particular relationships) to low-
dimensional representation of networks [HM17]. HIN do not use message passing
and their expressivity depends on the selected meta-paths.

Beyond node classification and link prediction, RGCN’s have other practical
uses. For example, Daza _et al._ [DC20] explored RGCNs for soft query
answering by embedding queries structured as relational graphs which typically
consists of a few nodes. Recently, Hsu _et al._ shows that RGCN can be used to
extract dependency trees from natural language [GHA+21].

##  3 Relational Graph Convolutional Network

In [SKB+18], Schlichtkrull _et al._ introduced the RGCN as a convolution
operation that performs message passing on multi-relational graphs. In this
section, we are going to explain the Graph Convolutional [KW16] and how they
can be extended for relational graphs. We will describe message passing in
terms of matrix multiplications and explain the intuition behind these
operations.

###  3.1 Message Passing

Figure 1: A schematic diagram of message passing in a directed graph with 6
nodes. $\textbf{h}_{i}$ is a vector that represents the node embedding of the
node $i$ (in orange). $\textbf{h}_{i}^{(l)}$ and $\textbf{h}_{i}^{(l+1)}$ show
the node embedding before and after the message passing step, respectively.
The neighboring nodes are labelled from $a$ to $e$.

We will begin by describing the basic Graph Convolutional Network (GCN) layer
for _directed graphs_.333The original Graph Convolutional Network [KW16]
operates over undirected graphs. This will serve as the basis for the RGCN in
Section 3.2.

The GCN [KW16] is a graph-to-graph layer that takes a set of vectors
representing nodes as input, together with the structure of the graph and
generates a new collection of representations for nodes in the graph. A
directed graph is defined as $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}$ is a set of vertices (nodes) and $\langle
i,j\rangle\in\mathcal{E}$ is a set of tuples indicating the presence of
_directed_ edges, pointing from node $i$ to $j$. Equation 1 shows the message
passing rule of a _single layer_ GCN for an undirected graph, $\mathcal{G}$.

$H=\sigma\left(AXW\right),$ (1)

Here, $X$ is a node feature matrix, $W$ represents the weight parameters, and
$\sigma$ is a non-linear activation function. $A$ is a matrix computed by row-
normalizing444For undirected graphs, a symmetrically normalized Laplacian
matrix is used instead [KW16]. the adjacency matrix of the graph
$\mathcal{G}$. The row normalization ensures that the scale of the node
feature vectors do not change significantly during message passing. The node
feature matrix, $X$, indicate the presence or absence of a particular feature
on a node.

Typically, more than a single convolutional layer is required to capture the
complexity of large graphs. In these cases, the RGCN layers are stacked one
after another so that the output of the preceeding RGCN layer $H^{(l-1)}$ is
used as the input for the current layer $H^{(l)}$, as shown in Equation 2. In
our work, we will use superscript $l$ to denote the current layer.

$H^{(l)}=\sigma\left(A\;H^{(l-1)}\;W\right),$ (2)

If the data comes with a feature vector for each node, these can be used as
the input $X$ for the first layer of the model. If feature vectors are not
available, one-hot vectors, of length $N$ with the non-zero element indicating
the node index, are often used. In this case, the input $X$ becomes the
identity matrix $I$, which can then be removed from Equation 1.

We can rewrite Equation 1 to make it explicit how the node representations are
updated based on a node’s neighbors:

$\textbf{h}_{i}=\sigma\left[\sum_{x\in
N_{i}}\frac{1}{|N_{i}|}{\textbf{x}_{i}}^{T}W\right].$ (3)

Here, $\textbf{x}_{i}$ is an input vector representing node $i$,
$\textbf{h}_{i}$ is the output vector for node $i$, and $N_{i}$ is the
collection of the incoming neighbors of $i$, that is the nodes $j$ for which
there is an edge ($j$, $i$) in the graph. For simplicity, the bias term is
left out of the notation but it is usually included. We see that the GCN takes
the average of $i$’s neighbouring nodes, and then applies a weight matrix $W$
and an activation $\sigma$ to the result. Multipliying ${\textbf{x}_{i}}^{T}W$
by $\frac{1}{|N_{i}|}$ means that we sum up all the feature vectors of all
neighboring nodes. This makes every convolution layer _permutation
equivariant_ , and that is: if either the nodes (in $A$) are permuted, then
the output representations are permuted in the same way. Overall, this
operation has the effect of passing information about neighboring nodes to the
node of interest, $i$ and this called _message passing_. Message passing is
graphically represented in Figure 1 for an undirected graph, where messages
from neighboring nodes ($a-e$) are combined to generate a representation for
node $i$. After message passing, the new representation of node $i$ is a
mixture of the vector embeddings of neighboring nodes.

If a graph is sparsely connected, a single graph-convolution layer may suffice
for a given downstream task. Using more convolutional layers encourages mixing
with nodes more than 1-hop away, however it can also lead to output features
being oversmoothed [LHW18]. This is an issue as the embeddings for different
nodes may be indistinguishable from each other, which is not desirable.

In summary, GCNs perform the following two operations: 1) They replace each
node representation by the average of its neighbors, and 2) They apply a
linear layer with a nonlinear activation function $\sigma$. There are two
issues with this definition of the GCN. First, the input representation of
node $i$ does not affect the output representation, unless the graph contains
a self-loop for $i$. This is often solved by adding self-loops explicitly to
all nodes. Second, only the representations of nodes that have incoming links
to i are used in the new representation of i. In the relational setting, we
can solve both problems elegantly by adding relations to the graph which we
will describe in the next section.

###  3.2 Extending GCNs for multiple relations

In this section, we explain how the basic message passing framework can
extended to Knowledge Graphs. We define a Knowledge Graph as a directed graph
with labelled vertices and edges. Formally, a KG can be defined as
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{R})$, where $\mathcal{R}$
represents the set of edge labels (relations) and $\langle
s,r,o\rangle\in\mathcal{E}$ is a set of tuples representing that a subject
node $s$ and an object node $o$ are connected by the labelled edge
$r\in\mathcal{R}$.

The Relational Graph Convolutional Network extends graph convolutions to
Knowledge Graphs by accounting for the directions of the edges and handling
message passing for different relations separately. Equation 4 is an extension
of the regular message passing rule (Equation 1).

$H=\sigma\left(\sum_{r=1}^{R}A_{r}XW_{r}\right),$ (4)

where $R$ is the number of relations, $A_{r}$ is an adjacency matrix
describing the edge connection for a given relation $r$ and $W_{r}$ is a
relation-specific weight matrix. The extended message passing rule defines how
the information should be mixed together with neighboring nodes in a
relational graph. In the message passing step, the embedding is summed over
the different relations.555Since RGCN layers are stacked such that the input
of a layer is the ouput of the previous layer, taking the sum over $R$
actually inflats the activations. However, for two-layer networks this does
not seem to affect performance. For deeper models, taking the mean over the
relations rather than the sum may be more appropriate.

With the message passing rule discussed thus far, the problem is that for a
given triple $\langle s,r,o\rangle$ a message is passed from $s$ to $o$, but
not from $o$ to $s$. For instance, for the triple
$\langle\texttt{Amsterdam,$$located\\_in,$$The\\_Netherlands}\rangle$ it would
be desirable to update both Amsterdam with information from The_Netherlands,
and The_Netherlands with information from Amsterdam, while modelling the two
directions as meaning different things. To allow the model to pass messages in
two directions, the graph is amended inside the RGCN layer by including
inverse edges: for each existing edge $\langle s,r,o\rangle$, a new edge
$\langle o,r^{\prime},s\rangle$ is added where $r^{\prime}$ is a new relation
representing the inverse of $r$. A second problem with the naive
implementation of the (R)GCN is that the output representation for a node $i$
does not retain any of the information from the input representation. To allow
such information to be retained, a self-loop $\langle s,r_{s},s\rangle$ is
added to each node, where $r_{s}$ is a new relation that expresses identity.
Altogether, if the input graph contains $R$ relations, the amended graph
contains $2R+1$ relations:
$\mathcal{R}^{+}=\mathcal{R}\cup\mathcal{R}^{\prime}\cup\mathcal{R}_{s}$.

Figure 2: A diagram of message passing in a directed, labelled graph with 6
nodes. $\textbf{h}_{i}$ is a vector that represents the node embedding of the
node $i$ (in orange). $\textbf{h}_{i}^{(l)}$ and $\textbf{h}_{i}^{(l+1)}$ show
the node embedding before and after the message passing step, respectively.
The neighboring nodes are labelled from $a$ to $e$.

###  3.3 Reducing the number of parameters

We use $N_{in}$ and $N_{out}$ to represent the input and output dimensions of
a layer, respectively. While the GCN [KW16] requires $N_{in}\times N_{out}$
parameters, relational message passing uses $R^{+}\times N_{in}\times N_{out}$
parameters. In addition to the extra parameters required for a separate GCN
for every relation, we also face the problem that Knowledge Graphs do not
usually come with a feature vector representing each node. As a result, as we
saw in the previous section, the first layer of an RGCN model is often fed
with a one-hot vector for each node. This means that for the first layer
$N_{in}$ is equal to the number of nodes in the graph.

In their work, Schlichtkrull _et al._ introduced two different weight
regularisation techniques to improve parameter efficiency: 1) Basis
Decomposition and 2) Block Diagonal Decomposition. Figure 3 shows visually how
the two different regularisation techniques work.

Basis Decomposition does not create a separate weight matrix $W_{r}$ for every
relation. Instead, the matrices $W_{r}$ are derived as linear combinations of
a smaller set of $B$ basis matrices $V_{b}$, which is shared across all
relations. Each matrix $W_{r}$ is then a weighted sum of the basis vectors
with component weight $C_{rb}$:

$W_{r}=\sum_{b=1}^{B}C_{rb}V_{b},$ (5)

Both the component weights and the basis matrices are learnable parameters of
the model, and in total they contain fewer parameters than $W_{r}$. With lower
number of basis functions, $B$, the model will have reduced degrees of freedom
and possibly better generalisation.

Block Diagonal Decomposition creates a weight matrix for each relation,
$W_{r}$, by partitioning $W_{r}$ into $\frac{N_{in}}{B}$ by
$\frac{N_{out}}{B}$ blocks, and then fixing the off-diagonal blocks to zeros
(shown in Figure 3).666The off-diagonal blocks are $\frac{N_{in}}{B}$ by
$\frac{N_{out}}{B}$ matrices containing only zeros. In Equation 6, we present
these zeroed blocks simply with 0. This deactivates the off-diagonal blocks,
such that only the diagonal blocks are updated during training. An important
requirement for this decomposition method is that the width/height of $W_{r}$
need to be divisible by $B$.

$W_{r}=\begin{bmatrix}Q_{r1}&$\emph{0}$&\dots&$\emph{0}$\\\
$\emph{0}$&Q_{r2}&$\emph{0}$&$\emph{0}$\\\ \vdots&$\emph{0}$&\ddots&\vdots\\\
$\emph{0}$&$\emph{0}$&\dots&Q_{rB}\end{bmatrix}$ (6)

Here, $B$ represents the number of blocks that $W_{r}$ is decomposed into and
$Q_{rb}$ are the diagonal blocks containing the relation-specific weight
parameters. Equation 6 shows that taking the direct sum of $Q_{r}$ over all
the blocks gives $W_{r}$, which can also be expressed as the sum of
$\text{diag}(Q_{rb})$ over all the diagonal elements in the block matrix. The
higher the number of blocks $b$, the lower the number of trainable weight
parameters for each relation, $W_{r}$, and vice versa. Block diagonal
decomposition is not applied to the weight matrix of the identity relation
$r_{s}$, which we introduced in Section 3.2 to add self-loops to the graph.

Figure 3: A simplified visualisation of the weight regularisation methods.
Left: A weight matrix, $W_{r}$, is decomposed into 2 bases ($B=2$). Bases are
represented by a tensor $V\in\mathbb{R}^{B\times N_{in}\times N_{out}}$ and
components by matrix $C\in\mathbb{R}^{R^{+}\times B}$. Right: A different
weight matrix, $W_{r}$, is decomposed into 3 blocks ($B=3$). Blocks are
tensors
$Q_{rb}\in\mathbb{R}^{{B}\times\frac{N_{in}}{B}\times\frac{N_{out}}{B}}$.
$N_{in}$ and $N_{out}$ are the input and output dimensions of layer,
respectively.

##  4 Torch-RGCN

The original implementation of the RGCN by Schlichtkrull _et al._ was written
using two different differentiable programming frameworks (Theano 0.9
[ARAA+16] and TensorFlow 1.4 [AAB+15] 777TensorFlow 2 is not backward
compatible with TensorFlow 1 code.) both which have become obsolete in the
past two years. Therefore, we have reproduced the RGCN using PyTorch [PGM+19].
We will refer to our implementation as _Torch-RGCN_ and the original
implementation from [SKB+18] as TensorFlow-RGCN (_TF-RGCN_). Our RGCN
implementation is available at https://github.com/thiviyanT/torch-rgcn.

In this Section, we will describe how we implemented the Relational Graph
Convolutional Network. We begin by introducing crucial concepts for the
implementation.

###  4.1 Einstein Summation

Message passing requires manipulating high-dimensional matrices and tensors
using many different operations (_e.g._ transposing, summing, matrix-matrix
multiplication, tensor contraction). We will use Einstein summation to express
these operations concisely.

Einstein summation (einsum) is a notational convention for simplifying tensor
operations [Kup14]. Einsum takes two arguments: 1) an equation888We use a
notation that maps directly to the way einstein summation is used in code,
rather than the standard notation. in which characters identifying tensor
dimensions provide instructions on how the tensors should be transformed and
reshaped, and 2) a set of tensors that need to be transformed or reshaped. For
example, einsum($ik,jk\rightarrow ij,A,B$) represents the following matrix
operation:

$C_{ij}=\sum_{k}A_{ik}\cdot B_{jk},$ (7)

The general rules of an einsum operation are that indices which are excluded
from the result are summed out, and indices which are included in all terms
are treated as the batch dimension. We use einsum operations in our
implementation to simplify the message passing operations.

###  4.2 Sparsity

Since many graphs are sparsely connected, their adjacency matrices can be
efficiently stored on memory as _sparse tensors_. Sparse tensors are memory
efficient because, unlike dense tensors, sparse tensors only store non-zero
values and their indices. We make use of sparse matrix
multiplications.999Recent advances in CUDA implementations have made it
possible to perform computations involving sparse matrix multiplications to
run on the GPU. For sparse matrix operations on GPUs, the only mulitplication
operation that is commonly available is multiplication of a sparse matrix $S$
by a dense matrix $D$, resulting in a dense matrix. We will refer to this
operation as spmm($S$, $D$). For our implementation, we endeavour to express
the sparse part of the RGCN message passing operation (Equation 4), including
the sum over relations, in a single sparse matrix multiplication.

###  4.3 Stacking Trick

Using nested loops to iteratively pass messages between all neighboring nodes
in a large graph would be very inefficient. Instead, we use a trick to
efficiently perform message passing for all relations in parallel.

Edge connectivity in a relational graph is represented as a three-dimensional
adjacency tensor $A\in\mathbb{R}^{R^{+}\times N\times N}$, where $N$
represents the number of nodes and $R^{+}$ represents the number of relations.
Typically, message passing is performed using batch matrix multiplications as
shown in Equation 4. However, at the time of writing, batch matrix operations
for sparse tensors are not available in most Deep Learning libraries. Using
spmm is the only efficient operation available, so we _stack_ adjacency
matrices and implement the whole RGCN in terms of this operation.

We augment $A$ by stacking the adjacency matrices corresponding to the
different relations $A_{r}$ vertically and horizontally into
$A_{v}\in\mathbb{R}^{(N+R^{+})\times N}$ and
$A_{h}\in\mathbb{R}^{N\times(N+R^{+})}$, respectively.

$A_{v}=\left[\begin{array}[]{l}A_{1}\\\ A_{2}\\\ \ \vdots\\\ A_{1^{\prime}}\\\
A_{2^{\prime}}\\\ \ \vdots\\\ A_{s}\end{array}\right]$ (8)

$A_{h}=\left[\begin{array}[]{l}A_{1}\;A_{2}\;\cdots\;A_{1^{\prime}}\;A_{2^{\prime}}\;\cdots\;A_{s}\end{array}\right]$
(9)

Here, $\left[\cdot\right]$ represents a concatenation operation, and $A_{v}$
and $A_{h}$ are both sparse matrices. By stacking $A_{r}$ either horizontally
or vertically, we can perform message passing using sparse matrix
multiplications rather than expensive dense tensor multiplications. Thus, this
trick helps to keep the memory usage low.

Algorithm 1 shows how message passing is performed using a series of matrix
operations. All these are implementations of the same operation, but with
different complexities depending on the shape of the input.

1) If the inputs $X$ to the RGCN layer are one-hot vectors, X can be removed
from the multiplication. The featureless message passing simply multiplies $A$
with $W$, because the node feature matrix $X$ is not given. Note that $X$, in
this case, can also be modelled using an identity matrix $I$. However, since
$AW=AIW$, we skip this step to reduce computational overhead.

2) In the horizontal stacking approach, $X$ multiplied with $W$. This yields
the $XW$ tensor, which is then reshaped into a $N\mathcal{R}\times N$ matrix.
The reshaped $XW$ matrix is then multiplied with $A_{h}$ using spmm.

3) In the vertical stacking approach, the $X$ is mixed with $A_{v}$ using
spmm. The product is reshaped into a tensor of dimension $\mathcal{R}\times
N\times N$. The tensor $\mathcal{AX}$ is then multiplied with $W$.

Any dense/dense tensor operations can be efficiently implemented with einsum,
but sparse/dense operations only allow multiplication of sparse matrix by
dense matrix. Therefore, we adopt the two different stacking approaches for
memory efficiency. The vertical stacking approach is suitable for low
dimensional input and high dimensional output, because the projection to low
dimensions is done first. While the horizontal stacking approach is good for
high dimensional input and low dimensional output as the projection to high
dimension is done last. These matrix operations are visually illustrated in
Figure 4.

Figure 4:  A simplified visual representation of different message passing
approaches: (Top-Left) Featureless-message passing, (Bottom-Left) Message
passing using horizontally stacked of adjacency matrices, and (Top-Right)
Message passing using vertically stacked adjacency matrices. $\bigotimes$
indicates multiplication between dense tensors, which can be implemented with
an einsum operator.
${\color[rgb]{0.10546875,0.65234375,0.44921875}\definecolor[named]{pgfstrokecolor}{rgb}{0.10546875,0.65234375,0.44921875}\bigotimes}$
refers to sparse-by-dense multiplication, for which the spmm operation is
required. Black arrow indicates tensor reshaping.

Input: $A$, $\sigma$, [X]

Result: $H$

if  _featureless_ then

$x\Leftarrow einsum(\mlq ni,io\rightarrow no\mrq,A_{h},W)$

$H\Leftarrow\sigma\left(x\right)$

else

if  _horizontally_stacked_ then

$x\Leftarrow einsum(\mlq ni,rio\rightarrow rno\mrq,X,W)$

reshape $x$ into a matrix with the dimensions $NR^{+}\times N_{out}$

$x\Leftarrow spmm(A_{h},x)$

else

$x\Leftarrow spmm(A_{v},X)$

reshape $x$ into a tensor with the dimensions $R^{+}\times N\times N_{in}$

$x\Leftarrow einsum(\mlq rio,rni\rightarrow no\mrq,W,x)$

end if

$H\Leftarrow\sigma\left(x\right)$

end if

Algorithm 1 Message Passing Layer

Thus far, we focused on how Relational Graph Convolutional layers work and how
to implement them. As mentioned in Section 2, RGCNs can be used for many
downstream tasks. Now, we will discuss how these graph-convolutional layers
can be used as building blocks in larger neural networks to solve two
downstream tasks implemented in the original RGCN paper [SKB+18]: _node
classification_ and _link prediction_. In the next two sections, we detail the
model setup, our reproduction experiments and new configurations of the
models. We begin with node classification.

##  5 Downstream Task: Node Classification

In the node classification task, the model is trained under a _transductive
setting_ which means that the whole graph, including the nodes in the test
set, must be available during training, with only the labels in the test set
withheld. The majority of the nodes in the graph are unlabelled and the rest
of the nodes are labelled (we call these _target nodes_). The goal is to infer
the missing class information, for example, that Amsterdam belongs to the
class City.

###  5.1 Model Setup

Figure 5:  An overview of the node classification model with a two-layer RGCN.
Different colour (magenta, green, blue yellow, violet) is used to highlight
different entity types. Unlabelled entities are in grey.

Figure 5 is a diagram of the node classification model with a two-layer RGCN
as described in [SKB+18]. Full-batch training is used for training the node
classification model, meaning that the whole graph is represented in the input
adjacency matrix $A$ for the RGCN. The input is the unlabeled graph, the
output are the class predictions and the true predictions are used to train
the model. The first layer of the RGCN is ReLU activated and it embeds the
relational graph to produce low-dimensional node embeddings. The second RGCN
layer further mixes the node embeddings. Using softmax activation the second
layer generates a matrix with the class probabilities,
$Y\in\mathbb{R}^{N\times C}$, and the most probable classes are selected for
each unlabelled node in the graph. The model is trained by optimizing the
categorical cross entropy loss:

$\mathcal{L}=-\sum_{i=1}^{\mathcal{Y}}\sum_{k=1}^{K}t_{ik}\ln\textbf{h}_{ik}^{(L)},$
(10)

where $\mathcal{Y}$ is the set of labelled nodes, $K$ represents the number of
classes, $t_{ik}$ is one-hot encoded ground truth labels and
$\textbf{h}_{ik}^{(L)}$ represents node representations from the RGCN. The
last layer ($L$) of the RGCN is softmax-activated. The trained model can be
used to infer the classes of unlabelled nodes.

###  5.2 e-RGCN

In GCNs [KW16], the node features $X$ are represented by a matrix
$X\in\mathbb{R}^{N\times F}$, where $N$ is the number of nodes and $F$ is the
number of node features. When node features are not available, one-hot vectors
can be used instead. An alternative approach would be to represent the
features with continuous values $E\in\mathbb{R}^{N\times D}$, where $D$ is the
node embedding dimension.

In the GCN setting [KW16], using one hot vectors is functionally very similar
to using embedding vectors: the multiplication of the one hot vector by the
first weight matrix $W$, essentially selects a row of $W$, which then
functions as an embedding of that node. In the RGCN setting, the same holds,
but we have a separate weight matrix for each relation, so using one-hot
vectors is similar to defining a separate node embedding for each relation.
When we feed the RGCN a single node embedding for each node instead, we should
increase the embedding dimension $D$ to compensate.

Initial experiments showed that this approach slightly underperforms the one-
hot approach on the benchmark data used in [SKB+18]. After some
experimentation, we ended up with the following model, which we call the
_embedding-RGCN_ (e-RGCN). Its message passing rule is described in Equation
11. The weight matrix is restricted to a diagonal matrix (with all off
diagonal elements fixed to zero).101010This is a special case of the block
decomposition with 1x1 blocks. and then the product is multiplied by the
adjacency matrix.

$h=\sigma\left(\sum_{r=1}^{R}A_{r}\;E\;\text{diag}(\textbf{w}_{r})\right),$
(11)

Here, $E$ is the node embeddings broadcasted across all the relations
$\mathcal{R}$, $w_{r}$ is a vector containing weight parameters for relation
$r$. Here, $\text{diag}(\cdot)$ is a function that takes a vector
$L\in\mathbb{R}^{Q}$ as an input and outputs a diagonal matrix
$N\in\mathbb{R}^{Q\times Q}$, where the diagonal elements are elements from
the original vector $L$.

Using a diagonal weight matrix improves parameter efficiency, while enabling
distinction between relations. We created a new node classfication model,
where the first layer is an e-RGCN layer and the second layer is a standard
RGCN (without regularisation) that predicts class probabilities. This model
provides competitive performance with the RGCN, using only 8% of the
parameters.

###  5.3 Node Classification Experiments

All node classification models were trained following Schlichtkrull _et al._
using full-batch gradient descent for 50 epochs. However, we used 100 epochs
for e-RGCN on the AM dataset. Glorot uniform initialisation [GB10] was used to
initialise parameters with a gain of $\sqrt{2}$ corresponding to the ReLU
activation function. Kaiming initialization [HZRS15] was used to initialise
the node embeddings in the e-RGCN node classification model.111111The gain
parameter is taken from the DGL implementation [WZY+19]. The original
implementation does not appear to apply a gain. This choice does not seem to
affect the classification performance. Basis decomposition was used for the
RGCN-based node classfication.12121240 bases for the AM & BGS. 30 bases for
MUTAG. All RGCN and e-RGCN models, except for the e-RGCN on the AM dataset,
were trained using a GPU.

####  5.3.1 Datasets

We reproduce the node classification experiments using the benchmark datasets
that were used in the original paper: AIFB [BS07], MUTAG [DLdCD+91], BGS
[dV13] and AM [DBWVG+12]. We also evaluate e-RGCN on the same datasets. AIFB
is a dataset that describes a research institute in terms of its staff,
research group, and publications. AM (Amsterdam Museum) is a dataset
containing information about artifacts in the museum. MUTAG is derived as an
example dataset for the machine learning model toolkit about complex
molecules. The BGS (British Geological Survey) dataset contains information
about geological measurements in Great Britain.

Since the messages in a two-layer RGCN cannot propagate further than two hops,
we can prune away the unused nodes from the graph. This significantly reduces
the memory usuage for large datasets (BGS & AM) without any performance
deterioration. To the best of our knowledge, this was first implemented in the
DGL library [WZY+19]. For the AM and BGS datasets, the graph was pruned by
removing any nodes that are 2 hops away from the target nodes. Pruning
significantly reduces the number of entities, relations and edges and thus,
lowers the memory consumption of the node classification model, making it
feasible to train it on a GPU with 12GB of memory. Table 1 shows the
statistics for the node classification datasets. We use the same training,
validation and test split as in [SKB+18].

Table 1:  Number of entities, relations, edges and classes along with the
number of labeled entities for each of the datasets. _Labeled_ denotes the
subset of entities that have labels and _entities_ are the nodes without any
labels. (*) indicates that entities more than two hops away from the target
label were pruned.
Dataset | AIFB | MUTAG | BGS* | AM*
---|---|---|---|---
Entities | 8,285 | 23,644 | 87,688 | 246,728
Relations | 45 | 23 | 70 | 122
Edges | 29,043 | 74,227 | 230,698 | 875,946
Labeled | 176 | 340 | 146 | 1,000
Classes | 4 | 2 | 2 | 11

####  5.3.2 Results

Table 2 shows the results of the node classification experiments in comparison
to the original RGCN paper. Torch-RGCN achieves similar performances to TF-
RGCN reported in [SKB+18]. We observed that the training times of the node
classification models largely depended on the size of the graph dataset. The
CPU training times varied from 45 seconds for the AIFB dataset to 20 minutes
for the AM dataset. Since our implementation makes use of GPU’s, we were able
to run the Torch-RGCN models on a GPU and train the model within a few
minutes.

Table 2: Node classification accuracy for TF-RGCN, Torch-RGCN and e-RGCN.
Results for TF-RGCN were taken from the original paper. These are averages
over 10 runs, with standard deviations.
Dataset | Model Accuracy (%)
---|---
TF-RGCN | Torch-RGCN | e-RGCN
AIFB | 95.83 $\pm$0.62 | 95.56 $\pm$0.61 | 89.17 $\pm$0.28
AM | 89.29 $\pm$0.35 | 89.19 $\pm$0.35 | 89.04 $\pm$0.25
BGS | 83.10 $\pm$0.80 | 82.76 $\pm$0.89 | 81.72 $\pm$0.53
MUTAG | 73.23 $\pm$0.48 | 73.38 $\pm$0.60 | 71.03 $\pm$0.58

##  6 Downstream Task: Link Prediction

We now turn towards the second task performed in the original paper, multi-
relational link prediction. The aim is to learn a scoring function that
assigns true triples high scores and false triples low scores [BUGD+13], with
the correct triple ranking the highest. After training, the model can be used
to predict which missing triples might be true, or which triples in the graph
are likely to be incorrect.

###  6.1 Model Setup

Figure 6:  A schematic visualisation of link prediction models. Edges are
coloured (red and green) to indicate different edge labels. RGCN-based
encoders can be seen an extension to traditional link predictors, such as
DistMult [YYH+14] and TransE [BUGD+13]. RGCNs enrich the node representations
used by these models by mixing them along the edges of the graph, before
applying the score function. In this case, removing the RGCN layers and the
upstream edge sampling, recovers the original DistMult. In the last step, the
vectors corresponding to entities and relation are element-wise multiplied and
the product $x$ is summed. For a given triple $\langle s,r,o\rangle$, the
model produces a single scalar value $x$ which indicates how likely the triple
is to be true.

We follow the procedure outlined by Schlichtkrull _et al._ Figure 6 shows a
schematic representation of the link prediction model as described in the
original paper. During training, traditional link predictors [BUGD+13, YYH+14]
simultaneously update node representations and learn a scoring function
(decoder) that predicts the likelihood of the correct triple being true. RGCN-
based link predictors introduce additional steps upstream.

We begin by sampling 30,000 edges from the graph using an approach called
neighborhood edge sampling (see Section 6.1.2). Then, for each triple we
generate 10 negative training examples, generating a batch size of 330,000
edges in total. Node embeddings $E\in\mathbb{R}^{N\times D}$ are used an input
for the RGCN.131313In the original implementation, the embeddings are
implemented as affine operation (_i.e._ biases are included) and they are ReLU
activated. We reproduce this behaviour but it is not clear whether this gives
any benefits over simple, unactivated embeddings (as used in the e-rgcn). The
RGCN performs message passing over the sampled edges and generates mixed node
embeddings. Finally, the DistMult scoring function [YYH+14] uses the mixed
node embeddings to compute the likelihood of a link existing between a pair of
nodes. For a given triple $\langle s,r,o\rangle$, the model is trained by
scoring all potential combination of the triple using the function:

$f(s,r,o)=\sum_{i}\left(\textbf{e}_{s}\operatorname*{\text{\scalebox{0.5}{$\bigotimes$}}}\textbf{r}\operatorname*{\text{\scalebox{0.5}{$\bigotimes$}}}\textbf{e}_{o}\right)_{i}=x$
(12)

Here, $\textbf{e}_{s}$ and $\textbf{e}_{o}$ are the corresponding node
embedding of entities $s$ and $o$, generated by the RGCN encoder. r is a low-
dimensional vector of relation $r$, which is part of the DistMult decoder. As
Schlichkrull _et al._ highlighted in their work, the DistMult decoder can be
replaced by any Knowledge Graph scoring function. We refer the reader to
[RBG19] and [RBF+21] for a comprehensive survey of state-of-the-art KGE
models.

Similar to previous work on link prediction [YYH+14], the model is trained
using negative training examples. For each observed (positive) triple in the
training set, we randomly sample 10 negative triples (_i.e._ we use a negative
sampling rate of 10). These samples are produced by randomly corrupting either
the subject or the object of the positive example (the probability of
corrupting the subject is 50%). Binary cross entropy loss141414Schlichtkrull
_et al._ multiply their loss by $\frac{1}{(1+\omega)|\hat{\mathcal{E}}|}$.
$\omega$ is the negative sampling rate and $|\hat{\mathcal{E}}|$ is the number
of edges sampled. We leave this term out of our implementation, because it is
a constant and thus it would not affect the training. is used as the
optimization objective to push the model to score observable triples higher
than the negative ones:

$\begin{array}[]{r}\mathcal{L}=-\sum_{(s,r,o,y)\in\mathcal{T}}y\log
l(f(s,r,o))+(1-y)\log(1-l(f(s,r,o))),\end{array}$ (13)

where $\mathcal{T}$ is the total set of positive and negative triples, $l$ is
the logistic sigmoid function, and $y$ is an indicator set to $y=1$ for
positive triples and $y=0$ for negative triples. $f(s,r,o)$ includes entity
embeddings from the RGCN encoder and relations embeddings from the DistMult
decoder.

####  6.1.1 Edge Dropout

In their work, Schlickrull _et al._ [SKB+18] apply edge dropout to the link
prediction model which acts as an additional regularisation method. This
involves randomly selecting edges and removing them from a graph. As described
in Section 3, for every edge in the graph inverse edges $A_{r^{\prime}}$ and
self-loops $A_{s}$ are added within the RGCN layer. Dropping edges after this
step poses a potential data leakage issue because inverse edges and self-loops
of dropped edges will be included in the message passing step and thus,
invalidate the model performance. To circumvent this issue, edges are dropped
from a graph before feeding it into the RGCN.

Edge dropout is applied such that the dropout rates on the self-loops
$\mathcal{R}_{s}$ are lower than for the data edges $\mathcal{R}$ and inverse
edges $\mathcal{R}^{\prime}$. One way to think about this that this ensures
that the message from a node to itself is prioritised over incoming messages
from neighboring nodes. In our implementation, we separate out $A_{s}$ from
$A$ and then apply the different edge dropout rates separately. The edge
dropout is performed before row-wise normalising $A$.

####  6.1.2 Edge Sampling

Graph batching is required for training the RGCN-based link prediction model,
because it is computationally expensive to perform message passing over the
entire graph due to the large number of hidden units used for the
RGCN.151515Schlichtkrull _et al._ use a large number of hidden units: 200 for
FB15k and WN18; 500 for FB15k-237. In the node classification fewer hidden
units are required in the RGCN. This makes the link prediction model more
memory demanding.

Schlichtkrull _et al._ sample an edge with the probability proportional to its
weight. In _uniform edge sampling_ , equal weights are given to all the edges.
However, in _neighborhood edge sampling_ , initial weights are proportional to
the node degrees of vertices connected to edges. Then as edges are being
sampled, the weight of its neighboring edges is increased and this increases
the probability of these edges being sampled [KW18]. This sampling approach
benefits link prediction because the neighboring edges provide context
information to deduce the existence of a relation between a given pair of
entities. In contrast, uniform edge sampling assumes that all edges are
independent of each other, which is not be applicable to Knowledge Graphs.

###  6.2 Link Prediction Experiments

As in the original paper, the models are evaluated using Mean Reciprocal Rank
(MRR) and Hits@$k$ ($k$ = 1, 3 or 10). The Torch-RGCN model was trained for
7,000 epochs. We monitored the training of our models by evaluating it at
regular intervals every 500 epochs. Schlichtkrull initialisation (_see
Appendix_) was used to initialise all parameters in the link prediction models
[SKB+18] and in our reproductions. Schlichtkrull _et al._ [SKB+18] trained
their models on the CPU. Our Torch-RGCN implementation and c-RGCN models run
on the GPU. Early stopping was not used. We used the hyperparameters described
in [SKB+18].

####  6.2.1 Datasets

To evaluate link prediction, Schlichtkrull _et al._ used subsets of Freebase
(FB-15k and FB15k-237)[SKB+18], and WordNet (WN18) [BUGD+13]. We only use WN18
161616The link prediction model was expensive to train (3-5 days of training
for a single model). WN18 was sufficient to establish reproduction.. WN18 is a
subset of WordNet the graph which describes the lexical relations between
words. To check our reproduction, we also used FB-Toy [RBG19] which was not in
the original paper. FB-Toy is a dataset consisting of a subset of FB15k. In
Table 3, we show the statistics corresponding to these graph datasets.

####  6.2.2 Details

For link prediction, a single-layer RGCN with basis decomposition for WN18 and
for FB-Toy a two-layer RGCN with block diagonal decomposition is used. An
$\mathcal{L}2$ regularisation penalty of 0.01 for the scoring function is
applied. To compute the _filtered_ link prediction scores, triples that occur
in the training, validation and test are filtered. The Torch-RGCN model is
trained on WN18 using batched training, in which 30,000 neighboring edges are
sampled at every epoch. An edge dropout rate of 0.2 is applied for self-loops
and 0.5 for data edges and inverse edges. Edges are randomly sampled from a
Knowledge Graph using the _neighborhood edge_ approach. In our reproduction
attempts, we have found that this approach enables the model to perform better
than uniform edge sampling. The RGCN is initialised using Schlichtkrull normal
initialisation (_see Appendix_), while the DistMult scoring function is
initialised using standard normal initialisation.

We follow the standard protocol for link prediction. See [RBG19] for more
details. Some of the hyperparameters used in training were not detailed in
[SKB+18]. To the furthest extent possible, we followed the same training
regime as the original paper and code base, and we recovered missing
hyperparameters. The hyperparameters for all experiments are provided in
documented configuration files on https://github.com/thiviyanT/torch-rgcn.

Table 3:  Number of entities and relation types along with the number of edges
per split for the three datasets.
Dataset | WN18 | FB-Toy
---|---|---
Entities | 40,943 | 280
Relations | 18 | 112
Train edges | 141,442 | 4565
Val. edges | 5,000 | 109
Test edges | 5,000 | 152

####  6.2.3 Results

We verify the _correctness_ of our implementation by reproducing the
performance on a small dataset (FB-Toy) and by comparing the statistics of
various intermediate tensors in the implementation with those of the reference
implementation.171717https://github.com/MichSchli/RelationPrediction We
selected a number of intermediate tensors in the link prediction model in our
implementation and the original implementation. Then, we measured the
statistics of the intermediate tensors. In Table 4 we report the statistics of
the intermediate tensors for TF-RGCN (original model) and Torch-RGCN (our
implementation) link prediction models. These results suggests that the
parameters used by both models came from a similar distribution and thus
verified that they are one-to-one replication.

Table 4:  Parameter statistics for intermediate products at various points in
link prediction model for the FB-Toy dataset. We report the minimum, maximum,
mean and the standard deviation of the distributions. ($\dagger$) Schlichkrull
_et al._ used separate weight matrices for data edges $\mathcal{R}$ and
inverse edges $\mathcal{R}^{\prime}$, resulting in two intermediate tensors
with the dimensions $112\times 100\times 5\times 5$. Thus, we report the
statistics for these two tensors.

No. | Intermediate Tensors | Tensor Dimensions |  | Parameter Statistics
---|---|---|---|---
| TF-RGCN | Torch-RGCN
1 | Node Embeddings: Initialisation | $280\times 500$ | min | -0.45209 | -0.48939
max | 0.45702 | 0.48641
mean | $-0.00004$ | $0.00029$
std | $0.10697$ | $0.10765$
2 | Node Embeddings: Output | $280\times 500$ | min | $0.0$ | $0.0$
max | $0.47124$ | $0.51221$
mean | $0.04318$ | $0.04290$
std | $0.06301$ | $0.06273$
3 | RGCN Layer 1: Block Initialisation for data edges and inverse edges $\dagger$ | $224\times 100\times 5\times 5$ | min | -1.38892 & -1.20551 | -1.28504
max | 1.47686 & 1.3872786 | 1.26404
mean | 0.00007 & -0.00008 | $0.00001$
std | 0.27726 & 0.27692 | $0.27715$
4 | RGCN Layer 1: Block Initialisation for self-loops | $500\times 500$ | min | -1.23380 | -1.20324
max | 1.30949 | 1.16375
mean | $-0.00049$ | $-0.00095$
std | $0.27716$ | $0.27755$
5 | RGCN Layer 1: Output | $280\times 500$ | min | $-2.58617$ | $-2.75152$
max | $2.43774$ | $2.63124$
mean | $0.02317$ | $0.00799$
std | $0.51760$ | $0.53759$
6 | DistMult: Relation Initialisation | $112\times 500$ | min | -4.12359 | -3.97444
max | 4.89700 | 3.95794
mean | $-0.00947$ | $-0.00186$
std | $0.99675$ | $0.99851$
7 | DistMult: Output | $3300\times 1$ | min | $-27.21030$ | -30.75097
max | $27.0885849$ | $25.89389$
mean | $0.03524$ | $0.78507$
std | $7.75823$ | $7.27595$

After confirming that our reproduction is correct, we attempted to replicate
the link prediction results on the WN18 dataset.181818Runs on FB15k and
FB15k-237 took from three to five days to complete training. Table 5 also
shows the results of the link prediction experiments carried out. The scores
obtained by the Torch-RGCN implementation is lower than that of the TF-RGCN
model and therefore, we were unable to duplicate the exact results reported in
the original paper [SKB+18]. We believe that the discrepancies between the
scores is caused by the differences in the hyperparameter configurations. The
exact hyperparameters that Schlichtkrull _et al._ used in their experiments
were not available.

Table 5: Mean Reciprocal Rank (MRR) and Hits@k (k=1, 3 and 10) for link
prediction using RGCN, Torch-RGCN and c-RGCN (see Section 6.3). Triples from
the truth set (train, validation and test set) have been filtered. Results for
TF-RGCN was taken from the original paper.
Dataset | Model | MRR | Hits@1 | Hits@3 | Hits@10
---|---|---|---|---|---
WN18 | TF-RGCN | 0.814 | 0.686 | 0.928 | 0.955
Torch-RGCN | 0.749 | 0.590 | 0.908 | 0.939
c-RGCN | 0.717 | 0.558 | 0.867 | 0.933

Despite our best efforts, we were unable to reproduce the exact link
prediction results reported in the original paper [SKB+18]. This is due to the
multitude of hyperparameters191919There are at least 10 non-trivial
hyperparameters: Number of Epochs, Learning Rate, Graph Batch Size, Negative
Sampling Rate, Number of RGCN layers, Dimension of RGCN layers, Weight
Decomposition Method, Number of Blocks or number of basis functions, Edge
Dropout Rate, $\mathcal{L}2$ regularisation penalty for the scoring function.,
not all of which are specified in the paper, and the long time required to
train the model, with runtimes of several days. We did however manage to show
the correctness of our implementation using a small-scale experiment. We
consider this an acceptable limitation of our reproduction, because the
current training time of the RGCN, compared to the state-of-the-art KGE models
[RBG19]. A Distmult embedding model can be trained in well under an hour on
any of the standard benchmarks, and as shown in [RBG19], outperforms the RGCN
by a considerable margin. Thus, the precise link prediction architecture
described in [SKB+18] is less relevant in the research landscape.

###  6.3 c-RGCN

Figure 7:  A schematic visualisation of c-RGCN based link prediction model.
Here, the encoder has a bottleneck architecture. $f_{\theta}$ and $g_{\phi}$
are linear layers. Prior to message passing $f_{\theta}$ compresses the input
node embeddings, and then $g_{\phi}$ projects the mixed node embeddings back
up to their original dimensions. The red arrow indicates the residual
connection. All edges from the training set are used (_i.e._ edge sampling is
not required).

The link prediction architecture presented in [SKB+18] does not represent a
realistic competitor for the state of the art and is very costly to use on
large graphs. Furthermore, a problem with the original RGCN link predictor
[SKB+18] is that we need high dimensional node representations to be
competitive with traditional link predictors, such as DistMult [YYH+14], but
the RGCN is expensive for high dimensions. However, we do believe that the
basic idea of message passing is worth exploring further in a link prediction
setting.

To show that there is promise in this direction, we offer a simplified link
prediction architecture that uses a fraction of the parameters of the original
implementation [SKB+18] uses. This variant places a bottleneck architecture
around the RGCN in the link prediction model, such that the embedding matrix
$E$ is projected down to a lower dimension, $C$, and then the RGCN performs
message propagation using the compressed node embeddings. Finally, the output
is projected up back to the original dimension, $D$, and computes the DistMult
score from the resulting high-dimensional node representations. We call this
encoding network the _compression-RGCN_ (c-RGCN). Equations 14 and 15 show the
message passing rule for the first and second layer of the c-RGCN encoder,
respectively. We selected a node embedding size of 128 and compressed it to a
vector dimension of 16. We also include a residual connection by including $E$
in the second layer of the c-RGCN. The residual connection allows the model,
in principle, to revert back to DistMult if the message passing adds no value.
If all RGCN weights are set to 0, we recover the original DistMult.

$H^{1}=\sigma\left(\sum_{r=1}^{R^{+}}A\;W_{r}\;f_{\theta}(E)\right),$ (14)

where $f(X)=XW_{\theta}+b$ with $W_{\theta}\in\mathbb{R}^{C\times E}$.

$H^{2}=E+g_{\phi}\left(\sigma\left(\sum_{r=1}^{R^{+}}A\;W_{r}\;H^{1}\right)\right),$
(15)

where $g(X)=XW_{\phi}+b$ with $W_{\phi}\in\mathbb{R}^{E\times C}$.

As shown in Table 5, the c-RGCN does not perform much worse than the original
implementation. However, it is much faster, and memory efficient enough for
full batch evaluation on the GPU. There is a clear trade-off between
compression size of the node embeddings and the performance in link
prediction. While this result is far from a state-of-the-art model, it serves
as a proof-of-concept that there may be ways to configure RGCN models for a
better performance/efficiency tradeoff.

##  7 Discussion

We now discuss the implications for the use of the RGCN model, the performance
of the new variants and the lessons learned from this reproduction.

###  7.1 Implications for RGCN usage

We believe that Relational Graph Convolutional Networks are still very
relevant because it is one of the simplest members of the message passing
models and is good starting place for exploration of machine learning for
Knowledge Graphs.

RGCNs clearly perform well on node classification tasks because the task of
classifying nodes benefits from message passing. This means that a class for a
particular node is selected by reasoning about the classes of neighboring
nodes. For example, a researcher can be categorised into a research domain by
reasoning about information regarding their research group and close
collaborators. Traditional Knowledge Graph Embeddings (KGE) models, such as
TransE and DistMult, lack the ability to perform node classification.

While the RGCN is a promising framework, in its current setting we found that
the link prediction model proposed by Schlichtkrull _et al._ is not
competitive with current state-of-the-art [RBG19] and the model is too
expensive with considerably lower performance. In our paper, we clarify that
RGCN-based link predictors are extensions of KGE models [RBG19], thus training
RGCN to predict links will always be more expensive than using a state-of-the-
art KGE model. RGCN-based link predictor take several days to train, while
state-of-the-art relation models run in well under an hour [RBG19].

To aid the usage of RGCN, we presented two new configurations of the RGCN:

e-RGCN. We propose a new variant of the node classification model which uses
significantly less parameters by exploiting a diagonal weight matrix. Our
results show that it performs competitively with the model from [SKB+18].

c-RGCN. We also present a proof-of-concept model that performs message passing
over compressed graph inputs and thus, improves the parameter efficiency for
link prediction. The c-RGCN has several advantages over the regular RGCN link
predictor: 1) c-RGCN does not require sampling edges, because it is able to
process the entire graph in full-batch, 2) c-RGCN takes a fraction of the time
it takes to train an RGCN link predictor, 3) c-RGCN uses fewer parameters, and
4) It is straightforward to implement. Although the results for the c-RGCN are
not as strong, this sets a path for further development towards efficient
message models for relational graphs.

###  7.2 Reproduction

Evolving technologies pose several challenges for the reproducibilty of
research artifacts. This includes frequent updates being made to existing
frameworks, such as PyTorch and TensorFlow, often breaking backward
compatibility. We were in a strong position to execute this reproduction: 1)
an author of this paper also worked on the original paper, 2) we contacted one
of the lead authors of this paper who was very responsive and 3) we were able
to run the original source code 202020https://github.com/tkipf/relational-gcn
& https://github.com/MichSchli/RelationPrediction inside a virtual
environment. Nevertheless, we found it considerably challenging to make a
complete reproduction. To explain why and to contribute to avoiding such
situations in the future, we briefly outline the lessons we have learned
during the reproduction.

Parameter Statistics. There were discrepancies between the description of the
link prediction model in [SKB+18] and the source code. The source code
reproduces the values similar to the MRR scores reported in [SKB+18]. Thus, to
reproduce the results we had to perform a deep investigation of the source
code. Using the original source, we relied on comparing the parameter
statistics and tensor sizes at various points in both models. Since these
statistics are helpful to verify the correctness of an implementation, we
believe this is a useful practice in aiding reproduction. For complex models
with long runtimes, an overview of descriptive statistics of parameter and
output tensors for the first forward pass can help to check implementation
without running full experiments. We are publishing statistics for
intermediate products that we obtained for the link prediction models (see
Table 4).

Small dataset. We found that the link prediction datasets used by [SKB+18]
were large and thus, impractical for debugging RGCN because it is costly to
train them on large graphs. Using a smaller dataset (FB-Toy [SKB+18]) would
enable quicker testing with less memory consumption. Thus, we report link
prediction results on the FB-Toy dataset [RBG19] (Table 7).

Training times. The training times were variable and strongly depended on the
size of the graph, the number of relations and the number of epochs.
Schlichtkrull _et al._ reported the computational complexity, but not
practical training times. It turns out that this is an important source of
uncertainty in verifying whether re-implementations are correct. We measured
the runtimes, which includes training the model and using the pre-trained
model for making inference. For 7000 epochs, the link prediction runtimes for
Torch-RGCN and c-RGCN on the WN18 dataset are 2407 and 53 minutes,
respectively. Node classification experiments took a few minutes to complete,
because they only required 50-100 epochs. We encourage authors to report such
concrete training times.

Hyperparameter Search. We found that hyperparameters reflect the complexity of
the individual datasets. For example, AIFB, the smallest dataset, was not
prone to overfitting. Whereas, the larger AM dateset required basis
decomposition and needs a reduced hidden layer size. For link prediction, we
were unable to identify the optimum hyperparameters for WN18, FB15k and
FB15k-237 due to the sheer size of the hyperparameter space and long training
times. We provide a detailed list of hyperparameter we use in our
reproduction. While this is becoming more common in the literature, this
serves as further evidence of the importance of this detailed hyperparameter
reporting.

Other factors. We still faced the common challenges in software reproduction
that others have long noted [FvEP+13], including missing dependencies,
outdated source code, and changing libraries. An additional challenge with
machine learning models is that hardware (e.g. GPUs) now also can impact the
performance of the model itself. For instance, while we were able to run the
original link prediction code in TensorFlow 1.4, the models no longer seemed
to benefit from the available modern GPUs. Authors should be mindful that even
if legacy code remains executable for a long time, executing it efficiently on
modern hardware may stop being possible much sooner. Here too, reporting
results on small-scale experiments can help to test reproductions without the
benefit of hardware acceleration.

##  8 Conclusion

We have presented a reproduction of Relational Graph Convolutional Networks
and, using the reproduction, we provide a friendly explanation of how message
passing works. While message passing is evidently useful for node
classification, our findings also show that RGCN-based link predictors are
currently too costly to make for a practical alternative to the state-of-the-
art. However, we believe that improving the parameter efficiency RGCNs could
potentially make it more accessible. We present two novel configurations of
the RGCN: 1) e-RGCN, which introduces node embeddings into the RGCN using
fewer parameters than the original RGCN implementation, and 2) c-RGCN, a
proof-of-concept model which compresses node embeddings and thus speeds up
link prediction. These configurations provide the foundation for future work.
We believe that the techniques proposed in this paper may also be important
for others implementing other message passing models. Lastly, our new
implementation of RGCN using PyTorch, TorchRGCN, is made openly available to
the community. We hope that this can help serve the community in the use,
development and research of this interesting model for machine learning on
Knowledge Graphs.

## Acknowledgement

We are very grateful to Michael Schlichtkrull for supporting us with the
reproduction of the link prediction results. Experiments were run on DAS-5
ASCI Supercomputer [BEdL+16] and on the Dutch national e-infrastructure with
the support of SURF Cooperative.

## References

  * [AAB+15] Martín Abadi, Ashish Agarwal, Paul Barham, et al., _TensorFlow: Large-scale machine learning on heterogeneous systems_ , 2015, Software available from tensorflow.org.
  * [ARAA+16] Rami Al-Rfou, Guillaume Alain, Amjad Almahairi, Christof Angermueller, Dzmitry Bahdanau, Nicolas Ballas, Frédéric Bastien, Justin Bayer, Anatoly Belikov, Alexander Belopolsky, et al., _Theano: A python framework for fast computation of mathematical expressions_ , arXiv (2016), arXiv–1605.
  * [BDK+13] Mihaela A Bornea, Julian Dolby, Anastasios Kementsietsidis, Kavitha Srinivas, Patrick Dantressangle, Octavian Udrea, and Bishwaranjan Bhattacharjee, _Building an efficient rdf store over a relational database_ , Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013, pp. 121–132.
  * [BEdL+16] Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff, _A medium-scale distributed system for computer science research: Infrastructure for the long term_ , Computer 49 (2016), no. 5, 54–63.
  * [BHB+18] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al., _Relational inductive biases, deep learning, and graph networks_ , arXiv preprint arXiv:1806.01261 (2018).
  * [BS07] Stephan Bloehdorn and York Sure, _Kernel methods for mining instance data in ontologies_ , The Semantic Web, Springer, 2007, pp. 58–71.
  * [BSCH19] Dan Busbridge, Dane Sherburn, Pietro Cavallo, and Nils Y Hammerla, _Relational graph attention networks_ , arXiv preprint arXiv:1904.05811 (2019).
  * [BUGD+13] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko, _Translating embeddings for modeling multi-relational data_ , Advances in neural information processing systems, 2013, pp. 2787–2795.
  * [DBWVG+12] Victor De Boer, Jan Wielemaker, Judith Van Gent, Michiel Hildebrand, Antoine Isaac, Jacco Van Ossenbruggen, and Guus Schreiber, _Supporting linked data production for cultural heritage institutes: the amsterdam museum case study_ , Extended Semantic Web Conference, Springer, 2012, pp. 733–747.
  * [DC20] Daniel Daza and Michael Cochez, _Message passing query embedding_ , 2020.
  * [DLdCD+91] Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch, _Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity_ , Journal of medicinal chemistry 34 (1991), no. 2, 786–797.
  * [dV13] Gerben KD de Vries, _A fast approximation of the weisfeiler-lehman graph kernel for rdf data_ , Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, 2013, pp. 606–621.
  * [FL19] Matthias Fey and Jan Eric Lenssen, _Fast graph representation learning with pytorch geometric_ , 2019.
  * [FvEP+13] Antske Fokkens, Marieke van Erp, Marten Postma, Ted Pedersen, Piek Vossen, and Nuno Freire, _Offspring from reproduction problems: What replication failure teaches us_ , Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, August 2013, pp. 1691–1701.
  * [GB10] Xavier Glorot and Yoshua Bengio, _Understanding the difficulty of training deep feedforward neural networks_ , Proceedings of the thirteenth international conference on artificial intelligence and statistics, 2010, pp. 249–256.
  * [GHA+21] Xiao Guo, I Hsu, Wael AbdAlmageed, Premkumar Natarajan, Nanyun Peng, et al., _Mrgcn: Mirror graph convolution network for relation extraction with long-term dependencies_ , arXiv preprint arXiv:2101.00124 (2021).
  * [HM17] Zhipeng Huang and Nikos Mamoulis, _Heterogeneous information network embedding for meta path based proximity_ , arXiv preprint arXiv:1701.05291 (2017).
  * [HZRS15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun, _Delving deep into rectifiers: Surpassing human-level performance on imagenet classification_ , Proceedings of the IEEE international conference on computer vision, 2015, pp. 1026–1034.
  * [KB14] Diederik P Kingma and Jimmy Ba, _Adam: A method for stochastic optimization_ , arXiv preprint arXiv:1412.6980 (2014).
  * [Kup14] L.P. Kuptsov, _Einstein rule_ , http://encyclopediaofmath.org/index.php?title=Einstein_rule&oldid=32064, 2014, [Online; accessed 18-June-2021].
  * [KW16] Thomas N Kipf and Max Welling, _Semi-supervised classification with graph convolutional networks_ , arXiv preprint arXiv:1609.02907 (2016).
  * [KW18] Jason M Klusowski and Yihong Wu, _Counting motifs with graph sampling_ , Conference On Learning Theory, PMLR, 2018, pp. 1966–2011.
  * [LHW18] Qimai Li, Zhichao Han, and Xiao-Ming Wu, _Deeper insights into graph convolutional networks for semi-supervised learning_ , Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
  * [NGJ+19] Natasha Noy, Yuqing Gao, Anshu Jain, Anant Narayanan, Alan Patterson, and Jamie Taylor, _Industry-scale knowledge graphs: lessons and challenges_ , Queue 17 (2019), no. 2, 48–75.
  * [NMTG15] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich, _A review of relational machine learning for knowledge graphs_ , Proceedings of the IEEE 104 (2015), no. 1, 11–33.
  * [Pau17] Heiko Paulheim, _Knowledge graph refinement: A survey of approaches and evaluation methods_ , Semantic web 8 (2017), no. 3, 489–508.
  * [PGM+19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al., _Pytorch: An imperative style, high-performance deep learning library_ , Advances in neural information processing systems, 2019, pp. 8026–8037.
  * [RBF+21] Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo, _Knowledge graph embedding for link prediction: A comparative analysis_ , ACM Transactions on Knowledge Discovery from Data (TKDD) 15 (2021), no. 2, 1–49.
  * [RBG19] Daniel Ruffinelli, Samuel Broscheit, and Rainer Gemulla, _You can teach an old dog new tricks! on training knowledge graph embeddings_ , International Conference on Learning Representations, 2019.
  * [SKB+18] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, _Modeling relational data with graph convolutional networks_ , European Semantic Web Conference, Springer, 2018, pp. 593–607.
  * [SSPH20] Koustuv Sinha, Shagun Sodhani, Joelle Pineau, and William L. Hamilton, _Evaluating logical generalization in graph neural networks_ , 2020.
  * [WZY+19] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang, _Deep graph library: A graph-centric, highly-performant package for graph neural networks_ , arXiv preprint arXiv:1909.01315 (2019).
  * [YYH+14] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng, _Embedding entities and relations for learning and inference in knowledge bases_ , arXiv preprint arXiv:1412.6575 (2014).

## Appendix

### Notation

We use lowercase letters to denote scalars (_e.g._ $x$), bold lowercase
letters for vectors (_e.g._ w), uppercase letters for matrices (_e.g._ $A$),
and caligraphic letters for sets (_e.g._ $\mathcal{G}$). We also use uppercase
letters for referring to dimensions and lowercase letters for indexing over
those dimensions (_e.g._ $\sum_{b=1}^{B}$).

### General Experimental Setup

All experiments were performed on a single-node machine with an Intel(R)
Xeon(R) Gold 5118 (2.30GHz, 12 cores) CPU and 64GB of RAM. GPU experiments
used a Nvidia GeForce GTX 1080 Ti GPU. We used the Adam optimiser [KB14] with
a learning rate of 0.01. For reproducibility, we provide an extension
description of the hyperparameters that we have used in node classifications
and link predictions in YAML files under the _configs_ directory on the
project GitHub page: https://github.com/thiviyanT/torch-rgcn.

We ran the original implementation of the link prediction model
212121https://github.com/MichSchli/RelationPrediction on the FB15-237 dataset.
The exact hyperparameters for WN18 and FB15k experiments were not available in
the original codebase. We used Tensorflow 1.4, Theano 1.0.5 and CUDA 8.0.44.
This replication required a Nvidia Titan RTX GPU with 24GB of GPU memory, but
model training and inference was performed on the CPU.

### Schlichtkrull Initialisation

The initialization used in the link prediction models in [SKB+18] differs
slightly from the more standard Glorot initialization [GB10].

$std=\Phi\times\frac{3}{\sqrt{\text{fan in}+\text{fan out}}},$ (16)

Here, gain ($\Phi$) is a constant that is used to scale the standard deviation
according the applied non-linearity. $std$ is used to sample random points
from either a standard normal or uniform distribution. We refer to this scheme
as _Schlichtkrull initialisation_. When gain is not required, $\Phi$ is set to
$1.0$.

### FB-Toy Link Prediction

We also performed link prediction experiment on the FB-Toy dataset. The mean
and standard error of the link prediction results are reported in Table 6.

Table 6: Mean and Standard Error of Mean Reciprocal Rank (MRR) and Hits@k
(k=1, 3 and 10) over 10 runs for link prediction using RGCN and Torch-RGCN on
FB-Toy dataset. Triples from the truth set (train, validation and test set)
have been filtered. All models that were trained on the GPU.
Dataset | Model | MRR | Hits@1 | Hits@3 | Hits@10
---|---|---|---|---|---
FB15k-Toy | TF-RGCN | $0.432\pm 0.008$ | $0.293\pm 0.007$ | $0.482\pm 0.011$ | $0.768\pm 0.010$
Torch-RGCN | $0.486\pm 0.009$ | $0.352\pm 0.011$ | $0.540\pm 0.009$ | $0.799\pm 0.008$