Stochastic dynamics on large networks: Prediction and inference

In this talk I will describe a model of price fluctuations in financial markets. The general structure of the model can be derived from very generic considerations concerning projected dynamics. In its simplest form it takes the form of a model describing a network of analog neurons. Such a system is expected to exhibit a large number of meta-stable states in a large part of its parameter, and the salient features of market dynamics, such as fat-tailed return distributions and volatility clustering can be understood in terms of an interplay between the dynamics within meta-stable states and the dynamics of occasional transitions between them.

We proposing a variation framework for solving high-dimension partial differential equation. A Variation problem is restricted to a model set and afterwards replaced by an empirical surrogate, like ins statistics, e.g. for regression. In the forward problem we apply this approach for solving a partial differential equation, e.g. diffusion equation with uncertain coefficients. We apply Baysean inversion to the inverse problem in parametric form. For the representation of high-dimensional functions, we use a hierarchical tensor representation (tree-tensor network states) to circumvent the curse of dimensions. (This has been shown to be a special deep neural network) Error estimates are proved to hold with high probability.

Wireless communication networks require reliable routing of messages, despite the fact that individual networks links are unreliable. Multi-hop routing protocols propose a promising solution to overcome the issue of message loss. For these protocols, successful relay of a message defines a percolation problem. Here, we present a percolation theory for a minimal model, where individual links switch between an active and an inactive state according to a two-state Markov process. Using renormalization group theory, we analytically compute the complete statistics of failure events. We show how the time-dependent probability to find a path of active links between two designated nodes converges towards an effective Bernoulli process, i.e. without memory, as the hop distance between the nodes increases. Our work extends classical percolation theory to the dynamic case. It elucidates temporal correlations of message losses with implications for the design of communication protocols and control algorithms.

Building on the work of Al-Mohy and Higham (2011) we describe a new algorithm for evaluating the left action of the exponential of a rate matrix on a vector of probabilities. The specifics of our application allow an algorithm that is both considerably simpler than the general algorithm of Al-Mohy and Higham, and over three times faster. We apply our algorithm to exact inference for partially and discretely observed Markov jump processes (MJPs) with finite state spaces, finding additional, substantial computational savings in the cases of well known epidemic models. We then consider MJPs with infinite state spaces and build on the work of Georgoulas, Hillston and Sanguinetti (2017) to provide a new, fast, and more easily tuned algorithm for Bayesian inference.

We construct and study the Google matrix of Bitcoin transactions during the time period from the very beginning in 2009 till April 2013. The Bitcoin network has up to a few millions of bitcoin users and we present its main characteristics including the PageRank and CheiRank probability distributions, the spectrum of eigenvalues of Google matrix and related eigenvectors. We find that the spectrum has an unusual circle-type structure which we attribute to existing hidden communities of nodes linked between their members. We show that the Gini coefficient of the transactions for the whole period is close to unity showing that the main part of wealth of the network is captured by a small fraction of users.

The interaction structure of networked dynamical systems fundamentally underlies their function and collective dynamics. Yet, identifying network physical couplings typically requires access to its complete continuous-time trajectories although these are often experimentally inaccessible. Here, we present a theory for revealing physical connectivity of networked systems only from the event time series their intrinsic collective dynamics generate. Representing the patterns of event timings in an \emph{event space} spanned by inter-event and cross-event intervals, we reveal which other units directly influence the inter-event times of any given unit. For illustration, we linearise an event space mapping constructed from the spiking patterns in model neural circuits to reveal the presence or absence of synaptic interactions between any pair of neurons as well as whether the coupling acts in an inhibiting or activating (excitatory) manner. These results enable us to reveal direct couplings for systems where a detailed model is not known and only indicators of state variables are observable. [This is joint work with Jose Casadiego and Marc Timme]

We present a new family of computation schemes to compute approximate marginals of discrete Markov Random Fields. The schemes shares some desirable properties both with Expectation Consistency and Belief Propagation. In particular it computes exact marginals on acyclic graphs; but includes some loop corrections and so is more accurate on graphs with cycles. Some applications to Ising models and constraint satisfaction problems will be shown.

