CAREER: Learning and Leveraging the Structure of Large Graphs: Novel Theory and Algorithms

从基因相互作用网络和大脑到无线传感器网络和电网，存在着许多大型、复杂的相互作用系统。图论为量化和利用这种相互作用提供了一种优雅而强大的数学形式。毫不奇怪，许多现代科学和工程任务依赖于图结构的发现和利用。不幸的是，在数据驱动算法的图形分析能力和它们在现实世界中的适用性之间存在着明显的脱节。具体而言，现有算法面临以下主要挑战：(i)依赖大量昂贵的实验/测量；这在科学和工程中通常遇到的大型系统中是令人望而却步的。（ii）对可获得的经过整理和标记的数据集的依赖；这在狭窄的学科范围之外是站不住脚的。为最坏情况进行设计；这种缺乏对问题特有结构的适应性严重损害了它们的统计和计算效率。为了应对上述挑战，本研究项目将关闭传统机器学习系统的闭环，其中数据采集和学习算法是分开设计的。该项目将设计几种新颖的压缩、自适应和交互算法，以有效地利用问题中的结构。这些将由学习理论的基础进步和利用图中的结构来补充。方法学的进步将对多种领域产生影响，如弹性网络基础设施、强大的神经成像和流行病的干预设计。研究活动与全面的教育、指导和推广计划紧密结合，将提高STEM的认识、获取和包容性，特别是在科学和工程领域的数据驱动方法方面。本项目的技术贡献分为两个相互关联的主题：(1)从压缩和交互获取的数据中学习图的结构。这一主题的研究将揭示数据获取成本和统计准确性之间新的和有趣的权衡。这些将由在贸易空间中实现不同点的最小最大最优算法补充。(2)利用图结构实现高效推理。该主题的研究统一于图上水平集估计的一般问题，并将为非参数学习、元学习和顺序决策的理论做出基础贡献。研究主题包括广泛的实验验证，与领域专家的合作，以及对实践产生有意义和长期影响的转化活动。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

From genetic interaction networks and the brain to wireless sensor networks and the power grid, there exist many large, complex interacting systems. Graph theory provides an elegant and powerful mathematical formalism for quantifying and leveraging such interactions. Unsurprisingly, many modern tasks in science and engineering rely on the discovery and exploitation of the structure of graphs. Unfortunately, there is a stark disconnect between the purported capabilities of data-driven algorithms for graph analytics and their real world applicability. Specifically, the following key challenges emerge for existing algorithms: (i) Reliance on large number of expensive experiments/measurements; this is prohibitive in the large systems typically encountered in science and engineering. (ii) Reliance on the availability of curated and labeled datasets; this is untenable outside a narrow set of disciplines. (iii) Design for worst-case scenarios; this lack of adaptivity to structure unique to the problem severely impairs their statistical and computational efficiency. In response to the above challenges, this research program will close the loop on traditional machine learning systems where data acquisition and learning algorithms are designed separately. The project will devise several novel compressive, adaptive, and interactive algorithms that efficiently exploit structure in the problem. These will be complemented by foundational advances to the theory of learning and leveraging structure in graphs. The methodological advances will have impact on diverse areas such as resilient cyber-infrastructure, robust neuroimaging, and intervention design for pandemics. The research activities are tightly integrated with a comprehensive education, mentoring, and outreach plan that will increase awareness, access, and inclusion in STEM, especially with respect to data-driven methods in science and engineering. The technical contributions of this project are organized into two interrelated themes: (1) Learning the structure of graphs from compressively and interactively acquired data. The research in this theme will reveal new and interesting tradeoffs between the cost of data acquisition and statistical accuracy. These will be complemented by minimax optimal algorithms that achieve various points in the tradespace. (2) Leveraging the graph structure to accomplish efficient inference. The research in this theme is unified by the general problem of level set estimation on graphs and will result in foundational contributions to the theory of nonparametric learning, meta-learning, and sequential decision making. The research themes feature extensive experimental validation, collaboration with domain experts, and translational activities with the view of driving meaningful and long-term impacting on practice.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.