Maximal Similar-Weight Biclique Enumeration for Large Bipartite Graphs

In this paper, we study the problem of maximal similar-weight biclique enumeration for large bipartite graphs. Given an edge-weighted bipartite graph$G=(U,\ V,\ E)$and a weight difference threshold$\delta$, we aim to efficiently enumerate all maximal similar-weight bicliques in$G$, where a maximal similar-weight biclique is a maximal complete subgraph$B(L,\ R)$of$G$such that the weight difference of edges in$E(B)$is not larger than$\delta$. This problem has many applications, such as item recommendation, fraud detection, and biclustering of gene expression data, etc. To the best of our knowledge, we are the first to systematically study this problem. It is very challenging to efficiently solve this problem due to its #P-completeness. In this paper, we propose a two-phase branch-and-bound baseline method, namely MSWBE, which explores the search space in a depth-first manner. Although MSWBE offers a useful computation framework to our problem, its performance is not yet satisfactory due to the large candidate set during the enumeration. To alleviate this, we propose an advanced approach, called MSWBE++. In particular, MSWBE++ exploits the search space by utilizing the edge connectivity and weight information simultaneously, and therefore refines the candidate set significantly. Observing that a straightforward implementation of MSWBE++ by following a depth-first search strategy may generate non-maximal bicliques, we develop a breadth-first search strategy to realize MSWBE++, which can discard the non-maximal sets at an early stage. To accelerate the computation, we introduce effective graph reduction techniques. Our extensive experimental results on 10 real-life datasets demonstrate that MSWBE++ significantly outperforms the baseline methods by up to 2 orders of magnitude. We conduct a case study to show that maximal similar-weight bicliques can provide useful searching hints for fraudulent rating detection.