Probability-Invariant Random Walk Learning on Gyral Folding-Based Cortical Similarity Networks for Alzheimer's and Lewy Body Dementia Diagnosis

This paper proposes a probability-invariant random walk framework that classifies individualized gyral folding-based cortical similarity networks without requiring explicit node alignment, thereby overcoming anatomical heterogeneity to achieve robust diagnosis of Alzheimer's disease and Lewy body dementia.

The Gist

Imagine your brain is a vast, bustling city. In a healthy city, the roads (neural connections) and buildings (brain regions) are organized in a way that supports smooth traffic and daily life. But in diseases like Alzheimer's and Lewy Body Dementia, the city starts to change. Roads get blocked, buildings crumble, and the layout becomes chaotic.

The big problem for doctors is that these two diseases look very similar on the surface, even though they are caused by different things and need different treatments. It's like trying to tell the difference between a city that is suffering from a power outage versus one that is suffering from a water shortage; if you only look at the dark streets, you might not know which one it is.

To solve this, scientists usually try to map the city using a standard "atlas" (like a generic map of New York City applied to every city in the world). But the problem is that every human brain is unique. The "streets" (gyri and sulci) fold in slightly different patterns for every single person. Trying to force a standard map onto a unique, wiggly brain is like trying to fit a square peg in a round hole—it misses the details and creates errors.

The New Solution: "The Anonymous Tourist"

The researchers in this paper, led by Minheng Chen and Dajiang Zhu, came up with a clever new way to map these unique brain cities without needing a standard map. They call their method PaIRWaL (Probability-Invariant Random Walk Learning).

Here is how it works, using a simple analogy:

1. The Problem with "Name Tags"

Imagine you are trying to compare two different cities. In old methods, you would say, "Let's compare the Central Park of City A to the Central Park of City B." But what if City A doesn't have a Central Park, or its "park" is in a totally different spot? You can't compare them directly because the "name tags" don't match.

In the brain, the "folding points" (where the brain wrinkles) are unique to every person. One person might have 500 folds, another 550. They are in different places. You can't just line them up and compare them.

2. The "Anonymous Tourist" (Random Walks)

Instead of trying to match specific landmarks, the researchers send out a tourist (a computer algorithm) into the brain city.

• The tourist starts at a random spot.
• They take a walk, moving from one neighborhood to another based on how similar the neighborhoods look (e.g., how thick the "walls" are or how deep the "alleys" are).
• Crucially, the tourist doesn't care about the names of the places they visit. They don't say, "I am at the Library." They just say, "I moved from a quiet, thick-walled room to a busy, thin-walled hallway."

This is called a Random Walk. Because the tourist doesn't rely on specific names, it doesn't matter if the cities have different numbers of buildings or if the buildings are in different orders. The pattern of the walk tells the story.

3. The "Anatomy-Aware" Notebook

The tourist carries a special notebook. As they walk, they write down:

• The steps: "I went from a small room to a big room."
• The neighborhood: "I noticed a neighbor I saw earlier."
• The region type: "I am currently in the 'Memory District' or the 'Vision District'." (This is the "Anatomy-Aware" part. They know what kind of area they are in, even if they don't know the specific name of the building).

By recording these steps as a sequence of events, the computer creates a "fingerprint" of the brain's layout.

4. The Detective's Conclusion

Finally, a "Detective" (the AI model) reads these notebooks.

• If the tourist's notebook from a patient with Alzheimer's shows a specific pattern of chaotic, broken connections in the memory districts, the detective flags it.
• If the notebook from a Lewy Body patient shows a different pattern of disruption, the detective flags that instead.

Because the method doesn't care about matching specific buildings, it works perfectly even if the patients have very different brain shapes. It focuses on the flow and structure of the city, not the address labels.

Why is this a Big Deal?

• It's Personal: It respects the unique "folding" of every human brain, rather than forcing them into a generic mold.
• It's Accurate: In tests with hundreds of patients, this method was better at telling the difference between Alzheimer's and Lewy Body Dementia than any previous method.
• It's Robust: It works even when the data is messy or the brain shapes are very different, which is common in real-world medical cases.

The Bottom Line

Think of this new method as a GPS that doesn't need street names. Instead of asking, "Where is Main Street?", it asks, "How does the traffic flow through the city?" By analyzing the flow patterns of the brain's unique folds, this AI can spot the subtle differences between two very similar diseases, helping doctors give the right treatment to the right patient sooner.

Technical Summary

1. Problem Statement

The paper addresses the critical challenge of differentiating between Alzheimer's Disease (AD) and Lewy Body Dementia (LBD), two neurodegenerative disorders with overlapping clinical symptoms but distinct pathological mechanisms and treatment needs.

• Limitations of Current Methods:
  • Atlas-Based Approaches: Traditional brain network models rely on standard anatomical atlases (parcellation). These often obscure individualized anatomical details and fail to capture disease-sensitive structural patterns specific to cortical folding.
  • Gyral Folding Networks: While using three-hinge gyri (3HGs) as nodes offers a biologically grounded, individualized alternative, existing graph learning methods struggle with them due to:
    1. Lack of Node Correspondence: High inter-individual variability in cortical folding makes it impossible to establish reliable one-to-one node alignment across subjects.
    2. Variable Topology: The number of detected 3HG landmarks varies per subject, resulting in graphs of different sizes and topologies.
  • The Gap: Most existing graph neural networks (GNNs) assume fixed node ordering or require strict node alignment, rendering them ineffective for these highly variable, individualized networks.

2. Methodology: PaIRWaL Framework

The authors propose PaIRWaL (Probability-Invariant Random Walk Learning), a framework designed to classify individualized gyral folding networks without explicit node alignment. The method ensures permutation invariance (the output distribution remains the same regardless of how nodes are indexed) and size invariance.

The framework consists of three core components (illustrated in Fig. 1 of the paper):

A. Graph Construction

• Nodes: Automatically extracted 3HGs from T1-weighted MRI surfaces.
• Edges: Constructed based on cortical similarity. Morphometric features (thickness, curvature, sulcal depth, etc.) are extracted from 5-ring neighborhoods around each 3HG.
• Connectivity: A symmetric Kullback-Leibler divergence measures similarity. The graph is built by retaining the Minimum Spanning Tree and the top 10% of strongest edges to ensure connectivity while suppressing noise.
• Node Attributes: Each 3HG is represented by an 81-dimensional morphometric fingerprint.

B. Probability-Invariant Random Walk Sampling

To handle variable graph sizes and lack of alignment, the method samples random walks rather than using fixed graph structures.

• Conductance-Based Sampling: A random walk is defined as a first-order Markov chain.
• Minimum Degree Local Rule (MDLR): The transition probability between nodes $u$ and $v$ is inversely proportional to the minimum degree of the two nodes ($c_G(u,v) = 1/\min(\deg(u), \deg(v))$).
  • Significance: Since node degrees are preserved under graph isomorphism, this rule ensures the walk distribution depends only on the graph structure, not node identities, satisfying the probability invariance condition.
• Non-backtracking: A constraint is added ($v_{t+1} \neq v_{t-1}$) to encourage exploration.

C. Anatomy-Aware Anonymized Walk Recording (A3WR)

The sampled walks are converted into machine-readable sequences that preserve structural and anatomical information without revealing node identities.

• Anonymization: Instead of using fixed node IDs, vertices are mapped to unique identifiers based on their order of first appearance in the walk.
• Sequence Encoding: Each step in the walk generates an event sequence containing:
  1. The anonymized node ID.
  2. Named Neighbors: Relations to previously visited neighbors (capturing local subgraph structure).
  3. ROI Attribute Tokens: Anatomical priors (Region-of-Interest labels) attached to the node.
  4. Morphometric Embeddings: Continuous feature vectors injected at the walk position.
• Invariance Guarantee: Because the encoding relies on relative order and isomorphism-invariant attributes (like ROI labels), the resulting sequence distribution is invariant to node permutations.

D. Reader and Aggregation

• Reader Network: A lightweight Multi-Layer Perceptron (MLP) processes the encoded sequence to predict class labels.
• Monte Carlo Aggregation: Since the sampling is stochastic, the final prediction is the average of predictions from $K$ random walks per graph, yielding a robust estimator.

3. Key Contributions

1. Novel Framework: Introduction of PaIRWaL, the first method to classify gyral folding networks using probability-invariant random walks, eliminating the need for explicit node alignment.
2. Theoretical Guarantee: Formal definition of probability invariance for stochastic graph models, ensuring that isomorphic graphs yield identical prediction distributions.
3. Anatomy-Aware Encoding: Development of the A3WR module, which integrates structural transitions, local neighborhood relations, and anatomical priors into a permutation-invariant sequence.
4. Robustness to Heterogeneity: The method successfully handles the variable node counts and topologies inherent in individualized cortical folding data, a limitation of standard GNNs.

4. Experimental Results

• Dataset: 303 subjects (108 Normal Controls, 90 AD, 105 LBD) from the University of Cambridge/MILOS project.
• Tasks: Multiclass classification (AD/LBD/CN) and three binary tasks (AD vs. CN, LBD vs. CN, AD vs. LBD).
• Baselines: Compared against 5 gyral folding-based models (GraphStat, GraphSAGE, GIN, GAT, AMP-GCN) and 3 atlas-based models (BrainNetCNN, BNT, CPSSM).
• Performance:
  • PaIRWaL achieved the highest accuracy (71.93%) and MCC (58.22%) in the multiclass task, outperforming all baselines.
  • It showed significant improvements (p < 0.05) in the challenging AD vs. LBD binary classification task, where differentiating the two dementias is most difficult.
• Ablation Studies: Removing components like anonymization, named neighbors, or ROI tokens significantly degraded performance, confirming the necessity of the full architecture.
• Sensitivity Analysis: Performance stabilized with walk lengths of 64–128 and required only a small number of sampled walks ($K=8$) for reliable estimates, ensuring computational efficiency.
• Interpretability: Heatmap visualizations revealed that the model focused on specific, anatomically meaningful cortical folding regions known to be associated with dementia pathology.

5. Significance

This work provides a robust solution for dementia diagnosis using neuroimaging data that respects individual anatomical uniqueness. By moving away from rigid atlas-based parcellation and explicit node alignment, PaIRWaL leverages the natural variability of cortical folding as a feature rather than a bug. The framework's ability to handle variable-sized, unaligned graphs makes it highly applicable to clinical settings where patient anatomy varies significantly due to aging and disease progression. The results suggest that probability-invariant random walk learning is a powerful paradigm for analyzing complex, individualized biological networks.