FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling

By Tengfei Ma, Cao Xiao. 2018

1,744 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Graph Learning

Citations in the corpus

Graph Convolutional Neural Networks for Web-Scale Recommender Systems (2018, methodology): “In terms of algorithm design, our work is most closely related to Hamilton et al. (2017a)’s GraphSAGE algorithm [18] and the closely related follow-up work of Chen et al. (2018) [8].”
Graph Convolutional Networks for Text Classification (2018, methodology): “Possible solutions to the problem are introducing inductive (Hamilton, Ying, and Leskovec 2017) or fast GCN model (Chen, Ma, and Xiao 2018).”
Deep Graph Infomax (2018, methodology): “We also provide supervised results for two related architectures— FastGCN (Chen et al., 2018) and Avg. pooling (Zhang et al., 2018).”
Predict then Propagate: Graph Neural Networks meet Personalized PageRank (2018, background): “…Hamilton et al., 2017; Veliˇckovi´c et al., 2018), random walks (Abu-El-Haija et al., 2018a; Ying et al., 2018; Li et al., 2018), edge features (Kearnes et al., 2016; Gilmer et al., 2017; Schlichtkrull et al., 2018) and making it more scalable on large graphs (Chen et al., 2018; Ying et al., 2018).”
Lifelong Graph Learning (2020, critical): “FastGCN [7] applied importance sampling to reduce variance and perform node sampling for each layer independently, resulting in a constant sample size in all layers.”
Simplifying Graph Convolutional Networks (2019, methodology): “For citation networks, we compare against GCN (Kipf & Welling, 2017) GAT (Velickovic et al., 2018) FastGCN (Chen et al., 2018) LNet, AdaLNet (Liao et al., 2019) and DGI (Velikovi et al., 2019) using the publicly released implementations.”
Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks (2019, methodology): “GCN [9] Vanilla SGD GraphSAGE [5] FastGCN [1] VR-GCN [2] Cluster-GCN”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, methodology): “Different from the current flourishing designs of GNNs (Bruna et al., 2014; Defferrard et al., 2016; Li et al., 2016; Kipf & Welling, 2017; Hamilton et al., 2017; Gilmer et al., 2017; Chen et al., 2018; Velic̆ković et al., 2018), the proposed ones are generalized from linear SEM, so that the new mod”
Simple and Deep Graph Convolutional Networks (2020, methodology): “We compare GCNII with the following state-of-the-art methods: GraphSAGE (Hamilton et al., 2017), VR-GCN (Chen et al., 2018b), GaAN (Zhang et al., 2018), GAT (Veliˇckovi´c et al., 2018), JKNet (Xu et al., 2018), GeniePath (Liu et al., 2019), Cluster-GCN (Chiang et al., 2019).”
Amalgamating Knowledge from Heterogeneous Graph Neural Networks (2021, methodology): “We adjust the training/validation/testing split for the training of teachers in the supervised scenario, as is also done in [2].”
A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directions (2021, methodology): “The sampling strategy is also adopted in a few other works [22, 29], which reduces the computation complexity of GNN and improves the scalability.”
Heterogeneous Graph Transformer (2020, methodology): “dea is to sample heterogeneous subgraphs in which different types of nodes are with similar proportions, since the direct usage of existing (homogeneous) GNN samplingmethods,suchasGraphSage[7],FastGCN[1],andLADIES[29], results in highly imbalanced ones regarding to both node and edge types.Inadditio”
How Powerful are Spectral Graph Neural Networks (2022, background): “Introduction Graph Neural Networks (GNNs) have achieved state-of-theart performance on almost all tasks among various graph representation learning methods (Yao et al., 2019; Fout et al., 2017; Chen et al., 2018).”
GNNExplainer: Generating Explanations for Graph Neural Networks (2019, methodology): “Thus, GNNEXPLAINER can be applied to: Graph Convolutional Networks [21], Gated Graph Sequence Neural Networks [26], Jumping Knowledge Networks [36], Attention Networks [33], Graph Networks [4], GNNs with various node aggregation schemes [7, 5, 18, 16, 40, 39, 35], Line-Graph NNs [8], position-aware ”
Graph convolutional networks: a comprehensive review (2019, methodology): “Abbreviations CNN: convolution neural network; ChebNet: Chebyshev polynomial based graph convolution (model proposed in [34]); GCN: graph convolutional network (model proposed in [37]); FastGCN: minibatch training for GCN (model proposed in [39]); CayleyNet: Cayley polynomial based graph convolution”
Robust Graph Representation Learning via Neural Sparsification (2020, methodology): “Several works (Zeng et al., 2020; Hamilton et al., 2017; Chen et al., 2018) focus on downsampling under predeﬁned dis-Robust tributions.”