2025/06/19 by Cui, Donghang, Li, Ronghua, Dai, Qiangqiang +2
Computer Science · #Advanced Graph Neural Networks #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2506.16121
openalex publication_date 2025/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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αkn), where αk < 2. We further enhance this framework by incorporating a novel pivoting technique, reducing the worst-case time complexity to O(mβkn), 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 10 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.