A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916306572279808 |
|---|---|
| author | Hashemi, Mohammad Gong, Shengbo Ni, Juntong Fan, Wenqi Prakash, B. Aditya Jin, Wei |
| author_facet | Hashemi, Mohammad Gong, Shengbo Ni, Juntong Fan, Wenqi Prakash, B. Aditya Jin, Wei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03358 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation Hashemi, Mohammad Gong, Shengbo Ni, Juntong Fan, Wenqi Prakash, B. Aditya Jin, Wei Social and Information Networks Artificial Intelligence Data Structures and Algorithms Machine Learning 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. |
| title | A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation |
| topic | Social and Information Networks Artificial Intelligence Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2402.03358 |