🌏 中文版
Video status: Recordings require sign-in or course authorization. Source details
This is Lecture 6 of Stanford CS224W: Machine Learning with Graphs, Fall 2025, dated 2025-10-09. It follows the course schedule and official slides; the slides credit Jure Leskovec, Charilaos Kanatsoulis, and the course team.
Materials and gaps
Public materials include the slides and optional readings listed on the schedule. Canvas video, live Q&A, board work, and Ed discussions are unavailable, so this article does not reconstruct them. The public 2021 videos are not evidence for a 2025 lecture.
Complete lecture agenda
1. What distinguishability means
The theoretical question is not merely whether a model fits, but whether two different local structures must receive the same representation. Once they collapse to one vector, no downstream prediction head can recover the distinction.
2. The Weisfeiler–Lehman test
The one-dimensional WL test repeatedly hashes a node's current color together with the multiset of neighbor colors. Different color histograms certify different graphs, but matching histograms do not prove isomorphism.
3. An upper bound for message passing
Standard message-passing GNNs are no more discriminative than one-dimensional WL. A non-injective aggregator can be strictly weaker: mean loses multiplicity, while max discards most frequency information.
4. GIN and injective aggregation
GIN combines sum aggregation with an MLP to approximate an injective map over bounded multisets. It approaches the theoretical ceiling but does not distinguish graphs that WL itself cannot separate.
5. Over-smoothing and depth limits
More layers expand the receptive field but can also make node states increasingly similar. Track validation metrics and distances between node embeddings rather than assuming deeper is always stronger.
Deep theory agenda
The distinguishability problem
For a node encoder, expressivity asks whether distinct rooted neighborhoods map to distinct representations; for a graph encoder, it asks whether node encoding plus readout separates distinct graphs. This is not simply a question of parameter count. If the first aggregation maps two different multisets to the same value, no deeper MLP can recover the discarded multiplicity or structure.
Graph isomorphism and WL
Graphs that differ only by a node permutation are isomorphic and should receive the same graph-classification output. Exhaustively checking all (n!) permutations is impractical. WL color refinement is efficient but incomplete: initialize node colors, then repeatedly encode each node's own color and the multiset of neighbor colors. Different color histograms prove the graphs differ; equal histograms mean only that WL failed to separate them, not that they are isomorphic.
Aligning WL with message passing
A message-passing layer likewise maps a center state and neighbor multiset to a new state. With identical initial features and identical incoming multisets at every round, a shared update produces identical embeddings. Thus ordinary neighborhood aggregation has a one-dimensional-WL upper bound, and a non-injective aggregator can be weaker still.
What mean and max discard
Mean cannot distinguish multisets with the same proportions but different sizes—for example, one neighbor from two identical copies. Max retains only the largest value in each coordinate, losing multiplicity and every non-maximal element. Sum has a better chance of retaining counts on bounded multisets when paired with a suitable element mapping, but it is not automatically injective without that transform.
The GIN update
GIN sums neighbor states, adds the center state scaled by (1+\epsilon), and applies an MLP. Epsilon may be fixed or learned so that the center remains distinguishable from its neighbors. The goal is an approximately injective multiset update that reaches the one-dimensional-WL ceiling—not a solution for regular graphs or other pairs that WL cannot distinguish.
Graph readout
Node-level power does not automatically become graph-level power. Mean readout may collapse graphs of different sizes that share a node-state distribution, whereas sum can retain counts. GIN commonly combines node summaries from several layers because each layer represents a different hop scale. The encoder, chosen layers, and readout jointly determine graph distinguishability.
Over-smoothing
Repeated propagation can make node states converge until mostly low-frequency graph signal remains. This training and representation dynamic differs from a WL expressivity bound: an architecture may be able to separate two inputs in principle while its trained embeddings fail to preserve the difference. Useful diagnostics include pairwise cosine similarity, class separation, and depth ablations, not training loss alone.
Over-squashing
Information from exponentially many distant nodes may be compressed into one fixed-width vector. Even when K layers make a dependency reachable, a narrow graph bottleneck can still impede information and gradients. Width, rewiring, global attention, and positional signals address different mechanisms; first diagnose dependency distance and graph bottlenecks before choosing one.
Using theoretical counterexamples
Counterexamples belong in tests, not only proofs. Construct tiny graphs that WL cannot distinguish or that mean aggregation collapses, give nodes identical features, and print every layer's embeddings. If a library model unexpectedly separates them, check for node IDs, random features, positional encodings, or normalization differences: any of these changes the theoretical setting.
Acceptance protocol
Deliver an expressivity audit stating the initial-feature assumption, whether aggregation is injective, how the center state is retained, depth, readout, theoretical ceiling, and one counterexample. Under equal parameter budgets, compare mean, max, and sum-plus-MLP across several seeds and graph sizes. Keep the conclusion within the tested distribution; “reaches the WL ceiling” never means “identifies every graph.”
Implementation and evidence boundaries
Initial-feature assumptions
WL/GNN comparisons must state initial colors or features. IDs, degrees, and random features may break symmetries before the architecture acts.
Local versus global limits
Finite-depth GNNs may fail before WL stabilizes. Separate receptive-field limits, aggregator collisions, and WL counterexamples.
Existence versus optimization
An injective function may exist without SGD finding it at finite width and precision. Controlled counting tasks separate training failure from architectural impossibility.
Complexity
GIN remains sparse-message-passing scale, while higher-order tuple models grow much faster. Expressivity must be compared with computational cost.
Claim boundary
Under stated initialization and injective aggregation/readout assumptions, GIN reaches one-dimensional WL power. It does not solve graph isomorphism universally.
Final theoretical acceptance test
Build four controlled pairs: multisets that mean collapses but sum separates; long paths whose difference lies beyond the chosen depth; graphs WL can separate but training fails to learn; and regular graphs that one-dimensional WL itself cannot separate. Save initial colors, WL colors at every round, GNN embeddings at every layer, and the final graph readout. This separates aggregator collision, receptive-field limits, optimization failure, and the theorem's ceiling. Add width, depth, and seed ablations, and attach every conclusion to its assumptions about initial features, precision, readout, and graph family.
Self-study checkpoint
Run one additional precision check with integer features designed to produce nearby sums. Compare the same sum-plus-MLP computation in float32 and float64, and record whether normalization makes distinct neighborhoods difficult to separate. This does not refute WL theory; it exposes the gap between exact injectivity and finite precision or width. For counting tasks, test count range and out-of-distribution graph sizes, and report “theoretically distinguishable” separately from “distinguished by this training run.”
Take one minimal graph or set of triples and write down the input, invariances retained by the model, output, and evaluation. If two examples that should differ remain identical at every step, you have located an expressive gap in the encoder.
Course video sources
Checked live: the archived Fall 2025 official page lists no public recording link (its Canvas entry is empty), and the current Fall 2026 official page says lecture videos are on Canvas for enrolled students only; the Canvas entry redirects to the Stanford sign-in page. The public Stanford Online YouTube playlists currently cover only the 2021 and 2023 offerings, whose lectures differ from the Fall 2025 offering this article follows, so they are not embedded or treated as Fall 2025 recordings.
Course and recording entries:
- Official course / lecture source
- CS224W Fall 2025 official archive
- Stanford Online CS224W public playlist (2021 offering, not Fall 2025)
- Stanford Online CS224W public playlist (2021 / 2023 offerings, not Fall 2025)
Checked: 2026-10-10.
Update Log
- 2026-10-10: Added explicit video status and checked recording sources and access notes.
- 2026-10-10: Rechecked video status. Confirmed the official pages list no public Fall 2025 recording, Canvas requires sign-in, and public playlists cover only 2021/2023; status unchanged and check date added.
References
Loading...