Mathematical Foundations of Multiscale Graph Representations and Interactive Learning

多尺度图表示和交互式学习的数学基础

• 批准号: 0808847
• 负责人: Mauro Maggioni
• 金额: $ 32万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-05-15 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0808847&HistoricalAwards=false
• 关键词: Mathematical; Foundations; Multiscale; Graph; Representations

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.

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