Graph Density and Uncertainty of Graphical Model Selection Algorithms

Graphical models became a popular tool in machine learning and data analysis. Graphical Model Selection Problem is a problem to recover a specific graph structure (graphical model) from a set of data. In many cases the data are given by a sample of observations of some multivariate distribution. In this setting any reconstruction algorithm can be evaluated by uncertainty of identification of the hidden graphical model by observations. In the present paper we study uncertainty of identification of so-called concentration graph which represents a dependence structure for the components of multidimensional random vector. We introduce and discuss different measures of uncertainty appropriate for the concentration graph identification problem and compare on this basis different identification algorithms, including optimization (graphical lasso) algorithm and a family of known multiple hypotheses testing algorithms. Novelty of our approach is in the study of dependence of uncertainty on the graph density. Some new and interesting phenomena are observed and discussed.