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-Paley 理论在规则格子情况下组织正弦曲线的方式。该奖项反映了 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