The matrix product approximation for the dynamic cavity method

Abstract

Stochastic dynamics of classical degrees of freedom, defined on vertices of locally tree-like graphs, can be studied in the framework of the dynamic cavity method which is exact for tree graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, and other technical, biological, and social networks. The central objects in the cavity method are edge messages -- conditional probabilities of two vertex variable trajectories. In this paper, we discuss a rather pedagogical derivation for the dynamic cavity method, give a detailed account of the novel matrix product edge message (MPEM) algorithm for the solution of the dynamic cavity equation as introduced in Phys. Rev. E 97, 010104(R) (2018), and present optimizations and extensions. Matrix product approximations of the edge messages are constructed recursively in an iteration over time. Computation costs and precision can be tuned by controlling the matrix dimensions of the MPEM in truncations. Without truncations, the dynamics is exact. Data for Glauber-Ising dynamics shows a linear growth of computation costs in time. In contrast to Monte Carlo simulations, the approach has a much better error scaling. Hence, it gives for example access to low probability events and decaying observables like temporal correlations. We discuss optimized truncation schemes and an extension that allows to capture models which have a continuum time limit.

23 pages, 14 figures; added data showing a linear temporal increase of computation costs for Glauber-Ising dynamics; codes provided at http://www.manyparticle.org/~barthel/mpem; published version

References in corpus (19)

• Statistical physics of social dynamics
• The density-matrix renormalization group in the age of matrix product states
• Matrix product states represent ground states faithfully
• A message passing approach for general epidemic models
• Continuous Matrix Product States for Quantum Fields
• Entropy and Entanglement in Quantum Ground States
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Holographic quantum states
• Dynamic message-passing equations for models with unidirectional dynamics
• Dynamical TAP equations for non-equilibrium Ising spin glasses
• Multigrid Algorithms for Tensor Network States
• The zero-patient problem with noisy observations
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• Inference of kinetic Ising model on sparse graphs
• Relevance of backtracking paths in epidemic spreading on networks
• One-dimensional quantum systems at finite temperatures can be simulated efficiently on classical computers
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• Variational perturbation and extended Plefka approaches to dynamics on random networks: the case of the kinetic Ising model
• Variational approximations for stochastic dynamics on graphs

Cited by in corpus (3)

• Matrix Product Belief Propagation for reweighted stochastic dynamics over graphs
• Scaling of contraction costs for entanglement renormalization algorithms including tensor Trotterization and variational Monte Carlo
• Nonequilibrium steady-state dynamics of Markov processes on graphs