UC Davis

This dissertation aims to address the statistical consistency for two classical structural learning problems, one is community detection in networks, and the other one is structural learning in probabilistic graphical models. The methods studied in this dissertation are straightforward and widely used. However, their statistical consistency has not been fully revealed, especially under more sophisticated conditions that emerge in modern data analysis.Chapter 2 discusses my joint work with Professor Xiaodong Li and Lihua Lei. We study the hierarchy of communities in real-world networks under a generic stochastic block model, in which the connection probabilities are structured in a binary tree. Under such model, we prove the strong consistency of a standard recursive bi-partitioning algorithm under a wide range of model param- eters, which include sparse networks with node degrees as small as O(logn). In addition, unlike most of existing work, our theory covers multi-scale networks where the connection probabilities may differ by orders of magnitude, which comprise an important class of models that are practically relevant but technically challenging to deal with. Finally we demonstrate the performance of our algorithm on synthetic data and real-world examples. Chapter 3 discusses my work supervised by Professor Xiaodong Li and Professor Yu Hu. In this work, we are interested in the problem of learning the directed acyclic graph (DAG) when data are generated from a linear structural equation model (SEM) and the causal structure can be characterized by a polytree. Under the Gaussian polytree models, we study sufficient and necessary conditions on the sample sizes for the well-known Chow-Liu algorithm to exactly recover both the skeleton and the equivalence class of the polytree, which is uniquely represented by a CPDAG. We also consider extensions to the sub-Gaussian case, and then study the estimation of the inverse correlation matrix under such models. Our theoretical findings are illustrated by comprehensive numerical simulations, and experiments on benchmark data also demonstrate the robustness of polytree learning when the true graphical structures can only be approximated by polytrees.