Stanford CS224W: Machine Learning with Graphs | 2021 | Lecture 3.3 - Embedding Entire Graphs

Summary

This lecture explores methods for embedding entire graphs rather than individual nodes, focusing on anonymous random walks to create graph embeddings. It discusses averaging node embeddings, introducing a virtual node, and using anonymous walks to represent graphs as probability distributions. The talk also covers embedding anonymous walks themselves and using these embeddings for downstream tasks like graph classification, clustering, and link prediction.

Takeaways

• 🌐 **Graph Embedding**: The lecture discusses methods for embedding entire graphs into an embedding space, rather than just individual nodes.
• 🔑 **Anonymous Random Walks**: A key method involves using anonymous random walks, which record the order of first-time visits to nodes rather than the nodes themselves.
• 📈 **Applications**: These embeddings can be used for various tasks like molecule classification, graph anomaly detection, and other predictive tasks in the embedding space.
• 📝 **Simple Aggregation**: One approach is to run standard node embedding techniques and then sum or average the node embeddings to represent the entire graph.
• 🔗 **Virtual Node Representation**: Introducing a virtual node to represent a graph or subgraph and then embedding this node can serve as the graph's embedding.
• 🔢 **Probability Distribution**: Graphs can be represented as a probability distribution over different anonymous walks of a certain length.
• 🔍 **Sampling Walks**: The number of anonymous walks needed can be calculated using a formula involving parameters for accuracy (Epsilon) and confidence (Delta).
• 🎯 **Objective Function**: The embeddings are learned such that adjacent anonymous walks can be predicted, similar to the approach used in DeepWalk or node2vec.
• 🔄 **Neighborhood Definition**: The neighborhood in this context is defined by the set of anonymous walks rather than by nodes, allowing for a different perspective on graph structure.
• 🔧 **Downstream Tasks**: The learned graph embeddings can be used for various downstream tasks such as graph classification, node classification, and link prediction.

Q & A

What is the main focus of the lecture?

The lecture focuses on embedding entire graphs rather than individual nodes, exploring methods based on anonymous random walks to achieve this.

Why might one want to embed an entire graph?

One might want to embed an entire graph for tasks such as molecule classification, graph anomaly detection, or any application that requires analysis in the embedding space.

What is the first simple idea discussed for embedding a graph?

The first idea is to run standard node embedding techniques like DeepWalk or node2vec and then sum or average the node embeddings to represent the entire graph.

What is a virtual node in the context of graph embedding?

A virtual node is a concept introduced to represent an entire graph or sub-graph. It is connected to the nodes of interest, and its embedding, determined by techniques like DeepWalk or node2vec, is considered the embedding of the graph.

What are anonymous walks and how do they relate to graph embedding?

Anonymous walks are random walks where the sequence of nodes visited is represented by the times of their first visit rather than their identities. This approach is used to create a representation of the graph that is agnostic to the nodes' identities.

How does the number of anonymous walks increase with walk length?

The number of possible anonymous walks increases exponentially with the length of the walk. For example, there are five anonymous walks of length 3, fifteen of length 4, and four million of length 12.

How can anonymous walks be used to embed a graph?

Anonymous walks can be used to embed a graph by simulating walks of a certain length, recording their counts, and representing the graph as a probability distribution over these walks.

What is the mathematical formula used to determine the number of anonymous walks needed for accurate estimates?

The formula involves two parameters, Epsilon and Delta, which define the acceptable error margin and probability. Plugging these into the formula gives the number of anonymous walks needed for sampling.

How can the embeddings of anonymous walks be learned?

The embeddings of anonymous walks can be learned by optimizing an objective function that aims to predict co-occurring walks within a certain window size, similar to the approach used in DeepWalk or node2vec.

What are the potential uses of the graph embedding Z_G obtained from anonymous walks?

The graph embedding Z_G can be used for various prediction tasks such as graph classification, where it can be input into a classifier or used in a dot product to predict labels.

How can node embeddings be combined for prediction tasks in directed graphs?

In directed graphs, node embeddings can be combined by concatenation to output different probabilities depending on the direction of the link, or by other operations like per-coordinate product, summing, or averaging for undirected graphs.