Approaches exist to construct continuous approximations of discrete state Markov systems (Kramers-Moyal approximation with Kurtz's theorem and van Kampen's system size expansion) which might be easier to solve or otherwise useful for large systems. However, these methods rely on an interpretation of the discrete states which embeds the states in an ambient continuous space and extends transition rates over that space, so that a diffusion approximation can be developed. We seek here to construct an agnostic method that embeds states of a continuous-time Markov chain (CTMC) by examining the transition rate matrix. Manifold learning methods such as diffusion maps recover an embedding consistent to the standard embedding for some population CTMCs (chemical reaction networks). Finally, we infer the drift vector field over the ambient space using a Gaussian process, to allow for an ODE solution as a first order approximation for the mean of the diffusion process.

We consider the problem of solving the TAP (Thouless-Anderson-Palmer) mean-field equations of the Ising model with arbitrary rotation invariant random coupling matrices, i.e. the model does not make reference to the distribution of eigenvalues of coupling matrix (but to the distribution of the eigenvectors). To this end, we present a dynamical functional analysis that allows us to design iterative algorithms with theoretically guaranteed convergence properties.

Neural networks, a central tool in machine learning, have demonstrated remarkable, high fidelity performance on image recognition and classification tasks.These successes suggest that it may be possible to use neural networks to parameterize high-dimensional functions with controllably small errors, potentially outperforming standard interpolation methods. We demonstrate, both theoretically and numerically, that this is indeed the case. We map the parameters of a neural network to a system of particles relaxing with an interaction potential determined by the loss function. We show that in the limit that the number of parameters n is large, the landscape of the mean-squared error becomes convex and the representation error in the function scales as $O(1/n)$. As a consequence, we rederive the universal approximation theorem for neural networks but we additionally prove that the optimal representation can be achieved through stochastic gradient descent, the algorithm ubiquitously used for parameter optimization in machine learning. These results show the necessity of the noise inherent in stochastic gradient descent and provide a precise scale for tuning this noise. From our insights, we extract several practical guidelines for large scale applications of neural networks, emphasizing the importance of both noise and quenching, in particular. We illustrate our findings on examples in which we train neural network to learn the energy function of the continuous 3-spin model on the sphere. The approximation error scales as our analysis predicts in as high a dimension as $d = 25$.

This paper focuses on two questions of Bayesian inference: 1) how a credible set changes if we replace the prior by another (simpler) prior? 2) Can one use the Bayesian credible sets as frequentist confidence sets. We apply recent results from Goetze at al (2018) on Gaussian large ball probability to address these issues.

We propose a neuronal network model for analyzing binary spiking activity from ensembles of neurons. The model is based on the Markovian dynamics of a (kinetic) Ising model with asynchronous updates and allows for the analysis of single trial, non stationary spike data. Our novel contribution is the introduction of a dynamical network couplings which can model changing, unobserved activity states. We assume that at random change points, network couplings change stochastically to new states, but that the total number of states is finite. Using prior distributions over model parameters, we aim at a Bayesian inference of functional network couplings and model states over time. We show that efficient inference with this model can be achieved by a variational Bayes framework after the introduction of auxiliary latent variables with P\'olya--Gamma distribution. These allow us to simplify the transition probabilities of the binary Ising variables. We demonstrate the applicability of our approach to neuronal data recorded invivo from V4 monkey area ($40$ neurons). State changes inferred by the model can be related to events in the simultaneously recorded local field potential.

