PaperlayerView exact revision on arXiv

Source-linked AI summary

Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks

Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, Quanquan Gu

arXiv:1911.07323v1cs.LGcs.SIstat.ML

TL;DR

Large-graph GCN training is limited by full-batch costs and by sampling methods’ receptive-field growth or sparse cross-layer connections. LADIES uses layer-dependent importance sampling over upper-layer neighborhoods, and the paper reports lower costs, lower variance, and stronger accuracy than prior methods and full-batch GCN.

  • Problem

    Training deep GCNs on large graphs is difficult because full-batch computation is costly and sampling methods face exponential expansion or sparse cross-layer connectivity.

  • Method

    LADIES samples upper-layer neighborhoods, computes layer-dependent importance probabilities, and recursively builds fixed-size bipartite computation graphs.

  • Results

    LADIES achieves lower memory and time costs, lower estimation variance, and higher benchmark test accuracy than existing GCN training methods.

  • Takeaways & Limitations

    LADIES can maintain high accuracy with small sample sizes, and stochastic sampling can improve generalization over full-batch GCN.

  • Takeaways & Limitations

    The variance analysis is restricted to two-layer GCNs, and FastGCN cannot guarantee connectivity between sampled nodes across layers.

Abstract

from arXiv · show

Graph convolutional networks (GCNs) have recently received wide attentions, due to their successful applications in different graph tasks and different domains. Training GCNs for a large graph, however, is still a challenge. Original full-batch GCN training requires calculating the representation of all the nodes in the graph per GCN layer, which brings in high computation and memory costs. To alleviate this issue, several sampling-based methods have been proposed to train GCNs on a subset of nodes. Among them, the node-wise neighbor-sampling method recursively samples a fixed number of neighbor nodes, and thus its computation cost suffers from exponential growing neighbor size; while the layer-wise importance-sampling method discards the neighbor-dependent constraints, and thus the nodes sampled across layer suffer from sparse connection problem. To deal with the above two problems, we propose a new effective sampling algorithm called LAyer-Dependent ImportancE Sampling (LADIES). Based on the sampled nodes in the upper layer, LADIES selects their neighborhood nodes, constructs a bipartite subgraph and computes the importance probability accordingly. Then, it samples a fixed number of nodes by the calculated probability, and recursively conducts such procedure per layer to construct the whole computation graph. We prove theoretically and experimentally, that our proposed sampling algorithm outperforms the previous sampling methods in terms of both time and memory costs. Furthermore, LADIES is shown to have better generalization accuracy than original full-batch GCN, due to its stochastic nature.

1 Introduction

Training deep GCNs on large graphs is difficult because recursive neighborhood dependencies create exponential computation growth, while existing sampling methods trade off redundancy, sparse connectivity, and variance. LADIES addresses these issues with layer-dependent, neighbor-dependent importance sampling.

  • Motivation: Deep GCN training remains challenging because each node’s embedding recursively depends on neighbors across layers, causing exponential computation growth.This limits applications to large-scale social, recommender, and knowledge graphs.
  • Existing methods: Node-wise sampling reduces each aggregation’s cost but can still incur large total cost through recursive neighbor expansion.GraphSAGE uniformly samples a fixed number of neighbors for each node.
  • Existing methods: Layer-wise importance sampling reduces computation but independently samples nodes across layers, risking sparse connections between consecutive layers.FastGCN bases probabilities on node degree.
  • LADIES: LADIES combines layer-wise, neighbor-dependent, and importance sampling to avoid receptive-field expansion, preserve sampled-graph connectivity, and reduce variance.The paper presents these three properties as requirements for an ideal sampling method.
  • LADIES: LADIES samples neighbors of upper-layer nodes, computes importance probabilities, and recursively constructs a fixed-size bipartite computation graph per layer.The procedure is designed to retain neighborhood dependence while controlling sample size.
  • Contributions: The paper reports improved time and memory complexity, smaller variance, and superior benchmark performance for LADIES.It also reports high accuracy with 256 samples on a graph containing 233k nodes.

2 Background

