Overview of Common Graph Embedding Methods in Industry

Graph embedding is a type of representation learning that aims to learn low‑dimensional dense vectors for graph nodes based on the graph topology, facilitating downstream tasks. This article introduces several graph embedding methods commonly used in industry.

1. DeepWalk

DeepWalk (2014) treats random walks on the graph as sentences and applies the skip‑gram model from word2vec to learn node embeddings. The algorithm shuffles node order, performs random walks from each node to generate sequences, and then trains skip‑gram on these sequences. For weighted or directed graphs, transition probabilities can be adjusted proportionally to edge weights.

Because skip‑gram predicts neighboring nodes, nodes sharing many common neighbors obtain similar embeddings.

2. Node2Vec

Node2Vec extends DeepWalk by introducing biased random walks that balance homophily and structural equivalence. Two walk strategies—breadth‑first search (BFS) and depth‑first search (DFS)—are used to emphasize structural similarity or homophily, respectively. Two hyper‑parameters p (return parameter) and q (in‑out parameter) control the bias: small p encourages returning to the previous node (BFS‑like), while small q encourages exploring farther nodes (DFS‑like). The transition probability is formalized as shown below.

Node2Vec uses the Alias sampling method to efficiently sample the next node.

3. LINE

LINE (Large‑scale Information Network Embedding) defines first‑order and second‑order proximities. First‑order proximity measures similarity of directly connected nodes; second‑order proximity measures similarity of nodes with many shared neighbors. LINE optimizes two separate objectives using KL‑divergence, with first‑order applicable to undirected graphs and second‑order to both directed and undirected graphs. The model learns two embeddings per node (source and context) and can concatenate them.

4. SDNE

SDNE (Structural Deep Network Embedding) employs a deep auto‑encoder to preserve both first‑ and second‑order proximities. The input is a row of the adjacency matrix; the encoder maps it to a low‑dimensional vector, and the decoder reconstructs the adjacency. The loss consists of first‑order proximity loss, second‑order proximity loss (weighted reconstruction), and an L2 regularization term.

First‑order loss forces embeddings of directly linked nodes to be close; second‑order loss encourages nodes with similar neighborhoods to have similar embeddings.

5. EGES

EGES (Enhanced Graph Embedding with Side Information) addresses sparsity and cold‑start problems in recommendation systems by incorporating side information (e.g., item category, price). It aggregates embeddings of the item and its side information using learned weights, then predicts context items with a skip‑gram‑like objective.

6. Metapath2Vec

Metapath2Vec extends homogeneous graph embedding to heterogeneous networks. After defining meta‑paths (sequences of node types), random walks are constrained to follow these meta‑paths, generating type‑consistent sequences. Skip‑gram is then applied to learn embeddings. Metapath2Vec++ further restricts negative sampling to nodes of the same type as the positive sample.

Author

Wanqing Zhuang, Senior Researcher at Tencent Games, focuses on modeling player behavior sequences. He graduated from the School of Computer Science, South China University of Technology.