Skip to content
Back to search results

Network Embedding — Node2Vec, DeepWalk, LINE

Year
2014 (DeepWalk); 2016 (Node2Vec)
Type
Representation learning / unsupervised network method
Font size

What does it do?

Network embedding is a family of representation-learning methods that map each node of a graph into a dense, low-dimensional vector while preserving the network's structural properties.

The approach was formalised for social-network data by Perozzi, Al-Rfou, and Skiena with DeepWalk (2014), which adapted the Word2Vec skip-gram model to random walks on graphs, and extended by Grover and Leskovec with Node2Vec (2016), which introduced a biased random walk that balances breadth-first and depth-first exploration. These embeddings turn relational data into feature vectors that standard machine-learning classifiers and clustering algorithms can consume directly.

The intuition behind the method

A graph is made of nodes and edges, but most machine-learning algorithms expect a table of numbers. Network embedding solves the translation problem. Just as Word2Vec learns word meanings by looking at which words appear near one another in sentences, DeepWalk learns node meanings by looking at which nodes appear near one another in random walks across the graph. The result is a coordinate in a vector space — nodes that are structurally similar or frequently co-visited end up close together. Once every node has a vector, you can feed those vectors into a classifier, cluster them with k-means, or visualise them with UMAP, without writing any graph-specific code.

History

The idea of applying Word2Vec to graph-structured data was introduced by Perozzi, Al-Rfou, and Skiena in DeepWalk (KDD 2014), which showed that random walks on a social graph could replace hand-crafted features for node classification. Grover and Leskovec extended this in Node2Vec (KDD 2016) by introducing a second-order biased random walk parameterised by p and q, providing explicit control over the trade-off between homophily-based and structural-equivalence-based neighbourhood exploration. Around the same period Tang et al. proposed LINE (WWW 2015), which learns embeddings by optimising first- and second-order proximity objectives directly rather than through random walks, making it suitable for very large graphs. Together these three methods established the field of network representation learning and inspired subsequent graph neural network architectures.

When to use it

Network embedding is appropriate when you have a graph of at least 50 nodes and you need continuous vector features for downstream tasks such as node classification, link prediction, or node clustering. The method suits both unweighted and weighted graphs, and handles directed or undirected structures. Choose DeepWalk when a simple, uniform random-walk baseline is sufficient. Choose Node2Vec when you want to tune the balance between homophily and structural equivalence through the p and q parameters. If you need to embed new, previously unseen nodes at inference time without retraining, prefer an inductive method such as GraphSAGE; network embedding in its standard form is transductive. The method does not require normally distributed node attributes.

Limitations and considerations

  • Transductive: the model cannot embed nodes that were not present during training without full retraining.
  • Hyperparameter sensitivity: embedding dimension, walk length, number of walks, window size, p, and q all affect embedding quality and require tuning.
  • Random walks do not capture higher-order graph structure (e.g., hyperedges or multi-relational edges) without extension.
  • Performance degrades on very small graphs (fewer than 50 nodes) where the walk corpus is too sparse to learn reliable statistics.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Converts relational graph data into fixed-length vectors compatible with any standard machine-learning pipeline.
  • Node2Vec's p and q parameters let the analyst tune the balance between community-sensitive and role-sensitive embeddings.
  • Edge weights can be incorporated into walk probabilities, capturing relationship strength without extra modelling steps.
  • Scales to large graphs through efficient random-walk sampling and the skip-gram training procedure.

Applications

  • Node classification in citation networks, social platforms, or biological interaction graphs.
  • Link prediction — identifying missing or future edges by comparing node embedding similarity.
  • Community detection by clustering node vectors with k-means or hierarchical methods.
  • Anomaly detection — nodes whose embeddings are outliers in the vector space may represent unusual structural roles.
  • Recommendation systems where users and items are nodes in a bipartite or multiplex interaction graph.

How it works

How it works

1

The process begins with a graph G in which nodes are entities and edges represent relationships. Edges may be directed or undirected and may carry weights that will later influence the probability of traversal. If edge weights are present they are included in walk probabilities; if absent all edges receive equal weight. At this stage the analyst also chooses the algorithm variant — DeepWalk for uniform random walks, Node2Vec for biased walks controlled by parameters p (return) and q (in-out), or LINE when first- and second-order neighbourhood proximity should be learned separately. The choice between Node2Vec parameter regimes is guided by the expected network property: homophily (similar nodes connect, so breadth-first exploration is preferred, q < 1) or structural equivalence (nodes with similar roles may be far apart, so depth-first exploration is preferred, p < 1).

2

Starting from each node, the algorithm simulates a series of random walks of fixed length (typically 30 steps) and repeats them many times (typically 200 walks per node). Each walk produces a sequence of node identifiers analogous to a sentence of words. In DeepWalk the next node is chosen uniformly from neighbours. In Node2Vec the next node is chosen according to transition probabilities biased by p and q: returning to the previous node is penalised by 1/p, staying at the same distance is kept at 1, and moving farther out is controlled by 1/q. The collection of all walks forms a corpus of node sequences that encodes the graph's topology.

3

The corpus of node sequences is fed into a skip-gram model (the same architecture as Word2Vec). For each node in a walk, the model predicts the surrounding context nodes within a window (typically 10 steps). Through stochastic gradient descent the model learns a dense vector representation of fixed dimension — commonly 64 or 128 — for every node such that nodes co-occurring in walks have similar vectors. The dimension is a hyperparameter: larger dimensions capture more structure but increase computation and risk overfitting on small graphs.

4

Once trained, the model provides one embedding vector per node. These vectors are used as features for node classification (feeding them into a logistic regression or neural classifier), link prediction (comparing vectors of candidate node pairs), or community detection (clustering the vectors). The embeddings are transductive: they are fixed for the nodes seen during training. If new nodes must be embedded after training, an inductive method such as GraphSAGE should be used instead, as a standard Node2Vec or DeepWalk model cannot generalise to unseen nodes without retraining.

Common pitfalls

  • Applying a Node2Vec model to new nodes that were not in the training graph — the model will not have a vector for them; use an inductive method (e.g., GraphSAGE) when transductive embedding is not acceptable.
  • Using default p=1, q=1 (equivalent to DeepWalk) without examining whether the network follows a homophily or structural-equivalence pattern — tuning p and q to the expected pattern can substantially improve downstream task performance.
  • Treating embedding dimension as a fixed constant: on small graphs a dimension of 64 or 128 may overfit; start lower and validate on the downstream task.
  • Ignoring the minimum sample requirement: graphs with fewer than 50 nodes produce walk corpora too thin to train reliable embeddings.

Frequently asked questions

What is the difference between DeepWalk, Node2Vec, and LINE?

DeepWalk uses uniform random walks and the Word2Vec skip-gram model — it is the simplest baseline. Node2Vec adds biased random walks controlled by p and q, allowing the analyst to tune whether the walk explores like breadth-first search (homophily) or depth-first search (structural equivalence). LINE does not use random walks at all; it optimises first- and second-order proximity objectives directly on the edge list, which is more scalable to very large graphs but sacrifices the walk-based neighbourhood signal.

How do I choose the p and q parameters in Node2Vec?

p controls the likelihood of returning to the previous node (low p = less backtracking), and q controls the exploration radius (q < 1 favours outward exploration, q > 1 keeps the walk near the source). If you expect nodes in the same community to be similar (homophily), set q < 1 to let the walk roam outward. If you expect nodes with the same structural role to be similar even if far apart, set p < 1 to encourage depth-first exploration. Validate both regimes on the downstream task.

Can I embed new nodes after training without retraining the whole model?

Standard Node2Vec and DeepWalk are transductive: the embedding matrix covers only the nodes seen during training. For inductive generalisation to new, previously unseen nodes, use an inductive graph neural network method such as GraphSAGE, which learns an aggregation function over node neighbourhoods that can be applied to any node at inference time.

How many dimensions should I use for the embedding?

The most common choices are 64 and 128, and these work well for medium to large graphs. For small graphs (50–200 nodes) start with a lower dimension (16 or 32) to avoid overfitting, and evaluate embedding quality by measuring downstream task performance (e.g., node classification accuracy) rather than reconstruction error alone.

Related methods

Sources

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    Open DOI reference
    Copied.
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

    Open DOI reference
    Copied.