cs.LGOct 31, 2026

GraCo: A Unified Toolkit of Graph Coarsening Algorithms and Metrics

Authors: Antonin Joly

Organizations: CNRS, IRISA, Rennes, France

Abstract

Graph coarsening aims to reduce a graph to a smaller one that preserves chosen properties of the original. It is increasingly used to scale graph learning to large graphs, as a non-differentiable step applied once before training. Many coarsening methods have been proposed in recent years, each with its own implementation, notation and evaluation. In this work, we introduce GraCo, a unified toolkit of graph coarsening methods. It relies on a single definition: a coarsening is fixed by a partition of the nodes and by the Laplacian the coarsened graph is consistent with. The coarsened graph, and the reduction and lifting matrices that map signals from the original graph to the coarsened one and back, follow from these two choices. We implement 17 methods from the literature and a random baseline, grouped into five families, with the same notation, inputs and outputs. We also build a collection of metrics from different papers, applicable to any coarsening. We check the implementations on a synthetic stochastic block model, then we report the runtime and peak memory of each method on Cora, PubMed, ogbn-arxiv and ogbn-products. GraCo is open-source and available at https://github.com/Antonin-J/graco.

Figures & tables

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle

    May 13, 2026Xu Bai, Bin Lu, Kun Zhang +4Graph Coarsening

  2. CoRe-GNN: Multilevel Message passing on Coarsened graphs

    Aug 3, 2026Antonin Joly, Nicolas Keriven, Aline RoumyGraph Neural NetworksGraph Coarsening

  3. Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification

    Mar 31, 2026Guan Wang, Shuyin Xia, Lei Qian +4Graph CoarseningGraph Neural Networks