Partial Optimality in Cubic Correlation Clustering for General Graphs

2025/10/23 by David Stein, Stein, David, Bjoern Andres +3 · 1 voice
Business, Management and Accounting · Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Facility Location and Emergency Management #cs.DM #cs.LG

paper · pdf · doi:10.48550/arxiv.2510.20431

Abstract

The higher-order correlation clustering problem for a graph G and costs associated with cliques of G consists in finding a clustering of G so as to minimize the sum of the costs of those cliques whose nodes all belong to the same cluster. To tackle this NP-hard problem in practice, local search heuristics have been proposed and studied in the context of applications. Here, we establish partial optimality conditions for cubic correlation clustering, i.e., for the special case of at most 3-cliques. We define and implement algorithms for deciding these conditions and examine their effectiveness numerically, on two data sets.

Citations

• Partial Optimality in Cubic Correlation Clustering
• Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds
• Combinatorial persistency criteria for multicut and max-cut
• Maximum Persistency in Energy Minimization
• Higher-order Segmentation via Multicuts

Discussions

• David Stein, Bjoern Andres, Silvia Di Gregorio: Partial Optimality in Cubic Correlation Clustering for General Graphs https://arxiv.org/abs/2510.20431 https://arxiv.org/pdf/2510.20431 https://arxiv.or [bsky, 0 points, 0 comments]

Related

• Partial Optimality in Cubic Correlation Clustering
• Correlation Clustering with Noisy Partial Information
• Correlation Clustering for General Graphs
• Fast Combinatorial Algorithms for Min Max Correlation Clustering
• Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost