Graph coarsening: from scientific computing to machine learning
Abstract The general method of graph coarsening or graph reduction has been a remarkably useful and ubiquitous tool in scientific computing and it is now just starting to have a similar impact in machine learning. The goal of this paper is to take a broad look into coarsening techniques...
| Main Authors: | , , |
|---|---|
| 其他作者: | |
| 格式: | 文件 |
| 语言: | English |
| 出版: |
Springer International Publishing
2022
|
| 在线阅读: | https://hdl.handle.net/1721.1/139626 |
| _version_ | 1826205743286583296 |
|---|---|
| author | Chen, Jie Saad, Yousef Zhang, Zechen |
| author2 | MIT-IBM Watson AI Lab |
| author_facet | MIT-IBM Watson AI Lab Chen, Jie Saad, Yousef Zhang, Zechen |
| author_sort | Chen, Jie |
| collection | MIT |
| description | Abstract
The general method of graph coarsening or graph reduction has been a remarkably useful and ubiquitous tool in scientific computing and it is now just starting to have a similar impact in machine learning. The goal of this paper is to take a broad look into coarsening techniques that have been successfully deployed in scientific computing and see how similar principles are finding their way in more recent applications related to machine learning. In scientific computing, coarsening plays a central role in algebraic multigrid methods as well as the related class of multilevel incomplete LU factorizations. In machine learning, graph coarsening goes under various names, e.g., graph downsampling or graph reduction. Its goal in most cases is to replace some original graph by one which has fewer nodes, but whose structure and characteristics are similar to those of the original graph. As will be seen, a common strategy in these methods is to rely on spectral properties to define the coarse graph. |
| first_indexed | 2024-09-23T13:17:58Z |
| format | Article |
| id | mit-1721.1/139626 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:17:58Z |
| publishDate | 2022 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1396262023-04-10T19:33:24Z Graph coarsening: from scientific computing to machine learning Chen, Jie Saad, Yousef Zhang, Zechen MIT-IBM Watson AI Lab Abstract The general method of graph coarsening or graph reduction has been a remarkably useful and ubiquitous tool in scientific computing and it is now just starting to have a similar impact in machine learning. The goal of this paper is to take a broad look into coarsening techniques that have been successfully deployed in scientific computing and see how similar principles are finding their way in more recent applications related to machine learning. In scientific computing, coarsening plays a central role in algebraic multigrid methods as well as the related class of multilevel incomplete LU factorizations. In machine learning, graph coarsening goes under various names, e.g., graph downsampling or graph reduction. Its goal in most cases is to replace some original graph by one which has fewer nodes, but whose structure and characteristics are similar to those of the original graph. As will be seen, a common strategy in these methods is to rely on spectral properties to define the coarse graph. 2022-01-19T20:17:10Z 2022-01-19T20:17:10Z 2022-01-10 2022-01-16T05:09:58Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/139626 Chen, Jie, Saad, Yousef and Zhang, Zechen. 2022. "Graph coarsening: from scientific computing to machine learning." PUBLISHER_CC en https://doi.org/10.1007/s40324-021-00282-x Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer International Publishing Springer International Publishing |
| spellingShingle | Chen, Jie Saad, Yousef Zhang, Zechen Graph coarsening: from scientific computing to machine learning |
| title | Graph coarsening: from scientific computing to machine learning |
| title_full | Graph coarsening: from scientific computing to machine learning |
| title_fullStr | Graph coarsening: from scientific computing to machine learning |
| title_full_unstemmed | Graph coarsening: from scientific computing to machine learning |
| title_short | Graph coarsening: from scientific computing to machine learning |
| title_sort | graph coarsening from scientific computing to machine learning |
| url | https://hdl.handle.net/1721.1/139626 |
| work_keys_str_mv | AT chenjie graphcoarseningfromscientificcomputingtomachinelearning AT saadyousef graphcoarseningfromscientificcomputingtomachinelearning AT zhangzechen graphcoarseningfromscientificcomputingtomachinelearning |