Reducing the Rank in Relational Factorization Models by Including Observable Patterns

Maximilian Nickel, Xueyan Jiang, Volker Tresp

TL;DR

This paper introduces the Additive Relational Effects (ARE) model, a hybrid approach that combines latent variable tensor factorization (like RESCAL) with observable heuristic patterns. By allowing simple rules to handle "easy" relationships, the model significantly reduces the mathematical complexity (rank) required. This leads to faster runtimes, lower memory usage, and better predictive accuracy on large knowledge graphs.

The Problem: The Rank Bottleneck

Learning from multi-relational data—such as Google’s Knowledge Graph or large-scale social networks—usually falls into two camps:

  1. Observable methods use explicit rules or heuristics (e.g., "if A is married to B, B is married to A").
  2. Latent variable methods (like tensor factorization) represent entities and relations as high-dimensional vectors to uncover hidden structures.

While tensor factorization is powerful, it suffers from a major bottleneck: rank. The rank determines how many latent features the model uses. High-rank models are more expressive but suffer from cubic scaling—doubling the rank can increase the computational cost eightfold. The authors identify a specific gap: certain simple relational patterns (like one-to-one mappings) are mathematically "expensive" for pure factorization models to represent, forcing them to use a high rank just to capture basic logic.

For example, relationships consisting of many small, strongly connected components (like a "married to" relation) theoretically require a rank equal to the number of pairs. For a million marriages, a pure factorization model would need a rank of a million, which is computationally impossible.

The Solution: Additive Relational Effects (ARE)

To solve this, the authors propose the Additive Relational Effects (ARE) model. It treats relationship prediction as a sum of two parts:

  1. The Latent Term (RESCAL): A standard tensor factorization that captures complex, hidden global structures.
  2. The Observable Term (The "Oracle"): An additive term that incorporates pre-calculated heuristics or "observable patterns" (like Common Neighbors, Katz Centrality, or Horn Clauses).

Mathematically, the model is represented as: $$X \approx \text{RESCAL}(A, R) + (M \times_3 W)$$ Where $M$ is an "oracle tensor" containing the scores from various heuristics, and $W$ is a weight matrix that learns which heuristic is most useful for which relationship.

To keep this scalable, the authors developed a specialized Alternating Least Squares (ALS) algorithm. Crucially, they found a way to update the weights without ever explicitly calculating the massive, dense tensors that usually crash memory during these operations.

Datasets

The model was evaluated on several classic and complex relational datasets:

  • Kinships: 26 types of kinship relations among 104 people in an Australian tribe.
  • Social Evolution: Data from a university dormitory tracking friendships, social media interactions, and political discussions.
  • SWRC: A Semantic Web dataset modeling a research group (people, publications, projects).
  • Cora: A large citation database where the task is to predict the topic of a paper based on its citations and authors.

Key Results

By letting the "observable" term handle logically simple but algebraically complex patterns, the "latent" term can focus on truly hidden structures. This allows the model to achieve better results with a much lower rank.

Predictive Power

Across all datasets, the hybrid ARE model consistently outperformed pure latent models (CP, Tucker, RESCAL) and pure heuristic models (MW).

Precision-Recall curves across multiple datasets showing ARE outperforming baselines.

Efficiency and Rank Compression

Because ARE offloads simple patterns to the observable term, it converges much faster and requires fewer latent dimensions. On the Cora dataset, ARE reached a higher accuracy (nDCG) in a fraction of the time it took the standard RESCAL model to finish its first iteration.

Runtime comparison on the Cora dataset between ARE and RESCAL.

Furthermore, in the Kinships dataset, ARE achieved state-of-the-art results (AUC of 96.9) with a rank of 90, whereas pure RESCAL required a rank of 100 to reach a lower performance threshold (AUC of 96).

Limitations and Future Work

While ARE solves the rank-scalability problem, it introduces a new dependency: the quality of the Oracle tensor ($M$). The model is only as good as the heuristics you feed it. If no good observable patterns are known for a specific domain, the model reverts to standard factorization.

Future directions suggested include investigating how hierarchical models or more complex sparse representations could further reduce the computational burden of modeling massive-scale knowledge bases.

Summary updated

Abstract

Tensor factorizations have become popular methods for learning from multi-relational data. In this context, the rank of a factorization is an important parameter that determines runtime as well as generalization ability. To determine conditions under which factorization is an efficient approach for learning from relational data, we derive upper and lower bounds on the rank required to recover adjacency tensors. Based on our findings, we propose a novel additive tensor factorization model for learning from latent and observable patterns in multi-relational data and present a scalable algorithm for computing the factorization. Experimentally, we show that the proposed approach does not only improve the predictive performance over pure latent variable methods but that it also reduces the required rank --- and therefore runtime and memory complexity --- significantly.
BibTeX
@inproceedings{nickel2014reducing,
  author = {Maximilian Nickel and Xueyan Jiang and Volker Tresp},
  title = {{Reducing the Rank in Relational Factorization Models by Including Observable Patterns}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure