Graph Embeddings

What are Graph Embeddings?

Graph embeddings transform nodes, edges, or entire graphs into dense vector representations that preserve structural and semantic properties. 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
• Captures Structural Equivalence: Nodes with similar local structures get similar embeddings
• 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

Key Properties Preserved

Homophily

Nodes that are close in the graph should have similar embeddings.

Structural Equivalence

Nodes with similar structural roles should have similar embeddings.

Community Structure

Nodes in the same community cluster together in embedding space.

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

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

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