Clustering with Entropy-based Recombination for Training GCNs on Large Graphs

With the development of deep learning methods on non-grid graph data, Graph Convolutional Networks (GCNs) are playing important roles in a wide range of scenarios. When dealing with graphs with ever-growing sizes, even if the compute capability of one GPU card is sufficient, its limited memory capacity would make the training on large graphs infeasible. Sampling methods on three levels (i.e., node-level, layer-level, and subgraph-level) have been proposed to improve the scalability of GCNs. However, there still exist drawbacks in sampling-based approaches including time-consuming sampling processes and biased node representations. To tackle these issues, we propose a novel subgraph-based sampling method considering the generalized distance of label distribution between each subgraph and the whole graph. Specifically, our method introduces two pre-steps before training: (1) partitioning all the nodes in the original graph into different clusters through an efficient clustering algorithm; (2) combining the clusters obtained in the first step into a set of bigger groups (subgraphs) based on the information entropy theory. Experiments show that our work could reserve similar label distribution to that on the whole graph and outperform SOTA models in terms of classification accuracy on different datasets. Besides, the time cost of our pre-processing procedure is acceptable compared with the time spent in training.