Spatial & Message-Passing GCNs

GraphSAGE, neighbor sampling, aggregators, inductive learning, scalability

Pinterest has 3 billion pins and 18 billion edges. New pins arrive every day. A spectral GCN requires the full adjacency matrix during training — it learns embeddings tied to the specific graph. Add a new pin and the model cannot embed it without retraining from scratch. At Pinterest's scale, that is not a deployment model.

GraphSAGE reframes the problem. Instead of learning fixed embeddings for each node, it learns aggregation functions — parameterized operations that map any neighborhood to an embedding. The same learned function applies to nodes never seen during training. Give it a new pin's features and its neighbors' features, run the aggregation, and you get an embedding in milliseconds. No retraining. This inductivity — generalizing to new nodes without retraining — is the architectural property that makes billion-scale GNN deployment possible.

The second key problem is neighborhood explosion. A 2-layer GNN on a node with 100 average-degree neighbors requires 100 first-hop neighbors and up to 10,000 second-hop neighbors. A 3-layer GNN requires up to 1 million. GraphSAGE samples a fixed number of neighbors at each hop — 25 at hop 1, 10 at hop 2 — capping computation at 250 nodes per target node regardless of actual degree. This bounded fan-out is what makes mini-batch training tractable.

The aggregation function choice matters. Mean aggregation treats all neighbors equally. Max-pooling picks the most activated feature across neighbors — useful when a few neighbors carry strong signal and the rest are noise. LSTM aggregation has higher capacity but breaks permutation invariance, which is a theoretical violation for graph learning.

NOT this. "GraphSAGE requires full-batch training." GraphSAGE was specifically designed for mini-batch training by sampling a fixed number of neighbors at each hop. Full-batch GCN requires the entire adjacency matrix in memory — infeasible for graphs with billions of nodes. GraphSAGE's fixed fan-out sampling is the mechanism that enables mini-batch training: a batch of 512 target nodes with sample sizes [25, 10] requires loading at most 512 + 12,800 + 128,000 = 141,312 nodes from the feature store, regardless of graph size. The architecture is designed around this constraint.

Key points

• GraphSAGE algorithm: for each node v, (1) sample a fixed-size neighborhood N(v) from the full neighbor set, (2) aggregate sampled neighbor features h_N(v) = AGGREGATE({h_u : u ∈ N(v)}), (3) concatenate ego + aggregated h_v = σ(W · CONCAT(h_v, h_N(v))). Repeat for K layers. After K layers, each node's embedding encodes its K-hop neighborhood. The same W and aggregation function apply to every node at every layer — generalization is structural, not node-specific.
• Neighbor sampling controls the otherwise exponential neighborhood expansion. Without sampling, a K-layer GNN on a node with 100 average-degree neighbors requires 100 1-hop, 10,000 2-hop, and 1M 3-hop neighbors. GraphSAGE samples a fixed |S_1| neighbors at hop 1, |S_2| at hop 2 — bounded computation per node. Sample sizes [25, 10] cap the computation at 250 nodes per target node for a 2-layer embedding, regardless of actual node degree.
• Mean aggregator: h_N(v) = σ(W · MEAN({h_u : u ∈ N(v) ∪ {v}})). Equivalent to GCN's normalized aggregation without self-loops. Simple and effective, but treats all neighbors equally. Concatenating the ego embedding (CONCAT(ego, MEAN(neighbors))) rather than replacing it with the mean outperforms pure mean by preserving the central node's own identity — a node in a neighborhood of high-degree hubs has different properties than the hubs themselves.
• LSTM aggregator: applies an LSTM to a random permutation of neighbor features. Empirically outperforms mean on some tasks despite being theoretically incorrect — LSTM is not permutation invariant, so different random orderings at inference give different embeddings. The LSTM may be exploiting a useful but spurious signal from node ID-based orderings. Use max-pooling if you want both good empirical performance and the theoretical correctness required by GNN theory.
• Max-pooling aggregator: h_N(v) = max({σ(W_pool · h_u + b) : u ∈ N(v)}). Applies elementwise max after a learned transformation. Captures the most activated feature across neighbors — useful when some neighbors are highly informative and most are noise. Often the best performer for node classification on heterophilic graphs where the most anomalous neighbor, not the average neighbor, carries the signal.
• Inductivity is the architectural insight that separates GraphSAGE from prior methods. Spectral GCN is trained with the full graph adjacency — its weights are tied to the specific graph via spectral filtering. GraphSAGE learns aggregation functions that map neighborhood features to embeddings — the same function applies to any neighborhood. New nodes: sample their neighbors, run the K-layer aggregation with trained weights, get an embedding in milliseconds. No retraining, no graph reconstruction.
• PinSage (Pinterest) is the reference production implementation: random-walk-based neighborhood sampling instead of uniform sampling (nodes visited more frequently in random walks from v are higher-weight neighbors); feature store (Redis/RocksDB) and graph store (adjacency lists) as separate systems; offline embedding computation via MapReduce; online serving via approximate nearest neighbor (FAISS/ScaNN). The architecture — not the GNN itself — is what makes 3B-pin scale feasible.
• Mini-batch training computation: for a batch of target nodes, expand neighborhoods layer by layer. For K=2 with sample sizes [25, 10]: a batch of 512 target nodes requires ~512×25 = 12,800 1-hop nodes and ~12,800×10 = 128,000 2-hop nodes. These nodes are fetched from a feature store, with neighborhood structure from a graph database. The feature lookup latency, not the GNN forward pass, dominates total training time at scale.

Recap

• GraphSAGE learns an aggregation function, not fixed embeddings — same function embeds unseen nodes in ms, no retraining.
• Inductivity is the point: new pins arrive daily; spectral GCN needs full-graph retrain, GraphSAGE doesn't.
• Neighbor explosion: deg-100, K=3 → up to 1M nodes. Fixed fan-out [25,10] caps at 250/target.
• Algorithm: sample $N(v)$ → aggregate → concat ego + neighbors → repeat K layers.
• Aggregators: mean (equal weight), max-pool (strongest neighbor), LSTM (higher capacity but breaks permutation invariance).
• Concat ego, don't replace with mean — preserves the central node's identity vs its hubs.
• PinSage = production reference: random-walk sampling, separate feature/graph stores, MapReduce offline embeddings, ANN serving.

Check your understanding