Building a Better Neighborhood: Learning Higher-Order Structure and Capturing Complexity in Graphs

Graphs are flexible and expressive structures for representing complex systems, making them invaluable tools for many machine learning problems. However, in the presence of higher-order dependencies (i.e., conditional probabilities in sequence data), traditional graphs underfit the true neighborhood structure. Even in cases where alternative structures like heterogeneous graphs, multilayer graphs, or hypergraphs have been used, they are typically constructed in ad hoc fashion, without regard for the purpose or application of the underlying system. But a number of recent works have shown that the assumption that a graph is a sufficient abstraction often does not hold, and that improving our capacity to model complex systems may require new ways of thinking about graphs and other relational systems. This dissertation is centered on a specific family of methods for representing complex systems as graphs, called “higher-order networks” (HONs), which encode conditional and variable orders of dependencies between nodes in a directed and weighted graph. Aligned with a surge of interest from researchers in expanding our capacity to model complex systems, it contributes novel methods for constructing HONs in unsupervised and supervised settings, demonstrates new applications of HONs, develops new approaches for using GNNs to capture neighborhood variance in graphs, and compares HONs to other state-of-the-art sequence models. This dissertation also makes novel contributions toward two applications of using complex systems for social good: predicting terrorist attacks and predicting COVID-19 exposure.