SCIENCE CHINA Information Sciences, Volume 61, Issue 5: 052101(2018) https://doi.org/10.1007/s11432-016-9070-4

## Learning dynamic dependency network structure with time lag

More info
• ReceivedJul 18, 2016
• AcceptedMar 16, 2017
• PublishedAug 30, 2017
Share
Rating

### Abstract

Characterizing and understanding the structure and the evolution of networks is an important problem for many different fields.While in the real-world networks, especially the spatial networks, the influence from one node to another tends to vary over both space and time due to the different space distances and propagation speeds between nodes. Thus the time lag plays an essential role in interpreting the temporal causal dependency among nodes and also brings a big challenge in network structure learning.However most of the previous researches aiming to learn the dynamic network structure only treat the time lag as a predefined constant, which may miss important information or include noisy information if the time lag is set too small or too large.In this paper, we propose a dynamic Bayesian model with adaptive lags (DBAL) which simultaneously integrates two usually separate tasks, i.e., learning the dynamic dependency network structure and estimating time lags, within one unified framework.Specifically, we propose a novel weight kernel approach for time series segmenting and sampling via leveraging samples from adjacent segments to avoid thesample scarcity. Besides, an effective Bayesian scheme cooperated with reversible jump Markov chainMonte Carlo (RJMCMC) and expectation propagation (EP) algorithm is proposed for parameter inference.Extensive empirical evaluations are conducted on both synthetic and two real-world datasets, and the results demonstrate that our proposed model is superior to the traditional methods in learning the network structure and the temporal dependency.

### Acknowledgment

This work was supported by National Science and Technology Support Plan (Grant No. 2014BAG01B02), National Natural Science Foundation of China (Grant No. 61572041), Joint Funds of the National Natural Science Foundation of China (Grant No. U1404604), and Beijing Natural Science Foundation (Grant No. 4152023).

### References

[1] Lèbre S, Becq J, Devaux F. Statistical inference of the time-varying structure of gene-regulation networks.. BMC Syst Biol, 2010, 4: 130 CrossRef PubMed Google Scholar

[2] Goldenberg A, Moore A W. Bayes net graphs to understand co-authorship networks? In: Proceedings of the 3rd International Workshop on Link Discovery, New York, 2005. 1--8. Google Scholar

[3] Chen X, Liu Y, Liu H, et al. Learning spatial-temporal varying graphs with applications to climate data analysis. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, Atlanta, 2010. Google Scholar

[4] Dhurandhar A. Learning maximum lag for grouped graphical granger models. In: Proceedings of IEEE International Conference on Data Mining Workshops. Washington: IEEE Computer Society, 2010. 217--224. Google Scholar

[5] Barthélemy M. Spatial networks. Phys Rep, 2011, 499: 1-101 CrossRef ADS arXiv Google Scholar

[6] Grzegorczyk M. A non-homogeneous dynamic Bayesian network with a hidden Markov model dependency structure among the temporal data points. Mach Learn, 2016, 102: 155-207 CrossRef Google Scholar

[7] Liu Y, Kalagnanam J R, Johnsen O. Learning dynamic temporal graphs for oil-production equipment monitoring system. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, 2009. 1225--1234. Google Scholar

[8] Song L, Kolar M, Xing E P. Time-varying dynamic Bayesian networks. In: Proceedings of Advances in Neural Information Processing Systems, Vancouver, 2009. 1732--1740. Google Scholar

[9] Dobigeon N, Tourneret J Y, Davy M. Joint Segmentation of Piecewise Constant Autoregressive Processes by Using a Hierarchical Model and a Bayesian Sampling Approach. IEEE Trans Signal Process, 2007, 55: 1251-1263 CrossRef ADS Google Scholar

[10] Talih M, Hengartner N. Structural learning with time-varying components: tracking the cross-section of financial time series. J R Statistical Soc B, 2005, 67: 321-341 CrossRef Google Scholar

