Models and Inference with Network Structure

Abstract:

Complex, structured data is ubiquitous in both industrial and academic settings and has elicited a commensurate interest in utilizing structured data to inform inference and decisions. We are particularly interested in data that has network structure and on problems that benefit from the application of network-based algorithms. We focus on four research problems of interest: scalable and realistic models for network valued data, graph-based estimation of information theoretic quantities, summarization of complex time-varying data using dynamic graphs, and finally community detection on large multi-layer networks.

This work advances the state-of-the-art in several directions. First, it introduces a new framework for complex hierarchical network interaction data using the concept of edge exchangeability. Second, it obtains new tight bounds for the multi-class Bayes error rate based on a graph-based technique, specifically the minimal spanning tree. Third, it introduces a new estimation method for Henze-Penrose divergence, a quantity relevant for graph-based multi-class classification. Fourth, it introduces adaptive directed information for estimating directed interaction networks. Fifth, it provides a comprehensive approach to multi-layer network community detection. Throughout, examples are provided using real datasets, such as the Enron email dataset, an arXiv dataset, and Twitter.