# A Unified Framework for Optimization-Based Graph Coarsening

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 54 references that are in the map.
- First posted on arXiv 2 Oct 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Condensing Graphs via One-Step Gradient Matching](https://mlsanity.com/paper/2206.07746/) (2022)
- [Spectrally approximating large graphs with smaller graphs](https://mlsanity.com/paper/1802.07510/) (2018)
- [Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications](https://mlsanity.com/paper/1803.01257/) (2018)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening](https://mlsanity.com/paper/1902.09702/) (2019)
- [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021)
- [Structured Graph Learning Via Laplacian Spectral Constraints](https://mlsanity.com/paper/1909.11594/) (2019)
- [A Multiscale Pyramid Transform for Graph Signals](https://mlsanity.com/paper/1308.4942/) (2013)
- [Unsupervised Learning of Graph Hierarchical Abstractions with Differentiable Coarsening and Optimal Transport](https://mlsanity.com/paper/1912.11176/) (2019)
- [Stochastic Multidimensional Scaling](https://mlsanity.com/paper/1612.07089/) (2016)
- [Robust Graph Neural Networks using Weighted Graph Laplacian](https://mlsanity.com/paper/2208.01853/) (2022)
- [Deep Approximately Orthogonal Nonnegative Matrix Factorization for Clustering](https://mlsanity.com/paper/1711.07437/) (2017)

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

- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [A Topology-aware Graph Coarsening Framework for Continual Graph Learning](https://mlsanity.com/paper/2401.03077/) (2024)
- [Efficient Large-Scale Urban Parking Prediction: Graph Coarsening Based on Real-Time Parking Service Capability](https://mlsanity.com/paper/2410.04022/) (2024)
- [Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening](https://mlsanity.com/paper/2505.14033/) (2025)
- [AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening](https://mlsanity.com/paper/2505.15842/) (2025)
- [Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle](https://mlsanity.com/paper/2605.13021/) (2026)
- [Modularity aided consistent attributed graph clustering via coarsening](https://mlsanity.com/paper/2407.07128/) (2024)
- [GraphFLEx: Structure Learning Framework for Large Expanding Graphs](https://mlsanity.com/paper/2505.12323/) (2025)
- [Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement](https://mlsanity.com/paper/2607.21885/) (2026)

## Abstract (arXiv)

Graph coarsening is a widely used dimensionality reduction technique for approaching large-scale graph machine learning problems. Given a large graph, graph coarsening aims to learn a smaller-tractable graph while preserving the properties of the originally given graph. Graph data consist of node features and graph matrix (e.g., adjacency and Laplacian). The existing graph coarsening methods ignore the node features and rely solely on a graph matrix to simplify graphs. In this paper, we introduce a novel optimization-based framework for graph dimensionality reduction. The proposed framework lies in the unification of graph learning and dimensionality reduction. It takes both the graph matrix and the node features as the input and learns the coarsen graph matrix and the coarsen feature matrix jointly while ensuring desired properties. The proposed optimization formulation is a multi-block non-convex optimization problem, which is solved efficiently by leveraging block majorization-minimization, log determinant, Dirichlet energy, and regularization frameworks. The proposed algorithms are provably convergent and practically amenable to numerous tasks. It is also established that the learned coarsened graph is ε∈(0,1) similar to the original graph. Extensive experiments elucidate the efficacy of the proposed framework for real-world applications.