PaperlayerView exact revision on arXiv

Source-linked AI summary

FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling

Jie Chen, Tengfei Ma, Cao Xiao

arXiv:1801.10247v1cs.LG

TL;DR

GCN’s transductive formulation and recursive neighborhood expansion create inductive-learning and scalability challenges on large, dense graphs. FastGCN reformulates graph convolutions as integral transforms estimated through Monte Carlo sampling, achieving faster training with comparable prediction performance.

  • Problem

    GCN requires training and test data together, while recursive neighborhood expansion makes batched training expensive for large, dense graphs.

  • Method

    FastGCN interprets graph convolutions as integral transforms and uses Monte Carlo sampling, with importance sampling available for variance reduction.

  • Results

    FastGCN is faster than GCN and GraphSAGE while maintaining comparable prediction performance.

  • Takeaways & Limitations

    FastGCN generalizes transductive GCN training inductively and addresses GCN’s memory bottleneck from recursive neighborhood expansion.

  • Takeaways & Limitations

    GraphSAGE can be better suited for massive graphs, while sampling overhead may reduce FastGCN’s timing advantage on small graphs.

Abstract

from arXiv · show

The graph convolutional networks (GCN) recently proposed by Kipf and Welling are an effective graph model for semi-supervised learning. This model, however, was originally designed to be learned with the presence of both training and test data. Moreover, the recursive neighborhood expansion across layers poses time and memory challenges for training with large, dense graphs. To relax the requirement of simultaneous availability of test data, we interpret graph convolutions as integral transforms of embedding functions under probability measures. Such an interpretation allows for the use of Monte Carlo approaches to consistently estimate the integrals, which in turn leads to a batched training scheme as we propose in this work---FastGCN. Enhanced with importance sampling, FastGCN not only is efficient for training but also generalizes well for inference. We show a comprehensive set of experiments to demonstrate its effectiveness compared with GCN and related models. In particular, training is orders of magnitude more efficient while predictions remain comparably accurate.

1 INTRODUCTION

GCN learns vertex representations by mixing neighborhood information, but its transductive setup and recursive neighborhood expansion limit inductive use and scalability. FastGCN addresses both issues by reformulating graph convolutions as integral transforms and estimating them with sampling.

  • GCN uses graph connectivity as a convolution filter to mix neighborhood information when learning vertex representations.
  • GCN’s adjacency matrix and embeddings jointly involve training and test vertices, making the original formulation transductive.
  • Expanding neighborhoods recursively across layers makes mini-batch training costly, especially on dense and powerlaw graphs.
  • FastGCN interprets graph convolutions as integral transforms under probability measures and uses Monte Carlo approximation for sampled losses and gradients.
  • FastGCN removes reliance on test data and provides controllable per-batch computation while maintaining highly comparable classification accuracy to GraphSAGE.

2 RELATED WORK

Related work includes graph-level spectral methods, vertex-embedding approaches, and neighborhood-aggregation methods. FastGCN is most closely related to GraphSAGE but differs by sampling vertices rather than neighbors.

  • Spectral graph methods define parameterized filters in the spectral domain and can learn representations for whole-graph classification.
  • Vertex-embedding methods include matrix factorization, random walks, proximity preservation, and deep neural architectures such as SDNE.
  • GraphSAGE aggregates neighborhood information and uses ad hoc sampling to restrict neighborhood size because GCN has a memory bottleneck.
  • FastGCN differs from GraphSAGE by sampling vertices rather than neighbors, yielding computational savings analyzed in the paper.

3 TRAINING AND INFERENCE THROUGH SAMPLING

