Maximum edge bi-clique via matrix decomposition

The maximum edge bi-clique (MEB) problem is the problem of finding a bi-clique with the maximum number of edges in a bipartite graph. In this paper, we have proposed a mathematical model for MEB along with an ADMM (Alternating Direction Method of Multiplier) based algorithm. Although the constraint set of the mathematical model resembles the matrix decomposition involving the adjacency matrix of a given graph, we have included the weighted ₁-norm in the objective function. We provide an analysis showing how the weighted ₁-norm induces rapid sparsity and, therefore, faster convergence of the ADMM algorithm. In addition, we have suggested a 'natural' condition with which to identify the MEB in random graphs. We have tested our mathematical model by running the ADMM algorithm on planted bi-cliques as well as on randomly generated graphs. Numerical comparisons with a recent algorithm using planted bi-cliques have shown the superiority of our approach. The errors obtained for random graphs have shown near-exact recoveries. Finally, we have applied our algorithm to real-world bipartite graphs for which bi-cliques have been recovered successfully.