GraphSAGE: Sampling and Aggregation
What you'll learn: How GraphSAGE enables scalable, inductive learning on massive graphs through smart neighborhood sampling and flexible aggregation strategies.
The Scalability Challenge
Graph Convolutional Networks (GCN) require computing embeddings for all nodes simultaneously using the full adjacency matrix. This becomes impractical for graphs with millions of nodes—you'd run out of memory fast! GraphSAGE (Graph SAmple and aggreGATE) solves this by learning to generate embeddings for unseen nodes through localized sampling.
Neighborhood Sampling
Instead of aggregating information from every neighbor (which could be thousands), GraphSAGE samples a fixed-size subset of neighbors at each layer. Think of it like polling: you don't need to survey everyone in a city to understand local opinions—a representative sample suffices.
For example, you might sample 10 neighbors in the first layer, then 5 neighbors of each sampled node in the second layer. This bounds computational cost regardless of node degree, making training scalable.
Aggregation Functions
GraphSAGE introduces learnable aggregation functions beyond simple mean pooling:
- Mean aggregator: Average neighbor features (similar to GCN)
- LSTM aggregator: Process neighbors as a sequence
- Max-pooling aggregator: Element-wise max after a transformation
The general formula combines your current features with aggregated neighbor information:
h_v^(k) = σ(W · CONCAT(h_v^(k-1), AGG({h_u^(k-1) : u ∈ Sample(N(v))})))
Inductive Learning Power
Because GraphSAGE learns how to aggregate rather than memorizing fixed embeddings, it can generate representations for brand-new nodes never seen during training—as long as they have features and connections.
Key Takeaway: GraphSAGE achieves scalable, inductive graph learning by sampling fixed-size neighborhoods and learning flexible aggregation functions, enabling efficient training on massive graphs and generalization to new nodes.