Stanford CS224W: ML with Graphs | 2021 | Lecture 6.1 - Introduction to Graph Neural Networks

Summary

This lecture introduces deep learning for graphs, focusing on graph neural networks (GNNs) and their applications. The professor reviews previous topics like node embeddings, where similar nodes in a graph are mapped close together in an embedding space. Shallow encoders, such as DeepWalk, have limitations like high computational cost and inability to handle unseen nodes. GNNs address these limitations by using deep, nonlinear transformations to create embeddings. They can handle more complex data types, such as dynamic graphs with multimodal features, enabling applications like node classification, link prediction, and graph similarity.

Takeaways

• 🧠 Introduction to deep learning for graphs, focusing on graph neural networks as a key topic of the course.
• 🖇️ Previously discussed node embeddings aimed to map nodes to a d-dimensional space where similar nodes are close.
• 📊 Node embeddings were encoded in an encoder-decoder framework to match node similarity in the graph and embedding space.
• 📝 Shallow encoding approaches, such as DeepWalk, directly learn an embedding matrix but have limitations like high parameter costs and lack of node features.
• ⚠️ Shallow methods are transductive, meaning they can't generate embeddings for unseen nodes or transfer embeddings across graphs.
• 💡 Deep graph encoders (graph neural networks) use multiple layers of nonlinear transformations for encoding, enabling better generalization and learning.
• 🌐 Graph neural networks can be trained for tasks like node classification, link prediction, and clustering, with an end-to-end approach.
• 🤖 Modern deep learning excels at fixed-size data types like images or sequences, but graph neural networks extend this to more complex, arbitrary graph structures.
• 🔄 Graphs have unique challenges, such as arbitrary size, complex topological structure, and no fixed ordering of nodes, making them different from grid-based data like images.
• 🌟 Graph neural networks enable representation learning for more complex data types, making them versatile for domains where graph structures are essential.

Q & A

What is the main topic of the lecture?

The main topic of the lecture is deep learning for graphs, specifically focusing on graph neural networks (GNNs) and their application to graph-structured data.

What are node embeddings, and why are they important in graph neural networks?

Node embeddings are d-dimensional representations of nodes in a graph, where the goal is to map similar nodes in the graph to similar positions in the embedding space. They are important because they enable the application of machine learning models to graph data by encoding node relationships and properties in a compact, meaningful way.

What is the limitation of shallow encoders like DeepWalk and Node2Vec?

The main limitations of shallow encoders like DeepWalk and Node2Vec include high memory and computation costs, lack of parameter sharing between nodes, and their transductive nature, meaning they can only make predictions for nodes seen during training. They also do not incorporate node features, which limits their ability to leverage additional information.

How do deep graph encoders differ from shallow encoders?

Deep graph encoders, like graph neural networks, apply multiple layers of nonlinear transformations based on the graph structure, allowing for more expressive and generalizable representations. They can also incorporate node and edge features, which shallow encoders cannot.

What are some tasks that graph neural networks (GNNs) can be applied to?

Graph neural networks can be applied to various tasks, including node classification, link prediction, clustering, community detection, and measuring similarity or compatibility between different graphs or sub-networks.

What makes graphs a challenging data structure for deep learning?

Graphs are challenging for deep learning because they have arbitrary size and complex topological structures. They lack spatial locality, fixed reference points, or defined node ordering, unlike grids or sequences. Additionally, graphs can be dynamic and contain multimodal features on nodes and edges.

What is the significance of non-linear transformations in deep graph encoders?

Non-linear transformations in deep graph encoders allow for capturing more complex relationships and dependencies between nodes in a graph. They enable the model to progressively refine the embeddings through multiple layers, leading to richer, more expressive representations.

Why is transductive learning a limitation in shallow encoding methods?

Transductive learning is a limitation in shallow encoding methods because it restricts the model to making predictions only for nodes that were present during training. It cannot generalize to unseen nodes or transfer knowledge between different graphs.

How do graph neural networks handle node features compared to shallow encoders?

Graph neural networks can directly incorporate node and edge features into the learning process, which helps them make more informed predictions. In contrast, shallow encoders like DeepWalk and Node2Vec do not use node features and only rely on the graph structure.

What are some examples of simple data types that traditional deep learning excels at processing?

Traditional deep learning excels at processing simple data types like fixed-size grids (e.g., images) and linear sequences (e.g., text or speech). These data types have well-defined spatial or sequential structures, making them easier to handle with standard deep learning techniques.

Outlines

00:00

📊 Introduction to Graph Neural Networks and Node Embeddings

