Efficient Primal-Dual Optimization for Non-Convex Graph Partitioning

Graph partitioning is a fundamental task in image segmentation and data clustering. However, identifying partitions with clear image and community boundaries remains challenging because convex relaxations can blur label transitions. This letter proposes a non-convex, sparsity-inducing model for semi-supervised graph partitioning. A Legendre–Fenchel transformation yields an equivalent min–max formulation, which is solved by a customized Chambolle–Pock primal–dual algorithm with an adaptively selected dual interval. Experiments on structured networks, clustering graphs, and images demonstrate accurate partitions and sharp boundaries.