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

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

Mohammad Hashemi, Shengbo Gong, Juntong Ni, Wenqi Fan, B. Aditya Prakash, Wei Jin

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Survey Track. Pages 8058-8066. https://doi.org/10.24963/ijcai.2024/891

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 techniques have 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.
Keywords:
Data Mining: DM: Mining graphs
Machine Learning: ML: Sequence and graph learning
Machine Learning: General