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

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

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.