Understanding random walk skip gram (c,d)D1 (c,a) D D Partition the multiset D into several sub-multisets according to the way in which each node and its context appear in a random walk node sequence More formally, for r=1, 2, . T, we define Dr={(0,):(m,c)∈D,w=%,c=7+r} D={(0,):(,c)∈D,m=7+,c=m} Divide-and-Conquer
21 Understanding random walk + skip gram • Partition the multiset 𝒟 into several sub-multisets according to the way in which each node and its context appear in a random walk node sequence. • More formally, for 𝑟 = 1, 2, ⋯ , 𝑇, we define Divide-and-Conquer
Understanding random walk skip gram #(v,c)|D 1g(6#(0)·#() =log h(
22 Understanding random walk + skip gram
Understanding random walk skip gram log(#(u,c)(DI b并(x)·#(c) () the length of random walk l→∞ #(t,c) D S\W@ (P")u tde ol(G) P=D-IA #(c)p m)D1“E(动(P w, C vol(G) (P) #(v)·#(c) vol(G)/1 (P)1c+ (P 2t d wv 1. Qiu et al. Network embedding as matrix factorization: unifying deepwalk, line, pte, and node 2vec WSDM, 18. The most cited paperin WSDM'18 as ofMay 2019 23
23 Understanding random walk + skip gram the length of random walk 𝐿 → ∞ 1. Qiu et al. Network embedding as matrix factorization: unifying deepwalk, line, pte, and node2vec. WSDM’18. The most cited paper in WSDM’18 as of May 2019
#(w,c)D p vol(G #()#()272(a∑(p)m。+ (Peu vol(G) 2T PD+>D(Pr) vol(G)/T D-A×∴xD-AD D-1AD1×…..×AD-1 2T r terms r terms vol(G) DAX D"AD1o7∑P)D2 r terms
24
DeepWalk is factorizing a matrix Wi L+2 Deep Walk is asymptotically and implicitly factorizing vol(G) 7∑(D4))D1 vol(G ∑∑A a Adjacency matriⅸ b: #negative samples D Degree matrix T: context window size
25 𝑤𝑖 𝑤𝑖−2 𝑤𝑖−1 𝑤𝑖+1 𝑤𝑖+2 DeepWalk is asymptotically and implicitly factorizing DeepWalk is factorizing a matrix 𝑣𝑜𝑙 𝐺 = 𝑖 𝑗 𝐴𝑖𝑗 𝑨 Adjacency matrix 𝑫 Degree matrix b: #negative samples T: context window size