Network Embedding - GitHub Pages

Network Embedding Yuanfu Lu BUPT June 17, 2019

Outline I Problem I Methodology I Application I Conclusion

Outline I Problem I Methodology I Application I Conclusion

Problem (a) Social Network I Homogeneous Network (a) I I 1 type of node and edge Heterogeneous Network (b) I I (b) Movie Network 2 types of node and edge Knowledge Graph (c) I triad (h, r , t) (c) Knowledge Graph

Problem I Input: a network/graph G (V, E) I Output: the representation of the network U Rn d , d V , d-dim vector ui for each node vi . Goal: learn a mapping function f : vi ui Rd

Outline I Problem I Methodology I Application I Conclusion

Methodology

Method: word2vec(ICLR’13) The CBOW architecture predicts the current word based on the context, and the Skip-gram predicts surrounding words given the current word.

Method: DeepWalk (KDD’14) Pr ({vi w , · · · , vi w } \vi Φ (vi )) i w Y Pr (vj Φ (vi )) j i w j6 i Maximize the cooccurrence probability among the nodes that appear within a window w , in a random walk.

Method: node2vec (KDD’16) max f X u V log X v V exp(f (u) · f (v )) X f (ni ) · f (u) ni NS (u) I BFS. Immediate neighbors of the source node. I DFS. Increasing distances from the source node.

Method: metapath2vec (KDD’17) I meta-path based random walk i 1 i p v vt , P 0 I v i 1 , vti E , φ v i 1 t 1 v i 1 , vti E , φ v i 1 6 t 1 v i 1 , vtt / E 1 Nt 1 vti 0 (heterogeneous) negative sample p (ct v ; θ) P e Xct ·Xv Xu·Xv u V e , p (ct v ; θ) P e Xct ·Xv ut Vt M X m log σ Xct · Xv Eu m P(u) log σ Xu · Xv m 1 e Xut ·Xv

Method: LINE (WWW’15)

Method: SDNE (KDD’16) L1st n X (K ) si,j yi i,j 1 L2nd n X i 1 (K ) yj k(x̂i xi ) 2 2 n X si,j kyi yj k22 i,j 1 bi k22 k(X̂ X ) Bk2F

Method: GCN (ICLR’17) Z f (X , A) softmax  ReLU ÂXW (0) W (1) L F XX l YL f 1 Ylf ln Zlf

Method: GraphSage (NIPS’17) I Mean aggregator n o n o hkv σ W · MEAN hk 1 hk 1 , u N (v ) v u I I LSTM aggregator Pooling aggregator n o hkv max σ Wpool hkui b , ui N (v ) JG (zu ) log σ z Q · Evn Pn (v ) log σ z u zv u zvn

Method: GAT (ICLR’18) exp αij P k Ni h i a T W hi kW hj LeakyReLU X 0 h i , hi σ αij W hj exp LeakyReLU a T W hi kW hk j Ni K X X 1 k k 0 hi σ α ij W hj K j N k 1 i

Method: RHINE (AAAI’19) f (p, q) wpq kxp xq k22 g (u, v ) wuv kxu yr xv k L LEuAR LTrIR P s RAR hp,s,qi PAR hp0 ,s,q0 i P 0 max [0, γ f (p, q) f (p 0 , q 0 )] AR P r RIR hu,r ,v i PIR hu0 ,r ,v 0 i P 0 max [0, γ g (u, v ) g (u 0 , v 0 )] IR

Method: HAN (WWW’19) h0i Mφi · hi , αijΦ 0 0 exp σ aT Φ · hi khj P , T 0 0 k N Φ exp (σ (aΦ · [hi khk ])) zΦ i σ i wΦi 1 X T q ·tanh W · zΦ i b , V i V exp (wΦi ) βΦi PP , i 1 exp (wΦi ) X αijΦ · h0j j NiΦ Z P X i 1 βΦi ·ZΦi

Method: DynamicTrias (AAAI’18) I Triadic closure process t Ptr (i, j, k) I 1 D E 1 exp θ, x tijk Social homophily and temporal smoothness g t (j, k) u tj u tk 2 2 , Ltsmooth PN i 1 0 u ti u it 1 2 2 t 1 t 1

