用信息几何解析判别式随机游走，揭示其内在结构与敏感性。
Information Geometry of Absorbing Markov-Chain and Discriminative Random Walks
- 将节点分类的随机游走建模为统计流形，推导出命中时间分布的闭式解。
- 发现种子节点的Fisher矩阵秩为1，构建低维平坦流形捕捉可识别方向。
- 提出敏感度评分，可用于主动标注、边权重调整和模型解释。
判别式随机游走（DRWs）是一种简单而强大的半监督节点分类工具，但其理论基础仍不完整。本文从信息几何视角重新审视DRWs，将吸收马尔可夫链上各类别命中时间分布视为一个统计流形。基于对数线性边权重模型，我们推导出命中时间概率质量函数、完整的矩阶层次结构以及可观测Fisher信息。每个种子节点的Fisher矩阵均为秩一，通过其零空间取商后得到一个低维且全局平坦的流形，该流形捕获了模型中所有可识别的方向。利用这一几何结构，我们引入了一种针对未标记节点的敏感度评分，该评分界定了在单位Fisher扰动下DRW介数的最大一阶变化，在一维情况下可达上界。该评分可指导有原则的主动标签获取、边权重重调及模型解释。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。