In this section, the speaker introduces a new topic: deep learning for graphs, with a focus on graph neural networks (GNNs). This marks an important transition in the course. The speaker explains how previous discussions have centered on node embeddings, where the goal was to map graph nodes into d-dimensional embeddings, ensuring that similar nodes are close in the embedding space. The idea was to learn a function that encodes graph nodes into vectors and measures node similarity through techniques like cosine distance or dot products. The speaker emphasizes that the existing node embedding techniques discussed so far—referred to as shallow encoding—are limited in terms of scalability and parameter efficiency, especially for large graphs. Each node requires unique parameters, leading to inefficiencies, and shallow encoding models, like DeepWalk, do not allow for generalization to unseen nodes or graphs.

05:00

🧠 Limitations of Shallow Encoders and Introduction to Deep Graph Encoders

The speaker addresses key limitations of shallow encoders, such as DeepWalk and node2vec, which do not incorporate node features and are computationally expensive due to the need for learning individual embeddings for each node. The speaker introduces the concept of deep graph encoders, particularly Graph Neural Networks (GNNs), as a more efficient alternative. These deep encoders use multiple layers of nonlinear transformations based on the graph structure, allowing for more complex learning and incorporating node and edge features. Deep encoders can be trained for various tasks, including node classification, link prediction, and clustering, offering flexibility and efficiency across a range of graph-based tasks.

10:03

🔄 The Challenge of Applying Deep Learning to Graphs

This paragraph discusses the challenges of applying traditional deep learning to graphs. While current deep learning methods excel with simple data types like fixed-size matrices (used for images) or linear sequences (used for text or speech), graphs present more complexity. Graphs do not have fixed sizes, clear topological structures, or reference points like grids or sequences. This complexity makes it difficult to apply deep learning techniques that were originally designed for simpler, more structured data. Graphs are dynamic, multi-modal, and vary in size and topology, necessitating new approaches, such as Graph Neural Networks (GNNs), for effective representation learning.

Keywords

💡Graph Neural Networks (GNNs)

Graph Neural Networks (GNNs) are a type of deep learning model specifically designed to process and analyze graph-structured data. In the video, GNNs are introduced as a central topic, offering a way to perform deep encoding on graphs. Unlike shallow encoders, GNNs utilize multi-layer transformations based on graph structures to capture complex relationships between nodes, which is important for tasks like node classification and link prediction.

💡Node Embeddings

Node embeddings are low-dimensional vector representations of nodes in a graph that preserve the graph’s structure and the relationships between nodes. The goal, as explained in the video, is to position similar nodes closer together in the embedding space. This concept plays a foundational role in understanding how GNNs transform graph data into useful embeddings for downstream tasks.

💡Shallow Encoding

Shallow encoding refers to a simpler approach to node embeddings where each node’s representation is learned directly, without involving complex transformations. The video contrasts shallow encoding methods, like DeepWalk, with GNNs. Shallow encoders are noted for being computationally expensive and limited in generalization since they do not share parameters across nodes or handle unseen nodes.

💡Similarity Function

A similarity function is used to define how relationships between nodes in the graph map to relationships in the embedding space. In the video, it’s explained that the goal is to ensure that similar nodes in the graph are similarly represented in the embedding space. Examples of similarity measures mentioned include cosine distance and dot products, which are crucial in determining how well the embeddings capture the structure of the graph.

💡Transductive Learning

Transductive learning is a type of machine learning where the model is only capable of making predictions on the examples it has seen during training. In the context of the video, shallow encoders are described as transductive because they cannot generate embeddings for unseen nodes, limiting their application to new graphs or nodes that weren’t part of the training set.

💡Non-linear Transformations

Non-linear transformations refer to the process of applying multiple layers of transformations in a neural network to capture complex patterns and relationships in data. In GNNs, these transformations are applied to the graph structure, enabling deeper and more expressive node embeddings. The video emphasizes that GNNs use non-linear transformations to build sophisticated representations of nodes.

💡Node Classification

Node classification is a task where the goal is to predict a label or category for each node in a graph based on its features and connections. The video mentions that GNNs can be trained end-to-end for node classification, utilizing graph structures and node features to improve accuracy in classifying nodes across various types of graphs.

💡Link Prediction

Link prediction is the task of predicting whether a link (or edge) exists between two nodes in a graph. In the video, link prediction is highlighted as one of the applications of GNNs. By leveraging the graph’s structure and node embeddings, GNNs can predict new or missing links, making them useful for tasks such as recommending friends on social networks.

💡Parameter Sharing

Parameter sharing refers to the idea that a model can reuse the same parameters across different parts of the data to reduce computational complexity. In the video, shallow encoders are criticized for lacking parameter sharing, meaning each node has to learn its own set of parameters. GNNs, however, allow for parameter sharing across nodes, making them more scalable to large graphs.

💡Dynamic Graphs

Dynamic graphs refer to graphs that evolve over time, with changes in node properties, edges, or topology. The video mentions that graphs often have dynamic and multi-modal features, which adds complexity to learning from them. GNNs are positioned as a powerful tool to handle such dynamic graphs, as they can continuously update node embeddings and predictions as the graph changes.

