# Data-Adaptive Graph Framelets with Generalized Vanishing Moments for Graph Machine Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 77 references that are in the map.
- First posted on arXiv 7 Sep 2023.

## Builds on (most cited first, 29 of 29)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation](https://mlsanity.com/paper/1603.03236/) (2016)
- [GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily](https://mlsanity.com/paper/2110.15777/) (2021)
- [Simplifying approach to Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2111.06748/) (2021)
- [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)
- [Decimated Framelet System on Graphs and Fast G-Framelet Transforms](https://mlsanity.com/paper/2012.06922/) (2020)
- [Subgraph-based filterbanks for graph signals](https://mlsanity.com/paper/1509.05642/) (2015)
- [Convolutional Neural Networks for Spherical Signal Processing via Spherical Haar Tight Framelets](https://mlsanity.com/paper/2201.07890/) (2022)
- [Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators](https://mlsanity.com/paper/2203.02858/) (2022)
- [Two-Channel Critically-Sampled Graph Filter Banks With Spectral Domain Sampling](https://mlsanity.com/paper/1804.08811/) (2018)
- [CDOpt: A Python Package for a Class of Riemannian Optimization](https://mlsanity.com/paper/2212.02698/) (2022)
- [Spline-Like Wavelet Filterbanks with Perfect Reconstruction on Arbitrary Graphs](https://mlsanity.com/paper/2209.06385/) (2022)
- [Perfect Reconstruction Two-Channel Filter Banks on Arbitrary Graphs](https://mlsanity.com/paper/2210.02024/) (2022)

## Abstract (arXiv)

In this paper, we propose a general framework for constructing tight framelet systems on graphs with localized supports based on partition trees. Our construction of framelets provides a simple and efficient way to obtain the orthogonality with k arbitrary orthonormal vectors. When the k vectors contain most of the energy of a family of graph signals, the orthogonality of the framelets intuitively possesses ``generalized (k-)vanishing'' moments, and thus, the coefficients are sparse. Moreover, our construction provides not only framelets that are overall sparse vectors but also fast and schematically concise transforms. In a data-adaptive setting, the graph framelet systems can be learned by conducting optimizations on Stiefel manifolds to provide the utmost sparsity for a given family of graph signals. Furthermore, we further exploit the generality of our proposed graph framelet systems for heterophilous graph learning, where graphs are characterized by connecting nodes mainly from different classes. The usual assumption that connected nodes are similar and belong to the same class for homophilious graphs is contradictory for heterophilous graphs. Thus, we are motivated to bypass simple assumptions on heterophilous graphs and focus on generating rich node features induced by the graph structure, so as to improve the graph learning ability of certain neural networks in node classification. We derive a specific system of graph framelets and propose a heuristic method to select framelets as features for neural network input. Several experiments demonstrate the effectiveness and superiority of our approach for non-linear approximation, denoising, and node classification.