Modern challenges in graph coarsening

Graph coarsening [1], or graph reduction, is a complex and difficult problem that consists
in, given a large graph, producing a smaller graph that “summarizes” the initial one. The
objective can be to save computing time and memory, but also to extract some interesting
properties of the original graph through its reduction. An ubiquitous tool in many areas
of scientific computing, it has been postulated that graph coarsening could bear many
interesting links with the recent domain of graph Machine Learning, which has known an
exponential growth in terms of scope, applications and literature in the last few years.
In particular, just as multi-scale Convolutional Neural Networks involve “pooling” steps,
researchers have tried to integrate graph coarsening methods in Graph Neural Networks
(GNN), but the results were generally not conclusive, mainly due to the complexity and
unstability of the current approaches. Hence the need for better, more stable approaches.
In this thesis, we will study more data-driven approaches to perform graph coarsening
through the definition of well-behaved cost functions, both supervised or unsupervised,
which could be more stable that approaches involving randomness. We will examine their
integration in GNNs such as Graph UNets [2].
There are many methods to perform graph coarsening, but most seek to preserve some
properties of the original graph, such as the spectrum of its Laplacian [4, 3]. Depending
on the candidate, we will examine such guarantees, and particularly their limitations. We
will study, both empirically and theoretically, the difference between random-based and
learning-based approaches for graph coarsening.