Structure Detection in High Dimensional Graphical Models

Abstract

Graphical models are powerful tools to study the dependency structures among random variables. In this thesis, we study structure detection problems in high dimensional graphical models. Given independent samples generated from a graphical model, the goal of structure detection is to distinguish whether the underlying graph is empty, or contains a subgraph of a certain structure.

In the first part of the thesis, we study the information-theoretic limits of structure detection problems in high temperature ferromagnetic (positive interaction only) Ising models. First, based on the high temperature expansion of Ising models, we derive a general information-theoretic lower bound for arbitrary alternative hypothesis. We then propose a general framework of linear tests on the sample covariance matrix that matches our minimax lower bounds. Our results reveal that a key quantity called graph arboricity drives the testability of the problem.

In the second part of the thesis, we discuss the computational limits of structure detection problems. First, based on a computational hardness conjecture of sparse principal component analysis, we prove that, unless the signal is strong enough, no polynomial time linear tests on the sample covariance matrix are capable of testing this problem. We also give another computational lower bound based on the oracle computational model, where the computational complexity is measured by the times an algorithm queries an oracle. Our results show that, for problems with high graph arboricity, the information-theoretic limits are unachievable by tractable algorithms.

In the third part of the thesis, we propose a unified framework to quantify local and global inferential uncertainty for high dimensional nonparanormal graphical models. In particular, we consider the problems of testing the presence of a single edge and constructing a uniform confidence subgraph. We develop pseudo likelihood based score and Wald tests to eliminate the unknown nuisance transformations. A U-statistic multiplier bootstrap method is then proposed to construct the confidence subgraph.