Note to other teachers and users of these slides: We would be delighted if you found our

material useful for giving your own lectures. Feel free to use these slides verbatim, or to modify
them to fit your own needs. If you make use of a significant portion of these slides in your own
lecture, please include this message, or a link to our web site: [Link]

CS224W: Machine Learning with Graphs

Jure Leskovec, Stanford University
[Link]
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 ¡ Colab 0 will be released today by 9PM on our
course website
¡ Colab 0:
§ Overview of NetworkX and PyTorch Geometric
§ Does not need to be handed in
§ TAs will hold a recitation session to walk you
through Colab 0:
§ Time: Friday (09/27), 3-4pm PT
§ Location: Zoom, link is posted on Ed
§ Session will be recorded

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 3
 ¡ Colab 1 will be released today by 9PM on our
course website
¡ Colab 1:
§ Will cover material from Lectures 1-2,
so you can get started right away!
§ Due on Thursday 10/10 (2 weeks from today)
§ Submit written answers and code on Gradescope

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 4
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 Given an input graph, extract node, link
and graph-level features, then learn a
model (SVM, neural network, etc.) that
maps features to labels.

Input Structured Learning

Prediction
Graph Features Algorithm

Feature engineering Downstream

(node-level, edge-level, graph- prediction task
level features)

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 6
 Graph Representation Learning alleviates
the need to do feature engineering every
single time.
Input Structured Learning
Prediction
Graph Features Algorithm

Feature Representation Learning -- Downstream

Engineering Automatically prediction task
learn the features

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 7
Goal: Efficient task-independent feature
learning for machine learning with graphs!

node vector
𝑢
𝑓: 𝑢 → ℝ!
ℝ!
Feature representation,
embedding

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 8
 ¡ Task: Map nodes into an embedding space
§ Similarity of embeddings between nodes indicates
their similarity in the network. For example:
§ Both nodes are close to each other (connected by an edge)
§ Encode network information
§ Potentially used for many downstream predictions

Vec Tasks
• Node classification
• Link prediction
• Graph classification
• Anomalous node detection
embeddings ℝ! • Clustering
• ….
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 9
 Example
2D embedding of nodes of the Zachary’s
¡
Karate Karate
• Zachary’s Club network:
Network:

Image from: Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 10
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 ¡ Assume we have an (undirected) graph G:
§ V is the vertex set.
§ A is the adjacency matrix (assume binary).
§ For simplicity: No node features or extra
information is used
4
3
2 æ0 1 0 1ö
1
ç ÷
ç1 0 0 1÷
A=ç
V: {1, 2, 3, 4} 0 0 0 1÷
ç ÷
ç1 1 1 0 ÷ø
è

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 12
¡ Goal is to encode nodes so that similarity in
the embedding space (e.g., dot product)
approximates similarity in the graph

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 13
Goal: similarity 𝑢, 𝑣 ≈ 𝐳"# 𝐳$
in the original network Similarity of the embedding

