# Differentiable Widest-Path Loss

- ID: 547
- Canonical URL: https://synthcore.org/idea/547/differentiable-widest-path-loss
- API JSON: https://synthcore.org/api/idea/547.json
- API Markdown: https://synthcore.org/api/idea/547.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.07123](https://arxiv.org/abs/2607.07123)
- Category: regularization
- Solves: accuracy, stability, generalization
- ML areas: cnn, loss, regularization, graph-nn
- Math tags: graph-theory, optimization, geometry
- Ratings: usefulness 8/10; difficulty 5/10; novelty 6/10

## Idea description

Add a reachability loss that forces annotated structural endpoints or landmarks to remain connected through high-confidence pixels. Instead of averaging error over all pixels, the loss penalizes the weakest pixel on the best available path, directly targeting bottlenecks responsible for broken vessels, roads, and cracks.

## Mathematical statement

The paper defines cell-wise max pooling from the pixel grid to a graph grid: for a scalar field X on the original grid and stride s, $(\Pi_sX)(y,x)=\max_{0\le i,j<s}X(s(y-1)+i+1,s(x-1)+j+1)$. Use this to obtain graph-node probabilities p_v in [0,1] from the network foreground probability map. For a source node a, a path $\pi=(v_0=a,v_1,\ldots,v_m=t)$ has capacity $c(\pi)=\min_{u\in\pi}p_u$, and widest-path reachability is $R(a,t)=\max_{\pi:a\leadsto t}c(\pi)$. The outer maximum chooses the strongest route while the inner minimum is controlled by its bottleneck pixel. For differentiable training, replace min by $\operatorname{smin}_\tau(z_1,\ldots,z_n)=-\tau\log\sum_i\exp(-z_i/\tau)$ and max by $\operatorname{smax}_\tau(z_1,\ldots,z_n)=\tau\log\sum_i\exp(z_i/\tau)$. A finite-step Bellman relaxation is $R_0(v)=1$ for source nodes and 0 otherwise, $R_{k+1}(v)=\operatorname{smax}_\tau\{\operatorname{smin}_\tau(R_k(u),p_v):u\in N(v)\}$, followed by $L_{\mathrm{reach}}=\sum_{(a,t)\in\mathcal P}w_{at}(1-R_K(t))$. Here N(v) is the 4- or 8-neighbor set, $\mathcal P$ is a set of source-target pairs sampled from the ground-truth skeleton, w_at is an optional inverse-frequency pair weight, K is the number of propagation iterations, and $\tau$ controls approximation smoothness. The extracted paper formula supplies the occupancy-preserving projection; the Max-Min path expression and soft Bellman recursion provide the implementable training formalization of the stated WPRF objective.

## Key formulas

- $(\Pi_sX)(y,x)=\max_{0\leq i,j<s}X\big(s(y-1)+i+1,\,s(x-1)+j+1\big)$
- $$R(a,t)=\max_{\pi:a\leadsto t}\;\min_{u\in\pi}p_u,\qquad c(\pi)=\min_{u\in\pi}p_u.$$
- $$\operatorname{smin}_\tau(z_1,\ldots,z_n)=-\tau\log\sum_{i=1}^{n}e^{-z_i},\qquad \operatorname{smax}_\tau(z_1,\ldots,z_n)=\tau\log\sum_{i=1}^{n}e^{z_i}.$$
- $$R_{k+1}(v)=\operatorname{smax}_\tau\!\left\{\operatorname{smin}_\tau\big(R_k(u),p_v\big):u\in N(v)\right\},\qquad L_{\mathrm{reach}}=\sum_{(a,t)\in\mathcal P}w_{at}\big(1-R_K(t)\big).$$

## Implementation notes

Integrate the module after the network foreground sigmoid and before the total segmentation loss. First construct a graph on a downsampled probability map: if the output has stride s, apply the paper's cell-wise max pooling to the foreground probability p, yielding one node value p_v per graph cell. Extract a one-pixel-wide skeleton from the ground-truth foreground mask with deterministic thinning, identify endpoints and junction-adjacent landmarks, and sample source-target pairs along the same ground-truth connected component. Reject pairs whose Euclidean distance is below a minimum length so the module tests meaningful connectivity. Use 4-neighbor connectivity for the baseline and optionally 8-neighbor connectivity as an ablation. For each source a, initialize R[0,a]=1 and all other nodes to zero. For k=0,...,K-1, compute each neighbor candidate q(u,v)=smin_tau(R[k,u],p[v]), aggregate candidates with smax_tau, and retain R[k+1,v]. Gather R[K,t] for target nodes and add lambda times L_reach to BCE or Dice loss. Use log-sum-exp for numerical stability, tau=0.05 to 0.2, K equal to the maximum graph distance of sampled pairs or a clipped value such as 32, and detach neither p nor R so gradients reach the logits. Estimate no mathematical quantities: s, K, tau, lambda, and pair weights are hyperparameters; the skeleton and pair set are recomputed per training sample. Start with a small U-Net on DRIVE retinal vessels or CrackForest, comparing BCE+Dice against BCE+Dice+reachability. Measure clDice, number of predicted connected components, endpoint-to-endpoint success rate, pixel IoU, and wall-clock training overhead. Success means fewer broken components and at least a 2-point clDice gain without materially worse pixel IoU or more than 20% training-time overhead.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built a differentiable widest-path MVP with cell-wise max pooling, softmin/softmax operators, finite-step Bellman propagation, and a toy optimization comparison. The mechanism manifested: low-temperature reachability converged to the hard bottleneck (0.350), first meaningful reach appeared at K=5 for graph distance 5, and bottleneck gradients were approximately 1 below the competing capacity and 0 above it. However, the literal recurrence is non-monotonic in K because it permits exact-length backtracking, and the toy optimization gain was negligible relative to its large runtime overhead, so this is not evidence of a practical training win.

### Mechanism check

- Verdict: Built a differentiable widest-path MVP with cell-wise max pooling, softmin/softmax operators, finite-step Bellman propagation, and a toy optimization comparison. The mechanism manifested: low-temperature reachability converged to the hard bottleneck (0.350), first meaningful reach appeared at K=5 for graph distance 5, and bottleneck gradients were approximately 1 below the competing capacity and 0 above it. However, the literal recurrence is non-monotonic in K because it permits exact-length backtracking, and the toy optimization gain was negligible relative to its large runtime overhead, so this is not evidence of a practical training win.
- Confidence: 8/10
- Limitations: Only a synthetic 1-D/2-D toy task was tested; no DRIVE, CrackForest, skeleton extraction, U-Net integration, clDice, connected-component, endpoint-success, or realistic FLOP comparison was performed. The implementation uses explicit Python neighbor loops and is an MVP rather than a production-efficient loss.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 1
- Paired wins: 0/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/100/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/100/bench_report.json)
- [custom_track.py](https://synthcore.org/code/100/custom_track.py)
- [report.md](https://synthcore.org/code/100/report.md)
- [report_bench_2026-08-30T141310.md](https://synthcore.org/code/100/report_bench_2026-08-30T141310.md)
- [verification_results.json](https://synthcore.org/code/100/verification_results.json)
- [widest_path_experiment.py](https://synthcore.org/code/100/widest_path_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/100)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.