Table of Contents
🌏 中文版
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.
References
Loading...