ACMCG: A Cost-effective Active Clustering with Minimal Constraint Graph

Active clustering enhances traditional semi-supervised clustering by introducing machine-led interaction, where informative constraints are dynamically selected and posed to humans. This enables goal-driven interaction and reduces the number of required constraints for achieving high-quality clustering. In this paper, we propose a newly designed Active Clustering framework with Minimal Constraint Graph (ACMCG). ACMCG operates on two cooperating tailored sparse graphs: a tree-structured graph (clustering tree) representing the nested clustering result, and a minimal constraint graph that supports constraint deduction during iterative refinement. In each refinement round, (a) the most suspicious edge in the tree is identified for constraint verification; (b) if a cannot-link constraint is confirmed, a pruning-and-grafting approach is performed to refine the clustering tree, guided by our proposed constraint deduction strategies; (c) the constraint is either deduced from the minimal constraint graph using transitive and probabilistic deduction, or obtained via user interaction when deduction fails. Extensive experiments across diverse domains demonstrate that ACMCG consistently outperforms both classical and state-of-the-art methods in accuracy, while significantly reducing the number of user-provided constraints and maintaining low computational cost, highlighting its cost-effectiveness in real-world applications.