Mathematical Foundations of Multiscale Graph Representations and Interactive Learning

大型高维数据集和图形的分析受到许多重要应用的推动，例如图像和文档数据库的研究，以及复杂动态系统(如交易数据、天气模式、分子动力学)的建模。这项研究涉及开发新的数学技术，用于从大数据集中提取信息并将其可视化。数据布局、可视化和人类交互以多尺度表示为中心，这使得在多个分辨率级别上访问数据、派生信息和与其相关联的推理过程成为可能。根据手头任务的不同，人与人之间的交互作用会影响数据的几何和推理过程。这些技术的成功开发将对任何适合于图形表示的应用数据产生重大影响，例如引文网络、社会网络、交易数据关联以及生物系统的许多方面，如基因表达和代谢途径。它还将揭示高维数据集和图的新的有趣的多尺度几何结构，并导致更好地理解如何从高维数据集和图中提取信息。本研究基于图上的扩散过程，提出了新的图和数据集的多尺度嵌入技术和算法。这样的过程被用来在不同的尺度上生成图的多尺度嵌入，以及在有和没有人工交互的情况下执行学习任务。这些多尺度嵌入在度量失真方面具有很强的量化保证。同时，构造的多尺度基具有在图上稀疏表示函数的可证明能力，使得它们非常适合于可视化和学习。我们在从基因网络到文档语料库的数据集上展示了上述内容。

ABSTRACTThe analysis of large high-dimensional data sets and graphs is motivated by many important applications, such as the study of databases of images and documents, and the modeling of complex dynamical systems (e.g. transaction data, weather patterns, molecular dynamics). This research involves the development of novel mathematical techniques for extracting and visualizing information from large data sets. The data layout, visualization, and human interaction are centered around multi-scale representations, which make it possible to access the data, the derived information and the inference processes associated with it at multiple levels of resolution. The human interaction affects both the geometry and the inference processes on the data, depending on the task at hand. The successful development of these techniques will have substantial impact on any application data which lends itself to a graph representation, such as citation networks, social networks, transaction data correlations, and many aspects of biological systems like gene expression and metabolic pathways. It will also reveal new and interesting multiscale geometric structures of high-dimensional data sets and graphs, and lead to a better understanding of how to extract information from them.This research develops novel multiscale embedding techniques and algorithms for graphs and data sets, based on diffusion processes on graphs. Such processes are used to generate multiscale embeddings of a graph, at different scales, as well as to perform learning tasks, with and without human interaction. These multiscale embeddings have strong quantitative guarantees in terms of metric distortion. At the same time, multiscale bases are constructed which have provable capabilities of sparsely representing functions on the graph, making them very well suited for both visualization and learning. We demonstrate the above on data sets ranging from gene networks to document corpora.