Adaptive Graph Partitioning for Clustering Datasets with Heterogeneous Density

In recent years, graph-partition-based clustering algorithms have attracted increasing attention. These algorithms first construct a graph over the data points and then partition this graph, regarding each connected subgraph in the partitioned graph as a cluster. However, traditional graph-partition-based clustering algorithms face challenges when clustering datasets with highly imbalanced density distributions. This is because, during the process of graph partitioning, they mainly rely on edge lengths and largely ignore local density variations. To address this issue, we propose the Adaptive Graph Partitioning (AGP) clustering algorithm. AGP integrates local density information into the partitioning process and adaptively normalizes the magnitudes of edge weights in both sparse and dense regions. This enhancement allows AGP to avoid the over-partitioning of dense clusters, effectively addressing a common problem in traditional graph-partition-based clustering algorithms. Additionally, the mechanism of connectivity domain differences is introduced into AGP, further enhancing the algorithm’s ability to discriminate between neighboring clusters that are difficult to separate. Extensive experiments on 13 benchmark datasets show that AGP achieves the best clustering performance on 7 datasets and performs competitively on the others, especially when density imbalance is severe. Moreover, scalability experiments on datasets with up to 100,000 data points, together with complexity analysis, demonstrate that AGP enjoys favorable time and memory efficiency compared with representative baselines.