# Generalizing Downsampling from Regular Data to Graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 88 references that are in the map.
- First posted on arXiv 6 Aug 2022.

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [Towards Sparse Hierarchical Graph Classifiers](https://mlsanity.com/paper/1811.01287/) (2018)
- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [A Clockwork RNN](https://mlsanity.com/paper/1402.3511/) (2014)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Memory-Based Graph Networks](https://mlsanity.com/paper/2002.09518/) (2020)
- [A Theoretical Comparison of Graph Neural Network Extensions](https://mlsanity.com/paper/2201.12884/) (2022)
- [Topology-Aware Graph Pooling Networks](https://mlsanity.com/paper/2010.09834/) (2020)
- [Path Integral Based Convolution and Pooling for Graph Neural Networks](https://mlsanity.com/paper/2006.16811/) (2020)
- [Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling](https://mlsanity.com/paper/1910.11436/) (2019)
- [iPool -- Information-based Pooling in Hierarchical Graph Neural Networks](https://mlsanity.com/paper/1907.00832/) (2019)
- [Structure-Feature based Graph Self-adaptive Pooling](https://mlsanity.com/paper/2002.00848/) (2020)
- [A Multiscale Pyramid Transform for Graph Signals](https://mlsanity.com/paper/1308.4942/) (2013)
- [A Non-Negative Factorization approach to node pooling in Graph Convolutional Neural Networks](https://mlsanity.com/paper/1909.03287/) (2019)
- [Clique pooling for graph classification](https://mlsanity.com/paper/1904.00374/) (2019)

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

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Graph-based Time Series Clustering for End-to-End Hierarchical Forecasting](https://mlsanity.com/paper/2305.19183/) (2023)
- [Graph-based Forecasting with Missing Data through Spatiotemporal Downsampling](https://mlsanity.com/paper/2402.10634/) (2024)
- [A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizability](https://mlsanity.com/paper/2406.09031/) (2024)
- [MDL-Pool: Adaptive Multilevel Graph Pooling Based on Minimum Description Length](https://mlsanity.com/paper/2409.10263/) (2024)
- [The Role of Node Features in Graph Pooling](https://mlsanity.com/paper/2605.06250/) (2026)

## Abstract (arXiv)

Downsampling produces coarsened, multi-resolution representations of data and it is used, for example, to produce lossy compression and visualization of large images, reduce computational costs, and boost deep neural representation learning. Unfortunately, due to their lack of a regular structure, there is still no consensus on how downsampling should apply to graphs and linked data. Indeed reductions in graph data are still needed for the goals described above, but reduction mechanisms do not have the same focus on preserving topological structures and properties, while allowing for resolution-tuning, as is the case in regular data downsampling. In this paper, we take a step in this direction, introducing a unifying interpretation of downsampling in regular and graph data. In particular, we define a graph coarsening mechanism which is a graph-structured counterpart of controllable equispaced coarsening mechanisms in regular data. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs. We leverage these concepts to define a graph pooling mechanism that we empirically assess in graph classification tasks, providing a greedy algorithm that allows efficient parallel implementation on GPUs, and showing that it compares favorably against pooling methods in literature.