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.