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

1 Introduction

• Graph reduction seeks a smaller dataset that preserves key information, addressing scalability and efficiency challenges posed by growing graph datasets.The survey also notes possible benefits for downstream-model compatibility, privacy, and visualization.Source: §1 · pp. 1–2
• Sparsification selects existing elements, coarsening aggregates nodes into super-nodes, and condensation synthesizes a smaller graph to preserve GNN performance.These strategies have often been studied in isolation, leaving their connections and distinctions less clear.Source: §1 · p. 2
• The survey reviews graph sparsification, coarsening, and condensation, and develops a unified perspective for differentiating their characteristics and representative algorithms.It also discusses practical applications of graph reduction methods.Source: §1 · p. 2
• The survey identifies key challenges and promising future research directions for graph reduction techniques.These directions are intended to guide the field’s continued advancement.Source: §1 · p. 2
• The survey presents graph condensation alongside conventional graph reduction techniques and explores synergies between graph reduction and GNNs, an aspect rarely covered in existing surveys.It also describes its scope as wider than the latest survey on graph learning acceleration.Source: §1 · p. 2

A Unified Framework of Graph Reduction

• Graph reduction produces a smaller graph by reducing node or edge count while preserving desired information, understood as minimizing a loss that measures differences in that information.The definition excludes graph representation learning and epoch-varying data augmentation; the survey primarily focuses on reducing nodes or edges rather than the number of graphs.Source: A Unified Framework of Graph Reduction · pp. 2–3
• Sparsification selects existing graph elements, coarsening maps nodes to super-nodes and aggregates the graph, while condensation learns a small synthetic labeled graph for comparable GNN performance.Sparsification and coarsening generally target graph properties; condensation targets downstream GNN performance and relies on labels.Source: A Unified Framework of Graph Reduction · p. 3
• Sparsification and coarsening retain or aggregate original elements, whereas condensation synthesizes graph elements; the first two are more interpretable because reduced elements relate back to the original graph.The three strategies share the goal of preserving key information in a smaller graph for downstream processes.Source: A Unified Framework of Graph Reduction · p. 3
• Figure 3 presents a taxonomy of methods across the three categories, and Table 2 qualitatively compares the strategies.The survey says it elaborates on the taxonomy in the following section.Source: A Unified Framework of Graph Reduction · p. 3

3 Methodology

• Representative algorithms for the three graph-reduction strategies are categorized by learning objectives, with popular approaches summarized in Table 3.The section covers sparsification, coarsening, and condensation.Source: §3 · p. 3

Preserving Graph Properties

• Traditional sparsification preserves pairwise distances, cuts, or spectrum; distance-preserving reductions are spanners, while cut- or spectrum-preserving reductions are sparsifiers.An output with loss at most ϵ is called an ϵ-spanner or ϵ-sparsifier.Source: Preserving Graph Properties · p. 3
• SPANNER adds original edges only when their weight is below current reduced-graph distance, guaranteeing every weighted graph a 2t-spanner with O(N^(1+1/t)) edges [1993]; Baswana and Sen tighten the upper bound to 2t−1 [Baswana and Sen, 2003].Source: Preserving Graph Properties · p. 4
• Twice Ramanujan Sparsifier guarantees a weighted (1 + ϵ)-sparsifier with at most (N−1)/2 edges, using effective-resistance sampling and reweighting.Other approaches address retaining original weights, directed graphs, spectral approximation with a low-stretch tree, and community detection [Anderson et al., 2014; Chung, 2005; Feng, 2016; Wu and Chen, 2020].Source: Preserving Graph Properties · p. 4

Preserving Performance

• For GNN performance, model-free methods score graph structure, including k-core density and walk index, but these metrics may not fit downstream models or tasks [Salha et al., 2019; Brandeis et al., 2020; Razin et al., 2023].The survey also identifies scores such as effective resistance, PageRank, KCenter, and trained-GNN explanations.Source: Preserving Performance · p. 4
• Model-based approaches use trained GNN embeddings, explanations, or learnable graph structure to score or prune nodes and edges [Jin et al., 2022b; Li et al., 2023a; Zheng et al., 2020; Chen et al., 2021; Liu et al., 2023a].GST combines semantic and topological information after UGS is reported to fail to preserve topology; TEDDY instead uses one-shot degree-based sparsification followed by distillation and projected gradient descent [Zhang et al., 2024a; Seo et al., 2024].Source: Preserving Performance · p. 4
• The transferability and universality of sparse graphs produced as byproducts of graph structure learning remain inadequately explored for other graph algorithms.OTC provides a holistic alternative, selecting nodes by minimizing optimal transport distance to a target distribution and retaining their incident edges.Source: Preserving Performance · p. 5

