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

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

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.