Choosing Which Slices to Annotate with Graph Sampling Theory

Doctors annotating a 3D scan (a CT or MRI volume) rarely draw the organ on every slice. They outline a few 2D slices and let software fill in the rest. How good the result is depends heavily on which slices they chose, yet current tools pick the next slice with ad hoc rules, such as "the slice where the model is least confident." This proposal treats the scan as a graph of small 3D regions and the organ mask as a smooth signal on that graph. That lets classical sampling theory for graphs answer three practical questions before much annotation effort is spent: which slices to annotate, roughly how many will be needed, and when adding more slices will start to hurt rather than help.

In plain terms, a mask that changes slowly across neighboring regions is a "bandlimited graph signal." It can be described by a few smooth basis patterns, the lowest-frequency eigenvectors of the graph Laplacian (the matrix that measures how much a signal differs between connected nodes). The key difference from ordinary graph sampling is that a human cannot label arbitrary scattered nodes. They label whole planes, and each annotated slice fixes the label of every region that plane cuts through. The contribution is therefore a sampling theory and algorithm for plane-structured sampling sets on volumetric graphs, tested against the heuristics and learned propagators currently used for sparse 3D annotation.

Core Claim

For slice-based 3D annotation, a good slice is one that makes the reconstruction problem well-conditioned. Concretely, the chosen slices should cover the low-frequency basis of a feature-weighted region graph so that the restricted basis matrix has a large smallest singular value. Uncertainty is the wrong criterion. We claim that greedy selection under this conditioning criterion, over axial, coronal and sagittal planes jointly, beats uncertainty-based and uniformly spaced slice choice at equal annotation budget. We further claim that the same quantities give a per-volume estimate of the signal bandwidth, and hence of the budget needed. Finally, they predict the non-monotonic "peaking" of error that On the Impact of Sample Size in Reconstructing Graph Signals proves for noisy least-squares reconstruction. With annotation noise concentrated at blurry boundaries, we expect that peaking to appear in real annotation curves as a visible dip, and a regularized estimator should remove it.

This proposal does not reframe sparse-annotation filling as Laplacian-regularized label propagation. That part is old: random-walker-style segmentation already does it, and a skeptic would rightly call it a rediscovery. Propagation is only the reconstruction engine here. The new object is the plane-constrained sampling-set design and the sample-size theory attached to it.

Research Program

Graph construction. Each volume is partitioned into roughly $10^4$ supervoxels (small, compact 3D regions). Supervoxels are the nodes. Edges connect spatial neighbors, with distances computed in physical millimeters so that thick-slice anisotropy is respected. Edge weights combine intensity similarity with features from a frozen pretrained volumetric encoder; we use the ViT from SegVol, a 3D foundation model pretrained on 90,000 unlabeled CT volumes. We also learn a small set of weighting parameters on training volumes. The motivation comes from Spatial Graph Signal Interpolation for BCI datasets, which reconstructs missing EEG electrodes by minimizing graph total variation and finds that learned graphs beat purely geometric ones. That work stays on at most 76 scalp sensors, so we inherit its design lesson but not its dense-inversion solver. At $10^4$ nodes, the bottom-$k$ eigenvectors come cheaply from Lanczos iteration. Reconstruction uses conjugate gradients, as in Complex Graph Laplacian Regularizer for Inferencing Grid States, which supplies the linear-time solver.

Reconstruction. Let $S$ be the set of supervoxels intersected by the annotated planes, $y_S$ their annotated labels, $L$ the Laplacian, and $\mu \ge 0$ a noise-dependent weight. The mask estimate is

$$\hat{x} = \arg\min_{x} \|x_S - y_S\|_2^2 + \mu\, x^T L x,$$

thresholded at 0.5. One such problem is solved per class. When $\mu \to 0$ with $x$ constrained to the span $U_k$ of the first $k$ Laplacian eigenvectors, this reduces to the least-squares bandlimited estimator analyzed in the sample-size paper.

Plane-structured selection. Each candidate plane $p$, whether axial, coronal or sagittal at any offset, contributes the rows of $U_k$ belonging to the supervoxels it cuts. We greedily add planes to maximize

$$F(P) = \log\det\Big(\epsilon I + \sum_{p \in P} U_{k,p}^T U_{k,p}\Big),$$

where $U_{k,p}$ is the block of rows for plane $p$ and $\epsilon$ a small ridge. $F$ is monotone submodular because it is a log-determinant of a sum of positive semidefinite terms. Greedy selection therefore carries the standard $(1-1/e)$ guarantee. We borrow this style of guarantee from Online Graph Completion, which uses leverage-score sequential sampling on node-level graphs (for example, 79 patients as nodes). We extend it from single nodes to whole planes. Unlike additive per-slice leverage scores, the log-determinant penalizes planes that re-cover basis directions already covered. That matters because adjacent axial slices are nearly redundant. Selection can be adaptive: after each annotation, $k$ and the graph weights are updated using the labels received so far.

Bandwidth and budget. A Sampling Theory Perspective of Graph-based Semi-supervised Learning shows, on synthetic data, that a class indicator's bandwidth tracks the data density on the decision boundary. We estimate $k$ per volume, before any annotation, from a coarse zero-shot mask produced by the frozen encoder, using that paper's iterated-Laplacian bandwidth estimator. We then test whether this estimate predicts the number of planes needed to reach a target Dice. Treating the sample-size paper's SNR threshold as operational, we estimate annotation noise from inter-observer disagreement where it is available. Otherwise we inject boundary noise synthetically. We then choose $\mu$ so that the predicted error dip near $|S| \approx k$ is suppressed.

