CS224W: Machine Learning with Graphs

Jure Leskovec, Stanford University

[Link]
 Given an input graph, extract node, link
and graph-level features, 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)

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 2
 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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 3
Goal: Efficient task-independent feature
learning for machine learning with graphs!

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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 4
 ¡ 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
• ….
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 5
 Example
2D embedding of nodes of the Zachary’s
¡
Karate
• Zachary Club network:
s Karate Network:

Image from: Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014.
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 6
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 ¡ Assume we have a 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 ÷ø
è

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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 9
Goal: similarity 𝑢, 𝑣 ≈ 𝐳"# 𝐳$
in the original network Similarity of the embedding

Need to define!

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 10
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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 11
 ¡ 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
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 12
 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
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 13
 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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 14
 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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 15
 ¡ Encoder + Decoder Framework
§ Shallow encoder: embedding lookup
§ Parameters to optimize: 𝐙 which contains node
embeddings 𝐳' for all nodes 𝑢 ∈ 𝑉
§ We will cover deep encoders (GNNs) in Lecture 6

§ Decoder: based on node similarity.

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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 16
 ¡ 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.

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 17
 ¡ 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.
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 18
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 𝑆 𝑥 = !" . '()

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 20
 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.
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 21
 probability that u
"
𝐳! 𝐳# ≈ and v co-occur on
a random walk over
the graph

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 22
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”

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 23
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
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 24
 ¡ 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 𝑅
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 25
 ¡ Given 𝐺 = (𝑉, 𝐸),
¡ Our goal is to learn a mapping 𝑓: 𝑢 → ℝ$ :
𝑓 𝑢 = 𝐳%
¡ Log-likelihood objective:
max ' log P(𝑁2 (𝑢)| 𝐳' )
/
' ∈1
§ 𝑁% (𝑢) is the neighborhood of node 𝑢 by strategy 𝑅

¡ Given node 𝑢, we want to learn feature

