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

Charilaos Kanatsoulis, Stanford University
[Link]
  Colab 3 is due today
 Homework 3 is due next Thursday 11/13
o Recitation session recording on Ed
o Project Milestone deadline has been pushed
back: now due Tuesday 11/11
o Colab 4 will be released today
o Homework 2 grades will be released today!
o Regrade requests open until 11/13
o Practice exam will be released today (on Ed)

11/6/2025 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 2
CS224W: Machine Learning with Graphs
Charilaos Kanatsoulis, Stanford University
[Link]
 Commerce Finance Social Media

11/6/2025 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 4
 Which products will a user
purchase in the next 7
days?

 Will an active user churn

in the next 90 days?
 What will be the total
sales for each product in
the next 30 days?

11/6/2025 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 5
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 6
 $20

$80

$15

$20

$80

$80

$15
Users Sales Products
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 7
ML in the language of
graphs:
▪ Node-level:
▪ Churn
▪ Life-time value
▪ Next best action
$20
▪ Link-level:
$80
▪ Product affinity
$15
▪ Recommendations
$20
▪ Graph-level:
$80
▪ Fraud, money
$80
laundering
$15
Users Sales Products
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 8
Graph Problem Graph ML Solutions

Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 9

 Training Table: A special table containing
training labels
▪ (entity ID, time, labels)
▪ Classification, Regression, Multi-class
Training Table

Entity ID Timestamp Label

99 10172024 1
99 10182024 1
… … …
100 10172024 1
100 10182024 0
… … …

Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 10

Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 11
Relational Entity Graph:
Create connections via
primary-foreign keys

$20

$80

$15

$20

$80

$80

$15
Users Sales Products
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 12
Training labels together with timestamps are
attached to the graph

May ‘23 Churn

$20
June ’23 Active
$80
May ‘23 Churn
$15
June ‘23 Active
$20

June ‘23 Active $80

April ’23 Active $80

May ’23 Churn $15

June ‘23 Active

Users Sales Products

Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 13

Node’s neighborhood defines a computation graph
Nodes learn how to optimally use information from neighbors to
obtain enhanced node representations

$20
May ‘23 Churn
$80

$15

$20

$80

$80

$15
June ‘23 Active
Users Sales Products

Entity Graph GNN computation graphs

Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link]
Why not use an LLM?

15
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 16
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 17
 LLMs are not trained to understand and
effectively learn from the relational
nature of Databases
 Database prediction is NOT sequence
modeling
 LLMs are NOT trained to predict the
future
 Context size is limited
Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 18
 Stay tuned for more discussion on LLMs later!
19
CS224W: Machine Learning with Graphs
Charilaos Kanatsoulis, Stanford University
[Link]
Relational Databases: multi-modal, multi-scale
information
Relational Databases: multi-modal, multi-scale
information
Entity level: Text, image, numerical, categorical,
timestamp
Relational Databases: multi-modal, multi-scale
information
Entity level: Text, image, numerical, categorical,
timestamp

Database level: Relational structure, Temporal Structure

 Tripartite patterns Cycle patterns

Structure changes over time!

24
CS224W: Machine Learning with Graphs
Charilaos Kanatsoulis, Stanford University
[Link]
26
27
 Edges in relational entity graphs are defined by primary–foreign key
links that merely record table connectivity without semantics.
 Edges in relational entity graphs are defined by primary–foreign key
links that merely record table connectivity without semantics.
 Junction tables are introduced, decomposing each many-to-many
association into a pair of one-to-many links.
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
11/6/2025 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 31
rel-amazon

rel-hm
rel-amazon rel-F1

rel-hm
 rel-amazon rel-F1

rel-hm

bridge structure hub structure

 (1) Imbalance: junction node are 1-hop neighbors and more
informative node become 2-hop.

 (2) Redundancy: information from the source node is passed to the

junction node in the first hop and routed back to itself in the second,
aggregated with the junction and 2-hop node information.
 Informal: An atomic route is a simple path between pink node-types.
 Atomic routes can be derived automatically without manual intervention or
domain-expert knowledge.

Tianlang Chen, Charilaos Kanatsoulis, and Jure Leskovec. "RelGNN: Composite Message Passing for Relational Deep Learning", In Forty-second International Conference on Machine

Learning (ICML), 2025

 Composite Message Passing: aggregates messages along atomic
routes in a single step.

 Instantiation example:

Tianlang Chen, Charilaos Kanatsoulis, and Jure Leskovec. "RelGNN: Composite Message Passing for Relational Deep Learning", In Forty-second International Conference on Machine

Learning (ICML), 2025

 rel-F1 rel-trial rel-amazon
Predict if the driver will qualify in the Predict the success rate of Predict the list of distinct items each
top-3 for a race in the next 1 month. a trial site in the next 1 year. customer will purchase and give a
detailed review in the next 3
months.

 RelGNN achieves SOTA performance on the vast majority of

tasks from RelBench, with improvements of up to 25%.
Tianlang Chen, Charilaos Kanatsoulis, and Jure Leskovec. "RelGNN: Composite Message Passing for Relational Deep Learning", In Forty-second International Conference on Machine

Learning (ICML), 2025

CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
 J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020

 Key components of Transformer

▪ (1) tokenizing
▪ (2) positional encoding
▪ (3) self-attention

 Key question: What should these be for a graph input?

Transformer
(3) self-attention
(2) Positional
encoding
+ + + + + + + +
𝑥1 𝑥2 𝑥3 𝑥𝑖 (1) Tokens

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 40

 J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020

 Key components of Transformer

▪ (1) tokenizing How to chose these
▪ (2) positional encoding
▪ (3) self-attention for graph data?
 Key question: What should these be for a graph input?

