# Information Geometry of Absorbing Markov-Chain and Discriminative Random Walks

arXiv: https://arxiv.org/abs/2602.08185 · HTML: https://mlsanity.com/paper/2602.08185/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 33 references that are in the map.
- First posted on arXiv 9 Feb 2026.

## Builds on (most cited first, 4 of 4)

- [A Survey of Graph Neural Networks for Social Recommender Systems](https://mlsanity.com/paper/2212.04481/) (2022)
- [LabelRank: A Stabilized Label Propagation Algorithm for Community Detection in Networks](https://mlsanity.com/paper/1303.0868/) (2013)
- [Node Centralities and Classification Performance for Characterizing Node Embedding Algorithms](https://mlsanity.com/paper/1802.06368/) (2018)
- [Graph-Smoothed Bayesian Black-Box Shift Estimator and Its Information Geometry](https://mlsanity.com/paper/2505.16251/) (2025)

## Abstract (arXiv)

Discriminative Random Walks (DRWs) are a simple yet powerful tool for semi-supervised node classification, but their theoretical foundations remain fragmentary. We revisit DRWs through the lens of information geometry, treating the family of class-specific hitting-time laws on an absorbing Markov chain as a statistical manifold. Starting from a log-linear edge-weight model, we derive closed-form expressions for the hitting-time probability mass function, its full moment hierarchy, and the observed Fisher information. The Fisher matrix of each seed node turns out to be rank-one, taking the quotient by its null space yields a low-dimensional, globally flat manifold that captures all identifiable directions of the model. Leveraging the geometry, we introduce a sensitivity score for unlabeled nodes that bounds, and in one-dimensional cases attains, the maximal first-order change in DRW betweenness under unit Fisher perturbations. The score can lead to principled strategies for active label acquisition, edge re-weighting, and explanation.