LINE e Objective of lINE C=∑∑(4kg9()+2(k9(m =1j= Align it with the Objective of SGNs c=∑(kwb)+(m(y) LINE is actually factorizing vol(G) 6D-lAD-1 Recall deepWalk's matrix form: g(b(r∑( DIAD Observation LINE is a special case of DeepWalk(T=1)
26 LINE
PTE degree text document text doc 1 information doc 2 information node network word network doc 3 network edge doc 4 label 3 elassification embeddin g classification classification (a)word-word network (b)word-document network (c)word-label network Heterogeneous text network Figure 2: Heterogeneous Text Network vol(Gww)(Drow)AwwDy Ww vol(Gw(oiw)-1 Aw(D)1 col log B vol(Gdw)(Drw )Adw(D log b, 1
27 PTE
node2vec- 2nd order random walk 1p1 (,)∈E,(v,)∈E, (,)∈E,(t,)∈E,≠,(v0,) u=1(,0)∈E,(v,)∈E,≠,(,n)gE; 0 otherwise Pn,=Prob(n+1=10;=t,y-1=)= u.U.1 T L=t,0,0U Stationary Distribution ∑ X ,U,u--, Existence guaranteed by Perron-Frobenius theorem, but may not be unique
28 node2vec — 2nd Order Random Walk
Unifying DeepWalk, LINE, PTE, and node 2vec into matrix forms Algorithm Closed Matrix Form Deepwalk log(vol(G)(T ET-1(D-1A)D-1)-log b LINE log(vol(G)D-AD)-log b a vol(Gww)(Dww)Aww(DWW)-1 PTE log B vol( Gdw)(Drw ) -Adw(Ddw-1 log b og y vol(Glw)(DWw )Alw(Dw)-1 eT Er=Eu Xw, uPG, w, u+Eu xc, uPW noaezvec (ΣaXw,u)(∑aXe,u) 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 of May 2019 29
29 Unifying DeepWalk, LINE, PTE, and node2vec into Matrix Forms 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
NetMF: explicitly factorizing the DW matrix Matrix Factorization aunified algorithm NetMF to explicitly factorizes the derived matrix 09 b(∑( DAD 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 of May 2019 30
30 NetMF: explicitly factorizing the DW matrix 𝑤𝑖 𝑤𝑖−2 𝑤𝑖−1 𝑤𝑖+1 𝑤𝑖+2 A unified algorithm NetMF to explicitly factorizes the derived matrix Matrix Factorization 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