Flexible and Sound Computational Harmonic Analysis Tools for Graphs and Networks

灵活可靠的图形和网络计算谐波分析工具

• 批准号: 1912747
• 负责人: Naoki Saito
• 金额: $ 40万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-06-15 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1912747&HistoricalAwards=false
• 关键词: Flexible; Sound; Computational; Harmonic; Analysis

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.

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

项目成果

Natural Graph Wavelet Packet Dictionaries

自然图小波包字典

• DOI: 10.1007/s00041-021-09832-3
• 发表时间: 2021
• 期刊: Journal of Fourier Analysis and Applications
• 影响因子: 1.2
• 作者: Cloninger, Alexander;Li, Haotian;Saito, Naoki
• 通讯作者: Saito, Naoki

The Scattering Transform Network with Generalized Morse Wavelets and its Application to Music Genre Classification

广义莫尔斯小波散射变换网络及其在音乐流派分类中的应用

• DOI: 10.1109/icwapr56446.2022.9947091
• 发表时间: 2022
• 期刊: Proceedings of 2022 International Conference on Wavelet Analysis and Pattern Recognition (ICWAPR
• 作者: Chak, Wai Ho;Saito, Naoki;Weber, David
• 通讯作者: Weber, David

Metrics of graph Laplacian eigenvectors

图拉普拉斯特征向量的度量

• DOI: 10.1117/12.2528644
• 发表时间: 2019
• 期刊: Wavelets and Sparsity XVIII
• 作者: Li, Haotian;Saito, Naoki
• 通讯作者: Saito, Naoki

WaveletsExt.jl: Extending the boundaries of wavelets in Julia

WaveletsExt.jl：扩展 Julia 中小波的边界

• DOI: 10.21105/joss.03937
• 发表时间: 2022
• 期刊: Journal of Open Source Software
• 作者: Liew, Zeng;Dan, Shozen;Saito, Naoki
• 通讯作者: Saito, Naoki

The extended generalized Haar-Walsh transform and applications

• DOI: 10.1117/12.2528923
• 发表时间: 2019-09
• 作者: Y. Shao;N. Saito