Stochastic Training of Graph Convolutional Networks

Jianfei Chen, Jun Zhu

TL;DR

This paper tackles the computational bottleneck of training Graph Convolutional Networks (GCNs) by developing novel variance-reduction techniques. Their "control variate" approach allows for significantly smaller neighbor sampling sizes, leading to faster training times (up to 7x speedup on large datasets) while maintaining comparable accuracy and theoretical convergence guarantees.

What Problem Does This Paper Address?

Graph Convolutional Networks (GCNs) are powerful tools for analyzing graph-structured data, but their effectiveness comes at a computational cost. The core operation in GCNs involves aggregating information from a node's neighbors. As you stack more GCN layers, a single node's "receptive field" (the set of nodes it ultimately influences or is influenced by) grows exponentially. This makes training GCNs on large graphs computationally expensive, often requiring batch processing that doesn't scale well. Previous attempts to speed this up using neighbor sampling (NS) lacked theoretical convergence guarantees and still required sampling hundreds of neighbors per node, which is still computationally demanding.

Methods

The authors introduce control variate (CV) based stochastic approximation algorithms to address the variance and convergence issues of neighbor sampling. The key idea is to maintain a "historical activation" for each node. When computing the current activation, they leverage this historical value as a control variate. This allows them to:

  • Reduce Variance: By using the difference between the current and historical activation, the variance of their estimator is reduced. This variance is shown to depend on the difference in activations, not just their magnitude, which is more stable.
  • Provide Theoretical Guarantees: Unlike previous NS methods, their CV-based algorithms are theoretically proven to converge to a local optimum of GCN, regardless of how few neighbors are sampled.
  • Enable Exact Testing: At test time, their method can produce exact predictions after a few epochs, outperforming NS which requires infinite samples for exactness.

They also introduce a preprocessing strategy that reorders operations (specifically, applying dropout after neighbor averaging) to further optimize computation. They also propose a Control Variate for Dropout (CVD) method to handle the variance introduced by dropout layers.

Datasets

The paper evaluates their methods on several standard graph datasets:

  • Citeseer
  • Cora
  • PubMed
  • NELL
  • PPI (for multi-label classification)
  • Reddit (a large-scale dataset)

They use standard train/validation/test splits and report results for both GCN and GraphSAGE models.

Key Insights and Ideas

  • Historical Activations as a Powerful Control Variate: The core insight is that historical node activations, when used as control variates, can significantly stabilize GCN training by reducing the variance of stochastic gradients.
  • Theoretical Guarantees for Stochastic GCNs: Providing formal convergence guarantees for stochastic GCN training is crucial for building trust and understanding the behavior of these methods, especially when using aggressive sampling.
  • Small Neighbor Sets are Sufficient: The most impactful finding is that sampling a very small number of neighbors (as few as two per node) can achieve performance comparable to exact methods, drastically reducing computational cost.
  • Preprocessing Matters: The order of operations, particularly regarding dropout, can be optimized for efficiency without sacrificing performance.

Key Results

  • Significant Speedup: On the large Reddit dataset, their method achieved a 7x speedup compared to previous state-of-the-art neighbor sampling algorithms.
  • Comparable Accuracy: Their algorithms achieved validation accuracy comparable to exact GCN training, even with drastically reduced neighbor sampling (e.g., 2 neighbors vs. hundreds).
  • Theoretical Convergence: They proved that their CV-based algorithms converge to a local optimum, a guarantee not offered by prior NS methods.
  • Exact Predictions at Test Time: Their method can recover exact predictions after a few epochs of forward passes, which is a significant advantage over NS.
  • Reduced Gradient Bias and Variance: Empirical results (Figure 5) show that their methods produce gradients with significantly lower bias and variance compared to NS.

Limitations and Future Work

  • Scalability for Extremely Large Graphs: While significantly faster, the paper mentions that for extremely large graphs, further subsampling of neighbor histories might be necessary.
  • Assumptions for Variance Analysis: The variance analysis in Section 5.2 relies on the assumption that node activations are uncorrelated, which is empirically shown to be a reasonable approximation for deeper GCNs due to graph sparsity.
  • Future Work: The paper suggests exploring the application of their methods to other graph-based models and tasks, and further investigating the impact of different preprocessing strategies.

Summary updated

Abstract

Graph convolutional networks (GCNs) are powerful deep neural networks for graph-structured data. However, GCN computes nodes' representation recursively from their neighbors, making the receptive field size grow exponentially with the number of layers. Previous attempts on reducing the receptive field size by subsampling neighbors do not have any convergence guarantee, and their receptive field size per node is still in the order of hundreds. In this paper, we develop a preprocessing strategy and two control variate based algorithms to further reduce the receptive field size. Our algorithms are guaranteed to converge to GCN's local optimum regardless of the neighbor sampling size. Empirical results show that our algorithms have a similar convergence speed per epoch with the exact algorithm even using only two neighbors per node. The time consumption of our algorithm on the Reddit dataset is only one fifth of previous neighbor sampling algorithms.
BibTeX
@inproceedings{chen2018stochastic,
  author = {Jianfei Chen and Jun Zhu},
  title = {{Stochastic Training of Graph Convolutional Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2018},
  url = {https://openreview.net/forum?id=By-tvnZdZS},
}
Figure