Abstract
Traditional hierarchical discovery methods often rely on rigid tree structures that fail to capture the overlapping categories inherent in real-world data. This paper presents a non-parametric Bayesian generative model that learns Directed Acyclic Graph (DAG) hierarchies for data sources and entities. By utilizing latent binary features and a containment-based rule, the model automatically identifies complex relationships and facilitates high-accuracy data enrichment.
Introduction: Beyond Tree Structures
In many data domains, objects are organized into hierarchies. For instance, a web directory might categorize restaurants by location and cuisine. However, standard machine learning approaches typically assume these hierarchies are trees, where each node has a single parent.
Real-world data is rarely so constrained. A specific restaurant might be classified as both "Italian" and "Seattle-based," effectively belonging to two parent categories. This multi-faceted nature necessitates a Directed Acyclic Graph (DAG) structure rather than a simple tree.
The challenge addressed here is learning these latent structures automatically from bipartite graphs—specifically, the containment relationships between sources (e.g., websites) and the entities they list.
Methodology
The proposed approach models the relationship between sources and entities using latent binary features.
Generative Model and Binary Features
Each source $s$ and entity $e$ is represented by a vector of binary features. For a source, a '1' indicates interest in a specific feature; for an entity, a '1' signifies possession of that feature. The core "Containment Rule" posits that a source $s$ is likely to contain an entity $e$ if $e$ possesses at least all the features that $s$ cares about. This rule induces a partial ordering that naturally forms a DAG.
Non-parametric Prior and Inference
To avoid pre-specifying the number of features, the model employs the Indian Buffet Process (IBP) as a non-parametric prior. This allows the feature space to adapt to the data's complexity. Inference is performed via Gibbs sampling. A key innovation is Collective Feature Sampling (CFS), which updates entire feature vectors simultaneously. This method significantly improves convergence speed compared to traditional one-at-a-time feature sampling, which often struggles with local optima in hierarchical spaces.
Experimental Evaluation
The model was tested on synthetic datasets designed with specific topological properties (Diamond, Star, Ring, Tree, and Flat) to evaluate its structural recovery capabilities. It was further applied to large-scale real-world data:
- YahooSmall: ~600 entities and ~21,000 websites.
- YahooBig: 700,000 restaurant listings and ~24.7 million edges.
Key Results and Impact
The model demonstrated superior performance in edge prediction tasks, consistently outperforming co-clustering and hierarchical clustering baselines. For example, in the "Star" hierarchy, the model achieved an Expected Prediction Error (EPE) of 1.3%, significantly lower than the 3.9% achieved by the best baseline.
Beyond structural discovery, the model excels at data enrichment. When applied to the massive YahooBig dataset, it inferred cuisine labels for over 50,000 previously unlabeled restaurants. Manual verification of these labels yielded an 89% accuracy rate, demonstrating the model's practical utility in cleaning and completing large-scale databases.
Conclusion
By moving from trees to DAGs and leveraging non-parametric Bayesian techniques, this model provides a flexible and powerful framework for discovering latent hierarchies. Its ability to handle multi-faceted entities and predict missing data makes it a valuable tool for organizing complex, real-world information systems. Future research may explore extending this framework to continuous features and dynamic, time-evolving hierarchies.
Summary updated