Draft:Dynamic message passing

Dynamic message passing (DMP) is a family of message-passing algorithms for computing marginal probabilities of various dynamical processes on networks. The need for such equations comes from the fact that standard message passing methods are computationally inefficient when directly applied to dynamic problems. ... DMP equations for unidirectional dynamics on trees were strictly derived from belief propagation.

Motivation

... Being able to compute marginal probabilities is specifically useful for prediction tasks, such as estimating the global spread. ... In case of simple unidirectional dynamics the complexity... ...

Equations for specific models

... network versions of compartmental models ...

Susceptible-Infected model

...In this simple model...

Susceptible-Infected-Recovered model

...adding the extra state...

Independent Cascade model

...special case of the above described SIR model...

$p_{i\rightarrow j}(t)=1-(1-p_{i}(0))\prod _{k\in \partial i\setminus j}(1-\alpha _{ki}\cdot p_{k\rightarrow i}(t)),$

Derivation from belief propagation

DMP equations can be directly derived from belief propagation equations, but it requires a modification of the original spreading graph. Straightforward... ...

$\mu ^{i\rightarrow j}({\vec {\sigma }}_{i})\propto \prod _{k\in \partial i\setminus j}\sum _{{\vec {\sigma }}_{k}}W_{i}({\vec {\sigma }}_{i};{\vec {\sigma }}_{k})\cdot \mu ^{k\rightarrow i}({\vec {\sigma }}_{k}),$

...

$\mu ^{i\rightarrow j}({\vec {\sigma }}_{i\rightarrow j},{\vec {\sigma }}_{j\rightarrow i})\propto \sum _{\{{\vec {\sigma }}_{k\rightarrow i}\}_{k\in \partial i\setminus j}}W_{i}({\vec {\sigma }}_{i\rightarrow j};\{{\vec {\sigma }}_{k\rightarrow i}\}_{k\in \partial i})\prod _{k\in \partial i\setminus j}\mu ^{k\rightarrow i}({\vec {\sigma }}_{k\rightarrow i},{\vec {\sigma }}_{i\rightarrow k}),$

...

$\mu ^{i\rightarrow j}({\vec {\sigma }}_{i}||{\vec {\sigma }}_{j})=\sum _{\{{\vec {\sigma }}_{k}\}_{k\in \partial i\setminus j}}W_{i}({\vec {\sigma }}_{i};\{{\vec {\sigma }}_{k}\}_{k\in \partial i})\prod _{k\in \partial i\setminus j}\mu ^{k\rightarrow i}({\vec {\sigma }}_{k}||{\vec {\sigma }}_{i}),$

...

$\mu ^{i}({\vec {\sigma }}_{i})=\sum _{\{{\vec {\sigma }}_{k}\}_{k\in \partial i}}W_{i}({\vec {\sigma }}_{i};\{{\vec {\sigma }}_{k}\}_{k\in \partial i})\prod _{k\in \partial i}\mu ^{k\rightarrow i}({\vec {\sigma }}_{k}||{\vec {\sigma }}_{i}),$

...

Independent Cascade model case

As an example...

$m_{T+1}^{i\rightarrow j}(\tau _{i}||\tau _{j})=\sum _{\{\tau _{k}\}_{k\in \partial i\setminus j}}W_{i}(\tau _{i};\{\tau _{k}\}_{k\in \partial i})\prod _{k\in \partial i\setminus j}m_{T}^{k\rightarrow i}(\tau _{k}||\tau _{i}),$

...

$m_{T+1}^{i}(\tau _{i})=\sum _{\{\tau _{k}\}_{k\in \partial i}}W_{i}(\tau _{i};\{\tau _{k}\}_{k\in \partial i})\prod _{k\in \partial i}m_{T}^{k\rightarrow i}(\tau _{k}||\tau _{i}),$

...

Limitations

DMP inherits properties of belief propagation and as such is exact on trees, unless further assumptions were used. It is also a good approximation for sparse and tree-like graphs, but breaks down when many short loops are present. Low, even linear, complexity in time is achieved for models with unidirectional dynamics, where a single trajectory can be parametrised by only a few parameters, regardless of the time horizon. ...Trees, Unidirectional dynamics...

Applications

DMP is an approximate inference technique, but its main strength comes from the fact that, unlike standard BP, it does not require iteration and with certain realistic assumptions about the dynamics, can be as computationally efficient as a single Monte Carlo run [needs citation]. These advantages, together with marginalisation over time, make DMP a perfect sub-rutine for more complex tasks, such as learning [needs citation] or optimisation [needs citation]. One good example is...(learning with partial observation <-- can deal with unobserved nodes due to marginalisation over nodes and is computationally efficient)... ...Inference, Learning, Optimisation...