When a segmentation network outlines a pancreas in CT or a flat polyp in colonoscopy, it usually fails in one particular way. The target and its neighbour have nearly the same intensity, so the predicted mask "leaks" across a thin stretch of boundary into the adjacent tissue. A clinician can see the leak and click on it. Today that click is used weakly: it either becomes a seed for a fixed similarity graph, which leaks through the same look-alike pixels, or it triggers re-running or fine-tuning the network. We propose a different use. In a narrow band around the network's uncertain boundary, we learn a new pixel affinity graph under a constraint that forces it to split into exactly as many disconnected pieces as there are structures meeting there. Each click then becomes a pairwise "these two pixels are the same structure" (must-link) or "these two pixels are different structures" (cannot-link) relation that the learned graph must respect. The graph cannot satisfy those relations without deleting the look-alike edges, which we call bridges, that carried the leak.
The claim to test is narrow. On low-contrast boundaries, most of the gain from user corrections comes from re-learning which pixel-to-pixel edges exist, and comparatively little from adding labels to a fixed graph. If this holds, a handful of clicks processed this way should remove leaks that random-walk propagation on the same deep features and the same clicks cannot remove. We will report Dice, 95% Hausdorff distance, and clicks-to-target on ETIS polyps, Synapse pancreas, left-atrium MRI and transvaginal ultrasound.
Where this sits relative to prior work
Constraint propagation over data manifolds supplies the mechanism. One family spreads sparse relations over a fixed similarity graph using random walks or heat diffusion: Semi-supervised Clustering with Pairwise Constraints: A Discriminative Approach, Constrained Metric Learning Via Distance Gap Maximization, and the eigenspace version Constrained clustering via spectral regularization. On a low-contrast boundary the fixed graph already contains the bridge, so diffusion carries constraints straight across it. That failure is the regime we target.
Semi-supervised Clustering via Pairwise Constrained Optimal Graph (PCOG) instead learns the affinity matrix $S$. It adds a rank constraint on its Laplacian, $\mathrm{rank}(L_S)=n-c$, which forces exactly $c$ connected components, and it reports zero violated cannot-links on ORL faces where competing methods violate up to 20%. We reuse this technique. PCOG was evaluated only on generic clustering data, it needs the number of clusters $c$ to be tuned, and it does not scale to full images. Our setting removes both obstacles. Inside a boundary band, $c$ is known from the anatomy (usually two), and the band holds a few thousand nodes rather than millions.
The closest image-domain precedent is Fast Constraint Propagation for Image Segmentation (SCP). It propagates must-link and cannot-link clicks over a subsample of pixels and feeds them into Normalized Cuts. Its graph is fixed and built from six hand-crafted colour and texture features, and it was tested only on natural images. Its observation that performance plateaus at roughly 2,500–3,000 sampled pixels does motivate our band size.
Boundary-Aware Feature Propagation for Scene Segmentation gates feature flow at predicted boundaries along 1D scanlines. It needs dense boundary labels, and the gate is only as good as the boundary prediction, which is exactly what fails at low contrast. Pairwise Similarity Regularization for Semi-supervised Graph Medical Image Segmentation (PaSR) aligns teacher and student pixel-similarity graphs during training, with no negative relations and no connectivity guarantee. Its ablation shows that similarities from deep layers over-smooth boundaries, which constrains our design: we must test which feature depths to build the band graph from. Combinatorial CNN-Transformer Learning with Manifold Constraints for Semi-supervised Medical Image Segmentation (M-CnT) applies "manifold" constraints only to class-level covariance statistics and never builds a pixel graph.
The boundary-ambiguity literature motivates the problem. CaraNet (CaraNet: Context Axial Reverse Attention Network for Segmentation of Small Medical Objects) and Multi-scale Information Sharing and Selection Network with Boundary Attention for Polyp Segmentation (MISNet) document the large drops on concealed polyps. The second paper reports that standard models lose over 38% on ETIS. Parallel Res2Net-based Network with ReverseAttention for Polyp Segmentation still needs a heuristic thresholding step to resolve gray boundary pixels. All of these networks are fed forward once and have no principled way to absorb a correction.
Core Claim
Given a frozen segmentation network and a few user clicks near an ambiguous boundary, the method learns a sparse affinity graph over the uncertain band. That graph satisfies the click relations, and it falls into exactly $c$ components. Per click, this corrects leakage better than three alternatives: propagating the same clicks on a fixed graph built from the same features, adapting the network itself to the clicks, and boundary-specialised networks with no interaction. The ingredient that matters is that the graph is learned under the component constraint. Supplying relations in pairwise rather than pointwise form is not the point. In a binary band, a cannot-link pair carries nearly the same information as two labelled seeds, and we say so plainly and test it directly.
Research Program
Building the band. We take the network's probability map and define the band as pixels or voxels whose foreground probability lies in an uncertainty interval, dilated by a few pixels. We over-segment the band into roughly 2,000–4,000 superpixels or supervoxels. Pixels just outside the band that the network is confident about become automatic anchors. Interior anchors are must-linked to the foreground and exterior anchors to the background, so the band is never solved in isolation.
Node features. Each node gets features pooled from the frozen backbone at several depths. Prompted by PaSR's over-smoothing finding, we compare shallow-only, deep-only and concatenated multi-depth features. Deep semantic context may help here even though it hurts PaSR. The reason is that the rank constraint deletes edges rather than averaging across them, so it does not inherit the over-smoothing problem of graph convolutions.
Graph learning. Following PCOG, we learn $S$ by minimising a fit-to-features term plus a cannot-link penalty, subject to $\mathrm{rank}(L_S)=n-c$, using alternating updates. Each update needs only the $c$ smallest eigenvectors of an $n\times n$ sparse Laplacian with $n$ in the low thousands, so it stays cheap. Must-links are imposed as hard merges of nodes.
Active click suggestion. We adapt PCOG's "Key Selection" to boundaries. The system proposes the pair whose cannot-link would cut the most edge weight in the current graph's weakest cut. This lets us measure whether suggested pairs beat user-placed or simulated clicks.
Automatic mode. A zero-click mode, using only confident-region anchors, serves as a post-processing reference. It also tests whether the learned graph helps even before any human input.
Baselines
The naive reference point is the frozen network's own prediction with no interaction. We use CaraNet for polyps and a 3D U-Net-class model for CT and MRI, all trained on the standard splits. Reported numbers anchor these networks. CaraNet reports mDice 74.7% on ETIS-LaribPolypDB. MISNet reports mDice 0.903 on Kvasir-SEG and 0.918 on CVC-ClinicDB. The full loss framework of Combating Uncertainty with Novel Losses for Automatic Left Atrium Segmentation reports 92.24% Dice on left atrium. The boundary-preserving method of Structure Boundary Preserving Segmentation for Medical Image With Ambiguous Boundary reports 83.52% Dice on TVUS. For Synapse pancreas specifically, no reported result was found on Lacuna. Our method is beaten outright if, at zero clicks, its automatic mode fails to improve on its own backbone. It is then beaten in practice if, at five clicks, it fails to beat the stronger baselines below.
The strongest competitor on the actual question is fixed-graph propagation of the same clicks on the same band and the same frozen multi-depth features. We run it two ways: as random-walk label propagation with clicks as seeds, and as an SCP-style fusion into Normalized Cuts. This is also the ablation that isolates our key ingredient. Inputs, nodes, features and clicks are identical, and only "learned component-constrained graph" versus "fixed similarity graph" differs. Both get the same validation budget for their kernel bandwidth or regularisation weight. Beating it means a statistically significant Dice and 95% Hausdorff gain at equal click counts, concentrated on cases where ground-truth-crossing edges carry high weight in the fixed graph. For reference on natural images, SCP reports an adjusted Rand index of 0.50 on its BSDS subset, against 0.40 for the prior constrained variant. We will rerun SCP with its original hand-crafted features on BSDS to confirm our reimplementation before moving to medical data.
A second ablation drops the rank constraint and keeps the learned $S$ with only the cannot-link penalty. A third replaces cannot-link pairs with the equivalent pointwise seeds. If the third ablation matches the full method, the pairwise framing is cosmetic. We expect that outcome in binary bands and will report it honestly. The pairwise framing should matter only at multi-organ junctions where $c>2$.
Why not just…?
Why not just fine-tune the network on the clicks at test time? This is the most serious threat. Test-time adaptation can, in principle, learn the right local feature distinction. It also risks overfitting to two or three pixels, and it costs backward passes through the full network. We run it under a matched wall-clock budget, updating only the decoder for a fixed number of steps per click, and compare clicks-to-target. If it matches us, the contribution reduces to a cheaper approximation. We will say so rather than claim superiority.
Why not just retrain with a boundary loss or an edge branch? Contour losses do help. On spleen CT, A Medical Image Segmentation Method based on Multi-scale Features and Contour Loss Constrain (S) lowers 95% Hausdorff distance from 7.5744 to 5.8814. But such models still produce a single answer with no way to absorb a correction, and their edge labels are noisiest exactly where contrast vanishes. Our method is complementary rather than competing: we run it on top of the strongest boundary-trained backbone. The relevant test is whether our gains shrink to nothing when the backbone already uses these losses.
Why not just seed a random walker on deep features? This is the fixed-graph baseline above, and it is the experiment that decides the paper. A random walker with fixed affinities assigns bridge pixels by their connectivity to the seeds, so a strong bridge drags the leak back. Our hypothesis predicts failure precisely on high-bridge cases. If the random walker matches us there too, the learned-graph idea is unnecessary.
Proposed Experiments
The benchmarks are ETIS-LaribPolypDB and CVC-ColonDB for concealed polyps, Synapse CT restricted to pancreas and its neighbours, Left Atrium GE-MRI, and TVUS endometrium. We simulate clicks with a standard protocol: each click goes at the centre of the largest current error region and is labelled from ground truth, up to ten clicks, with paired cannot-links placed across the error's adjacent boundary. Metrics are Dice, 95% Hausdorff distance, number of clicks to reach a target Dice, cannot-link violation rate, and a leakage measure. The leakage measure is false-positive area that is connected to the true structure through the band.
The decisive analysis stratifies test cases by bridge strength. We define bridge strength as the total fixed-graph edge weight crossing the ground-truth boundary within the band. We then plot each method's per-click Dice gain against it. The hypothesis predicts that our advantage over fixed-graph propagation grows with bridge strength and vanishes on low-bridge cases. A flat curve would falsify the mechanism even if average numbers looked good.
Secondary checks are of four kinds. First, the feature-depth comparison tests whether PaSR's over-smoothing finding reverses under edge deletion. Second, we compare suggested against simulated click placement. Third, we measure sensitivity to the regularisation weight, with $c$ fixed by anatomy, to test whether the tuning burden documented for PCOG and spectral regularisation disappears in this setting. Fourth, we target interactive latency below one second per click on a single GPU and will report whether we reach it.
References
- Semi-supervised Clustering with Pairwise Constraints: A Discriminative Approach
- Constrained Metric Learning Via Distance Gap Maximization
- Constrained clustering via spectral regularization
- Semi-supervised Clustering via Pairwise Constrained Optimal Graph
- Fast Constraint Propagation for Image Segmentation
- Boundary-Aware Feature Propagation for Scene Segmentation
- Pairwise Similarity Regularization for Semi-supervised Graph Medical Image Segmentation
- Combinatorial CNN-Transformer Learning with Manifold Constraints for Semi-supervised Medical Image Segmentation
- CaraNet: context axial reverse attention network for segmentation of small medical objects
- Multi-scale information sharing and selection network with boundary attention for polyp segmentation
- Parallel Res2Net-based Network with ReverseAttention for Polyp Segmentation
- Combating Uncertainty with Novel Losses for Automatic Left Atrium Segmentation
- Structure Boundary Preserving Segmentation for Medical Image With Ambiguous Boundary
- A Medical Image Segmentation Method based on Multi-scale Features and Contour Loss Constrain (S)