Out-of-Sample Representation Learning for Knowledge Graphs

Marjan Albooyeh, Rishab Goel, Seyed Mehran Kazemi

Abstract Many important problems can be formulated as reasoning in knowledge graphs. Representation learning has proved extremely effective for transductive reasoning, in which one needs to make new predictions for already observed entities. This is true for both attributed graphs (where each entity has an initial feature vector) and non-attributed graphs (where the only initial information derives from known relations with other entities). For out-of-sample reasoning, where one needs to make predictions for entities that were unseen at training time, much prior work considers attributed graphs. However, this problem is surprisingly under-explored for non-attributed graphs. In this paper, we study the out-of-sample representation learning problem for non-attributed knowledge graphs, create benchmark datasets for this task, develop several models and baselines, and provide empirical analyses and comparisons of the proposed models and baselines.

Introduction

Knowledge Graph (KG) embedding models, such as DistMult or TransE, have traditionally operated in a transductive setting. They excel at predicting missing links between entities that were present during the training phase. However, real-world KGs are dynamic; new entities—such as new products in an e-commerce graph or newly identified genes in a biological network—frequently emerge. These "out-of-sample" entities pose a significant challenge because standard models lack pre-computed embeddings for them.

While attributed KGs can leverage textual descriptions or visual features to initialize embeddings for new entities, many KGs are non-attributed. In these cases, the only information available for a "stranger" entity is its set of relationships with existing "in-sample" entities. This paper addresses the critical gap of performing inductive reasoning in such non-attributed environments.

Figure 1: Illustration of out-of-sample reasoning in a knowledge graph, where a new entity $J_{new}$ must be represented based on its relations to existing entities.

Methodology

The authors propose a framework that enables models to reason about unseen entities without retraining. This is achieved through two primary innovations: a specialized training regime and novel aggregation functions.

1. Out-of-Sample-Aware Training

The core idea is to simulate the out-of-sample scenario during the training phase. In the proposed Algorithm 2, the model does not simply look up fixed embeddings. Instead, with a probability $\psi$, it treats an existing entity as if it were out-of-sample. It "hides" the entity's embedding and forces itself to reconstruct a representation using an aggregation function based on its neighbors. This ensures that the learned embeddings and the aggregation process are mutually optimized for the inductive task.

2. Aggregation Functions

To represent a new entity $v$ using its neighbors, the authors extend the DistMult model with two aggregators:

  • oDistMult-ERAvg: This approach calculates an "ideal" vector for the new entity from each of its observed relations and then averages these vectors.
  • oDistMult-LS: This more advanced method treats the relational constraints as a system of linear equations. It employs Least Squares (LS) optimization to find the vector $z_v$ that best satisfies all neighbor relations simultaneously, providing a more robust representation in sparse settings.

Datasets

To evaluate these methods, the authors introduced two new benchmarks: oWN18RR (based on WordNet) and oFB15k-237 (based on Freebase). These datasets are specifically designed for out-of-sample tasks, ensuring that test entities have a minimum number of triples to define them to the model before their predictive performance is measured.

Key Results and Insights

The empirical evaluation revealed that the training strategy is often more impactful than the specific choice of aggregator. Using the out-of-sample-aware training (Alg 2) led to a performance increase of 16% to 28% in Mean Reciprocal Rank (MRR) on the oWN18RR dataset compared to standard transductive training.

The $\psi$ Sweet Spot

A critical finding was the role of the hyperparameter $\psi$. As shown in Figure 6(a), the best performance was achieved at $\psi \approx 0.5$. This suggests that a balanced mix of transductive and inductive training allows the model to learn high-quality base embeddings while simultaneously mastering the aggregation task.

Figure 6: (a) Impact of the out-of-sample training probability $\psi$ on performance. (b, c) Performance across different neighbor density bins for oWN18RR and oFB15k-237.

The Neighbor Paradox

Counter-intuitively, the models' performance tended to decrease as the number of neighbors for an out-of-sample entity increased (see Figure 6(b) and 6(c)). The authors hypothesize that simple averaging or least-squares methods may be susceptible to "noise" from less informative neighbors. This "neighbor paradox" highlights a limitation of current non-attentional aggregation strategies.

Conclusion and Future Work

This work demonstrates that effective out-of-sample reasoning in non-attributed KGs is possible through simulated inductive training. The proposed models, oDistMult-LS and oDistMult-ERAvg, establish new baselines for this task without compromising performance on in-sample entities. Future research will focus on incorporating attention mechanisms to better weight informative neighbors and extending the framework to temporal and hypergraph structures.

Summary updated

Abstract

Many important problems can be formulated as reasoning in knowledge graphs. Representation learning has proved extremely effective for transductive reasoning, in which one needs to make new predictions for already observed entities. This is true for both attributed graphs(where each entity has an initial feature vector) and non-attributed graphs (where the only initial information derives from known relations with other entities). For out-of-sample reasoning, where one needs to make predictions for entities that were unseen at training time, much prior work considers attributed graph. However, this problem is surprisingly under-explored for non-attributed graphs. In this paper, we study the out-of-sample representation learning problem for non-attributed knowledge graphs, create benchmark datasets for this task, develop several models and baselines, and provide empirical analyses and comparisons of the proposed models and baselines.
BibTeX
@inproceedings{albooyeh2020out,
  author = {Marjan Albooyeh and Rishab Goel and Seyed Mehran Kazemi},
  title = {{Out-of-Sample Representation Learning for Knowledge Graphs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=zXg8eXj8BJ3},
}
Figure