Conductance-based graph clustering has been recognized as a fundamental
operator in numerous graph analysis applications. Despite the significant
success of conductance-based graph clustering, existing algorithms are either
hard to obtain satisfactory clustering qualities, or have high time and space
complexity to achieve provable clustering qualities. To overcome these
limitations, we devise a powerful \textit{peeling}-based graph clustering
framework \textit{PCon}. We show that many existing solutions can be reduced to
our framework. Namely, they first define a score function for each vertex, then
iteratively remove the vertex with the smallest score. Finally, they output the
result with the smallest conductance during the peeling process. Based on our
framework, we propose two novel algorithms \textit{PCon\_core} and
\emph{PCon\_de} with linear time and space complexity, which can efficiently
and effectively identify clusters from massive graphs with more than a few
billion edges. Surprisingly, we prove that \emph{PCon\_de} can identify
clusters with near-constant approximation ratio, resulting in an important
theoretical improvement over the well-known quadratic Cheeger bound. Empirical
results on real-life and synthetic datasets show that our algorithms can
achieve 5$\sim$42 times speedup with a high clustering accuracy, while using
1.4$\sim$7.8 times less memory than the baseline algorithms.

本文提出了一个基于 peeling 的图聚类框架 PCon ，并使用该框架提出了两个线性时间和空间复杂度的算法 PCon_core 和 PCon_de ，可以在处理十亿级别的图数据时实现高准确度的聚类效果，而且 PCon_de 的近似度理论上提升到了常数级，相较于基线算法可以在速度上提升 5~42 倍且更节省内存。