CAREER: Statistical Inference on Random Graphs and Hypergraphs: Geometry, Combinatorics, and Computation

Over the past few decades, the study of complex networks has evolved into an important and dynamic field of research due to the ubiquity of relational data. Statistics plays an increasingly significant role in network analysis because it provides a toolbox for extracting information from noisy network data. Statistical inferential methods have been successfully applied to analyze a broad range of real-world networks, including social, biological, and technological networks. The overall objective of this research is to further advance the theory and methodology for statistical inference with network data. By modeling large-scale networks as random graphs, this research will develop novel algorithmic techniques and analytic tools for inferential tasks on networks. Furthermore, this project will provide research opportunities to undergraduate and graduate students with diverse backgrounds, broadening their participation in interdisciplinary research through summer programs. By integrating research topics with teaching, the PI will also develop innovative statistics curricula that foster students' interest in data science. The research will focus on the following aspects of statistical inference on random graphs. First, to analyze networks with node attributes, the project will study a class of random geometric graphs, as well as associated detection and recovery problems. Second, a major computational challenge in network analysis lies in the recovery of hidden combinatorial structures. The project will address a variety of such combinatorial structural learning problems, such as geometric graph matching and vertex ordering in nonparametric models. Third, while many real-world networks are hypergraphs, the tools and results are relatively limited, and this project will fill the gap by developing new models and methods for analyzing random hypergraphs. For each of these problems, the research will follow a principled approach to characterize the information-theoretic and computational limits. The project will also develop and implement novel efficient algorithms with provable guarantees, including combinatorial methods based on subgraph counts and improved spectral methods. In summary, the research will substantially forward the development of statistical methods for random graphs, leading to long-term advances in our understanding of network data. 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.