On Efficient Large Maximal Biplex Discovery

Cohesive subgraph discovery is an important problem in bipartite graph mining. In this paper, we focus on one kind of cohesive structure, called $k$k-biplex, where each vertex of one side is disconnected from at most $k$k vertices of the other side. We consider the large maximal $k$k-biplex enumeration problem which is to list all those maximal $k$k-biplexes with the number of vertices at each side at least a non-negative integer $\theta$theta. This formulation, we observe, has various applications and targets to find non-redundant results by excluding non-maximal ones. Existing approaches suffer from massive redundant computations and can only run on small and moderate datasets. Towards improving scalability, we propose an efficient tree-based algorithm with two advanced strategies and powerful pruning techniques. Experimental results on real and synthetic datasets show the superiority of our algorithm over existing approaches.

Automated summary

In this paper, we address the problem of cohesive subgraph discovery in bipartite graph mining, focusing on the $k$-biplex structure. We propose an efficient tree-based algorithm with advanced strategies and pruning techniques to solve the large maximal $k$-biplex enumeration problem. Experimental results demonstrate the superiority of our algorithm over existing approaches in terms of scalability and performance on both real and synthetic datasets.