High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions
Abstract
We consider the problem of Ising and Gaussian graphical model selection given n i.i.d. samples from the model. We propose an efficient threshold-based algorithm for structure estimation based known as conditional mutual information test. This simple local algorithm requires only low-order statistics of the data and decides whether two nodes are neighbors in the unknown graph. Under some transparent assumptions, we establish that the proposed algorithm is structurally consistent (or sparsistent) when the number of samples scales as n= Omega(J_min^-4 log p), where p is the number of nodes and J_min is the minimum edge potential. We also prove novel non-asymptotic necessary conditions for graphical model selection.
Cite
Text
Anandkumar et al. "High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions." Neural Information Processing Systems, 2011.Markdown
[Anandkumar et al. "High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions." Neural Information Processing Systems, 2011.](https://mlanthology.org/neurips/2011/anandkumar2011neurips-highdimensional/)BibTeX
@inproceedings{anandkumar2011neurips-highdimensional,
title = {{High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions}},
author = {Anandkumar, Animashree and Tan, Vincent and Willsky, Alan S.},
booktitle = {Neural Information Processing Systems},
year = {2011},
pages = {1863-1871},
url = {https://mlanthology.org/neurips/2011/anandkumar2011neurips-highdimensional/}
}