We present a new effective and scalable framework for training GNNs in
supervised node classification tasks, given graph-structured data. Our approach
increasingly refines the weight update operations on a sequence of path graphs
obtained by linearizing random spanning trees extracted from the input network.
The path graphs are designed to retain essential topological and node
information of the original graph. At the same time, the sparsity of path
graphs enables a much lighter GNN training which, besides scalability, helps in
mitigating classical training issues, like over-squashing and over-smoothing.
We carry out an extensive experimental investigation on a number of real-world
graph benchmarks, where we apply our framework to graph convolutional networks,
showing simultaneous improvement of both training speed and test accuracy, as
compared to well-known baselines.

提出一种新的有效且可扩展的框架，用于在给定图形结构数据的监督节点分类任务中训练 GNNs。该方法通过在从输入网络提取的随机生成树线性化的一系列路径图上越来越细化的权重更新操作进行。在此过程中，路径图旨在保留原始图的基本拓扑和节点信息。同时，路径图的稀疏性使得训练更轻便，有助于缓解经典训练问题，如过度压缩和平滑。在许多真实世界图形基准测试中进行了广泛的实验研究，将该框架应用于图卷积网络，与众所周知的基线相比，同时提高了训练速度和测试精度。