Learning the Influence Graph of a Markov Process that Randomly Resets to the Past

2025/09/19 by S. Senthil, Senthil, Sudharsan, Avhishek Chatterjee +1
Computer Science · Decision Sciences · Physics and Astronomy · #Complex Network Analysis Techniques #Data Quality and Management #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.2509.16129

openalex publication_date 2025/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Learning the influence graph G of a high-dimensional Markov process is central to many application domains, including social networks, neuroscience, and financial risk analysis. However, in many of these applications, future states of the process are occasionally and unpredictably influenced by a distant past state, thus destroying the Markovianity. To study this practical issue, we propose the past influence model (PIM), which captures the occasional "random resets to past" by modifying the Markovian dynamics in [1], which, in turn, is a non-linear generalization of the dynamics studied in [2], [3]. The recursive greedy algorithm proposed in this paper recovers any bounded degree G when the number of ``jumps back in time" is order-wise smaller than the total number of samples, and the algorithm does not require memory.

Citations

• Learning Gaussian DAG Models without Condition Number Bounds
• Learning the Influence Graph of a High-Dimensional Markov Process with Memory
• Mixing Times and Structural Inference for Bernoulli Autoregressive Processes
• Greedy Learning of Markov Network Structure
• Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms

Related

• Learning the Influence Graph of a High-Dimensional Markov Process with Memory
• Learning Temporal Dependence from Time-Series Data with Latent Variables
• Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms
• Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
• Robust causal structure learning with some hidden variables