GraCo: A Unified Toolkit of Graph Coarsening Algorithms and Metrics
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
| Method | Year | Criterion | Feat. | Impl. | Scale |
|---|---|---|---|---|---|
| Global clustering | |||||
| Random | – | none | GPU | very large | |
| METIS [ 26 ] | 1997 | balanced edge cut | CPU | very large | |
| Graclus [ 12 ] | 2007 | normalized cut | GPU | very large | |
| Leiden [ 35 ] | 2019 | modularity | CPU | very large | |
| UGC [ 27 ] | 2024 | feature-structure similarity | GPU | very large | |
| Cora | PubMed | ogbn-arxiv | ogbn-products | |||||||||
| Method | time | CPU | GPU | time | CPU | GPU | time | CPU | GPU | time | CPU | GPU |
| Random | 0.01 | 0 | – | 0.01 | 11 | – | 0.01 | 0 | – | 0.12 | 0 | – |
| METIS | 0.07 | 0 | – | 0.83 | 16 | – | 4.5 | 163 | – | 84.6 | 0 | – |
| Graclus | 0.04 | 3 | – | 0.21 | 23 | – | 1.5 | 152 | – | 49.7 | 0 | – |
| Leiden ‡ | 2.9 | 32 | – | 34.7 | 64 | – | 2718 | 355 | – | 33523 | 0 | – |
| UGC | 0.25 | 56 | – | 0.54 | 216 | – | 3.4 | 1496 | – | 35.1 | 4628 | – |
| Metric | Source | Used by | Feat. | Struct. | Lap. | Label |
|---|---|---|---|---|---|---|
| Spectral fidelity | ||||||
| rsa | [ 31 ] | [ 23 , 25 , 24 ] | ✓ | ✓ | ||
| mean_REE | [ 31 ] | [ 29 , 27 , 11 ] | ✓ | ✓ | ||
| spectral_distance | [ 38 ] | [ 41 ] | ✓ | ✓ | ||
| Operator reconstruction | ||||||
| reconstruction_error | – | [ 29 , 11 ] | ✓ | ✓ | ||
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
| Cora | PubMed | |||||||||
| Method | RSA | REE | CME | max_acc | RSA | REE | CME | max_acc | ||
| Global clustering | ||||||||||
| Random | 0.71 | 7.14 | 10.03 | 58.7 | 48.4 | 0.71 | 4.43 | 12.59 | 37.2 | 61.8 |
| METIS | 0.72 | 1.95 | 3.20 | 37.9 | 86.0 | 0.79 | 2.49 | 3.66 | 28.7 | 84.3 |
| Graclus | 0.73 | 1.94 | 3.62 | 35.7 | 87.6 | 0.71 | 2.99 | 3.48 | 25.8 | 85.9 |
| Leiden | 0.70 | 1.58 | 3.40 | 29.2 | 89.3 | 0.70 | 1.59 | 4.54 | 22.3 | 87.7 |
| Method | Default in the toolkit | Alternatives from the original paper | Alternatives we add |
|---|---|---|---|
| UGC | features and , mixed by | features only | — |
| GW GPC, GW KGPC | adjacency | combinatorial , signless | self-loop normalized , |
| Kcenter | features after two hops, † | raw features | any number of hops |
| Herding | features after two hops, † | raw features | any number of hops |
| OTCoarsening | and features | — | — |
| Local Variation | self-loop normalized † | combinatorial | normalized |
| Method | On by default | Other options |
|---|---|---|
| Random | – | equal-size variant: a shuffled index list split into balanced chunks (the default draws cluster identifiers i.i.d.). |
| Graclus | seeding of the global torch random stream, from which the torch-cluster kernel samples its visit order; the kernel takes no seed argument. | – |
| Leiden | log-scale binary search on the resolution to reach a requested ratio † , with a tolerance n_clusters_tol on the community count. | – |
| UGC | projections of and of the sparse computed separately, so the augmented matrix of the released code is never formed densely. | – |
| GW GPC, KGPC | – | two normalizations (paper: uniform); both coarse operators, of the paper and , returned in info . The partition is the same for both. |
| Kcenter, Herding | recast as coarseners: pivots on the propagated features plus nearest-pivot assignment (the originals are coreset selectors) † ; the assignment is computed by blocks, so the distance matrix is never formed. | – |
| Option | Paper | Released code | Default |
|---|---|---|---|
| score_square | (Eq. 2) | code | |
| cut | , the top- values (Eq. 3) | paper | |
| zero_row_filter | no filter (Eq. 4, Eq. 9) | get_nonzero_rows | paper |
| argmax alone | attach | isolate | isolate_recursive | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| asked | purity | largest | purity | largest | uncovered | levels | purity | ||||
| 0.5 | 1243 | 987 | 0.795 | 418 | 0.901 | 59 | 417 | 1404 | 1 | 1404 | 0.930 |
| 0.7 | 746 | 656 | 0.661 | 1025 | 0.862 | 44 | 1024 | 1680 | 2 | 830 | 0.883 |
| 0.9 | 249 | 231 | 0.464 | 1836 | 0.794 | 178 | 1835 | 2066 | 4 | 252 | 0.780 |
| pair | lift | |||
|---|---|---|---|---|
| dickens | ||||
| binary | ||||
| normalized |
| Cora | PubMed | ||||||||||||
| Cand. | pair | CME | RSA | acc | CME | RSA | acc | CME | RSA | acc | CME | RSA | acc |
| Exact cost (ConvMatch) | |||||||||||||
| kNN | dickens | 36.2 | 2.14 | 90.5 | 53.0 | 2.61 | 86.4 | 28.2 | 4.83 | 88.5 | 36.2 | 4.01 | 84.0 |
| binary | 36.0 | 2.16 | 90.4 | 52.8 | 2.82 | 85.7 | 27.5 | 2.69 | 88.6 | 35.1 | 3.48 | 84.2 | |
| normalized | 35.5 | 2.16 | 90.2 | 51.6 | 2.78 | 86.1 | 27.4 | 2.69 | 88.5 | 34.9 | 2.98 | 84.3 | |
| region | Eq. 1 ( nope ) | repository ( nope_repo ) |
|---|---|---|
| (only ) | ||
| (only ) | ||
| (both) |
| asked | , size (repository) | , count (default) | |
|---|---|---|---|
| 0.5 | 1243 | 1281 | 1243 |
| 0.7 | 746 | 1057 | 746 |
| 0.9 | 249 | 407 | 249 |
| Option | [ 41 ] | [ 36 ] | Default |
|---|---|---|---|
| init | BFS from the highest-degree centers (Eq. 4) | METIS asked for parts | BFS |
| accept | (Eq. 8) | sum | |
| use_transitivity | (Eq. 6) | alone | true |
| Dataset | Type | Nodes | Feat. | Cls. | Symmetrized | Before LCC |
|---|---|---|---|---|---|---|
| Cora | homophilic | 2,485 | 1,433 | 7 | 2,708 | |
| CiteSeer | homophilic | 2,120 | 3,703 | 6 | 3,327 | |
| PubMed | homophilic | 19,717 | 500 | 3 | – | |
| chameleon | heterophilic | 2,277 | 2,325 | 5 | ✓ | – |
| squirrel | heterophilic | 5,201 | 2,089 | 5 | ✓ | – |
| Amazon-ratings | heterophilic | 24,492 | 300 | 5 | – |
| Method | Default | Tuned | Key hyperparameter |
|---|---|---|---|
| UGC | 0.50 | 0.50 | none (insensitive) |
| STPGC | 0.76 | 0.85 | raised from to of |
| FGC | 0.50 | 0.86 | learning rate ; , lowered to and , raised to ; iterations |
| IPE | 0.49 | 0.84 | Grassmann rank , learning rate , iterations |
| Method | Configs | Grid |
|---|---|---|
| UGC | 12 | adjacency in the hash: yes, no; projectors ; distribution: uniform, normal |
| STPGC | 24 | , |
| FGC | 1152 | solver: metrics, sparsity; learning rate (metrics only); , , ; iterations |
| IPE | 432 | variant: SINGC, INGC; learning rate ; , ; Grassmann rank ; iterations for SINGC, outer steps for INGC |
| Method | vor | conn | vor | conn | ||
|---|---|---|---|---|---|---|
| Random | 147 | 0.05 | 0.11 | 50 | 0.03 | 0.00 |
| METIS | 150 | 0.46 | 0.72 | 50 | 0.65 | 0.56 |
| Graclus | 145 | 0.72 | 1.00 | 45 | 0.83 | 1.00 |
| Leiden | 150 | 0.92 | 1.00 | 49 | 0.96 | 1.00 |
| UGC | 156 | 0.09 | 0.24 | 49 | 0.07 | 0.14 |
Graph Coarsening
Graph coarsening reduces a large graph to a smaller one while aiming to preserve structure and information needed for analysis or learning.
See all 23 papers