Graph Neural Networks (GNNs) are popular models for machine learning on
graphs that typically follow the message-passing paradigm, whereby the feature
of a node is updated recursively upon aggregating information over its
neighbors. While exchanging messages over the input graph endows GNNs with a
strong inductive bias, it can also make GNNs susceptible to over-squashing,
thereby preventing them from capturing long-range interactions in the given
graph. To rectify this issue, graph rewiring techniques have been proposed as a
means of improving information flow by altering the graph connectivity. In this
work, we identify three desiderata for graph-rewiring: (i) reduce
over-squashing, (ii) respect the locality of the graph, and (iii) preserve the
sparsity of the graph. We highlight fundamental trade-offs that occur between
spatial and spectral rewiring techniques; while the former often satisfy (i)
and (ii) but not (iii), the latter generally satisfy (i) and (iii) at the
expense of (ii). We propose a novel rewiring framework that satisfies all of
(i)--(iii) through a locality-aware sequence of rewiring operations. We then
discuss a specific instance of such rewiring framework and validate its
effectiveness on several real-world benchmarks, showing that it either matches
or significantly outperforms existing rewiring approaches.

图神经网络是基于图的机器学习的流行模型，本文提出了一种新的图重连框架，通过一系列的重连操作满足降低过度挤压、保持图的局部性和稀疏性等特点，并验证其在多个真实世界基准测试中的有效性。