Far apart: outliers, extremal eigenvalues, and spectral gaps in random graphs and random matrices

University Of California-San Diego, La Jolla CA

Investigators

Abstract

Technological and scientific advances in the last few decades have completely changed the way in which society operates. Massive amounts of data is produced and collected. This creates the need for data to be classified and categorized in order to extract meaningful and useful information. To model enormous networks, whether social, biological, or electrical, mathematicians and computer scientists have introduced the concepts of graphs and hypergraphs, with their tensors, adjacency matrices, and spectra, and have connected properties of the latter to properties of the former in order to better understand the structure of the current technological world. The goal of this project is to advance basic understanding of outliers in the spectra of random networks; such outliers have been connected to applications from Machine Learning to Bioinformatics and Coding Theory, as their presence or absence can be used to deduce various network properties. The results of this project can be used to develop algorithms, theoretical algorithmic guarantees, and benchmarks for a variety of applications in science and technology. Through its educational component (which includes research training opportunities for graduate and undergraduate students), this project will contribute to creating and ensuring the success of the next generation of mathematicians and data scientists. The PI will study general network models with certain symmetry properties (e.g., homogeneous and inhomogeneous bipartite random graphs, uniform and non-uniform hypergraphs, and the Hypergraph Stochastic Block Model). One part of the project involves creating and analyzing a randomized generalized eigenvalue algorithm, based on finding tight bounds on the smallest singular value for a random matrix model. Methods to be employed include concentration techniques and the non-backtracking operator, in addition to other techniques from combinatorics, probability, linear algebra, and statistics, to find sharp thresholds for regimes in which outliers may or may not exist in the variety of graph and hypergraph models. The PI will also study thresholds for community recovery and detection problems in the Hypergraph Stochastic Block Model. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.