Modelling Relational Data using Bayesian Clustered Tensor Factorization

Ilya Sutskever, Ruslan Salakhutdinov, Joshua B. TenenbaumNeurIPS 2009 · OpenReview

Understanding complex relational structures between various types of objects is a fundamental challenge in machine learning. When learning probabilistic models from relational data—often represented as triples like (object_a, relation_r, object_b)—researchers typically face a stark tradeoff between interpretability and predictive power.

Cluster-based models, such as the Infinite Relational Model (IRM), group objects into discrete clusters. This yields highly interpretable representations (e.g., grouping all mammals together), but these models often struggle to capture fine-grained nuances, leading to lower predictive accuracy. Conversely, factorization-based models assign continuous latent vectors to every entity. While they excel at predicting whether an unobserved relation is true, the resulting latent dimensions are usually impossible for a human to interpret.

To bridge this gap, researchers introduced the Bayesian Clustered Tensor Factorization (BCTF) model. BCTF embeds distributed representations within a nonparametric Bayesian framework, discovering meaningful groups of objects and relations while outperforming traditional models on link prediction tasks.

The BCTF Architecture

The core innovation of BCTF is how it marries tensor factorization with nonparametric clustering.

Factorization Backbone: At its foundation, the model utilizes tensor factorization. Each object $a$ is represented by two vectors: $a_L$ for its role as a "left" argument and $a_R$ for its role as a "right" argument. Each relation $r$ is represented by a matrix $R$. The probability of a relation being true is determined by the inner product $a_L^T R b_R$.

Tensor Factorization Backbone

Nonparametric Clustering: Instead of treating these latent vectors as entirely independent, BCTF employs a Chinese Restaurant Process (CRP) to partition objects and relations into clusters.

Hierarchical Priors: Each discovered cluster has its own learned mean and covariance. Objects within a cluster are sampled from this cluster-specific Gaussian distribution. This structure encourages "soft" similarity: objects in the same cluster will share similar vector representations, yet they retain enough individual identity to capture fine-grained, object-specific details.

Inference is handled via a sophisticated Markov Chain Monte Carlo (MCMC) setup, utilizing collapsed Gibbs sampling for cluster assignments and Hybrid Monte Carlo (HMC) for the relation matrices.

Key Insights and Performance

The model was rigorously evaluated across five diverse datasets: Animals, Kinship, UML, Movielens, and Conceptnet. Across the board, BCTF demonstrated that it offers the "best of both worlds," consistently achieving lower Root Mean Squared Error (RMSE) and higher Area Under the Curve (AUC) than pure clustering (IRM) and Multiple Relational Clustering (MRC).

Robustness to Sparsity: BCTF uses clusters to regularize the factorization, which proves exceptionally helpful when data is sparse. On the Conceptnet dataset—which is 99.9% sparse—standard Maximum A Posteriori (MAP) factorization fails due to massive overfitting. The fully Bayesian nature of BCTF allows it to maintain high performance, achieving an AUC of 0.94 where MAP-based approaches struggled at 0.48–0.57.

Automatic Regularization: Because it is a fully Bayesian model, BCTF handles its own regularization. This avoids the labor-intensive process of manual cross-validation required by MAP models to tune hyperparameters.

Structural Discovery and Interpretability: BCTF successfully recovers known structures without prior supervision. By visualizing the covariance of the learned vectors, the model demonstrates qualitative success, such as grouping movies into coherent genres or categorizing common-sense concepts into logical groups.

Clustering on the Animals Dataset

Limitations and Future Directions

While BCTF represents a significant step forward, the authors note a few limitations:

  • Likelihood Function: The model uses a Gaussian likelihood for binary data to facilitate easier Gibbs sampling. The authors acknowledge this is less ideal than a logistic function.
  • Computational Scaling: Although BCTF scales better than previous Bayesian relational models, sampling the relation matrices scales as $d^6$ (where $d$ is the dimensionality). This becomes computationally expensive for very high-dimensional models.
  • Vector Representation: Assigning two distinct vectors ($a_L, a_R$) per object speeds up inference but makes it harder for the model to capture "position-independent" properties of objects, particularly in highly sparse regimes.

Ultimately, BCTF successfully demonstrates that we do not have to sacrifice interpretability for predictive accuracy when modeling complex relational data.

Summary updated

Abstract

We consider the problem of learning probabilistic models for complex relational structures between various types of objects. A model can help us ``understand a dataset of relational facts in at least two ways, by finding interpretable structure in the data, and by supporting predictions, or inferences about whether particular unobserved relations are likely to be true. Often there is a tradeoff between these two aims: cluster-based models yield more easily interpretable representations, while factorization-based approaches have better predictive performance on large data sets. We introduce the Bayesian Clustered Tensor Factorization (BCTF) model, which embeds a factorized representation of relations in a nonparametric Bayesian clustering framework. Inference is fully Bayesian but scales well to large data sets. The model simultaneously discovers interpretable clusters and yields predictive performance that matches or beats previous probabilistic models for relational data.
BibTeX
@inproceedings{sutskever2009modelling,
  author = {Ilya Sutskever and Ruslan Salakhutdinov and Joshua B. Tenenbaum},
  title = {{Modelling Relational Data using Bayesian Clustered Tensor Factorization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=SkZq2_Z_Wr},
}
Figure