Tensor Methods for Network Analysis

Abstract

In this dissertation, we study two canonical statistical problems in the hypergraph setting -- community detection and non-parametric estimation. We focus on the stochastic hypergraph block model, where each vertex belongs to a community, and hyperedge probabilities are dependent on the communities of its corresponding vertices. Our main algorithmic tool for community detection is the tensor power method, in which a tensor map is repeatedly applied until convergence. Despite being a direct generalization of the matrix power method, the tensor power method has interesting differences compared to the matrix power method, which we explore in this work. We begin by showing that in certain parameter ranges, the tensor power method succeeds in recovering eigenvectors when applied to expected adjacency tensor. Since the expected adjacency tensor is not orthogonally decomposable, this is already a nontrivial result, as most of the tensor decomposition that exist in the literature are for orthogonally decomposable tensors. Next, interpreting the adjacency tensor as a perturbation of the expected adjacency tensor, we show that applying the tensor power method to the adjacency tensor can be used to recover the underlying communities of the stochastic hypergraph block model, by way of recovering the eigenvectors of the expected adjacency tensor. For this step, we require a tensor concentration result, and we show that the adjacency tensor concentrates around the expected adjacency tensor in spectral norm by using an enhanced ε-net argument. Regarding non-paremetric estimation, we study statistical and algorithmic aspects of using hypergraphons, which are limits of large hypergraphs, for modeling higher-order interactions. Although hypergraphons are extremely powerful from a modeling perspective, we consider a restricted class of Simple Lipschitz Hypergraphons (SLH), which are more amenable to efficient estimation. We also provide rates of convergence for our estimator that are optimal for the class of SLH. Simulation results are provided to corroborate the theory.