Where Do the Gains in Iterative Graph-Cut Object Discovery Come From?

Several recent methods find objects in images without any labels using the same move. They treat the image as a graph whose nodes are image patches and whose edges measure how similar two patches look to a self-supervised vision model. They cut the graph to separate one object, remove that object, and cut again to find the next one. This "cut-and-mask" loop produces the pseudo-labels behind the strongest unsupervised object detectors. It has been credited with steady headline gains, such as CuVLER's jump from 29.2 to 33.2 average precision (AP) on ImageNet over CutLER.

Each of these papers changes several things at once: the feature backbone, the boundary-cleanup filter, the number of cuts per image, and the detector-training recipe run on top of the masks. The number of cuts is chosen by looking at labeled results, which quietly supplies supervision to a method billed as unsupervised. A similar audit of weakly supervised localization showed that hidden tuning of this kind erased most of a field's apparent progress. We propose the same audit for iterative graph partitioning, with one new tool that makes the audit possible. That tool is a way to score an iterative partitioner without ever fixing its stopping rule, by treating the order in which it cuts out objects as a ranking.

Core Claim

We hypothesize that, once backbone, refinement filter, and detector recipe are frozen, most of the reported improvement from newer iterative partitioners comes from three sources other than the partitioning algorithm itself. The first is stronger or ensembled features. The second is boundary snapping by a Conditional Random Field (CRF, a filter that aligns coarse masks to image edges). The third is stopping rules tuned with labels. A cheap baseline, connected components on a thresholded patch-affinity graph, should then come within a small margin of iterative Normalized Cut (NCut, a graph cut that penalizes lopsided splits) at a fraction of the cost.

The claim is falsifiable in both directions. If iterative NCut keeps a clear lead under a frozen, label-free protocol, that is a positive result the field currently lacks.

Relation to Prior Work

The motivating evidence comes from protocol audits in neighboring areas. Evaluation for Weakly Supervised Object Localization: Protocol, Metrics, and Datasets confined hyperparameter and threshold tuning to a small held-out labeled split and introduced threshold-free metrics. Under that protocol, the old Class Activation Mapping baseline matched newer methods, and a few-shot supervised baseline beat them. That audit covered single-object, weakly supervised methods, not unsupervised multi-object graph cuts, and it has no analogue of a stopping rule. Revisiting Point Cloud Shape Classification with a Simple and Effective Baseline froze training protocols in 3D classification: PointNet++ rose from 90.0% to 93.3%, and a simple 2D projection baseline beat newer architectures. We borrow its logic of freezing everything except the component under test.

The methods under audit are the following. TokenCut makes a single NCut on DINO patch features, followed by CRF or bilateral refinement; it reports 68.8 CorLoc on VOC07. CutLER introduced MaskCut, which repeats the cut a fixed three times and feeds the masks to a loss that ignores unlabeled regions and to multi-round self-training. CuVLER runs VoteCut, which applies cuts across an ensemble of DINO and DINOv2 models and merges them by pixel voting. LaVG uses Panoptic Cut, an iterative NCut followed by DenseCRF and then label assignment with CLIP text embeddings; it reports 62.1 mIoU on VOC21 at 12.59 s per image. LOST supplies a cheap alternative: it seeds from the lowest-degree patch and takes connected components. It also shows that detector training alone added about 7 CorLoc points, a direct warning that downstream training can mask differences between discovery methods.

Is clustering enough for LiDAR instance segmentation? shows that k-nearest-neighbor graphs with connected components beat learned instance heads on LiDAR. We test whether that finding carries over from 3D coordinates to 2D feature space.

Unsupervised Object Localization in the Era of Self-Supervised ViTs: A Survey collates published numbers but reruns nothing. That is exactly the gap: no head-to-head comparison under a frozen protocol exists in the file.

One constraint shapes our metric design. Object-Proposal Evaluation Protocol is 'Gameable' shows that proposal metrics can be inflated without better localization. A ranking metric could reward a method that simply emits many masks, so we fix the proposal budget and check the metric against downstream results.

Research Program

The central construction is order-aware evaluation of the cut sequence. An iterative partitioner run to exhaustion, up to a fixed budget of $K$ cuts, emits masks in the order it extracts them. We score each mask by its cut order, with an optional tie-break by the NCut objective value, and compute class-agnostic mask AP over that ranked list at fixed $K$ (we use 10 and 20).

This removes the stopping rule from evaluation, in the same way that MaxBoxAccV2 removes the score threshold. It also exposes whether early cuts are reliably real objects, which a fixed-$N$ score hides.

For deployment, stopping rules must still be chosen. Our protocol allows only two ways to choose them. The first is fully label-free criteria, such as a gap between successive graph eigenvalues, the residual graph's density, or the cut objective exceeding a limit. The second is a small held-out labeled tuning split, disjoint from the test data, following Choe et al. Every method is reported under both regimes and, separately, under the "oracle" test-set tuning that is common today. The gap between oracle and label-free results is itself a headline number.