[11] Xuan X, Murphy K. Modeling changing dependency structure in multivariate time series. In: Proceedings of the 24th International Conference on Machine Learning, Omaha, 2007. 1055--1062. Google Scholar

[12] Knapp C, Carter G. The generalized correlation method for estimation of time delay. IEEE Trans Acoust Speech Signal Process, 1976, 24: 320-327 CrossRef Google Scholar

[13] Green P J. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 1995, 82: 711-732 CrossRef Google Scholar

[14] Minka T P. Expectation propagation for approximate Bayesian inference. In: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, Seattle, 2001. 362--369. Google Scholar

[15] Eaton D, Murphy K. Bayesian structure learning using dynamic programming and MCMC,. arXiv Google Scholar

[16] Guo F, Hanneke S, Fu W, et al. Recovering temporally rewiring networks: a model-based approach. In: Proceedings of the 24th International Conference on Machine Learning, Corvallis, 2007. 321--328. Google Scholar

[17] Husmeier D, Dondelinger F, Lebre S. Inter-time segment information sharing for non-homogeneous dynamic Bayesian networks. In: Proceedings of Conference and Workshop on Neural Information Processing Systems (NIPS), Vancouver, 2010. 901--909. Google Scholar

[18] Sakurai Y, Papadimitriou S, Faloutsos C. Braid: stream mining through group lag correlations. In: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Melbourne, 2005. 599--610. Google Scholar

[19] Tibshirani R. Regression shrinkage and selection via the lasso. J Roy Stat Soc B, 1996, 58: 267--288. Google Scholar

[20] Dondelinger F, Lèbre S, Husmeier D. Non-homogeneous dynamic Bayesian networks with Bayesian regularization for inferring gene regulatory networks with gradually time-varying structure. Mach Learn, 2013, 90: 191-230 CrossRef Google Scholar

[21] Ishwaran H, Rao J S. Spike and slab variable selection: Frequentist and Bayesian strategies. Ann Statist, 2005, 33: 730-773 CrossRef Google Scholar

[22] George E I, McCulloch R E. Approaches for Bayesian variable selection. Stat Sin, 1997, 7: 339--373. Google Scholar

[23] Hernández-Lobato J M, Hernández-Lobato D, Suárez A. Expectation propagation in linear regression models with spike-and-slab priors. Mach Learn, 2015, 99: 437-487 CrossRef Google Scholar

[24] Green P J, Hastie D I. Reversible jump MCMC. Genetics, 2009, 155: 1391--1403. Google Scholar

[25] Robert C P, Ryden T, Titterington D M. Bayesian inference in hidden Markov models through the reversible jump Markov chain Monte Carlo method. J R Statistical Soc B, 2000, 62: 57-75 CrossRef Google Scholar

[26] Gelman A, Rubin D B. Inference from Iterative Simulation Using Multiple Sequences. Statist Sci, 1992, 7: 457-472 CrossRef ADS Google Scholar

[27] Arnold A, Liu Y, Abe N. Temporal causal modeling with graphical granger methods. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, 2007. 66--75. Google Scholar

[28] Murphy K. An introduction to graphical models. Rap Tech, 2001: 1--19. Google Scholar

[29] Dagum P, Galper A, Horvitz E. Dynamic network models for forecasting. In: Proceedings of the 8th International Conference on Uncertainty in Artificial Intelligence, Stanford, 1992. 41--48. Google Scholar

[30] Zhou X, Hong H, Xing X, et al. Mining dependencies considering time lag in spatio-temporal traffic data. In: Proceedings of International Conference on Web-Age Information Management, Qingdao, 2015. 285--296. Google Scholar

[31] Zhang R J, Cao J, Lee S. Carbonaceous aerosols in PM10 and pollution gases in winter in Beijing. J Environ Sci, 2007, 19: 564-571 CrossRef Google Scholar

• Figure 1

Illustration of the dynamic dependency network with varying lags.

• Figure 2

