  Stochastic processes on graphs can describe a great variety of phenomena
ranging from neural activity to epidemic spreading. While many existing methods
can accurately describe typical realizations of such processes, computing
properties of extremely rare events is a hard task. Particularly so in the case
of recurrent models, in which variables may return to a previously visited
state. Here, we build on the matrix product cavity method, extending it
fundamentally in two directions: first, we show how it can be applied to Markov
processes biased by arbitrary reweighting factors that concentrate most of the
probability mass on rare events. Second, we introduce an efficient scheme to
reduce the computational cost of a single node update from exponential to
polynomial in the node degree. Two applications are considered: inference of
infection probabilities from sparse observations within the SIRS epidemic
model, and the computation of both typical observables and large deviations of
several kinetic Ising models.
