logo

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

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

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

京ICP备18024590号-1