Pith. sign in

REVIEW 12 cited by

A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2402.03358 v4 pith:DDLYQX5J submitted 2024-01-29 cs.SI cs.AIcs.DScs.LG

Mohammad Hashemi , Shengbo Gong , Juntong Ni , Wenqi Fan , B. Aditya Prakash , Wei Jin This is my paper · ORCID
classification cs.SIcs.AIcs.DScs.LG
keywords graphreductionsurveycomprehensivemethodschallengescoarseningcondensation
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

Many real-world datasets can be naturally represented as graphs, spanning a wide range of domains. However, the increasing complexity and size of graph datasets present significant challenges for analysis and computation. In response, graph reduction, or graph summarization, has gained prominence for simplifying large graphs while preserving essential properties. In this survey, we aim to provide a comprehensive understanding of graph reduction methods, including graph sparsification, graph coarsening, and graph condensation. Specifically, we establish a unified definition for these methods and introduce a hierarchical taxonomy to categorize the challenges they address. Our survey then systematically reviews the technical details of these methods and emphasizes their practical applications across diverse scenarios. Furthermore, we outline critical research directions to ensure the continued effectiveness of graph reduction techniques, as well as provide a comprehensive paper list at \url{https://github.com/Emory-Melody/awesome-graph-reduction}. We hope this survey will bridge literature gaps and propel the advancement of this promising field.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 12 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing

    cs.AI 2025-06 conditional novelty 6.0 of 10

    GBGC uses granular-ball computing to coarsen graphs adaptively, achieving faster runtime and competitive classification accuracy on benchmark datasets.

  2. Simple yet Effective Graph Distillation via Clustering

    cs.LG 2025-05 conditional novelty 6.0 of 10

    ClustGDD distills large graphs by clustering node embeddings and refining synthetic attributes, achieving state-of-the-art node classification accuracy at orders of magnitude lower time cost.

  3. Random Walk Guided Hyperbolic Graph Distillation

    cs.LG 2025-01 conditional novelty 6.0 of 10

    HyDRO distills graphs in hyperbolic space with random-walk spectral gap matching, improving link prediction and continual graph learning.

  4. Training-free Heterogeneous Graph Condensation via Data Selection

    cs.LG 2024-12 conditional novelty 6.0 of 10

    FreeHGC performs training-free heterogeneous graph condensation through structural data selection and synthesis, matching or beating training-based condensation on seven datasets.

  5. Quantum Compilation Toolkit for Rydberg Atom Arrays with Implications for Problem Hardness and Quantum Speedups

    quant-ph 2024-12 conditional novelty 6.0 of 10

    A graph-reduction, compatibility-checking, and embedding toolkit maps generic maximum independent set problems onto Rydberg atom arrays, with large empirical reductions and a hardware demo on QuEra Aquila.

  6. GCAL: Adapting Graph Models to Evolving Domain Shifts

    cs.LG 2025-05 conditional novelty 5.0 of 10

    GCAL combines information-maximization adaptation with variational memory graph generation to prevent catastrophic forgetting in unsupervised continual graph domain adaptation.

  7. GraphFLEx: Structure Learning Framework for Large Expanding Graphs

    cs.LG 2025-05 reject novelty 5.0 of 10

    GraphFLEx uses clustering, hashing-based coarsening, and local graph learning to incrementally infer structure in large expanding graphs, claiming faster runtime and near-original accuracy.

  8. Inference-friendly Graph Compression for Graph Neural Networks

    cs.LG 2025-04 reject novelty 5.0 of 10

    A graph compression scheme that merges inference-equivalent nodes so GNN inference can run on a smaller graph with no or little decompression, claiming 55-85% inference cost reduction with small accuracy loss.

  9. SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks

    cs.LG 2025-02 conditional novelty 5.0 of 10

    A supervised edge-sampling sparsifier that keeps only 20% of edges can match or beat the full graph for GNN node classification, with especially large gains on heterophilic graphs.

  10. Heterogeneous Graph Condensation via Role-Aware Clustering

    cs.LG 2026-07 conditional novelty 4.5 of 10

    Role-aware clustering (class-partitioned targets, type-wise non-targets) plus cluster-level reconstruction yields compact heterogeneous graphs that train HGNNs near full-graph accuracy at far lower condensation cost.

  11. ScaleNet: Scale Invariance Learning in Directed Graphs

    cs.LG 2024-11 reject novelty 4.0 of 10

    The paper reports state-of-the-art node classification on five of six tested datasets using multi-scale products of a directed adjacency matrix, but the claimed scale invariance is not rigorously demonstrated.

  12. Explainable Malware Detection through Integrated Graph Reduction and Learning Techniques

    cs.CR 2024-12 conditional novelty 2.0 of 10

    Leaf Prune, a simple removal of nodes with degree ≤ 1, reduces CFG/FCG size drastically in GNN malware detection with negligible accuracy change.

Pith tools