SCIENTIA SINICA Informationis, Volume 46 , Issue 7 : 870-882(2016) https://doi.org/10.1360/N112015-00136

Structure learning in graphical models incorporating the scale-free prior

More info
  • ReceivedOct 7, 2015
  • AcceptedNov 26, 2015


In this paper, we consider the problem of structure learning in graphical models under the prior that the underlying networks are scale free. We propose a novel regularization model, which incorporates the scale-free prior, with a penalty that is a hybrid of the Log-type and $L_q$-type penalty functions. An iterative reweighted $L_1$ algorithm is employed to solve the model. Numerical studies show that our method is both effective and practical and performs well in terms of parameter estimation and model selection.

Funded by




[1] Barabási A L, Albert R. Statistical mechanics of complex networks. Rev Mod Phys, 2002, 74: 47-97 CrossRef Google Scholar

[2] Ewards D M. Introduction to Graphical Modelling. New York: Springer, 2000. Google Scholar

[3] Dempster A P. Covariance selection. Biometrika, 1972, 32: 95-108. Google Scholar

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

[5] Meinshausen N, Bühlmann P. High-dimensional graphs with the lasso. Ann Statist, 2006, 34: 1436-1462 CrossRef Google Scholar

[6] Yuan M, Lin Y. Model selection and estimation in the Gaussian graphical model. Biometrika, 2007, 94: 19-35 CrossRef Google Scholar

[7] Friedman J, Hastie T, Tibshirani R. Sparse inverse covariance estimation with the graphical lasso. Biostat, 2008, 9: 432-441 CrossRef Google Scholar

[8] Ravikumar P, Raskutti G, Wainwright M J, et al. High-dimensional covariance estimation by minimizing $L_1$-penalized log-determinant. Electron J Stat, 2011, 5: 935-980 CrossRef Google Scholar

[9] Peng J, Wang P, Zhou N, et al. Partial correlation estimation by joint sparse regression models. J Am Statist Assoc, 2009, 104: 735-746 CrossRef Google Scholar

[10] Hero A, Rajaratnam B. Hub discovery in partial correlation graphs. IEEE Trans Inf Theory, 2012, 58: 6064-6078 CrossRef Google Scholar

[11] Tan K M, London P, Mohan K, et al. Learning graphical models with hubs. J Mach Learn Res, 2014, 15: 3297-3331. Google Scholar

[12] Liu Q, Ihler A T. Learning scale free networks by reweighed $L_1$ regularization. In: Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, Fort Lauderdale, 2011. 15: 40-48. Google Scholar

[13] Knight K, Fu W J. Asymptotics for lasso-type estimators. Ann Statist, 2000, 28: 1356-1378 CrossRef Google Scholar

[14] Fan J Q, Li R Z. Variable selection via nonconcave penalized likelihood and its oracle properties. J Am Statist Assoc, 2001, 96: 1348-1360 CrossRef Google Scholar

[15] Huang J, Horowitz J L, Ma S. Asymptotic properties of bridge estimators in sparse high-dimensional regression models. Ann Statist, 2008, 36: 587-613 CrossRef Google Scholar

[16] Zhang H, Wang Y, Chang X Y, et al. $L_{1/2}$ regularization. Sci Sin Inform, 2010, 40: 412-422 [张海, 王尧, 常象宇, 等. $L_{1/2}$正则化. 中国科学: 信息科学, 2010, 40: 412-422]. Google Scholar

[17] Lange K, Hunter D, Yang I. Optimization transfer using surrogate objective functions (with discussion). J Comput Graph Statist, 2000, 9: 1-59. Google Scholar

[18] Witten D, Friedman J H, Simon N. New insights and faster computations for the graphical lasso. J Comput Graph Statist, 2011, 20: 892-900 CrossRef Google Scholar

[19] van der Vaart A W. Asymptotic Statistics. New York: Cambridge University Press, 1998. 61-67. Google Scholar

[20] Geyer C. On the asymptotics of constrainted M-estimation. Ann Statist, 1994, 22: 1993-2010 CrossRef Google Scholar

[21] Zou H, Li R Z. One-step sparse estimates in nonconcave penalized likelihood models. Ann Statist, 2008, 36: 1509-1533 CrossRef Google Scholar

[22] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286: 509-512 CrossRef Google Scholar

[23] Spellman P T, Sherlock G, Zhang M Q, et al. Comprehensive identification of cell cycleregulated genes of the yeast saccharomyces cerevisiae by microarray hybridization. Mol Biol Cell, 1998, 9: 3273-3297 CrossRef Google Scholar

[24] Chen G, Larsen P, Almasri E, et al. Rank-based edge reconstruction for scale-free genetic regulatory networks. BMC Bioinformatics, 2008, 9: 75-3297 CrossRef Google Scholar

[25] Ravikumar P, Wainwright M J, Lafferty J D. High-dimensional Ising model selection using $l_1$-regularized logistic regression. Ann Statist, 2010, 38: 1287-1319 CrossRef Google Scholar

[26] Chen S, Witten D, Shojaie A. Selection and estimation for mixed graphical models. Biometrika, 2015, 102: 47-64 CrossRef Google Scholar

[27] Zhang L J, Zhang H. Joint estimation of multiple graphical models via bridge. Appl Math: J Chinese Univ (Ser A), 2014, 92: 127-137 [张凌洁, 张海. 多图模型的联合估计的群桥方法. 高校应用数学学报, 2014, 92: 127-137]. Google Scholar