Extracting hierarchical backbones from bipartite networks

Woo Seong Jo, Jaehyuk Park, Arthur Luhur, Beom Jun Kim, Yong-Yeol AhnarXiv 2020 · arXiv

Bipartite networks, which represent interactions between two distinct sets of entities (e.g., authors and keywords, or genes and biological functions), are ubiquitous in data science. While these networks are rich in information, standard analysis often involves "flattening" them into unipartite projections. This process frequently obscures the subtle hierarchical relationships—the "is-a" or "part-of" structures—inherent in the data.

Researchers from Northwestern University and Indiana University have introduced a novel framework to automatically uncover these hidden structures. Their method extracts a "hierarchical backbone" (HB) from bipartite data, transforming complex co-occurrence patterns into structured Directed Acyclic Graphs (DAGs).

Methodology: Leveraging Directional Asymmetry

The core challenge in extracting hierarchy from bipartite projections is distinguishing between simple association and directional subordination. For instance, while "Statistical Physics" and "Physics" are strongly associated, the relationship is asymmetric: most practitioners of statistical physics are physicists, but the reverse is not true.

The hierarchical backbone extraction pipeline. (a-b) Illustrating the intuition of directional asymmetry where $P(u|v) > P(v|u)$ suggests $u \to v$. (c-f) The multi-step process from initial projection to the final pruned backbone.

The proposed HB method follows a rigorous statistical pipeline:

  1. Statistical Filtering: The process begins with a one-mode projection. To filter out random noise, the researchers employ a z-score based on a hypergeometric distribution (the bipartite configuration model), identifying pairs that co-occur significantly more than expected by chance.
  2. Estimating Hierarchical Strength ($\alpha$): The central innovation is a metric, $\alpha_{u \to v}$, measuring the strength and direction of a relationship. It relies on conditional probability: if $v$ is a sub-category of $u$, then $P(u|v)$ should be significantly higher than $P(v|u)$.
  3. Weighting and Construction: The metric incorporates node degree to favor broader parent categories. By thresholding $\alpha$, the algorithm constructs a DAG.
  4. Parsimonious Pruning: Finally, redundant "shortcut" edges are removed to ensure a clean, interpretable hierarchy.

Performance and Validation

To validate the HB method, the authors used semi-synthetic benchmarks derived from the Gene Ontology (GO), a gold-standard hierarchy of biological terms. They tested the algorithm's ability to reconstruct known relationships from simulated annotation data.

Performance comparison of the HB method against baseline algorithms (Algorithm A and B). Precision-Recall and TPR-FPR curves are shown for edge and path reconstruction across various network sizes ($N$) and noise levels.

The results demonstrate that the HB method consistently outperforms existing baselines. Notably, the method is exceptionally robust to data sparsity. In real-world scenarios where data is often incomplete, the HB algorithm maintains high precision and recall, successfully capturing the "essential" backbone of the network.

Real-World Applications: From LinkedIn to Biology

The utility of the hierarchical backbone was further demonstrated across diverse datasets:

  • Professional Skill Hierarchies: Applying the method to a dataset of ~340,000 LinkedIn users in the software industry, the algorithm successfully mapped a logical skill tree. General categories like "Management" and "Software" emerged at the top, with specialized branches for "Web Development" (JavaScript, HTML) and "Systems Programming" (Linux, C++) forming naturally below.
  • Biological Discovery: When applied to real-world gene-function associations, the method not only replicated much of the manually curated Gene Ontology but also suggested potential improvements. It identified biologically valid relationships (e.g., between "ATP-binding" and "Nucleotide-binding") that were supported by co-occurrence data but missing from official records.

Conclusion

The hierarchical backbone method provides a powerful, automated tool for discovering structure in complex bipartite networks. By moving beyond simple associations to capture directional asymmetry, it offers a scalable way to build or refine ontologies in fields ranging from recruitment and labor economics to bioinformatics. As datasets continue to grow in size and complexity, such automated structural discovery will be vital for maintaining accurate and useful knowledge representations.

Reference: Jo, W. S., Park, J., Luhur, A., Kim, B. J., & Ahn, Y. Y. (2020). Extracting hierarchical backbones from bipartite networks. arXiv preprint arXiv:2002.07239v2.

Summary updated

Abstract

We propose a method for extracting hierarchical backbones from a bipartite network. Our method leverages the observation that a hierarchical relationship between two nodes in a bipartite network is often manifested as an asymmetry in the conditional probability of observing the connections to them from the other node set. Our method estimates both the importance and direction of the hierarchical relationship between a pair of nodes, thereby providing a flexible way to identify the essential part of the networks. Using semi-synthetic benchmarks, we show that our method outperforms existing methods at identifying planted hierarchy while offering more flexibility. Application of our method to empirical datasets---a bipartite network of skills and individuals as well as the network between gene products and Gene Ontology (GO) terms---demonstrates the possibility of automatically extracting or augmenting ontology from data.
BibTeX
@misc{jo2020extracting,
  author = {Woo Seong Jo and Jaehyuk Park and Arthur Luhur and Beom Jun Kim and Yong-Yeol Ahn},
  title = {{Extracting hierarchical backbones from bipartite networks}},
  year = {2020},
  eprint = {2002.07239},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.07239},
}
Figure