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

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

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.