On efficient large maximal biplex discovery

Kaiqiang Yu, Cheng Long, Deepak P, Tanmoy Chakraborty

Research output: Contribution to journalArticlepeer-review


Cohesive subgraph discovery is an important problem in bipartite graph mining. In this paper, we focus on one kind of cohesive structure, called k-biplex, where each vertex of one side is disconnected from at most k vertices of the other side. We consider the large maximal k-biplex enumeration problem which is to list all those maximal k-biplexes with the number of vertices at each side at least a non-negative integer . 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.

Original languageEnglish
Pages (from-to)824-829
Number of pages6
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number1
Early online date03 May 2021
Publication statusPublished - 01 Jan 2023


Dive into the research topics of 'On efficient large maximal biplex discovery'. Together they form a unique fingerprint.

Cite this