BIGDATA: F: Collaborative Research: Mining for Patterns in Graphs and High-Dimensional Data: Achieving the Limits

虽然现代数据集非常大，但每个变量的信息量往往相对较小。这包括来自基因组学、社交网络以及机器学习和人工智能中的许多应用程序的数据集。例如，在基因组学中，我们经常跟踪数十万个基因，但每个基因只有几百个独立的样本。同样，在线社交网络规模庞大，但友谊的结构只给我们提供了相对较少的每个人的数据。这种类型的数据被称为“高维”，对数学、统计学和计算机科学提出了新的挑战，特别是当它们(与所有真实数据一样)是噪声或不完整的时候。这个项目将准确地确定何时以及如何在这些海量但有噪声的数据集中找到模式，为许多领域的科学家提供有用的指导，他们需要多少数据才能得出可靠的结论，并开发新的算法，以高效和优化地解决现代数据科学问题。通过对社区发现、噪声图同构和矩阵/张量分解的研究，该项目将开发一个通用框架，以1)定位信息论极限，低于该极限，观测噪声太大而无法检测潜在模式，甚至无法判断模式是否存在；2)设计成功的高效算法，一直到尽可能低的信噪比；3)证明重要的算法类在某些困难的情况下需要超多项式时间。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

While modern datasets are very large, the amount of information per variable is often relatively small. This includes datasets from genomics, social networks, and many applications in machine learning and artificial intelligence. For instance, in genomics we often track hundreds of thousands of genes, but only have a few hundred independent samples for each one. Similarly, online social networks are massive, but the structure of friendships only gives us a relatively small amount of data per individual. This kind of data is called "high-dimensional", and poses new challenges for mathematics, statistics, and computer science, especially when (as with all real data) they are noisy or incomplete. This project will identify exactly when and how it is mathematically possible to find patterns in these massive but noisy datasets, giving scientists across many fields a useful guide to how much data they need to draw reliable conclusions, and to develop new algorithms that will solve modern data science problems efficiently and optimally.Through the study of community detection, noisy graph isomorphism, and matrix/tensor factorization, this project will develop a general framework to 1) locate the information-theoretic limit below which the observation is too noisy to detect the underlying pattern, or even to tell if a pattern exists; 2) devise efficient algorithms that succeed all the way down to the lowest possible signal-to-noise ratio; 3) prove that important classes of algorithms need super-polynomial time in certain hard regimes.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.