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:
- 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.
- 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).
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."
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