Multiscale Basis Dictionaries and Best Bases for Data Analysis on Graphs and Networks

多尺度基础字典以及图和网络数据分析的最佳基础

• 批准号: 1418779
• 负责人: Naoki Saito
• 金额: $ 47.5万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1418779&HistoricalAwards=false
• 关键词: Multiscale; Basis; Dictionaries; Best; Bases

In recent years, the advent of new sensors, measurement technologies, and social network infrastructure has provided huge opportunities to visualize complicated interconnected network structures and record data of interest at various locations in such networks. Consequently, there is an explosion of interest and demand to analyze such data and make inferences, predictions, and diagnostics. Examples of such data include, but are not limited to: biology and medicine (e.g., blood flow rates in a network of blood vessels); computer and social sciences (e.g., information flows in social networks); electrical engineering (e.g., sensor networks); hydrology and geology (e.g., river flow measurements in a ramified river network); and civil engineering (e.g., traffic flow on a road network). The investigator and his team will develop mathematical and computational tools referred to as "multiscale basis dictionaries" on a given graph, which will have a positive impact in solving practical data analysis problems on graphs and networks in diverse fields as listed above. In particular, these dictionaries will be able to capture subtle features discriminating anomalous events from normal events on graphs, which may shed light on underlying causes of such anomalies. Students engaged in this project will be trained to be the next generation of interdisciplinary scientists who have deep knowledge in one area yet have open mind to the other areas and try to actively seek collaborations with domain experts. Such an attitude and a perspective will be indispensable for their future career, either in academia or in industry.The goal of this project is to develop above-mentioned multiscale basis dictionaries and best bases selected from such dictionaries for graphs and networks, and demonstrate the usefulness by examining their performance on a variety of data analysis tasks on graphs and networks such as compression, denoising, semi-supervised learning, and anomaly detection. Mathematical and computational tools for analyzing such datasets, particularly for those on directed graphs, have not been well developed. For more conventional data supported on simple Euclidean domains and data sampled on regular lattices, harmonic analysis tools such as Fourier and wavelet transforms as well as multiscale basis dictionaries, e.g., wavelet packets and local trigonometric transforms, have a proven track record of success. This project can be viewed as the continuing effort of the investigator to transfer and extend these computational harmonic analysis tools from the realm of regular lattices and simple Euclidean domains to more general graph domains. The multiscale basis dictionaries for graphs including a complete Haar-Walsh basis dictionary will certainly enrich the current collection of data analysis tools on such domains because these dictionaries contain a huge number of possible bases from which one can quickly select a basis most suitable for a given task via the best-basis selection algorithm. In particular, any addition of mathematical and computational tools for data analysis on directed graphs is well rewarded since there are comparably few tools available despite their practical importance. This is partly because so many classes of directed graphs exist, and consequently, there has been confusion over the definitions of graph Laplacian matrices. Instead, this project provides a new viewpoint: on a directed graph, the connectivity between any two vertices are not a local concept; rather it is a global concept. Finding a shortest path connecting a given pair of vertices provides critical information on a directed graph. To utilize such information fully, spectral analysis of the distance matrices and the associated integral operators on a directed graph is performed using the singular value decomposition instead of analyzing the graph Laplacians using the eigendecomposition.

近年来，新的传感器、测量技术和社交网络基础设施的出现为可视化复杂的互联网络结构和记录此类网络中各个位置的感兴趣数据提供了巨大的机会。因此，人们对分析这些数据并进行推断、预测和诊断的兴趣和需求激增。此类数据的示例包括但不限于：生物学和医学（例如，血管网络中的血流速率）;计算机和社会科学（例如，社交网络中的信息流）;电气工程（例如，传感器网络）;水文和地质（例如，分支河流网络中的河流流量测量）;以及土木工程（例如，道路网络上的交通流量）。研究人员和他的团队将开发数学和计算工具，称为“多尺度基础字典”在一个给定的图，这将有一个积极的影响，在解决实际的数据分析问题的图和网络在不同的领域如上所述。特别是，这些字典将能够捕捉细微的特征区分异常事件从正常事件的图形，这可能会揭示这种异常的根本原因。参与该项目的学生将被培养成为下一代跨学科科学家，他们在一个领域拥有深厚的知识，但对其他领域持开放态度，并积极寻求与领域专家的合作。无论是在学术界还是在工业界，这样的态度和观点都是他们未来职业生涯中不可或缺的。本项目的目标是开发上述多尺度基字典和从这些字典中选择的最佳基用于图和网络，并通过检查它们在各种图和网络数据分析任务中的性能来证明它们的有用性，如压缩，去噪，半监督学习，和异常检测。用于分析这些数据集的数学和计算工具，特别是用于有向图的数据集的数学和计算工具，尚未得到很好的开发。对于在简单欧几里德域上支持的更常规的数据和在规则网格上采样的数据，谐波分析工具（诸如傅立叶和小波变换）以及多尺度基字典（例如，小波包和局部三角变换具有成功的证明记录。这个项目可以被看作是调查人员的持续努力，转移和扩展这些计算谐波分析工具，从领域的规则格和简单的欧几里德域更一般的图形域。图的多尺度基字典，包括一个完整的Haar-Walsh基字典，肯定会丰富目前收集的数据分析工具，这些领域，因为这些字典包含了大量的可能的基础，人们可以快速地选择一个基础最适合于一个给定的任务，通过最佳基选择算法。特别是，任何增加的数学和计算工具的数据分析有向图是很好的回报，因为有很少的工具，尽管它们的实际重要性。这部分是因为有向图的种类太多，因此，对图拉普拉斯矩阵的定义存在混淆。相反，这个项目提供了一个新的观点：在有向图上，任何两个顶点之间的连通性不是一个局部概念，而是一个全局概念。找到连接给定顶点对的最短路径提供了有向图的关键信息。为了充分利用这些信息，谱分析的距离矩阵和相关的积分算子的有向图上执行使用奇异值分解，而不是使用本征分解分析图拉普拉斯算子。