Node Embeddings: DeepWalk & Node2Vec

Node embedding is the fundamental bridge that allows us to apply standard Deep Learning tools to non-Euclidean graph data. By mapping discrete nodes into a continuous vector space, we unlock the ability to perform classification, clustering, and link prediction with unprecedented efficiency.

---

1. The Non-Euclidean Challenge

Unlike images (fixed grids) or text (sequences), graphs are Size Independent and Permutation Invariant.

• Permutation Invariance: Changing the order of nodes in an adjacency matrix doesn't change the graph structure, but it completely changes the matrix. Standard NNs fail here because they are sensitive to input order.
• Geometric Deep Learning: This is the field dedicated to learning from these complex, non-Euclidean structures where "up" and "down" don't exist, only connectivity and local topology.

Our goal is to learn a mapping function $f$:

$f: u \rightarrow \mathbb{R}^d$

The Golden Rule: If two nodes are "close" in the graph (connected or sharing high-order proximity), their vectors should be "close" in the embedding space (typically measured by dot product or cosine similarity).

---

2. DeepWalk: The Word2Vec of Graphs

DeepWalk was a paradigm shift. It proposed that if we can't treat a graph like a sentence, we can simulate sentences using random walks.

The Algorithm

1. Random Walk Generation: For every node, perform $N$ random walks of length $L$.
2. Corpus Building: Treat each walk as a "sentence" where nodes are "words".
3. Skip-Gram Optimization: Use the Word2Vec skip-gram model to maximize the probability of seeing a neighbor given a node.

$\max_f \sum_{u \in V} \log \text{Pr}(\{v_j\}_{j \in \text{context}} \mid f(u))$

• Why it works: Under the Homophily Hypothesis, nodes that are close in the graph will appear in the same random walks frequently. Word2Vec then pushes their vectors closer together.

---

3. Node2Vec: The Steering Wheel

DeepWalk is essentially a "uniform" drunkard. Node2Vec introduces a biased random walk that can be tuned to capture different structural properties using two parameters: $p$ and $q$.

The Search Strategies

• Breadth-First Search (BFS): Captures Homophily. The walker stays close to the source, capturing community structure.
• Depth-First Search (DFS): Captures Structural Equivalence. The walker wanders far away, identifying nodes with similar "roles" (e.g., both are hubs or bridges) even if they aren't in the same community.

The $p$ and $q$ Control

1. Return Parameter ($p$): High $p$ discourages the walker from going back to the previous node.
2. In-Out Parameter ($q$): Low $q$ encourages the walker to move outward (DFS style), while high $q$ keeps it local (BFS style).

---

4. Metapath2vec: Heterogeneous Embeddings

Standard DeepWalk assumes all nodes are the same type. Modern graphs (Knowledge Graphs, Academic Networks) are Heterogeneous.

Metapath2vec uses "meta-paths" to guide the walker. For example, in a network of Authors ($A$) and Papers ($P$), a meta-path could be $A \rightarrow P \rightarrow A$. This ensures the "sentences" produced follow a logical semantic structure, allowing the model to learn sophisticated cross-entity relationships.

---

Summary Comparison

Method	Walk Type	Primary Goal	Graph Type
DeepWalk	Uniform Random	Local Proximity	Homogeneous
Node2Vec	Biased Random	Homophily + Roles	Homogeneous
Metapath2vec	Meta-path Guided	Semantic Relationships	Heterogeneous

---

Python Implementation: DeepWalk

deepwalk.py

import random
import networkx as nx
from gensim.models import Word2Vec

class DeepWalk:
    def __init__(self, graph, walk_length=10, num_walks=80):
        self.graph = graph
        self.walk_length = walk_length
        self.num_walks = num_walks
        self.walks = []

    def _generate_single_walk(self, start_node):
        walk = [str(start_node)]
        while len(walk) < self.walk_length:
            cur = int(walk[-1])
            neighbors = list(self.graph.neighbors(cur))
            if len(neighbors) == 0: break
            walk.append(str(random.choice(neighbors)))
        return walk

    def generate_corpus(self):
        nodes = list(self.graph.nodes())
        for _ in range(self.num_walks):
            random.shuffle(nodes)
            for node in nodes:
                self.walks.append(self._generate_single_walk(node))
        return self.walks

    def train(self, embed_size=128, window=5):
        if not self.walks: self.generate_corpus()
        model = Word2Vec(self.walks, vector_size=embed_size, 
                         window=window, sg=1, hs=1, workers=4)
        return model.wv

# Usage
# G = nx.karate_club_graph()
# dw = DeepWalk(G)
# embeddings = dw.train()

Pro Tip: Transductive vs. Inductive

DeepWalk and Node2Vec are Transductive. This means if you add a new node to the graph, you have to re-train the entire model. For dynamic, ever-changing graphs, look into GraphSAGE (Inductive learning).