Fast and Effective GNN Training through Sequences of Random Path Graphs
This work addresses scalability and accuracy challenges in GNN training for node classification, particularly in label-scarce real-world scenarios, though it appears incremental as it builds on existing spectral graph theory and GNN methods.
The authors tackled the problem of training Graph Neural Networks (GNNs) more efficiently and accurately, especially with small training sets, by introducing GERN, a framework based on random path graphs derived from spanning trees, which achieved simultaneous improvements in training speed and test accuracy on real-world benchmarks.
We present GERN, a novel scalable framework for training GNNs in node classification tasks, based on effective resistance, a standard tool in spectral graph theory. Our method progressively refines the GNN weights on a sequence of random spanning trees suitably transformed into path graphs which, despite their simplicity, are shown to retain essential topological and node information of the original input graph. The sparse nature of these path graphs substantially lightens the computational burden of GNN training. This not only enhances scalability but also improves accuracy in subsequent test phases, especially under small training set regimes, which are of great practical importance, as in many real-world scenarios labels may be hard to obtain. In these settings, our framework yields very good results as it effectively counters the training deterioration caused by overfitting when the training set is small. Our method also addresses common issues like over-squashing and over-smoothing while avoiding under-reaching phenomena. Although our framework is flexible and can be deployed in several types of GNNs, in this paper we focus on graph convolutional networks and carry out an extensive experimental investigation on a number of real-world graph benchmarks, where we achieve simultaneous improvement of training speed and test accuracy over a wide pool of representative baselines.