Ensemble approaches for Link Prediction

A knowledge graph G is a triple (V, R, E), where V is a set of vertices representing entities, R is a set of relations, and E is a set of labelled edges representing relationships between entities, that is, E ⊆ V × R × V. Knowledge graphs are typically stored using the W3C standard RDF (Resource Description Framework) [1], which models graphs as sets of triples (h, r, t) where head entity and tail entity h, t ∈ V and relation r ∈ R.

A relevant problem for knowledge graphs is predicting unknown triples based on known ones. Knowledge graph embedding (KGE) is a prominent approach for link prediction by scoring the plausibility of links in the vector space. To perform link prediction, KGEs [3, 8 , 9] map entities h and t and relations r into elements h, r, and t in low-dimensional vector space, and score the plausibility of a link (h, r, t) using a score function on h, r, and t.
Combining the scores of different KGE models [6, 11, 10], or of several runs of the same KGE model [12], demonstrated to improve the performance of link prediction with KGE. The single models used in such approaches are executed on the entire graph G. On the other end, ensemble methods like bagging and random forests, have demonstrated that the combination of weak learners, executed on a subset of the original data, results in a stronger one.

Bagging [4] fit different base models to different randomly sampled versions of the data to encourage different models to make diverse predictions. Random forest [5] extends the previous method by randomly subsampling features in addition to data points to differentiate the base models even more. In both cases, the final prediction is given by the aggregation of the predictions made by the base models. However, to the best of our knowledge, the idea underlying ensemble models, to derive scores on subsets of datasets, was never applied to link prediction with KGE. In this thesis, you will re-use the underlying idea of bagging and random forest and translate it into an ensemble of KGE embeddings. In link prediction settings, the vertices V constitute the data points, while the features are the relations R.  Thus, the bagging setting can be reproduced by subsampling the vertices of the graph G, while the random forest can be reproduced by subsampling both the vertices and the relations. Using the KGEmb framework, you will:
1. Subsample the entities and/or the relations of the original graph G;
2. Run a KGE model (e.g. TransE) on each subsampled graph;
3. Aggregate the scores provided by each model to compute the final score

Finally, you will obtain the random forest and the bagging version of TransE, respectively TransE_rand and TransE_bagg. Given the advantages of ensemble models, we conjecture that TransE_rand and TransE_bagg will outperform the original version of TransE.
You will evaluate the methods with link prediction tasks on standard benchmarks like WN18RR [3], FB15k-237 [2] and YAGO3-10 [7].