Efficient Biclique Counting in Large Bipartite Graphs

A (p, q) -biclique is a complete subgraph (X, Y) that |X|=p, |Y|=q. Counting (p, q) -bicliques in bipartite graphs is an important operator for many bipartite graph analysis applications. However, getting the count of (p, q) -bicliques for large p and q (e. g. , p, q ≥ 10) is extremely difficult, because the number of (p, q) -bicliques increases exponentially with respect to p and q. The state-of-the-art algorithm for this problem is based on the (p, q) -biclique enumeration technique which is often costly due to the exponential blowup in the enumeration space of (p, q) -bicliques. To overcome this problem, we first propose a novel exact algorithm, called EPivoter, based on a newly-developed edge-pivoting technique. The striking feature of EPivoter is that it can count (p, q) -bicliques for all pairs of (p, q) using a combinatorial technique, instead of exhaustively enumerating all (p, q) -bicliques. Second, we propose a novel dynamic programming (DP) based h-zigzag sampling technique to provably approximate the count of the (p, q) -bicliques for all pairs of (p, q), where an h-zigzag is an ordered simple path in G with length 2h-1 (h = minp, q). We show that our DP-based sampling technique is very efficient. Third, to further improve the efficiency, we also propose a hybrid framework that integrates both the exact EPivoter algorithm and sampling-based algorithms. Extensive experiments on 7 real-world graphs show that our algorithms are several orders of magnitude faster than the state-of-the-art algorithm.