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

Sudharsan Senthil, Avhishek Chatterjee · 2025

Read Learning the Influence Graph of a Markov Process that Randomly Resets to Past by Sudharsan Senthil, Avhishek Chatterjee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-16129.txt.

Introduction

Most processes forget their distant past, but real systems in social, brain, and finance data sometimes jump back to an old state. Sudharsan Senthil and Avhishek Chatterjee model such random resets to the past and ask how to learn the hidden influence graph behind the data. The graph shows which parts of the system drive which others.

Their stepwise greedy method rebuilds any graph of bounded links, as long as the jumps back stay rare compared with the sample count. The method needs no stored memory of past steps. That makes it suited to long data streams where storing all history is not an option.

Catalog record

CREATORSudharsan Senthil, Avhishek Chatterjee
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-16129

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning the Influence Graph of a Markov Process that Randomly Resets to Past Sudharsan Senthil, Avhishek Chatterjee Abstract Learning the influence graph G G of a high-dimensional Markov processes is a challenging problem. Prior work [ 1 ] addresses this task when the process has finite memory. However, the more general regime in which the system probabilistically “jumps back in time”—so that the state at t + 1 t{+}1 depends on a sample from a distant past t − d t{-}d —remains unexplored. The process with probabilistic resets can be modeled as a Markov process with memory, but estimations become computationally expensive. To tackle this, this letter introduces PIMRecGreedy , a modification of the RecGreedy algorithm from [ 2 ] , originally designed for i.i.d. samples. The proposed method doesn’t assume memory, therefore requires no prior knowledge of d d and recovers G G with high probability even without access to the specific time indices at which such temporal jumps occur, and without imposing any constraints on the graph structures. I Introduction Learning the underlying influence (causal) graph G of a high-dimensional multivariate stochastic process has applications in multiple domains, including online social networks, neural and biological signal processing, and financial risk analysis [ 3 , 4 , 5 , 6 ] . The existing literature focuses on learning the influence graphs of Markov stochastic processes. Motivated by important phenomena in social networks and financial risk analysis, in this paper we study the problem of learning the influence graphs of a class of stochastic processes whose distant past occasionally influences the future in an unpredictable way. In a multivariate Markov dynamic with an influence graph, the next state of a process variable depends on the current states of process variables that have directed edges to it. We study the following modification of such a Markov process. The future states depend on the current states with probability p , and with probability 1-p they depend on the states d time-steps back. Intuitively, it is a process in which a Markovian evolution is randomly reset to a distant past state. The task is to recover the influence graph from samples of the process observed over T time-steps, without knowing the instances when the “random resets to the past” occurred. This phenomenon appears in many domains, where the distant past occasionally influences the future in addition to present. For instance, in social networks, users may sometimes form opinions based on older interactions rather than the latest activities. In many social networks, agents express short opinions in binary form (likes/dislikes), which in turn influence the beliefs of others in the network. Occasionally, opinions expressed in the distant past resurface and shape the opinions of others. Similarly, in financial markets, sudden shocks or crises often resurface after long intervals, influencing present-day risk perception and investment behavior. For example, an unexpected downturn may trigger responses not only to recent market fluctuations but also to memories of past crises (such as the 2008 financial collapse), leading investors to update their portfolios based on distant past rather than current scenario [ 7 , 8 ] . The social network model proposed in this paper captures the phenomenon in which the network as a whole is influenced by the past, rather than just a subset of participants. We also model the reactions of the network participants with a binary alphabet, though the framework can be easily extended to problems involving larger observable symbol sets. Though analytical guarantees for learning processes with random resets to past have not been studied before, a large body of work has addressed the problem of learning i.i.d. graphical model structures. Early work by Chow and Liu [ 9 ] introduced tree-structured approximations for discrete distributions, and subsequent efforts extended these ideas to bounded tree-width Markov networks [ 10 ] . In high-dimensional settings, algorithms based on sparsity have been popular, including \ell_{1} -regularized logistic regression for Ising models [ 11 ] and group-sparse regularization techniques [ 12 ] . Other approaches exploit structural properties: Bresler et al. [ 13 ] proposed reconstruction methods for Markov random fields, while Wu et al. [ 14 ] investigated loosely connected graphs. Greedy methods have also proven effective for scalable structure recovery [ 15 ] . And, more recently [ 16 ] provided algorithms for learning directed Gaussian graphical models with sample complexity. The algorithm proposed in this paper is for learning processes with random resets to past, which is a generalization of the RecGreedy algorithm introduced in [ 2 ] for i.i.d. samples. Recently, a similar approach was adopted in [ 1 ] to learn Markovian processes without random resets to past, but with a finite memory. The paper is organized as follows. In Section II we introduce the Past Influence Model , and describe how its evolves over discrete time steps. In Section III we define the learning problem, followed by Section IV , where we propose the PIMRecGreedy algorithm, explaining how it works and why it is more effective than simply considering a Markov process with a large enough memory, along with its sample complexity theorem. Section V presents the performance of PIMRecGreedy across varying sample sizes The proof of Theorem 1 is provided in the Appendix. II The Social Network Model II-A Modeling Influence is modeled by a directed graph G=(V,E) , where nodes represent agents and directed edges represent influence. A directed edge (u,v)\in E means u influences v , and self-influence is modeled by (v,v)\in E . The neighborhood of v is \mathcal{N}_{v}:=\{u\neq v:(u,v)\in E\} . Time evolves in discrete steps. At each t , node v generates M_{v}(t)\sim\min(\text{Poisson}(\mu_{v}(X_{v}(t))),\overline{M})+1 independent Bernoulli samples with success probability X_{v}(t) , where \mu_{v}:[0,1]\to\mathbb{R} is L -Lipschitz and \overline{M} is a constant cap. Out of these samples, N_{v}(t) are ones. Each directed edge (u,v) has weight a_{uv}\in(0,1) , with \sum_{u}a_{uv}=1 . The internal parameter X_{v}(t) evolves via Eqn. ( II-A ) through three components: neighborhood observations \mathcal{N}_{v} , intrinsic bias l_{v} , and random fluctuation Z_{v}(t)\in[0,1] with mean 0<\bar{z}_{v}<1 and parameter \beta\in(0,1) . C(t)\sim\mathrm{Ber}(p) models the ignoring of the last d samples. The coefficient \alpha_{v} measures v ’s openness to external influence, trading off social input against internal dynamics. We call this the PIM (Past Influence Model) . We sometimes refer to the time-resets as tails. \displaystyle X_{v}(t+1)=(1-\alpha_{v})\left[(1-\beta)Z_{v}(t)+\beta l_{v}\right] \displaystyle+\alpha_{v}\sum_{u\in\mathcal{N_{v}}\cup v}\alpha_{uv}\left[C(t)\frac{N_{u}(t)}{M_{u}(t)}+(1-C(t))\frac{N_{u}(t-d)}{M_{u}(t-d)}\right] (1) II-B Some Mathematical Structures Given the observations \{(N_{v}(t),M_{v}(t)):v\in V\}_{t=0}^{T-1} , we define the variable Y_{v}(t):=\frac{N_{v}(t)}{M_{v}(t)} . We also define: • Y_{Q}(t):=\{Y_{v}(t):v\in Q\subseteq V\} • Y_{u,Q}(t):=\{Y_{v}(t):v\in Q\cup\{u\},Q\subseteq V\} • Y(t):=\{Y_{v}(t):v\in V\} If there was no coin toss in Eqn. ( II-A ) the process Y(t) becomes a normal Markov chain, \{W(t)\} . The directed conditional entropy of node v given a set Q is defined as: -\sum_{Y_{Q,v}(t)}\sum_{Y_{v}(t+1)}\mathbf{P}(Y_{v}(t+1),Y_{Q,v}(t))\log\mathbf{P}(Y_{v}(t+1)|Y_{Q,v}(t)), for some Q\subset V and v\not\in Q . In a stationary setting, this quantity becomes time-invariant and is denoted as H(v_{+}|v,Q) . This can be computed by first calculating the joint entropies H(v_{+},v,Q)=-\sum\mathbf{P}(Y_{v}(t+1),Y_{Q,v}(t))\log\mathbf{P}(Y_{v}(t+1),Y_{Q,v}(t)) and H(v,Q) and H(v,Q)=-\sum_{Y_{Q,v}(t)}\mathbf{P}(Y_{Q,v}(t))\log\mathbf{P}(Y_{Q,v}(t)) , in the former, the summation is over Y_{Q,v}(t) and Y_{v}(t+1) . In practice, the conditional entropy H(v_{+}|v,Q) cannot be computed directly due to unknown distributions. Instead, we estimate it from data and denote the estimate by \hat{H}(v_{+}|v,Q) . Specifically, we compute

Read the complete text