Machine Learning with Graphs

Personal study notes written in my own words from publicly available lectures and course pages. Not affiliated with or endorsed by Stanford University. No assignment solutions are published here.

What the course is about

Most machine learning assumes inputs that come as fixed-size vectors, grids, or sequences. Graphs break that assumption: a molecule, a social network, a knowledge base, or a road map has no natural ordering of its parts, no fixed size, and its information lives as much in the connections as in the nodes. CS224W is about turning graph structure into something a learning algorithm can use, first with hand-designed features, then with learned embeddings, and finally with neural networks that pass messages along edges.

You should be comfortable with linear algebra (matrix products, eigenvectors), basic probability, and the mechanics of training a neural network with gradient descent. Knowing what a softmax, a cross-entropy loss, and an embedding table are will make the second half of the course much easier. No prior graph theory is assumed beyond adjacency matrices and degrees.

The lectures follow one arc. The early part builds intuition with classical tools: structural features, random walks, and PageRank. The middle introduces graph neural networks, how to design them, and how to reason about what they can and cannot distinguish. The last part applies the machinery to specific settings: knowledge graphs, recommender systems, community structure, graph generation, large-scale training, and questions of trust. Each later topic reuses the message-passing view introduced in the middle, so it pays to understand that section thoroughly.

Lecture notes

01 · Why graphs, and the three levels of tasks

A graph is a set of nodes $V$ and edges $E$, often stored as an adjacency matrix $A \in \{0,1\}^{|V| \times |V|}$ or, more practically, as an adjacency list. Edges can be directed or undirected, weighted, and typed; nodes and edges can carry feature vectors. The main modeling choice is deciding what the nodes and edges represent, because that choice determines what the model can learn.

Prediction tasks are organized by their granularity:

Two ideas run through everything that follows. First, a good graph learner must be indifferent to the arbitrary order in which nodes are listed (permutation invariance for graph-level outputs, permutation equivariance for node-level outputs). Second, a node’s identity is largely determined by its neighborhood, so almost every method here summarizes neighborhoods, either with formulas or with learned functions.

What goes wrong in practice is usually at the modeling step: an edge type gets dropped because it was inconvenient, or a directed relation is stored as undirected and the model learns something backwards. The next lecture starts with the classical answer to the question “how do you summarize a neighborhood?”

02 · Traditional feature-based methods

Before neural networks, graph prediction meant computing structural features by hand and feeding them to a logistic regression or a random forest. The features differ by task level.

For nodes, the basic ones are degree, centrality measures (eigenvector, betweenness, closeness), and the clustering coefficient, which is the fraction of a node’s neighbor pairs that are themselves connected. Graphlets generalize this: count how many times a node participates in each small rooted subgraph (paths, triangles, stars, up to a few nodes) and stack the counts into a graphlet degree vector. This captures local structure much more finely than degree alone.

For edges, the goal is to score how likely two nodes are to be connected. Distance-based features use shortest path length. Neighborhood-overlap features count common neighbors, normalize them (Jaccard), or weight them so that rare shared neighbors count more, as in Adamic-Adar:

Global overlap features such as the Katz index count paths of all lengths with geometric decay, computable in closed form from powers of $A$.

For whole graphs, kernel methods compare graphs through bag-of-structure representations: the graphlet kernel counts small subgraphs, and the Weisfeiler-Lehman kernel iteratively refines node colors by hashing neighbor colors, then compares color histograms. WL is cheap and surprisingly strong.

The practical failure is that hand-designed features encode whatever the designer thought to include and nothing more. Computing graphlet counts is also expensive for larger motifs. The next lecture replaces designed features with learned ones.

03 · Node embeddings: DeepWalk and node2vec

The goal of node embedding is a function $z_v = \text{ENC}(v)$ such that similarity in embedding space, usually the dot product $z_u^\top z_v$, mirrors similarity in the graph. The simplest encoder is a lookup table with one free vector per node. The question is how to define graph similarity.

Random walks give a flexible answer: two nodes are similar if short random walks starting from one tend to visit the other. For each node $u$, run walks and collect the multiset of visited nodes $N_R(u)$. Then train the embeddings to make those co-visits probable:

