Buying the Hard Angiograms: Truthful Budgeted Procurement of Vessel Annotations

Training a network to trace blood vessels in X-ray angiograms (images in which injected contrast dye makes arteries visible) still depends on experts drawing every vessel by hand. Self-supervised methods help but plateau well below supervised training. The frames that most need expert labels are the same frames that cost experts the most time: tortuous arteries, faint thin branches, overlapping vessels. If a lab pays one flat price per frame, the experts it can afford will mostly accept the easy frames. If it lets experts name their own price and pays what they ask, they have every reason to inflate the price. We propose treating annotation purchase as a truthful procurement auction. The buyer's valuation scores each candidate frame by how much new vascular structure it would add to the training set. Experts are paid under a rule where stating their true cost is always their best move, and total spending never exceeds a hard budget.

The two-sentence version is this. Annotation cost and annotation value are positively correlated in vessel segmentation, which breaks both flat pricing and pay-what-you-ask. A budget-feasible descending-price auction with a vessel-topology valuation should buy more segmentation accuracy per dollar, and we can measure exactly when it stops helping.

Core Claim

The claim is empirical and conditional. On angiography segmentation, suppose annotator costs are private, heterogeneous, and rise with structural difficulty. Then a truthful budget-feasible clock auction that selects frames by a submodular vascular-coverage value will reach a given segmentation Dice with a smaller budget than two alternatives: the best flat posted price, and uncertainty-driven active learning under flat pay. The advantage should shrink toward zero as the cost–value correlation shrinks. That second prediction is what makes the claim falsifiable rather than decorative.

Two things are new relative to the closest work. The truthful procurement mechanism of Budget-Feasible Mechanisms for Submodular Welfare Maximization in Procurement Auctions uses descending clock auctions with geometric thresholds and was evaluated on CIFAR-10 subset selection and social-graph influence. There, value comes from generic diversity, and nothing ties cost to value. From Fairness to Truthfulness: Rethinking Data Valuation Design shows that Shapley and leave-one-out payments invite cost misreporting and collapse trade, while Myerson and VCG payments do not. That study was run on medical text retrieval (MedQuAD) with a buyer valuation assumed known. We bring the mechanism to image annotation, where the buyer's value must be estimated from unlabeled pixels before any label exists. We also make the cost–value correlation the central experimental variable.

Research Program

Each seller is an annotator offering to label a fixed batch of frames for one private cost. Keeping one cost per seller keeps the problem in the single-parameter setting, where Myerson's characterization applies: truthfulness is equivalent to selection that is monotone in the bid, with threshold payments.

The buyer's value for a set $S$ of batches must be computable from unlabeled images. We use a weighted facility-location function over image patches:

$$V(S) = \sum_{j \in P} w_j \max_{i \in S} \mathrm{sim}(j, i).$$

Here $P$ is the set of patches from all candidate frames, $\mathrm{sim}(j,i)$ is the best feature similarity between patch $j$ and any patch in batch $i$, and $w_j$ is the predicted thin-vessel density of patch $j$. The features and the vessel prior come from DARL, described in Diffusion Adversarial Representation Learning for Self-supervised Vessel Segmentation. DARL learns the non-contrast background with a diffusion model (a generator trained to denoise random noise into images) and reads vessels as departures from that background.

The weight $w_j$ upweights thin branches. This borrows the motivation of the false-negative-penalizing loss in DFA-Net, where a missed branch counts as clinically worse than a spurious one. The function $V$ is monotone submodular, meaning each new batch adds less value as coverage fills in. Because $V$ depends only on images and never on bids, the value side cannot be manipulated by sellers.

We run two mechanisms on top of $V$. The first is BFM-VM from the Cui et al. paper above, which has a deterministic approximation ratio of about 0.0528. The second is the backward-greedy clock of Deterministic Budget-Feasible Clock Auctions. Both present each seller with a falling price and a take-it-or-leave-it decision. This makes truthfulness obvious to a non-economist clinician, not merely provable.

Costs are the weak link, so we measure them rather than invent them. A timing pilot has a few annotators trace a sample of XCAD and retinal frames. We then regress minutes-per-frame on structural features computed from ground-truth masks: skeleton length, branch-point count, local contrast. This regression gives an empirical cost model. We add a private multiplicative noise term per annotator, and we vary its correlation with difficulty.

Baselines