Around this metric we build a factorized testbed. Backbones are held fixed across methods: DINO ViT-B/8, DINOv2 ViT-B/14, and DINOv2 ViT-L/14. Refinement is one of three settings: none, a single frozen DenseCRF configuration, or a frozen bilateral solver. Partitioners are swapped in and out one at a time. For end-to-end numbers, a single frozen detector recipe (CutLER's, one round of self-training) is trained on each partitioner's pseudo-masks with identical compute. This separates mask quality from what the detector can recover.

Baselines

The naive reference point is connected components on a thresholded affinity graph. We compute patch-key cosine similarity, keep edges above a threshold, drop the largest component when it touches the image border (a background heuristic), and rank the remaining components by size. The threshold is chosen by the same label-free or held-out rule as every other method. It is the 2D-feature analogue of ALPINE and is essentially instant to run. LOST's degree-seeded expansion is a second cheap baseline.

A one-shot spectral clustering baseline takes the first $K$ graph Laplacian eigenvectors, clusters them with k-means, and makes no iterative masking. It isolates whether the cut-and-mask loop matters beyond ordinary spectral clustering.

The strongest existing methods are MaskCut and VoteCut, run from their released settings but re-run on shared backbones. The best reported number in the file is CuVLER's 33.2 AP on ImageNet versus CutLER's 29.2, and that is the gap we will try to reproduce and then decompose. For open-vocabulary segmentation, the reference is LaVG's 62.1 mIoU on VOC21 against SCLIP's 59.1. We rerun Panoptic Cut with and without DenseCRF, and with its discovery stage replaced by connected components, keeping the CLIP labeling step fixed.

Two ablations isolate the key ingredients. A parameter-matched VoteCut control runs a single cut on concatenated DINO and DINOv2 features, and a second control runs a single cut on one ViT-L of comparable size. These show whether voting beats simply using more feature capacity. Swapping the refinement filter shows how much of the mask gain belongs to the CRF.

Finally, a few-shot supervised baseline, a detector fine-tuned on the same small labeled split used for tuning, tells us whether discovery is worth more than the labels the protocol already allows.

A method "beats" a baseline if it wins on order-aware mask AP and on frozen-recipe detector AP. The win must hold across three seeds and at least two backbones, by more than the seed spread.

Why not just…?

Why not just compare the numbers already collected in the survey? Those numbers mix backbones, refinement filters, and tuning regimes. The survey itself reruns nothing, so the 29.2-to-33.2 gap cannot be attributed to any single factor from published tables.

Why not just use connected components and skip graph cuts entirely? This is a real possibility, and we treat it as a hypothesis rather than a threat. ALPINE's LiDAR result and LOST's CorLoc gains make it plausible. Scenes with touching, similar-looking objects, which the file flags as a known failure of affinity graphs, are where NCut's balance penalty should help. We will report results separately on crowded COCO images to see whether the lead of iterative cuts, if any, concentrates there.

Why not just fine-tune with a few labels, since few-shot beat weak supervision in Choe et al.? It may well win on in-domain accuracy. CutLER's 5%-label result suggests discovery is most valuable as initialization and for new domains. We therefore include the few-shot baseline on COCO and compare zero-shot transfer on Watercolor2K and other cross-domain sets, where few-shot labels from COCO do not directly apply.

Why not just fix the number of cuts at three as MaskCut does? A fixed count under-segments crowded scenes and over-segments simple ones. The order-aware metric shows the full tradeoff curve, and the label-free rules test whether that tradeoff can be managed without labels.

Proposed Experiments

Datasets are VOC07 and VOC12 (CorLoc and mask AP), COCO20k and COCO val (class-agnostic mask AP), ImageNet (for pseudo-label generation and discovery AP), and Watercolor2K, UVO, and LVIS (for transfer). For grounding, we use VOC21, Pascal Context, and ADE20K with LaVG's labeling step. We also report wall-clock time per image on one GPU, since 12.59 s versus 0.6 s is a practical constraint.

The decisive checks are four. First, does the VoteCut-over-MaskCut gain survive the parameter-matched single-cut control? If more than half the gain disappears, the gain comes from features, not voting. Second, how far does each method drop when moving from oracle stopping to label-free stopping? Third, what share of Panoptic Cut's mIoU remains without DenseCRF, and is it still above connected components with the same CRF? Fourth, does the ranking of methods by order-aware mask AP predict the ranking by frozen-recipe detector AP? If it does not, the mask metric is gameable in the way the object-proposal critique warns, and we report that too.

The deliverable is a public, frozen protocol plus the full decomposition table, showing which parts of the claimed progress in iterative graph partitioning belong to the partitioning algorithm itself.