Deep Graph Coarsening: Learning to Contract Edges

Graph coarsening reduces the number of nodes in a graph while preserving the structural properties that downstream tasks rely on. Classical coarsening methods are fixed algorithms designed heuristically to preserve a particular property of the graph, such as the low end of the Laplacian spectrum. They do not adapt to the graph domain at hand, and targeting a different property requires designing a new heuristic. We propose to learn the coarsening operator instead, directly from the objective it should optimize. We demonstrate that this is possible. Our general framework lets a graph neural network assign scores to the edges of a graph, and then contract a maximum-weight forest with a given number of edges. To address that the coarsening operation is discrete and non-differentiable, we use a straight-through estimator and smoothen the objective with noise. We evaluate our method using a Laplacian spectrum-preserving objective. Across nine graph datasets and three reduction ratios, the learned operator outperforms the best classical baseline in 24 of 27 settings and on all nine datasets at the highest reduction ratio ($75\%$). Notably, these include methods explicitly designed for this objective, whereas our method is general.