DL0191 GCN, GraphSAGE, and GAT

All three layers do the same thing at a high level: build a new vector for node as a weighted combination of its neighbors’ vectors, then apply a linear map and a nonlinearity. The real difference is where the mixing coefficient comes from and how the neighborhood is enumerated. GCN fixes the coefficient from the graph alone as symmetric degree normalization , applied to the full neighborhood in one sparse matrix product over the entire graph. GraphSAGE replaces the full neighborhood with a fixed-size random sample and a permutation-invariant aggregator (mean, max-pool, or LSTM), and keeps the node’s own vector in a separate concatenated slot instead of averaging it away. GAT makes the coefficient content-dependent: a small shared scoring vector reads both endpoint features, a softmax over each node’s neighborhood turns those scores into weights , and several attention heads are run in parallel. Transductive versus inductive is then mostly a property of the training procedure and of what the coefficients depend on, not of the layer equation itself.

(1) GCN Weights Are Structural And Frozen: depends only on the two degrees, so a high-degree hub is deliberately down-weighted and no coefficient is ever learned. This is a strong, cheap prior when features are weak and the graph is homophilous.
(2) GraphSAGE Weights Are Uniform Over A Sample: the mean aggregator gives every sampled neighbor , and the sample size is the knob that bounds compute rather than the node’s true degree.
(3) Self Vector Handling Differs: GCN and GAT fold the node into the same sum through a self-loop, while GraphSAGE concatenates it and gives it its own block of the weight matrix, which preserves the node’s own signal at depth.
(4) GAT Weights Are Learned From Features: can vary across edges of identical degree, which is what lets the layer ignore a noisy neighbor. The price is stored coefficients and gradients flowing through the attention scores.
(5) Transductive Is A Training Choice, Not A Law: the published GCN is trained full-batch on a single normalized adjacency, so a new node changes degrees and the normalization; GraphSAGE was designed minibatch-first so the same weights run on an unseen node by sampling its fan-out.
(6) Depth Costs Differently: full-neighborhood expansion grows as roughly per target node, while sampling caps it at at the cost of estimator variance.

Figure 1: One neighborhood, three weighting rules. GCN reads its coefficients off the degrees, so the sparsest neighbor A gets the largest share and the hub D the smallest. GraphSAGE throws away two neighbors and splits the mass uniformly over what survives, keeping the self vector in a separate concatenated slot. GAT lets features decide, so neighbor B dominates with despite having a middling degree.

Mathematical Formulation:

Where:

• is the incoming representation of node and the layer output; is the elementwise nonlinearity and the shared linear map.
• is the neighborhood including the self-loop, and is the corresponding degree, so is the fixed GCN coefficient that never changes during training.
• is the sampled fan-out of fixed size at layer , and is a permutation-invariant reducer (mean, elementwise max over an MLP, or LSTM over a shuffled order).
• is concatenation, so the GraphSAGE weight matrix has shape and the node’s own features get an independent parameter block.
• is the shared attention vector and the raw score; the softmax is taken over so that per node.
• GAT runs heads whose outputs are concatenated in hidden layers and averaged in the output layer, multiplying both parameter count and stored coefficients by .

The cost picture follows directly. A full-batch GCN layer is and needs the whole feature matrix plus every layer’s activations resident, which is why it stops fitting long before the graph itself does. GAT adds scores and their gradients on top of the same sparse pattern, so its memory is edge-bound rather than node-bound. GraphSAGE instead bounds a minibatch: with batch size and fan-outs , the computation graph holds a number of node instances that is completely independent of . That is the property that makes web-scale graph learning practical, and it is the mechanism behind Pinterest’s PinSage, which trains on a graph of billions of nodes by expanding only short sampled neighborhoods per target.

Minibatch Fan-Out Budget:

Figure 2: Depth is what makes full-neighborhood aggregation intractable. On a graph with average degree 100, a 3-hop receptive field already touches about a million node instances per target and a 4-hop field exceeds the graph size, meaning most of the graph is re-visited for a single prediction. A fixed fan-out of 25 then 10 keeps the same depth at roughly 2,800 instances, trading exactness for a cost that no longer depends on .