Information Geometry of Absorbing Markov-Chain and Discriminative Random Walks

• URL: http://arxiv.org/abs/2602.08185v1
• Date: Mon, 09 Feb 2026 01:09:09 GMT
• Title: Information Geometry of Absorbing Markov-Chain and Discriminative Random Walks
• Authors: Masanari Kimura,
• Abstract summary: Discrimi Random Walks (DRWs) are a simple yet powerful tool for semi-supervised node classification.<n>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.
• Score: 3.6381003292700425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Variational Bayesian Flow Network for Graph Generation [54.94088904387278]
  We propose Variational Bayesian Flow Network (VBFN) for graph generation.<n>VBFN performs variational lifting to a tractable joint Gaussian variational belief family governed by structured precisions.<n>On synthetic and molecular graph datasets, VBFN improves fidelity and diversity, and surpasses baseline methods.
  arXiv  Detail & Related papers  (2026-01-30T03:59:38Z)
• Inverting Self-Organizing Maps: A Unified Activation-Based Framework [39.146761527401424]
  We show that the activation pattern of a SOM can be inverted to recover the exact input under mild geometric conditions.<n>We introduce the Manifold-Aware Unified SOM Inversion and Control (MUSIC) update rule.<n>We validate the approach using synthetic Gaussian mixtures, the MNIST and the Faces in the Wild dataset.
  arXiv  Detail & Related papers  (2026-01-20T11:02:54Z)
• An approach to Fisher-Rao metric for infinite dimensional non-parametric information geometry [0.6138671548064355]
  Being infinite dimensional, non-parametric information geometry has long faced an "intractability barrier"<n>This paper introduces a novel framework to resolve the intractability with an Orthogonal Decomposition of the Tangent Space.<n>By defining the Information Capture Ratio, we provide a rigorous method for estimating intrinsic dimensionality in high-dimensional data.
  arXiv  Detail & Related papers  (2025-12-25T00:18:41Z)
• Graph Semi-Supervised Learning for Point Classification on Data Manifolds [16.311715311352597]
  We propose a graph semi-supervised learning framework for classification tasks on data manifold.<n>Motivated by the manifold hypothesis, we model data as points sampled from a low-dimensional $mathcalM subset mathbbRF$.<n>We show that, under uniform sampling from $mathcalM$, the generalization gap of the semi-supervised task diminishes with increasing graph size.
  arXiv  Detail & Related papers  (2025-06-13T19:52:54Z)
• Supervised Quadratic Feature Analysis: Information Geometry Approach for Dimensionality Reduction [0.0]
  Supervised dimensionality reduction maps labeled data into a low-dimensional feature space while preserving class discriminability.<n>We present Supervised Quadratic Feature Analysis (SQFA), a linear dimensionality reduction method that maximizes Fisher-Rao distances between class-conditional distributions.<n>We show that SQFA features support good classification performance with Quadratic Discriminant Analysis (QDA) on three real-world datasets.
  arXiv  Detail & Related papers  (2025-01-31T21:17:01Z)
• Lindbladian reverse engineering for general non-equilibrium steady states: A scalable null-space approach [49.1574468325115]
  We introduce a method for reconstructing the corresponding Lindbaldian master equation given any target NESS. The kernel (null-space) of the correlation matrix corresponds to Lindbladian solutions. We illustrate the method in different systems, ranging from bosonic Gaussian to dissipative-driven collective spins.
  arXiv  Detail & Related papers  (2024-08-09T19:00:18Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.<n>We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.<n>We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• Semi-Supervised Laplace Learning on Stiefel Manifolds [48.3427853588646]
  We develop the framework Sequential Subspace for graph-based, supervised samples at low-label rates. We achieves that our methods at extremely low rates, and high label rates.
  arXiv  Detail & Related papers  (2023-07-31T20:19:36Z)
• Quantum State Assignment Flows [3.7886425043810905]
  This paper flows for assignment as state spaces representing data associated with layers of an underlying weighted graph. The novel approach for data representation and analysis, including the representation of data across the graph by and entanglementization, is presented.
  arXiv  Detail & Related papers  (2023-06-30T18:29:14Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• On the Arbitrary-Oriented Object Detection: Classification based Approaches Revisited [94.5455251250471]
  We first show that the boundary problem suffered in existing dominant regression-based rotation detectors, is caused by angular periodicity or corner ordering. We transform the angular prediction task from a regression problem to a classification one. For the resulting circularly distributed angle classification problem, we first devise a Circular Smooth Label technique to handle the periodicity of angle and increase the error tolerance to adjacent angles.
  arXiv  Detail & Related papers  (2020-03-12T03:23:54Z)
• Unifying Graph Convolutional Neural Networks and Label Propagation [73.82013612939507]
  We study the relationship between LPA and GCN in terms of two aspects: feature/label smoothing and feature/label influence. Based on our theoretical analysis, we propose an end-to-end model that unifies GCN and LPA for node classification. Our model can also be seen as learning attention weights based on node labels, which is more task-oriented than existing feature-based attention models.
  arXiv  Detail & Related papers  (2020-02-17T03:23:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.