Hierarchical infinite relational model

Feras A. Saad, Vikash K. Mansinghka

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.

Introduction

Relational data—information about how entities like people, genes, or countries interact—is notoriously difficult to model because of its inherent complexity and interconnectedness. A popular tool for this is the Infinite Relational Model (IRM), which clusters entities based on their relational patterns. However, the IRM suffers from a significant "inductive bias" flaw: it assumes that each domain has exactly one global clustering that explains every relation it participates in.

The Problem: Combinatorial Over-clustering

When modeling a country's trade, alliances, and human rights records simultaneously, the IRM forces a single master partition to explain all three. This leads to two primary issues:

  1. Combinatorial Over-clustering: To satisfy all relations at once, the model creates a massive number of tiny, spurious clusters.
  2. Rigidity: It fails to recognize that an entity might belong to one group in a "trade context" but a completely different group in a "military context."

The HIRM Approach

The Hierarchical Infinite Relational Model (HIRM) addresses these limitations by adding a layer of hierarchy to the standard IRM. Instead of modeling all relations together, the HIRM uses a Chinese Restaurant Process (CRP) to partition the relations themselves into non-overlapping blocks or "subsystems."

Comparison of standard IRM and HIRM. IRM (b) forces a single global partition, while HIRM (c) discovers independent subsystems.

Within each subsystem, the model runs a standard IRM, meaning each subsystem gets its own private set of entity clusterings. This Bayesian nonparametric approach allows the model to infer the number of subsystems and clusters directly from the data.

Experimental Evaluation

The HIRM was evaluated across three diverse settings:

  • Object-Attribute Benchmarks: 20 standard datasets (e.g., NLTCS, Netflix, DNA) with up to 18 million data cells.
  • Political Interactions: The "Dimensionality of Nations" dataset, featuring 15 countries and 56 different types of interactions.
  • Genomics: A yeast genome dataset containing 9 domains and over 1,200 unique gene identifiers.
Relational schemas for the Country and Gene datasets used in the evaluation.

Key Insights and Results

The HIRM's core strength is the discovery that entities have multiple identities. In yeast genome data, genes cluster differently depending on whether the focus is Localization or Class. Furthermore, the model can identify Structural Independence; for example, finding that "Geopolitical Blocs" are statistically independent of "Economy and Culture" in political data.

On the 20-dataset benchmark, HIRM significantly outperformed the standard IRM and Dirichlet Process Mixture Models (DPMM) in 17 out of 20 cases. It also achieved results comparable to specialized deep learning models like Sum-Product Networks (SPNs), despite being a more interpretable Bayesian model. Qualitatively, in the political data, the HIRM correctly identified the USA as a statistical outlier in "Student/Immigrant exchange" while simultaneously placing it in standard clusters for "Geopolitical Rivalry."

Conclusion

By breaking complex systems into independent subsystems, the HIRM avoids the "cluster explosion" seen in standard models, leading to better generalization and more succinct representations. Future work may explore allowing overlapping memberships for relations and improving computational efficiency for massive datasets through variational inference.

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