Extracting Taxonomies from Bipartite Graphs

Tobias Kötter, Stephan Günnemann, Christos Faloutsos, Michael R. Berthold

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:

  1. 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.
  2. Object Inheritance (Bottom-Up): A parent concept "inherits" the set of objects associated with its children.
Figure 1: Illustration of the transformation from a bipartite graph (left) to a hierarchical taxonomy (right) using the inheritance principle.

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.

Figure 2: Accuracy comparison between the proposed method and MONA across increasing levels of noise.

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

Abstract

Given a large bipartite graph that represents objects and their properties, how can we automatically extract semantic information that provides an overview of the data and -- at the same time -- enables us to drill down to specific parts for an in-depth analysis? In this work in-progress paper, we propose extracting a taxonomy that models the relation between the properties via an is-a hierarchy. The extracted taxonomy arranges the properties from general to specific providing different levels of abstraction.
BibTeX
@inproceedings{kotter2015extracting,
  author = {Tobias Kötter and Stephan Günnemann and Christos Faloutsos and Michael R. Berthold},
  title = {{Extracting Taxonomies from Bipartite Graphs}},
  booktitle = {The Web Conference},
  year = {2015},
  doi = {10.1145/2740908.2742753},
}
Figure