# Decimated Framelet System on Graphs and Fast G-Framelet Transforms

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2020.

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

- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [How Framelets Enhance Graph Neural Networks](https://mlsanity.com/paper/2102.06986/) (2021)
- [Permutation Equivariant Graph Framelets for Heterophilous Graph Learning](https://mlsanity.com/paper/2306.04265/) (2023)
- [How Curvature Enhance the Adaptation Power of Framelet GCNs](https://mlsanity.com/paper/2307.09768/) (2023)
- [Unifying over-smoothing and over-squashing in graph neural networks: A physics informed approach and beyond](https://mlsanity.com/paper/2309.02769/) (2023)
- [A Magnetic Framelet-Based Convolutional Neural Network for Directed Graphs](https://mlsanity.com/paper/2210.10993/) (2022)
- [Generalized energy and gradient flow via graph framelets](https://mlsanity.com/paper/2210.04124/) (2022)
- [Robust Graph Representation Learning for Local Corruption Recovery](https://mlsanity.com/paper/2202.04936/) (2022)
- [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)
- [When Graph Neural Networks Meet Dynamic Mode Decomposition](https://mlsanity.com/paper/2410.05593/) (2024)
- [Frameless Graph Knowledge Distillation](https://mlsanity.com/paper/2307.06631/) (2023)
- [Revisiting Generalized p-Laplacian Regularized Framelet GCNs: Convergence, Energy Dynamic and Training with Non-Linear Diffusion](https://mlsanity.com/paper/2305.15639/) (2023)
- [Generalized Laplacian Regularized Framelet Graph Neural Networks](https://mlsanity.com/paper/2210.15092/) (2022)
- [Data-Adaptive Graph Framelets with Generalized Vanishing Moments for Graph Machine Learning](https://mlsanity.com/paper/2309.03537/) (2023)

## Abstract (arXiv)

Graph representation learning has many real-world applications, from super-resolution imaging, 3D computer vision to drug repurposing, protein classification, social networks analysis. An adequate representation of graph data is vital to the learning performance of a statistical or machine learning model for graph-structured data. In this paper, we propose a novel multiscale representation system for graph data, called decimated framelets, which form a localized tight frame on the graph. The decimated framelet system allows storage of the graph data representation on a coarse-grained chain and processes the graph data at multi scales where at each scale, the data is stored at a subgraph. Based on this, we then establish decimated G-framelet transforms for the decomposition and reconstruction of the graph data at multi resolutions via a constructive data-driven filter bank. The graph framelets are built on a chain-based orthonormal basis that supports fast graph Fourier transforms. From this, we give a fast algorithm for the decimated G-framelet transforms, or FGT, that has linear computational complexity O(N) for a graph of size N. The theory of decimated framelets and FGT is verified with numerical examples for random graphs. The effectiveness is demonstrated by real-world applications, including multiresolution analysis for traffic network, and graph neural networks for graph classification tasks.