Identifying Maximum Defective Bicliques in Large Bipartite Graphs
Zhiyi Wang, Lijun Chang, Jeffrey Xu Yu · 2025
Finding dense subgraphs in a bipartite graph is a powerful tool for uncovering meaningful patterns and extracting valuable insights across various domains. In this paper, we relax the definition of biclique to$k$-defective biclique by allowing up-to$k$missing edges, such that larger, but still dense, substructures can be identified. Then, we propose algorithms to find the defective biclique with the largest number of vertices, which is an NP-hard problem. Nevertheless, we prove that our algorithm runs in$\mathcal{O}^{*}\left(\gamma^{n+k}\right)$time, beating the trivial$\mathcal{O}^{*}\left(2^{n}\right)$time complexity; here the$\mathcal{O}^{*}$notation hides polynomial factors,$n$is the number of vertices in the input graph$G$and$\gamma \approx 1.8393$is a constant. We further prove the diameter-three property of$k$-defective bicliques with at least$k+1$vertices on each side, and utilize it to reduce the exponent from$n+k$to$\alpha \Delta^{2}+k$where$\alpha$and$\Delta$are the degeneracy and maximum degree of$G$, respectively. Finally, we propose several practical techniques (i.e., upper bounds, reduction rules, an iterative computation framework, and finding a large initial solution) to improve the practical efficiency of our algorithm. Extensive empirical studies on real bipartite graphs are conducted to evaluate our techniques. As a by-product, our analysis techniques can also be used to prove a time complexity of$\mathcal{O}^{*}\left(\gamma^{n+k}\right)$for maximum defective clique computation in traditional unipartite graphs, improving the state-of-the-art time complexity.