PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphSAINT: Graph Sampling Based Inductive Learning Method

Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, Viktor Prasanna

arXiv:1907.04931v4cs.LGstat.ML

TL;DR

Large-graph GCN training is hindered by neighbor explosion and the unresolved challenge of efficiently training deeper or variant architectures. GraphSAINT samples the training graph to build complete GCNs on subgraphs, using normalization and variance-reduction sampling. It reports advantages in accuracy and training time across five large graphs, including F1 scores of 0.995 on PPI and 0.970 on Reddit.

  • Problem

    Scaling GCNs to large graphs and deeper architectures remains difficult because layer-wise sampling must address neighbor explosion and efficient minibatch training.

  • Method

    GraphSAINT samples the training graph first, builds complete GCNs on sampled subgraphs, and uses normalization and variance-reduction sampling to improve minibatch training.

  • Results

    GraphSAINT demonstrates advantages in accuracy and training time across five large graphs, with F1 scores of 0.995 on PPI and 0.970 on Reddit.

  • Takeaways & Limitations

    Graph sampling based minibatches provide a training framework that also supports architecture variants such as jumping knowledge and attention.

  • Takeaways & Limitations

    GraphSAINT's topology-based sampling defines influence from connectivity rather than jointly using node connections and attributes, and distributed training remains future work.

Abstract

from arXiv · show

Graph Convolutional Networks (GCNs) are powerful models for learning representations of attributed graphs. To scale GCNs to large graphs, state-of-the-art methods use various layer sampling techniques to alleviate the "neighbor explosion" problem during minibatch training. We propose GraphSAINT, a graph sampling based inductive learning method that improves training efficiency and accuracy in a fundamentally different way. By changing perspective, GraphSAINT constructs minibatches by sampling the training graph, rather than the nodes or edges across GCN layers. Each iteration, a complete GCN is built from the properly sampled subgraph. Thus, we ensure fixed number of well-connected nodes in all layers. We further propose normalization technique to eliminate bias, and sampling algorithms for variance reduction. Importantly, we can decouple the sampling from the forward and backward propagation, and extend GraphSAINT with many architecture variants (e.g., graph attention, jumping connection). GraphSAINT demonstrates superior performance in both accuracy and training time on five large graphs, and achieves new state-of-the-art F1 scores for PPI (0.995) and Reddit (0.970).

1 INTRODUCTION

Scaling GCNs to large graphs and deeper layers is difficult because layer-wise neighborhood support can grow exponentially. GraphSAINT instead samples the training graph first, builds complete GCNs on sampled subgraphs, and addresses the resulting estimator bias and variance.

  • GCNs have mainly used shallow models on relatively small graphs, leaving efficient training for larger datasets and deeper layers as an open need.
  • Neighbor explosion occurs because each node recursively gathers information from multi-hop neighbors, causing potential exponential growth in support nodes and training time.
  • GraphSAINT samples the training graph before constructing a complete GCN on each sampled subgraph, rather than sampling across GCN layers.
  • Normalization techniques address bias from non-identical node sampling probabilities, while variance-reduction analysis motivates improved sampling algorithms.

2 RELATED WORK

Prior work scales GCNs through layer sampling, subgraph construction, or clustering, while other methods increase model capacity through attention, long-range propagation, and skip connections. Efficient minibatch training for these deeper architectural variants remains unresolved.

  • Layer sampling methods were introduced to enable efficient minibatch training of GCNs on large graphs after earlier full-batch methods targeted smaller datasets.
  • Subgraph-based approaches promote minibatches with connected nodes, while ClusterGCN forms minibatches by randomly selecting densely connected preprocessed clusters.
  • Graph attention architectures dynamically adjust edge weights to capture neighbor features, while PageRank-GCN methods propagate information from many hops away.
  • Skip connections and high-order graph convolutions support deeper or longer-distance propagation, but efficient minibatch training for these variants remains unanswered.

3 PROPOSED METHOD: GraphSAINT

