Research map / Label-efficient and robust learning / Recognition and long-tail
A3S: A General Active Clustering Method with Pairwise Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes A3S, a cluster-adjustment active clustering framework that initializes clusters adaptively (via Fast Probabilistic Clustering), then actively aggregates must-linked cluster pairs and splits impure clusters, guided by an NMI-gain analysis, to reach near-perfect clustering with few pairwise queries.
Problem
Active clustering with pairwise must-link/cannot-link queries becomes costly for large datasets with many classes, and cluster-adjustment methods need the cluster number as input and are misled by outlier queries.
Approach
Adaptive initialization of cluster number, then selecting cluster pairs to aggregate by expected NMI gain (a theorem gives conditions under which merging pure-enough clusters does not reduce NMI), plus a density/purity test that splits impure clusters and isolates outliers, with fast transitive inference of constraints.
Key results
- On MK100, A3S ends with fission rate 0.94, entropy ratio 1.08 and purity 0.9752, and can reach NMI 0.99 with fewer than 500 additional queries.
- On MS1M-100k, A3S reaches near-optimal ARI of 0.995 with only 3100 queries in 8581.86 seconds.
- Baselines typically need more than 4000 queries on datasets with thousands of samples, while A3S achieves comparable performance with a few hundred queries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use A3S instead of COBRA | active clustering · MK100 | NMI: 0.90 -> 0.93 | Helped |
| use A3S instead of COBRA | active clustering · MK100 | clustering purity: 0.8509 -> 0.9752 | Helped |
| run A3S with 3100 queries | active clustering · MS1M-100k | ARI: 0.995 with only 3100 queries | Helped |
| use four feature views instead of one (ablation) | A3S · Handwritten | initial clustering purity: 0.916 -> 0.989 | Helped |
| use multi-view aggregated pairwise probabilities (ablation) | A3S · Handwritten | overall clustering effectiveness | Helped |
| vary the initial clustering algorithm (ablation) | A3S · MK100 and Humbi-Face | clustering performance | Helped |
| increase the adaptive cluster number (ablation) | A3S · datasets in the adaptive-cluster-number study | queries needed | No clear effect |
| perturb the density threshold from d-0.1 to d or d-0.05 (ablation) | A3S · datasets in the hyperparameter study | final clustering result | No clear effect |
| add multi-view features (ablation) | A3S · Handwritten | convergence and NMI/ARI | Helped |
Surprising findings
- Semi-supervised baselines (Random, FFQS, NPU, URASC) show performance fluctuations as more genuine constraints are added, since constraints can conflict with similarity structure.
Limitations
- Purity test cannot discover all low-quality clusters with purity below 0.7; multi-view features are suggested as a remedy.
- Results on the initial adaptive cluster number are sensitive for K-means initialization, and theory assumes cluster purity near 1 and small cluster sizes relative to N.
- Evaluated only on image-based datasets with a limited set of features; multi-view experiments limited to Handwritten.
Experimental setup
Datasets: Market-1501 Humbi Handwritten MS1M
Benchmarks: MK20 MK100 Handwritten Humbi-Face MS1M-10k MS1M-100k
Metrics: NMI ARI fission rate entropy ratio purity
Baselines: Random FFQS NPU URASC COBRA
Builds on: Fast Probabilistic Clustering PCKMeans probabilistic clustering COBRA
Closest papers by meaning
- Correlation Clustering with Adaptive Similarity Queries (NeurIPS 2019 · similarity 0.86)
- Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.84)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.84)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.83)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.83)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.