🌏 中文版
Video status: Recordings require sign-in or course authorization. Source details
This is Lecture 7 of Stanford CS224W: Machine Learning with Graphs, Fall 2025, dated 2025-10-14. 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. The perfect-GNN thought experiment
The slides begin with a perfect-GNN thought experiment: isomorphic neighborhoods should share a representation and different neighborhoods should not. The definition exposes a tension—some tasks need structural invariance, while others need absolute or relative position.
2. Three levels of standard-GNN failure
At node, edge, and graph levels, standard GNNs can produce identical computational graphs for distinct inputs. This symmetry is not a training failure; the input and aggregator preserve the same information.
3. Identity-aware encoding
Identity-aware methods mark the target node while computing its representation, so messages know whom they are relative to. This can reveal cycles and local structures hidden from anonymous message passing.
4. Substructure counting
Another route explicitly supplies motif, walk, or subgraph counts. It adds higher-order structural signal at the price of preprocessing, computation, and an inductive bias over which substructures matter.
5. Position-aware encoding
Position-aware methods use anchors or distances to locate nodes in the graph. Before choosing an encoder, decide whether the task needs structural role, community proximity, or relative position; they are different notions of similarity.
Two routes to more powerful encoders
The perfect-GNN contradiction
A useful thought experiment asks for representations that identify a node uniquely while remaining invariant to arbitrary node renaming. Those requirements conflict on symmetric nodes: without extra target or positional information, an equivariant encoder must treat automorphic nodes alike.
Node-level failure
Nodes with identical rooted neighborhoods receive identical messages at every layer, even when a query needs to distinguish their roles. Greater width cannot recover an identity that never entered the computation.
Edge-level failure
Encoding two endpoints independently can lose their joint position and enclosing structure. Link prediction therefore may require pair-conditioned labels or a target-edge-removed enclosing subgraph, not merely concatenated node embeddings.
Graph-level failure
Readout inherits collisions from node encodings and may introduce new ones when mean or max discards counts. Graph classification must audit both the local encoder and the permutation-invariant pooling operation.
Identity-aware encoding
Mark the query node and rerun message passing so the representation answers “relative to this target” rather than assigning one universal vector. The benefit is query-specific discrimination; the cost is that whole-graph embeddings may no longer be reusable.
Substructure-aware GNNs
Motif counts, rooted subgraphs, or higher-order tuples expose structure that ordinary one-dimensional message passing misses. Degree-matched controls are necessary because a claimed motif signal may otherwise be only a degree proxy.
Position-aware tasks
Distances to selected anchors provide coordinates relative to the graph. They can distinguish roles in one graph, but anchor choice, clipping, disconnected nodes, and transfer to a new graph become part of the model definition.
Choosing structure or position
Use substructure features when the label depends on local motifs or counts; use position-aware features when the target depends on where a node lies relative to a query or anchors. Adding both without ablation hides which missing information solved the task.
A spectral view
Laplacian eigenvectors offer global coordinates but have sign ambiguity and unstable bases under repeated eigenvalues. Any spectral encoder must respect those invariances rather than treating a particular eigensolver output as a fixed identity.
Acceptance protocol
Test symmetric nodes, endpoint pairs with the target edge removed, degree-matched motif examples, and anchor perturbations. Report accuracy together with query-time cost, preprocessing, and transfer to unseen graphs so extra power is not detached from its assumptions.
Implementation and evidence boundaries
Target conditioning
Identity-aware computation changes the marking for every query target, so cached whole-graph embeddings may no longer apply and per-query cost matters.
Pair labeling
Enclosing-subgraph link models must remove the target edge before computing endpoint-distance labels, or the structure reveals the answer.
Counting tasks
Degree-matched positives and negatives prevent motif counters from succeeding through simple degree proxies.
Anchor stability
Position-aware models must report anchor seeds, selection, distance clipping, and transfer to new graphs.
Failure taxonomy
Distinguish symmetry, insufficient depth, missing features, optimization, and poor anchor coverage before selecting a remedy.
Final encoder acceptance
For each remedy, preserve one minimal counterexample and its layer-by-layer states. Verify permutation behavior, remove labels or anchors in ablations, and state whether the output is node-, pair-, or graph-conditioned; only then attribute the gain to identity, substructure, or position.
Self-study checkpoint
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...