Pivot-based Maximal Biclique Enumeration

Aman Abidi, Rui Zhou, Lu Chen, Chengfei LiuIJCAI 2020 · DOI

TL;DR

This paper introduces a novel algorithm, PMBE, for efficiently enumerating all maximal bicliques in bipartite graphs. By leveraging a "pivot pruning" technique and a new "rev-topological ordering" for vertex selection, PMBE significantly speeds up the process compared to existing methods, making it more scalable for large real-world datasets.

What Problem Does This Paper Address?

Bipartite graphs are powerful tools for representing relationships in various domains, from social networks to bioinformatics. A "biclique" within such a graph is a complete subgraph where all nodes in one set are connected to all nodes in the other. Identifying "maximal" bicliques – those not contained within any larger biclique – is crucial for tasks like community detection and pattern discovery. However, existing algorithms struggle with the massive search space involved, leading to inefficient enumeration and redundant results. Specifically, while pivot-based pruning is effective for general clique finding, it hasn't been effectively applied to bicliques. Furthermore, the optimal way to order vertices for biclique enumeration remains a point of contention, with existing methods incurring extra overhead.

Methods

The core of this paper is the Pivot-based Maximal Biclique Enumeration (PMBE) algorithm. PMBE builds upon existing techniques but introduces two key innovations:

  • Optimized Pivot Pruning: The authors adapt the "pivot pruning" concept, traditionally used for clique enumeration, to the biclique problem. This technique aims to reduce the search space by intelligently selecting a "pivot" vertex. If a potential biclique doesn't include the pivot or one of its neighbors, it can be pruned early. To efficiently implement this, they introduce a Containment Directed Acyclic Graph (CDAG) index structure. CDAG systematically stores containment relationships between vertices, allowing for near-constant time queries to determine if one vertex is contained within another.
  • Rev-Topological Ordering for Heuristic Pivot Selection: Recognizing that the effectiveness of pivot pruning heavily depends on the pivot choice, the paper proposes a novel heuristic. They analyze the semantics of vertex ordering and suggest a rev-topological order derived from the CDAG. This offline ordering ensures that vertices are processed in a way that maximizes the pruning power of the pivot, without introducing additional computational cost during the enumeration process itself. The algorithm selects the last vertex in this rev-topological order as the pivot.

The PMBE algorithm integrates these components: first, it constructs the CDAG and determines the rev-topological order; then, it uses this order to guide the pivot selection and pruning process for enumerating maximal bicliques.

Datasets

The authors evaluated their PMBE algorithm on ten real-world datasets from diverse domains, including:

  • Corporate Leadership
  • Unicode
  • UCforum
  • Service
  • Movielens (User-Tag and User-Movie)
  • MovieLens (Tag-Movie)
  • Wikinews (News)
  • Wikibooks (Books)

They also extended their experiments to very large datasets like GitHub and Youtube to demonstrate scalability.

Key Insights and Ideas

  • Pivot Pruning is Underutilized for Bicliques: The paper highlights that a powerful technique for general clique finding has been overlooked in the biclique domain, presenting a significant opportunity for improvement.
  • CDAG is Key to Efficient Pivot Pruning: The proposed CDAG structure is crucial for making pivot pruning practical by enabling fast containment checks.
  • Ordering Matters (A Lot): The experiments suggest that vertex ordering plays a more significant role in pruning efficiency than the pivot itself. The rev-topological order is a key enabler for PMBE's success.
  • Synergy of Techniques: Combining pivot pruning with rev-topological ordering (as in PMBE) yields superior results compared to using either technique in isolation (PMBE_pivot and PMBE_rev-top).

Key Results

The experimental results demonstrate that PMBE significantly outperforms existing state-of-the-art algorithms like iMBEA and LCM-MBC in terms of running time across various real-world datasets.

  • PMBE achieved substantial speedups, often outperforming competitors by a significant margin, especially on larger datasets.
  • The paper shows that PMBE generates fewer duplicate bicliques compared to LCM-MBC.
  • While PMBE_rev-top (using only ordering) and PMBE_pivot (using only pivot pruning) showed improvements, the combined PMBE algorithm consistently delivered the best performance.
  • The index construction time for CDAG was also reported, showing it to be a worthwhile overhead for the subsequent gains in enumeration speed.

Limitations and Future Work

  • Runtime Complexity: While PMBE is significantly faster, its theoretical time complexity remains exponential in the number of maximal bicliques (O(|V|dmaxβ)), which is inherent to the problem of enumerating all such structures.
  • Future Work: The paper suggests extending PMBE to handle larger datasets and potentially exploring parallelization for even greater efficiency. The authors also hint at further investigations into optimizing the CDAG construction and rev-topological ordering process.

Summary updated

BibTeX
@inproceedings{abidi2020pivot,
  author = {Aman Abidi and Rui Zhou and Lu Chen and Chengfei Liu},
  title = {{Pivot-based Maximal Biclique Enumeration}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/492},
}
Figure