Full-batch GCNs are costly on large dense graphs, while neighbor and independent layer-wise sampling introduce redundancy, receptive-field growth, or disconnected sampled layers. The background establishes LADIES as a complexity- and variance-oriented alternative.

  • Full-batch GCN: Full-batch training stores and aggregates embeddings for all nodes across layers, making memory and time costs expensive on large dense graphs.Updating parameters only once per epoch can also slow convergence.
  • Mini-batch training: Mini-batching labeled nodes reduces computation but still requires representations over a large receptive field because graph dependencies remain.Sampling output nodes alone does not remove the underlying dependency structure.
  • Node-wise sampling: GraphSAGE samples a fixed number of neighbors per node, but independent embedding calculations create redundant computation within the same layer.VR-GCN uses historical activations to reduce estimator variance, while retaining the neighbor-sampling strategy and its time complexity.
  • Layer-wise sampling: FastGCN samples a fixed number of nodes per layer using degree-based probabilities, reducing time and memory complexity through a smaller sampled adjacency matrix.Its sampling operation is conducted independently at each layer.
  • Layer-wise sampling: Independent layer-wise sampling cannot guarantee connectivity between sampled nodes at different layers, which incurs large variance in approximate embeddings.This is identified as FastGCN’s major limitation.
  • Complexity comparison: LADIES does not depend on total graph size or suffer exponential layer sensitivity, while requiring smaller samples than FastGCN for good performance.The paper therefore presents it as applicable to very deep and large GCNs.

3 LADIES: LAyer-Dependent ImportancE Sampling

LADIES addresses the inefficiencies of node-wise and independent layer-wise sampling by generating each layer’s samples from the neighborhoods of sampled upper-layer nodes and using importance probabilities. It constructs smaller, denser sampled computation graphs while retaining layer-dependent connectivity and normalizing modified Laplacians.

  • Motivation: LADIES targets exponential computation growth in node-wise sampling and sparse sampled graphs in independent layer-wise sampling.Node-wise methods recursively sample neighbors, whereas independent layer-wise sampling can produce sparse or all-zero inter-layer connections.
  • Independent Layer-wise Sampling: Independent layer-wise sampling approximates GCN aggregation by selecting a subset of previous-layer nodes and constructing a smaller sampled adjacency representation.The sampled matrices operate on sl and s(l−1) nodes, both much smaller than the full graph.
  • Layer-dependent Sampling: LADIES generates samples top-down from the union of neighbors of nodes sampled in the upper layer.At layer l−1, candidate nodes are restricted to V(l−1) = ∪vi∈Sl N(vi).
  • Importance Sampling: LADIES assigns importance probabilities within this neighborhood and samples a fixed number of nodes to reduce variance.The probabilities depend on Q(l) and P because the activation matrix H(l−1) is unavailable when samples are characterized.
  • Sampled Computation Graph: The sampled inter-layer operator is ˜P(l−1) = Q(l)PS(l−1)Q(l−1)⊤, computed using sparse matrix products.Restricting sampling to relevant neighbors gives more connections between consecutive sampled layers and a denser computation graph.
  • Normalization: LADIES normalizes modified Laplacian matrices because insufficient samples can otherwise produce very large maximum singular values when the network is deep.The normalization is introduced to maintain stable embedding scales and avoid exploding or vanishing gradients.

4 Experiments

Experiments compare LADIES with full-batch GCN, GraphSage, and FastGCN on node-classification datasets using accuracy, time, memory, and convergence. LADIES achieves strong accuracy with small samples and can generalize better than full-batch GCN on PubMed.

  • Experimental setup: Experiments evaluate 5-layer GCNs on Cora, Citeseer, Pubmed, and Reddit using accuracy, running time, memory, and convergence metrics.Training is repeated 10 times, and results use mean and variance at the convergence point.
  • Overall comparison: LADIES achieves the highest accuracy among the compared methods while using a small sampling number.The comparison includes full-batch GCN, GraphSage, and FastGCN.
  • Comparison with baselines: FastGCN may fail to converge well on larger graphs, whereas using 8192 sampled nodes on Reddit matches LADIES accuracy but costs more memory and time.GraphSage with five sampled nodes incurs substantially higher memory and time costs because of redundancy and uniform sampling.
  • Sampling size: LADIES can converge with sampling number 16, reaching F1-score = 77.6 with low time and memory cost on PubMed.The paper states that smaller sampling can further enhance LADIES beyond the sample numbers used for fair comparison.
  • Generalization: On PubMed, LADIES has higher validation and test F1-scores than full-batch GCN despite lower training-set F1-score.The authors attribute this to stochastic sampling mitigating graph noise and reducing overfitting to training data.

5 Conclusions