Plate notation for the DBAL model. Blank circles are observations, shaded circles are latent variables, and the variables in squares are model parameters.

• Figure 3

Comparison between the true $\boldsymbol~\beta$ and learned $\boldsymbol~\beta^*$. (a) The ground truth $\boldsymbol~\beta$; (b) the learned $\boldsymbol~\beta^*$.

• Figure 4

The true lags $\boldsymbol~L$ and the residual matrix $~\Delta~\boldsymbol~L$ between learned lags and the truth. (a) The ground truth $\boldsymbol~L$; (b) the residual matrix $~\Delta~{\boldsymbol~L}$ between learned lags and the truth.

• Figure 5

The F1 score of network structures learned by different methods and the log-likelihood of model. (a) The F1 score of network structures learned by different methods; (b) log-likelihood of Model.

• Figure 6

(Color online) The changepoints and the dynamic causal relationships of PM2.5. (a) The changepoints when we estimate the dynamic causal relationships of PM2.5; (b) the dynamic causal relationships of PM2.5.

• Figure 7

(Color online) The PM2.5 and and wind speed. (a) The PM2.5 and learned changepoint; (b) the wind speed level of No.3 station.

• Figure 8

(Color online) The dependent stations and time lags of No.3 station. The learned dependency of No.3 station in (a) the first segment and (b) the second segment.

• Figure 9

(Color online) The traffic flow and learned changepoint.

• Figure 10

(Color online) The learned dependency in highway traffic network. The learned dependency between traffic ramps in (a) the first segment and (b) the second segment.

•

Algorithm 1 Procedure for estimating dynamic dependency network structures with estimation of lags

Input: data $\boldsymbol~X$ and $y\boldsymbol~$, the maximum number of changepoints $k_{\rm~max}$ Output: $k,{\xi},\boldsymbol{\beta_s},\boldsymbol{L},\boldsymbol{Z}$

Initialization: $k,{\xi}$

Iteration $i$: $i=1$

sample $\mu_0\sim\mu[0,1]$

if $u_0\leq~b_k$ then

consider changepoint birth Propose a new changepoint ${\xi^*}|{{\xi}}\sim{u_{\{1,\ldots,N\}\backslash\{~{{\xi~}}\}}}$ Update_state (current state, Eq. (14))ELSIF$u_0\leq~b_k+d_k$

consider changepoint death Choose a changepoint $\xi^*\in{~\xi}$ to be deleted Update_state (current state, Eq. (15))ELSIF$u_0\leq~b_k+d_k+q_k$

consider changepoint shift Randomly choose a changepoint $\xi\in{~\xi}~$ shift to a new changepoint ${\xi^*}|{{\xi}}\sim{u_{\{1,\ldots,N\}\backslash\{~{{\xi~}}\}}}$ Update_state (current state, Eq. (16))

else

Update the network structure of every segment

end if

$i\leftarrow~i+1$ and go to 4

• Table 1   Notation explanation
 Notation Description $\boldsymbol~X$ The observed variables $\boldsymbol~y$ The target variable selected from $\boldsymbol~X$ $d$ The dimension of all the observed variables $N$ The length of observations $k$ The number of changepoints $\xi$ The vector of changepoints $\boldsymbol~\beta$ The tensor of regression coefficients $\boldsymbol~L$ The tensor of lags $s$ The index of segment
• Table 2   Comparative methods
 Method Network state Varying form Lag SGL Static – $T$ TVDBN Dynamic Time point 1 DBN Static – 1 NHDBNs Dynamic Period 1 DBNL Dynamic Period 1 TLHL Static – Learned
•

Algorithm 2 Function update_state (current state, Eq. (e))

Input: Current state, Eq. (e) Output: New state

Evaluate acceptance probability $A$ according to Eq. (e)

Sample $u\sim{U_{[0,1]}}$

if $u~\le~{A}$ then

Return the updated state

else

Return the current state

end if

• #### 1

Citations

• Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有