3.2 Graph Coarsening

• Coarsening groups and aggregates nodes, potentially producing hierarchical views; methods are divided by whether they use a reconstruction objective.The section motivates coarsening as a response to information loss from selecting nodes or edges.Source: §3.2 · p. 5

Reconstruction-Based Methods

• Reconstruction-based methods lift supernodes back to original-node scale and optimize a mapping matrix to reduce adjacency- or Laplacian-based reconstruction differences.These methods are categorized as spatial or spectral according to whether they use the adjacency or Laplacian matrix.Source: Reconstruction-Based Methods · p. 5
• Spatial methods minimize reconstruction error using a lifted adjacency matrix; GraSS merges sampled node pairs with the smallest error increase, while later work connects the objective to geometric clustering or weighted sampling [LeFevre and Terzi, 2010; Riondato et al., 2017; Beg et al., 2018].The lifted adjacency entries encode within-supernode and between-supernode edge densities.Source: Reconstruction-Based Methods · p. 5
• Spectral methods compare Laplacian eigenvalues or eigenvectors, including relative eigenvalue error on the top-k eigenvalues; pairwise contraction, edge-weight optimization, and correction sets are also discussed [Loukas, 2019; Loukas and Vandergheynst, 2018; Zhao et al., 2018; Navlakha et al., 2008; Khan et al., 2015].Other approaches optimize structure and attributes, preserve the Laplacian pseudoinverse probabilistically, or learn coarse-graph edge weights with a GNN [Kumar et al., 2023; Bravo Hermsdorff and Gunderson, 2019; Cai et al., 2021].Source: Reconstruction-Based Methods · pp. 5–6

Reconstruction-Free Methods

• Reconstruction-free methods include motif-based network reduction, attribute- and relation-based summary graphs, MDL summaries, continuous-attribute cutoffs, diffusion-preserving representations, and task-based learnable node merging.k-snap allows users to control summary resolution, while Netgist uses reinforcement learning for node-merging policies.Source: Reconstruction-Free Methods · p. 6

Remarks on Graph Coarsening

• GNN coarsening covers pooling for graph classification and methods for node classification, including label aggregation, relation summarization, convolution-aware merging, and matching embeddings across coarsening ratios [Such et al., 2017; Bacciu et al., 2023; Huang et al., 2021; Generale et al., 2022; Dickens et al., 2023; Buffelli et al., 2022].KPlexPool is a non-parametric pooling method designed to generalize across graph natures and connectivity patterns [Bacciu et al., 2021].Source: Remarks on Graph Coarsening · p. 6
• For large graphs, VNG matches forward propagation using weighted k-means, while Graph Skeleton reduces background nodes around target nodes to preserve target-node classification performance.Other coarsening connections include Kron reduction for preserving pairwise effective resistance and graph partitioning or clustering through contraction and aggregation.Source: Remarks on Graph Coarsening · p. 6

3.3 Graph Condensation

• Graph condensation constructs a much smaller synthetic graph from scratch, aiming for comparable model performance to training on the original graph.It is motivated by the task-information and representative-node-or-edge limitations of sparsification and coarsening.Source: §3.3 · p. 7

Matching-Based Methods

• GCond matches training gradients across real and synthetic graphs, while DosCond uses a one-step scheme and bounds the resulting loss gap by its gradient-matching loss.GCond parameterizes the synthetic adjacency to preserve attribute–structure correlations; DosCond models edges probabilistically and also addresses graph classification.Source: Matching-Based Methods · p. 8
• Performance gains in graph condensation can correlate with worse demographic parity; FGD adds a coherence metric to the GM loss, while GCARe regularizes subgroup distillation.FedGKD applies gradient-matching condensation in federated graph learning.Source: Matching-Based Methods · pp. 8–9
• Distribution Matching directly aligns real and synthetic data distributions, addressing the computational overhead and architecture dependence associated with gradient matching.CaT uses this objective; GCDM matches receptive-field distributions, and DisCo separately condenses nodes and edges to improve scalability.Source: Matching-Based Methods · p. 9

Kernel Ridge Regression Methods

• KIDD turns graph-level condensation into a single-level objective by substituting the lower-level closed-form solution, using a graph kernel such as GNTK.The survey describes the squared-loss formulation with KRR and real–synthetic and synthetic–synthetic kernel matrices.Source: Kernel Ridge Regression Methods · p. 9