representations that are predictive of the nodes
2/14/21
in its random walk neighborhood 𝑁& (𝑢)
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 26
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 𝑁' (𝑢)
max F log P(𝑁' (𝑢)| 𝐳$ ) Maximum likelihood objective
(
$ ∈*
*𝑁! (𝑢) can have repeat elements since nodes can be visited multiple times on random walks
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 27
 Equivalently,
ℒ=( ( −log(𝑃(𝑣|𝐳1 ))
1∈3 4∈5' (1)

• Intuition: Optimize embeddings 𝑧$ to maximize

the likelihood of random walk co-occurrences
• Parameterize 𝑃(𝑣|𝐳𝑢 ) using softmax:
Why softmax?
exp(𝐳$+ 𝐳" ) We want node 𝑣 to be
𝑃 𝑣 𝐳$ = most similar to node 𝑢
∑,∈* exp(𝐳$+ 𝐳, ) (out of all nodes 𝑛).
Intuition: ∑" exp 𝑥" ≈
max exp(𝑥" )
"
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 28
Putting it all together:
exp(𝐳!( 𝐳$ )
ℒ=# # − log( ( )
∑)∈# exp(𝐳! 𝐳) )
!∈# $∈%3 (!)

sum over all sum over nodes 𝑣 predicted probability of 𝑢

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

Optimizing random walk embeddings =

Finding embeddings 𝐳𝒖 that minimize L
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 29
But doing this naively is too expensive!

exp(𝐳!( 𝐳$ )
ℒ=# # −log( ( )
∑)∈# exp(𝐳! 𝐳) )
!∈# $∈%3 (!)

Nested sum over nodes gives

O(|V|2) complexity!

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 30
 But doing this naively is too expensive!

exp(𝐳!( 𝐳$ )
ℒ=# # −log( ( )
∑)∈# exp(𝐳! 𝐳) )
!∈# $∈%3 (!)

The normalization term from the softmax is

the culprit… can we approximate it?

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 31
 Why is the approximation valid?
Technically, this is a different objective. But

¡ Solution: Negative sampling Negative Sampling is a form of Noise

Contrastive Estimation (NCE) which approx.
maximizes the log probability of softmax.
New formulation corresponds to using a

exp 𝐳'4 𝐳(
logistic regression (sigmoid func.) to
distinguish the target node 𝑣 from nodes 𝑛!
log( ) sampled from background distribution 𝑃" .

∑9∈1 exp 𝐳'4 𝐳9 More at [Link]

≈ log 𝜎 𝐳'4 𝐳( − ∑8567 log 𝜎 𝐳'4 𝐳9! , 𝑛5 ~𝑃1

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 “negative samples” 𝑛.
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 32
 exp 𝐳'4 𝐳( random distribution
log( ) over nodes
∑9∈1 exp 𝐳'4 𝐳9
8
≈ log 𝜎 𝐳'4 𝐳( −' log 𝜎 𝐳'4 𝐳9! , 𝑛5 ~𝑃1
567

§ 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
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 33
§ After we obtained the objective function, how do
we optimize (minimize) it?
ℒ=* * −log(𝑃(𝑣|𝐳8 ))
8∈: ;∈<$ (8)

§ Gradient Descent: a simple way to minimize ℒ :

§ Initialize 𝑧$ at some randomized value for all 𝑖.

§ Iterate until convergence.

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

$ℒ
§ For all 𝑖, make a step towards the direction of derivative:𝑧' ← 𝑧' − 𝜂 .
$&$
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 34
§ Stochastic Gradient Descent: Instead of evaluating
gradients over all examples, evaluate it for each
individual training example.
§ Initialize 𝑧" at some randomized value for all 𝑖.

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

!∈+% (#)
&ℒ (")
§ Sample a node 𝑖, for all 𝑗 calculate the derivative &(#
.
&ℒ (")
§ For all 𝑗, update:𝑧) ← 𝑧) − 𝜂 &( .
#

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 35
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(𝑃(𝑣|𝐳% ))
%∈6 7∈8& (%)
We can efficiently approximate this using
negative sampling!
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 36
 ¡ 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., 2013)
§ The issue is that such notion of similarity is too constrained
¡ How can we generalize this?
Reference: Perozzi et al. 2014. DeepWalk: Online Learning of Social Representations. KDD.
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 37
 ¡ 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 𝑁9 (𝑢) of node 𝑢 leads to rich node
embeddings
¡ Develop biased 2nd order random walk 𝑅 to
generate network neighborhood 𝑁9 (𝑢) of node 𝑢
Reference: Grover et al. 2016. node2vec: Scalable Feature Learning for Networks. KDD.
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 38
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, 2016).

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).
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 39
 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- 012 𝑢 = { 𝑠 , 𝑠 , 𝑠 } Local microscopic view
and edges. A typical solution involves hand-engineering domain-
specific features based3 4on expert 5 knowledge. Even if one discounts
node’s
the tedious work of feature engineering, such features are usually
proce-
leads to
𝑁 612 𝑢 = { 𝑠 , 𝑠 , 𝑠 } Global macroscopic view
designed for specific 7 tasks 8 and 9 do not generalize across different
2/14/21 prediction tasks.
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 40
 u

BFS: DFS:
Micro-view of Macro-view of
neighbourhood neighbourhood

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 41
Biased fixed-length random walk 𝑹 that given a
node 𝒖 generates neighborhood 𝑵𝑹 𝒖
¡ Two parameters:
§ Return parameter 𝒑:
§ Return back to the previous node
§ In-out parameter 𝒒:
§ Moving outwards (DFS) vs. inwards (BFS)
§ Intuitively, 𝑞 is the “ratio” of BFS vs. DFS

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 42
Biased 2nd-order random walks explore network
neighborhoods:
§ Rnd. walk just traversed edge (𝑠7 , 𝑤) and is now at 𝑤
§ Insight: Neighbors of 𝑤 can only be:
Same distance to 𝒔𝟏
s2 s3
w Farther from 𝒔𝟏

u s1
Back to 𝒔𝟏

Idea: Remember where the walk came from

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 43
 ¡ Walker came over edge (𝐬𝟏 , 𝐰) and is at 𝐰.
Where to go next?
s2 1
1/𝑞 s3 1/𝑝, 1/𝑞, 1 are
w unnormalized
1/𝑞
s1 probabilities
u 1/𝑝 s4

¡ 𝑝, 𝑞 model transition probabilities

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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 44
 ¡ Walker came over edge (𝐬𝟏 , 𝐰) and is at 𝐰.
Where to go next?
Target 𝒕 Prob. Dist. (𝒔𝟏 , 𝒕)
s2 1
1/𝑞 s3 s1 1/𝑝 0
w w → s2 1 1
1/𝑞
u s1 1/𝑝 s4
s3 1/𝑞 2
s4 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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 45
 ¡ 1) Compute random walk probabilities
¡ 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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 46
 ¡ Different kinds of biased random walks:
§ Based on node attributes (Dong et al., 2017).
§ Based on learned weights (Abu-El-Haija et al., 2017)

¡ Alternative optimization schemes:

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

¡ Network preprocessing techniques:

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

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 47
 ¡ 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 2 nodes are connected
§ Neighborhood overlap (covered in Lecture 2)
§ Random walk approaches (covered today)

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 48
 ¡ 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, 2017 survey)
¡ Random walk approaches are generally more
efficient
¡ In general: Must choose definition of node
similarity that matches your application!

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 49
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
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 51
 Simple idea 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., 2016 to classify
molecules based on their graph structure
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 52
 ¡ Idea 2: Introduce a “virtual node” to
represent the (sub)graph and run a standard
graph embedding technique

¡ Proposed by Li et al., 2016 as a general

technique for subgraph embedding
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 53
 States in anonymous walks correspond to the
index of the first time we visited the node in a
random walk

Anonymous Walk Embeddings, ICML 2018 [Link]

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 54
 ¡ Agnostic to the identity of the nodes visited
(hence anonymous)
¡ Example RW1:

¡ Step 1: node A node 1

¡ Step 2: node B node 2 (different from node 1)
¡ Step 3: node C node 3 (different from node 1, 2)
¡ Step 4: node B node 2 (same as the node in step 2)
¡ Step 5: node C node 3 (same as the node in step 3)

¡ Note: RW2 gives the same anonymous walk

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 55
 Number of anonymous walks grows exponentially:
§ There are 5 anon. walks 𝑤" of length 3:
𝑤* =111, 𝑤+ =112, 𝑤, = 121, 𝑤- = 122, 𝑤. = 123
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 56
 ¡ Simulate anonymous walks 𝑤. of 𝑙 steps and
record their counts
¡ Represent the graph as a probability
distribution over these walks

¡ For example:
§ Set 𝑙 = 3
§ Then we can represent the graph as a 5-dim vector
§ Since there are 5 anonymous walks 𝑤# of length 3: 111, 112,
121, 122, 123
§ 𝒁𝑮 [𝑖] = probability of anonymous walk 𝑤5 in 𝐺

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 57
 ¡ Sampling anonymous walks: Generate
independently a set of 𝑚 random walks
¡ Represent the graph as a probability distribution
over these walks

¡ How many random walks 𝑚 do we need?

§ We want the distribution to have error of more than
𝜀 with prob. less than 𝛿: For example:
There are 𝜂 = 877
2 anonymous walks of length
𝑚 = H (log 2I − 2 − log 𝛿 ) 𝑙 = 7. If we set
𝜀 𝜀 = 0.1 and 𝛿 = 0.01 then
we need to generate
𝑚=122,500 random walks
where: 𝜂 is the total number of anon. walks of length 𝑙.
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 58
 Rather than simply represent each walk by the
fraction of times it occurs, we learn embedding
𝒛𝒊 of anonymous walk 𝒘𝒊
¡ Learn a graph embedding 𝒁𝑮 together with all
the anonymous walk embeddings 𝒛𝒊
𝑍 = {𝑧. : 𝑖 = 1 … 𝜂}, where 𝜂 is the number of
sampled anonymous walks.

How to embed walks?

¡ Idea: Embed walks s.t. the next walk can be
predicted
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 59
 ¡ A vector parameter 𝒛𝑮 for input graph
§ The embedding of entire graph to be learned
¡ Starting from node 1: Sample anonymous
random walks, e.g. 𝑤& 𝑤' 𝑤( 𝑤)

¡ Learn to predict walks that co-occur in 𝚫-size

window (e.g. predict 𝑤; given 𝑤< , 𝑤= if Δ = 1)
¡ Objective: 231

max ? log 𝑃(𝑤/ |𝑤/31 , … , 𝑤/41 , 𝒛𝑮 )

/01
¡ Sum the objective over all nodes in the graph

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 60
 ¡ Run 𝑻 different random walks from 𝒖 each of length 𝒍:
𝑁. 𝑢 = 𝑤7' , 𝑤H' … 𝑤J'
¡ Learn to predict walks that co-occur in 𝚫-size window
¡ Estimate embedding 𝑧5 of anonymous walk 𝑤5
Let 𝜂 be number of all possible walk embeddings
JPO
1
Objective: max : log 𝑃 𝑤N {𝑤NPO , … , 𝑤NQO , 𝒛𝑮 )
K,M 𝑇
N6O
All possible walks
123(4 5& )
§ 𝑃 𝑤, {𝑤,-., … , 𝑤,/., 𝒛𝑮 ) = ∑)
(require negative sampling)
$'( 123(4(5$ ))
7 .
§ 𝑦 𝑤, = 𝑏 + 𝑈 ⋅ 𝑐𝑎𝑡( ∑ 𝑧 , 𝒛𝑮 )
8. '9-. '
*
§ 𝑐𝑎𝑡( ∑,-./, 𝑧- , 𝒛𝑮 ) means an average of anonymous walk embeddings in window,
+,
concatenated with the graph embedding 𝒛𝑮
§ 𝑏 ∈ ℝ, 𝑈 ∈ ℝ1 are learnable parameters. This represents a linear layer.
Anonymous Walk Embeddings, ICML 2018 [Link]
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 61
 ¡ We obtain the graph
embedding 𝒛𝑮 (learnable Overall Architecture
parameter) after
optimization
¡ Use 𝒛𝑮 to make predictions
(e.g. graph classification)
§ Option1: Inner product
Kernel 𝒛2𝑮𝟏 𝒛𝑮𝟐 (Lecture 2)
§ Option2: Use a neural
network that takes 𝒛𝑮 as
input to classify
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 62
 We discussed 3 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

¡ Approach 3: Anonymous Walk Embeddings

§ Idea 1: Sample the anon. walks and represent the
graph as fraction of times each anon walk occurs
§ Idea 2: Embed anonymous walks, concatenate their
embeddings to get a graph embedding
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 63
 ¡ We will discuss more advanced ways to obtain
graph embeddings in Lecture 8.
¡ We can hierarchically cluster nodes in graphs,
and sum/avg the node embeddings according
to these clusters.

2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 64
 ¡ 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: 𝑓(𝑧2 , 𝑧3 )= 𝑔([𝑧2 , 𝑧3 ])
§ Hadamard: 𝑓(𝑧2 , 𝑧3 )= 𝑔(𝑧2 ∗ 𝑧3 ) (per coordinate product)
§ Sum/Avg: 𝑓(𝑧2 , 𝑧3 )= 𝑔(𝑧2 + 𝑧3 )
§ Distance: 𝑓(𝑧2 , 𝑧3 )= 𝑔(||𝑧2 − 𝑧3 ||4 )
§ Graph classification: graph embedding 𝒛𝑮 via aggregating
node embeddings or anonymous random walks.
Predict label based on graph embedding 𝑧D
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 65
 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 and Anonymous Walk Embeddings
2/14/21 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 66