Welcome to CS224W, Machine Learning with Graphs.
My name is Jure Leskovec.
I'm Associate Professor of Computer Science at
Stanford University and I will be your instructor.
What I'm going to do in the first lecture is to motivate and get you excited about graph,
uh, structured data and how can we apply novel machine learning methods to it?
So why graphs?
Graphs are a general language for describing and an-
analyzing entities with the relations in interactions.
This means that rather than thinking of the world
or a given domain as a set of isolated datapoints,
we really think of it in terms of networks and relations between these entities.
This means that there is
the underla- ler- underlying graph of relations between the entities,
and these entities are related, uh,
to each other, uh,
according to these connections or the structure of the graph.
And there are many types of data that can naturally be
represented as graphs and modeling these graphical relations,
these relational structure of the underlying domain,
uh, allows us to, uh,
build much more faithful,
much more accurate, uh,
models of the underlying,
uh, phenomena underlying data.
So for example, we can think of a computer networks, disease pathways, uh,
networks of particles in physics, uh,
networks of organisms in food webs,
infrastructure, as well as events can all be represented as a graphs.
Similarly, we can think of social networks,
uh, economic networks, communication networks,
say patients between different papers,
Internet as a giant communication network,
as well as ways on how neurons in our brain are connected.
Again, all these domains are inherently network or graphs.
And that representation allows us to capture
the relationships between different objects or entities,
uh, in these different, uh, domains.
And last, we can take knowledge and
represent facts as relationships between different entities.
We can describe the regulatory mechanisms in our cells,
um, as processes governed by the connections between different entities.
We can even take scenes from real world and presented them
as graphs of relationships between the objects in the scene.
These are called scene graphs.
We can take computer code software and represent it as a graph of, let's say,
calls between different functions or as
a structure of the code captures by the abstract syntax tree.
We can also naturally take molecules which are composed of nodes, uh,
of atoms and bonds as a set of graphs, um,
where we represent atoms as nodes and their bonds as edges between them.
And of course, in computer graphics,
we can take three-dimensional shapes and- and represent them, um, as a graphs.
So in all these domains,
graphical structure is the- is
the important part that allows us to model the under- underlying domain,
underlying phenomena in a fateful way.
So the way we are going to think about graph
relational data in this class is that there are essentially two big,
uh, parts, uh, of data that can be represented as graphs.
First are what is called natural graphs or networks,
where underlying domains can naturally be represented as graphs.
For example, social networks,
societies are collection of seven billion individuals and connections between them,
communications and transactions between electronic devices, phone calls,
financial transactions, all naturally form, uh, graphs.
In biomedicine we have genes,
proteins regulating biological processes,
and we can represent interactions between
these different biological entities with a graph.
And- and as I mentioned,
connections between neurons in our brains are,
um, essentially a network of, uh, connections.
And if we want to model these domains,
really present them as networks.
A second example of domains that also have relational structure,
um, where- and we can use graphs to represent that relational structure.
So for example, information and knowledge is many times organized and linked.
Software can be represented as a graph.
We can many times take, uh,
datapoints and connect similar data points.
And this will create our graph,
uh, a similarity network.
And we can take other, um, uh,
domains that have natural relational structure like molecules,
scene graphs, 3D shapes, as well as,
you know, in physics,
we can take particle-based simulation to simulate how,
uh, particles are related to each other through,
uh, and they represent this with the graph.
So this means that there are many different domains, either, uh,
as natural graphs or natural networks,
as well as other domains that can naturally be
modeled as graphs to capture the relational structure.
And the main question for this class that we are
going to address is to talk about how do we take
advantage of this relational structure to be- to make better, more accurate predictions.
And this is especially important because
couplings domains have reached a relational structure,
uh, which can be presented, uh, with a graph.
And by explicitly modeling these relationships,
we will be able to achieve, uh,
better performance, build more, uh,
accurate, uh, models, make more accurate predictions.
And this is especially interesting and important in the age of deep learning,
where the- today's deep learning modern toolbox is specialized for simple data types.
It is specialized for simple sequences, uh, and grids.
A sequence is a, uh,
like text or speech has this linear structure and there
has- there are been amazing tools developed to analyze this type of structure.
Images can all be resized and have this spatial locality so- so
they can be represented as fixed size grids or fixed size standards.
And again, deep learning methodology has been very good at processing this type of,
uh, fixed size images.
However, um, graphs, networks are much harder to process because they are more complex.
First, they have arbitrary size and arb- and complex topology.
Um, and there is also no spatial locality as in grids or as in text.
In text we know left and right,
in grids we have up and down, uh, left and right.
But in networks, there is no reference point,
there is no notion of,
uh, uh, spatial locality.
The second important thing is there is no reference point,
there is no fixed node ordering that would allow us,
uh, uh, to do, uh,
to do deep learning.
And often, these networks are dynamic and have multi-model features.
So in this course,
we are really going to, uh,
talk about how do we develop neural networks that are much more broadly applicable?
How do we develop neural networks that are applicable to complex data types like graphs?
And really, it is relational data graphs that are the- the new frontier,
uh, of deep learning and representation learning, uh, research.
So intuitively, what we would like to do is we would like to do,
uh, build neural networks,
but on the input we'll take, uh, uh,
our graph and on the output,
they will be able to make predictions.
And, uh, these predictions can be at the level of individual nodes,
can be at the level of pairs of nodes or links,
or it can be something much more complex like a brand new generated graph or, uh,
prediction of a property of a given molecule that can be represented,
um, as a graph on the input.
And the question is,
how do we design this neural network architecture
that will allow us to do this end to end,
meaning there will be no human feature engineering, uh, needed?
So what I mean by that is that, um,
in traditional, uh, machine learning approaches,
a lot of effort goes into des- designing proper features,
proper ways to capture the structure of the data so that machine learning models can,
uh, take advantage of it.
So what we would like to do in this class,
we will talk mostly about representation learning
where these feature engineering step is taken away.
And basically, as soon as we have our graph,
uh, uh, repr- graph data,
we can automatically learn a good representation of the graph so that it can be used for,
um, downstream machine learning algorithm.
So that a presentation learning is about automatically extracting or learning features,
uh, in the graph.
The way we can think of representation learning is to map
nodes of our graph to a d-dimensional embedding,
to the d-dimensional vectors,
such that seeming that are nodes in the network are
embedded close together in the embedding space.
So the goal is to learn this function f that will take
the nodes and map them into these d-dimensional,
um, real valued vectors,
where this vector will call this, uh, representation, uh,
or a feature representation or an embedding of a given node,
an embedding of an entire graph,
an embedding of a given link,
um, and so on.
So a big part of our class we'll be, uh,
investigating and learning about latest presentation learning,
deep learning approaches that can be applied,
uh, to graph, uh, structured data.
And we are going to, uh, uh,
talk about many different topics in
machine learning and the representation learning for graph structure data.
So first, we're going to talk about traditional methods
for machine learning and graphs like graphlets and graph kernels.
We are then going to talk about methods to generate, um,
generic node embeddings, methods like DeepWalk and Node2Vec.
We are going to spend quite a bit of time talking about
graph neural networks and popular graph neural network architectures like graph,
uh, convolutional neural network,
the GraphSage architecture or Graph Attention Network, uh, architecture.
We are also going to study the expressive power of graph neural networks,
um, the theory behind them,
and how do we scale them up to very large graphs.
Um, and then in the second part of this course,
we are also going to talk about heterogeneous graphs,
knowledge graphs, and applications,
uh, to logical reasoning.
We're learning about methods like TransE and BetaE.
We are also going to talk about how do we build deep generative models for
graphs where we can think of the prediction of the model to
be an entire newly generated graph.
And we are also going to discuss applications to biomedicine, um,
various scientific applications, as well
as applications to industry in terms of recommender systems,
fraud detection, and so on.
So here is the outline of this course.
Week by week, 10 weeks, starting, uh,
starting today and all the way to the middle of March,
um, where, uh, the- the course will finish.
We will have 20 lectures and we will cover all the topics,
uh, that I have discussed,
and in particular focus on
graph neural networks and the representation learning in graphs.