Highlights

Introduction to deep learning for graphs, focusing on graph neural networks as a central topic.

Node embeddings are used to map nodes in a graph into d-dimensional spaces, where similar nodes are embedded close together.

The concept of encoder-decoder framework: encoding the nodes of a graph and decoding their similarity.

Shallow encoding techniques like deep walk and node2vec are limited by their inability to handle large graphs and require large numbers of parameters.

Shallow encoders suffer from being transductive, meaning they cannot generate embeddings for unseen nodes during training.

A major drawback of shallow encoding is that it doesn’t incorporate node features, limiting its ability to capture node properties.

Deep graph encoders, such as graph neural networks, introduce multi-layer non-linear transformations for node embeddings based on the graph structure.

Deep neural networks are capable of handling tasks such as node classification, link prediction, clustering, and graph comparison.

Graph neural networks allow for end-to-end training, connecting graph structures to task-specific labels.

Classical deep learning tools are well-suited for simple data types like fixed-size matrices and linear sequences, but struggle with complex data types like graphs.

Graph neural networks provide a way to extend deep learning to complex data types with arbitrary size and complex topological structures.

Unlike images and text, graphs have no fixed reference point, no spatial locality, and no ordering for their nodes.

Graphs are often dynamic and multimodal, with features assigned to both nodes and edges, creating additional complexity in representation.

Graph neural networks expand the scope of deep learning, applying it to areas that require more than fixed-size matrices or linear sequences.

Graphical representations are crucial for numerous domains where traditional deep learning approaches are insufficient.

Transcripts

Great. So, uh, welcome back to the class.

Uh, we're starting a very exciting, uh,

new topic, uh, for which we have been building up,

uh, from the beginning of the course.

So today, we are going to talk about, uh,

deep learning for graphs and in particular,

uh, techniques around graph neural networks.

And this should be one of the most central topics of the- of the class.

And we are going to spend the next, uh, two weeks, uh,

discussing this and going, uh,

deeper, uh, into this exciting topic.

So the way we think of this is the following: so far,

we have been talking about node embeddings,

where our intuition was to map nodes of

the graph into d-dimensional embeddings such that,

uh, nodes similar in the graph are embedded close together.

And our goal was to learn this, uh,

function f that takes in a graph and gives us the positions,

the embeddings of individual nodes.

And the way we thought about this is,

we thought about this in this encoder-decoder framework where we said

that we want the similarity of nodes in the network,

uh, denoted as here to be similar or to

match the similarity of the nodes in the embedding space.

And here, by similarity,

we could measure distance.

Uh, there are many types of distances you can- you can quantify.

One type of a distance that we were interested in was cosine distance, a dot products.

So we say that, you know,

the dot product of the embeddings of the nodes

has to match the notion of similarity of them in the network.

So the goal was, that given an input network,

I want to encode the nodes by computing

their embeddings such that if nodes are similar in the network,

they are similar in the embedding space as well.

So their similarity, um, is higher.

And of course, when we talked about this,

we were defining about what does it mean to be

similar and what does it mean, uh, to encode?

And, ah, as I mentioned,

there are two key components in

this node embedding framework that we talked to- in- in the class so far.

So our goal was to make each node to a low-dimensional vector.

And, um, we wanted to encode the embedding of a node in this vector, uh, z_v.

And this is a d-dimensional embedding.

So, you know, a vector of d numbers.

And, uh, we also needed to specify the similarity function that specifies how

the relationships in the vector space

mapped to the relationships in the original network, right?

So we said, um, you know,

this is the similarity defined in terms of the network.

This is the similarity defined, uh,

in terms of the, um, embedding space,

and this similarity computation in the embedding space,

we can call this a dot,

uh, uh, we can call this a decoder.

So our goal was to encode the coordinate so that when we decode them,

they decode the similarity in the network.

Um, so far, we talked about what is called shallow encoding,

which is the simplest approach to, uh,

learning that encoder which is that basically encoder is just an embedding-look- look-up,

which means we said we are going to learn this matrix z,

where every node will have our column,

uh, reserved in this matrix.

And this- the way we are going to decode the- the embedding of a given node will simply

be to basically look at the appropriate column of

this matrix and say here is when it's embedding the store.

So this is what we mean by shallow because basically,

you are just memorizing the embedding of every node.

We are directly learning,

directly determining the embedding of every node.

Um, so what are some of the limitations of the approaches?

Um, like deep walk or nodes to end that we have talked about, uh,

so far that apply this, uh,

shallow approach to- to learning node embeddings.

First is that this is extremely expensive in

terms of the number of parameters that are needed, right?

The number of parameters that the model has,

the number of variables it has to

learn is proportional to the number of nodes in the network.

It is basically d times number of nodes.

This- the reason for this being is that for every node we have

