Collaborative Research: AF: Small: Graph Analysis: Integrating Metric and Topological Perspectives

合作研究：AF：小：图分析：整合度量和拓扑视角

• 批准号: 2310412
• 负责人: Facundo Memoli
• 金额: $ 30万
• 依托单位: Ohio State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2310412&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Graph

Graphs are one of the most common types of data across various application fields in science and engineering. Graph analysis has been central for multiple communities, including the classical graph theory community, network analysis, graph optimization, as well as the modern day graph learning communities. Traditionally, graphs are regarded as purely combinatorial objects. However, as applications of graphs proliferate, they tend to be regarded as much richer structures. For example, a graph might be viewed as a noisy skeleton of a hidden geometric domain, and there could be rich, complex data associated with its nodes or edges. While this viewpoint is not new, existing algorithmic treatments of graphs have not yet fully leveraged this perspective. In this project, the investigators aim to further integrate various (geo)metric and topological perspectives into graph analysis in order to enrich graph analysis algorithms and broaden the range of methodologies one can use to tackle diverse graph related tasks. This project will integrate ideas and notions from metric geometry, applied topology, spectral geometry and also algorithms to develop new perspectives and effective methods to analyze complex graphs. It will inject new ideas to graph analysis and learning, while at the same time also advancing the field of geometric and topological data analysis. Given the ubiquity of graphs data, methods resulting from this project can potentially impact various application fields, from scientific domains such as molecular biology, materials science, neuroscience, to engineering domains such as chip design. Results from this project will be integrated into the data science curriculum, strengthening the workforce by training undergraduates and graduates in data science.More specifically, the investigators will consider a range of important problems related to the study of individual as well as of collections of graphs. A central theme of this project is to view graphs as objects enriched beyond their combinatorial structures. Two specific research thrusts that the investigators will focus on are: (1) various graph distances, trade-offs between their discriminating power and computational complexity, and potential applications in graph sparsification and in the study of graph neural networks; and (2) modeling, recovering and using (potentially higher order) structures in graphs. To tackle the challenges emerging from these two research thrusts, the investigators will use various metric and topological methods. Examples include viewing graphs as metric spaces and bringing in topological tools (e.g., the interleaving distance from applied topology) to compare them; viewing graphs as metric measure spaces so as to use optimal transport ideas; and bringing together topological persistence through the high dimensional Laplace operator to study spectral structures induced by graphs.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.

图是科学和工程中各个应用程序领域中最常见的数据类型之一。图形分析对于多个社区来说是核心，包括经典图理论社区，网络分析，图形优化以及现代图表学习社区。传统上，图被视为纯粹的组合对象。但是，随着图的应用扩散，它们往往被认为是更丰富的结构。例如，图可能被视为隐藏几何域的嘈杂骨架，并且可能有与其节点或边缘相关的丰富，复杂的数据。尽管这种观点并不是什么新鲜事物，但现有的图形算法处理尚未完全利用这种观点。在该项目中，研究人员旨在将各种（GEO）指标和拓扑视角进一步整合到图形分析中，以丰富图形分析算法并扩大人们可以用来解决各种图形相关任务的方法范围。该项目将整合来自度量几何，应用拓扑，光谱几何形状以及算法的思想和概念，以开发新的观点和有效的方法来分析复杂图。它将向图形分析和学习注入新的想法，同时也推进了几何和拓扑数据分析领域。鉴于图形数据的无处不在，该项目产生的方法可能会影响从分子生物学，材料科学，神经科学等科学领域到诸如CHIP设计等工程领域的各个应用领域。该项目的结果将集成到数据科学课程中，通过培训本科生和数据科学的毕业生来加强劳动力。更具体地说，研究人员将考虑与个人以及图表集合有关的一系列重要问题。该项目的一个核心主题是将图形视为富含其组合结构的对象。研究人员将重点关注的两项特定的研究推力是：（1）各种图形距离，其歧视功率和计算复杂性之间的权衡以及图形稀疏中的潜在应用以及图形神经网络的研究； （2）图中的建模，恢复和使用（潜在的高阶）结构。为了应对这两个研究推力所带来的挑战，研究人员将使用各种指标和拓扑方法。示例包括将图视为度量空间，并引入拓扑工具（例如，从应用拓扑结构的交织距离）进行比较；将图视为公制量度空间，以便使用最佳的运输想法；并通过高维拉普拉斯操作员将拓扑持久性汇总到研究图形引起的光谱结构。该奖项反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，认为值得通过评估来支持。