Unit 5.7 · about 2 h
206 / 324Graph message passing and oversmoothing
Graphs make neighborhoods explicit. Each layer trades local identity for wider context, and past a point the averaging erases what made nodes distinct.
- explain
You can now
- Explain one message-passing step as neighborhood aggregation plus update.
- State permutation equivariance for layers and invariance for readouts, and test it.
- Recognize oversmoothing and name the random-walk averaging behind it.
Covers
- Graph message passing, permutation behavior and oversmoothing recognition
Study, in this order
4 steps
- Graphs and adjacency powersUnderstanding Deep Learning - representation foundations
Sections 13.1-13.2 (pp. 241-244): node and edge matrices; entry \((m, n)\) of \(A^L\) counts length-\(L\) walks; Figures 13.3-13.4
- Tasks and equivariant layersUnderstanding Deep Learning - representation foundations
Sections 13.3-13.4.1 (pp. 245-250): graph and node tasks; layers must be permutation-equivariant; Figure 13.7 aggregate-then-update
- Why deep GNNs stallUnderstanding Deep Learning - representation foundations
Notes to Chapter 13, Oversmoothing and suspended animation (pp. 265-266): two-layer norm, random-walk stationary washout, over-squashing, residuals for depth
- Graph encoding notebookUnderstanding Deep Learning - representation foundations
Notebook 13.1, Graph Representation: adjacency and embedding encodings
Depth · Open only if the \(A^L\) walk counting in Section 13.2 is unclear.
Focus on
- \(A^L\) counts walks, not paths: revisits allowed. The diagonal of \(A^2\) holds node degrees.
- Correct layers are permutation-equivariant: permuting node order permutes embeddings identically. Readouts for graph labels must be invariant.
- Repeated averaging converges toward the random-walk stationary distribution, so deep stacks wash out local signal.
- Two layers are the empirical norm: the original GCN and GraphSAGE both use two. Depth needs residual connections or similar fixes, not more of the same layer.
Reproduce closed-book
Traps
- Counting paths with \(A^L\). Walks may revisit nodes; the book states this explicitly.
- Expecting depth to help by default. Mean aggregation converges across nodes, so a 10-layer stack can underperform a 2-layer one.
- Indexing nodes as an ordered input. If shuffling IDs changes predictions beyond permutation, the layer is wrong, not the data.
Practice
UDL Chapter 13 problems: graphs, walks and equivariance
Problems 13.1, 13.3, 13.5 and 13.7 (pp. 266-267): adjacency matrices, walk counts, the responsible permutation matrix, and the equivariance proof for the simple layer.
Self-test
-
Path 1-2-3: length-2 walks from 1 to 3, and from 2 to 2?
One (1-2-3) and two (2-1-2, 2-3-2), matching the \(A^2\) entries 1 and 2. -
What must a permutation of node order do to layer outputs?
Permute them identically (equivariance); a graph-level readout must stay unchanged (invariance). -
All node embeddings look identical after six layers. Diagnose and name the mechanism.
Oversmoothing from repeated neighborhood averaging toward the stationary distribution. Confirm per-layer cross-node spread, then cut depth or add residuals. -
Why do the original GCN and GraphSAGE use two layers?
Two hops already mix neighborhoods; deeper stacks wash out local information faster than they add useful context, per the Notes.
Completion criterion
Stop when
You solve Problems 13.1, 13.3, 13.5 and 13.7 without notes, and on a small graph you can show cross-node spread shrinking with depth under repeated mean aggregation.
Mark passed, then open 6.1 Only mark this when you can do it without notes.Leads to
- 4.3 Equivariance, residual CNN blocks and resolution cost Compare graph permutation equivariance with translation equivariance, and residual paths that allow depth.
- 3.2 Dead, saturated and exploding units, and residual paths Track embedding health across layers the way you track activations across depth.
Resources for this unit
- Understanding Deep Learning - representation foundations Use 9.3.6-9.3.7 for transfer and self-supervision, 12.9-12.10 for image transformers, and 13.1-13.4 plus 13.10 for GNN vocabulary. Open notebooks 9.4, 12.4 and 13.1 only when a figure or mechanism is unclear.
Also in this section
- D2L - Vision Transformer Use vision-transformer.md for patch extraction, patch embeddings and a tested small encoder. Add a compact SimCLR-style or paired-data contrastive objective in the explicit training loop from Sections 2 and 3.
- Stanford CS231n - transformer and self-supervised assignment slice Use only the Assignment 3 components for transformers, self-supervised learning, CLIP or DINO that directly test representation and pairing. Keep the controlled local evaluator as the gate.
- TensorTonic - patchify and symmetric CLIP loss Solve only Patchify a Batch of Images and Implement Symmetric CLIP Contrastive Loss. Transfer both into the controlled experiment and preserve local leakage and collapse tests.
- Deep-ML candidate - InfoNCE Loss If the platform admission check passes, use problem 384 once after deriving the objective. Add local tests for temperature extremes, missing positives, duplicate pairs and normalized versus unnormalized embeddings.
- SimCLR - A Simple Framework for Contrastive Learning of Visual Representations Use Section 2.1 Eq. (1) and Algorithm 1 for NT-Xent, 2.3 for the linear-evaluation protocol, 3.1 with Figures 5-6 for augmentation composition and shortcuts, 4.2 for the projection head, and 5.1-5.2 with Table 5 and Figure 9 for temperature and batch-size effects.
- CLIP - Learning Transferable Visual Models From Natural Language Supervision Use Section 2.3 for the symmetric image-text objective and learned temperature, 2.5 for batch size and temperature limits, and 3.1.2 with 3.1.4 for zero-shot transfer and prompt ensembling.
- SimSiam - Exploring Simple Siamese Representation Learning Use Figure 2 and Table 1 for collapse under removed stop-gradient or predictor, including the per-channel spread diagnostic.