The denominator over all nodes is too expensive, so negative sampling replaces it with a sigmoid on the positive pair plus a handful of random negatives, exactly as in word2vec. DeepWalk uses plain unbiased walks.

node2vec adds two knobs that bias the walk. The return parameter $p$ controls the chance of stepping back to the previous node; the in-out parameter $q$ controls whether the walk stays close (BFS-like, capturing community membership) or wanders outward (DFS-like, capturing structural role). Small $q$ explores; small $p$ stays local.

Graph-level embeddings can be built by summing or averaging node embeddings, or by adding a virtual node connected to everything and embedding that. Anonymous walks, which record only the pattern of first visits, offer another route.

The weakness of all of these: embeddings are transductive. A node that appears after training has no vector, and node features are ignored entirely. Neural encoders fix both problems later.

04 · PageRank and random walk with restart

PageRank treats a directed graph as a flow of importance. Each node splits its current score equally among its out-links, and a node’s new score is the sum of what flows in. Writing $M$ for the column-stochastic matrix with $M_{ji} = 1/d_i^{\text{out}}$ when $i \to j$, the fixed point satisfies $r = M r$, so $r$ is the leading eigenvector of $M$ and also the stationary distribution of a random surfer.

Two problems break the plain version: dead ends (nodes with no out-links) leak score, and spider traps (closed cycles) absorb it. The fix is teleportation: with probability $\beta$ follow a link, otherwise jump to a uniformly random node.

Power iteration solves this: initialize $r$ uniformly, apply the update, renormalize, repeat until the change drops below a tolerance. It converges in a few dozen iterations on web-scale graphs.

import numpy as np
def pagerank(M, beta=0.85, tol=1e-8):
    n = M.shape[0]
    r = np.ones(n) / n
    while True:
        r_new = beta * M @ r + (1 - beta) / n
        r_new /= r_new.sum()          # re-absorb leaked mass from dead ends
        if np.abs(r_new - r).sum() < tol:
            return r_new
        r = r_new

Personalized PageRank changes only the teleport set: jump back to a chosen set of nodes rather than anywhere. Random walk with restart is the extreme case where the set is a single query node; the resulting scores rank other nodes by proximity to the query, which is a strong baseline for recommendation. Simulating the walk directly, rather than solving the linear system, is often enough.

A common mistake is forgetting to renormalize when the graph has dead ends, which makes the scores shrink every iteration. The next lecture uses the same “iterate until stable” idea for classification.

05 · Message passing and collective classification

Suppose some nodes have labels and you want to label the rest. Node features alone waste information: in many graphs, connected nodes share labels (homophily), or a node’s label is predictable from its neighbors’ labels even when they differ. Collective classification exploits these correlations by letting predictions influence each other.

Relational classification is the simplest scheme. Each unlabeled node holds a class probability, initialized uniformly, and repeatedly replaces it with the weighted average of its neighbors’ probabilities:

Labeled nodes stay fixed. Node features are ignored, and convergence is not guaranteed, though in practice the values settle.

Iterative classification adds features. Train one classifier on node features alone to produce initial labels, and a second classifier on node features plus a summary of neighbor labels (counts, or the most common label). Then loop: recompute the summaries, reapply the second classifier, until labels stop changing.

Loopy belief propagation is the principled version. Nodes exchange messages that say, in effect, “given what I believe, here is how likely each of your labels is,” using a label-compatibility matrix. It is exact on trees and approximate, occasionally non-convergent, on graphs with cycles.

The lasting idea is not any single algorithm but the pattern: a node’s state is updated from messages sent by its neighbors, repeated for several rounds. Graph neural networks make the message and update functions learnable.

06 · Graph neural networks: GCN, GraphSAGE, GAT

A graph neural network builds a node’s representation from its multi-hop neighborhood. Layer $l$ collects the layer-$l$ embeddings of the neighbors, aggregates them with an order-invariant function, and combines the result with the node’s own embedding. Stacking $K$ layers gives every node a receptive field of its $K$-hop neighborhood. Because the same weights are shared across all nodes, the model is inductive: it can embed nodes and graphs it never saw during training.

