# Graph Coarsening with Neural Networks

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 75 references that are in the map.
- First posted on arXiv 2 Feb 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [MolGAN: An implicit generative model for small molecular graphs](https://mlsanity.com/paper/1805.11973/) (2018)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Towards Sparse Hierarchical Graph Classifiers](https://mlsanity.com/paper/1811.01287/) (2018)
- [Constrained Generation of Semantically Valid Graphs via Regularizing Variational Autoencoders](https://mlsanity.com/paper/1809.02630/) (2018)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Structured Graph Learning Via Laplacian Spectral Constraints](https://mlsanity.com/paper/1909.11594/) (2019)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [COPT: Coordinated Optimal Transport for Graph Sketching](https://mlsanity.com/paper/2003.03892/) (2020)
- [A Multiscale Pyramid Transform for Graph Signals](https://mlsanity.com/paper/1308.4942/) (2013)

## Built on by (most cited first, 30 of 55)

- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs](https://mlsanity.com/paper/2212.09034/) (2022)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [EIGNN: Efficient Infinite-Depth Graph Neural Networks](https://mlsanity.com/paper/2202.10720/) (2022)
- [MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization](https://mlsanity.com/paper/2210.00102/) (2022)
- [DropMessage: Unifying Random Dropping for Graph Neural Networks](https://mlsanity.com/paper/2204.10037/) (2022)
- [MAgNET: A Graph U-Net Architecture for Mesh-Based Simulations](https://mlsanity.com/paper/2211.00713/) (2022)
- [Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition](https://mlsanity.com/paper/2405.13707/) (2024)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Generative Coarse-Graining of Molecular Conformations](https://mlsanity.com/paper/2201.12176/) (2022)
- [Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks](https://mlsanity.com/paper/2207.08629/) (2022)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [Graph Data Condensation via Self-expressive Graph Structure Reconstruction](https://mlsanity.com/paper/2403.07294/) (2024)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Towards Data-centric Graph Machine Learning: Review and Outlook](https://mlsanity.com/paper/2309.10979/) (2023)
- [Mirage: Model-Agnostic Graph Distillation for Graph Classification](https://mlsanity.com/paper/2310.09486/) (2023)
- [Principle of Relevant Information for Graph Sparsification](https://mlsanity.com/paper/2206.00118/) (2022)
- [A Unified Framework for Optimization-Based Graph Coarsening](https://mlsanity.com/paper/2210.00437/) (2022)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [Can Modifying Data Address Graph Domain Adaptation?](https://mlsanity.com/paper/2407.19311/) (2024)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [Representing Molecules as Random Walks Over Interpretable Grammars](https://mlsanity.com/paper/2403.08147/) (2024)
- [Calibrated Dataset Condensation for Faster Hyperparameter Search](https://mlsanity.com/paper/2405.17535/) (2024)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Improving Heterogeneous Graph Learning with Weighted Mixed-Curvature Product Manifold](https://mlsanity.com/paper/2307.04514/) (2023)

## Abstract (arXiv)

As large-scale graphs become increasingly more prevalent, it poses significant computational challenges to process, extract and analyze large graph data. Graph coarsening is one popular technique to reduce the size of a graph while maintaining essential properties. Despite rich graph coarsening literature, there is only limited exploration of data-driven methods in the field. In this work, we leverage the recent progress of deep learning on graphs for graph coarsening. We first propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph and associated projection/lift operators. Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way. Through extensive experiments on both synthetic and real networks, we demonstrate that our method significantly improves common graph coarsening methods under various metrics, reduction ratios, graph sizes, and graph types. It generalizes to graphs of larger size (25× of training graphs), is adaptive to different losses (differentiable and non-differentiable), and scales to much larger graphs than previous work.