Potential Energy (PE) between 2 bodies with mass, refers to the relative gravitational pull between them. Analogously, in the context of a graph, nodes can thought of as objects where a) the product of the degrees of nodes acts as a proxy for mass, b) the clustering coeficients of common neighbours as a proxy for gravitational acceleration, and c) the inverse of the shortest distance between nodes as a proxy for distance in space, which allows for PE calculation as introduced in prior work. In this work, we are investigating the efects of incorporating PE in Link Prediction (LP) with Relational Graph Convolutional Networks (R-GCN). Specifically, we explore the benefits of including PE calculation as an informative prior to the LP task and in a follow-up experiment as a learnable feature to predict. We performed several experiments and show that considering PE in the LP process has certain advantages and find that the information PE provides was not captured by the embeddings produced by the R-GCN.
Nowadays, Knowledge Graphs (KGs) are widely used in a variety of diferent fields [
Traditional LP employed topological features of graphs to predict edges between nodes that are not present, yet are true. More recently proposed LP approaches employ advancements in Machine Learning and specifically in the area of Graph Neural Networks to learn latent representations for entities and relations in a graph. These representations are then used to perform the LP task. However, there are cases where the underlying topological features of the graph get lost in the transition to vector space in the form of multi-dimensional embeddings.
Potential Energy in graphs, as introduced by Kumar and Sharma [
In this work, we evaluate PE as an additional signal for performing LP in a co-authorship
network. We further investigate whether PE can be predicted by the vanilla R-GCN architecture
[
We consider link prediction (recovering of missing triples) in a transductive setting, as our task.
Missing pieces of information in graphs can be predicted using the neighborhood information
of nodes. For example, knowing that Michael works with a person with whom Wouter works
as well, implies that it is likely that the triple (Michael, friend_with, Wouter) belongs to the
Knowledge Graph. Our link prediction model follows the work of Schlichtkrull et al. [
The Relational Graph Convolutional Network (R-GCN) is Graph Neural Network that operates on relational data. This means that the data is a graph with directed typed edges. The update for layer + 1 and node is: ℎ (+1) = ︃( ∑︁ ∑︁ ∈ℛ ∈ 1 , ()ℎ () + 0()ℎ() , )︃ (1) where denotes the set of neighbor indices of node under relation ∈ ℛ of incoming edges of type to node , is the weight matrix of relation type , and 0 the weight matrix used to sure the next update of a node retains the information from the . , is the number previous state (simulating a self loop). This update accumulates feature vectors of neighbors via a normalized sum after performing a relation specific transformation. Executing the neural network means evaluating Equation (1) for each node in the graph, for each layer (sequentially). Rosaline Michael
VU Amsterdam Triply
Rosaline Michael
VU Amsterdam
Triply
Link prediction is the task in which we predict either missing edges in the graph, when the
graph is static, or potential future links that need to be added when the graph is dynamic.
Formally, let = (, ℰ , ℛ) be our graph with vertices , edges ℰ , and relation types ℛ, which
we assume to be complete. Then, given an incomplete set of edges, ^ℰ , the objective is to assign
scores to potential existing edges (, , ) in order to determine how likely they are to belong
to ℰ . Following [
The nodes at the first layer of the R-GCN can be initialized with features. We initialize them
with a feature vector which represents the textual information we have available about the
node. To do this, we encode string attributes with a pre-trained BERT model [
1This representation is a diagonal matrix and learnt separately from the representations in the R-GCN.
2.2. Potential Energy
In this work, we want to see the efect of including a topological feature as additional information
for the link prediction of the R-GCN. We chose the Potential Energy (PE) as introduced by Kumar
and Sharma [
1 c) (,) , the inverse of the length of the shortest distance (path) between the nodes.
In this definition we assume that if there is no path between two nodes, (, ) = +∞, and hence the potential energy becomes zero.
In this paper, we do not work with a bipartite graph, but rather a Knowledge Graph = (, ℰ , ℛ), as defined in Section 2.1.1. Hence, we have to (re-)define what Potential Energy means. We make the following modifications, when computing : 1. We only have one set of nodes, and hence the nodes , ∈ . 2. To compute the shortest path, we ignore the relation types and regard the graph as undirected.
Otherwise, we use the PE formula as stated above. In a Knowledge Graph, if the nodes are in disconnected components, their PE is zero. We illustrate the PE in Figure 1.
We evaluate our model on a Knowledge Graph with scholarly data; namely the IOS LD Connect Scholarly Knowledge Graph3. All the metadata about the papers are serialized and published as Linked Data following the bibliographic ontology4 and is accessible through a SPARQL endpoint5.
2In that work, the authors do not combine this measure with a learning approach. 3http://ld.iospress.nl 4http://bibliontology.com/#sec-sioc-rdf 5http://ld.iospress.nl:3030 DistMult R-GCN α DistMult R-GCN
PE
Regression
Loss
MLP R-GCN α
R-GCN DistMult
MLP Dense Layer
Dense Layer
Dense Layer
Dense Layer
Input Vanilla R-GCN
Input eR-GCN
Input PE Estimator
Input eR-GCN-MLP
Preprocessing. As a first data cleaning step, we removed all triples related to geometrical information. Then, we gather nodes relevant for co-authorship link prediction; namely entities of the following types with their respective textual attributes: authors with their full name, articles with their title and keywords, and afiliations with their names. Then, we extract the relations which link authors to the papers they wrote, co-authors of a specific paper to each other, and authors to their afiliations. In parallel, we merged nodes if there were multiple nodes representing the same entity, for example two nodes for the exact same author, as indicated by the owl:sameAs relation. The resulting graph has 17748 edges, which we split in 65% (13330) for training, 20% (2525) for validation and 15% (1893) for testing.
To investigate whether the potential energy is beneficial to link prediction with an R-GCN, we modify the decoder part of our architecture to incorporate the potential energy between the nodes. We perform two experiments. In both, we initially train the R-GCN with the link prediction objective, see Vanilla R-GCN on the far left side of Figure 2. eR-GCN. For the first experiment, we incorporate the potential energy into the decoder by taking a linear combination of the output of the original decoder and the calculated potential energy amongst the specific pair of nodes in the triple, as such: + , (, , ) = (1 − ) (3)
We then optimize the parameter via the link prediction objective. The reason behind these experiments lies in what we would like to observe. First of all, our goal is to showcase whether PE improves the LP task and quantify said improvement. Hence, we would like to observe the behaviour of the parameter and specifically whether post-training it is greater than zero. If that is the case, it implies that PE as a metric holds valuable information for the LP task, that either the R-GCN or the DistMult decoder failed to capture. We refer to the resulting model as energized R-GCN or eR-GCN. eR-GCN-MLP. In order to deduce whether it is solely the DistMult decoder which is unable to decode the PE information, or whether it is an inherent weakness to the R-GCN, we setup a second experiment. In the first stage of this experiment, we train a MLP which estimates the potential energy from the embeddings created by the R-GCN, see PE Estimator in Figure 2. The hypothesis is that if the embeddings contain the topological information necessary to predict PE, then the MLP should be able to estimate it (the MLP is a universal function approximator). We then utilise the output of the MLP to replace the actual computation of the PE and again observe both the performance and the value of , see eR-GCN-MLP in Figure 2. If the value of is similarly high compared to the first experiment, then this is a sign that a diferent decoder would be able to capture the information contained in the PE. If is lower, then this means that the topological information contained in the PE calculation is not captured by the embeddings.
The pre-trained BERT embeddings used have a dimension of 768, which is too computationally expensive for our model to use, so we employed an MLP to reduce the dimensions to 64. This is then also the input dimension of the nodes of our 3-layer R-GCN. On the first hidden layer, the dimension is 14, the second and the output layer have a dimension of 32. In the R-GCN we made use of basis decomposition, with 2 bases. The internal dimensions and number of bases were optimized using a hyper-parameter search on the vanilla R-GCN , and then kept the same for the other experiments. We used Adam as an optimizer for 300 epochs and a learning rate of 0.01. Regarding the training objectives, the link prediction models are all trained using the cross-entropy loss while for training the regression model to predict the PE, we employ the L1 loss (we also experimented with L2 loss, with comparable results).
Negative Sampling. Link prediction models are trained on both positive and negative samples. In the context of KGs, every triple that exists in the graph is considered true. However, negative triples are not present. Hence, in order to train our model we generated negative samples by corrupting the subject or object of existing triples. We did this corruption by replacing the head or tail of an existing triple, with another entity from the graph sampled uniform at random. In every split, we included one negative triple for every positive one. 3.4. Results
Model R-GCN eR-GCN eR-GCN-MLP
Training loss
Validation AUC-ROC
Test AUC-ROC
Scaling factor ( )
The results obtained for the two baseline and the two experiments are in Table 1. These are the mean and standard deviations of the training loss, validation and test accuracy and scaling factor over 30 runs.
Baseline. As a baseline of our experiments, we compare against the standard R-GCN version for link prediction without the enhanced DistMult decoder. The results of this model are on the ifrst row on Table 1, denoted by R-GCN. We introduce and compare the baseline against two variants of our introduced eR-GCN model. eR-GCN. The first experiment utilises the pre-calculated PE as an additional feature for performing LP. The parameter remains trainable, allowing for further insights on the trade-of between utilising and not utilising PE. We observe that that the eR-GCN the scaling factor is relatively large, meaning that the potential energy is incorporated, and provides useful information which the standard decoder cannot capture. eR-GCN-MLP The second experiment employs an additional MLP to perform a regression task over the PE. Intuitively, we would like to see whether the latent node representations retain some original graph topological features, by trying to predict the PE from them. We observe that the scaling factor becomes zero, meaning that it does not contribute positively to the predictive power of the model and thus the information provided by the potential energy was not captured in the embeddings which the R-GCN gave when trained with the DistMult objective.
eR-GCN and Link Prediction. Our encoder-decoder model approach to LP is based on
DistMult in the decoder [
We have introduced the energized relational graph convolutional network (eR-GCN) and investigated the impact of employing Potential Energy between nodes as an enriching factor in LP. Furthermore, our findings suggest that the vanilla R-GCN architecture cannot capture PE, at least not when trained with a DistMult decoder. Moreover, enriching the factorization model with the PE metric proved valuable for the link prediction task, yielding a small improvement of the AUC-ROC over the R-GCN baseline.
There are several ways in which our work could be extended. First, we can probe into adding more layers or residual connections to the R-GCN, aiming to increase its generalization power towards topological graph features, such as the PE. Additionally, we would like to investigate if the lack in ability for R-GCNs to capture PE, is true for other topological features of the graph. Lastly, in order to solidify our findings further, it would be necessary to run more extensive experimentation using a wider selection of datasets, to measure the efect of the properties of the graph on the reported improvements. Finally, a detailed theoretical analysis of the GNN used in our experiments could provide further insights on why the network is unable to capture the Potential Energy. Besides, there might be other GNN architectures which can capture complex topological features, such as PE, of the graph. Further investigation should be carried out to determine whether this is only a restriction of the R-GCN specifically.
We would like to thank Wouter Beek and Rosaline de Haan from Triply, Amsterdam and Peter Bloem from the Vrije Universiteit Amsterdam, for the interesting discussions on this work and their overall support. The work presented here overlaps with the thesis of the first author.