The graph convolutional network normalizes by degree and applies a single weight matrix:

In matrix form this is $H^{(l+1)} = \sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)})$ with $\tilde{A} = A + I$.

GraphSAGE separates the self and neighbor terms and makes the aggregator pluggable:

where AGG can be a mean, a max after an MLP (pooling), or an LSTM over a shuffled neighbor list. Embeddings are often $\ell_2$-normalized after each layer.

The graph attention network learns how much each neighbor matters instead of using fixed degree weights:

and then aggregates $\sum_u \alpha_{vu} W h_u$. Multiple attention heads are run in parallel and concatenated or averaged.

Training follows the task: cross-entropy on labeled nodes, a pair score for edges, pooled embeddings for graphs. The most common practical error is stacking many layers expecting more power; deep GNNs blur node embeddings together, a problem the next lecture addresses directly.

07 · The GNN design space

A GNN is a pipeline, and each stage is a design decision. Within a layer, the choice is the message function (usually a linear map), the aggregation (sum, mean, max, attention), and the nonlinearity. Batch normalization on node embeddings stabilizes training; dropout on the linear map regularizes it.

Between layers, the key problem is over-smoothing. Each layer averages a node with its neighbors, so after many layers the receptive fields of different nodes overlap almost completely and their embeddings collapse toward one another. The practical rules are to keep the number of message-passing layers close to the graph’s diameter of interest, to put expressive MLPs before and after message passing (pre- and post-processing layers) rather than adding more GNN layers, and to add skip connections so that shallow, more distinctive embeddings survive to the output. A skip connection can be a residual sum or a concatenation of all layer outputs.

The graph itself can also be changed. If nodes have no features, give them a constant or a one-hot identity (one-hot works only transductively) or hand-computed counts such as triangles or cycle lengths that message passing struggles to detect. If the graph is too sparse, add virtual edges (for example, connect two-hop neighbors) or a virtual node linked to everything to shorten paths. If it is too dense, sample a subset of neighbors per layer, which also regularizes.

Treat these as hyperparameters worth searching, not fixed conventions. The natural question that follows is how much any of these architectures can actually distinguish.

08 · How expressive are GNNs? WL test and GIN

Two nodes with identical features and identical multi-hop neighborhood structure will always receive the same GNN embedding, since the computation graphs are the same. The question is the converse: when the neighborhoods differ, does the GNN notice?

The reference point is the Weisfeiler-Lehman color refinement test. Every node starts with the same color; at each round, a node’s new color is an injective hash of its current color together with the multiset of its neighbors’ colors. After $K$ rounds, two graphs with different color histograms are non-isomorphic. A GNN layer has exactly this shape, with the aggregator playing the role of the hash. So a GNN is at most as powerful as 1-WL, and it reaches that ceiling only when its aggregation is injective on multisets.

Mean and max aggregation are not injective. Mean cannot tell a neighbor multiset $\{a, b\}$ from $\{a, a, b, b\}$; max cannot tell $\{a\}$ from $\{a, a\}$. Sum can. The graph isomorphism network builds on this observation, using a sum followed by an MLP, which by the universal approximation theorem can represent an injective function of the summed multiset:

Here $\epsilon$ can be learned or fixed at zero. GIN is provably as expressive as 1-WL, and it can be read as a neural version of the WL kernel from lecture 02.

The ceiling still matters: 1-WL cannot distinguish some regular graphs, cannot count cycles, and gives identical embeddings to two nodes with the same local view even when their global positions differ. Adding structural features or node identifiers pushes past the limit at some cost to generality.

09 · Heterogeneous graphs and knowledge graph embeddings

Real graphs have several node types and several relation types: papers and authors, drugs and proteins, users and items. A heterogeneous graph stores each edge as a triple $(h, r, t)$ with a relation type. The direct GNN extension is the relational GCN, which uses a separate weight matrix per relation and normalizes per relation and node:

With many relations the parameter count explodes, so weights are made block-diagonal or built from a few shared basis matrices.

Knowledge graphs push this to its extreme: millions of entities, hundreds of relations, and the main task is completion, predicting the missing tail of $(h, r, ?)$. Shallow embedding models score triples directly.

