Trajectory-informed graph-based clustering for longitudinal cancer subtyping

This paper proposes a novel trajectory-informed graph-based clustering method that integrates multi-modal longitudinal data to identify clinically relevant cancer subtypes with distinct prognostic trajectories, thereby advancing personalized oncology beyond static biomarker approaches.

The Gist

Imagine you are trying to sort a massive pile of puzzle pieces to find which ones fit together to make a complete picture. In the world of cancer, these "puzzle pieces" are patients. For decades, doctors have tried to group patients into subtypes (like "Type A" or "Type B" cancer) to decide on the best treatment.

The Old Way: Taking a Single Snapshot
Traditionally, doctors looked at a patient's cancer like a still photograph. They took a biopsy (a tiny sample of tissue), looked at it under a microscope, and said, "Okay, this looks like Group A."

But cancer isn't a still photo; it's a movie. It changes, grows, and reacts to treatment over time. A patient might look like "Group A" on day one, but by month six, their cancer might have evolved into something completely different. The old methods missed the plot twists, the character development, and the ending of the movie.

The New Way: Watching the Whole Movie
This paper proposes a new method called "Trajectory-Informed Graph-Based Clustering." That's a mouthful, so let's break it down with some analogies.

1. The "Social Network" of Patients (The Graph)

Imagine you want to find your soulmates. You could look at their static profile pictures (height, eye color, job). But a better way is to see how they move through life. Do they travel the same paths? Do they face similar challenges? Do they react to storms in the same way?

The authors built a digital social network where every patient is a node (a dot). Instead of connecting dots based on who looks alike, they connect dots based on who has lived through similar life stories.

• The "Life Story" (Trajectory): They tracked patients through key chapters: Diagnosis → Treatment → Surveillance → Relapse (the cancer coming back) → Death.
• The "Movie Reel" (Longitudinal Data): They didn't just look at the start; they looked at the whole reel, including how the tumor changed shape on CT scans over time.

2. The "Smart Matchmaker" (The Algorithm)

The computer acts like a super-smart matchmaker. It asks two questions for every pair of patients:

1. Are you similar at the start? (Do you have similar age, gender, and initial tumor features?)
2. Did you travel the same road? (Did you respond to chemo the same way? Did your tumor shrink or grow at the same speed? Did you relapse at the same time?)

The algorithm draws a line between patients who traveled similar roads. If Patient A and Patient B both had a tumor that shrank quickly, then relapsed slowly, they get a strong line connecting them. If Patient A's tumor grew fast and Patient B's stayed still, the line is weak or non-existent.

3. Finding the "Tribes" (Clustering)

Once all the lines are drawn, the computer looks for clusters or "tribes."

• Tribes aren't just about who looks alike; they are about who survives alike.
• The goal is to find groups where everyone in the group has a very similar "movie ending" (prognosis).

The Real-World Test: The Liver Metastasis Experiment

The team tested this on 102 patients with colorectal cancer that had spread to the liver. They used a special kind of "X-ray vision" (radiomics) to turn CT scans into thousands of data points, describing the tumor's texture and shape like a fingerprint.

They ran the "matchmaker" algorithm three different ways, trying to see which "movie plot" made the most sense:

1. Plot A: Diagnosis → Treatment → Death.
2. Plot B: Diagnosis → Treatment → Relapse.
3. Plot C: Diagnosis → Treatment → (Relapse OR Death).

The Results:

• Plot A was the winner for predicting who would live the longest. It successfully split the patients into two clear groups: a "High-Risk Tribe" (who passed away relatively quickly) and a "Low-Risk Tribe" (who lived much longer, often 10+ years).
• The "Aha!" Moment: The algorithm found that specific changes in the tumor's texture (how "grainy" or "smooth" it looked on the scan) were the best predictors of which tribe a patient belonged to. It wasn't just about the size of the tumor; it was about the story the tumor told through its texture over time.

Why Does This Matter?

Think of it like weather forecasting.

