Skip to main content

Graph Embeddings and Node2Vec

Learning low-dimensional vector representations of graphs through random walks, DeepWalk, Node2Vec, and skip-gram models

Which node pairs become training examples when we sample a graph? Nodes are entities and edges are legal walk steps. Start at A, generate a short walk, and count nodes within two positions of each center.

The table calculates those context counts from the actual walk. DeepWalk samples neighbors uniformly; node2vec biases transitions using p and q. A fixed seed makes the controls reproducible. A learned embedding would optimize predictions of those context occurrences; the embedding-space drawing is authored geometry, not a trained result. Changing p or q changes the walk and its counts, not a fictitious learned score.

Graph embeddings
Strategy
Step 1 / 100

Walk → context counts

Deterministic walk (seed 42 + starting node): A. Window radius 2; each ordered center/context occurrence increments one count. Counts change with the walk settings. A learned embedding would fit these counts with an optimization objective; the embedding-space drawing remains an authored layout.

Scroll the table horizontally to inspect all columns.

CenterABCDEFGH
A00000000
B00000000
C00000000
D00000000
E00000000
F00000000
G00000000
H00000000

Sampled walk and calculated context counts

Node2Vec Parameters: p=1 (return), q=1 (in-out). Low p encourages revisiting, low q encourages exploration (DFS), high q encourages local search (BFS).

What are Graph Embeddings?

Graph embeddings transform nodes, edges, or entire graphs into dense vector representations trained to emphasize chosen structural or contextual relationships. These embeddings enable machine learning on graph data by converting discrete graph structures into continuous vector spaces.

Random Walk Strategies

DeepWalk

  • Uniform Random Walks: Equal probability to all neighbors
  • Context objective: Nodes occurring in similar walk contexts can receive similar representations
  • Simple and Scalable: Works well for large graphs

Node2Vec

  • Biased Random Walks: Controlled by parameters p and q
  • Return Parameter (p): Controls likelihood of returning to previous node
    • Low p: Encourages revisiting, local exploration
    • High p: Discourages backtracking
  • In-Out Parameter (q): Controls exploration vs exploitation
    • Low q: DFS-like behavior, explores graph globally
    • High q: BFS-like behavior, stays local

Skip-Gram Training

The skip-gram model learns embeddings by predicting context nodes given a center node:

  1. Generate Random Walks: Sample sequences of nodes
  2. Create Training Pairs: (center node, context node) within window
  3. Optimize Embedding: Maximize probability of observing context given center
  4. Loss Function: Negative log-likelihood with negative sampling

Objectives and tradeoffs

Homophily

An objective can favor nearby nodes; the sampling and loss determine how strongly.

Structural Equivalence

Similar roles need not imply adjacency. Favoring roles can conflict with grouping by community.

Community Structure

Community separation is a possible outcome to evaluate, not a guarantee of every embedding method.

Applications

  1. Node Classification: Predict node labels using embeddings as features
  2. Link Prediction: Compute similarity between node embeddings
  3. Community Detection: Cluster nodes in embedding space
  4. Graph Visualization: Use 2D/3D projections of embeddings
  5. Recommendation Systems: Find similar items via embedding similarity

Comparison of Methods

MethodWalk StrategyTrainingProsCons
DeepWalkUniformSkip-gramSimple, scalableNo edge weights
Node2VecBiased (p,q)Skip-gramFlexibleMore parameters
LINE1st/2nd orderDirectPreserves proximityMemory intensive
GraphSAGESamplingAggregationInductiveComplex

Best Practices

  1. Walk Parameters: Start with walk_length=80, num_walks=10
  2. Window Size: Use window_size=10 for skip-gram
  3. Embedding Dimension: Typically 64-256 dimensions
  4. Node2Vec Tuning:
    • Grid search p, q ∈ 4
    • p=1, q=1 gives DeepWalk behavior
  5. Evaluation: Use downstream task performance

What comes next

Once nodes have feature vectors, graph convolution shows how a message-passing layer can update them using neighbors.

If you found this explanation helpful, consider sharing it with others.

Mastodon