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理论在常规晶格情况下组织正弦波的方式类似。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.