to determine or learn d-parameters,

d-values that determine its embedding.

So, um, this means that, uh,

for huge graphs the parameter space will be- will be giant.

Um, there is no parameter sharing, uh, between the nodes.

Um, in some sense, every node has to determine its own unique embedding.

So there is a lot of computation that we need to do.

Then, um, this is what is called, uh, transductive.

Um, this means that in transductive learning,

we can only make predictions over the examples that we have actually seen,

uh, during the training phase.

So this means, in this case,

if you cannot generate an embedding for

a node that- for a node that was not seen during training.

We cannot transfer embeddings for one graph to another because for every graph,

for every node, we have to directly learn- learn that embedding in the training space.

And then, um, another important,

uh, uh, drawback of this shallow encoding- encoders,

as I said, like a deep walk or, uh,

node correct, is that they do not incorporate node features, right?

Many graphs have features,

properties attached to the nodes of the network.

Um, and these approaches do not naturally, uh, leverage them.

So today, we are going to talk about deep graph encoders.

So we are going to discuss graph neural networks that are examples of deep, um,

graph encoders where the idea is that this encoding of, uh, er, er,

of an embedding of our node v is

a multi-layers of nonlinear transformations based on the graph structure.

So basically now, we'll really think about

deep neural networks and how they are transforming

information through multiple layers of

nonlinear transforms to come up with the final embedding.

And important to note that all these deep encoders

can be combined also with node similarity functions in Lecture 3.

So we could say I want to learn a deep encoder that encodes the similarity function,

uh, for example, the random walk similarity function that we used,

uh, in the previous lectures.

Or in this case,

we can actually directly learn the- the-

the encoder so that it is able to decode the node labels,

which means we can actually directly train these models for, uh,

node classification or any kind of,

uh, graph prediction task.

So intuitively, what we would like to do,

or what we are going to do is we are going to develop

deep neural networks that on the left will- on the input will take graph,

uh, as a structure together with, uh, properties,

features of nodes, uh,

and potentially of edges.

We will send this to the multiple layers of

non-linear transformations in the network so that at the end,

in the output, we get, for example,

node embeddings, we also embed entire sub-graphs.

We can embed the pairs of nodes and make various kinds of predictions, uh, in the end.

And the good thing would be that we are able to train this in an end-to-end fashion.

So from the labels, uh,

on the right all the way down to the,

uh, graph structure, uh, on the left.

Um, and this would be in some sense,

task, uh, agnostic or it will be applicable to many different tasks.

We'll be able to do, uh, node classification,

we'll be able to do, uh, link prediction,

we'll be able to do any kind of clustering community detection,

as well as to measure similarity, um, or,

um, compatibility between different graphs or different sub-networks.

So, uh, this, uh, will really, uh,

allow us to be applied to any of these,

uh, different, uh, tasks.

So why is this interesting or why is it hard or why is it different from,

let's say, classical, uh,

machine learning or classical deep learning?

If you think about the classical deep learning toolbox,

it is designed for simple data types.

Essentially, what tra- traditional or current toolbox is really good at is,

we know how to process fixed-size matrices, right?

So basically, I can resize every image and I represent it as

a fixed-size matrix or as a fixed-size grid graph.

And I can also take,

for example, texts, speech,

and represent- think of it basically as a linear sequence,

as a chain graph.

And we know how to process that, uh, really, really well.

So kind of the claim, uh,

and motivation for this is that

modern deep learning toolbox is designed for simple data types,

meaning sequences, uh, linear sequences,

and, uh, fixed-size grids.

Um, and of course the question is,

how can we generalize that?

How can we apply deep learning representation learning to more complex data types?

And this is where graph neural networks come into play because they allow

us to apply representation learning to

much more complex data types than just the span of two very simple,

uh, uh, data types,

meaning the fixed size grids,

uh, and linear sequences.

And why is this hard?

Why this non-trivial to do?

It's because networks have a lot of complexity, right?

They have arbitrary size and they have complex topological structure, right?

There is no spatial locality like in grids.

Uh, this means there is also no reference point or at no fixed orderings on the nodes,

which means that in a graph there is no top left or bottom right as there is in a grid,

or you know there is no left and right,

as you can define in a text because it's a sequence.

In a graph, there is no notion of a reference point.

There is no notion of direction.

Um, and more interestingly, right,

these graphs are often dynamic and have multiple,

um multi-modal features assigned to the nodes and edges of them.

So this becomes, uh,

very- very interesting because it really, um, expands, uh,

ways in which we can describe the data and in which we

can represent the underlying domain in underlying data.

Because not everything can be represented as

a ma- fixed size matrix or as a linear sequence.

And there are- as I showed in the beginning,

right, in the first lecture,

there is a lot of domains,

a lot of use cases where, um,

proper graphical representation is,

uh, very, very important.