Connectivity Losses That Can See a Single Broken Voxel

Neural networks that segment thin structures such as blood vessels, nerve canals, roads and cracks often produce masks that score about 98% on pixel overlap and are still broken. One missing voxel at a junction cuts a vessel tree in two, and a blood-flow simulation or a shortest-path planner built on that mask then fails. The losses currently used to prevent this include clDice, which compares centerlines (one-voxel-wide "skeletons") of prediction and ground truth, and Skeleton Recall, which rewards covering a precomputed skeleton. Both are assembled from a fixed number of local erosion and dilation steps. This note argues that the depth limit is a principled failure and not a tuning detail. Logicians have a precise result here: a modal language built only from "somewhere nearby" and "everywhere nearby" operators cannot express that a space is connected. The language needs either a global operator or a fixed-point (reachability) operator. Losses built from a bounded number of min- and max-pooling steps are formulas of exactly that restricted language, evaluated with soft truth values. As a result, the penalty they assign to one break shrinks toward zero as the structure gets longer.

The proposal has two parts. First, we make this incompleteness claim precise for segmentation losses. Second, we build the smallest extension that removes it: a loss defined by the least fixed point of "reachable through the predicted foreground," evaluated in a soft max–min semantics. The loss puts its entire gradient on the bottleneck voxel that disconnects two ground-truth-connected points. Because it is written in a modal specification language, the same machinery handles multi-class relational constraints, such as requiring that this artery class touches both of those classes. Persistent-homology losses cannot state constraints of that kind.

Core Claim

Treat the voxel grid as a finite topological space, with neighborhoods given by the usual 6- or 26-adjacency. In this space the modal "necessarily" operator is interior (erosion, a min-pool) and "possibly" is closure (dilation, a max-pool). This is the topological reading studied in Modal languages for topology: Expressivity and definability. That paper proves that basic modal formulas are exactly the properties invariant under topo-bisimulation. It also proves that connectedness becomes definable only once a global modality is added. Soft-clDice from clDice is a composition of $k$ soft erosions and dilations, where $k$ is the number of skeletonization iterations. Its value at each voxel therefore depends only on a radius-$k$ neighborhood, and the loss is an average of such local terms.

We call a loss family $\delta$-complete for connectivity if every prediction that disconnects two ground-truth-connected points incurs a penalty of at least $\delta$, where $\delta$ does not depend on image size. Our first claim is that no loss family formed by averaging bounded-depth modal terms is $\delta$-complete for any fixed $\delta>0$. A one-voxel gap in a structure whose skeleton has $|S|$ voxels changes such a loss by $O(k/|S|)$, because only the voxels within radius $k$ of the gap see it. Our second claim is that adding one fixed-point operator and one global aggregation restores $\delta$-completeness at loss level. This parallels how Partiality and Adjointness in Modal Logic recovers completeness for Euclidean logics by extending the language instead of changing the semantics. It also parallels Normal Multimodal Logics, where transitive-closure (induction) operators are what break naive constructions and must be handled directly.

Concretely, let $L(x)\in[0,1]$ be predicted foreground probability at voxel $x$. We use Gödel (max–min) semantics, which is the soft semantics soft-clDice already uses implicitly. The soft reachability of $q$ from seed $p$ is the least fixed point $R_p = \mathbf{1}_p \vee (L \wedge \Diamond R_p)$. It has the closed form

$$R_p(q) = \max_{\pi: p \to q} \; \min_{x \in \pi} L(x),$$

the strength of the best path's weakest voxel, where $\pi$ ranges over grid paths.

For a set $P^+$ of point pairs connected in the ground truth, and a set $P^-$ of pairs separated in it (by background, or by belonging to different classes), the loss is

$$\ell_{\mathrm{reach}} = \max_{(p,q)\in P^+}\big(\tau - R_p(q)\big)_+ \;+\; \max_{(p,q)\in P^-}\big(R_p(q)-\tau\big)_+ ,$$

