×

Sequential change-point detection in high-dimensional Gaussian graphical models. (English) Zbl 1499.62194

Summary: High dimensional piecewise stationary graphical models represent a versatile class for modelling time varying networks arising in diverse application areas, including biology, economics, and social sciences. There has been recent work in offline detection and estimation of regime changes in the topology of sparse graphical models. However, the online setting remains largely unexplored, despite its high relevance to applications in sensor networks and other engineering monitoring systems, as well as financial markets. To that end, this work introduces a novel scalable online algorithm for detecting an unknown number of abrupt changes in the inverse covariance matrix of sparse Gaussian graphical models with small delay. The proposed algorithm is based upon monitoring the conditional log-likelihood of all nodes in the network and can be extended to a large class of continuous and discrete graphical models. We also investigate asymptotic properties of our procedure under certain mild regularity conditions on the graph size, sparsity level, number of samples, and pre- and post-changes in the topology of the network. Numerical works on both synthetic and real data illustrate the good performance of the proposed methodology both in terms of computational and statistical efficiency across numerous experimental settings.

MSC:

62H22 Probabilistic graphical models
62L10 Sequential statistical analysis
68W27 Online algorithms; streaming algorithms

References:

[1] Yves Atchade and Leland Bybee. A scalable algorithm for gaussian graphical models with change-points.arXiv preprint arXiv:1707.04306, 2017.
[2] Alexander Aue, Siegfried H¨ormann, Lajos Horv´ath, Matthew Reimherr, et al. Break detection in the covariance structure of multivariate time series models.The Annals of Statistics, 37(6B):4046-4087, 2009. · Zbl 1191.62143
[3] Jushan Bai and Pierre Perron. Estimating and testing linear models with multiple structural changes.Econometrica, pages 47-78, 1998. · Zbl 1056.62523
[4] Jushan Bai and Pierre Perron. Computation and analysis of multiple structural change models.Journal of applied econometrics, 18(1):1-22, 2003.
[5] Ian Barnett and Jukka-Pekka Onnela. Change point detection in correlation networks. Scientific reports, 6:18893, 2016.
[6] Mich‘ele Basseville and Igor V Nikiforov.Detection of abrupt changes: theory and application, volume 104. Prentice Hall Englewood Cliffs, 1993. · Zbl 1407.62012
[7] David A Bessler and Jian Yang. The structure of interdependence in international stock markets.Journal of international money and finance, 22(2):261-287, 2003.
[8] Erwin Bolthausen. On the central limit theorem for stationary mixing random fields.The Annals of Probability, pages 1047-1050, 1982. · Zbl 0496.60020
[9] St´ephane Boucheron, G´abor Lugosi, and Pascal Massart.Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. · Zbl 1279.60005
[10] Peter B¨uhlmann and Sara Van De Geer.Statistics for high-dimensional data: methods, theory and applications. Springer Science & Business Media, 2011. · Zbl 1273.62015
[11] Tony Cai, Weidong Liu, and Xi Luo. A constrained‘1minimization approach to sparse precision matrix estimation.Journal of the American Statistical Association, 106(494): 594-607, 2011. · Zbl 1232.62087
[12] Tony Cai, Weidong Liu, and Yin Xia. Two-sample covariance matrix testing and support recovery in high-dimensional and sparse settings.Journal of the American Statistical Association, 108(501):265-277, 2013. · Zbl 06158341
[13] Hao Chen and Nancy Zhang. Graph-based change-point detection.The Annals of Statistics, 43(1):139-176, 2015. · Zbl 1308.62090
[14] Alex Gibberd and Sandipan Roy. Consistent multiple changepoint estimation with fused gaussian graphical models.Annals of the Institute of Statistical Mathematics, pages 1-27, 2020.
[15] Xavier Guyon.Random fields on a network: modeling, statistics, and applications. Springer Science & Business Media, 1995. · Zbl 0839.60003
[16] Rikkert Hindriks, Mohit H Adhikari, Yusuke Murayama, Marco Ganzetti, Dante Mantini, Nikos K Logothetis, and Gustavo Deco. Can sliding-window correlations reveal dynamic functional connectivity in resting-state fmri?Neuroimage, 127:242-256, 2016.
[17] Lajos Horv´ath and Gregory Rice. Extensions of some classical methods in change point analysis.Test, 23(2):219-255, 2014. · Zbl 1305.62310
[18] Cho-Jui Hsieh, M´aty´as A Sustik, Inderjit S Dhillon, and Pradeep Ravikumar.Quic: quadratic approximation for sparse inverse covariance estimation.Journal of Machine Learning Research, 15(1):2911-2947, 2014. · Zbl 1319.65048
[19] R Matthew Hutchison, Thilo Womelsdorf, Joseph S Gati, Stefan Everling, and Ravi S Menon. Resting-state networks show dynamic functional connectivity in awake humans and anesthetized macaques.Human brain mapping, 34(9):2154-2177, 2013.
[20] Beatrix Jones and Mike West. Covariance decomposition in undirected gaussian graphical models.Biometrika, 92(4):779-786, 2005. · Zbl 1160.62328
[21] Michael G Kallitsis, Shrijita Bhattacharya, Stilian Stoev, and George Michailidis. Adaptive statistical detection of false data injection attacks in smart grids. InSignal and Information Processing (GlobalSIP), 2016 IEEE Global Conference on, pages 826-830. IEEE, 2016.
[22] Hossein Keshavarz, Clayton Scott, and XuanLong Nguyen. Optimal change point detection in gaussian processes.Journal of Statistical Planning and Inference, 193:151-178, 2018. · Zbl 1377.62175
[23] Mladen Kolar and Eric P Xing. Estimating networks with jumps.Electronic journal of statistics, 6:2069, 2012. · Zbl 1295.62032
[24] Mladen Kolar, Le Song, Amr Ahmed, and Eric P Xing. Estimating time-varying networks. The Annals of Applied Statistics, pages 94-123, 2010. · Zbl 1189.62142
[25] Jun Li and Song Xi Chen. Two sample tests for high-dimensional covariance matrices.The Annals of Statistics, 40(2):908-940, 2012. · Zbl 1274.62383
[26] Steven E Pav. Moments of the log non-central chi-square distribution.arXiv preprint arXiv:1503.06266, 2015.
[27] Sheldon M Ross.Introduction to probability models. Academic press, 2014.
[28] Sandipan Roy, Yves Atchad´e, and George Michailidis. Change point estimation in high dimensional markov random-field models.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2016.
[29] Charles Stein. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. InProceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2: Probability Theory. The Regents of the University of California, 1972. · Zbl 0278.60026
[30] Martin J Wainwright and Michael I Jordan. Graphical models, exponential families, and variational inference.Foundations and TrendsRin Machine Learning, 1(1-2):1-305, 2008. · Zbl 1193.62107
[31] Xindong Wu, Xingquan Zhu, Gong-Qing Wu, and Wei Ding. Data mining with big data. IEEE transactions on knowledge and data engineering, 26(1):97-107, 2014.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.