Research map / Graph learning / Graph algorithms and clustering
Taxonomy of reduction matrices for Graph Coarsening
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes the reduction matrix in spectral graph coarsening beyond pseudo-inverse of the lifting matrix, characterizes admissible sets, and shows RSA can be reduced by optimizing the reduction matrix alone for a fixed lifting matrix.
Problem
Graph coarsening is defined by a lifting and a reduction matrix, and the standard practice ties the reduction matrix to the pseudo-inverse of the lifting matrix; this leaves the RSA (restricted spectral approximation) loss unexplored over the freedom in the reduction matrix.
Approach
Only the lifting matrix must be constrained (well-partitioned and binary) to define a consistent coarsened Laplacian; the reduction matrix can be any admissible matrix (projection, reflexive generalized inverse, or same-support inverse), so for a fixed lifting matrix it can be optimized to lower the RSA constant.
Key results
- On Cora, optimized reduction matrices (P*_g, P*_g,l1, P*_Q^T) achieve RSA constants lower than Moore-Penrose and Loukas reductions, with the gap growing at higher coarsening ratios.
- With SGC on Cora at r=0.7, P*_g,l1 reaches 78.3% vs 77.7% for P_MP and 76.8% for Loukas; the gains are marginal and less visible on Citeseer.
- The optimized sparse reduction matrices retain near-identical RSA while reducing non-zero coefficients by about 99.8% relative to the dense P*_g.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the Moore–Penrose reduction with RSA-optimized P_g* | SGC on Cora · Cora, r=0.3 | accuracy: 80.5 $\pm$ 0.0 -> 80.7 $\pm$ 0.0 | Helped |
| Replace the Moore–Penrose reduction with RSA-optimized P_g* | SGC on Cora · Cora, r=0.5 | accuracy: 80.1 $\pm$ 0.0 -> 80.0 $\pm$ 0.0 | Hurt |
| Use RSA optimization with an l1 sparsity penalty instead of P_MP | SGC on Cora · Cora, r=0.7 | accuracy: 77.7 $\pm$ 0.0 -> 78.3 $\pm$ 0.0 | Helped |
| Use RSA-optimized P_g* instead of P_MP | GCN on Cora · Cora, r=0.5 | accuracy: 80.7 $\pm$ 0.9 -> 81.3 $\pm$ 0.6 | Helped |
| Use dense Rao-inspired reduction instead of P_MP | GCN on Cora · Cora, r=0.7 | accuracy: 78.6 $\pm$ 0.9 -> 55.11 $\pm$ 2.4 | Hurt |
| Use RSA-optimized P_g* instead of P_MP | GCN on Citeseer · Citeseer, r=0.7 | accuracy: 71.0 $\pm$ 1.0 -> 69.6 $\pm$ 1.0 | Hurt |
| Optimize the reduction matrix for RSA rather than use the classical P_MP and P_Loukas choices | Graph coarsening reduction matrices · Cora and Citeseer, coarsening ratios 0.05 to 0.85 | RSA constant | Helped |
| Add sparsity constraints using an l1 penalty or Q transpose support | RSA-optimized reduction matrices · Low coarsening ratios | RSA constant | No clear effect |
| Use the dense Rao-inspired reduction despite its stronger RSA | GNN propagation on coarsened graphs · Cora and Citeseer node classification | accuracy | Hurt |
| Apply the RSA-optimized reductions instead of classical reductions | GNNs trained on coarsened graphs · Cora and Citeseer node classification | accuracy | Mixed |
| Initialize P_g,l1* with P_MP or P_Loukas instead of dense P_rao (ablation) | P_g,l1* optimization on Cora, r=0.5 · Cora, r=0.5 | RSA constant | Hurt |
| Decrease the number of nodes contracted at each coarsening step (ablation) | Adapted Loukas algorithm · Graph coarsening | RSA constant | Helped |
Surprising findings
- The Rao-Mitra inspired reduction gives the best RSA but performs poorly for GNN node classification (e.g., GCN accuracy drops to 55.1% on Cora at r=0.7), attributed to its density.
- Lower RSA translates only marginally into better GNN accuracy, questioning the link between RSA and GNN performance.
Limitations
- Experiments restricted to medium-scale graphs (Cora, Citeseer PCC) because the RSA requires the square root of the Laplacian, which is dense and infeasible for large graphs like Reddit.
- GNN gains from RSA optimization are marginal and mostly visible only on homophilous graphs.
- Analysis restricted to RSA as the scoring function; heterophily or feature-aware criteria not explored.
Experimental setup
Datasets: Cora Citeseer
Benchmarks: Cora Citeseer
Metrics: RSA constant node classification accuracy
Baselines: Moore-Penrose reduction Loukas reduction Rao-Mitra inspired reduction
Builds on: Loukas coarsening Rao and Mitra generalized inverses Kipf GCN SGC
Closest papers by meaning
- Spectrally Approximating Large Graphs with Smaller Graphs (ICML 2018 · similarity 0.90)
- Graph Coarsening with Message-Passing Guarantees (NeurIPS 2024 · similarity 0.89)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.86)
- Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks (NeurIPS 2026 · similarity 0.86)
- UGC: Universal Graph Coarsening (NeurIPS 2024 · similarity 0.86)
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.