# Dynamic node2vec

## Descriptionβ

**Dynamic Node2Vec** is a **random walk based** method that creates embeddings
for every new node added to the graph. For every new edge, there is a
recalculation of probabilities (weights) that are used in walk sampling. A goal
of the method is to enforce that the embedding of node `v`

is similar to the
embedding of nodes with the ability to reach node `v`

across edges that appeared
one before the other.

### Why Dynamic node2vecβ

Many methods, like **node2vec**,
**DeepWalk**, focus on computing the
embedding for static graphs which has its qualities but also some big drawbacks.

Networks in **practical applications** are **dynamic** and evolve constantly
over time. For example, new links are formed (when people make new friends on
social networks) and old links can disappear. Moreover, new nodes can be
introduced into the graph (e.g., users can join the social network) and create
new links to existing nodes.

**Naively applying one of the static** embedding algorithms leads to
unsatisfactory performance due to the following challenges:

**Stability**: the embedding of graphs at consecutive time steps can differ substantially even though the graphs do not change much.**Growing Graphs**: All existing approaches assume a fixed number of nodes in learning graph embeddings and thus cannot handle growing graphs.**Scalability**: Learning embeddings independently for each snapshot leads to running time linear in the number of snapshots. As learning a single embedding is computationally expensive, the naive approach does not scale to dynamic networks with many snapshots

Dynamic Node2Vec is created by F.Beres et al in the "Node embeddings in dynamic graphs".

## Materialsβ

### Implementationβ

**Dynamic Node2Vec** is implemented as part of the
**MAGE** project. Be sure to check it out in
the link above. βοΈ

### Blog postsβ

Our little magician Memgraph MAGE has recently received one more spell - the Online Node2Vec algorithm. Since he is still too scared to use it, you, as a brave spirit, will step up and use it on a real challenge to show MAGE how itβs done. This challenge includes building an Online Recommendation System using k-means clustering and the newborn spell - Online Node2Vec algorithm.

Many methods, like node2vec and deepwalk, focus on computing the embedding for static graphs which is great but also has a big drawback. Networks in practical applications are dynamic and evolve constantly over time. New links are formed, and old ones can disappear. Moreover, new nodes can be introduced into the graph (e.g., users can join the social network) and create new links toward existing nodes.

## Use casesβ

Dynamic Node2Vec can be used to find communities in social networks like Twitter, Facebook, and so on. In order to find communities, we first need to apply dynamic node2vec and then use an unsupervised machine learning algorithm, i.e. k-means which will find us clusters among node embeddings.

We can use dynamic node2vec in the case of link prediction. To do so, after obtaining node embeddings we can predict new links depending on the similarity of the node embeddings.

Furthermore, we can use dynamic node2vec for the node classification task. Node features (embeddings) are input to a one-vs-rest logistic regression. We train our model only on the subset of labels and test it on the rest of them. Our model here is a one-vs-rest logistic regression. You can check out the following paper for more references.

For graph classification, we can create a virtual node that is connected to all the nodes in the graph. After running dynamic node2vec, the embedding of the virtual node will represent an embedding of the entire graph which we can then compare to embeddings of other graphs.