GraphSAINT samples the training graph first, then builds a complete GCN on each sampled subgraph, using normalization to remove bias and specialized samplers to reduce variance. Its design targets scalable inductive learning while preserving connectivity and supports efficient training across GCN architectures.

  • 3 PROPOSED METHOD: GraphSAINT: GraphSAINT separates graph sampling from propagation and extends naturally to architecture variants such as jumping knowledge connections.Complete sampled-subgraph GCNs make skip connections straightforward, while some layer-sampling methods require sampler modifications.
  • 3.1 MINIBATCH BY GRAPH SAMPLING: GraphSAINT constructs minibatches by sampling small training subgraphs before building a complete GCN on each subgraph.Each iteration independently samples Gs with |Vs| much smaller than |V|, then performs forward and backward propagation on that complete subgraph.
  • 3.1 MINIBATCH BY GRAPH SAMPLING: The sampler should preserve connectivity among influential nodes while assigning every edge non-negligible sampling probability.The paper defines influence through graph connectivity and uses topology-based samplers, because feature-aware joint sampling may be costly.
  • 3.2 NORMALIZATION: Graph sampling can introduce bias, so GraphSAINT normalizes feature propagation and minibatch loss using node and edge sampling probabilities.Aggregator normalization uses edge probabilities, while loss normalization uses node probabilities; these coefficients can be estimated during preprocessing.
  • 3.3 VARIANCE: GraphSAINT derives sampling strategies that reduce estimator variance, including an optimal independent edge sampler under a fixed expected edge budget.The analysis exploits independent graph-edge decisions and dependence across layer edges to derive edge probabilities.
  • 3.3 VARIANCE: The proposed edge probability is simplified to depend on graph topology, assigning higher probability to edges joining low-degree nodes.The simplification ignores activation-dependent terms, yielding pe proportional to 1/deg(u) + 1/deg(v).

4 DISCUSSION

GraphSAINT combines graph sampling with broad GCN architecture compatibility, yielding scalability, accuracy, and low training complexity through connected subgraphs, unbiased estimation, and simple preprocessing.

  • GraphSAINT supports jumping knowledge, attention, and higher-order or graph-classification architectures through graph-sampled minibatches.Its complete subgraph GCNs make skip connections straightforward, while attention and other architectures can operate within sampled subgraphs.
  • GraphSAINT achieves high scalability, high accuracy, and low training complexity compared with layer- and graph-sampling alternatives.The paper attributes these properties respectively to reduced neighborhood size, better inter-layer connectivity and unbiased minibatch estimation, and simple parallelizable preprocessing.

5 EXPERIMENTS

Experiments evaluate GraphSAINT across five inductive supervised graph-learning tasks and compare accuracy, convergence, scalability, and architecture variants against established methods.

  • Setup: Experiments cover protein-function, image, online-post, business, and product-category classification on PPI, Flickr, Reddit, Yelp, and Amazon.The evaluation uses an inductive, supervised learning setting.
  • Setup: GraphSAINT is compared with vanilla GCN, GraphSAGE, FastGCN, S-GCN, AS-GCN, and ClusterGCN using released implementations.The baselines and GraphSAINT are implemented in TensorFlow with Python 3.
  • Comparison with state-of-the-art: Table 2 reports test-set F1-micro scores, while Table 3 adds comparison with ClusterGCN.Table 2 uses two-layer GCN models with matched hidden dimensions across methods; accuracy means and confidence intervals use three runs.
  • Comparison with state-of-the-art: GraphSAINT achieves significantly higher accuracy on all datasets with appropriate graph samplers and is faster than AS-GCN.S-GCN reaches similar Reddit accuracy but requires over 9× longer training time; AS-GCN’s sampler is expensive to execute.
  • Evaluation on graph samplers: Random-edge and random-walk samplers outperform random-node sampling, while random-walk accuracy stabilizes beyond r = 750.For PPI, increasing the number of roots from 250 to 750 significantly improves accuracy.
  • GraphSAINT on architecture variants and deep models: GraphSAINT yields two orders of magnitude speedup over GraphSAGE for 4-layer GAT and JK-net minibatches.With the edge sampler, JK-SAINT improves from 0.966 for 2 layers to 0.970 for 4 layers.

6 CONCLUSION

GraphSAINT is presented as a graph-sampling-based method for training deep GCNs on large graphs, with normalization and sampling algorithms aimed at improving training quality. Experiments demonstrate advantages in accuracy and training time, while distributed training remains a future direction.

  • GraphSAINT trains deep GCNs on large graphs using graph-sampling-based minibatches.
  • Normalization techniques and sampling algorithms are proposed to improve the quality of subgraph-defined minibatches.
  • Experiments demonstrate advantages for GraphSAINT in both accuracy and training time.
  • Distributed training with graph-sampling-based minibatches is identified as an interesting future direction.

A PROOFS

The proofs analyze variance and covariance properties of subgraph minibatches under sampling assumptions. They also connect the theoretical analysis to practical sampler budgets and an approximate edge-sampling implementation.

  • Theorem 3.2 analyzes covariance and variance for independent edge sampling.
  • The proof begins by assuming the relevant quantity is one-dimensional and scalar.
  • Sampler parameters specify budgets rather than exact subgraph sizes because nodes or edges may be sampled repeatedly.
  • The approximate edge sampler has O(m) complexity excluding subgraph induction and matches the original sampler’s accuracy when m ≪ |E| for a given m.

C.1 HARDWARE SPECIFICATION AND ENVIRONMENT

