When the same objects are described in several independent ways, called views (the pixels of a digit and its stroke profile, or a web page's text and the anchor text pointing to it), each view can be clustered separately. Where those clusterings disagree, at least one of them is wrong. Co-testing is an active-learning strategy that spends human labels only on such disagreements, and it is among the best-supported label-saving strategies in supervised learning. It has never been made to work for clustering. The obstacle is basic. Cluster labels from different views are arbitrary names, so "view A says cluster 3, view B says cluster 5" carries no disagreement signal. And when clusters are curved or non-convex, a single center per cluster sits in empty space, so even the shape of the disagreement is distorted.
We propose to represent each cluster in each view as a set of small local groups, which we call prototypes, rather than as one center. We then ask where the views disagree about which prototypes belong together. A disagreement becomes a question about two prototypes ("are these two groups the same cluster?"). A human answers it with one same-cluster query, and the answer propagates to every point in both groups. The core claim is that, on multi-view data with non-convex clusters, the merge decisions the views disagree on are where the consensus clustering's errors sit. Querying exactly those decisions should therefore reach a given accuracy with far fewer oracle interactions than querying near cluster centers, querying random pairs, or querying disagreeing individual points.
What exists and what is missing
Co-testing comes from Selective Sampling with Redundant Views and Selective Sampling with Co-Testing: Preliminary Results. Those papers train one classifier per view and query points where the classifiers disagree; they report a 47% average error reduction on wrapper induction. Wang and Zhou supply the theory that motivates our bet. On multi-view active learning and the combination with semi-supervised learning shows that under α-expansion, meaning that disagreement between views grows at least in proportion to each view's error, querying disagreements cuts label complexity from roughly $1/\epsilon$ to $\log(1/\epsilon)$. Multi-View Active Learning in the Non-Realizable Case extends this result to noisy labels. All of this work is confined to binary classification with aligned labels. It does not say what a "disagreement" is between two clusterings.
On the representation side, several methods replace one center with many representatives. Cure: An Efficient Clustering Algorithm for Large Databases keeps well-scattered points shrunk toward the center. Local Centroids Structured Non-Negative Matrix Factorization gives each cluster $m$ local centroids and reports a COIL20 NMI of 0.8995 versus 0.6601 for single-centroid NMF. ECMdd: Evidential c-medoids clustering with multiple prototypes uses weighted medoids. All three fix the number of prototypes by hand and use no oracle. We reuse their representational idea and also propose a partial answer to the multiplicity problem: the oracle's answers decide when prototypes must be split.
Two papers constrain the design most directly. Multiple Medoids based Multi-view Relational Fuzzy Clustering with Minimax Optimization, called M4-FC, already combines multiple medoids with multiple views. It resolves view conflict by minimizing the worst view's cost, and it reports 95.45% accuracy on Multiple Features. It is fully unsupervised, so a conflict is settled by compromise, never by asking. Active Deep Multi-view Clustering, called ADMC, is the closest active method. It deliberately queries the points nearest single cluster centers in a fused space and reaches 0.9651 accuracy on BBCSport. Its selection rule is the opposite of co-testing, and its authors name uncertainty-driven selection as future work. Pairwise same-cluster queries come from Clustering with Same-Cluster Queries and Semi-Supervised Active Clustering with Weak Oracles. Both assume one view and one center with a spherical margin, and the latter states that non-spherical geometry is open. We borrow their query type and drop their geometry.
Core Claim and Mechanism
Each view $v$ is first over-segmented into many small local groups, using CURE-style representatives or LCSNMF-style local centroids. The common refinement of these per-view segmentations, after small pieces are merged, gives a shared set of atoms $a$. Each atom is a tight group of points that every view keeps together locally. Each view also produces its own coarse clustering. From that clustering we read a co-membership indicator $s_v(a,b)\in\{0,1\}$ for every pair of nearby atoms. This step removes the label-alignment problem, because co-membership means the same thing in every view. The contention of an atom pair is
$$ c(a,b) = |a|\,|b|\;\widehat{\mathrm{Var}}_v\!\left[s_v(a,b)\right], $$
where $|a|$ is the number of points in atom $a$ and the variance runs over the $P$ views. The score is largest when the views split evenly on a merge that affects many points. We restrict it to atom pairs that are neighbors in at least one view's nearest-neighbor graph, which keeps the candidate set near-linear in the number of atoms.
The learner then repeats a simple loop. It queries the highest-contention pair by showing the oracle the most central point of each atom. It records the answer as a must-link or cannot-link constraint between the two atoms and closes the constraints under transitivity. It then re-solves a constrained consensus partition on the small atom graph. Because a single answer settles $|a||b|$ point pairs, the query count scales with the number of contested merges, not with the number of points.
A second rule handles prototype multiplicity. We occasionally probe large atoms whose members are spread unevenly across views. A cannot-link answer inside an atom splits that atom, so the number of prototypes grows only where the oracle shows it must.
Research Program
The work has three parts. First, an empirical test of the assumption itself. We will measure what fraction of the unsupervised consensus clustering's wrong atom-pair decisions fall inside the top contention set. This is the clustering analogue of α-expansion.
Second, the active algorithm above. We will compare it on equal oracle budgets, counting one point label as $k-1$ pairwise queries for a $k$-cluster problem, since a point label fixes its relation to every cluster. We will also report the unconverted count.
Third, a controlled synthetic study. We will build two-view crescents, rings and spirals, with per-view noise and a tunable correlation between the views. The point is to show where the method breaks: Wang and Zhou's theory predicts the benefit should collapse as the views become correlated. We will also test robustness to an abstaining oracle of the kind studied by Kim and Ghosh.
Baselines
The naive reference is random pairwise same-cluster queries between neighboring atoms, fed into the identical constrained consensus solver. If contention selection does not beat random selection on the same atom graph, the selection criterion contributes nothing. Below this sits the unsupervised floor. That floor is M4-FC run on the same views and distance matrices. Its reported accuracy on Multiple Features is 95.45% (Multiple Medoids based Multi-view Relational Fuzzy Clustering with Minimax Optimization). We will reproduce it with the authors' tuning protocol and require our method to exceed it on Multiple Features within a small budget.
The strongest existing method is ADMC (Active Deep Multi-view Clustering). It reports 0.9651 ACC on BBCSport, against 0.7868 for the unsupervised SDSNE, and it beats semi-supervised competitors on Caltech-2V using 30 annotations versus their 50. We will run its released configuration on BBCSport and Caltech-2V at budgets of 10 to 50 point labels, matched by converted pairwise budgets for our method. Each method gets the same hyperparameter search size on a held-out split. Beating ADMC means equal or better ACC and NMI at a lower converted budget, or higher accuracy at the same budget, averaged over seeds with confidence intervals. We will also run an ADMC variant whose selection module is replaced by fused-space entropy. This tests whether simply adding uncertainty to ADMC, as its authors propose, closes the gap.
Two ablations isolate the key ingredients. The point-level ablation samples individual point pairs on which the views disagree about co-membership, with no atoms. It keeps contention but drops the multi-point unit. The single-center ablation builds contention from per-view k-means clusterings, with one center per cluster. It keeps the atom propagation but loses non-convex geometry. We also run the classic single-view alternative: concatenate the views and apply the same-cluster-query algorithm of Clustering with Same-Cluster Queries, or margin-based uncertainty sampling.
Why not just…?
Why not just run single-center active clustering with same-cluster queries? Its guarantees rest on a margin around one center. Semi-Supervised Active Clustering with Weak Oracles itself lists non-spherical clusters as unsolved, and the LCSNMF gap on COIL20 (0.8995 versus 0.6601 NMI) shows how much single-centroid models lose on curved structure. The crescent and ring synthetics, together with the single-center ablation, test this directly. If the ablation matches the full method on real benchmarks, we will report that the multi-point component matters only for strongly non-convex data.
Why not just let ADMC select uncertain points instead of central ones? This is a real threat, and it is why the entropy-swapped ADMC variant is included. Our argument is structural. Fused-space uncertainty is a single model's confidence and can be confidently wrong, the failure co-testing was designed for. Online Active Learning for Cost Sensitive Domain Adaptation found that multi-view disagreement beat single-view uncertainty on all six of its domain pairs. If the entropy variant matches us, the contribution reduces to the query unit, and we will say so.
Why not just query individual points where views disagree, skipping prototypes? This is the most plausible simpler competitor. It may work well when clusters are compact. The point-level ablation settles it by comparing queries needed to reach a given accuracy. We expect atoms to win because one answer covers $|a||b|$ point pairs, but that advantage must show up on BBCSport and Multiple Features, not only on synthetics.
Why not just trust the unsupervised minimax consensus? M4-FC is already strong on Multiple Features. The question is whether a handful of queries on its contested merges fixes what remains. The ADMC gains over SDSNE suggest oracle input can be worth a great deal. If M4-FC errors lie mostly outside the contention set, querying cannot help, and the error-concentration check will reveal that.
Proposed Experiments
We will use Multiple Features (six views of digits), BBCSport, Caltech-2V and Cora with ACC and NMI. We will add the WebKB Course two-view data treated as a two-cluster problem. For Course, the only reported number is classification error of about 0.07 with 72 labels against above 0.10 for random sampling (Multi-View Active Learning in the Non-Realizable Case). That figure serves as a sanity anchor, not a clustering baseline. We found no reported result on Lacuna for pairwise-query multi-view clustering on any of these datasets, so all such comparisons will be run by us.
The first decisive check is error concentration. If fewer than half of consensus merge errors fall in the top-contention set at budgets below 5% of atom pairs, the core claim is false. The second is that accuracy-per-query curves must beat random atom-pair queries, the point-level ablation and ADMC at matched converted budgets. The third is the view-correlation sweep. Gains should shrink as the views become correlated, as expansion theory predicts. A method that gains equally regardless of view correlation would be winning for reasons other than co-testing, and we would investigate that before claiming the mechanism.
References
- Selective Sampling with Redundant Views
- Selective Sampling with Co-Testing: Preliminary Results
- On multi-view active learning and the combination with semi-supervised learning
- Multi-View Active Learning in the Non-Realizable Case
- Cure: An Efficient Clustering Algorithm for Large Databases
- Local Centroids Structured Non-Negative Matrix Factorization
- ECMdd: Evidential c-medoids clustering with multiple prototypes
- Multiple Medoids based Multi-view Relational Fuzzy Clustering with Minimax Optimization
- Active Deep Multi-view Clustering
- Clustering with Same-Cluster Queries
- Semi-Supervised Active Clustering with Weak Oracles
- Online Active Learning for Cost Sensitive Domain Adaptation