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.

• Publication year

  2025

• Venue

  International Conference on Information and Knowledge Management

• Publication date

  2025-11-10

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/3746252.3761132
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Representative Point-Based Clustering With Neighborhood Information for Complex Data Structures

  2025cited by this paper
• Cluster optimized batch mode active learning sample selection method

  2025cited by this paper
• Scalable Semi-Supervised Clustering via Structural Entropy With Different Constraints

  2025cited by this paper
• Deep spectral clustering by integrating local structure and prior information

  2024cited by this paper
• ACDM: An Effective and Scalable Active Clustering with Pairwise Constraint

  2024cited by this paper
• Semi-Supervised Clustering Algorithms Through Active Constraints

  2024cited by this paper
• Effective semi-supervised graph clustering with pairwise constraints

  2024cited by this paper
• A Novel Hierarchical High-Dimensional Unsupervised Active Learning Method

  2024cited by this paper
• A neighborhood-based robust clustering algorithm using Apollonius function kernel

  2024cited by this paper
• Unlabeled data selection for active learning in image classification

  2024cited by this paper
• Improving generalized zero-shot learning via cluster-based semantic disentangling representation

  2024cited by this paper
• Boosting cluster tree with reciprocal nearest neighbors scoring

  2024cited by this paper
• Semi-supervised batch active learning based on mutual information

  2024cited by this paper
• Active Clustering Ensemble With Self-Paced Learning

  2023cited by this paper
• A review on semi-supervised clustering

  2023cited by this paper
• A Systematic Literature Review on Identifying Patterns Using Unsupervised Clustering Algorithms: A Data Mining Perspective

  2023cited by this paper
• Spectral clustering with robust self-learning constraints

  2023cited by this paper
• Uncertainty-driven dynamics for active learning of interatomic potentials

  2023cited by this paper
• Two-stage semi-supervised clustering ensemble framework based on constraint weight

  2022cited by this paper
• “Probable Error of a Mean, The”

  2022cited by this paper
• Active constraints selection based on density peak

  2022cited by this paper
• Scalable clustering by aggregating representatives in hierarchical groups

  2022cited by this paper
• Efficient algorithm for finding the influential nodes using local relative change of average shortest path

  2021cited by this paper
• Query-Augmented Active Metric Learning

  2021cited by this paper
• Active Block Diagonal Subspace Clustering

  2021cited by this paper
• Semi-supervised Consensus Clustering Based on Frequent Closed Itemsets

  2020cited by this paper
• ASCENT: Active Supervision for Semi-Supervised Learning

  2020cited by this paper
• A density-based approach for querying informative constraints for clustering

  2020cited by this paper
• Fast and Effective Active Clustering Ensemble Based on Density Peak

  2020influential reference
• Hierarchical Clustering Supported by Reciprocal Nearest Neighbors

  2019cited by this paper
• A novel measure of identifying influential nodes in complex networks

  2019cited by this paper
• COBRA: A Fast and Simple Method for Active Clustering with Pairwise Constraints

  2018cited by this paper
• COBRAS: Interactive Clustering with Pairwise Queries

  2018cited by this paper
• On comparing partitions

  2015cited by this paper
• Active Learning of Constraints for Semi-Supervised Clustering

  2014cited by this paper
• Fast exact k nearest neighbors search using an orthogonal search tree

  2010cited by this paper
• Complex Wavelet Structural Similarity: A New Image Similarity Index

  2009cited by this paper
• Constrained Clustering: Advances in Algorithms, Theory, and Applications

  2008cited by this paper
• Active Semi-Supervision for Pairwise Constrained Clustering

  2004cited by this paper
• Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties

  1999cited by this paper
• Parameterisation of a stochastic model for human face identification

  1994cited by this paper
• Ieee Transactions on Pattern Analysis and Machine Intelligence 1 Active Clustering with Model-based Uncertainty Reduction

  year unknowncited by this paper

• No citing papers are available for this paper.