---
title: "Node2vec"
date: last-modified
date-format: YYYY-MM-DD
vignette: >
  %\VignetteIndexEntry{Node2vec}
  %\VignetteEngine{quarto::html}
  %\VignetteEncoding{UTF-8}
knitr:
  opts_chunk:
    collapse: true
    comment: '#>'
author:
  Gregor Lueg
---

# Running node2vec

## Setup

```{r}
#| label: setup
library(genewalkR)
library(data.table)
library(magrittr)
library(ggplot2)
```

## Background

Node2vec generates vector representations of nodes in a graph by running biased
random walks that sample the local neighbourhood of each node, then training a
skip-gram model over the resulting sequences. Nodes that appear in similar
contexts across the graph will have similar embedding vectors. For a full
description of the algorithm, see [Grover & Leskovec](https://arxiv.org/abs/1607.00653).

## Synthetic data

`genewalkR` provides quite a few synthetic graph data sets for testing and
exploration purposes, namely:

- **Barbell graph**: a graph of two distinct clusters
- **Cavemen graph**: a graph with distinct communities with a low probability of
  connection between them.
- **Stochastic blocks**: a more densely connected graph with communities; 
  however, more cross-edges compared to the previous graphs.

## Exploring node2vec

Let's check what node2vec does with different types of graphs and if the 
embeddings faithfully recover the graph structure.

### Barbell graph

Let's load in the barbell graph.

```{r}
#| label: loading in barbell data
# this creates a random data set with 20 nodes per barbell cluster
barbell_data <- node2vec_test_data(
  test_type = "barbell",
  n_nodes_per_cluster = 20L
)
```

#### Exploring the data

Let's transform this into an igraph first and just look at the graph as is.

```{r}
#| label: generate igraph from barbell data
g <- igraph::graph_from_data_frame(d = barbell_data$edges, directed = FALSE)

plot(g, vertex.label = NA)
```

#### Running node2vec

You can appreciate a nice barbell graph with two distinct groups. Now let's
run node2vec on this data. The node2vec implementation is based on
[node2vec-rs](https://github.com/GregorLueg/node2vec-rs), a Rust-based
implementation of node2vec. In its default setting, we use a HIGHLY optimised
version that runs on the CPU with SIMD-acceleration and a RWlock free version
of SGD - known as [Hogwild!](https://arxiv.org/abs/1106.5730). This approach
is also used in the original version of word2vec, 
[see Mikolov, et al.](https://arxiv.org/abs/1301.3781)
The issue with this is that the underlying embeddings will not be deterministic;
however, the structure of the underlying graph will be identified. If you
really, really, really need deterministic results here, set the parameter
`n_workers = 1L`.

```{r}
#| label: run node2vec
# run node2vec
barbell_node2vec_results <- node2vec(
  graph_dt = barbell_data$edges,
  .verbose = TRUE
)

# the parameters are controlled via a supplied parameter list, see code here
str(params_node2vec())

# this list can be supplied and tells node2vec how to run
```

Let's generate a PCA of the embedding and explore the first two principal 
components visually

```{r}
#| label: node2vec pca
# run pca on the embeddings
pca_results <- prcomp(barbell_node2vec_results, scale. = TRUE)

pca_dt <- as.data.table(pca_results$x[, 1:2], keep.rownames = "node") %>%
  merge(., barbell_data$node_labels, by = "node")

pca_dt[, cluster := factor(cluster)]

ggplot(data = pca_dt, mapping = aes(x = PC1, y = PC2)) +
  geom_point(
    mapping = aes(color = cluster),
    size = 3
  ) +
  theme_bw() +
  labs(color = "Cluster:")
```

As you can appreciate, node2vec embeddings nicely identify the two groups
in the underlying graph. 

### Cavemen graph

Visualisation of the graph structure in igraph first (same as for the previous
graph):

```{r}
#| label: cavemen igraph
# generate the cavemen
caveman_data <- node2vec_test_data(
  test_type = "cavemen",
  n_clusters = 5L,
  p_between = 0.5
)

g <- igraph::graph_from_data_frame(d = caveman_data$edges, directed = FALSE)

plot(g, vertex.label = NA)
```

Let's visualise the PCA on top of the embeddings generated by node2vec on this 
graph structure.

```{r}
#| label: cavemen node2vec visualisation
# run node2vec
cavemen_node2vec_results <- node2vec(
  graph_dt = caveman_data$edges,
  .verbose = TRUE
)

# run pca on the embeddings
pca_results <- prcomp(cavemen_node2vec_results, scale. = TRUE)

pca_dt <- as.data.table(pca_results$x[, 1:2], keep.rownames = "node") %>%
  merge(., caveman_data$node_labels, by = "node")

pca_dt[, cluster := factor(cluster)]

ggplot(data = pca_dt, mapping = aes(x = PC1, y = PC2)) +
  geom_point(
    mapping = aes(color = cluster),
    size = 3
  ) +
  theme_bw() +
  labs(color = "Cluster:")
```

### Stochastic blocks 

In this last graph example, we have less defined communities with more between 
edges across the communities. We will do exactly what we did before.

```{r}
#| label: stochastic block igraph
# generate the stochastic block graph
stochastic_block_data <- node2vec_test_data(
  test_type = "stochastic_block",
  n_clusters = 3L,
  p_between = 0.05
)

g <- igraph::graph_from_data_frame(
  d = stochastic_block_data$edges,
  directed = FALSE
)

plot(g, vertex.label = NA)
```

Let's visualise again the PCA here:

```{r}
#| label: stochastic block node2vec visualisation
# run node2vec
stochastic_blocks_node2vec_results <- node2vec(
  graph_dt = stochastic_block_data$edges,
  .verbose = TRUE
)

# run pca on the embeddings
pca_results <- prcomp(stochastic_blocks_node2vec_results, scale. = TRUE)

pca_dt <- as.data.table(pca_results$x[, 1:2], keep.rownames = "node") %>%
  merge(., stochastic_block_data$node_labels, by = "node")

pca_dt[, cluster := factor(cluster)]

ggplot(data = pca_dt, mapping = aes(x = PC1, y = PC2)) +
  geom_point(
    mapping = aes(color = cluster),
    size = 3
  ) +
  theme_bw() +
  labs(color = "Cluster:")
```

In conclusion, node2vec generates an embedding of the underlying network 
structure that you can then use to visualise the data or do additional analyses
(with some already part of this package and more to be added). Pending on your 
needs, you can go high on the available workers and make this fast, or if you 
really, really, really need similar embeddings every single time, you can also 
choose to disable the parallelism during training (the random walks will
still be generated via Rayon in parallel).