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.

This dissertation aims to address the problem of estimating the number of communities in count-weighted networks. We propose two methods from very different perspectives.

The first method we propose is a stepwise procedure, referred to as Stepwise Model-Assisted Spectral Thresholding (SMAST), selecting the number of communities in general count-weighted networks, which are common in the real-world. In the $m$-th step of the procedure, we first cluster the nodes into $m$ groups with a certain spectral clustering method, and estimate the mean parameters of the general degree-corrected stochastic blockmodel (DCSBM). Then the adjacency matrix is normalized by the estimated degree-correction parameters as well as the solution to a small-scale matrix scaling problem. The eigenvalues of the resultant normalized adjacency matrix are then truncated with the threshold $(2+\epsilon)\sqrt{n}$ in magnitude, where $\epsilon$ is a prespecified small constant, e.g. $0.05$. The procedure continues to the $(m+1)$-th step if the number of remaining significant eigenvalues is greater than $m$, and stops otherwise.A prominent feature of this method is that it is derived under the general DCSBM, and can be applied to general count-weighted networks. In theory, if SCORE is used for spectral clustering, SMAST is shown to be consistent in estimating the true number of communities under certain assumptions that hold for a broad class of count-weighted networks. An extension of the Nonsplitting Property of SCORE to the general DCSBM, and recent results on spectral radii of inhomogeneous random matrices, play essential roles in the analyses. Extensive numerical experiments on simulated and real networks have also been conducted to demonstrate the empirical effectiveness of SMAST.

The second method is a network rank selection method based on approximate risk estimation. We treat the problem of estimating the number of communities in a network as selecting the rank of the expected adjacency matrix.For each given rank $r$, the spectral estimate of the expected adjacency matrix is obtained by spectral truncation of the observed adjacency matrix with rank $r$. The goodness of rank $r$ is evaluated by quantifying the estimation error of the estimated expected adjacency matrix. By choosing the error measure based on the binomial deviance, following existing work in the literature on risk estimation under the Bernoulli model, we can estimate the optimism of the apparent error over the true error by the divergence of the estimator with respect to the observation. Moreover, the divergence formula of any spectral function can be calculated in closed-form, which provides an estimate of the true error as the apparent error plus the divergence. This framework can be straightforwardly extended to Poisson networks, and thus can be used to solve the problem of rank selection for count-weighted networks. The closed-form formula of the estimated true error is derived in this case as well. We have applied this method to several benchmark networks in the literature and found the performance comparable and even better than other state-of-the-art model-based approaches.