# Fast Haar Transforms for Graph Neural Networks

arXiv: https://arxiv.org/abs/1907.04786 · HTML: https://mlsanity.com/paper/1907.04786/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2019.

## Built on by (most cited first, 20 of 20)

- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Pushing the Limits of Fewshot Anomaly Detection in Industry Vision: Graphcore](https://mlsanity.com/paper/2301.12082/) (2023)
- [How Framelets Enhance Graph Neural Networks](https://mlsanity.com/paper/2102.06986/) (2021)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Fusing Higher-order Features in Graph Neural Networks for Skeleton-based Action Recognition](https://mlsanity.com/paper/2105.01563/) (2021)
- [Permutation Equivariant Graph Framelets for Heterophilous Graph Learning](https://mlsanity.com/paper/2306.04265/) (2023)
- [A Meta-Learning Approach for Training Explainable Graph Neural Networks](https://mlsanity.com/paper/2109.09426/) (2021)
- [Generalized energy and gradient flow via graph framelets](https://mlsanity.com/paper/2210.04124/) (2022)
- [Graph Neural Networks With Lifting-based Adaptive Graph Wavelets](https://mlsanity.com/paper/2108.01660/) (2021)
- [Haar Wavelet Feature Compression for Quantized Graph Convolutional Networks](https://mlsanity.com/paper/2110.04824/) (2021)
- [Spectral Transform Forms Scalable Transformer](https://mlsanity.com/paper/2111.07602/) (2021)
- [Framelet Message Passing](https://mlsanity.com/paper/2302.14806/) (2023)
- [Dirichlet Energy Enhancement of Graph Neural Networks by Framelet Augmentation](https://mlsanity.com/paper/2311.05767/) (2023)
- [Exploring Sparsity in Graph Transformers](https://mlsanity.com/paper/2312.05479/) (2023)
- [Frameless Graph Knowledge Distillation](https://mlsanity.com/paper/2307.06631/) (2023)
- [Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification](https://mlsanity.com/paper/2206.00979/) (2022)
- [Spectral Regularization Allows Data-frugal Learning over Combinatorial Spaces](https://mlsanity.com/paper/2210.02604/) (2022)
- [Revisiting Generalized p-Laplacian Regularized Framelet GCNs: Convergence, Energy Dynamic and Training with Non-Linear Diffusion](https://mlsanity.com/paper/2305.15639/) (2023)
- [SStaGCN: Simplified stacking based graph convolutional networks](https://mlsanity.com/paper/2111.08228/) (2021)
- [Coarse-to-Fine Contrastive Learning on Graphs](https://mlsanity.com/paper/2212.06423/) (2022)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have become a topic of intense research recently due to their powerful capability in high-dimensional classification and regression tasks for graph-structured data. However, as GNNs typically define the graph convolution by the orthonormal basis for the graph Laplacian, they suffer from high computational cost when the graph size is large. This paper introduces Haar basis which is a sparse and localized orthonormal system for a coarse-grained chain on graph. The graph convolution under Haar basis, called Haar convolution, can be defined accordingly for GNNs. The sparsity and locality of the Haar basis allow Fast Haar Transforms (FHTs) on graph, by which a fast evaluation of Haar convolution between graph data and filters can be achieved. We conduct experiments on GNNs equipped with Haar convolution, which demonstrates state-of-the-art results on graph-based regression and node classification tasks.