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.
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.
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