  


A Continuous Characterization of the MaximumEdge Biclique Problem
Nicolas Gillis(nicolas.gillisuclouvain.be) Abstract: The problem of finding large complete subgraphs in bipartite graphs (that is, bicliques) is a wellknown combinatorial optimization problem referred to as the maximumedge biclique problem (MBP), and has many applications, e.g., in web community discovery, biological data analysis and text mining. In this paper, we present a new continuous characterization for MBP. Given a bipartite graph G, we are able to formulate a continuous optimization problem (namely, an approximate rankone matrix factorization problem with nonnegativity constraints, R1N for short), and show that there is a onetoone correspondence between (i) the maximum (i.e., the largest) bicliques of G and the global minima of R1N, and (ii) the maximal bicliques of G (i.e., bicliques not contained in any larger biclique) and the local minima of R1N. We also show that any stationary points of R1N must be close to a biclique of G. This allows us to design a new type of biclique finding algorithm based on the application of a blockcoordinate descent scheme to R1N. We show that this algorithm, whose algorithmic complexity per iteration is proportional to the number of edges in the graph, is guaranteed to converge to a biclique and that it performs competitively with existing methods on random graphs and text mining datasets. Finally, we show how R1N is closely related to the MotzkinStrauss formalism for cliques. Keywords: maximumedge biclique problem, biclique finding algorithm, algorithmic complexity, nonnegative rankone approximation Category 1: Combinatorial Optimization (Meta Heuristics ) Category 2: Applications  Science and Engineering (DataMining ) Citation: Accepted in the Journal of Global Optimization conditioned on minor revisions Download: [PDF] Entry Submitted: 12/20/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  