Entity search Who are most similar to christos faloutsos? [Sun et al. 2011] (a)Path: APA Rank Author Score Christos Faloutsos Spiros Papadimitriou127 Jimeng sun 0.12 Term Conf 34567891 ia-Yu pan 0.114 Agma J.M. Traina0110 Jure Leskovec 0.096 Paper Caetano traina r 0.096 Hanghang tong 0.091 Deepayan Chakrabarti0083 Flip Kor 0.053 Author (c) Path: APTPA Rank Author Score 123 Christos faloutsos Jian Pei 0.661 Srinivasan Parthasarathy0600 Jeffrey Xu Y 0.587 456789 Ming-Syan Chen 0.579 Jiawei Han 0.576 Mohammed Javeed Zaki0571 Hans-Peter K 0.563 Yannis Manolopoulos 0.548 10 Rakesh agrawal 0.545
Entity Search • Who are most similar to Christos Faloutsos? – [Sun et al., 2011 ] 16
What's Still Missing/Unachievable Let's consider a random walk on grap Construct n *n adjacency matrix M Normalize W=D-1/2MD-1/2(D: degree matrix) One step random walk: p+l= Wpt Stationary distribution follows: p= Wp PageRank
What’s Still Missing/Unachievable? • Let’s consider a random walk on graph – Construct 𝑛 ∗ 𝑛 adjacency matrix 𝐌 – Normalize 𝐖 = 𝐃 −𝟏/𝟐𝐌𝐃 −𝟏/𝟐 (𝐃: degree matrix)) – One step random walk: 𝐩 𝑡+1 = 𝐖𝐩 𝑡 – Stationary distribution follows: 𝐩 = 𝐖𝐩 17
Personalized page rank Page Rank [page et al., 98 p+1=(E+(1-aw)p With a probability to randomly /lazily jump Personalized page Rank/semi-supervised learning [Haveliwala et al. TKDE 03, Jeh and Widom, WWw03 [ Zhu et al. ICML03, Zhou et al., NIPS 03 1=aq+(1-Wp With a probability to restart with a label prior Walk length: 0 Alpha:0 Distance: Inf Walk length: 0 Alpha: 0. 1 Distance: Inf Walk length:0 Alpha: 0.5 Distance: Inf Lazy random Walk PPR alph ha=0.1) PR(alpha =0.5)
Personalized PageRank • PageRank [Page et al., ‘98] – 𝐩 t+𝟏 = (α𝐄 + 1 − α 𝐖)𝐩 t – With a probability to randomly/lazily jump • Personalized PageRank/semi-supervised learning – [Haveliwala et al., TKDE’03, Jeh and Widom, WWW’03] – [Zhu et al., ICML’03, Zhou et al., NIPS’03] – 𝐩 𝑡+𝟏 = α𝐪 + (1 − α)𝐖𝐩 𝑡 – With a probability to restart with a label: prior Lazy Random Walk PPR (alpha = 0.1) PPR(alpha = 0.5) 18