01 Intro
01 Intro
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: http://cs224w.Stanford.edu
Thu, 10/3 4. A general perspective on GNNs Thu, 11/7 13. Relational Deep Learning
Tue, 10/8 5. GNN augmentation and training Tue, 11/12 14. Advanced topics in GNNs
Tue, 10/15 7. Designing Powerful GNNs Tue, 11/19 16. Geometric Deep Learning
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 18
¡ Colabs 0 and 1 will be released on our course
website at 3pm Thursday (9/26)
¡ Colab 0:
§ Does not need to be handed-in
¡ Colab 1:
§ Due on Thursday 10/10 (2.5 weeks from today)
§ Submit written answers and code on Gradescope
§ Will cover material from Lectures 1-4, but you
can get started right away!
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 19
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
http://cs224w.stanford.edu
Why Graphs?
Graphs are a general
language for describing and
analyzing entities with
relations/interactions
Text/Speech
vs.
Text
Networks Images
¡ No fixed node ordering or reference point
¡ Often dynamic and have multimodal features
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs 30
How can we develop neural networks
that are much more broadly
applicable?
Graphs are the new frontier
of deep learning
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs 31
ICLR 2023 keywords
Actor 3 Albert
Protein 1 Protein 2
Protein 5
Protein 9 |N|=4
|E|=4
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs 34
¡ A heterogeneous graph is defined as
𝑮 = 𝑽, 𝑬, 𝑹, 𝑻
§ Nodes with node types 𝑣! ∈ 𝑉
§ Edges with relation types 𝑣! , 𝑟, 𝑣" ∈ 𝐸
§ Node type 𝑇 𝑣!
§ Relation type 𝑟 ∈ 𝑅
§ Nodes and edges have attributes/features
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 35
Biomedical Knowledge Graphs Academic Graphs
Example node: Migraine Example node: ICML
Example edge: (fulvestrant, Treats, Breast Neoplasms) Example edge: (GraphSAGE, NeurIPS)
Example node type: Protein Example node type: Author
Example edge type (relation): Causes Example edge type (relation): pubYear
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 36
¡ How to build a graph:
§ What are nodes?
§ What are edges?
¡ Choice of the proper network representation
of a given domain/problem determines our
ability to use networks successfully:
§ In some cases, there is a unique, unambiguous
representation
§ In other cases, the representation is by no means
unique
§ The way you assign links will determine the nature
of the question you can study
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs 37
Undirected Directed
¡ Links: undirected ¡ Links: directed
(symmetrical, reciprocal)
L D
A B
F M C
I
D
E
B G G
A
H
F
C
¡ Other considerations:
§ Weights § Types
§ Properties § Attributes
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs 38
¡ Bipartite graph is a graph whose nodes can A
be divided into two disjoint sets U and V such that
every link connects a node in U to one in V; that is, B
U and V are independent sets
C
¡ Examples: D
§ Authors-to-Papers (they authored)
E
§ Actors-to-Movies (they appeared in)
§ Users-to-Movies (they rated)
U V
§ Recipes-to-Ingredients (they contain)
¡ “Folded” networks:
§ Author collaboration networks
§ Movie co-rating networks
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs 39
CS224W: Machine Learning with Graphs
Jure Leskovec, Stanford University
http://cs224w.stanford.edu
Node level
Graph-level
Community
prediction,
(subgraph)
Graph
level
generation
Edge-level
? Node-level Graph-level
Link-level
? B
F
?
A
D E
G
C
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 43
? ?
?
? Machine
Learning
?
Node classification
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 44
Goal: Characterize the structure and position of
a node in the network:
§ Node degree
§ Node importance & position
§ E.g., Number of shortest paths passing through a node
§ E.g., Avg. shortest path length to other nodes
§ Substructures around B
the node F
A
D E
G
C
H
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 45
Graphlet Degree Vector
et Degree
aphlet Vector
Degree Vector
An automorphism “orbit” takes into account the
symmetries
¡ Graphlets: of the graph vector of rooted subgraphs
A count
rphism “orbit”“orbit”
utomorphism takes into account
takes the
into account the
theat
smetries
of The ofathe
graphgiven
graphletgraphnode.
degree vector is a feature vector with
¡ Example:
the frequency of the node in each
All possible orbit on
graphlets position
up to 3 nodes
et degreedegree
graphlet vector vector
is a feature vector vector
is a feature with with
ncy of the node
frequency of theinnode
eachin orbit
eachposition
orbit position
𝑢
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 46
Algorithm Dataset
BlogCatalog PPI Wikipe
Spectral Clustering 0.0405 0.0681 0.039
DeepWalk 0.2110 0.1768 0.127
LINE 0.0784 0.1447 0.116
node2vec 0.2581 0.1791 0.155
node2vec settings (p,q) 0.25, 0.25 4, 1 4, 0.
Different ways to label nodes of the network: Gain of node2vec [%] 22.3 1.3 21.8
? B
F
A
D E
G
C
? H
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 52
¡ Users interacts with items
§ Watch movies, buy merchandise, listen to music
§ Nodes: Users and items
§ Edges: User-item interactions
¡ Goal: Recommend items users might like
Users
Interactions
30%
, 65%
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs
prob. prob. 55
Zitnik et al., Modeling Polypharmacy Side Effects with Graph Convolutional Networks, Bioinformatics 2018
¡ For example:
B
F
A
D E
G
C
H
10/4/24 Jure Leskovec, Stanford CS224W: Machine Learning with Graphs, http://cs224w.stanford.edu 59
¡ a
Stokes, Jonathan M., et al. "A deep learning approach to antibiotic discovery."
Cell 180.4 (2020): 688-702.