In vitro and in vivo spiking activity clearly differ. Whereas networks in vitro develop strong bursts separated by periods of very little spiking activity, in vivo cortical networks show continuous activity. This is puzzling considering that both networks presumably share similar single-neuron dynamics and plasticity rules. We propose that the defining difference between in vitro and in vivo dynamics is the strength of external input. In vitro, networks are virtually isolated, whereas in vivo every brain area receives continuous input. We analyze a model of spiking neurons in which the input strength, mediated by spike rate homeostasis, determines the characteristics of the dynamical state. In more detail, our analytical and numerical results on various network topologies show consistently that under increasing input, homeostatic plasticity generates distinct dynamic states, from bursting, to close-to-critical, reverberating and irregular states. This implies that the dynamic state of a neural network is not fixed but can readily adapt to the input strengths. Indeed, our results match experimental spike recordings in vitro and in vivo: the in vitro bursting behavior is consistent with a state generated by very low network input (< 0.1%), whereas in vivo activity suggests that on the order of 1% recorded spikes are input-driven, resulting in reverberating dynamics. Importantly, this predicts that one can abolish the ubiquitous bursts of in vitro preparations, and instead impose dynamics comparable to in vivo activity by exposing the system to weak long-term stimulation, thereby opening new paths to establish an in vivo-like assay in vitro for basic as well as neurological studies.

In Reinforcement Learning an agent learns how to act in an environment in order to achieve desired goals. In general, the agent only has access to partial information from the world, and has to learn how to act appropriately in face of this uncertainty. One of the earliest results in the theory of Optimal Control (Feldbaum 1965) demonstrates that in order to act appropriately, the agent must also probe the environment in order to gain information and reduce uncertainty. In other words, exploring the environment is an essential component of learning to act. However, very few provably effective procedures were proposed in the control literature to solve this problem. In recent years, several elegant solutions to the problem of exploration have been proposed in the Machine Learning literature for the case of finite state and action spaces (which was of little concern to the control theorists). However, the problem of effective exploration in continuous spaces is still very much open, and of increasing importance in many applications. We survey some recent approaches to exploration in continuous domains, in both model based and model free settings, and suggest open problems for future research.

In developing organisms, the expression levels of multiple genes determine spatially prescribed cell identities. It is unclear, however, what rules govern this specification, what level of precision is achieved, and how early in development this information is available. Using the gap gene network in the early fly embryo as an example, we show how expression levels of these four genes can be jointly decoded into an optimal specification of position with 1% accuracy. This wild-type decoder correctly predicts, with no free parameters, the dynamics of pair-rule expression patterns at different developmental time points and in various mutant backgrounds. Our results are consistent with the idea that developmental enhancers approximate a mathematically optimal decoding strategy, and that precise cellular identities are available at the earliest stages of development, contrasting the prevailing view of a slowly refining positional information across successive layers of the patterning network.

In evolutionary dynamics, the notion of a ‘well-mixed’ population is usually associated with all-to-all interactions at all times, i.e. a full interaction graph. This assumption simplifies the mathematics of evolutionary processes, and makes analytical solutions possible. At the same time the term ‘well-mixed’ suggests that this situation can be achieved by physically stirring the population. Using simulations of populations in chaotic flows, we show that in most cases this is not true: conventional well-mixed theories do not predict fixation probabilities correctly, regardless of how fast or thorough the stirring is. We propose a new analytical description in the fast-flow limit. This approach is valid for processes with global and local selection, and accurately predicts the suppression of selection as competition becomes more local. We also discuss the fixation and invasion properties of mutants in flowing populations, and show how heterogeneous networks, generated by flow, affect the outcome of evolutionary processes. Reference: Stirring does not make populations well mixed Francisco Herrerías-Azcué, Vicente Pérez-Muñuzuri, and Tobias Galla Scientific Reports, volume 8, Article number: 4068 (2018)

The regulation of gene expression is commonly achieved through transcriptional factor binding to DNA. However the presence of binding reactions often leads to analytically intractable stochastic models of gene expression. I will here introduce the linear-mapping approximation (LMA) that maps systems with protein-promoter interactions onto approximately equivalent systems with no binding reactions. This leads to analytic or semi-analytic expressions for the approximate time-dependent and steady-state protein number distributions. Stochastic simulations verify the method's accuracy in capturing the changes in the protein number distributions with time for a wide variety of networks displaying auto- and mutual-regulation of gene expression and independently of the ratios of the timescales governing the dynamics. The method is also used to study the first-passage time distribution of promoter switching, the sensitivity of the size of protein number fluctuations to parameter perturbation and the stochastic bifurcation diagram characterizing the onset of multimodality in protein number distributions. I will also discuss how the LMA can be used to reliably infer parameter values of gene regulatory networks with feedback loops from population snapshot data in a fraction of the time of popular Bayesian approaches.