Need to define!

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 14
1. Encoder maps from nodes to embeddings
2. Define a node similarity function (i.e., a
measure of similarity in the original network)
3. Decoder 𝐃𝐄𝐂 maps from embeddings to the
similarity score
4. Optimize the parameters of the encoder so
that: 𝐃𝐄𝐂(𝐳 "𝐳 ) ! #

similarity 𝑢, 𝑣 ≈ 𝐳"# 𝐳$
in the original network Similarity of the embedding

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 15
 ¡ Encoder: maps each node to a low-dimensional
vector d-dimensional
ENC 𝑣 = 𝐳! embedding
node in the input graph
¡ Similarity function: specifies how the
relationships in vector space map to the
relationships in the original network
similarity 𝑢, 𝑣 ≈ 𝐳"# 𝐳$ Decoder
Similarity of 𝑢 and 𝑣 in dot product between node
the original network embeddings
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 16
 Simplest encoding approach: Encoder is just an
embedding-lookup
ENC 𝑣 = 𝐳𝒗 = 𝐙 ⋅ 𝑣

!× 𝒱 matrix, each column is a node

𝚭∈ℝ embedding [what we learn /
optimize]
indicator vector, all zeroes
𝒱
𝑣∈𝕀 except a one in column
indicating node v
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 17
 Simplest encoding approach: encoder is just an
embedding-lookup
embedding vector for a
embedding specific node
matrix

Dimension/size
𝐙= of embeddings

one column per node

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 18
 Simplest encoding approach: Encoder is just an
embedding-lookup

Each node is assigned a unique

embedding vector
(i.e., we directly optimize
the embedding of each node)

Many methods: DeepWalk, node2vec

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 19
 ¡ Encoder + Decoder Framework
§ Shallow encoder: Embedding lookup
§ Parameters to optimize: 𝐙 which contains node
embeddings 𝐳' for all nodes 𝑢 ∈ 𝑉
§ We will cover deep encoders in the GNNs

§ Decoder: based on node similarity.

§ Objective: maximize 𝐳() 𝐳' for node pairs (𝑢, 𝑣)
that are similar

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 20
 ¡ Key choice of methods is how they define node
similarity.

¡ Should two nodes have a similar embedding if

they…
§ are linked?
§ share neighbors?
§ have similar “structural roles”?
¡ We will now learn node similarity definition that uses
random walks, and how to optimize embeddings for
such a similarity measure.

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 21
 ¡ This is unsupervised/self-supervised way of
learning node embeddings.
§ We are not utilizing node labels
§ We are not utilizing node features
§ The goal is to directly estimate a set of coordinates
(i.e., the embedding) of a node so that some aspect
of the network structure (captured by DEC) is
preserved.
¡ These embeddings are task independent:
§ They are not trained for a specific task but can be
used for any task.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 22
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 ¡ Vector 𝐳! :
§ The embedding of node 𝑢 (what we aim to find).
¡ Probability 𝑃 𝑣 𝐳! ) : Our model prediction based on 𝐳#
§ The (predicted) probability of visiting node 𝑣 on
random walks starting from node 𝑢.

Non-linear functions used to produce predicted probabilities