The TransE idea is that a relation is a translation vector: $h + r \approx t$. It is trained with a margin loss against corrupted triples. Its weakness is that a symmetric relation forces $r = 0$, and a 1-to-N relation forces all tails to coincide. RotatE replaces translation with rotation in the complex plane, which keeps composition (rotations compose) while allowing symmetry (a rotation by $\pi$ is its own inverse).

No single model wins everywhere; check which relation patterns your data contains before choosing. The next lecture asks harder questions of the same embeddings.

10 · Reasoning over knowledge graphs

Link prediction answers one-hop questions. Real queries are multi-hop: “which proteins are associated with diseases treated by drug X?” translates to a path of two relations from an anchor entity. Because knowledge graphs are incomplete, you cannot just traverse; a missing edge would kill the whole path. The alternative is to reason in embedding space, where traversal becomes vector arithmetic.

With TransE-style embeddings, a path query is answered by starting at the anchor and adding the relation vectors in order; entities near the resulting point are the answers. This works for chains but breaks on conjunctions (“drugs that treat both A and B”), since a single point cannot represent a set that then gets intersected.

Query2box addresses this by embedding queries as axis-aligned boxes, each with a center and an offset (half-widths). Entities are points. A relation moves and grows the box: the center is translated and the offset is increased. Intersection of several boxes is computed with a learned attention over centers and a shrinking of offsets so the result lies inside all inputs. Distance from an entity to a box is the outside distance plus a down-weighted inside distance; training pulls answer entities inside the box and pushes sampled negatives out.

Unions are the hard case: the union of two arbitrary boxes is not a box, and it can be shown that handling unions in general needs embedding dimension that grows with the number of entities. The practical fix rewrites any query into disjunctive normal form, pushes the union to the very end, and takes the minimum distance across the disjuncts.

The general lesson: pick a geometric object whose closure properties match the logical operations you need.

11 · Subgraphs and motifs

A subgraph is either node-induced (pick nodes, keep all edges among them) or edge-induced (pick edges, keep their endpoints). Motifs are small, recurring, significant subgraphs: feed-forward loops in gene regulation, triangles in social networks, reciprocal edges in trade. Significance is measured against a null model. Generate random graphs with the same degree sequence (the configuration model, or edge-switching), count the motif in each, and compute a z-score; the vector of z-scores over motif types is a significance profile that fingerprints a network.

Deciding whether a query graph appears inside a target is subgraph isomorphism, which is NP-complete in general. Neural subgraph matching sidesteps exact search by embedding neighborhoods and encoding the “is contained in” relation as an order. In an order embedding, $z_A \preceq z_B$ coordinate-wise means A is a subgraph of B. Transitivity, antisymmetry, and closure under intersection all hold for the coordinate-wise order, matching the subgraph relation. Training uses a max-margin loss that pushes positive pairs to satisfy the order and negative pairs to violate it by a margin. The same embeddings support frequent motif mining: grow candidate subgraphs step by step, staying in the region of embedding space that many target neighborhoods dominate.

What typically goes wrong: counting node-induced when the biological question was about edge-induced patterns, or using an Erdos-Renyi null model that ignores degree heterogeneity and therefore flags every dense structure as significant. Subgraph-level reasoning returns in the recommender lecture, where a two-hop neighborhood of a user is the object of interest.

12 · GNNs for recommender systems

A recommender is a bipartite graph of users and items, with an edge for each interaction. The task is link prediction restricted to unseen user-item pairs, evaluated by ranking: for each user, does the model put held-out positive items in the top $K$? Recall at $K$ is the usual metric.

Embedding-based collaborative filtering gives each user and item a vector and scores a pair by dot product. Training uses the Bayesian personalized ranking loss, which for each user samples a positive item and a negative item and pushes the positive score above the negative through a log-sigmoid on the difference.

GNNs improve the embeddings by propagating them along the bipartite edges. Neural graph collaborative filtering did this with full GCN layers. LightGCN observed that, since the input embeddings are already learnable, the per-layer weight matrices and nonlinearities add little. Its update is pure normalized averaging, $E^{(l+1)} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} E^{(l)}$, and the final embedding is the mean over all layers. It trains faster and generalizes better than the heavier version.

