Graph-Based Machine Learning Quiz

CS224W: Node Embeddings

• CS224W is a machine learning course focusing on graphs at Stanford University.
• The course covers node embeddings, a technique for representing nodes in a graph in a low-dimensional vector space.
• Traditional machine learning for graphs requires feature engineering for each individual graph.
• Graph representation learning removes the need to manually engineer features for each graph.
• The goal of graph representation learning is to efficiently learn task-independent features for machine learning tasks on graphs.
• Node embeddings aim to map nodes to vectors, where a node's similarity in the embedding space corresponds to similarity in the network.
• Embeddings are potentially useful for various downstream tasks, including node classification, link prediction, graph classification, anomalous node detection, and clustering.
• Zachary's Karate Club network is an example used to illustrate 2D node embeddings.

Recap: Traditional ML for Graphs

• Traditional machine learning for graphs involves extracting node, link, and graph-level features from an input graph.
• A machine learning model (e.g., SVM, neural network) is then trained to map these extracted features to graph-related labels.
• Feature engineering is a critical step in this approach.

Graph Representation Learning

• Graph representation learning automates feature extraction by directly learning features from the graph structure.
• It alleviates the need for manual feature engineering.
• Learning the features automatically from the graph means better scalability.

Why Embedding?

• Graph embeddings aim to map nodes into an embedding space, making nodes with similar relationships close in the space.
• Similarity in embeddings indicates similarity in the original graph structure.

Setup

• A graph G is represented with a vertex set V and an adjacency matrix A.
• The adjacency matrix is assumed to be binary.
• No additional node features are considered for simplicity.

Embedding Nodes

• The goal is to create node embeddings that capture the similarity structure of the original graph.
• The similarity in the embedding space should reflect the relationships in the graph.

Learning Node Embeddings

• The encoder transforms nodes into embeddings.
• A node similarity function defines how similarities in the graph map to the embedding space.
• The decoder maps embeddings to similarity scores.
• The encoder parameters are optimized such that the encoded similarity reflects the original graph similarity.

“Shallow” Encoding

• The simplest encoding approach where the encoder directly provides an embedding for each node from a learned embedding matrix.
• The embedding matrix contains a low-dimensional vector (embedding) for every node in the graph

Framework Summary

• The framework involves a shallow encoder with an embedding lookup, where the parameters to optimize are the embeddings.
• The decoder is based on node similarity, aiming to maximize the dot product between similar nodes' embeddings.

How to Define Node Similarity?

• The method that defines node similarity is key to the node embedding technique.
• Similarity can be determined based on links, shared neighbors, or structural roles.

Note on Node Embeddings

• Node embeddings are learned using an unsupervised/self-supervised approach.
• Node labels and features are not used in the learning process.
• The goal is to preserve network structure by capturing coordinates (embedding) of the nodes.
• Embeddings are task-independent, usable for various tasks.

Random Walk Approaches for Node Embeddings

• The focus here is on using random walks to learn node embeddings.
• The approach aims to estimate the probability of visiting a node during a random walk.
• Non-linear functions, like softmax, are utilized to normalize predicted probabilities of visits on random walks.

Random-Walk Embeddings

• The goal is represented through similarity in the embedding space.
• The strategy involves estimating probabilities of each node being visited from a start node over a graph walk.
• Optimizing embeddings, via a maximum likelihood approach, aims to accurately encode random walk statistics.

Why Random Walks?

• Random walks provide a flexible way to define node similarity.
• They capture the local and higher-order structural information from the graph better than just node neighbors or links.
• Random walks are computationally efficient, considering only co-occurring node pairs during training.

Unsupervised Feature Learning

• The intuition is to embed nodes in a low dimensional space that preserves their relationships in the network.

Feature Learning as Optimization

• The goal is to learn a function that maps each node to its embedding (low-dimensional representation) in the graph.

Random Walk Optimization

• Embeddings are optimized by examining random walks over nodes in the graph, finding walks that co-occur on the graph, and optimizing for the likelihood of those co-occurrences.

Random Walk Optimization

• Optimizing involves calculating probabilities from random walk co-occurrences and determining an equivalent function.
• These calculations initially face high computational complexity that necessitates approximation via negative sampling.

Negative Sampling

