Hierarchical Infinite Relational Model

Feras A. Saad, Vikash K. Mansinghka

Abstract

The Hierarchical Infinite Relational Model (HIRM) is a novel probabilistic generative model designed for noisy, sparse, and heterogeneous relational data. By inferring multiple non-overlapping clusters of relations through a top-level Chinese restaurant process, HIRM allows for structural independences that standard models cannot capture. Within each relation cluster, a Dirichlet process mixture partitions domain entities to model relation value distributions. This paper presents algorithms for fully Bayesian posterior inference via Gibbs sampling and demonstrates HIRM's efficacy on density estimation benchmarks and real-world datasets in politics and genomics.

Introduction: The Challenge of Relational Data

In complex relational datasets—such as those containing users, products, and transactions—the goal is often to discover hidden clusters of entities to improve predictive accuracy. The standard approach, the Infinite Relational Model (IRM), suffers from a "one-size-fits-all" limitation. It assumes that if a domain (e.g., "Users") appears in multiple relations, it must share the exact same clustering across all of them.

This assumption often leads to "over-clustering." For example, in a geopolitical dataset, countries might group by economic ties in one context and by military alliances in another. Forcing a single global partition results in fragmented, uninformative groups. HIRM addresses this by allowing different relations to be explained by independent, context-specific partitions.

The HIRM Framework

HIRM introduces a two-level hierarchy to the clustering process to enable more flexible structure learning:

  1. Top-Level Relation Clustering: The model employs a Chinese Restaurant Process (CRP) to partition relations (tables or attributes) into non-overlapping "subsystems." This step identifies which variables are truly dependent.
  2. Subsystem-Level Entity Clustering: Within each subsystem, the model functions like a standard IRM, using another CRP to partition domain entities (e.g., genes or countries).
Comparison of IRM and HIRM partitioning strategies. HIRM (c) allows for structural independences by partitioning relations into independent subsystems, unlike the global partition of IRM (b).

Unlike the IRM, HIRM allows a domain to have a distinct partition for every subsystem it participates in. This inductive bias enables the representation of structural independences that are invisible to global models. Inference is performed using a fully Bayesian Gibbs sampling approach, including an auxiliary sampler to manage relation movement between subsystems.

Experimental Evaluation

The authors evaluated HIRM across three primary domains:

  • Object-Attribute Benchmarks: 20 diverse datasets (e.g., Netflix, MSNBC, DNA) with up to 18 million data cells.
  • Political Interactions: The "Dimensionality of Nations" dataset, featuring 15 countries and 56 binary interactions.
  • Genomics: A yeast genome dataset involving 1,243 genes across 9 domains such as "Function" and "Location."
Relational schemas for (a) political data and (b) genomics data, illustrating the complex, multi-domain relationships HIRM is designed to model.

Key Results and Insights

  • Predictive Performance: HIRM outperformed standard IRM and Dirichlet Process Mixture Models (DPMM) in 17 out of 20 benchmark cases. It also remained competitive with high-capacity deep learning models like LearnSPN, despite HIRM's greater interpretability.
  • Structural Discovery: In genomics data, HIRM successfully identified that genes might be similar in "Cellular Localization" but distinct in "Biological Class." In political data, it discovered that certain global events, like US immigration patterns, are statistically independent of other geopolitical rivalries.
  • Likelihood Gains: The discovered structure in illustrative cases was found to be orders of magnitude more likely under the posterior than the rigid structures imposed by standard IRM.

Conclusion

HIRM provides a robust framework for discovering latent structure in heterogeneous data. By breaking massive systems into independent subsystems, it achieves better fit and faster performance in many scenarios. Future work will focus on scaling these methods via variational inference and extending the subsystem logic to continuous data distributions.

Summary updated

Abstract

This paper describes the hierarchical infinite relational model (HIRM), a new probabilistic generative model for noisy, sparse, and heterogeneous relational data. Given a set of relations defined over a collection of domains, the model first infers multiple non-overlapping clusters of relations using a top-level Chinese restaurant process. Within each cluster of relations, a Dirichlet process mixture is then used to partition the domain entities and model the probability distribution of relation values. The HIRM generalizes the standard infinite relational model and can be used for a variety of data analysis tasks including dependence detection, clustering, and density estimation. We present new algorithms for fully Bayesian posterior inference via Gibbs sampling. We illustrate the efficacy of the method on a density estimation benchmark of twenty object-attribute datasets with up to 18 million cells and use it to discover relational structure in real-world datasets from politics and genomics.
BibTeX
@inproceedings{saad2021hierarchical,
  author = {Feras A. Saad and Vikash K. Mansinghka},
  title = {{Hierarchical Infinite Relational Model}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=4KN5gnXjIj},
}
Figure