Unscrambling disease progression at scale: fast inference of event permutations with optimal transport

Peter A. Wijeratne, Daniel C. Alexander

Abstract

Understanding the temporal evolution of chronic diseases is a fundamental challenge in clinical research, often hindered by the lack of longitudinal data. While Event-Based Models (EBMs) provide a framework for reconstructing disease trajectories from cross-sectional snapshots, they suffer from a combinatorial explosion that limits their resolution. This paper introduces the variational event-based model (vEBM), a framework that leverages optimal transport and variational inference to scale disease progression modeling to high-dimensional, pixel-level data. By transforming a discrete permutation problem into a continuous optimization task, the vEBM achieves a 1,000x speedup over traditional methods, enabling the first pixel-level tracking of Alzheimer’s disease and Age-related Macular Degeneration (AMD).

Introduction: The "Snapshot" Problem

Chronic diseases like Alzheimer’s evolve over decades, yet clinical datasets typically consist of "snapshots"—single observations from many different patients at various stages of illness. Reconstructing a coherent timeline from these disparate points is essential for early diagnosis and clinical trial design.

Event-Based Models (EBMs) were developed to address this by treating disease progression as a sequence of discrete events, such as a specific biomarker becoming abnormal. However, the computational cost of finding the optimal sequence is prohibitive. For a model with $N$ features, there are $N!$ possible permutations. This "combinatorial explosion" has historically forced researchers to aggregate high-resolution imaging data into a few dozen coarse anatomical regions, losing significant granular information in the process.

Methodology: Scaling the Combinatorial Wall

The variational event-based model (vEBM) overcomes these scaling limits by replacing discrete searching with continuous optimization. The framework relies on two primary mathematical innovations:

  1. Optimal Transport (OT) and the Sinkhorn-Knopp Algorithm: Instead of evaluating every possible sequence, the vEBM treats the problem as "transporting" latent disease events to their optimal positions in a timeline. By utilizing the Sinkhorn-Knopp algorithm, the model approximates a permutation matrix within the Birkhoff polytope—a continuous space of doubly stochastic matrices. This shift allows the model to use efficient, gradient-based optimization.
  2. Variational Inference (VI) and Gumbel-Sinkhorn: The authors define a differentiable Variational Evidence Lower Bound (ELBO). Using the Gumbel-Sinkhorn distribution as a reparameterization trick for permutations, the model becomes trainable via standard backpropagation and the Adam optimizer.

By "softening" the rigid sequence into a continuous probability space, the vEBM can be solved efficiently and then "hardened" back into a discrete sequence using the Hungarian algorithm.

Experimental Validation

The vEBM was validated across three distinct datasets to test its speed, accuracy, and clinical relevance:

  • Synthetic Benchmarks: Used to compare vEBM against existing models like ALPACA. In simulations with 200 features, the vEBM was 1,000 times faster while maintaining superior accuracy and robustness to noise.
  • Alzheimer’s Disease Neuroimaging Initiative (ADNI): The model analyzed voxel-level brain maps from 816 individuals. It successfully reconstructed the known spread of Alzheimer’s—moving from the ventricles to sub-cortical regions and finally the cortex—but at a much finer grain than previously possible.
  • Duke University Ophthalmology 2013: The model processed retinal thickness maps from 384 individuals to study Age-related Macular Degeneration (AMD), showcasing pixel-level progression from the center of the eye outward.

Key Insights and Results

The End of Manual Dimensionality Reduction

Traditionally, researchers had to manually select "regions of interest" (ROIs) to make EBMs computationally tractable. The vEBM is efficient enough to handle raw pixel data directly. This allows the model to discover pathological patterns autonomously, identifying subtle, asymmetric progression in Alzheimer’s that human-defined boundaries might overlook.

Interpretability at Scale

Unlike many high-dimensional "black box" models (e.g., deep learning autoencoders), the vEBM remains highly interpretable. Every event in the inferred sequence maps directly back to the original feature space, whether that be a specific pixel in a brain scan or a clinical test score.

Clinical Utility

The vEBM provides a robust mechanism for "staging" individual patients. By comparing a single patient's snapshot against the inferred global timeline, the model can accurately place them on the disease trajectory. This capability is vital for identifying the right participants for clinical trials at the right time.

Limitations and Future Directions

While the vEBM represents a significant leap forward, some challenges remain. The current implementation uses dense matrices, which can lead to memory constraints when scaling to extremely high-resolution 3D volumes. Future iterations may utilize sparse matrix representations to further reduce the hardware requirements. Additionally, while the framework supports uncertainty quantification, further research is needed to fully integrate confidence intervals into the inferred sequences. Finally, the model still requires images to be registered to a common template to ensure feature correspondence across the cohort.

Conclusion

The vEBM shifts the paradigm of disease progression modeling toward "low-compute, high-interpretability" AI. By achieving a 1,000x speedup, it enables researchers to move beyond coarse regional summaries to high-resolution, pixel-level insights, potentially uncovering new biomarkers and therapeutic windows for complex chronic diseases.

Summary updated

BibTeX
@inproceedings{wijeratne2024unscrambling,
  author = {Peter A. Wijeratne and Daniel C. Alexander},
  title = {{Unscrambling disease progression at scale: fast inference of event permutations with optimal transport}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=SoYCqMiVIh},
}
Figure