CRII: CIF: Learning Hidden Structures in Networks: Fundamental Limits and Efficient Algorithms

Purdue University, West Lafayette IN

Investigators

Abstract

The problem of learning hidden structures in network data arises in many contemporary applications such as recommender systems, network privacy, and genomics. This problem intersects high-dimensional statistical inference and large-scale network analysis. On the one hand, classical statistical paradigm focuses on optimal statistical performance of learning algorithms, while it neglects computational complexity that becomes increasingly critical as network data gets big. On the other hand, computer scientists mostly focus on computationally efficient approximation algorithms for worst-case instances, while they neglect the underlying statistical structures that can be potentially exploited to improve the algorithm performance. This research combines both statistical and computational perspectives to characterize fundamental performance limits and develop efficient optimal algorithms for learning hidden structures in networks. This research has two interrelated thrusts: graphon estimation and graph matching. Graphon estimation learns the underlying generating mechanism of a network from a single snapshot of the network. Graph matching matches the vertex sets of two graphs with correlated edges to minimize the number of adjacency disagreements. This research involves: (1) developing efficient algorithms for graphon estimation and graph matching by exploiting insights from spectral graph theory, convex relaxations, and statistical physics; (2) deriving sharp statistical performance limits by drawing tools from information theory, convex duality theory, and random matrix theory; (3) identifying fundamental computational barriers which limit computationally efficient procedures from attaining the optimal statistical performance. The investigator also deploys the algorithms developed in this research to real network data, leading to fast and accurate algorithms for preference elicitation in recommender systems, de-anonymization in social networks, and DNA assembly in genomics. 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.