Transformer
(3) self-attention
(2) Positional
encoding
+ + + + + + + +
𝑥1 𝑥2 𝑥3 𝑥𝑖 (1) Tokens

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 41

 J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020

 A graph Transformer must take the

following inputs:  Key components of Transformer
▪ (1) tokenizing
▪ (1) Node features?
▪ (2) positional encoding
▪ (2) Adjacency information? ▪ (3) self-attention
▪ (3) Edge features?

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 42

 J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020

 A graph Transformer must take the

following inputs:  Key components of Transformer
▪ (1) tokenizing
▪ (1) Node features?
▪ (2) positional encoding
▪ (2) Adjacency information? ▪ (3) self-attention
▪ (3) Edge features?

 There are many ways to do this

 Different approaches correspond to different
“matchings” between graph inputs (1), (2),
(3) transformer components (1), (2), (3)

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 43

 J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020

 A graph Transformer must take the

following inputs:  Key components of Transformer
▪ (1) tokenizing
▪ (1) Node features?
▪ (2) positional encoding
▪ (2) Adjacency information? ▪ (3) self-attention
▪ (3) Edge features?

 There are many ways to do this

 Different approaches correspond to different
“matchings” between graph inputs (1), (2),
(3) transformer components (1), (2), (3)

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 44

 How to use PEARL: in practice?
▪ Step 1: Sample node ids from a probability distribution.
▪ Step 2: Process each set of node samples independently via a GNN.
▪ Step 3: Summarize the outputs via empirical expectation.
▪ Step 4: concatenate PEARL embeddings with node features X.
▪ Step 5: pass through main GNN/Transformer as usual.
▪ Step 6: Backpropagate gradients to train PEARL + Prediction model jointly.

11/6/2025 Joshua
Jure Leskovec,
Robinson,
Stanford
Stanford
CS224W:
CS224W:
Machine
Machine
Learning
Learning
with
with
Graphs
Graphs 45
(Text) Transformers
- An input token is represented with 2 elements
○ Token id, position
feature structure

46
Graph Transformers
- An input token is represented with 2 elements
○ Node feature, graph positional encoding
feature structure

47
Graph Transformers
- An input token is represented with 2 elements
○ Node feature, graph positional encoding
feature structure

- Most GTs are designed

for homogeneous, static
graphs
- However, for additional
RDL complexity such as
heterogeneity and
temporality, this design
needs to be improved
48
 J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020

 A graph Transformer must take the

following inputs:  Key components of Transformer
▪ (1) tokenizing
▪ (1) Node features?
▪ (2) positional encoding
▪ (2) Adjacency information? ▪ (3) self-attention
▪ (3) Edge features?
▪ (3) Node types
▪ (4) Timestamp

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 49

In Relational Graph Transformer
- We use multiple elements to represent the graph structure
○ Node feature, <multiple information elements>
structure

50
  Designed for homogeneous graphs

 No temporal dynamics

 Computational overhead

 Graph changes over time

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 51

  The relational entity graph is:
▪ Large-scale
▪ Heterogeneous
▪ Temporal

 Add a categorical encoding to capture the

heterogeneity
 Add a time encoding to capture the temporal
structure

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 52

  Challenge: The relational entity graph is
▪ Large-scale

 Solution: We need to sample a subgraph

around the seed node

11/6/2025 Joshua Robinson, Stanford CS224W: Machine Learning with Graphs 53

Relational Entity Graphs
- Training (seed) nodes which correspond to node-types
with respect to which tasks are defined.
- We are going to sample a context (subgraph) around
each seed node.
54
Token Preparation (Sampling Stage)
- For each training node ( ), a fixed set of K tokens ( ) from
local neighborhood (e.g., up to 2 hops) is selected through a
temporal-aware sampling.
- We encode structure with a GNN positional encoding for each
node in the context + hop distance from seed node.

56
Token Preparation (Sampling Stage)
- For each training node ( ), a fixed set of K tokens ( ) from
local neighborhood (e.g., up to 2 hops) is selected through a
temporal-aware sampling.
- Each node in K set is represented by a 5-tuple:
(node feature, node type, hop distance, time, GNN PE)

57
seed nodes local tokens

59
 node node type hop time subgraph
feature distance

seed nodes local tokens

Token Feature Encoders

- Each node in K set is represented by a 5-tuple:
(node feature, node type, hop distance, time, GNN PE)

60
 tokens fed to
Transformer

element Torch Frame

nn Embedding nn Embedding Time Encoder GNN Encoder

wise
Encoder

encoders node node type hop time subgraph

feature distance

seed nodes local tokens

Token Feature Encoders

- Each node in K set is represented by a 5-tuple:
(node feature, node type, hop distance, time, GNN PE)
- Each of these elements is passed to a feature encoder and the
combination becomes the token features for Transformer Network
61
 tokens fed to
Transformer

element Torch Frame

nn Embedding nn Embedding Time Encoder GNN Encoder

wise
Encoder

encoders node node type hop time subgraph

feature distance

seed nodes local tokens

Token Feature Encoders

- Each node in K set is represented by a 5-tuple:
(node feature, node type, hop distance, time, GNN PE)
- Each of these elements is passed to a feature encoder and the
combination becomes the token features for Transformer Network
62
Takeaway:
- Contribution of the multi-element tokenization strategy to
capture arbitrary structure in relational data

66
Takeaway:
- Relational Graph Transformers improve over GNNs

67
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
[Link]
  They are schema- and task- specific

 The do not transfer knowledge from one

database to another or one task to another
 Do not generalize to new databases or tasks
11/6/2025 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 69
  Goal: Bring the success of foundation models
(LLMs, ViT) to relational data.

11/6/2025 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, [Link] 70
71
Relational Graph Transformer is the backbone for
first Relational Foundation Model
with zero-shot capabilities powered by ICL

72
73