Inference of the sparse kinetic Ising model using the decimation method

In this paper we study the inference of the kinetic Ising model on sparse graphs by the decimation method. The decimation method, which was first proposed in Decelle and Ricci-Tersenghi [Phys. Rev. Lett. 112, 070603 (2014)] for the static inverse Ising problem, tries to recover the topology of the inferred system by setting the weakest couplings to zero iteratively. During the decimation process the likelihood function is maximized over the remaining couplings. Unlike the ${\ell }_1$-optimization-based methods, the decimation method does not use the Laplace distribution as a heuristic choice of prior to select a sparse solution. In our case, the whole process can be done auto-matically without fixing any parameters by hand. We show that in the dynamical inference problem, where the task is to reconstruct the couplings of an Ising model given the data, the decimation process can be applied naturally into a maximum-likelihood optimization algorithm, as opposed to the static case where pseudolikelihood method needs to be adopted. We also use extensive numerical studies to validate the accuracy of our methods in dynamical inference problems. Our results illustrate that, on various topologies and with different distribution of couplings, the decimation method outperforms the widely used ${\ell }_1$-optimization-based methods.

Figure 1

True couplings (blue circles) compared with couplings inferred (red crosses) by maximizing likelihood method (a), ${\ell }_1$ minimization + refinement (b), and decimation (c). The relative error [Eq. (11)] is $0.209, 0.079$, and $0.026$ from left to right, respectively. The network is a two-dimensional $(2\mathrm{D}$) lattice with size $N=49, \beta =2.0, R=10$, and $T=500$.

Figure 2

Illustration of the results obtain by maximizing the likelihood together with the ${\ell }_1$ prior on a set of data generated by a parallel dynamics. The considered system is a 2D ferromagnet at low temperature, $\beta =0.61$, and we use $T=1000$ and $R=1$. The histograms show the parameters obtained for $\lambda =0.1$ (top) and $\lambda =1.1$ (bottom). Clearly, the number of zero couplings change drastically when $\lambda$ changes.

Figure 3

(a) Illustration of a typical tilted-likelihood function. In this case we are in a hard region, $N=49, \beta =1.5$ with $R=10$ and $T=500$ of a 2D symmetric model with $J=\pm 1$. We observe a well-defined peak which indicates where to stop the decimation process. In the inset we show that the relative error is minimized at the peak. In this case, the decimation process reconstructs perfectly the network as indicated in (b). (b) The ROC curve for the same system in (a). The ROC curves show the number of true positives on the $y$ axis and true negatives on the $x$ axis. The goal is therefore to reach the top-right angle for a perfect reconstruction. Here the decimation process and the Deci-O2 method are shown at different stages of the decimation [at $T=0$ the curve start at (0,1)]. For the ${\ell }_1$ method, different points correspond to different values of $\lambda$. We can see that our method works better than the two other ones. The ${\ell }_1$ method is clearly less good even when considering the best possible $\lambda$ [$\delta$ indicates the value of the cutoff but is chosen such that it goes into the gap separating zero couplings from the nonzero ones (see Fig. 2)].

Figure 4

Results obtained on a 2D symmetric model $J=\pm 1$ with $N=49, R=10$, and $T=500$ for various values of $\beta$. In the top panel, we can see the topology reconstruction [Eq. (12)] of the three methods: decimation, Deci-O2, and ${\ell }_1$. We can see clearly that the decimation always recovers perfectly the topology of the graph, whereas ${\ell }_1$ performs poorly. The Deci-O2 method works almost as well as the decimation. In the bottom panel, we show the error in the reconstruction [Eq. (11)]. All methods perform similarly with a slight advantage shown with the decimation. This behavior can be explained by the fact that, often, the error in the topology reconstruction is dominated by the false negative couplings. The ${\ell }_1$ finds a lot of false positives but they are inferred quite close to zero (i.e., their true value) and therefore they do not contribute much to the reconstruction error.

Figure 5

Comparison of the performance of the three methods on different topologies: (a) 3D lattice with $N=64, J=\pm 1, R=10$, and $T=500$; (b) ER random graph with $N=50, J=\pm 1, R=10$, and $T=500$; (c) Gaussian couplings on a random graph with $N=50, {\sigma }_{\mathrm{Gauss}}=0.1, R=10$, and $T=500$; (d) asymmetric couplings with $J_{ij}=\pm 1$ on a random graph with $N=50, R=1$, and $T=5000$. In each figure the crosses correspond to the value of $P_{\mathrm{neigh}}$ [Eq. (11)], and the circles and the squares correspond to the relative error $\epsilon$ [Eq. (11)]. From those figures we can conclude that the decimation always works much better than the ${\ell }_1$ method. The Deci-O2 method is comparable but always slightly worse than the decimation. The details concerning the comparison are described in the text.