FastGCN recasts graph convolutions as integral transforms, enabling Monte Carlo estimation and batched training despite graph-induced dependence. Its vertex sampling avoids recursive neighborhood expansion and supports variance reduction through importance sampling.

  • Motivation: GCN graph convolutions create dependent sample losses because each vertex incorporates recursively expanding neighborhood information.This makes conventional independent-sample SGD gradients difficult to compute efficiently.
  • Functional formulation: FastGCN interprets each layer as an embedding-function integral transform over graph vertices sharing a probability measure.The functional formulation separates training and test data naturally for inductive learning.
  • Monte Carlo training: Monte Carlo estimates of the layer integrals produce a batched training algorithm whose estimator is consistent as all sample counts grow.The consistency statement is formalized as convergence to the original loss with probability one.
  • Batched computation: FastGCN samples vertices independently at each layer, so the number of involved vertices grows with the sum of layer sample sizes rather than their product.This contrasts with neighborhood sampling, whose worst-case expansion multiplies sample sizes across layers.
  • Variance reduction: Importance sampling changes the vertex sampling measure to reduce layer-estimator variance, although the optimal distribution is expensive to recompute during training.The optimal choice minimizes variance, while the practical choice avoids repeatedly computing the changing embedding–parameter product.

4 EXPERIMENTS

Experiments evaluate FastGCN on Cora, Pubmed, and Reddit against GCN and GraphSAGE, examining sampling choices, precomputation, training speed, and prediction accuracy. FastGCN achieves substantially faster training while retaining comparable accuracy, though GraphSAGE's improved implementation narrows the gap on Cora.

  • Experimental setup: Experiments compare GCN, GraphSAGE, and FastGCN on Cora, Pubmed, and Reddit node-classification tasks.The datasets increase in graph size, and the implementations use two-layer networks.
  • Sampling and precomputation: Increasing FastGCN sample sizes raises per-epoch training time while generally improving micro F1 accuracy on Pubmed.The comparison equalizes sample sizes across both layers.
  • Sampling and precomputation: Precomputing ˆAH(0) substantially decreases training time while maintaining comparable accuracy, so subsequent experiments use precomputation.The input features are fixed, making the bottom-layer product constant throughout training.
  • Sampling and precomputation: Importance sampling consistently produces higher prediction accuracy than uniform sampling across the three datasets.The authors attribute this result to lower sampling variance and use importance sampling thereafter.
  • Overall comparison: FastGCN is fastest, improving training time by at least an order of magnitude over the runner-up except on Cora, while achieving accuracy highly comparable to the other methods.The comparison uses FastGCN sample sizes selected for best prediction accuracy; Figure 3 reports per-batch time and prediction accuracy.
  • Overall comparison: An improved GraphSAGE implementation makes its per-batch time more favorable on Cora, but does not affect large graphs such as Reddit or the reported orders-of-magnitude advantage.The revised implementation is in PyTorch, whereas the other implementations are in TensorFlow.

5 CONCLUSIONS

FastGCN reformulates graph convolutions as integral transforms, enabling sampling-based training that generalizes GCN from transductive to inductive learning. It addresses GCN’s neighborhood-expansion bottleneck while maintaining highly comparable prediction performance.

  • 5 CONCLUSIONS: FastGCN generalizes GCN training from transductive to inductive learning and addresses the memory bottleneck caused by recursive neighborhood expansion.Its sampling scheme follows from reformulating the loss and gradient through integral transforms of embedding functions.
  • 5 CONCLUSIONS: FastGCN and GraphSAGE use substantially different sampling schemes, with FastGCN’s computational cost analyzed against GraphSAGE.FastGCN samples vertices rather than neighbors, according to the related-work discussion.
  • 5 CONCLUSIONS: FastGCN is orders of magnitude faster than GCN and GraphSAGE while maintaining highly comparable prediction performance.The conclusion reports this pattern across the experimental comparison without specifying a single dataset or metric.
  • 5 CONCLUSIONS: The integral-transform interpretation may extend to first-order-neighborhood graph models, but variance-reduction strategies for those models remain an open research direction.The paper specifically mentions MoNet and message-passing neural networks as possible targets for further investigation.

A PROOFS