Other Methods

• Other methods match real and synthetic graph eigenbasis representations through class-center attributes, while MIRAGE extracts frequent computation trees from multiple graphs.GCEM uses subspace attributes because the real and synthetic eigenvector subspaces differ in size; MIRAGE’s frequent tree sets capture a significant portion of distribution mass.Source: Other Methods · pp. 9–10
• SFGC outputs condensed node features without graph structure, whereas GEOM uses an expanding window and reports lossless condensation on standard benchmarks.SFGC aligns long-term training trajectories using an offline expert parameter distribution; GEOM adjusts the matching range for difficult and easy nodes.Source: Other Methods · p. 10

4 Applications

• Graph reduction is applied beyond efficiency to architecture search, continual learning, visualization and explanation, privacy, and data augmentation.The survey presents these as applications of graph reduction’s versatility.Source: §4 · p. 10

4.1 Neural Architecture Search

• Training candidate GNN architectures on condensed graphs can speed neural architecture search, with reported performance correlation to full-data training.A dedicated condensation objective for NAS preserves hyperparameter-optimization outcomes and outperforms other condensation methods at finding the optimal architecture.Source: §4.1 · p. 10

4.2 Continual Graph Learning

• Reduced graphs support continual graph learning by serving as replay data; PUMA adds pseudo-labeled unlabeled nodes to CaT’s memory bank.The survey also describes curvature-based sparsification for storing nodes and edges in a replay buffer.Source: §4.2 · p. 10

4.3 Visualization & Explanation

• Coarsening, sparsification, and condensation support graph visualization and explanation, including multilevel visualization and inspection of reduced-graph patterns.Users can set graph granularity in k-snap and CANCEL for customized discovery; GDM uses condensation to explain GNN behavior during training.Source: §4.3 · p. 10

4.4 Privacy

• Graph reduction can preserve anonymity or support differential privacy, but the degree of reduction trades off against utility.In federated learning, FedGKD trains on condensed local graphs to mitigate potential membership leakage.Source: §4.4 · pp. 10–11

4.5 Data Augmentation

• Repeated reductions at different ratios can generate graph views for data augmentation, while HARP, MILE, DistMILE, and MSGC produce varied embeddings or embedding sets.HARP builds a graph hierarchy; MILE replaces its random walk with GNNs, DistMILE adds high-performance computing, and MSGC optimizes multiple initialized small graphs.Source: §4.5 · p. 11

5.1 Comprehensive Evaluation

• Evaluation should cover diverse graph properties and downstream tasks together to clarify reduced datasets’ practical utility across applications and domains.The survey names homophily and tasks including node classification, clustering, link prediction, and graph classification.Source: §5.1 · p. 11

5.2 Scalability

• Condensation remains computationally costly, making larger informative summaries and application to large-scale graphs challenging.The survey attributes its memory and execution costs to intricate optimization processes.Source: §5.2 · p. 11

5.3 Interpretability of Condensation Process

• Condensation interpretability is limited because continuous synthetic attributes are hard to interpret and synthetic nodes often lack clear correspondence to real nodes.The survey proposes interpretability frameworks, GNN interpretability techniques, and further theoretical analysis as research directions.Source: §5.3 · p. 11

5.4 Distribution Shift

• Reduction may induce distribution shift, but the field lacks consensus on how to define graph-data distributions or which properties represent them.The survey notes that measures beyond those used for distribution matching, such as graph size, may change after reduction.Source: §5.4 · p. 11

5.5 Robustness

• Reduced node attributes risk losing fidelity, while systematic evaluation, graph-specific attack strategies, and defenses for reduced-graph robustness remain underdeveloped.The survey mentions adversarial training combined with KIP as one robustness-improvement approach.Source: §5.5 · p. 12

5.6 Diverse Types of Graphs

• Most reduction work targets simple non-attributed or attributed graphs, leaving several real-world graph types incompletely explored.These include heterophilous, heterogeneous, directed, knowledge, hyper-, and dynamic graphs.Source: §5.6 · p. 12

• The survey establishes a formal definition and hierarchical taxonomy organizing graph reduction methods into sparsification, coarsening, and condensation.Source: §6 · p. 12
• It reviews prominent methods’ technical details and practical applications across real-world scenarios.Source: §6 · p. 12
• It identifies existing challenges and potential directions for future research in graph reduction.Source: §6 · p. 12