A segmentation network for blood vessels or neuron membranes can score well on per-pixel overlap and still cut a vessel in two or close a membrane into a false loop. The structure is what clinicians and connectomics pipelines rely on. Topology-aware losses already reduce these errors on average. No method can yet prove that a network's output keeps its structure, for example "this vessel stays one connected piece," for every input inside a small perturbation set. Formal verification of neural networks gives such proofs, but only for scalar margins like "class $y$ beats class $i$." Encoding a count of connected components or loops directly into an exact solver makes the problem combinatorial over every pixel.
We propose a verifier that splits the problem in two. A standard bound-propagation pass labels each output pixel as certainly foreground, certainly background, or uncertain under the perturbation. Every reachable segmentation $S$ then lies between the certain-foreground set $L$ and the possibly-foreground set $U$. Homology is the algebra that counts connected components and loops. Computing it on $L$, on $U$, and on the inclusion map from $L$ into $U$ certifies most topological claims in one pass. The same computation flags a small set of "topologically critical" uncertain pixels, and these are the only places where expensive branch-and-bound refinement is spent. The bet is that topology tells the verifier where precision matters. That would make topological certificates far cheaper than demanding every pixel be stable.
Core Claim
Write $L \subseteq S \subseteq U$ for the sandwich of reachable binary outputs. The inclusion $L \hookrightarrow U$ factors through every reachable $S$. So any connected component or loop that exists in $L$ and survives into $U$ is present in every reachable output. These surviving features are the image of $H(L) \to H(U)$, which a two-step persistent homology computation returns. This gives lower bounds on the Betti numbers, the counts $\beta_0$ of components and $\beta_1$ of loops, and it directly certifies statements such as "the Circle of Willis loop is closed" or "seed regions A and B are connected."
Upper bounds, meaning no spurious fragments and no false loops, cannot come from the sandwich alone. An isolated uncertain pixel can turn on by itself and create a new component. Here we use a local criterion. Any uncertain pixel 8-adjacent to $L$ cannot form a new component, so new-component candidates are confined to clusters of uncertain pixels that do not touch $L$. Analogously, false-loop candidates are confined to holes of $L$ whose boundary cells are uncertain. Only the pixels in these candidate clusters need branch-and-bound. Each candidate becomes a small conjunctive query, "can these specific pixels simultaneously flip?", which an exact verifier answers far more easily than a global topological property.
The new element is not bound propagation or persistent homology alone. It is using the homology of the bound sandwich both as a sound certificate and as the branching heuristic for a complete verifier.
Relation to Prior Work
The verification side supplies the machinery. Evaluating Robustness of Neural Networks with Mixed Integer Programming runs cheap interval presolving before exact mixed-integer programming and observes that robustly trained networks have many stable ReLUs. Our certain/uncertain pixel labels are the output-space analogue of their stable/unstable neurons. General Cutting Planes for Bound-Propagation-Based Neural Network Verification (GCP-CROWN) combines GPU bound propagation with solver-generated cutting planes. We reuse it as the refinement engine, but replace its specification, a single linear margin, with many small pixel-conjunction queries chosen by topology. Differentiable Abstract Interpretation for Provably Robust Neural Networks (DiffAI) trains networks through abstract bounds. We use it to produce certifiably trained segmenters. Its own result also constrains us: cheap interval domains collapse accuracy, with 91.4% error on F-MNIST, so we cannot assume loose bounds will do.
Fully Automatic Neural Network Reduction for Formal Verification shrinks networks by merging similarly bounded neurons. That reduction is complementary to ours: it reduces the network, while we reduce the specification. Stress-Testing Neural Network Verifiers with Provably Robust Instances shows that leading verifiers return unsound answers near the analytical margin. This is a warning that our certificates must be checked against ground-truth instances.
The topology side motivates the problem and supplies the training losses. Topology-Preserving Deep Image Segmentation makes persistent homology a differentiable loss through critical pixels. Our "critical uncertain pixels" deliberately borrow that idea, but we use them for proof search rather than for gradients. Topology Optimization in Medical Image Segmentation With Fast χ Euler Characteristic computes the Euler characteristic $\chi$ with local convolution kernels. Because that computation is linear in local pixel patterns, bounding $\chi$ under perturbation is easy. The same paper notes that $\chi$ cannot tell a lost component from an extra hole, which is exactly why we certify Betti numbers rather than $\chi$.
Topology-Preserving Adversarial Training is the closest work joining topology and robustness. It preserves latent neighborhood structure empirically and gives no certificates. The decidability results in Fundamental Limits in Formal Verification of Message-Passing Neural Networks concern graph networks on unbounded inputs and do not apply here, because images are finite grids. Their message that bounded structure restores decidability is consistent with our patch-based setting.
Research Program
We will build the verifier on top of an existing bound-propagation library. Pixel bounds come from CROWN-style linear relaxation, and refinement uses GCP-CROWN. The topological stage runs in two dimensions on cubical complexes, where components are found by union-find in near-linear time. For loops, we use a duality trick: on a 2D grid, $\beta_1$ of the foreground relates to $\beta_0$ of the background complement. Loop certification therefore reduces to component computations on the complement sandwich $\bar U \subseteq \bar S \subseteq \bar L$. This keeps the 2D topological stage essentially linear and avoids the cubic boundary-matrix reduction.
In 3D we need $\beta_1$ of voxel volumes, so a genuine persistence computation is required. It is run once per instance on a two-step filtration, which is still cheap compared with the verifier.
We consider three perturbation models. The first is $L_\infty$ balls on input intensities. The second is low-dimensional photometric perturbations, contrast and brightness shifts, which are realistic for microscopy and fundus imaging and give much tighter bounds. The third is bounded elastic shifts, as an exploratory case.
Full U-Nets on megapixel images are beyond current complete verifiers, so we verify output crops whose whole receptive field is included in the input. This is honest about scale, and we report how certified fraction degrades with crop size. Crop boundaries need care: structures crossing them are handled by certifying relative statements, such as "boundary entry points A and B are connected inside the crop," in the spirit of the relative homology used in Topology-Preserving Deep Image Segmentation.
Our analysis will establish soundness of the sandwich certificate and of the local upper-bound criterion, and characterize when the one-pass certificate is already complete, namely when no candidate clusters exist. We will also study how training changes certifiability. Networks trained with Dice loss, with the persistent-homology loss, with the fast-$\chi$ loss, and with DiffAI-style certified training should differ sharply in how many uncertain pixels sit at topologically critical locations.
Baselines
The naive reference point is pixelwise certification. CROWN is run on every output pixel, and the topology counts as certified only if every pixel is stable, that is, if $L = U$. It is the obvious thing a verification practitioner would do, and it is sound. We expect it to be extremely conservative, because thin vessels have many marginal boundary pixels whose flips change no topology. It uses the same bound computation as our first stage, so the comparison isolates the value of topological reasoning at zero extra network cost. Beating it means certifying topology on substantially more crops at equal perturbation radius.
The strongest existing method is GCP-CROWN applied to every unstable pixel with its default branching. It is the most capable complete verifier in the file, the first to solve all 100 oval20 instances at under 5 seconds each and 23 of 30 oval21 instances against the 2021 winner's 11 (General Cutting Planes for Bound-Propagation-Based Neural Network Verification). Note that these are classification benchmarks. We found no reported result on Lacuna for certified topology of segmentation outputs on ISBI12, CREMI, DRIVE, or TopCoW, so we will establish this baseline ourselves. It will run with identical networks, identical crops, the same GPU, and the same per-instance timeout. Beating it means a higher certified fraction within the timeout, or equal certified fraction at a large wall-clock reduction.
We also compare against a sup-norm stability bound. Here persistence is computed once on the midpoint likelihood map, and any feature whose persistence exceeds twice the largest bound width is treated as certified. This is the simplest topological shortcut. It is sound but uses one global width, and our per-pixel sandwich should dominate it.
The key ablation keeps the full pipeline but spends the same branch-and-bound budget on randomly chosen or largest-width uncertain pixels instead of topology-selected ones. If this ablation matches our method, the topological guidance carries no weight.
For the reverse direction, a topology-loss attack serves as an empirical upper bound. It runs PGD on the persistent-homology loss of Topology-Preserving Deep Image Segmentation to search for real topological violations, and the gap between attacked and certified fractions measures remaining looseness. Every verifier is also run on synthetic instances with analytically known topology, following the methodology of Stress-Testing Neural Network Verifiers with Provably Robust Instances, to check for unsound claims.
Why not just…?
Why not just use randomized smoothing? Smoothing certifies any black-box model by voting over noisy copies, and it has been applied to graph topology attacks (Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothing). It is a real threat for $L_2$ perturbations on large images, where deterministic verifiers do not reach. Its guarantees are probabilistic and per-output. Extending them to a segmentation's Betti numbers requires either treating the whole topology as one smoothed label, which needs very many samples to pin down, or certifying every pixel, which inherits the conservatism of the naive baseline. We will run smoothed segmentation with a topology-level vote as a comparison, accepting that it may win at large radii and full resolution. Our claim is restricted to the regime where deterministic certificates are required and feasible.
Why not just certify the Euler characteristic, since it is local and cheap? Bounding $\chi$ under perturbation is close to trivial: it is a linear count of local pixel patterns, which is the source of the 72.7x speedup in Topology Optimization in Medical Image Segmentation With Fast χ Euler Characteristic. However, $\chi = \beta_0 - \beta_1$ in 2D, so a broken vessel combined with a spurious loop leaves $\chi$ unchanged, and the certificate would miss exactly the failure we care about. We include a $\chi$-certificate baseline and report how often it certifies an instance that our attack shows violates the Betti numbers.
Why not just train with topology-preserving or adversarial losses and skip certification? These losses lower error on average. On ISBI12, for example, the persistent-homology loss drops Betti Number Error from 3.187 to 0.429 (Topology-Preserving Deep Image Segmentation). Topology-Preserving Adversarial Training adds only empirical robustness. DiffAI's results show what uncertified training gives you: an uncertified baseline network had a 100% provable error bound against 3.6% for the certifiably trained one (Differentiable Abstract Interpretation for Provably Robust Neural Networks). We treat these losses as training conditions to compare, not as alternatives to proof.
Why not just use the reduction approach to shrink the network? Neuron merging (Fully Automatic Neural Network Reduction for Formal Verification) is orthogonal to our method and can be stacked with it. We will test the combination rather than treat it as a competitor.
Proposed Experiments
The main benchmarks are ISBI12 and CREMI for neuron membranes, DRIVE and FIVES for retinal vessels, and Massachusetts Roads for thin networks. TopCoW provides the 3D test, where the Circle of Willis loop is a natural $\beta_1$ property. For each dataset we train small verifiable U-Net-style segmenters under four regimes: Dice only, persistent-homology loss, fast-$\chi$ loss, and DiffAI certified training. We then sample output crops and target properties, either "the ground-truth number of components and loops is preserved" or "given seed regions remain connected."
The primary metric is certified topological accuracy: the fraction of crops whose Betti numbers are proven to match the clean prediction across the perturbation set, plotted against radius. Secondary metrics are wall-clock time per crop, the fraction of uncertain pixels that are topologically critical, and the gap to the attack upper bound.
Three results decide whether the idea holds. First, at equal radius, our one-pass certificate alone should exceed pixelwise certification by a wide margin on vessel and membrane data. If uncertain pixels are rarely topologically harmless, the premise fails. Second, topology-guided refinement should beat both full GCP-CROWN and the random-pixel ablation under equal timeouts. If random selection matches it, the guidance adds nothing and we would report the sandwich certificate as the sole contribution. Third, no certificate may be contradicted by the attack or by the analytically constructed instances. Any contradiction is treated as a soundness bug, not noise.
A final scaling study reports how certified fraction and runtime change as crop size grows and as we move from 2D to 3D. This tells us honestly how far topology-guided specification reduction pushes verifiable segmentation before network size becomes the limit again.
References
- Evaluating Robustness of Neural Networks with Mixed Integer Programming
- General Cutting Planes for Bound-Propagation-Based Neural Network Verification
- Differentiable Abstract Interpretation for Provably Robust Neural Networks
- Fully Automatic Neural Network Reduction for Formal Verification
- Stress-Testing Neural Network Verifiers with Provably Robust Instances
- Topology-Preserving Deep Image Segmentation
- Topology Optimization in Medical Image Segmentation With Fast χ Euler Characteristic
- Topology-preserving Adversarial Training for Alleviating Natural Accuracy Degradation
- Fundamental Limits in Formal Verification of Message-Passing Neural Networks
- Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothing