Research map / Graph learning / GNN architectures
Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training
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.
Proposes SGBGC, a supervised, adaptive graph coarsening method that partitions nodes into label-pure granular-balls used as super nodes to train GNNs faster with near-original accuracy.
Problem
GNN training on large graphs is costly; existing graph coarsening methods are training-dependent or unsupervised and require a predefined coarsening rate.
Approach
Use granular-ball computing on graphs: iteratively split the graph into connected label-pure granular-balls (purity threshold T=1), starting from sqrt(N) label-balanced high-degree centers, and use them as super nodes, so the coarsening rate is determined adaptively rather than fixed.
Key results
- At coarsening ratio 0.1 on Co-CS, SGBGC reaches 92.22% accuracy vs 88.47% for FGC (best baseline at that ratio in Table 1).
- On Cora at ratio 0.5, SGBGC gets 87.85% vs CMGC 88.40%, i.e. comparable but not best in that setting.
- Adaptive granular-ball coarsening (no preset ratio) gives 87.57% on Cora vs 88.38% on the full graph, with ratios 0.36-0.49.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply SGBGC coarsening instead of training on the original graph | GCN node classification · Cora, Citeseer, Pubmed, Co-CS, and Co-Phy (adaptive rates) | accuracy: 88.38 -> 87.57; 76.48 -> 75.38; 86.40 -> 86.29; 93.78 -> 93.28; 96.65 -> 96.39 | Hurt |
| Use SGBGC rather than the strongest baseline at the listed r=0.3 settings | GCN node classification · Cora, Pubmed, Co-CS, and Co-Phy | accuracy: Cora: 85.96$\pm$0.84 -> 86.29$\pm$0.79; Pubmed: 85.80$\pm$0.30 -> 86.28$\pm$0.20; Co-CS: 89.94$\pm$0.04 -> 93.09$\pm$0.1 | Mixed |
| Use SGBGC instead of CMGC at r=0.5 | GCN node classification · Citeseer | accuracy: 77.33$\pm$0.85 -> 75.25$\pm$1.02 | Hurt |
| Use SGBGC rather than the original graph under label noise | GCN node classification · Citeseer (5% noise, r=0.3) | accuracy: 73.21% -> 75.20% | Helped |
| Increase initial centers from √N to 2√N or 4√N (ablation) | SGBGC · Pubmed | coarsening time: 29.7 seconds -> 35.0 seconds; 29.7 seconds -> 78.4 seconds | Hurt |
Surprising findings
- Under 10% and 15% label noise, SGBGC underperforms on Cora at ratio 0.5 relative to GSGC/VNGC in several cells, contrary to the claim of uniformly superior robustness.
Limitations
- Reported accuracy is not best in several settings (e.g., CMGC best on Cora at 0.5 and Citeseer at 0.5), and the method relies on label information so it is supervised only.
- Experiments limited to node classification on five citation/co-author datasets; graph classification and link prediction left to future work.
- Theoretical analysis relies on approximations (e.g., P^T P ≈ I, L_gb ≈ L) that are not rigorously justified.
Experimental setup
Datasets: Cora Citeseer Pubmed Co-CS Co-Phy
Benchmarks: Cora Citeseer Pubmed Co-CS Co-Phy
Metrics: accuracy coarsening time (seconds) memory usage
Baselines: VNGC VEGC JCGC GSGC GCOND FGC CMGC
Builds on: GCN SCAL GCOND CMGC
Closest papers by meaning
- Graph Coarsening with Neural Networks (ICLR 2021 · similarity 0.89)
- Graph Coarsening with Message-Passing Guarantees (NeurIPS 2024 · similarity 0.87)
- GRAIN: Multi-Granular and Implicit Information Aggregation Graph Neural Network for Heterophilous Graphs (AAAI 2025 · similarity 0.86)
- Towards Scalable and Deep Graph Neural Networks via Noise Masking (AAAI 2025 · similarity 0.86)
- Bonsai: Gradient-free Graph Condensation for Node Classification (ICLR 2025 · similarity 0.86)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.86)
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.