Graph Embedding Families: From Points to Distributions

Graph embedding methods have evolved from simple matrix factorization to complex deep learning architectures. Understanding the "family" of an algorithm is key to choosing the right tool for specific constraints like scalability, uncertainty, or graph dynamics.

---

1. Vector Point-Based Methods

The most common family. Every node is mapped to a single, deterministic coordinate in a latent space.

1.1 Matrix Factorization-Based (The Compression View)

Treats graph embedding as a dimensionality reduction problem on the adjacency matrix $A$.

• The Goal: $A \approx Z \cdot Z^T$, where $Z$ is the embedding matrix.
• HOPE: Preserves asymmetric transitivity in directed graphs.
• GraRep: Captures high-order proximity by factorizing k-step transition matrices.
• Limitations: High computational cost ($O(|V|^2)$ or $|V|^3$) and inability to handle non-linear structures.

1.2 Random Walk-Based (The NLP View)

Address scalability by simulating "sentences" through the graph.

• DeepWalk: Uniform random walks + Word2Vec.
• Node2Vec: Biased random walks (BFS vs. DFS) to capture community and roles.
• Pros: Highly scalable ($O(|V|)$), works on massive networks.

1.3 Deep Learning-Based (The AutoEncoder View)

Uses Neural Networks to capture complex non-linearities.

• SDNE (Structural Deep Network Embedding): Uses a deep autoencoder to preserve both first-order (local) and second-order (global) proximity simultaneously.

---

2. Gaussian Distribution-Based Methods

Vector point methods are overconfident. They give a precise dot even when a node's position is ambiguous (e.g., a user who belongs to both the "Gaming" and "Cooking" communities).

Gaussian methods (like Graph2Gauss) represent each node as a probability distribution $\mathcal{N}(\mu, \Sigma)$ instead of a point.

• Uncertainty Quantification: The variance ($\Sigma$) tells us how "sure" the model is about a node's position.
• Asymmetric Proximity: These methods can model directed relationships more naturally by measuring the KL-divergence between distributions.

---

3. Dynamic Graph Embedding

Real-world graphs (Social Media, Financial Transactions) change over time. Nodes and edges are added or deleted constantly.

• DynGraph2Vec: Uses RNNs or LSTMs to capture how a node's neighborhood evolves over time.
• EvolveGCN: Adapts the Graph Convolutional Network (GCN) parameters at every time step using a recurrent mechanism (GRU/LSTM).
• Goal: Learn embeddings that are stable over time while capturing temporal trends.

---

4. Hyperbolic Embeddings: The Modern Frontier

Most graphs (especially Social and Biological ones) have a hierarchical or "tree-like" structure. Euclidean space is terrible for embedding trees—the space needed grows exponentially, but Euclidean volume only grows polynomially.

Poincaré Embeddings solve this by using Hyperbolic Space.

• Why it's Pro: In a hyperbolic disc, the "distance" increases exponentially as you move toward the edge. This allows us to embed massive hierarchies with very low dimensions while preserving parent-child relationships perfectly.

---

Summary Comparison

Family	Key Method	Representation	Best For
Matrix Factorization	HOPE	Point	Small, static directed graphs
Random Walk	Node2Vec	Point	Large-scale community detection
Deep Learning	SDNE	Point	Capturing complex non-linearities
Gaussian	Graph2Gauss	Distribution	Uncertainty & Asymmetric links
Hyperbolic	Poincaré	Point (Disc)	Hierarchies & Taxonomies

---

Reference

• Understanding Graph Embedding Methods and Their Applications Paper
• Hyperbolic Node Embeddings Poincaré Paper