¡ Softmax function:
§ Turns vector of 𝐾 real values (model predictions)
𝒛[#]
into
"
𝐾 probabilities that sum to 1: 𝑆(𝒛)[𝑖] = ∑( 𝒛[%]
%&' "
¡ Sigmoid function:
§ S-shaped function that turns real values into the range of (0, 1).
)
Written as 𝜎 𝑥 = !" .)*+

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 24
 10
9

12
2 Step 3 Step 4

8 Step 5
1
11
3
Given a graph and a starting
4 Step 1 Step 2 point, we select a neighbor of
it at random, and move to this
neighbor; then we select a
6
5 neighbor of this point at
random, and move to it, etc.
The (random) sequence of
7 points visited this way is a
random walk on the graph.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 25
 probability that u
"
𝐳! 𝐳# ≈ and v co-occur on
a random walk over
the graph

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 26
1. Estimate probability of visiting node 𝒗 on a
random walk starting from node 𝒖 using
some random walk strategy 𝑹

2. Optimize embeddings to encode these

random walk statistics:
Similarity in embedding space (Here:
dot product=cos(𝜃)) encodes random walk “similarity”
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 27
1. Expressivity: Flexible stochastic definition of
node similarity that incorporates both local
and higher-order neighborhood information
Idea: if random walk starting from node 𝑢
visits 𝑣 with high probability, 𝑢 and 𝑣 are
similar (high-order multi-hop information)

2. Efficiency: Do not need to consider all node

pairs when training; only need to consider
pairs that co-occur on random walks
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 28
 ¡ Intuition: Find embedding of nodes in
𝑑-dimensional space that preserves similarity

¡ Idea: Learn node embedding such that nearby

nodes are close together in the network

¡ Given a node 𝑢, how do we define nearby

nodes?
§ 𝑁. 𝑢 … neighbourhood of 𝑢 obtained by some
random walk strategy 𝑅
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 29
 ¡ Given 𝐺 = (𝑉, 𝐸),
¡ Our goal is to learn a mapping 𝑓: 𝑢 → ℝ$ :
𝑓 𝑢 = 𝐳%
¡ Log-likelihood objective:
arg max 3 log P(𝑁3 (𝑢)| 𝐳' )
/
' ∈2
§ 𝑁$ (𝑢) is the neighborhood of node 𝑢 by strategy 𝑅

¡ Given node 𝑢, we want to learn feature

representations that are predictive of the nodes
10/4/24
in its random walk neighborhood 𝑁& (𝑢).
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 30
1. Run short fixed-length random walks
starting from each node 𝑢 in the graph using
some random walk strategy R.
2. For each node 𝑢 collect 𝑁& (𝑢), the multiset*
of nodes visited on random walks starting
from 𝑢.
3. Optimize embeddings according to: Given
node 𝑢, predict its neighbors 𝑁' (𝑢).
arg max I log P(𝑁' (𝑢)| 𝐳$ ) Maximum likelihood
objective
(
$ ∈+
*𝑁! (𝑢) can have repeat elements since nodes can be visited multiple times on random walks
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 31
 Equivalently,

arg min ℒ = . . −log(𝑃(𝑣|𝐳6 ))

5
6∈8 9∈:' (6)

• IntuiEon: OpNmize embeddings 𝒛$ to minimize

the negaNve log-likelihood of random walk
neighborhoods 𝑁(𝑢).
• Parameterize 𝑃(𝑣|𝐳𝑢 ) using soGmax: Why softmax?
We want node 𝑣 to be
,
exp(𝐳$ 𝐳" ) most similar to node 𝑢
𝑃 𝑣 𝐳$ = (out of all nodes 𝑛).

∑-∈+ exp(𝐳$, 𝐳- ) Intuition: ∑ exp 𝑥 ≈

max exp(𝑥 )
"
"
" "

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 32
PuHng it all together:
exp(𝐳!) 𝐳% )
ℒ=# # − log( ) )
∑*∈# exp(𝐳! 𝐳* )
!∈# %∈&4 (!)

sum over all sum over nodes 𝑣 predicted probability of 𝑢

nodes 𝑢 seen on random and 𝑣 co-occuring on
walks star0ng from 𝑢 random walk

OpEmizing random walk embeddings =

Finding embeddings 𝐳𝒖 that minimize L
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 33
But doing this naively is too expensive!

exp(𝐳!) 𝐳% )
ℒ=# # −log( ) )
∑*∈# exp(𝐳! 𝐳* )
!∈# %∈&4 (!)

Nested sum over nodes gives

O(|V|2) complexity!

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 34
But doing this naively is too expensive!

exp(𝐳!) 𝐳% )
ℒ=# # −log( ) )
∑*∈# exp(𝐳! 𝐳* )
!∈# %∈&4 (!)

The normalizaEon term from the soGmax is

the culprit… can we approximate it?

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 35
 Why is the approximation valid?
Technically, this is a different objective. But

¡ SoluEon: NegaNve sampling Negative Sampling is a form of Noise

Contrastive Estimation (NCE) which approx.
maximizes the log probability of softmax.
exp 𝐳'5 𝐳( New formulation corresponds to using a
−log( ) logistic regression (sigmoid func.) to

∑:∈2 exp 𝐳'5 𝐳: distinguish the target node 𝑣 from nodes 𝑛!

sampled from background distribution 𝑃" .
More at [Link]

≈ log 𝜎 𝐳'5 𝐳( + ∑9678 log 𝜎 −𝐳'5 𝐳:! , 𝑛6 ~𝑃2

sigmoid function random distribution

(makes each term a “probability”
between 0 and 1)
over nodes
Instead of normalizing w.r.t. all nodes, just
normalize against 𝑘 random “negaEve samples” 𝑛/
¡ Nega0ve sampling allows for quick likelihood calcula0on.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 36
 exp 𝐳'5 𝐳( random distribution
log( ) over nodes
∑:∈2 exp 𝐳'5 𝐳:
9
≈ log 𝜎 𝐳'5 𝐳( +3 log 𝜎 −𝐳'5 𝐳:! , 𝑛6 ~𝑃2
678
§ Sample 𝑘 negative nodes 𝑛/ each with prob.
proportional to its degree.
§ Two considerations for 𝑘 (# negative samples):
1. Higher 𝑘 gives more robust estimates
2. Higher 𝑘 corresponds to higher bias on negative events
In practice 𝑘 =5-20.
Can negative sample be any node or only the nodes not on the
walk? People often sample any node (for efficiency).
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 37
§ After we obtained the objective function, how do
we optimize (minimize) it?
ℒ=) ) −log(𝑃(𝑣|𝐳: ))
:∈< =∈>$ (:)

§ Gradient Descent: a simple way to minimize ℒ :

§ Initialize 𝑧$ at some randomized value for all nodes 𝑢.

§ Iterate until convergence:

$ℒ 𝜂: learning rate
§ For all 𝑢, compute the derivative .
$&&

$ℒ
§ For all 𝑢, make a step in reverse direction of derivative: 𝑧# ← 𝑧# − 𝜂 .
$&&
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 38
§ Stochastic Gradient Descent: Instead of evaluating
gradients over all examples, evaluate it for each
individual training example.
§ Initialize 𝑧! at some randomized value for all nodes 𝑢.

§ Iterate until convergence: ℒ (#) = B −log(𝑃(𝑣|𝐳# ))

!∈*' (#)
%ℒ (?)
§ Sample a node 𝑢, for all 𝑣 calculate the gradient .
%'@
%ℒ (?)
§ For all 𝑣, update:𝑧( ← 𝑧( − 𝜂 .
%'@

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 39
1. Run short fixed-length random walks starting
from each node on the graph
2. For each node 𝑢 collect 𝑁& (𝑢), the multiset of
nodes visited on random walks starting from 𝑢.
3. Optimize embeddings 𝑍 using Stochastic
Gradient Descent:
ℒ=1 1 −log(𝑃(𝑣|𝐳% ))
%∈5 6∈7& (%)
We can efficiently approximate this using
negative sampling!
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 40
 ¡ So far we have described how to optimize
embeddings given a random walk strategy R
¡ What strategies should we use to run these
random walks?
§ Simplest idea: Just run fixed-length, unbiased
random walks starting from each node (i.e.,
DeepWalk from Perozzi et al.)
§ The issue is that such notion of similarity is too constrained
¡ How can we generalize this?
Reference: Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 41
 ¡ Goal: Embed nodes with similar network
neighborhoods close in the feature space.
¡ We frame this goal as a maximum likelihood
optimization problem, independent to the
downstream prediction task.
¡ Key observation: Flexible notion of network
neighborhood 𝑁& (𝑢) of node 𝑢 leads to rich node
embeddings
¡ Develop biased 2nd order random walk 𝑅 to
generate network neighborhood 𝑁& (𝑢) of node 𝑢
Reference: Grover et al. node2vec: Scalable Feature Learning for Networks. KDD.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 42
Feature Learning for Networks

Idea: use flexible, biased

Jure random walks that can
Leskovec
trade off between localUniversity
Stanford and global views of the
jure@[Link]
network (Grover and Leskovec).

s1 s2 s8
careful
s7
cent re-
BFS
d to sig- u s6
features DFS
sitive to s4 s9
s3 s5
r learn- Figure 1: BFS and DFS search strategies from node u (k = 3).
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 43
 Jure Leskovec
Stanford University
jure@[Link]

Two classic strategies to define a neighborhood

𝑵𝑹 𝒖 of a given node 𝒖:
s1 s2 s8
careful
s7
cent re-
BFS
d to sig- u s6
eatures DFS
sitive to s4 s9
s3 s5
r learn- Figure 1: BFS and DFS search strategies from node u (k = 3).
vec, we Walk of length 3 (𝑁 𝑢 of size 3): &
eatures
𝑁
een net- 123 𝑢 = { 𝑠 , 𝑠 , 𝑠 } Local microscopic view
and edges. A typical solution involves hand-engineering domain-
specific features based4 5on expert 6 knowledge. Even if one discounts
node’s
the tedious work of feature engineering, such features are usually
proce-
leads to
𝑁 723 𝑢 = { 𝑠 , 𝑠 , 𝑠 } Global macroscopic view
designed for specific 8 tasks 9 and : do not generalize across different
10/4/24 prediction tasks.
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 44
 u

BFS: DFS:
𝑁& (⋅) will provide 𝑁& (⋅) will provide a
a micro-view of macro-view of
neighbourhood neighbourhood
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 45
Biased fixed-length random walk 𝑹 that given a node
𝒖 generates neighborhood 𝑵𝑹 𝒖
¡ Random walk has two parameters:
§ Return parameter 𝒑:
§ Return back to the previous node
§ In-out parameter 𝒒:
§ Moving outwards (DFS) vs. inwards (BFS) from the previous node
§ Intuitively, 𝑞 is the “ratio” of BFS vs. DFS
¡ Next, we specify how a single step of biased
random walk is performed.
¡ Random walk is then just a sequence of these steps.

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 46
Define the random walk by specifying the walk
transition probabilities on edges adjacent to the
current node 𝑤:
§ Rnd. walk just traversed edge (𝒕, 𝒘) and is now at 𝒘
§ We specify edge transition probs. out of node 𝒘
§ Insight: Neighbors of 𝑤 can only be:
Distance 1 from 𝒕
s1 s2
w Distance 2 from 𝒕

u t
Distance 0 from 𝒕
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 47
 ¡ Walker came over edge (𝒕, 𝐰) and is now at 𝐰.
How to set edge transition probabilities?
s1 1
1/𝑞 s2 1/𝑝, 1/𝑞, 1 are
w unnormalized
1/𝑞
w probabilities
u 1/𝑝 s3

¡ 𝑝, 𝑞 model transition probabilities

§ 𝑝 … return parameter
§ 𝑞 … ”walk away” parameter

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 48
 ¡ Walker came over edge (𝐬𝟏 , 𝐰) and is at 𝐰.
How to set edge transition probabilities?
Target 𝒙 Prob. Dist. (𝒕, 𝒙)
s1 1
1/𝑞 s2 t 1/𝑝 0
w w → s1 1 1
1/𝑞
u t 1/𝑝 s3
s2 1/𝑞 2
s3 1/𝑞 2
Unnormalized
§ BFS-like walk: Low value of 𝑝 transition prob.
segmented based

§ DFS-like walk: Low value of 𝑞 on distance from 𝑡

𝑁& (𝑢) are the nodes visited by the biased walk

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 49
 ¡ 1) Compute edge transition probabilities:
§ For each edge (𝑡, 𝑤) we compute edge walk
probabilities (based on 𝑝, 𝑞) of edges (𝑤,⋅)
¡ 2) Simulate 𝑟 random walks of length 𝑙 starting
from each node 𝑢
¡ 3) Optimize the node2vec objective using
Stochastic Gradient Descent

¡ Linear-time complexity
¡ All 3 steps are individually parallelizable
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 50
 ¡ Different kinds of biased random walks:
§ Based on node attributes (Dong et al.).
§ Based on learned weights (Abu-El-Haija et al.)

¡ Alternative optimization schemes:

§ Directly optimize based on 1-hop and 2-hop random walk
probabilities (as in LINE from Tang et al.).

¡ Network preprocessing techniques:

§ Run random walks on modified versions of the original
network (e.g., Ribeiro et al. struct2vec, Chen et al. HARP).

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 51
 ¡ Core idea: Embed nodes so that distances in
embedding space reflect node similarities in
the original network.
¡ Different notions of node similarity:
§ Naïve: Similar if two nodes are connected
§ Random walk approaches (covered today)

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 52
 ¡ So, what method should I use..?
¡ No one method wins in all cases….
§ E.g., node2vec performs better on node classification
while alternative methods perform better on link
prediction (Goyal and Ferrara, survey).
¡ Random walk approaches are generally more
efficient.
¡ In general: Must choose definition of node
similarity that matches your application.

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 53
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 ¡ Goal: Want to embed a subgraph or an entire
graph 𝐺. Graph embedding: 𝐳𝑮 .

𝒛(

¡ Tasks:
§ Classifying toxic vs. non-toxic molecules
§ Identifying anomalous graphs
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 55
 Simple (but effective) approach 1:
¡ Run a standard graph embedding
technique on the (sub)graph 𝐺.
¡ Then just sum (or average) the node
embeddings in the (sub)graph 𝐺.

𝒛𝑮 = # 𝒛#
#∈%
¡ Used by Duvenaud et al. to classify molecules
10/4/24
based on their graph structure
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 56
 ¡ Approach 2: Introduce a “virtual node” to
represent the (sub)graph and run a standard
graph embedding technique

¡ Proposed by Li et al. as a general technique

for subgraph embedding
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 57
 We discussed 2 ideas to graph embeddings:

¡ Approach 1: Embed nodes and sum/avg them

¡ Approach 2: Create super-node that spans the

(sub) graph and then embed that node.

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 58
 ¡ DiffPool: We can also hierarchically cluster
nodes in graphs, and sum/avg the node
embeddings according to these clusters.

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 59
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 ¡ Recall: encoder as an embedding lookup
embedding vector for a
embedding specific node
matrix

Dimension/size
𝐙= of embeddings

one column per node

Objective: maximize 𝐳!)𝐳$ for node pairs (𝑢, 𝑣) that are similar

10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 61
 ¡ Simplest node similarity: Nodes 𝑢, 𝑣 are
similar if they are connected by an edge
¡ This means: 𝐳"# 𝐳$ = 𝐴$,"
which is the (𝑢, 𝑣) entry of the graph
adjacency matrix 𝐴
¡ Therefore, 𝒁> 𝒁 = 𝐴
𝒁* 𝒁
4 æ0 1 0 1ö
ç ÷
3 ç1 0 0 1÷ ×
A=ç
2 0 0 0 1÷
ç ÷
1 ç1 1 1 0 ÷ø
è
𝐳$ 𝐳!
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 62
 ¡ The embedding dimension 𝑑 (number of rows in 𝒁)
is much smaller than number of nodes 𝑛.
¡ Exact factorization 𝐴 = 𝒁𝑻 𝒁 is generally not possible
¡ However, we can learn 𝒁 approximately
¡ Objective:min ∥ A − 𝒁< 𝒁 ∥=
𝐙
§ We optimize 𝒁 such that it minimizes the L2 norm
(Frobenius norm) of A − 𝒁) 𝒁
§ Note today we used softmax instead of L2. But the goal to
approximate A with 𝒁) 𝒁 is the same.
¡ Conclusion: Inner product decoder with node
similarity defined by edge connectivity is
equivalent to matrix factorization of 𝐴.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 63
 ¡ DeepWalk and node2vec have a more
