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.