• Old Method: Looking at the sky right now and saying, "It's cloudy, so it might rain."
• New Method: Looking at the pressure systems, wind patterns, and temperature changes over the last week to say, "This storm system is moving fast and will hit hard in 3 days."

By understanding the trajectory (the path) rather than just the snapshot (the current state), doctors can:

• Predict the future better: Know who is likely to relapse before it happens.
• Personalize treatment: Give the "High-Risk Tribe" stronger, more aggressive treatment immediately, while sparing the "Low-Risk Tribe" from harsh drugs they might not need.
• Design better trials: Test new drugs on groups of patients who are actually similar in how their disease moves, rather than just how it looks.

In a Nutshell:
This paper teaches us that to understand cancer, we can't just look at a photo of the patient. We have to watch the movie. By using math to map out the "journey" of every patient, we can group them into tribes that share the same destiny, allowing doctors to write a better script for their treatment.

Technical Summary

Here is a detailed technical summary of the paper "Trajectory-informed graph-based clustering for longitudinal cancer subtyping."

1. Problem Statement

Cancer subtyping is essential for prognosis and personalized treatment, yet current methods rely heavily on static, cross-sectional data (e.g., biopsy scores, single-timepoint imaging). These approaches fail to capture:

• Biological heterogeneity: The complex variation in tumor evolution across individuals.
• Temporal dynamics: The longitudinal progression of the disease, including transitions between clinical states (e.g., therapy, relapse, surveillance, death).
• Multimodal integration: The need to combine static covariates (demographics) with time-varying data (imaging phenotypes, treatment responses).

The authors argue that existing clustering methods (e.g., Profile Regression, Nearest Shrunken Centroid, Variational Deep Survival Clustering) often treat time as an afterthought, lack interpretability, or fail to model the stochastic nature of disease transitions effectively.

2. Methodology

The paper proposes a Trajectory-Informed Graph-Based Clustering framework. The core innovation is learning a patient similarity graph where edge weights are not pre-defined but are jointly learned from static covariates and dynamic disease trajectories modeled via Multi-State Models (MSMs).

A. Multi-State Model (MSM) Formulation

The disease progression is modeled as a stochastic process $\{X(t)\}$ moving through a finite set of states $S = \{1, \dots, K\}$ (e.g., Healthy $\to$ Diagnosis $\to$ Therapy $\to$ Relapse $\to$ Death).

• Transitions: Modeled using Stratified Cox Proportional Hazards models. For each transition $k$, the hazard function is:
  $$\lambda_k(t|X_k) = \lambda_0(t) \exp(\beta_k^T X_k)$$
  where $X_k$ represents covariates specific to that transition, and $\beta_k$ are regression coefficients.
• Distance Metric: A patient similarity distance $d(i, j)$ is constructed by combining:
  1. Covariate Distance: Euclidean distance between baseline features ($d_{cov}$).
  2. MSM-based Distance: A weighted distance based on the difference in predicted transition hazards. This uses the log-hazard ratio and weights it by the inverse variance of the estimated coefficients ($\hat{Var}(\beta_k)$) to account for estimation uncertainty:
     $$d_{msm}(i, j) = \sum_{k=1}^K w_k \|\beta_k^T (X_{i,k} - X_{j,k})\|^2, \quad w_k = \frac{1}{\hat{Var}(\beta_k)}$$

B. Joint Optimization Framework

The method learns the similarity matrix $S$ (defining the graph) and the MSM parameters $\beta$ simultaneously.

• Objective Function: The optimization minimizes a composite loss:
  1. Stratified Cox Partial Log-Likelihood: To fit the survival/transition models.
  2. $\ell_1$-Regularization: To enforce sparsity in $\beta$ (feature selection).
  3. Similarity-Regularized Distance: Minimizing the weighted distance between patients $i$ and $j$ if they are assigned high similarity ($S_{ij}$).
  4. Spectral Clustering Constraint: A term $\alpha \cdot \text{Tr}(U^T L U)$ is added, where $L$ is the graph Laplacian and $U$ contains cluster indicators. This forces the graph to have exactly $c$ connected components (clusters).

C. Optimization Algorithm

