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

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

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.