Complex behaviour in many systems arises from the stochastic interactions of spatially distributed particles or agents. Stochastic reaction-diffusion processes are widely used to model such behaviour in disciplines ranging from biology to the social sciences, yet they are notoriously difficult to simulate and calibrate to observational data. In this talk, I will show how ideas from statistical physics and machine learning can be used to provide a solution to the inverse problem of learning a stochastic reaction-diffusion process from data. Our solution relies on a novel, non-trivial connection between stochastic reaction-diffusion processes and spatio-temporal Cox processes, a well-studied class of models from computational statistics. This allows us to naturally define an approximate likelihood, which can be optimised with respect to the kinetic parameters of the model. We show on several examples from systems biology and epidemiology that the method yields consistently accurate parameter estimates, and can be used effectively for model selection.

We consider a system of particles which move in cellular space and undergo chemical reactions. Depending on the spatial scaling and the particle number scaling, different mathematical models are appropriate. For well-mixed systems with multiple population scales, there exist hybrid approaches which combine the different models in an efficient way. Based on the spatio-temporal master equation, such hybrid approaches can also be extended to spatially inhomogeneous settings. In this talk, we give an overview of the existing approaches and discuss ideas for further recombinations, with the aim of appropriately modelling reaction-diffusion kinetics. As an application, we consider processes of gene expression and neurotransmission.

I will discussed the situation of large interacting particle systems where the coupling is determined by a graph. We are interested in finding low dimensional representations and their self-consistent evolution equations through dedicated Markov chain aggregation methods. We will introduce the notion of k-local symmetry to perform approximate lumping quantified through the KL distance. For special dynamics we will also discuss more aggressive reductions and give a central limit theorem result for the asymptotic dynamics of the aggregation when the number of nodes in the graph tends to infinity.

Stochastic dynamical models on large networks can often only be simulated, typically at a large computational cost. When we are interested in understanding behaviours of the model - described in some formal language - we can rely on simulations to estimate the probability of the model. Doing this under parametric uncertainty may be infeasible. We will present how to leverage Bayesian Machine Learning to get an efficient and accurate estimate of how behavioural probabilities change with model parameters, with applications in parameter synthesis and model design.

(Tentative) In this presentation I will describe an adaptive importance sampling algorithm for rare events simulation that is based on a dual stochastic control formulation of a path sampling problem. I will show that the associated semi-linear dynamic programming equations admit an equivalent formulation as a system of uncoupled forward-backward stochastic differential equations that can be solved efficiently by a least squares Monte Carlo algorithm. The approach will be illustrated with suitable numerical examples and the extension of the algorithm to high-dimensional systems, specifically molecular dynamics will be discussed.

I will describe innovations in the design of algorithms for sampling high dimensional probability distributions using methods based on discretization of stochastic differential equations. Important strides have been made in recent years in obtaining highly efficient and stable numerical methods for Langevin dynamics. These methods are already widely used in molecular dynamics, but have broader potential for applications in large scale complex systems as well as in general stochastic inference for parameterization of nonlinear models. I will also describe algorithms for enhanced sampling, including ensemble preconditioning and simulated tempering, which both offer potential to dramatically improve the convergence to equilibrium. I will also showcase several software projects which provide a platform for exploring sampling methods in various applications.

Continuous-time data assimilation can be rephrased as an interacting particle system, mean field equation, respectively. The feedback particle filter (FPP) formulation is particularly attractive as it can be viewed as controlled version of the free dynamics in the spirit of Kalman’s original work. The FPP also naturally leads to the popular ensemble Kalman-Bucy filter. The assimilation of discrete-in-time data is more delicate. However, application of a coupling approach, originally considered by Schroedinger, to the discrete-time data assimilation problem leads again to a controlled version of the underlying stochastic process. Alternatively, optimal transportation and ensemble transform methods can also be used to enhance available particle filters. I will survey these recent developments.

