Source-linked AI summary
Adaptive Sampling Towards Fast Graph Representation Learning
Wenbing Huang, Tong Zhang, Yu Rong, Junzhou Huang
TL;DR
Large-scale GCN training is limited by the computation and memory required by expanding neighborhoods across layers. The paper introduces adaptive layer-wise sampling with explicit variance reduction and skip connections, and reports stronger effectiveness, accuracy, and convergence than sampling-based counterparts.
Problem
Large-scale GCN training is computationally intensive and memory-consuming because feed-forward propagation requires full neighborhood expansion across layers.
Method
The paper builds GCN layers top-down with conditional layer-wise sampling, explicitly reduces sampling variance, and adds skip connections for second-order proximity.
Results
The method outperforms GraphSAGE and FastGCN in effectiveness and accuracy, while skip connections further improve convergence speed and eventual classification accuracy.
Takeaways & Limitations
Adaptive layer-wise sampling provides controllable, shared neighborhoods for faster GCN training, while skip connections extend message passing to distant nodes.
Takeaways & Limitations
Variance reduction penalizes only top-layer variance for efficiency, although other hidden-layer activations remain stochastic.
Abstract
from arXiv · showhide
Graph Convolutional Networks (GCNs) have become a crucial tool on learning representations of graph vertices. The main challenge of adapting GCNs on large-scale graphs is the scalability issue that it incurs heavy cost both in computation and memory due to the uncontrollable neighborhood expansion across layers. In this paper, we accelerate the training of GCNs through developing an adaptive layer-wise sampling method. By constructing the network layer by layer in a top-down passway, we sample the lower layer conditioned on the top one, where the sampled neighborhoods are shared by different parent nodes and the over expansion is avoided owing to the fixed-size sampling. More importantly, the proposed sampler is adaptive and applicable for explicit variance reduction, which in turn enhances the training of our method. Furthermore, we propose a novel and economical approach to promote the message passing over distant nodes by applying skip connections. Intensive experiments on several benchmarks verify the effectiveness of our method regarding the classification accuracy while enjoying faster convergence speed.
1 Introduction
GCNs provide strong graph-vertex representations, but neighborhood expansion makes large-scale training computationally and memory intensive. The paper addresses this with adaptive layer-wise sampling, explicit variance reduction, and skip connections for distant message passing.
- GCNs aggregate graph-vertex features and have achieved state-of-the-art node-classification performance.
- Neighborhood expansion across layers creates prohibitive computation and memory costs, even for small mini-batches.
- Layer-wise sampling builds the network top-down, conditionally samples lower layers, shares neighborhoods across parents, and controls layer size.
- The adaptive sampler approximates an otherwise uncomputable variance-minimizing distribution and explicitly reduces variance through training.
- Skip connections between layers l+1 and l−1 reuse nodes as 2-hop neighborhoods, preserving second-order proximity without extra computations.
- Experiments on Cora, Citeseer, Pubmed, and Reddit report improved classification accuracy and convergence speed.
2 Related Work
Graph convolution research spans spectral and non-spectral approaches, attention and patch-based models, and sampling methods for efficient graph representation learning. This paper differs from GraphSAGE and FastGCN through conditional layer-wise sampling that shares neighborhoods and captures between-layer connections.
- Spectral graph convolutions define filtering in the Fourier domain and later use localized spectral filters or Chebyshev expansions.
- Non-spectral methods define graph convolution directly from spatial connections, including degree-specific weights, multi-hop transition powers, and fixed-size neighborhoods.
- Patch and self-attention approaches assign different importance weights to nodes within a neighborhood, increasing model capacity.
- GraphSAGE samples neighborhoods node-wise, whereas FastGCN samples each layer independently from an identical distribution.
- The proposed layer-wise strategy samples lower layers conditioned on upper ones, enabling neighborhood sharing and capturing between-layer correlations.
3 Notations and Preliminaries
The paper represents an undirected graph with nodes, weighted adjacency, and node features, then defines GCN hidden states through normalized neighborhood aggregation and learned layer filters.
- The graph is modeled as G=(V,E), with nodes vi, edges (vi,vj), and N denoting the number of nodes.
- The adjacency matrix A stores edge weights, while X stores D-dimensional node features xi.
- GCN hidden features h^(l)(vi) are propagated layer by layer using a re-normalized adjacency matrix, nonlinear activation, and filter matrix W^(l).
4 Adaptive Sampling
Adaptive sampling replaces full neighborhood expansion with fixed-size, shared layer-wise sampling, reducing computation while supporting explicit variance reduction. The method approximates an infeasible optimal sampler, learns a self-dependent sampling function, and incorporates variance into training.
- GCN feed-forward computation becomes costly because neighborhoods expand recursively across layers, producing substantial computation and memory demands.
- Monte-Carlo sampling reduces complexity from O(|E|D(l)D(l−1)) to O(n^2D(l)D(l−1)) when n ≪ N and both sampled layers contain n points.
- Layer-wise sampling constructs layers top-down, samples lower-layer nodes conditioned on the current layer, and shares those sampled nodes across all current-layer parents.
- The fixed size n per layer makes total sampling nodes grow linearly with network depth, unlike node-wise sampling whose input-layer count can grow as O(n^d).
- Because the variance-minimizing sampler is infeasible, the method substitutes a self-dependent node-feature function and explicitly minimizes variance through a hybrid classification-and-variance loss.
- The hybrid loss penalizes only top-layer variance for efficient computation, with λ fixed at 0.5 in the experiments.
5 Preserving Second-Order Proximities by Skip Connections
The method uses skip connections to pass messages across two layers and preserve second-order proximity without separately sampling 2-hop neighborhoods. This design differs from ResNet skip connections, which target accuracy through increased depth.
- The GCN update normally aggregates only 1-hop neighborhoods, while random-walk-based multi-hop sampling adds computational cost, especially on dense graphs.
- A skip connection from layer l−1 to layer l+1 reuses l−1 nodes as 2-hop neighborhoods, combining 1-hop and 2-hop aggregation.
- The skip connection preserves second-order proximity without extra 2-hop sampling and supports information transfer between distant layers for back-propagation and training.
- Unlike ResNet identity mappings used to gain accuracy by increasing depth, this model derives the skip calculation specifically to preserve second-order proximity.
6 Discussions and Extensions
The paper positions its layer-wise sampler as a general framework that differs from GraphSAGE and FastGCN through conditional, trainable sampling. It also discusses why standard GAT-style attention is impracticable and motivates a self-dependent alternative.
- Relation to other sampling methods: GraphSAGE samples fixed-size neighborhoods node by node, whereas FastGCN constructs layers independently and the proposed method conditions lower-layer sampling on upper-layer nodes.Conditional sampling captures between-layer correlations.
- Relation to other sampling methods: Both GraphSAGE and FastGCN can be viewed as specific variants of the paper’s broader sampling framework.GraphSAGE corresponds to a uniform node-wise sampler, while FastGCN uses a node-independent layer-wise sampler.
- Relation to other sampling methods: Unlike GraphSAGE and FastGCN, the proposed sampler is parameterized and trainable for explicit variance reduction.It modifies the optimal importance-sampling distribution with a self-dependent function and fine-tunes the network and sampler.
- Taking the attention into account: Directly applying GAT-like attention is impracticable because sampling probabilities would depend on lower-layer hidden features unavailable before sampling.The paper therefore develops a self-dependent attention mechanism instead.
- Taking the attention into account: The attention mechanism uses learnable parameters W1 and W2.These parameters define the self-dependent attention computation described after the limitation of direct GAT-like attention.
7 Experiments
Experiments evaluate the method on citation and social-network benchmarks using multiple baselines and ablations. The results report faster convergence, lower training cost than full or node-wise alternatives, strong accuracy, and benefits from variance reduction and skip connections.
- Experimental setup: The benchmarks cover citation networks Cora, Citeseer, and Pubmed plus Reddit, spanning graphs from O(10^3) to more than 10^5 vertices.The experiments use academic-paper classification and Reddit community prediction.
- Experimental setup: The experiments separate test data from training and use the full GCN architecture to compute embeddings for new test nodes.The framework is described as inductive, with sampling used as an alternative for testing.
- Comparisons with other sampling methods: Adapt converges faster than other sampling methods on Cora, Citeseer, and Reddit, with more stable curves than IID sampling.It even outperforms the Full model on Cora and Reddit in the reported convergence comparisons.
- Training efficiency: All sampling methods run faster per epoch than the Full model, while Adapt is faster than Node-Wise because its architecture is more compact.Node-Wise uses layer sizes 25n, 5n, and n, whereas Adapt uses n nodes in all layers.
- Ablation studies: Removing variance reduction decreases Adapt’s accuracy on Cora and Reddit, while its effect on Citeseer is not significant.The paper conjectures that Citeseer’s lower average degree limits neighborhood diversity.
- Comparisons with state-of-the-art methods: Across the reported benchmark comparisons, Adapt achieves the best performance among the evaluated methods, while removing variance reduction especially lowers performance on Cora and Reddit.The comparison includes KLED, DCN, GraphSAGE, and FastGCN results.
- Skip-connection evaluation: Adding a skip connection significantly speeds convergence on Cora, reducing the required epochs from around 150 to 100.Its final-accuracy improvement is described as not large, while repeated-trial results show a slight performance improvement.
- Skip-connection evaluation: Explicit 2-hop sampling further boosts classification accuracy, whereas skip connections are slightly less accurate but avoid computing the 2-order adjacency expansion.The skip-connection approach is therefore more computationally beneficial for large and dense graphs.
8 Conclusion
The paper concludes that adaptive layer-wise sampling accelerates GCN training and outperforms sampling-based counterparts in reported effectiveness and accuracy. Skip connections preserve second-order proximity while improving convergence speed and eventual classification accuracy.
- Conclusion: The framework accelerates GCN training by constructing the network layer by layer with an adaptive sampler for variance reduction.The sampler shares between-layer information and controls the number of sampled nodes.
- Conclusion: The method outperforms GraphSAGE and FastGCN in effectiveness and accuracy across extensive experiments.The conclusion characterizes these as sampling-based counterparts.
- Conclusion: Skip connections preserve second-order proximity and further enhance convergence speed and eventual classification accuracy.The conclusion presents this as an additional benefit of the proposed framework.
Appendix
The supplementary material provides sampler-gradient calculations and additional experimental details and results.
- Appendix: The appendix derives the gradient of the loss function in Eq. (10) with respect to the sampler.It also includes more experimental settings and results.
9 Gradient Calculation
The gradient analysis shows that the expectation and classification-loss terms have zero gradient with respect to the sampler, while the variance term requires an explicit sampled estimate and gradient calculation.
- The gradient of the expectation ˆµq(vi) with respect to sampler q(uj) is zero.
- The classification loss likewise has zero gradient with respect to the sampler.
- The variance term is first estimated using sampled instances before its gradient is calculated.
- The sampled instances are generated independently from q(uj).
10 More Experimental Evaluations
Additional evaluations report accuracy curves across several datasets and show that skip connections can improve convergence, with dataset-dependent effects during training.
- Figure 4 reports test-data accuracy curves on Cora, Citeseer, and Reddit, with one epoch defined as a complete pass through all training samples.
- The hidden-layer sampling-node counts for Cora, Citeseer, Pubmed, and Reddit are 128, 128, 256, and 512, respectively.
- On Pubmed, the proposed method consistently outperforms IID and Node-Wise counterparts, while its performance remains more stable toward the end of training.The Full model reaches its best accuracy around the 30-th epoch but drops after the 60-th epoch due to overfitting.
- Skip connections speed convergence on Citeseer but improve Pubmed performance only during early training epochs.
- Skip connections cannot be applied to Reddit because its bottom layer is fixed and its output features are pre-computed.