Graph coarsening aims to reduce the size of a large graph while preserving
some of its key properties, which has been used in many applications to reduce
computational load and memory footprint. For instance, in graph machine
learning, training Graph Neural Networks (GNNs) on coarsened graphs leads to
drastic savings in time and memory. However, GNNs rely on the Message-Passing
(MP) paradigm, and classical spectral preservation guarantees for graph
coarsening do not directly lead to theoretical guarantees when performing naive
message-passing on the coarsened graph. In this work, we propose a new
message-passing operation specific to coarsened graphs, which exhibit
theoretical guarantees on the preservation of the propagated signal.
Interestingly, and in a sharp departure from previous proposals, this operation
on coarsened graphs is oriented, even when the original graph is undirected. We
conduct node classification tasks on synthetic and real data and observe
improved results compared to performing naive message-passing on the coarsened
graph.

通过提出一种适用于粗化图的新的消息传递操作，我们在合成和真实数据上进行节点分类任务，并观察到与在粗化图上执行简单的消息传递相比，取得了改进的结果。