The proofs establish consistency and variance properties for the Monte Carlo estimators used in FastGCN. They derive convergence through iid sampling, variance scaling, total-variance arguments, and induction across layers.

  • Consistency proofs: Under iid sampling, the Monte Carlo estimator converges almost surely to the corresponding graph-convolution integral.The proof invokes the strong law of large numbers and then uses continuity of the activation function.
  • Layerwise convergence: Almost-sure convergence of successive sampled layers follows by induction, with the continuous mapping theorem handling the activation function.The proof first establishes convergence for an intermediate layer and then completes the argument recursively.
  • Variance analysis: The overall variance is obtained by applying the law of total variance after taking expectations and variances over iid sampled vertices.The proof sequence instantiates the sampling expressions and combines conditional and front-sampling variation.
  • Variance analysis: The variance of the estimator conditioned on a vertex is reduced by a factor of 1/t relative to the variance of the sampled integrand.This scaling is stated for the estimators analyzed in the proposition proofs.
  • Importance sampling: The optimal importance-sampling distribution is proportional to b(u)|x(u)| dP(u), with normalization required for it to integrate to unity.This choice follows from the variance minimization argument.

B ADDITIONAL EXPERIMENT DETAILS

The additional experiment details define the GCN and GraphSAGE baselines used to compare FastGCN’s training time and prediction accuracy.

  • Baselines: The batched GCN baseline removes sampling and uses all nodes in each batch because the original GCN cannot operate on very large graphs such as Reddit.For Cora and Pubmed, the experiments also compare against the original GCN.
  • Baselines: GraphSAGE-GCN uses GCN aggregation for training-time comparison, while GraphSAGE-mean is additionally evaluated for accuracy.GraphSAGE-GCN is described as the fastest aggregator choice among those tested.
  • Baseline settings: GraphSAGE uses two layers with neighborhood sample sizes S1 = 25 and S2 = 10, with batch size matched to FastGCN.These settings follow Hamilton et al. (2017).

B.2 EXPERIMENT SETUP

The experiments use Cora, Pubmed, and Reddit with revised training indices, tuned learning rates and model dimensions, and fixed optimization and batching settings.

  • Datasets: The experiments use Cora, Pubmed, and Reddit, while keeping validation and test indices unchanged and assigning the remaining nodes to training.Cora and Pubmed come from the GCN repository, and Reddit comes from the GraphSAGE dataset source.
  • Hyperparameters: Learning rates are selected from {0.01, 0.001, 0.0001}, with FastGCN hidden dimension 128 for Reddit and 16 for Cora and Pubmed.The setup also performs hyperparameter selection for model dimension.
  • Training configuration: Batch sizes are 256 for Cora and Reddit and 1024 for Pubmed, with dropout set to 0 and Adam used for optimization.These settings are part of the reported experiment configuration.
  • Inference configuration: At test time, the trained parameters are applied using all graph nodes rather than sampling.The reported inference procedure differs from the sampled training procedure.
  • Hardware: Running-time comparisons use a single machine with a 4-core 2.5 GHz Intel Core i7 processor and 16G RAM.The hardware specification defines the environment for timing comparisons.

C.1 TRAINING TIME COMPARISON

FastGCN retains a substantial overall training-time advantage despite convergence effects, while Figure 4 tracks training and test accuracy against training time across Cora, Pubmed, and Reddit.

  • FastGCN maintains a substantial advantage in overall training time despite convergence weakening its orders-of-magnitude per-batch speedup.The comparison should use the batched GCN version because original GCN does not scale under memory limitations.
  • Table 4 reports total training time in seconds.
  • Figure 4 plots training and test accuracy against training time for Cora, Pubmed, and Reddit.

C.2 ORIGINAL DATA SPLIT FOR CORA AND PUBMED

On the original Cora and Pubmed split, scarce labels make FastGCN less accurate than GCN in its inductive form, while its transductive version matches GCN accuracy. The convergence analysis separately establishes an O(1/k) rate under strict-convexity and bounded-gradient assumptions.

  • Original data split results: FastGCN’s accuracy is inferior to GCN on the original split because labeled data are scarce, while FastGCN-transductive matches GCN accuracy.The original split uses substantially fewer training labels than the supervised Reddit-aligned setting.
  • Original data split results: GCN training is slower on this split because the reproduced hyperparameters differ from the better learning rate used for the new split.The better learning rate accelerates convergence on the new data split.
  • Convergence analysis: The convergence analysis addresses the bias of the consistent gradient estimator and treats a simple case rather than providing a comprehensive theory.
  • Convergence analysis: Under strict convexity, uniformly bounded gradients, and γ_k = (lk)^-1, the update converges at order O(1/k).
Loading 1801.10247v1…