• Negative sampling is used for efficient computation.
• Unlike normalizing over all nodes, it normalizes over a subset of sampled negative nodes for each node in the graph, thus reducing computation complexity.

Stochastic Gradient Descent

• Gradient descent is used to minimize the objective function.
• Stochastic gradient descent is used to calculate the gradient for each training example.

Random Walks: Summary

• The summary describes the steps to obtain and find useful random walks on graphs for node embedding.

How Should We Randomly Walk?

• The summary mentions different strategies for random walks.
• DeepWalk from Perozzi et al. (2013) is presented as a simple strategy.
• The current algorithm has limitations that need to be addressed or generalized.

Overview of Node2Vec

• node2vec embeds nodes to be close when they have similar neighborhoods in the graph.
• The method is independent of the downstream task.
• Flexible neighborhoods result in richer node embeddings.
• It uses a biased random walk to generate neighborhoods around each node, which addresses the limitations of unconstrained random walks..

node2vec: Biased Walks

-The technique uses biased random walks to generate node neighborhoods.

• Biased random walks trade off between local and global exploration in the graph (e.g., BFS vs. DFS).

Biased Random Walks

• Biased random walks, such as those implemented in node2vec, explore network neighborhoods by considering the second-order relationships between nodes.
• The walk is modified to allow for a bias towards either node neighborhood, based on a given parameter
• Parameters (p, q) model probabilities associated with either returning to the previous node or a different node. They control the bias towards local and global neighborhoods.

node2vec Algorithm

• The node2vec algorithm involves computing random-walk probabilities.
• Simulating random walks for a determined length, initialized from each node in the graph.
• Optimizing the node2vec objective using stochastic gradient descent yields node embeddings.
• The three steps are individually parallelizable for reduced runtime.

Other Random Walk Ideas

• Other techniques using biased random walks, alternative optimization schemes, or network preprocessing methods were discovered.

Summary So Far

• A core concept of graph embedding is embedding nodes so distances reflect original graph similarity
• Different approaches to node similarity were illustrated.
• Naive similarity methods, neighborhood overlap, and random walk approaches were highlighted.

Summary So Far

• No single method performs across all situations; the choice depends on the particular application's requirements.
• Random walk approaches are often efficient.

Embedding Entire Graphs

• The goal is to embed entire subgraphs or graphs.
• Embeddings are obtained for individual graphs.
• Various types of graph embeddings are proposed.

Approach 1

• A simple approach to graph embedding is summing or averaging the node embeddings in a subgraph.

Approach 2

• The method introduces a virtual node to represent the entire (sub)graph for standard graph embeddings.

Approach 3: Anonymous Walk Embeddings

• Anonymous walk embeddings are agnostic to the identity of the nodes visited.
• A random walk gives the index of the first time we visit a node.
• Walks are represented by probability distributions.

Sampling Anonymous Walks

• Generate a set of random anonymous walks to represent the graph.
• The number of walks needed to achieve a desired level of error is discussed.

Learn Walk Embeddings

• The core concept is learning graph embeddings for a whole graph together with all anonymous walk embeddings.
• An objective function is formulated for learning the embedding parameters, considering co-occurrence of walks in a context window.
• Random walks enable a more nuanced understanding of graph relationships.

Learn Walk Embeddings

• Learning walk embeddings involves obtaining graph embeddings by optimizing a function based on the likelihood of random walks co-occurring during training.

Summary

• Three distinct strategies were presented for obtaining graph embeddings.

Preview: Hierarchical Embeddings

• More advanced embedding methods are available.
• Clustering nodes hierarchically and summing/averaging node embeddings within each cluster is a method.

How to Use Embeddings

• Embeddings can be used for various applications including clustering, node and graph classification.
• Methods to measure distance between embeddings are also discussed; for example, these are concatenation, Hadamard product, summation or average, and distance measure.

Today's Summary

• Graph representation learning is reviewed, a technique for learning node and graph embeddings used for downstream tasks that do not require feature engineering.
• Encoder and decoder components of the framework, including node similarity measures, are discussed.
• Different types of graph embedding are presented, including DeepWalk and node2vec.
• Extensions include graph embedding, anonymous walk embeddings, and techniques for creating hierarchical embeddings are discussed.