Principled and Scalable Methods for Analysis of Higher-Order Networks

Abstract

Graphs have enjoyed immense success as a model for analyzing pairwise interactions, such as friendships on Facebook, where people are encoded as nodes and friendships as edges that link nodes. However, many datasets exhibit higher-order interactions that go beyond the scope of the pairwise graph model, such as product co-purchasing data on Amazon. We lose important information by ignoring this higher-order structure. Currently, few methods for directly analyzing higher-order data exist. In this dissertation, we present principled and scalable methods for analyzing higher-order information. We first focus on the hypergraph perspective, where the hyperedges representing an interaction can connect two or more nodes at once. In the first part of the thesis, we introduce methods for analyzing hypergraphs that have multiple types of interactions. In particular, in Chapter 2 we develop a framework for detecting communities of nodes in hypergraphs that have different types or categories of hyperedges. In Chapter 3, we use the theory from Chapter 2 to construct a method for diverse recommender systems that scales to large datasets. In the next part of the thesis, we present some novel methods for dealing with hypergraphs that have special structure. In particular, in Chapter 3 we present a principled method for recovering planted "core" nodes. In the last part of the thesis, we present higher-order methods for graphs that come with edge flow metadata. In particular, in Chapter 4 we show that their associated Laplacian harmonic vectors exhibit spacial localization, and leverage this insight to create a principled algorithm that allows us to efficiently localize holes in these complexes.