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

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

• 批准号: 2310411
• 负责人: Yusu Wang
• 金额: $ 30万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2310411&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.

图是科学和工程各个应用领域最常见的数据类型之一。图分析一直是多个社区的核心，包括经典图论社区、网络分析、图优化以及现代图学习社区。传统上，图被视为纯粹的组合对象。然而，随着图的应用激增，它们往往被认为是更丰富的结构。例如，图可能被视为隐藏几何域的嘈杂骨架，并且可能存在与其节点或边关联的丰富、复杂的数据。虽然这种观点并不新鲜，但现有的图算法处理尚未充分利用这种观点。在这个项目中，研究人员的目标是进一步将各种（几何）计量和拓扑视角整合到图分析中，以丰富图分析算法并扩大可用于解决各种图相关任务的方法范围。该项目将整合度量几何、应用拓扑、谱几何和算法的思想和概念，以开发新的视角和有效的方法来分析复杂的图形。它将为图分析和学习注入新的思路，同时也推进几何和拓扑数据分析领域的发展。鉴于图形数据无处不在，该项目产生的方法可能会影响各个应用领域，从分子生物学、材料科学、神经科学等科学领域到芯片设计等工程领域。该项目的结果将被纳入数据科学课程，通过培训数据科学的本科生和研究生来加强劳动力队伍。更具体地说，研究人员将考虑与个人以及图表集合的研究相关的一系列重要问题。该项目的中心主题是将图视为超出其组合结构的丰富对象。研究人员将重点关注的两个具体研究重点是：（1）各种图距离，其判别能力和计算复杂性之间的权衡，以及图稀疏化和图神经网络研究中的潜在应用； (2) 建模、恢复和使用图中的（可能更高阶的）结构。为了应对这两个研究方向出现的挑战，研究人员将使用各种度量和拓扑方法。示例包括将图视为度量空间并引入拓扑工具（例如，与应用拓扑的交错距离）来比较它们；将图表视为度量测量空间，以便使用最佳传输思想；并通过高维拉普拉斯算子将拓扑持久性结合起来，研究由图引起的谱结构。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。