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

CRII：CIF：学习网络中的隐藏结构：基本限制和高效算法

• 批准号: 1755960
• 负责人: Jiaming Xu
• 金额: $ 17.44万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-01 至 2019-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1755960&HistoricalAwards=false
• 关键词: CRII; CIF; Learning; Hidden; Structures

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.

在许多当代应用程序（例如推荐系统，网络隐私和基因组学）等许多当代应用中，学习隐藏结构的问题。该问题与高维统计推断和大规模网络分析相交。一方面，经典的统计范式着重于学习算法的最佳统计性能，而它忽略了随着网络数据的大量大规模的计算复杂性，该计算复杂性变得越来越重要。另一方面，计算机科学家主要专注于最坏情况下的计算有效近似算法，而他们忽略了可以利用的基本统计结构来提高算法性能。这项研究结合了统计和计算观点，以表征基本性能限制，并开发有效的最佳算法来学习网络中的隐藏结构。这项研究具有两个相互关联的推力：图形估计和图形匹配。 Graphon估计从网络的单个快照中学习网络的基本生成机制。图形匹配与两个图形的顶点集匹配具有相关边缘的两个图形集，以最大程度地减少邻接分歧的数量。这项研究涉及：（1）通过利用光谱图理论，凸出松弛和统计物理学来开发用于图形估计和图形匹配的有效算法； （2）通过从信息理论，凸双重性理论和随机矩阵理论中绘制工具来得出尖锐的统计绩效限制； （3）识别基本计算障碍，该计算障碍将计算有效程序限制在达到最佳统计绩效。研究者还将这项研究中开发的算法部署到真实的网络数据中，从而导致快速准确的算法，以促进推荐系统的偏好，社交网络中的匿名化以及基因组学中的DNA组装。该奖项反映了NSF的法定任务，并通过使用基金会的智能效果和广泛的crakia和广泛的评估来进行评估。