Spectral methods for single and multiple graph inference

North Carolina State University, Raleigh NC

Investigators

Abstract

Networks provide an elegant and natural representation for describing a collection of entities and their interactions. Network data appear prominently in many scientific domains such as ecology (food webs), sociology (social networks), biology (protein-protein interactions), telecommunications, and cybersecurity (cellular and computer networks). This project addresses two important inference problems in network science. The first is to quantify the similarities between a collection of networks for the purpose of classifying a network into categories such as being typical or anomalous. The second is dimension reduction for large and complex networks; this is essential in the development of memory and computationally efficient algorithms for analyzing network data. The investigator will complement theoretical and methodological investigations by developing open-source software packages for network analysis, and mentoring graduate students in statistics and data science. The research program has three main aims. The first is to study efficient parameters estimation for latent position graphs. Given a latent position graph, the investigator will derive both uniform error bounds and normal approximations for its estimated latent positions. The second aim is to develop valid and robust two-sample testing procedures for latent position graphs with a particular emphasis on the setting where the link function is an unknown radial function. Combining these two aims allows practitioners to compare graphs while ignoring irrelevant features such as difference in edge densities or nodes relabeling in real data. The third aim is to conduct perturbation analysis of randomized singular value decomposition (RSVD) when used for dimension reduction of large, noisy graphs. Viewing the observed adjacency matrix as arising from a general “signal-plus-noise” framework, the investigator will derive upper bounds for the spectral and two-to-infinity-norm distances between the approximate singular vectors of the observed matrix and the true singular vectors of the signal matrix. These upper bounds will depend on the signal-to-noise ratio and the number of power iterations. Finally, as part of this third aim the investigator will also derive uniform entrywise approximation for recovery of a low-rank signal matrix using RSVD. Results established under this third aim can be applied to general matrix-valued data beyond graphs. 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.