where $\tau$ is the decision threshold. The outer maxima play the role of the global modality. Any broken pair yields a penalty near $\tau$ no matter how long the vessel is. The subgradient lands on the single bottleneck voxel of the best path, which is the voxel whose repair would reconnect the pair.

We treat Litak's result in Complete Additivity and Modal Incompleteness only as motivation, not as a theorem we import. He shows that semantics whose operators distribute over arbitrary unions miss naturally occurring logics. Voxel-additive losses such as Dice, cross-entropy and averaged soft-skeleton terms are the loss-level counterpart of that pointwise decomposability, and they miss connectivity for the analogous reason.

Research Program

The first component is theoretical. We will state and prove the $O(k/|S|)$ locality bound for the class of losses built by averaging depth-$k$ soft erosion and dilation terms, which includes soft-clDice, cbDice-style radius-weighted variants and Skeleton Recall. We will also prove that $\ell_{\mathrm{reach}}$ is $\delta$-complete with $\delta=\tau-\epsilon$ for any mask whose broken pair falls in $P^+$.

The second component is the fixed-point loss. Iterating max-pooling to convergence on a GPU would take as many steps as the structure's geodesic diameter, which can be hundreds of voxels in 3D. Instead, we compute all maximin path values from one maximum spanning tree per class, using Kruskal's algorithm with union-find. This costs near-linear time on the CPU and returns the bottleneck voxel for every pair at once. The same union-find machinery made 3D Betti matching feasible in Efficient Betti Matching Enables Topology-Aware 3D Segmentation via Persistent Homology. Pairs in $P^+$ are skeleton endpoints and junctions of the precomputed ground-truth skeleton, reusing the static CPU skeleton idea from Skeleton Recall Loss, plus randomly sampled skeleton points. Pairs in $P^-$ are sampled across nearby but separated components, which is where false bridges form.

The third component is relational specification. For multi-class vessel trees we derive, from each ground-truth volume, its class-adjacency graph and the connectivity of each class. We then write the constraints in a small multimodal language with one modality per class, a fixed-point operator and a global modality. An example constraint is "class $a$ is internally connected and externally touches class $b$," which is the RCC8 relation ec studied in Modal Logics of Topological Relations. Lutz and Wolter show that satisfiability for that logic is undecidable over Euclidean spaces. That result constrains what we may attempt, but it does not block us, because we only ever model-check formulas on a finite, already-predicted grid, and this takes polynomial time. The constraints are read off the labels, so no anatomical knowledge is hand-coded. Each constraint compiles to reachability terms of the form above. For example, "$a$ touches $b$" becomes the requirement that the soft reachability through $L_a \vee L_b$ between a seed in $a$ and a seed in $b$ reaches $\tau$ along a path that contains voxels of both classes.

The fourth component is diagnostics. We introduce two evaluation quantities that make the claim testable. Pair reachability rate is the fraction of ground-truth-connected landmark pairs that are connected in the thresholded prediction. Relational constraint satisfaction is the fraction of ground-truth adjacency and connectivity constraints that the prediction satisfies. We report these alongside Dice, clDice, and Betti-0 and Betti-1 errors.

Baselines

The naive reference is nnU-Net trained with Dice plus cross-entropy on the same splits. It anchors how much fragmentation plain overlap training leaves behind. On the mandibular canal, Automatic segmentation of mandibular canal using transformer based neural networks reports nnU-Net Dice 0.796 against 0.844 for their Swin-UNetR with clDice pipeline. We will reproduce the nnU-Net figure before comparing anything else.

The centerline baselines are soft-clDice clDice, cbDice Centerline Boundary Dice Loss for Vascular Segmentation and Skeleton Recall Skeleton Recall Loss. They are the losses our theory says are incomplete, so they are the direct target. On TopCoW small communicating arteries, the cbDice paper reports Dice 38.5% for clDice and 43.4% for cbDice with nnU-Net. On 13-class TopCoW, the Skeleton Recall paper reports that clDice crashed out of memory on a 40GB A100. It also reports that Skeleton Recall adds about 8% training time and about 2% VRAM. Skeleton Recall is therefore the strongest efficient competitor and the one we must beat on multi-class 3D.

