Tractography reconstructs the brain's white matter wiring from diffusion MRI by tracing curves through a field of local fiber directions. Its main failure is not a lack of sensitivity. In the ISMRM 2015 challenge, 96 pipelines found about 90% of the true bundles but produced four invalid bundles for every valid one. Half of those invalid bundles were shared across nearly all groups, and supplying noise-free data did not remove them (The challenge of mapping the human connectome based on diffusion tractography). The main cause is the bottleneck: a region where several bundles run side by side in the same direction and then split apart. Such regions are present in 50–70% of oriented fiber elements in the human brain (Prevalence of white matter pathways coming into a single diffusion MRI voxel orientation). A tracker that decides one step at a time cannot tell which incoming fiber should leave by which exit. The global alternatives also fall short. They fit the measured signal, and a good signal fit does not guarantee anatomy: loops and fibers that stop inside white matter can "steal" signal from real pathways (Microstructure Informed Tractography: Pitfalls and Open Challenges).
This proposal treats whole-brain tractography as a directed routing problem and borrows one specific tool from the theory of the asymmetric traveling salesman problem (ATSP), the directed-graph version of the classic tour-finding problem. The tool is the Held-Karp relaxation: a linear program over fractional edge usage that adds subtour elimination cuts, constraints forcing every group of vertices to connect to the rest of the graph. In ATSP, dropping these cuts lets the solver cover all vertices with cheap disconnected loops. We argue that signal-fitting tractography fails in the same way. Asking a flow to explain every fiber element's measured density rewards short loops and dead-end fragments inside white matter. Held-Karp-style cuts rooted at the cortex remove exactly these solutions. Because the costs are direction-dependent, the flow must also respect conserved volume at bottleneck entries and exits.
Core Claim
Model white matter as a directed graph. Each state is a fiber element (a "fixel", one fiber direction within one voxel) together with the direction of travel. Each edge carries an asymmetric cost that penalizes turning and misalignment with the local asymmetric fiber orientation distribution (AFODF), a direction estimate that is not forced to be antipodally symmetric. We solve for a nonnegative flow $x_e$ on each edge $e$, with throughput $y_v$ at state $v$ and measured fiber density $a_v$:
$$\min_{x,y \ge 0} \; \sum_e c_e x_e + \lambda \sum_v |y_v - a_v| \quad \text{s.t.} \quad x(\delta^-(v)) = x(\delta^+(v)) = y_v \;\; \forall v \in W,$$
$$x(\delta^+(S)) \ge y_v \quad \forall S \subseteq W,\; v \in S.$$
Here $W$ is the set of white-matter states. Gray matter is collapsed into a root that supplies and absorbs flow, $\delta^\pm$ denote outgoing and incoming edge sets, and $\lambda$ trades path cost against density fit. The second line is the generalized subtour elimination constraint familiar from prize-collecting tours. It says that any set of white-matter states carrying flow must send at least that much flow out of itself, so no volume can circulate or terminate inside white matter.
We make three testable claims. First, without the cuts, a substantial share of the optimal flow sits in white-matter cycles. This is the tractography analogue of ATSP's cycle-cover relaxation and the mechanism behind "partial fibers steal signal." Second, with the cuts, invalid bundles in the ISMRM phantom drop measurably, specifically in bottleneck regions. In those regions volume conservation plus asymmetric turning costs favor straight-through pairings that local trackers ignore. Third, the gap between this LP and its integer rounding is small on real instances.
The third claim is an empirical integrality-gap question in the spirit of computational ATSP gap studies (On the integrality gap of small Asymmetric Traveling Salesman Problems), asked on brains instead of worst-case graphs.
Relation to Prior Work
The motivating evidence comes from Schilling et al. and Maier-Hein et al. Schilling et al. showed that bottlenecks are pervasive. Maier-Hein et al. showed that invalid bundles persist even on clean data and called for global, structurally constrained reconstruction. Neither paper proposes an optimization method.
The constraining evidence comes from Microstructure Informed Tractography: Pitfalls and Open Challenges. That work filters a fixed dictionary of candidate streamlines through the linear model $y = Ax + \eta$ and shows three failure modes. Missing fibers produce spurious weights. Duplicate fibers split weight among themselves. Low fitting error does not imply valid anatomy. We accept all three findings. We differ in two ways: we optimize over paths in a graph instead of a fixed dictionary, and we add connectivity cuts that no continuous dictionary filter contains.
Global Tractography with Embedded Anatomical Priors also forces endpoints into gray matter, reporting 100% valid and 0% invalid connections on FiberCup. It uses simulated annealing with Markov chain Monte Carlo (MCMC) over spline streamlines, which has no optimality certificate. Our cuts express the same anatomical prior as polyhedral constraints, so the LP's lower bound certifies how far any rounded solution is from optimal.
Three papers supply parts of the method. A Random Riemannian Metric for Probabilistic Shortest-Path Tractography computes geodesics between two chosen endpoints under a symmetric tensor metric and names direction-dependent (Finsler) costs as the missing step. Our line-graph costs are a discrete Finsler metric, and we route all bundles jointly instead of one pair at a time. Mitigating Gyral Bias via Asymmetric Fiber Orientation Distributions supplies the asymmetric orientation field and a local exit-equals-entry continuity constraint. We use its AFODFs as input and lift that local conservation to a global one with connectivity. Wu et al. still extract streamlines by local stepping.
From ATSP theory we reuse two things: the Held-Karp cut structure and the practice of turning a connected fractional solution into tours by merging cycles at shared vertices. The Svensson–Tarnawski–Végh constant-factor algorithm (A Constant-Factor Approximation Algorithm for the ATSP) shows these ideas carry provable guarantees. Its backbones and laminar reductions are too heavy for practice, so we do not claim its constants carry over.
Research Program
We will build the state graph from AFODF lobes estimated with Wu et al.'s convex method. Each state is a fixel plus its incoming direction. Edges go to neighboring fixels, with cost equal to a turning-angle penalty plus an asymmetric orientation-mismatch term. The fiber density $a_v$ comes from lobe amplitude.
The LP will be solved with a first-order solver, with cut generation in the style of TSP codes. We solve without cuts, find connected components of the support graph that do not touch the gray-matter root, add the violated cuts, and repeat. Exact separation by max-flow is run only on the remaining candidates.
Rounding proceeds in four steps. We decompose the fractional flow into paths and cycles. We merge each cycle into a path that shares a state with it; the cuts guarantee such a path is reachable. We pay the added turning cost at each merge. We then discretize path weights into streamlines. We will record how much each merge costs, since this overhead is exactly what an ATSP-style approximation analysis would bound.
Alongside the experiments, we will study the question theoretically. The target is a bounded-overhead rounding result when turning costs obey a triangle-like inequality on directions, or a counterexample showing this fails.
Baselines
The naive reference point is deterministic local streamline tracking, the pipeline family in The challenge of mapping the human connectome. There, the field-wide result was about 90% bundle recovery with roughly four invalid bundles per valid one and about 36% volume overlap. We rerun it through the same Tractometer scoring on the ISMRM 2015 phantom.
The strongest learned competitor is TractoTransformer. It reports a valid-connection rate of 84% and an F1 of 75% on the ISMRM phantom, with inference of about 43 minutes on four V100 GPUs. DeepTract reports all 25 bundles, 69.3% overlap and F1 70.1. No per-method invalid-bundle count was found on Lacuna for either model. We will therefore rerun released models where possible and score invalid bundles ourselves. Beating this baseline means fewer invalid bundles at equal or higher valid-connection rate and F1, on the same phantom and scoring script.
The strongest global competitor is anatomically constrained MCMC (Global Tractography with Embedded Anatomical Priors), which reports 100% valid and 0% invalid connections on FiberCup against Gibbs tracking's 22% and 15%. Because FiberCup is nearly saturated by that result, the comparison that matters is on the ISMRM phantom. There we give MCMC the same wall-clock budget as our LP.
The continuous-filtering competitor is dictionary filtering per Microstructure Informed Tractography, applied to a dense candidate set from AFODF tracking. It uses the same AFODF input and endpoint filtering.
Two ablations isolate the key ingredients. The first removes the cuts, leaving flow conservation plus the density fit. The second makes costs symmetric by dropping the incoming-direction state. We tune every method's hyperparameters on held-out phantom noise realizations with an equal number of configurations.
Why not just…?
Why not just run a min-cost flow from cortex to cortex, with no cuts? With positive costs and no density-fit term, a min-cost flow has no cycles, so the cuts would indeed be redundant. But such a flow ignores the measured fiber density and collapses onto a few cheap routes. Once density is fitted, cycles and dead ends become the cheapest way to explain white-matter signal, and this is the failure the pitfalls paper documents. The first ablation measures directly how much flow sits in white-matter cycles and what that does to invalid bundles. If that fraction is negligible, the ATSP machinery is unnecessary and we will say so.
Why not just filter a dense tractogram with endpoint constraints? This is the real threat. It combines Daducci-style filtering with the gray-matter endpoint prior. Its limitation is structural: it can only reweight candidates it is given, so missing true paths lead it to invent spurious ones. It also cannot enforce volume conservation at bottleneck exits. Running it on the same AFODF candidates, and scoring invalid bundles restricted to bottleneck fixels, will show whether graph-level optimization adds anything beyond better filtering.
Why not just train a better sequence model? Learned trackers condition on history and could in principle learn pairings through bottlenecks. Still, they decode greedily and report no invalid-bundle reduction on Lacuna, and they cost 43 GPU-minutes per brain across four V100s. Our comparison is at matched invalid-bundle scoring. A learned model that matches our invalid-bundle count would refute the claim that global structure is needed.
Proposed Experiments
The primary benchmark is the ISMRM 2015 phantom with its 25 ground-truth bundles. We report valid and invalid connections, valid and invalid bundles, overlap, overreach and F1. We also report a new bottleneck-restricted analysis. Following Schilling et al.'s definition, we find phantom fixels where several ground-truth bundles share one orientation, and measure the rate at which streamlines entering with one bundle leave with another.
FiberCup serves as a sanity check. On HCP subjects, we use TractSeg-defined bundles as a plausibility reference and measure test–retest stability. We also report runtime against TractoTransformer's 43 minutes.
Three checks decide the question. First, without cuts, a nontrivial fraction of flow must lie in white-matter cycles, and the cuts must remove it. Second, the invalid-bundle count, especially among the systematic invalid bundles shared across challenge pipelines, must fall relative to AFODF-plus-filtering at equal valid-connection rate. Third, the gap between the LP bound and the rounded cost must stay small across subjects.
If the second check fails while the first succeeds, the conclusion is also informative. It would mean that systematic invalid bundles are geometrically plausible given orientation alone, so no connectivity constraint can remove them without additional anatomical priors.
References
- The challenge of mapping the human connectome based on diffusion tractography
- Prevalence of white matter pathways coming into a single white matter voxel orientation: The bottleneck issue in tractography
- Microstructure Informed Tractography: Pitfalls and Open Challenges
- On the integrality gap of small Asymmetric Traveling Salesman Problems: A polyhedral and computational approach
- Global Tractography with Embedded Anatomical Priors for Quantitative Connectivity Analysis
- A Random Riemannian Metric for Probabilistic Shortest-Path Tractography.
- Mitigating gyral bias in cortical tractography via asymmetric fiber orientation distributions
- A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- TractoTransformer: Diffusion MRI Streamline Tractography using CNN and Transformer Networks
- DeepTract: A Probabilistic Deep Learning Framework for White Matter Fiber Tractography