The non-convex joint problem is solved via Alternating Minimization (Block Coordinate Descent):

1. Update $\beta$: Fixed $S$ and $U$. Solved using Proximal Gradient Descent (handling the non-smooth $\ell_1$ term).
2. Update $S$: Fixed $\beta$ and $U$. Solved analytically for each row, enforcing non-negativity and row-stochasticity (sum to 1). A sparsity mechanism is applied to select only the $\kappa$-nearest neighbors.
3. Update $U$: Fixed $\beta$ and $S$. Solved by computing the eigenvectors of the Laplacian $L$ corresponding to the $c$ smallest eigenvalues.

3. Key Contributions

1. Novel Framework: A unified approach that integrates longitudinal clinical trajectories (via MSMs) with multimodal data (static covariates + time-varying imaging) into a single graph-based clustering model.
2. Learned Similarity: Unlike traditional methods that use fixed distance metrics, the similarity graph is data-driven and informed by the risk of disease progression, making it sensitive to both phenotypic and genotypic evolution.
3. Theoretical Guarantees: The paper provides a convergence analysis proving the existence and uniqueness of the global minimum under specific conditions.
4. Interpretability: The model yields sparse regression coefficients (identifying key biomarkers) and distinct patient subgroups with clear clinical trajectories, avoiding the "black box" nature of deep learning survival models.

4. Results

A. Simulation Studies

The authors validated the method on synthetic data with varying dimensions (sample size, number of states, censoring rates).

• Prediction Accuracy: The proposed model achieved a significantly higher Concordance Index (C-index) (0.94) and Time-Dependent AUROC (0.98) compared to baselines (Cox-only, Fixed-Graph + Cox, Random Survival Forest).
• Cluster Recovery: The method successfully recovered latent patient strata, achieving high Adjusted Rand Index (ARI) and Adjusted Mutual Information (AMI), outperforming tree-based and standard graph methods.
• Ablation Study: Removing any component (similarity penalty, neighbor smoothness, or sparsity) degraded performance, confirming the necessity of the joint learning structure.
• Scalability: The algorithm demonstrated near-linear scaling with sample size in log-log plots.

B. Real-World Application: Colorectal Liver Metastases (CRLM)

The method was applied to a cohort of 98 patients with colorectal liver metastases, utilizing:

• Data: Baseline demographics, longitudinal radiomic features (109 features from CT scans at baseline and post-chemotherapy), and survival outcomes (relapse, death).
• Three MSM Configurations:
  1. Model 1 (Baseline $\to$ Therapy $\to$ Death): Identified 2 subgroups with significant survival separation (Log-Rank $p=0.04$). One group had a 50% 10-year survival rate, while the other declined rapidly. Key biomarker: Intensity-based skewness.
  2. Model 2 (Baseline $\to$ Therapy $\to$ Relapse): High classifier AUC (0.94) but poor survival separation (Log-Rank $p=0.05$, overlapping curves). Suggests clustering was driven by feature similarity rather than outcome heterogeneity.
  3. Model 3 (Competing Risks: Relapse vs. Death): Achieved the best Log-Rank p-value (0.003) and balanced performance. It successfully stratified patients by relapse risk, though death risk stratification was limited by low event frequency.

5. Significance and Conclusion

• Clinical Utility: The framework successfully identifies patient subtypes that are not only statistically distinct but also clinically actionable. For instance, Model 1 identified a high-risk group that could benefit from intensified monitoring, while Model 3 highlighted the importance of relapse prevention over post-relapse stratification.
• Bridging Static and Dynamic: The study demonstrates that integrating time-resolved imaging (radiomics) with survival modeling via graph learning uncovers prognostic patterns invisible to static analysis.
• Future Directions: The authors note limitations regarding the Markovian assumption (ignoring history beyond the current state) and the linear combination of competing risks. Future work aims to relax these assumptions to better capture complex patient heterogeneity.

In summary, this paper presents a robust, interpretable, and mathematically grounded method for cancer subtyping that leverages the full trajectory of a patient's disease, offering a significant advancement over static, cross-sectional clustering approaches.