The naive reference point is to spend nothing. We train on DARL pseudo-labels alone, which reports XCAD IoU 0.471 in its paper. The ceiling is full supervision on every labeled frame. Self-Supervised Vessel Segmentation via Adversarial Learning reports a supervised UNet at XCAD Dice 0.724, against 0.557 for its self-supervised model. The value of procurement lives in that gap.

The strongest competitor is a Bayesian-optimal flat posted price. We tune a single per-batch price on the known cost distribution to maximize expected Dice under the budget, then accept every seller whose cost is below it, choosing among those by $V$. This is the realistic institutional alternative, and it is also truthful. The auction is therefore only justified if it beats this baseline.

A second competitor is uncertainty-based active learning under flat pay. It selects the frames where DARL is least confident and pays the tuned posted price. It tests whether a good selection rule alone, without price discovery, captures the gain.

A third competitor is pay-as-bid greedy selection by value per bid. We evaluate it twice. Under truthful bids, it is a full-information upper reference. Under strategic bids, sellers adapt their shading through no-regret learning over repeated rounds. Following Aggarwal et al., who show that deterministic auctions give learning bidders flat utility landscapes, we check that the simulated bidders actually converge before reporting results.

Two ablations isolate the key ingredient. One replaces $V$ with a frame count, which removes structural valuation. The other replaces the vessel-weighted $V$ with unweighted facility location on generic features, which is the CIFAR-style valuation of the Cui et al. paper.

All methods share the following: the same pool, the same held-out test folds, the same segmentation network (a UNet trained under a fixed schedule), and the same budget grid. Each baseline gets the same hyperparameter search budget as the auction's single tuning knob. Beating a baseline means reaching its Dice at a budget at least 20% smaller, with the difference exceeding the spread over 30 cost draws, at the budget where the posted price attains half the self-supervised-to-supervised gap. We found no reported result on Lacuna for budget-constrained annotation procurement on any vessel dataset, so these comparisons are all produced within this study.

Why not just…?

Why not just pay a flat price per frame? This is the real threat, and the headline experiment is built around it. A tuned posted price is truthful and simple. When costs are nearly homogeneous, or unrelated to difficulty, we expect it to tie the auction. The auction can only win by buying expensive high-value batches that the flat price excludes, or by avoiding overpayment on cheap ones. The correlation sweep will show whether that regime occurs at the correlation levels measured in the timing pilot. If it does not, we will report that flat pricing suffices.

Why not just use self-supervised segmentation and skip labels? The file's numbers argue against stopping there. Self-supervised XCAD Dice is 0.557 against 0.724 supervised, and DFA-Net reaches Dice 0.8896 with expert labels on clinical DSA. The self-supervised authors attribute the plateau to synthetic masks missing real caliber changes and tortuosity. We keep DARL as the zero-budget baseline and as the source of the value function, so this proposal extends it rather than replacing it.

Why not just pay by Shapley value or leave-one-out contribution? From Fairness to Truthfulness proves that these rules do not make truthful cost reports optimal, and reports zero trades in high-cost regimes. They also require labels before payment can be computed, whereas procurement decisions must happen before labeling. We therefore do not rerun them as a main baseline.

Why not just do active learning? Active learning answers "which frames" and ignores "at what price". The flat-pay active-learning baseline tests directly whether selection alone recovers the gain. If it matches the auction, the contribution reduces to the valuation, and the ablations will show that too.

Proposed Experiments

The primary pool is the 126 expert-annotated XCAD frames, grouped into annotator batches, with five-fold held-out test splits. The 1,621 unlabeled XCAD pairs serve only to train DARL features. A second domain pools DRIVE, STARE, HRF, and ARIA (about 220 labeled fundus images). The Tongji DSA set (292 images) is used if access can be obtained.

The main plot shows test Dice against budget for every method, at three cost–value correlation levels anchored to the pilot estimate. We report realized surplus alongside it.

Truthfulness is checked empirically, in the style of FACT or Fiction, which showed utility peaking at zero misreport. We sweep each seller's misreport from −50% to +50% and plot utility. We also report the budget overshoot of pay-as-bid under learned shading.

The decisive check is the correlation sweep. The claim survives only if the auction's advantage over the tuned posted price is significant at the correlation measured in the pilot, and vanishes as correlation goes to zero. An advantage that stays constant across the sweep would mean it comes from $V$, not from the mechanism. The count-valued and generic-feature ablations would then confirm that.

A secondary check is whether thin-branch recall improves more than overall Dice. We measure it as skeleton recall on vessels under three pixels wide. This is where the vessel-weighted value should matter if it matters at all.