×

Estimating time-varying networks. (English) Zbl 1189.62142

Summary: Stochastic networks are a plausible representation of the relational information among entities in dynamic systems such as living cells or social communities. While there is a rich literature in estimating a static or temporally invariant network from observation data, little has been done toward estimating time-varying networks from time series of entity attributes. We present two new machine learning methods for estimating time-varying networks, which both build on a temporally smoothed \(l_{1}\)-regularized logistic regression formalism that can be cast as a standard convex-optimization problem and solved efficiently using generic solvers scalable to large networks. We report promising results on recovering simulated time-varying networks. For real data sets, we reverse engineer the latent sequence of temporally rewiring political networks between Senators from the US Senate voting records and the latent evolving regulatory networks underlying 588 genes across the life cycle of Drosophila melanogaster from the microarray time course.

MSC:

62M10 Time series, auto-correlation, regression, etc. in statistics (GARCH)
62M99 Inference from stochastic processes
68T05 Learning and adaptive systems in artificial intelligence
05C90 Applications of graph theory
91F10 History, political science
92D10 Genetics and epigenetics
65C60 Computational problems in statistics (MSC2010)

Software:

glmnet; glasso; CVX

References:

[1] Arbeitman, M., Furlong, E., Imam, F., Johnson, E., Null, B., Baker, B., Krasnow, M., Scott, M., Davis, R. and White, K. (2002). Gene expression during the life cycle of Drosophila melanogaster. Science 297 2270-2275.
[2] Banerjee, O., El Ghaoui, L. and d’Aspremont, A. (2008). Model selection through sparse maximum likelihood estimation. J. Mach. Learn. Res. 9 485-516. · Zbl 1225.68149
[3] Bresler, G., Mossel, E. and Sly, A. (2008). Reconstruction of Markov random fields from samples: Some observations and algorithms. In APPROX ’08 / RANDOM ’08: Proceedings of the 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization 343-356. Springer, Berlin. · Zbl 1159.68636 · doi:10.1007/978-3-540-85363-3_28
[4] Davidson, E. H. (2001). Genomic Regulatory Systems . Academic Press, San Diego.
[5] Drton, M. and Perlman, M. D. (2004). Model selection for Gaussian concentration graphs. Biometrika 91 591-602. · Zbl 1108.62098 · doi:10.1093/biomet/91.3.591
[6] Duchi, J., Gould, S. and Koller, D. (2008). Projected subgradient methods for learning sparse Gaussians. In Proceedings of the Twenty-fourth Conference on Uncertainty in AI (UAI) 145-152.
[7] Efron, B., Hastie, T., Johnstone, I. and Tibshirani, R. (2004). Least angle regression. Ann. Statist. 32 407-499. · Zbl 1091.62054 · doi:10.1214/009053604000000067
[8] Fan, J. and Li, R. (2001). Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc. 96 1348-1360. · Zbl 1073.62547 · doi:10.1198/016214501753382273
[9] Fan J., Feng Y. and Wu, Y. (2009). Network exploration via the adaptive LASSO and SCAD penalties. Ann. Appl. Statist. 3 521-541. · Zbl 1166.62040 · doi:10.1214/08-AOAS215
[10] Friedman, J., Hastie, J. and Tibshirani, R. (2007). Sparse inverse covariance estimation with the graphical lasso. Biostat , kxm045. Available at . · Zbl 1143.62076
[11] Friedman, J., Hastie, T. and Tibshirani, R. (2008). Regularization paths for generalized linear models via coordinate descent. Technical report, Dept. Statistics, Stanford Univ.
[12] Friedman, J., Hastie, T., Hofling, H. and Tibshirani, R. (2007). Pathwise coordinate optimization. Ann. Appl. Statist. 1 302. · Zbl 1378.90064 · doi:10.1214/07-AOAS131
[13] Getoor, L. and Taskar, B. (2007). Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning) . MIT Press, Cambridge, MA. · Zbl 1141.68054
[14] Grant, M. and Boyd, S. (2008). Cvx: Matlab software for disciplined convex programming (web page and software). Available at .
[15] Guo, F., Hanneke, S., Fu, W. and Xing, E. P. (2007). Recovering temporally rewiring networks: A model-based approach. In Proceedings of the 24th International Conference on Machine Learning 321-328. ACM Press, New York.
[16] Hanneke, S. and Xing E. P. (2006). Discrete temporal models of social networks. Lecture Notes in Computer Science 4503 115-125.
[17] Koh, K., Kim, S.-J. and Boyd, S. (2007). An interior-point method for large-scale l1-regularized logistic regression. J. Mach. Learn. Res. 8 1519-1555. · Zbl 1222.62092
[18] Kolar, R. and Xing, E. P. (2009). Sparsistent estimation of time-varying discrete Markov random fields. ArXiv e-prints.
[19] Lauritzen, S. L. (1996). Graphical Models . Oxford Univ. Press, Oxford. · Zbl 0907.62001
[20] Luscombe, N., Babu, M., Yu, H., Snyder, M., Teichmann, S. and Gerstein, M. (2004). Genomic analysis of regulatory network dynamics reveals large topological changes. Nature 431 308-312.
[21] Meinshausen, N. and Bühlmann, P. (2006). High-dimensional graphs and variable selection with the lasso. Ann. Statist. 34 1436. · Zbl 1113.62082 · doi:10.1214/009053606000000281
[22] Peng, J., Wang, P., Zhou, N. and Zhu, J. (2009). Partial correlation estimation by joint sparse regression models. J. Amer. Statist. Assoc. 104 735-746. · Zbl 1388.62046 · doi:10.1198/jasa.2009.0126
[23] Ravikumar, P., Wainwright, M. J. and Lafferty, J. D. (2010). High-dimensional ising model selection using \ell 1 regularized logistic regression. Ann. Statist. 38 1287-1319. · Zbl 1189.62115 · doi:10.1214/09-AOS691
[24] Rinaldo, A. (2009). Properties and refinements of the fused lasso. Ann. Statist. 37 2922-2952. · Zbl 1173.62027 · doi:10.1214/08-AOS665
[25] Rothman, A. J., Bickel, P. J., Levina, E. and Zhu, J. (2008). Sparse permutation invariant covariance estimation. Electron. J. Statist. 2 494. · Zbl 1320.62135 · doi:10.1214/08-EJS176
[26] Sarkar, P. and Moore, A. (2006). Dynamic social network analysis using latent space models. SIGKDD Explor. Newsl. 7 31-40.
[27] Tibshirani, R., Saunders, M., Rosset, S., Zhu, J. and Knight, K. (2005). Sparsity and smoothness via the fused lasso. J. Roy. Statist. Soc. Ser. B 67 91-108. · Zbl 1060.62049 · doi:10.1111/j.1467-9868.2005.00490.x
[28] Tseng, P. (2001). Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109 475-494. · Zbl 1006.65062 · doi:10.1023/A:1017501703105
[29] van Duijn, M. A. J., Gile, K. J. and Handcock, M. S. (2009). A framework for the comparison of maximum pseudo-likelihood and maximum likelihood estimation of exponential family random graph models. Social Networks 31 52-62.
[30] Wainwright, M. J. and Jordan, M. I. (2008). Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn. 1 1-305. · Zbl 1193.62107 · doi:10.1561/2200000001
[31] Wainwright, M. J. (2009). Sharp thresholds for high-dimensional and noisy sparsity recovery using \ell 1 -constrained quadratic programming (lasso). IEEE Trans. Inform. Theory 55 2183-2202. · Zbl 1367.62220 · doi:10.1109/TIT.2009.2016018
[32] Watts, D. and Strogatz, S. (1998). Collective dynamics of ‘small-world’ networks. Nature 393 440-442. · Zbl 1368.05139
[33] Yuan, M. and Lin, Y. (2007). Model selection and estimation in the Gaussian graphical model. Biometrika 94 19-35. · Zbl 1142.62408 · doi:10.1093/biomet/asm018
[34] Zhou, S., Lafferty, J. and Wasserman, L. (2008). Time varying undirected graphs. In Conference on Learning Theory (R. A. Servedio and T. Zhang, eds.) 455-466. Omnipress, Madison, WI.
[35] Zou, H. and Li, R. (2008). One-step sparse estimates in nonconcave penalized likelihood models. Ann. Statist. 36 1509. · Zbl 1142.62027 · doi:10.1214/009053607000000802
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.