Abstract
Bipartite graphs are a fundamental data structure for representing relationships between two distinct sets of entities, such as objects and their properties. However, these graphs often lack an explicit hierarchical structure, making them difficult to navigate or summarize. This paper introduces a method to automatically extract taxonomies (is-a relationships) from bipartite graphs using the Minimum Description Length (MDL) principle. By treating taxonomy extraction as a compression problem, the approach identifies the most compact tree structure that explains property inheritance, providing a noise-robust alternative to traditional clustering methods.
Introduction
In many domains, data is naturally represented as a bipartite graph (e.g., Drugs $\leftrightarrow$ Properties, Documents $\leftrightarrow$ Keywords). While these graphs capture flat associations, they often hide deeper hierarchical information. For instance, knowing that a "mammal" is a type of "vertebrate" is a valuable structural insight that is typically latent in the raw data.
Existing methods for discovering these hierarchies often rely on natural language processing—which is inapplicable to raw graph data—or rigid set-coverage algorithms that are highly sensitive to noise. This work addresses these limitations by developing a robust framework that transforms flat property lists into meaningful, hierarchical taxonomies.
Methodology
The MDL Framework
The core of the proposed approach is the Minimum Description Length (MDL) principle. MDL posits that the best model for a given dataset is the one that minimizes the total description length of both the model and the data given the model. In this context, the "model" is the taxonomy tree ($T$), and the "data" is the original bipartite graph ($G$). The goal is to minimize: $$L(G, T) = L(T) + L(G|T)$$ where $L(T)$ represents the cost of describing the tree structure and $L(G|T)$ represents the cost of describing the deviations (errors) between the graph and the taxonomy.
Inheritance and Compression
The model leverages a two-way inheritance principle to achieve compression:
- Property Inheritance (Top-Down): If a parent node in the taxonomy possesses a property, all its descendants are assumed to inherit that property. This allows properties to be stored only once at the highest possible level.
- Object Inheritance (Bottom-Up): A parent concept "inherits" the set of objects associated with its children.
Optimization Algorithm
Finding the globally optimal tree is an NP-hard problem. Consequently, the authors employ a greedy heuristic algorithm. The process begins by identifying general properties (those shared by many objects) to form the upper levels of the tree. It then performs a bottom-up search for each subsequent property, placing it under the parent node that minimizes the total description cost.
Experimental Evaluation
Synthetic Benchmarks
The method was tested against synthetic datasets containing binary taxonomies with varying levels of random noise (spurious or missing edges). Accuracy was compared against MONA (Monothetic Analysis), a standard hierarchical clustering technique.
As shown in Figure 2, the MDL-based approach maintains significantly higher accuracy than MONA as noise increases. While MONA's performance degrades rapidly, the proposed method remains robust, demonstrating the effectiveness of including error costs ($L(G|T)$) in the optimization objective.
Real-World Application: DrugBank
The algorithm was applied to the DrugBank dataset, which includes 1,578 drugs and 5,000 categories. The method successfully extracted logical hierarchies without prior linguistic knowledge. For example, it identified a "DNA branch" that correctly clustered biological entities like the Varicella-Zoster Virus (VZV) and chickenpox based on their shared properties as DNA-related entities.
Conclusion
By framing taxonomy extraction as a compression task, this method provides a powerful, automated way to discover hierarchical structure in bipartite data. Its primary strengths lie in its property-centric approach—allowing objects to exist in multiple branches—and its inherent tolerance for noisy real-world data. Future work will focus on improving the heuristic search to handle extremely large-scale graphs with millions of nodes.
Summary updated