Flexible and Sound Computational Harmonic Analysis Tools for Graphs and Networks

近年来，由于几种科学技术趋势的融合，基于图形和网络的数据分析领域正在经历快速增长：新传感器和社交网络基础设施的出现，以及低成本计算设备的可用，引发了学术界和工业界的研究和开发活动的爆炸性增长。开发更灵活但在数学上可靠的图形数据分析工具已成为一个紧迫的问题。即将开发的算法和软件工具将对解决不同领域的图形和网络上的实际数据分析问题产生积极影响，例如生物和医学(分析在神经元网络上测量的数据)、计算机科学(分析社会网络中的友谊关系)、电气工程(监测和控制传感器网络)、地质学(测量分叉河流网络中的水流)和土木工程(监测道路网络上的交通流量)，等等。此外，这些算法和软件工具将对常规格式的数据非常有用，例如通常的数字信号和图像。这是因为这些工具可以将常规数据视为图形，从而可以提取常规方法不容易获得的信号特征。从事这个项目的学生将被培养成下一代跨学科科学家，他们在一个领域拥有深厚的知识，但对其他领域持开放态度，并试图积极寻求与领域专家(如神经科学家或土木工程师)的合作。拟议的项目还将借鉴PI在以下不同领域的经验：图像分析；科学计算；统计信号处理；计算神经科学；以及调和分析。这些学生将获得广阔的视野，这将有助于他们未来的职业生涯，无论是在学术上还是在工业上。这个项目的目标是开发灵活和完善的计算调和分析工具，用于分析记录在图形和网络上的数据，并展示它们在各种应用中的有效性。PI团队已经开发了这样一个工具，称为广义Haar-Walsh变换(GHWT)，它完全将传统的Haar-Walsh小波包变换从规则的格子设置提升到更一般的图形设置。然而，这还不够。拟议的项目将扩展GHWT，使其更加灵活和适应感兴趣的图形数据。特别是，PI团队将开发扩展的GHWT(EGHWT)和相关的图的最佳基选择算法，在计算成本相似的情况下显著改进以前的GHWT，并将其应用于从同时图像分割和压缩到矩阵数据分析的重要问题。PI团队还将研究给定图形的自然对偶域是什么，以及如何构建声音图形小波理论并在图形上生成平滑的多尺度基本词典。这部分从定义输入图的图拉普拉斯矩阵的任意两个特征向量之间的多尺度度量开始。然后，项目将构建图的自然对偶域，即，低维欧几里德空间，其中使用该度量嵌入这些特征向量(就像规则空间格子的傅里叶域格子)。一旦做到这一点，它应该能够通过在对偶域中适当地分组和聚集特征向量来在该图上构建自然和声音小波和多尺度基本词典，其方式类似于传统的Littlewood-Paley理论在常规格子情况下组织正弦曲线的方式。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

In recent years, the field of data analysis on graphs and networks is experiencing rapid growth due to a confluence of several trends in science and technology: the advent of new sensors and social network infrastructure, together with the availability of low-cost computing devices, has ignited an explosion in research and development activities in both academia and industry. It has become a pressing issue to develop more flexible yet mathematically sound tools for graph data analysis. The algorithms and software tools to be developed will make a positive impact in solving practical data analysis problems on graphs and networks in diverse fields, e.g., biology and medicine (analyzing data measured on neuronal networks); computer science (analyzing friendship relations in social networks); electrical engineering (monitoring and controlling sensor networks); geology (measuring stream flows in a ramified river network); and civil engineering (monitoring traffic flow on a road network), to name a few. Moreover, those algorithms and software tools will be highly useful for data in conventional formats such as usual digital signals and images. This is because those tools can treat the conventional data as graphs, consequently can extract signal features that are not readily accessible by conventional methods. 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 as neuroscientists or civil engineers). The proposed project will also bring in the insights gained by the experience of the PI in the different fields: image analysis; scientific computing; statistical signal processing; computational neuroscience; and harmonic analysis. These students will gain broad perspectives, which will be helpful for their future career, either in academia or in industry.The goal of this project is to develop flexible and sound computational harmonic analysis tools for analyzing data recorded on graphs and networks and demonstrate their usefulness on a variety of applications. The PI team has developed such a tool, called the Generalized Haar-Walsh Transform (GHWT), which completely lifted the conventional Haar-Walsh wavelet packet transform from the regular lattice setting to the much more general graph setting. Yet, that is not enough. The proposed project will extend the GHWT to make it more flexible and adaptive to graph data of interest. In particular, the PI team will develop the extended GHWT (eGHWT) and the associated best-basis selection algorithm for graphs that will significantly improve the previous GHWT with the similar computational cost, and apply it to important problems ranging from simultaneous image segmentation and compression to matrix data analysis. The PI team will also investigate what would be the natural dual domain of a given graph and how one could build a sound graph wavelet theory and generate smooth multiscale basis dictionaries on graphs. This part begins with the idea of defining a multiscale metric between any two eigenvectors of the graph Laplacian matrix of an input graph. Then, the project will construct the natural dual domain of the graph, i.e., a low dimensional Euclidean space where those eigenvectors are embedded using that metric (like the Fourier domain lattice for the regular spatial lattice case). Once this is done, it should be able to build natural and sound wavelets and multiscale basis dictionaries on that graph by appropriately grouping and clustering the eigenvectors in the dual domain in a similar manner to how the conventional Littlewood-Paley theory organizes the sinusoids in the regular lattice case.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.