The modern world can be best described as interlinked networks, of individuals, computing devices and social networks; where information and opinions propagate through their edges in a probabilistic or deterministic manner via interactions between individual constituents. These interactions can take the form of political discussions between friends, gossiping about movies, or the transmission of computer viruses. Winners are those who maximise the impact of scarce resource such as political activists or advertisements, or by applying resource to the most influential available nodes at the right time. We developed an analytical framework, motivated by and based on statistical physics tools, for impact maximisation in probabilistic information propagation on networks; to better understand the optimisation process macroscopically, its limitations and potential, and devise computationally efficient methods to maximise impact (an objective function) in specific instances. The research questions we have addressed relate to the manner in which one could maximise the impact of information propagation by providing inputs at the right time to the most effective nodes in the particular network examined, where the impact is observed at some later time. It is based on a statistical physics inspired analysis, Dynamical Message Passing that calculates the probability of propagation to a node at a given time, combined with a variational optimisation process. We address the following questions: 1) Given a graph, a budget and a propagation/infection process, which nodes are best to infect to maximise the spreading? 2) Maximising the impact on a subset of particular nodes at given times, by accessing a limited number of given nodes. 3) Identify the most appropriate vaccination targets to isolate a spreading disease through containment of the epidemic. We also point to potential applications. Lokhov A.Y. and Saad D., Optimal Deployment of Resources for Maximizing Impact in Spreading Processes, PNAS 114 (39), E8138 (2017)

The standard model of diffusion assumes Fick's law, namely that the rate at which one substance diffuses through another is directly proportional to the concentration gradient of the diffusive substance. However one might expect nonlinear corrections in various situations e.g. if obstacles are present or if there are more than one species at high concentrations. In many cases of interest, the diffusion takes place on a heterogeneous support of the network type. The brain, Internet and the cyberworld, foodwebs, social contacts and commuting fall within the vast realm of network science. Irrespective of the specific domain, individual entities (e.g. material units, bits of information) belonging to a certain population, jump from one site (node) to its adjacent neighbors, following the intricate web of distinct links, which defines the architecture of the complex network. In real-world applications, the carrying capacity of each node is finite, an ineluctable constraint that should be accommodated for under crowded conditions. With this motivation in mind, we here introduce a nonlinear operator to describe diffusion in a crowded network. The derivation originates from a microscopic stochastic framework and it is solidly grounded on first principles. More precisely, individual units sitting on a node behave as standard random walkers: jumps towards adjacent nodes are equiprobable. Each node can only host a finite number of walkers, or, in other words, it bears a finite carrying capacity. The transition probability from one node to another weights the free available space at the destination site. Starting from this microscopic formulation, we derive a diffusion equation characterized by a transport operator that differs from the standard random-walk Laplacian matrix, for the presence of nonlinear terms involving products of the density of walkers. This difference is directly reflected in the stationary solution: the asymptotic concentration of crawlers per node is a nonlinear function of the node’s connectivity and not just proportional to it, as it is the case under standard diffusion. This latter is recovered when operating under diluted condition. Based on this generalization, we shall also outline an innovative scheme to reconstruct the unknown topology of a network, which exploits the dynamical entanglement among walkers, as instigated by the competition for the available space. The method allows one to accurately determine the distribution of connectivities and to quantify, with unprecedented efficiency, the size of the examined network. Notably, all necessary information is gathered from just one random node of the collection. We successfully tested our method in both synthetic networks but also in realistic ones (see Figure 1 for the C. Elegans neural network). References
 [1] M. Asllani, T. Carletti, F. Di Patti, D. Fanelli and F. Piazza, Hopping in the Crowd to Unveil Network Topology, Phys. Rev. Lett. 120, 158301 (2018)

