Graph coarsening: from scientific computing to machine learning
Open Access
- 10 January 2022
- journal article
- research article
- Published by Springer Nature in SeMA Journal
- Vol. 79 (1) , 187-223
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.Keywords
Funding Information
- National Science Foundation (DMS-2011324)
- U.S. Department of Energy (DE-OE0000910)
- National Science Foundation (DMS-2011324)
This publication has 90 references indexed in Scilit:
- Geometry of complex networks and topological centralityPhysica A: Statistical Mechanics and its Applications, 2013
- A multilevel Crout ILU preconditioner with pivoting and row permutationNumerical Linear Algebra with Applications, 2007
- Laplacian Eigenmaps for Dimensionality Reduction and Data RepresentationNeural Computation, 2003
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- The electrical resistance of a graph captures its commute and cover timescomputational complexity, 1996
- Weighted graph based ordering techniques for preconditioned conjugate gradient methodsBIT Numerical Mathematics, 1995
- Algebraic multilevel iteration method for Stieltjes matricesNumerical Linear Algebra with Applications, 1994
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- A survey of multilevel preconditioned iterative methodsBIT Numerical Mathematics, 1989
- Multi-level adaptive solutions to boundary-value problemsMathematics of Computation, 1977