  A variety of tasks on dynamic graphs, including anomaly detection, community
detection, compression, and graph understanding, have been formulated as
problems of identifying constituent (near) bi-cliques (i.e., complete bipartite
graphs). Even when we restrict our attention to maximal ones, there can be
exponentially many near bi-cliques, and thus finding all of them is practically
impossible for large graphs. Then, two questions naturally arise: (Q1) What is
a "good" set of near bi-cliques? That is, given a set of near bi-cliques in the
input dynamic graph, how should we evaluate its quality? (Q2) Given a large
dynamic graph, how can we rapidly identify a high-quality set of near
bi-cliques in it? Regarding Q1, we measure how concisely, precisely, and
exhaustively a given set of near bi-cliques describes the input dynamic graph.
We combine these three perspectives systematically on the Minimum Description
Length principle. Regarding Q2, we propose CutNPeel, a fast search algorithm
for a high-quality set of near bi-cliques. By adaptively re-partitioning the
input graph, CutNPeel reduces the search space and at the same time improves
the search quality. Our experiments using six real-world dynamic graphs
demonstrate that CutNPeel is (a) High-quality: providing near bi-cliques of up
to 51.2% better quality than its state-of-the-art competitors, (b) Fast: up to
68.8x faster than the next-best competitor, and (c) Scalable: scaling to graphs
with 134 million edges. We also show successful applications of CutNPeel to
graph compression and pattern discovery.