The experiments use a single-machine CPU/GPU environment and parallelize independent subgraph sampling across 40 CPU cores. The appendix also specifies GraphSAINT’s sampling inputs, graph construction procedures, and dataset representations.

  • Experiments run on dual Intel Xeon CPUs, one NVIDIA Tesla P100 GPU, and 512GB DDR4 memory.
  • The implementation uses Python, Cython for sampling, TensorFlow, CUDA, and cuDNN.
  • Independent subgraph samplers run in parallel on 40 CPU cores.
  • Graph sampling algorithms take a training graph with node, edge, root, and random-walk parameters and return a sampled graph.
  • Flickr, Yelp, and Amazon construct graph nodes, edges, features, and labels from image, user-review, and product-review data respectively.
  • Figure 5 represents degree distributions as the probability that a node has degree at least k.

C.3 ADDITIONAL DETAILS IN EXPERIMENTAL CONFIGURATION

The experimental appendix documents baseline-code references, hyperparameter search, evaluation, model configurations, and the setup for Figure 4. It also explains the JK-net and GAT variants used with GraphSAINT.

  • Hyperparameter search covers hidden dimensions of 128, 256, or 512; dropout from 0.0 to 0.3; and learning rates from 0.1 to 0.0001.
  • Hidden dimensions for the reported tables and figures are dataset-specific: 512 for PPI, 256 for Flickr, 128 for Reddit, and 512 for Yelp and Amazon.
  • Models are selected by validation F1-micro and reloaded for test-set accuracy evaluation.
  • Figure 4 configurations: Figure 4 compares GraphSAINT-based GAT and JK-net configurations on Reddit.
  • Figure 4 configurations: JK-net adds a final layer aggregating hidden features from graph-convolution layers 1 through L.
  • Figure 4 configurations: GAT computes neighbor-aggregation edge weights with an additional neural network and multi-head attention.
  • Figure 4 configurations: GAT-SAINT removes softmax normalization across all neighbors because minibatches may not contain every training-graph neighbor.

D.1 TRAINING EFFICIENCY ON DEEP MODELS

GraphSAINT’s training cost is approximately linear with GCN depth, addressing the steep depth-related cost growth associated with layer sampling.

  • Training cost for GraphSAINT is approximately linear with GCN depth on Reddit and Yelp.The comparison measures average time per minibatch as the number of layers increases.

D.2 COST OF SAMPLING AND PRE-PROCESSING

GraphSAINT’s graph sampling adds limited training overhead, while its offline preprocessing remains advantageous on large, dense graphs compared with ClusterGCN.

  • Sampling one subgraph takes less than 25% of training time in most cases for Node, Edge, and RW samplers.MRW sampling is more expensive than these samplers.
  • GraphSAINT preprocessing incurs no training-time overhead on PPI, Yelp, and Amazon under the Table 2 setting.Preprocessing takes less than 40% and 15% of total training time on Flickr and Reddit, respectively.
  • AS-GCN’s sampler is much more expensive than GraphSAINT’s graph sampler.The analysis models AS-GCN’s sampling network as an additional single-layer MLP, and Table 8 reports its training-time breakdown.
  • ClusterGCN preprocessing on Amazon exceeds 4× the total training time, whereas GraphSAINT’s sampling cost does not increase significantly for large graphs.ClusterGCN uses METIS for clustering, while GraphSAINT sampling and ClusterGCN clustering can both be performed offline.
  • GraphSAINT achieves significantly faster convergence than ClusterGCN on large, dense graphs such as Amazon when preprocessing, sampling, and training are combined.The comparison uses total convergence time, including preprocessing, sampling, and training.

D.3 EFFECT OF BATCH SIZE

Batch size affects accuracy differently across graph minibatch methods, with method-specific optima and failures reported for some baselines.

  • FastGCN’s accuracy improves noticeably when batch size increases from 400 to 4000.Increasing batch size may improve minibatch connectivity, although gains from 2000 to 4000 are not significant.
  • ClusterGCN’s optimal batch size depends on graph structure: small batches work better for PPI, while Amazon accuracy is not significantly affected.The reported accuracies are tuned across batch sizes and other hyperparameters.
  • GraphSAGE can lose accuracy with overly large batches because neighbor expansion increases support requirements.For a 2-layer GCN, a minibatch of 2 × 10^3 may require support from 2 × 10^5 nodes.
  • Some baseline implementations have practical limitations: certain training configurations do not converge, and codes may throw runtime errors on Yelp or Amazon.The convergence caveat and runtime-error caveat are reported separately.
  • S-GCN fails to learn properly on Reddit and Yelp at batch size 500, with accuracy fluctuating at a very low level after tuning.The passage reports this behavior under the evaluated settings.
Loading 1907.04931v4…