AMATH Seminar: Random walks on graphs and hypergraphs: eigenvalues and clustering

AMATH Seminar, October 15, 2020 Sinan Askoy Pacific Northwest National Laboratory Title: Random walks on graphs and hypergraphs: eigenvalues and clustering Abstract: In this two part talk, we discuss pure and applied combinatorics problems rooted in the study of random walks. In the first half, we discuss several problems in extremal spectral graph theory pertaining to random walk parameters. First, focusing on undirected graphs, we find the minimum spectral gap of the normalized Laplacian matrix over all simple, connected n-vertex graphs, settling a conjecture of Aldous and Fill. Turning attention to directed graphs, we then consider the principal ratio, a measure of digraph irregularity based on the maximum to minimum values of vertices in the stationary distribution. Improving upon previous bounds, we prove a sharp upper bound for this ratio over all strongly connected digraphs on n vertices, and characterize all graphs achieving the upper bound. We also discuss the directed analog of the normalized Laplacian matrix, and prove a lower bound on its spectral gap. In the second half, we propose a Laplacian based approach for clustering hypergraph-structured data. We first discuss our motivations for developing hypergraph clustering methods, reviewing several areas of application. Our proposed method is rooted in recent work, which has advocated utilizing edge-dependent vertex weights to define non-reversible hypergraph random walks. Based on these random walks, we employ tools developed in the first half of the talk to construct hypergraph Laplacians and design clustering algorithms that utilize them as inputs. Testing on real data, we compare the performance of these clustering algorithms experimentally against a variety of existing hypergraph clustering methods. We conclude by highlighting avenues for future work.