A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation
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.
Code (4)
Tasks
SurveySimilar Papers 제목 키워드 기반
Understanding the Impact of Graph Reduction on Adversarial Robustness in Graph Neural Networks
As Graph Neural Networks (GNNs) become increasingly popular for learning from large-scale graph data across various domains, their susceptibility to adversarial attacks when using graph reduction techniques for scalabili…
Adversarial RobustnessOn the Robustness of Graph Reduction Against GNN Backdoor
Graph Neural Networks (GNNs) are gaining popularity across various domains due to their effectiveness in learning graph-structured data. Nevertheless, they have been shown to be susceptible to backdoor poisoning attacks,…
Computational EfficiencyData PoisoningSampling and multilevel coarsening algorithms for fast matrix approximations
This paper addresses matrix approximation problems for matrices that are large, sparse and/or that are representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsen…
Dimensionality ReductionIsing on the Graph: Task-specific Graph Subsampling via the Ising Model
Reducing a graph while preserving its overall structure is an important problem with many applications. Typically, reduction approaches either remove edges (sparsification) or merge nodes (coarsening) in an unsupervised …
Graph ClassificationGraph Neural NetworkImage SegmentationSemantic SegmentationGraph reduction with spectral and cut guarantees
Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the sp…