The Transferability of Downsamped Sparse Graph Convolutional Networks
This work addresses the need for theoretical guarantees in downsampling methods for efficient GCN training on sparse graphs, though it is incremental as it builds on existing downsampling approaches.
The paper tackles the problem of analyzing the transferability of downsampling methods for training graph convolutional networks on large-scale sparse graphs, deriving an expected upper bound for transfer error that decreases with smaller graph sizes, higher average degrees, and increased sampling rates, with experimental validation.
To accelerate the training of graph convolutional networks (GCNs) on real-world large-scale sparse graphs, downsampling methods are commonly employed as a preprocessing step. However, the effects of graph sparsity and topological structure on the transferability of downsampling methods have not been rigorously analyzed or theoretically guaranteed, particularly when the topological structure is affected by graph sparsity. In this paper, we introduce a novel downsampling method based on a sparse random graph model and derive an expected upper bound for the transfer error. Our findings show that smaller original graph sizes, higher expected average degrees, and increased sampling rates contribute to reducing this upper bound. Experimental results validate the theoretical predictions. By incorporating both sparsity and topological similarity into the model, this study establishes an upper bound on the transfer error for downsampling in the training of large-scale sparse graphs and provides insight into the influence of topological structure on transfer performance.