In many applications of finance, biology and sociology, complex systems involve entities interacting with each other. These pro- cesses have the peculiarity of evolving over time and of comprising latent factors, which influence the system without being explicitly measured. In this work we present latent variable time-varying graphical lasso (LTGL), a method for multivariate time-series graph- ical modelling that considers the influence of hidden or unmea- surable factors. The estimation of the contribution of the latent factors is embedded in the model which produces both sparse and low-rank components for each time point. In particular, the first component represents the connectivity structure of observable vari- ables of the system, while the second represents the influence of hidden factors, assumed to be few with respect to the observed variables. Our model includes temporal consistency on both com- ponents, providing an accurate evolutionary pattern of the system. We derive a tractable optimisation algorithm based on alternating direction method of multipliers, and develop a scalable and effi- cient implementation which exploits proximity operators in closed form. LTGL is extensively validated on synthetic data, achieving optimal performance in terms of accuracy, structure learning and scalability with respect to ground truth and state-of-the-art meth- ods for graphical inference. We conclude with the application of LTGL to real case studies, from biology and finance, to illustrate how our method can be successfully employed to gain insights on multivariate time-series data.

A connection between the distributed alternating direction method of multipliers (ADMM) and lifted Markov chains was recently proposed by Franca et al. 2016 for a distributed averaging problem on a graph G. This was followed by a conjecture that ADMM is faster than gradient descent by a square root factor in its convergence time, in close analogy to the mixing speedup achieved by lifting several Markov chains. Nevertheless, a proof was lacking. In this talk, I will start by revisiting Franca’s conjecture. Afterwards, I will fully characterize the distributed over-relaxed ADMM for this consensus problem in terms of the topology of the graph G. To be specific, I will relate its convergence rate with the mixing time of random walks on the graph G. A consequence of this result is a proof of the aforementioned conjecture, which, interestingly, is valid for any graph, even those whose random walks cannot be accelerated via Markov chain lifting.

Building on the work of Al-Mohy and Higham (2011) we describe a new algorithm for evaluating the left action of the exponential of a rate matrix on a vector of probabilities. The specifics of our application allow an algorithm that is both considerably simpler than the general algorithm of Al-Mohy and Higham, and over three times faster. We apply our algorithm to exact inference for partially and discretely observed Markov jump processes (MJPs) with finite state spaces, finding additional, substantial computational savings in the cases of well known epidemic models. We then consider MJPs with infinite state spaces and build on the work of Georgoulas, Hillston and Sanguinetti (2017) to provide a new, fast, and more easily tuned algorithm for Bayesian inference. Fast exact inference for Markov jump processes using the rate matrix.

The detailed structure and temporal evolution of real-world contact networks are becoming increasingly accessible at different scales. Such information is combined into individual-based models of epidemic diffusion to perform risk assessment analysis from partial observations of the outbreak. Common methods used in computational epidemiology are based on Monte Carlo Approximate Bayesian Computation and require a large computational effort to partially account for different initial conditions and model parameters. I will review a different approach, based on generalized mean-field methods such as Belief Propagation, that can be used to study the dynamics of common epidemic models on (contact) networks and to develop efficient algorithmic techniques for a variety of related Bayesian inference problems (e.g. the identification of the first infected individuals from a partial/noisy observation at later times, the inference of the epidemic parameters and the prediction of future evolution of the epidemic process). The performances of the method are tested in the case of computer-generated epidemic processes (SIR model) on random graphs and real-world contact networks. Finally, I will discuss the application of these methods to detect contagion channels in the Italian livestock trade network.

How can we understand processes that happened in prehistoric times when there were no written records of events? We are tackling this question by building a model that reconstructs possible scenarios to make sense of the available, often sparse and uncertain, archaeological data. The dynamical process we are studying is the spreading of an innovation in the ancient world. We are presenting a data-driven mathematical model that describes the migration dynamics of agents, their interactions and the spreading of an innovation among them. The model will be applied to one of the impactful innovations that emerged and spread throughout Asia into Europe between 6200 and 3000 BC, the wool-bearing sheep. The resulting simulations will be used to analyse dynamical properties of the system, such as first hitting times, and to explore how the migration dynamics are coupled to the innovation spreading.

In this work, we present an interacting variant of the well known Geometric Brownian Motion model which plays a central role in modern day financial theory and practice. The model is attractive in that it is able to reproduce many of the so called stylised facts of financial markets through the interplay of many metastable states and transitions between them. The focus however, will be on how such dynamical regimes play a role in inference of the interaction network. We present results primarily for the synthetic case before finally applying this to real data.