The strongest global competitor is Betti matching: TopoMatch Topologically Faithful Image Segmentation via Induced Matching of Persistence Barcodes in 2D and DiceBetti Efficient Betti Matching in 3D. Unlike the skeleton losses, it is not bounded-depth. The file reports no Betti-error number on Lacuna for either method (the summaries state only qualitative superiority), so we will rerun it ourselves.

For fairness, every method uses the same nnU-Net backbone, the same epochs and the same augmentation. Each topological loss gets the same five-point sweep over its mixing weight, chosen on validation data. We report wall-clock time and peak VRAM for every method.

The key ablation truncates the fixed point at depth $k$ for $k \in \{5, 20, 80\}$ while keeping the global max aggregation. This isolates whether the fixed point, as opposed to the aggregation, does the work. A second ablation replaces the outer max with a mean, which removes the global modality.

We will count the proposal as beating a baseline under three conditions. First, it lowers Betti-0 error and raises pair reachability by a margin larger than the seed-to-seed standard deviation over three seeds. Second, Dice stays within one point of the best baseline. Third, on 13-class TopCoW it improves relational constraint satisfaction over Skeleton Recall at comparable cost.

Why not just…?

Why not just raise the clDice or Skeleton Recall weight? Raising the weight scales every centerline error equally, so a one-voxel break still counts as a vanishing fraction of the loss relative to other skeleton misses. The locality bound predicts that the break-versus-bulk ratio is independent of the weight. The weight sweep in our baseline protocol tests this directly. If a large weight closes the reachability gap without costing Dice, our claim fails on that dataset and we will report it.

Why not just use Betti matching, which is already global? This is the real threat. Component counting is size-independent, so on binary structures Betti matching may match our loss. Two differences remain testable. First, Betti matching checks that the number of components agrees; it does not check which specific points must be linked. A prediction can have the correct Betti numbers while wiring the wrong branches together. That error is exactly what the relational constraints on 13-class TopCoW measure. Second, its cost profile is heavier, as its own authors note that the method remains CPU-bound in 3D. If Betti matching equals us on relational satisfaction as well, the contribution shrinks to the theory and the efficiency, and we will say so.

Why not just reconnect fragments after prediction? One option is bridging nearby components with shortest paths at inference. Another is the connectivity-constrained ILP of Connectivity-constrained Interactive Panoptic Segmentation, which enforces connectivity only as non-differentiable post-processing on superpixels. We will include a shortest-path bridging post-processor applied to the Dice baseline. Bridging can connect components that should stay separate, and it cannot recover a vessel segment the network never detected. We therefore expect it to raise pair reachability while lowering Betti-1 and relational accuracy through false shortcuts. If it does not, training-time connectivity is unnecessary for that dataset.

Proposed Experiments

The first check is synthetic and decides the theory before any training. We generate tubes of skeleton lengths from 50 to 5,000 voxels, insert a controlled number of one-voxel gaps, and plot each loss's value against length. The prediction is that clDice, cbDice and Skeleton Recall penalties fall roughly as 1/length, while $\ell_{\mathrm{reach}}$ stays flat near $\tau$. If the clDice penalty does not decay, the premise is wrong.

The main training experiments cover DRIVE and Massachusetts Roads in 2D, and binary TopCoW, 13-class TopCoW, ToothFairy mandibular canal and Parse 2022 pulmonary arteries in 3D, all with the baselines above. On ToothFairy, we additionally stratify reachability failures by location along the canal. This tests whether the bottleneck gradient helps in the faded entry and exit zones that the mandibular-canal paper identifies as the dominant failure. The relational experiment runs on 13-class TopCoW and reports constraint satisfaction per class pair. The decisive outcome is the depth-truncation ablation. If performance with truncated depth reaches full-fixed-point performance at small $k$, then locality is not the operative limitation and the incompleteness story is refuted in practice. If the gap closes only as $k$ approaches the geodesic diameter, the claim holds.