2022/11/22 by Longlong Lin, Rong-Hua Li, Lin, Longlong +3 · 3 citations
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Caching and Content Delivery #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2211.12511
openalex publication_date 2022/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 peeling-based graph clustering framework 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 PCon_core and 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 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∼42 times speedup with a high clustering accuracy, while using 1.4∼7.8 times less memory than the baseline algorithms.