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

About This Grant

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.