Baselines

The naive reference is uniformly spaced axial slices at the same budget, followed by the same graph reconstruction. This is roughly what annotators do by default. Beating it shows that selection matters at all.

The strongest existing selection method is the Maximum Softmax Probability slice recommendation of Slice and Conquer. SnC couples 2D interaction with a 3D propagation network and optical-flow alignment, and reports Dice 0.849 on MSD-Lung against a previous best of 0.815. We run its rule, picking the least-confident slice, on top of our own reconstruction engine. The comparison then isolates the selection criterion: same graph, same budget of planes, same encoder. As a second comparison, we pair it with a 3D propagation network for end-to-end parity. Beating it means higher mean Dice at budgets of 1 to 6 planes. The largest gains are expected at 2 to 4 planes, where conditioning should matter most, and they should be significant across volumes by paired test.

The strongest learned sparse-annotation method is 3D U-Net. Trained with zero loss weight on unlabeled voxels from 1 to 3 orthogonal slices, it reaches IoU 0.863 on Xenopus kidney confocal stacks with 3-fold cross-validation, against 0.796 for a 2D baseline. We retrain it under the same fold splits, with slices chosen by each selection rule. We also give it the same frozen-feature input where that helps, so that selection and reconstruction effects are not confounded. Matching 0.863 IoU with graph reconstruction alone, and exceeding it once the selection rule is applied, would count as beating it.

For the foundation-model reference, we use SegVol's reported average Dice of 0.8593 on AMOS22. Its protocol is prompt-based rather than slice-based, so the number is context, not a like-for-like target. We run SegVol prompted from the same annotated slices.

Two ablations isolate the key ingredient. The first replaces the log-determinant with additive per-slice leverage scores, which removes redundancy-awareness. The second restricts selection to axial planes only, which tests whether cross-orientation planes matter.

Why not just…?

Why not just train a 3D U-Net on the sparse slices, since a tuned plain 3D U-Net is hard to beat? An attempt at beating the 3D U-Net won KiTS2019 at 91.23% composite Dice and found residual variants within 0.35% of the plain model. This is a real threat for reconstruction quality given enough labeled volumes. It does not address which slices to label within a single new volume, and the sparse-annotation 3D U-Net drops from 0.863 to 0.704 IoU in the fully automated setting. Our design treats the U-Net as an alternative reconstructor inside the selection comparison. If the U-Net plus our selection beats graph reconstruction plus our selection, we will report the method as a slice-selection rule and drop the claim that the graph reconstruction is better.

Why not just pick diverse slices in feature space, for example a k-center core-set over slice embeddings? This is the most dangerous alternative, because diversity already captures some of the redundancy our log-determinant penalizes. No reported result on Lacuna was found for core-set slice selection in volumetric segmentation. We include it as a baseline with the same encoder features. The distinguishing prediction is that conditioning-based selection should concentrate planes where the mask boundary is dense, which the bandwidth theory predicts. Feature diversity instead spreads planes across the whole volume. If the core-set method matches ours, the spectral machinery is unnecessary, and the experiment will show that.

Why not just interpolate between annotated slices with optical flow or splines? The BCI interpolation paper found geometry-only spherical splines inferior to graph interpolation. SnC itself flags its TV-L1 optical flow step as costly. Flow interpolation also cannot use coronal or sagittal planes jointly with axial ones. We include flow-warped interpolation as a reconstruction baseline under uniform slices.

Why not just prompt a 3D foundation model? SegVol needed 90,000 unlabeled and 6,000 labeled volumes, and the runner-up on AMOS22 reached only 0.6668 Dice, so quality varies widely between models. We use SegVol's frozen features rather than competing with it. If its prompted output already saturates Dice after one plane, selection is moot on that dataset, and we will report that.

Proposed Experiments

The primary benchmark is the Xenopus kidney stacks, because they carry the reported sparse-annotation number. Secondary benchmarks are MSD-Lung and KiTS19, where SnC was evaluated, and AMOS22 for multi-organ generalization. Annotations are simulated from ground-truth masks. Slice-level noise is simulated by boundary dilation and erosion of 1 to 3 voxels, which mimics low-contrast edges.

For each volume we trace Dice and average surface distance as a function of the number of planes under each selection rule, and report the area under that curve.

Three decisive checks follow.

The first tests selection. Log-determinant selection must beat MSP and uniform selection in area under the curve on at least three of four datasets, with the same reconstructor. If additive leverage scores match it, the redundancy argument fails.

The second tests budget prediction. The pre-annotation bandwidth estimate must correlate with the number of planes needed to reach 0.8 Dice across volumes, with Spearman correlation above 0.5 as a pre-registered threshold. Otherwise the budget-prediction claim is dropped.

The third tests peaking. Under injected noise, the unregularized least-squares estimator should show an error rise near $|S| \approx k$, as the sample-size theory predicts, and the $\mu$-regularized estimator should remove it. If no dip appears on real data even at high noise, we will say that the theory's regime does not reach clinical annotation.

We also report wall-clock time for eigenvector computation and conjugate-gradient reconstruction per interaction. Selection is only usable if it runs within a few seconds, comparable to SnC's reported under-2.5-second loop.