DeepWalk node embeddings

Formula: random walks + skip-gram

Usage

Deepw(
  G,
  walk_len = 10,
  dim = 8,
  n_walks = 4,
  window = 3,
  epochs = 1,
  lr = 0.05,
  neg = 2,
  seed = 42
)

Arguments

G

An n x n adjacency matrix.

walk_len

Length of each walk.

dim

Embedding dimension.

n_walks

Walks started from each node.

window

Skip-gram context window.

epochs

Passes over the corpus.

lr

SGD step size.

neg

Negative samples per positive pair.

seed

Seed of the deterministic stream.

Value

List with estimate, embedding, walks, n_walks_total, degree, n, dim, method.

Details

Truncated uniform random walks are treated as sentences and fed to skip-gram with negative sampling. The walk itself is the whole model assumption: from a node of degree d each neighbour is taken with probability exactly 1/d, so the stationary distribution is proportional to degree.

References

Perozzi, Al-Rfou & Skiena (2014), DeepWalk, KDD 2014:701-710.

Examples

G <- matrix(c(0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0), 4, 4, byrow = TRUE)
Deepw(G, dim = 4, walk_len = 5, n_walks = 2)
#> $estimate
#> [1] 0.003179637
#> 
#> $embedding
#>             [,1]        [,2]        [,3]        [,4]
#> [1,]  0.03001782  0.06103993  0.03431656 -0.04528434
#> [2,] -0.12270361 -0.07729287  0.06482800 -0.12935236
#> [3,]  0.01029798 -0.09519040 -0.06580563  0.05562667
#> [4,]  0.03453990 -0.06140595 -0.10860119 -0.10971831
#> 
#> $walks
#> $walks[[1]]
#> [1] 1 4 1 2 1
#> 
#> $walks[[2]]
#> [1] 2 1 4 1 4
#> 
#> $walks[[3]]
#> [1] 3 2 3 2 1
#> 
#> $walks[[4]]
#> [1] 4 3 4 3 2
#> 
#> $walks[[5]]
#> [1] 1 2 1 2 3
#> 
#> $walks[[6]]
#> [1] 2 3 2 3 4
#> 
#> $walks[[7]]
#> [1] 3 2 1 4 3
#> 
#> $walks[[8]]
#> [1] 4 3 4 3 4
#> 
#> 
#> $n_walks_total
#> [1] 8
#> 
#> $degree
#> [1] 2 2 2 2
#> 
#> $n
#> [1] 4
#> 
#> $dim
#> [1] 4
#> 
#> $method
#> [1] "DeepWalk node embeddings"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"