The paper presents LADIES for training deep and large GCNs. Its layer-dependent importance sampling is reported to improve computational costs, estimation variance, and test accuracy relative to existing methods.

  • Method: LADIES uses layer-dependent importance sampling to ensure a dense computation graph while avoiding drastic receptive-field expansion.The method is proposed for training deep and large GCNs.
  • Theory: Theoretically, LADIES has lower memory cost, time complexity, and estimation variance than existing GCN training methods including GraphSAGE and FastGCN.The conclusion summarizes the paper’s theoretical comparison with prior methods.
  • Results: Experiments report that LADIES achieves the best test accuracy with lower computational time and memory cost on benchmark datasets.This is the paper’s overall experimental conclusion.

A Complexity comparison between different algorithms

The complexity comparison separates embedding and weight storage from feature propagation and transformation. Layer-wise methods avoid dependence on the full graph size, while node-wise methods incur layer-dependent growth.

  • Components: Memory consists of intermediate embedding storage and weight-matrix storage, with the latter contributing O(LK^2) for all methods.The embedding-storage term varies by algorithm.
  • Full-batch GCN: Full-batch GCN requires O(L|V|K + LK^2) memory because it stores embeddings for all |V| nodes across L layers.Its feature propagation uses sparse-dense matrix multiplication.
  • Node-wise sampling: GraphSAGE has memory O(bKs_node^(L−1) + LK^2) and time growth involving s_node^L, reflecting recursive neighbor expansion.The per-batch propagation cost is O(bKs_node^L), while feature transformation adds a lower-order term.
  • Node-wise sampling: VR-GCN requires O(L|V|K + LK^2) memory because it stores historical activations, with time complexity matching GraphSAGE.Its storage requirement depends on all graph nodes and historical activations.
  • Layer-wise sampling: FastGCN has total memory O(LKs_layer + LK^2) and time O(LKs_layer^2 + LK^2), after discarding relatively small terms.Its layer-wise sampling stores sampled embeddings rather than embeddings for every graph node.
  • LADIES: LADIES has memory O(LKs_layer + LK^2) and time O(LKs_layer + LK^2_s_layer), matching FastGCN’s asymptotic complexity.The supplied passage states these are layer-wise sampling complexities.

B Variance comparison between different algorithms

The paper defines average embedding variance to compare layer-wise and node-wise sampling methods, then analyzes variance under assumptions on the Laplacian and activation-weight product.

  • Variance setup: Average variance measures the expected squared error between sampled and true intermediate embeddings for output-layer nodes.Layer-wise methods sample b_s hidden-layer nodes, whereas node-wise methods sample m neighbors per node.
  • FastGCN: FastGCN estimates variance with layer-independent importance probabilities based on node degrees and independent sampling matrices.The probabilities are p_i = ||P_*,i||_2 / ||P||_F.
  • GraphSAGE: GraphSAGE estimates each node embedding from m randomly sampled neighbors, with independent randomness across hidden and output layers.Its variance analysis assumes the sampling randomness at the two layers is independent.
  • VR-GCN: VR-GCN reduces the analyzed quantity by replacing activations H with the residual H − H̄ using a history activation matrix.The residual scale is summarized by Δφ = max_j ||(H_j,* − H̄_j,*)W||_2.
  • LADIES: LADIES defines the candidate set as the union of neighbors of sampled upper-layer nodes and uses a diagonal selector for that set.Its variance analysis relies on layer-dependent samples rather than independent output- and hidden-layer samples.

C Convergence Curves

On Pubmed, LADIES converges well with a sampling number of 8, while FastGCN with 512 samples fails to converge in the authors’ previous experiments.

  • Training curves: 8 samples already yield good convergence for LADIES on Pubmed.The training curve is reported for different sampling numbers.
  • Training curves: 512 samples are insufficient for FastGCN to converge in the authors’ previous experiments.The comparison is stated alongside LADIES’ convergence behavior on Pubmed.
  • Convergence comparison: LADIES achieves more robust convergence than FastGCN with fewer samples and less time.This conclusion is reported from the Pubmed convergence curves.

D Differences with FastGCN

LADIES differs from FastGCN by restricting candidates to upper-layer neighborhoods and deriving novel layer-dependent importance probabilities.

  • Candidate restriction: LADIES restricts candidate nodes to the union of neighborhoods of sampled upper-layer nodes, producing a denser sampled adjacency matrix than FastGCN.This restriction preserves neighbor dependence across consecutive layers.
  • Importance probabilities: LADIES uses layer-dependent sampling probabilities derived by optimizing the theoretical variance-related formulation.The paper identifies these probabilities as novel relative to FastGCN.
Loading 1911.07323v1…