Graph density and uncertainty of graphical model selection algorithms

P. 188–201.

Valeriy Kalyagin, Ilya Kostylev

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.

Keywords: uncertainty, Graphical model, Concentration graph, Optimal identification algorithm, Graph density

Publication based on the results of: Research on graph and network structures and its applications (2023)

In book

14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers. Communications in Computer and Information Science (CCIS, volume 1913)

Vol. 1913. , Springer, 2023.