Graph Embedding

Node2Vec is a random walk-based algorithm that learns continuous feature representations for nodes in a network. It uses a flexible, biased random walk strategy to explore a node's neighborhood, balancing breadth-first (homophily) and depth-first (structural equivalence) sampling.

• Key Innovation: Introduces parameters p (return) and q (in-out) to control walk behavior.
• Objective: Maximizes the probability of observing network neighbors for a node in a fixed-length random walk.
• Use Case: Excellent for node classification and link prediction in homogeneous graphs, such as social networks or citation graphs.

DeepWalk applies language modeling techniques to networks by treating sequences of nodes generated from random walks as 'sentences.' It uses the Skip-gram model from Word2Vec to learn node embeddings.

• Core Process: Generates uniform random walks from each node, then learns embeddings by predicting context nodes within a window.
• Strength: Simple and effective for capturing community structure (homophily).
• Limitation: Uses uniform random walks, lacking the flexibility of later methods like Node2Vec. It is a foundational algorithm for network representation learning.

GraphSAGE (Graph Sample and AggregatE) is an inductive framework for generating node embeddings. Unlike transductive methods (Node2Vec, DeepWalk), it learns a function that generates embeddings by sampling and aggregating features from a node's local neighborhood, enabling it to generalize to unseen nodes.

• Inductive Learning: Can generate embeddings for new nodes without retraining the entire model.
• Aggregator Functions: Employs mean, LSTM, or pooling aggregators to combine neighbor features.
• Primary Use: Large, dynamic graphs where new nodes are frequently added, such as recommendation systems.

TransE (Translational Embedding) is a seminal model for knowledge graph embedding. It represents relationships as translations in the embedding space: if a triple (head, relation, tail) holds true, then the embedding of the head plus the relation should be close to the embedding of the tail (h + r ≈ t).

• Objective: Minimizes a margin-based ranking loss.
• Strength: Efficient and effective for modeling one-to-one relationships.
• Weakness: Struggles with complex relationship patterns like one-to-many and many-to-one. It inspired many subsequent models (TransH, TransR) designed to address this limitation.

A Graph Convolutional Network is a type of Graph Neural Network (GNN) that performs a localized, spectral-based convolution operation on graph data. It learns node representations by aggregating transformed feature information from a node's direct neighbors.

• Mechanism: Each layer computes a node's new representation as a weighted sum of its own features and its neighbors' features, followed by a non-linear activation.
• Semi-Supervised Learning: Excels at tasks like node classification with limited labeled data.
• Foundation: The GCN layer is a fundamental building block for many modern deep learning models on graphs.

Struc2Vec is an algorithm designed to capture structural identity—the notion that nodes are similar based on their local network roles, regardless of their proximity or community membership. It constructs a multi-layer graph that encodes structural similarity at different scales.

• Key Insight: Nodes that are far apart in the original graph but have similar local structures (e.g., both are bridges or hubs) should have similar embeddings.
• Process: Uses a hierarchy of weighted graphs and generates context via random walks on this hierarchy.
• Application: Ideal for role-based classification, such as identifying influencers or outliers in social or financial networks.

A Graph Neural Network (GNN) is a class of deep learning models designed to perform inference directly on graph-structured data. Unlike graph embedding algorithms that produce static vectors, GNNs learn to generate embeddings through an iterative process of neighborhood aggregation and feature transformation. Each node's representation is updated by combining its own features with those of its connected neighbors, allowing the model to capture both local graph structure and node attributes. GNNs are the primary architecture used for supervised tasks like node classification and link prediction, where embeddings are learned end-to-end for a specific objective.