M4-088M4: Sequences & TransformersGraph Neural Networks (GNN / GAT)Easy
⚡Flashcard Drill➔Mastery:
Comparison of Graph Convolutional Networks: GCN, GraphSAGE, and GAT
🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
📐 Mathematical Definition
⚡ One-Sentence Core Answer
GCN uses fixed symmetric degree normalization, GraphSAGE introduces mini-batch neighborhood sampling with flexible aggregators, and GAT dynamically learns anisotropic attention weights across neighboring edges.
📌 Key Takeaways
- •GCN (Kipf & Welling): full-graph transductive spectral approximation; uses fixed normalized adjacency , computationally rigid and vulnerable to degree variations
- •GraphSAGE (Hamilton et al.): inductive mini-batch training; samples fixed-size neighbor sets and supports general aggregators (Mean, LSTM, Pooling)
- •GAT (Veličković et al.): spatial self-attention; dynamically assigns learned attention coefficients to neighbors, handling heterogeneous edge importance
📐 Mathematical Derivations
Mathematical Mechanism: 1. GCN (Graph Convolutional Network): First-order Chebyshev spectral approximation: Matrix form: , where and . Weights are static, isotropic, and depend solely on node degrees. 2. GraphSAGE: Samples a uniform subset of fixed size : Enables mini-batch SGD and inductive generalization to unseen nodes. 3. GAT (Graph Attention Network): Computes anisotropic attention coefficients via LeakyReLU: Updates representations using multi-head attention: .
🏭 Production Trade-offs
Deep Dive & Engineering Trade-offs: ① Scalability & Inductive Generalization: GCN requires loading the full graph adjacency matrix into VRAM, making it transductive and impractical for billion-scale web graphs. GraphSAGE enables inductive mini-batch training by bounding neighborhood size (e.g., sampling 25 neighbors at hop 1, 10 at hop 2), becoming the industry standard for production recommender systems. ② Computational Complexity: GCN is fastest ( sparse matrix multiply); GAT has highest latency and memory footprint () due to dynamic attention score computation and softmax over neighbor sets. ③ Static vs Dynamic Weights: GCN treats all neighbors equally weighted by degree; GAT assigns high attention to informative neighbors while ignoring noisy edges, performing superiorly on noisy citation networks. ④ Neighbor Explosion: GraphSAGE's fixed-size neighbor sampling addresses the exponential neighborhood expansion problem () inherent in multi-hop training. ⑤ Interview Strategy: Structure the comparison across three axes: normalization mechanism (degree vs attention), training regime (full-graph transductive vs sampled mini-batch inductive), and computational complexity.
⚠️ Common Interview Pitfalls
- ✕Attempting to train full-graph GCN on massive industrial graphs with millions of nodes without partitioning
- ✕Assuming GAT is always superior (on simple homophilic graphs, GCN/GraphSAGE achieve identical accuracy with less compute)
- ✕Confusing GraphSAGE's inductive sampling with simple node dropout
🎯 Interviewer Follow-up Inquiries
- ?Why is GCN strictly transductive in its original formulation while GraphSAGE is inductive?
- ?What causes the neighborhood expansion problem when scaling GNNs to 3 or more hops?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
📚