ATD: Diffusion and Transport on Graphs: Active Learning, Low-Dimensional Representations, and Anomaly Detection

从生物学和化学到计算机视觉和图像处理，再到地理学和经济学等科学学科的数据自然地被表示为图形。例如，图中的每个节点可以表示一个观察到的数据点，其边连接相似的数据点。或者，单个观察到的数据点可以被理解为其本身的图形（例如，地理地图或分子）。为了有效地分析这些数据集，考虑潜在结构并有效地扩展到具有大量节点的图的计算方法是必不可少的。为了充分利用当代传感器和模拟在tb级规模上生成的丰富多样的图形数据，需要严格的数学和易于处理的算法。在这种情况下，研究者将开发方法来表示，分析和学习异构图上的函数。该项目将开发面向公众的开源软件，并为研究生，特别是那些来自代表性不足群体的研究生提供培训机会。该项目将侧重于两个相互关联的设置：(i)通过时间非齐次扩散过程对图上的函数进行半监督学习，该过程从少量函数查询中推断出统计和几何性质；（ii）通过最优传输概念分析异质图的概率分布。在半监督学习的背景下，图的几何形状将通过主动学习与揭示的标签信息相结合，产生时间非齐次的马尔可夫扩散矩阵，简洁地表征数据。当考虑由具有不同节点数量和连接属性的异构图组成的数据集时，将利用Gromov-Wasserstein距离框架进行变化和异常检测。这项工作的重点将放在图论、高维概率和统计以及机器学习的核心问题上，但许多有趣的猜想和提出的算法将直接受到实际数据科学问题的推动。遥感图像处理将作为一个特别广泛的影响核心理论和算法的研究。一套具有数学性能保证的半监督学习和图形分析工具将作为开源软件发布。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Data across scientific disciplines ranging from biology and chemistry to computer vision and image processing to geography and economics are naturally represented as graphs. For example, each node in a graph may represent an observed data point, with edges connecting similar data points. Alternatively, a single observed data point may be understood as a graph in and of itself (e.g., a geographic map or a molecule). In order to efficiently analyze such datasets, computational methods that account for latent structure and scale efficiently to graphs with large numbers of nodes are essential. Both rigorous mathematics and tractable algorithms are required to make full use of rich and varied graph data generated at terabyte scale by contemporary sensors and simulations. In this context, the investigator will develop methods for representing, analyzing, and learning functions on heterogeneous graphs. The project will develop open-source software available to the public and provide training opportunities for graduate students, particularly those from underrepresented groups. The project will focus on two interconnected settings: (i) semisupervised learning of functions on a graph via time-inhomogeneous diffusion processes that infer statistical and geometric properties from a small number of function queries; (ii) analysis of probability distributions across heterogeneous graphs via notions of optimal transport. In the context of semisupervised learning, the geometry of the graph will be combined with revealed label information via active learning, yielding time-inhomogeneous Markov diffusion matrices that succinctly characterize the data. When considering datasets consisting of heterogeneous graphs with differing numbers of nodes and connectivity properties, the framework of Gromov-Wasserstein distances will be leveraged for change and anomaly detection. The emphasis of this work will be on core problems in graph theory, high-dimensional probability and statistics, and machine learning, but many of the conjectures of interest and proposed algorithms will be directly motivated by real data science problems. Remotely sensed image processing will feature as a particular broader impact of the core theoretical and algorithmic investigations. A suite of semisupervised learning and graph analysis tools that enjoy mathematical performance guarantees will be released as open-source software.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.