Maximum Defective Biclique Search in Large Bipartite Graphs

The problem of identifying the maximum edge biclique in bipartite graphs has attracted considerable attention in bipartite graph analysis, with numerous real-world applications such as fraud detection, community detection, and online recommendation systems. However, real-world graphs may contain noise or incomplete information, leading to overly restrictive conditions when employing the biclique model. To mitigate this, we focus on a new relaxed subgraph model, called the k -defective biclique, which allows for up to k missing edges compared to the biclique model. We investigate the problem of finding the maximum edge k -defective biclique in a bipartite graph, and prove that the problem is NP-hard. To tackle this computation challenge, we propose a novel algorithm based on a new branch-and-bound framework, which achieves a worst-case time complexity of O (

mα n k

), where

α k <

2. We further enhance this framework by incorporating a novel pivoting technique, reducing the worst-case time complexity to

O(mβ n k )

, where

β k < α k .

To improve the efficiency, we develop a series of optimization techniques, including graph reduction methods, novel upper bounds, and a heuristic approach. Extensive experiments on 11 large real-world datasets validate the efficiency and effectiveness of the proposed approaches. The results indicate that our algorithms consistently outperform state-of-the-art algorithms, offering up to 1000× speedups across various parameter settings.