complex node similarity definition based on
random walks
¡ DeepWalk is equivalent to matrix
factorization of the following complex matrix
expression:
1 *
𝑙𝑜𝑔 𝑣𝑜𝑙(𝐺) : (𝐷 .-𝐴)+ 𝐷 .- − log 𝑏
𝑇 +,-

§ Explanation of this equation is on the next slide.

Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 64
 Volume of graph
𝑣𝑜𝑙 𝐺 = > > 𝐴',( Diagonal matrix 𝐷
' ( 𝐷#,# = deg(𝑢)

1 .
log 𝑣𝑜𝑙(𝐺) B (𝐷 /- 𝐴)+ 𝐷 /- − log 𝑏
𝑇 +,-

context window size Number of

See Lec 3 slide 30: Power of normalized negative samples
𝑇 = |𝑁% 𝑢 | adjacency matrix

¡ Node2vec can also be formulated as a matrix

factorization (albeit a more complex matrix)
¡ Refer to the paper for more details:
Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 65
 ¡ How to use embeddings 𝒛𝒊 of nodes:
§ Clustering/community detection: Cluster points 𝒛𝒊
§ Node classification: Predict label of node 𝑖 based on 𝒛𝒊
§ Link prediction: Predict edge (𝑖, 𝑗) based on (𝒛𝒊 , 𝒛𝒋 )
§ Where we can: concatenate, avg, product, or take a difference
between the embeddings:
§ Concatenate: 𝑓(𝒛( , 𝒛) )= 𝑔([𝒛( , 𝒛) ])
§ Hadamard: 𝑓(𝒛( , 𝒛) )= 𝑔(𝒛( ∗ 𝒛) ) (per coordinate product)
§ Sum/Avg: 𝑓(𝒛( , 𝒛) )= 𝑔(𝒛( + 𝒛) )
§ Distance: 𝑓(𝒛( , 𝒛) )= 𝑔(||𝒛( − 𝒛𝒋 ||+ )
§ Graph classification: Graph embedding 𝒛𝑮 via aggregating
node embeddings or virtual-node.
Predict label based on graph embedding 𝒛9 .
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 66
 We discussed graph representation learning, a way to
learn node and graph embeddings for downstream
tasks, without feature engineering.
¡ Encoder-decoder framework:
§ Encoder: embedding lookup
§ Decoder: predict score based on embedding to match
node similarity
¡ Node similarity measure: (biased) random walk
§ Examples: DeepWalk, Node2Vec

¡ Extension to Graph embedding: Node embedding

aggregation
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 67
 Limitations of node embeddings via matrix
factorization and random walks
§ Transductive (not inductive) method:
§ Cannot obtain embeddings for nodes not in the training set
§ Cannot apply to new graphs
§ If you apply DeepWalk to the same graph multiple times, each time
you’ll get a different embedding each time. Why?

4 A newly added node 5 at test time

3 (e.g., new user in a social network)
2 Cannot compute its embedding
1 5 with DeepWalk / node2vec. Need to
recompute all node embeddings.
Training set
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 68
 ¡ Cannot capture structural similarity:
3 13
4 5 10
2 12
1 11

§ Node 1 and 11 are structurally similar – part of one

triangle, degree 2, …
§ However, they have very different embeddings.
§ It’s unlikely that a random walk will reach node 11 from node 1.

¡ DeepWalk and node2vec do not capture

structural similarity.
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 69
 ¡ Cannot utilize node, edge and graph features

4
Feature vector
3 (e.g. protein properties in a
2 protein-protein interaction graph)
1 5
DeepWalk / node2vec
embeddings do not incorporate
such node features

Solution to these limitations: Deep Representation

Learning and Graph Neural Networks
(To be covered in depth next)
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 70