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

学习网络数据中的隐藏结构的问题出现在许多当代应用中，例如推荐系统、网络隐私和基因组学。这个问题与高维统计推断和大规模网络分析交叉。一方面，经典的统计范式关注学习算法的最佳统计性能，而忽略了随着网络数据变得越来越大而变得越来越重要的计算复杂性。另一方面，计算机科学家大多专注于最坏情况下的计算效率近似算法，而忽略了潜在的统计结构，可以利用它来提高算法的性能。这项研究结合了统计和计算的角度来描述基本的性能限制，并开发有效的最佳算法来学习网络中的隐藏结构。本研究有两个相互关联的方向：图子估计和图匹配。Graphon估计从网络的单个快照中学习网络的底层生成机制。图匹配是将两个具有相关边的图的顶点集进行匹配，以最小化邻接不一致的数量。这项研究涉及：（1）通过利用谱图理论、凸松弛和统计物理学的见解，开发用于图子估计和图匹配的有效算法;（2）通过从信息论、凸对偶理论和随机矩阵理论中绘制工具，导出尖锐的统计性能限制;（3）识别限制计算高效过程获得最佳统计性能的基本计算障碍。该研究人员还将本研究中开发的算法部署到真实的网络数据中，从而为推荐系统中的偏好诱导、社交网络中的去匿名化和基因组学中的DNA组装提供了快速准确的算法。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.