A Critical Examination of RESCAL for Completion of Knowledge Bases with Transitive Relations

Pushpendre Rastogi, Benjamin Van DurmearXiv 2016 · OpenReview

TL;DR

This paper critically examines the RESCAL knowledge graph embedding model, demonstrating through theoretical analysis and empirical validation that it fundamentally struggles to represent asymmetric transitive relations. This limitation is crucial because such relations (like "is-a" or "part-of") are common and important in real-world knowledge bases, and RESCAL's inability to capture them can lead to incorrect inferences.

What Problem Does This Paper Address?

Knowledge bases (KBs) like Freebase and YAGO2 are essential for many Natural Language Processing (NLP) tasks, providing structured information about entities and their relationships. However, these KBs are often incomplete, necessitating "link prediction" or "knowledge base completion" techniques to infer missing facts. While many models have shown high empirical performance, there's a lack of theoretical understanding about why they succeed or fail, especially concerning the properties of the knowledge base itself. This paper focuses on RESCAL, a popular embedding-based method, and investigates its limitations, particularly with respect to transitive and asymmetric relations, which are common in KBs (e.g., "Fluffy is-a Dog" and "Dog is-a Animal" implies "Fluffy is-a Animal").

Methods

The authors employ a two-pronged approach:

  1. Theoretical Analysis: They mathematically analyze RESCAL's scoring function, which uses entity embeddings (vectors) and relation embeddings (matrices). They derive a condition under which RESCAL could represent transitive relations. By proving that any matrix satisfying this condition must be symmetric, they demonstrate that RESCAL cannot encode asymmetric transitive relations. This is formalized in Theorem 1, which states that every transitive matrix is symmetric.
  2. Empirical Validation: They design experiments using both simulated data (a binary tree with transitive closure) and a real-world dataset (WordNet's hyponymy hierarchy). They train RESCAL under different settings (full dataset vs. subset) and evaluate its performance on various subsets of edges, including reversed edges (Erev), to specifically test their hypothesis about asymmetric relation failures.

Datasets

  • Simulated Data: A complete, balanced, rooted, directed binary tree of depth 11, augmented with its transitive closure. This dataset allowed for controlled experiments with known transitive properties.
  • WordNet: The hyponymy hierarchy of the "living_thing" synset was extracted. This provided a real-world KB with inherent transitive and asymmetric relationships.

Key Insights and Ideas

  • RESCAL's Symmetry Constraint: The core insight is that RESCAL's mathematical formulation, when applied to transitive relations, inherently leads to symmetric relation matrices. This means if RESCAL learns "A is-a B," it will also infer "B is-a A," which is incorrect for asymmetric relations.
  • The Importance of KB Properties: The paper highlights that understanding the inherent properties of a knowledge base (like transitivity and symmetry) is crucial for selecting and evaluating appropriate models.
  • Failure on Reversed Edges: The empirical results strongly support the theoretical findings, showing significantly lower accuracy on reversed edges (Erev) when dealing with asymmetric transitive relations, a failure mode that standard evaluation protocols might miss.
  • Dimensionality vs. KB Size: Performance degrades as the number of entities increases, especially with fixed embedding dimensionality, suggesting scalability issues for RESCAL in large KBs.

Key Results

  • Theoretical Proof: RESCAL cannot encode asymmetric transitive relations due to the symmetric nature of transitive matrices derived from its scoring function.
  • Simulated Data:
    • Accuracy on reversed edges (Erev) was significantly lower than on forward edges (E) when RESCAL was tested on its ability to infer transitive relations.
  • Performance degraded as the number of entities (V) increased, while dimensionality (d) had a positive impact.
  • WordNet Data: Similar trends were observed, with lower accuracy on Erev, confirming the model's struggle with the asymmetric hyponymy relation. For example, with V=16413 and d=50, accuracy on Erev was only 58% in the FullSet setting.

Limitations and Future Work

  • Strong Assumptions: The theoretical analysis relies on the assumption that the constraint of transitivity holds over all vectors in the vector space, which might be a simplification for finite KBs. The authors acknowledge that an asymmetric matrix could potentially work for a finite set of deductions.
  • Evaluation Protocol: The paper points out that standard evaluation methods (splitting into train/test sets) might mask the specific failure mode of RESCAL on reversed edges, especially when dealing with transitive relations.
  • Future Work: The authors suggest that their approach of analyzing KB properties and their impact on model performance can be extended to analyze other KBC methods. They also imply the need for models that can explicitly handle asymmetric transitive relations.

Summary updated

Abstract

Link prediction in large knowledge graphs has received a lot of attention recently because of its importance for inferring missing relations and for completing and improving noisily extracted knowledge graphs. Over the years a number of machine learning researchers have presented various models for predicting the presence of missing relations in a knowledge base. Although all the previous methods are presented with empirical results that show high performance on select datasets, there is almost no previous work on understanding the connection between properties of a knowledge base and the performance of a model. In this paper we analyze the RESCAL method and prove that it can not encode asymmetric transitive relations in knowledge bases.
BibTeX
@misc{rastogi2016critical,
  author = {Pushpendre Rastogi and Benjamin Van Durme},
  title = {{A Critical Examination of RESCAL for Completion of Knowledge Bases with Transitive Relations}},
  year = {2016},
  eprint = {1605.04672},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.04672},
}
Figure