PinSage scales the idea to billions of pins. Its main tricks are defining neighborhoods by short random walks and keeping the top-visited nodes (importance pooling), which bounds neighborhood size and weights neighbors by relevance; curriculum learning that gradually introduces hard negatives that are close to but not equal to the positive; and pre-computing neighborhoods so that inference is a map-reduce job.

The common failure is evaluating with random negatives, which makes any model look good; hard negatives and time-based splits give honest numbers.

13 · Community detection

Communities are groups of nodes with dense internal connections and sparse external ones. Detecting them means turning that intuition into an objective.

Modularity compares the number of edges inside groups to the number expected under a null model that preserves degrees. With $m$ edges, degrees $k_i$, and community labels $c_i$:

The term $k_i k_j / 2m$ is the expected number of edges between $i$ and $j$ if edges were rewired at random with the same degrees. Positive $Q$ means more internal edges than chance; values above roughly $0.3$ usually indicate meaningful structure.

Maximizing $Q$ exactly is NP-hard, so the Louvain method uses a greedy two-phase loop. Phase one visits nodes one at a time and moves each into the neighboring community that gives the largest modularity gain, repeating until no move helps. Phase two collapses each community into a super-node with weighted edges, then returns to phase one on the smaller graph. The result is a hierarchy of communities, and it scales to very large graphs.

Modularity has a resolution limit: it can merge small, genuinely distinct communities when the graph is large, because the null model term shrinks as $m$ grows. It also assigns each node to exactly one community. Overlapping models such as the affiliation graph model and its likelihood-based fitting (BigCLAM) let a node belong to several communities with different strengths, and the fit can be done by gradient ascent. Louvain plus a look at the resolution parameter is the reasonable default.

14 · Generative models for graphs

Graph generation serves anomaly detection, simulation, and drug design. Traditional models are simple and interpretable. Erdos-Renyi picks each edge independently, giving binomial degrees and no clustering. Small-world models rewire a ring lattice to get high clustering with short paths. Kronecker graphs grow a small initiator matrix through repeated Kronecker products and reproduce heavy-tailed degrees and shrinking diameters. None of them learn from data.

Deep generative models learn a distribution $p_{\text{model}}(G)$ from examples and sample from it. The difficulty is that a graph of $n$ nodes has $O(n^2)$ possible edges and $n!$ equivalent orderings. GraphRNN makes generation sequential: fix a node ordering, then emit one node at a time, and for each node emit the edges to all previous nodes. A graph-level RNN carries state across nodes; an edge-level RNN produces the binary edge decisions for the current node. Training is teacher-forced; sampling draws each edge from the emitted Bernoulli. Using a breadth-first node ordering matters: it caps how far back an edge can reach, which shrinks the edge-level sequence and reduces the number of orderings the model must cover.

Evaluating generated graphs is done by comparing statistics (degree, clustering, orbit counts) with a distributional distance, since there is no per-sample ground truth. For goal-directed generation, such as molecules with a target property, a reinforcement learning policy (GCPN) adds edges step by step and is rewarded for validity and the property.

Recent offerings also point to diffusion models, which reverse a gradual noising of adjacency and features and sidestep the ordering problem. All of these train on small graphs; the next lecture handles the opposite regime.

15 · Scaling GNNs to large graphs

Full-batch GNN training keeps every node embedding of every layer in memory and multiplies by the full adjacency matrix. That works for tens of thousands of nodes, not billions. Naively minibatching nodes does not help, because a $K$-layer GNN needs each sampled node’s entire $K$-hop neighborhood, which for a hub is the whole graph. Three responses are standard.

Neighbor sampling, introduced with GraphSAGE, caps the fan-out at each hop: sample at most $s_1$ neighbors at hop one, $s_2$ at hop two, and so on, so each node’s computation graph has at most $s_1 s_2 \cdots s_K$ leaves. Fresh samples each epoch regularize. The cost is noisy gradients, and with hubs even the pruned trees overlap heavily.

