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:
- Combinatorial Over-clustering: To satisfy all relations at once, the model creates a massive number of tiny, spurious clusters.
- 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."
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.
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