Method: HTNE (KDD’18)

Application

Application: Node Clustering I Setting I Evaluation NMI (C , C 0 ) MI (C ,C 0 ) max(H(C ),H(C 0 )) H(C ) is the entropy of C , and MI (C , C 0 ) is the mutual information metric of C and C 0 . Yuanfu Lu et al. Relation Structure-Aware Heterogeneous Information Network Embedding. AAAI2019.

Application: Node Classification I Setting I Evaluation Xiao Wang et al. Heterogeneous Graph Attention Network. WWW2019.

Application: Network Reconstruction I Setting I Evaluation Precision@k {(i,j) (i,j) Ep Eo } Ep Ep is the set of top-k predicted links, Eo is the set of observed links. Daxin Wang et al. Structural Deep Network Embedding. KDD2016.

Application: Link Prediction I Setting I Evaluation Yukuo Cen et al. Representation Learning for Attributed Multiplex Heterogeneous Network. KDD2019.

Application: Recommendation I Setting I Evaluation Mingdong Ou et al. Asymmetric Transitivity Preserving Graph Embedding. KDD2016.

Outline I Problem I Methodology I Application I Conclusion

Conclusion I Existing methods summary I Existing methods problem I Future work

I I I I I I I I I I I I I I I I I I I I I I I I Hongyun Cai et al. A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications. TKDE2017. Peng Cui et al. A Survey on Network Embedding. TKDE2018. Palash Goyal et al. Graph Embedding Techniques, Applications, and Performance: A Survey. arXiv2017. Mikolov et al. Efcient Estimation of Word Representations in Vector Space. ICLR2013. Bryan Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD2014. Jian Tang et al. LINE: Large-scale Information Network Embedding. WWW2015. Jian Tang et al. PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks. KDD2015. Shaosheng Cao et al. GraRep: Learning Graph Representations with Global Structural Information. CIKM2015. Aditya Grover et al. node2vec: Scalable Feature Learning for Networks. KDD2016. Mingdong Ou et al. Asymmetric Transitivity Preserving Graph Embedding. KDD2016. Daixin Wang et al. Structural Deep Network Embedding. KDD2016. Yuxiao Dong et al. metapath2vec: Scalable Representation Learning for Heterogeneous Networks. KDD2017. Linchuan Xu et al. Embedding of Embedding (EOE) : Joint Embedding for Coupled Heterogeneous Networks. WSDM2017. Tao-yang Fu et al. HIN2Vec: Explore Meta-paths in Heterogeneous Information Networks for Representation Learning. CIKM2017. Thomas N. Kipf et al. Semi-supervised Classification with Graph Convolution Networks. ICLR2017. William L. Hamilton et al. Inductive Representation Learning on Large Graphs. NIPS2017. Dingyuan Zhu et al. High-order Proximity Preserved Embedding For Dynamic Networks. TKDE2018. Hongxu Chen et al. PME: Projected Metric Embedding on Heterogeneous Networks for Link Prediction. KDD2018. Chuan Shi et al. Heterogeneous Information Network Embedding for Recommendation. TKDE2018. Lekui Zhou et al. Dynamic Network Embedding by Modeling Triadic Closure Process. AAAI2018. Yuan Zuo et al. Embedding Temporal Network via Neighborhood Formation. KDD2018. Petar Velickovic et al. Graph Attention Networks. ICLR2018. Yuanfu Lu et al. Relation Structure-Aware Heterogeneous Information Network Embedding. AAAI2019. Xiao Wang et al. Heterogeneous Graph Attention Network. WWW2019.

Thank You Q&A

I Lekui Zhou et al. Dynamic Network Embedding by Modeling Triadic Closure Process. AAAI2018. I Yuan Zuo et al. Embedding Temporal Network via Neighborhood Formation. KDD2018. I Petar Velickovic et al. Graph Attention Networks. ICLR2018. I Yuanfu Lu et al. Relation Structure-Aware Heterogeneous Information Network Embedding. AAAI2019.