Cluster sampling (Cluster-GCN) partitions the graph into communities with a fast algorithm such as METIS, then treats each partition, or a random union of a few partitions, as a minibatch and runs full message passing inside it. Edges across partitions are dropped, which biases the gradient, and taking unions of clusters with their between-cluster edges reduces that bias. Embeddings are shared within the batch rather than recomputed per tree, so it is much faster.

Simplified GCN removes the nonlinearities from a GCN. Without them, $K$ layers collapse to $\tilde{A}^K X W$, and $\tilde{A}^K X$ can be precomputed once with sparse matrix products. Training is then a logistic regression on fixed features, which minibatches trivially. It loses expressiveness but works well when homophily is strong.

The final lecture covers what happens when the graph changes over time and when the predictions need to be trusted.

16 · Temporal graphs and trustworthy GNNs

Many graphs are event streams: a message at time $t$, a transaction, a citation. A temporal graph is a set of time-stamped edges, and the honest evaluation splits by time, training on the past and predicting the future. Static GNNs ignore this and leak future information when trained on the whole graph.

Temporal GNNs make time explicit. Temporal graph attention networks attend over a node’s past interactions with a learned time-encoding of the interval since each one, so recent events count differently from old ones. Temporal graph networks add a per-node memory vector updated by a recurrent cell each time the node participates in an event, then run message passing over the recent neighborhood with the memories as features. Both are inductive over new nodes and new time stamps.

Trustworthiness spans three concerns. Explainability asks which edges and features drove a prediction. GNNExplainer learns a soft mask over the edges of a node’s computation graph and over feature dimensions, chosen to maximize mutual information between the masked subgraph and the original prediction while keeping the mask small; the surviving edges are the explanation. Robustness asks how easily an adversary can flip a prediction by adding a few edges or perturbing features; on citation and social graphs, small structural edits to a target’s neighborhood are often enough, and adversarial training or certified smoothing are the standard defenses. Fairness asks whether outcomes differ across groups defined by sensitive attributes, which graphs can amplify through homophily even when the attribute is never used as a feature.

The cross-cutting lesson: because a GNN’s prediction depends on other nodes, every property you care about, correctness, explanation, robustness, fairness, must be reasoned about at the level of neighborhoods rather than individual examples.

Key equations at a glance

Common mistakes

• Using mean or max aggregation and then wondering why the model cannot distinguish nodes with different neighborhood sizes. Use sum aggregation (GIN-style) when structural counting matters.
• Stacking ten message-passing layers on a graph with diameter five. The embeddings over-smooth. Keep GNN depth small, add pre- and post-processing MLPs, and use skip connections.
• Running PageRank without handling dead ends, so total score shrinks each iteration and the ranking drifts. Renormalize after each step or redistribute leaked mass uniformly.
• Training node2vec or DeepWalk and then expecting embeddings for nodes added later. Shallow embeddings are transductive; switch to a GNN if new nodes will appear.
• Modeling a symmetric relation with TransE. The translation vector is forced toward zero. Pick a model such as DistMult, ComplEx, or RotatE whose geometry allows symmetry.
• Evaluating a recommender or a temporal link predictor with random splits. Future edges leak into training. Split by time and rank against hard negatives.
• Reading a high modularity score as proof of community structure without a null-model comparison. Random graphs with heavy-tailed degrees can have non-trivial modularity, and the resolution limit hides small communities.
• Ignoring edge direction or edge type because the library defaults to undirected homogeneous graphs. Directed and heterogeneous structure often carries most of the signal; use a relational model when types exist.

Related courses

• CS229 supplies the supervised-learning foundations, logistic regression and gradient descent, that every classifier in these notes sits on top of.
• CS230 covers the deep learning training practices (batch norm, dropout, initialization) reused in the GNN design space lecture.
• CS224N introduces word2vec and attention; node2vec and GAT are direct adaptations to graphs.
• CS231n explains convolution on grids, which is the special case that graph convolution generalizes.
• CS246 treats PageRank, community detection, and link analysis at web scale from the data-mining side.
• CS234 provides the policy-gradient background behind goal-directed graph generation.