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.8× 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.
이상 탐지, 군집 탐색, 압축, 그리고 그래프 이해 등 동적 그래프에 대한 다양한 태스크는 해당 그래프를 구성하는 (근사) 완전 이분 부분 그래프를 찾는 문제로 연구되었다. 주어진 그래프에서 큰 (근사) 완전 이분 부분 그래프만 고려하라도 그 수가 기하급수적이므로 모두를 찾는 것은 실질적으로 불가능하다. 그렇다면 자연스럽게 두 가지 의문이 생긴다: (Q1) 근사 완전 이분 부분 그래프의 “좋은” 집합이란 무엇일까? 즉, 입력 동적 그래프에 대한 근사 완전 이분 부분 그래프의 집합이 주어지면, 그 퀄리티를 어떻게 평가해야 할까? (Q2) 큰 동적 그래프에서 어떻게 근사 완전 이분 부분 그래프의 좋은 집합을 빠르게 찾을 수 있을까? Q1과 관련하여, 본 연구는 주어진 근사 완전 이분 부분 그래프 집합이 입력 동적 그래프를 얼마나 간결하고 정확하며 완전하게 설명하는지 측정하고, 최소 설명 길이 원칙에 따라 세 관점을 체계적으로 결합한다. Q2와 관련하여, 본 연구는 퀄리티가 높은 근사 완전 이분 부분 그래프 집합의 빠른 탐색 알고리즘, CutNPeel 을 제안한다. 입력 그래프를 상황에 맞게 재분할함으로써 CutNPeel 은 탐색 공간을 줄이고 탐색 퀄리티를 향상시킨다. 6개의 실제 동적 그래프를 사용한 실험을 통해 CutNPeel 의 다음과 같은 특징을 제시한다. (a) 고품질: 최첨단 알고리즘보다 최대 51.2% 더 우수한 품질의 근사 완전 이분 부분 그래프를 탐색하고, (b) 빠름 : 차상위 알고리즘보다 최대 68.8× 빠르며, (c) 확장성: 1억 3천 4백만 엣지를 갖는 그래프로 확장 가능하다. 또한, CutNPeel 을 그래프 압축과 패턴 마이닝에 성공적으로 응용할 수 있음을 보여준다.
