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.