New heuristic approaches for maximum balanced biclique problem

The maximum balanced biclique problem (MBBP) is an important extension of the maximum clique problem (MCP), which has wide industrial applications. In this paper, we propose a new local search framework for MBBP where four heuristics are incorporated to improve its performance. Our framework alternates between an extension phase via adding vertex pairs and a restarting phase via removing vertex pairs. Three heuristics are proposed for selecting the pairs for addition and removal. The first heuristic is a prediction score function to greedily select the vertex pairs for addition, which makes use of the structural information of the problem. The second heuristic is a self-adaptive restarting heuristic that removes a dynamic number of vertex pairs from the candidate solution to allow the search to continue from a new search area. The third heuristic is proposed for solving massive graphs and is called the two-mode perturbation heuristic. It is used for selecting pairs of vertices for addition and lowers the average complexity for this task. We also introduce a k-bipartite core reduction rule to decrease the scale of all massive instances, which helps our algorithm find optimal solutions for many massive instances. These techniques lead to two efficient local search algorithms for MBBP. Experimental results demonstrate that the proposed algorithms can scale up to massive instances with billions of edges and that the proposed algorithms outperform state-of-the-art MBBP algorithms on standard benchmarks.