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.
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.
| Center | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| E | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| F | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| H | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
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:
- Generate Random Walks: Sample sequences of nodes
- Create Training Pairs: (center node, context node) within window
- Optimize Embedding: Maximize probability of observing context given center
- 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
- Node Classification: Predict node labels using embeddings as features
- Link Prediction: Compute similarity between node embeddings
- Community Detection: Cluster nodes in embedding space
- Graph Visualization: Use 2D/3D projections of embeddings
- Recommendation Systems: Find similar items via embedding similarity
Comparison of Methods
| Method | Walk Strategy | Training | Pros | Cons |
|---|---|---|---|---|
| DeepWalk | Uniform | Skip-gram | Simple, scalable | No edge weights |
| Node2Vec | Biased (p,q) | Skip-gram | Flexible | More parameters |
| LINE | 1st/2nd order | Direct | Preserves proximity | Memory intensive |
| GraphSAGE | Sampling | Aggregation | Inductive | Complex |
Best Practices
- Walk Parameters: Start with walk_length=80, num_walks=10
- Window Size: Use window_size=10 for skip-gram
- Embedding Dimension: Typically 64-256 dimensions
- Node2Vec Tuning:
- Grid search p, q ∈ 4
- p=1, q=1 gives DeepWalk behavior
- 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.
Related concepts
Understanding complete, dimensional, and cluster collapse — the failure modes that every self-supervised method must prevent. Learn why collapse happens and how contrastive, asymmetric, regularization, and masking approaches solve it.
Understand contrastive loss for representation learning: interactive demos of InfoNCE, triplet loss, and embedding space clustering with temperature tuning.
Understand where self-supervised targets come from, how masked prediction creates a learning task, and why predicting pixels differs from predicting learned features.
Follow how a learned target encoder supplies feature targets, how stop-gradient separates backward paths, and how exponential moving averages update its parameters.
Move a pretrained encoder to a downstream task: trace frozen features, head training, partial and full fine-tuning, learning rates, and BatchNorm state.
Evaluate frozen image features with nearest neighbors and linear probes, separate training from validation and test data, and understand what each protocol can establish.
