Graph Neural Networks and Applications Jie Tang Computer Science Tsinghua University The slides can be downloaded at http://keg.cs.tsinghuaeducn/jietang
1 Graph Neural Networks and Applications Jie Tang Computer Science Tsinghua University The slides can be downloaded at http://keg.cs.tsinghua.edu.cn/jietang
Networked world facebook Alibaba Group 里巴巴集团 ·2 billion mau >777 million trans. (alipay) 26.4 billion minutes/day ·200 billion on11/11 twitter 新浪微博 weibo. com 320 million mau ·462 million users ·Peak:143 K tweets/s influencing our daily life instagram 头系今日头条 700 million Mau 1.5 billion mau ·95 million pics/day 70 minutes/user/day snapchat ·300 million mau QQ 860 million mau ·30 minutes/use/day WeChat: 1.1 billion Mau
2 Networked World • 2 billion MAU • 26.4 billion minutes/day • 462 millionusers • influencing our daily life • 320 millionMAU • Peak: 143K tweets/s •QQ: 860 million MAU • WeChat: 1.1 billion MAU • 700 millionMAU • 95 million pics/day • >777 million trans. (alipay) • 200 billion on 11/11 • 300 millionMAU • 30 minutes/user/day • ~1.5 billion MAU • 70 minutes/user/day
Mining big Graphs/Networks An information/social graph is made up of a set of individuals/entities (nodes)tied by one or more interdependency (edges), such as friendship Mining big networkS: A field is emerging that leverages the capacity to collect and analyze data at a scale that may reveal patterns of individu and group behaviors.” 1. David Lazer, Alex Pentland, Lada Adamic, Sinan Aral, Alber-Laszlo Barabasi, et aL. Computational Social Science. Science 2009
3 Mining Big Graphs/Networks • An information/social graph is made up of a set of individuals/entities (“nodes”) tied by one or more interdependency (“edges”), such as friendship. 1. David Lazer, Alex Pentland, Lada Adamic, Sinan Aral, Alber-Laszlo Barabasi, et al. Computational Social Science. Science 2009. Mining big networks: “A field is emerging that leverages the capacity to collect and analyze data at a scale that may reveal patterns of individual and group behaviors.” [1]
Let us start with an example Social influence and prediction
4 Let us start with an example —Social influence and prediction
Social Influence: Love Trump Trump makes I hate Trump, the USa great again worst president ever Trump is fantastic Trump is great No Trump in 2020 He cannot be the next president O Positive ONe
5 Social Influence: “Love Trump” Trump makes USA great again Trump is great! Trump is fantastic I hate Trump, the worst president ever He cannot be the next president! No Trump in 2020! Positive Negative
Beyond Peer Influence Influence is a very complicated mechanism Peer influence Conformity influence Structural influence Tahl I Lanier ad different comunale suchan or Positive or negative?
6 Beyond Peer Influence • Influence is a very complicated mechanism – Peer influence – Conformity influence – Structural influence or ? Positive or negative?
Social prediction in Tencent networks Example: King of Glory(王者荣耀 o。9E F C OA C OIA Who are more likely to be"active", V, or v2? e.g., active ="call-back King of Glory O Active neighbor O Inactive neighbor User to be influenced 1. J. Qiu, J. Tang, H Ma, Y Dong, K Wang, and J. Tang. DeepInf: Social Influence Prediction with Deep Learning. KDD18
7 Social prediction in Tencent networks Active neighbor Inactive neighbor v User to be influenced Who are more likely to be “active”, v1 or v2? v A B D E F C v H A B H D E F C v1 v2 e.g., active = “call-back King of Glory” Example: King of Glory (王者荣耀) 1. J. Qiu, J. Tang, H. Ma, Y. Dong, K. Wang, and J. Tang. DeepInf: Social Influence Prediction with Deep Learning. KDD'18
Structural Influence B C 2.5 25 2.0 2.0 2.0 co28 至::[:至 型0.5 0.5 Contact ma已边m-e 1. J Gander, L Backstrom, C Marlow, J Kleinberg. Structural diversity in social contagion. PNAS, 2012, 109(16)5962-5966
8 Structural Influence 1. J. Ugander, L. Backstrom, C. Marlow, J. Kleinberg. Structural diversity in social contagion. PNAS, 2012, 109 (16) 5962-5966
Influence Learning Learning influence in signed triads And apply the triadic influence for prediction REGRESSION ANALYSIS FOR 30 KINDS OF TRIADS Triad Coet Coef Triad 008272 0.0110*享 3画◎|00543 0.0004 @|00429 (0.003) (0.004) (0.003) (0.004) 5 (0.003) 6·|087 7o00.020586-o.0313% 9|4083 00070●0168* (0.002) 10012ooau‖sy .0563 -00221 14 (0.002) 5 0.0157* (0.001) (0003) 6画@0167*17 0.0164 (0.003) 画00841900032 0.0066年 0.002) -0.0001 20.0090 8600534-2466-0. o 0.0089* (0.002) (0002) (0.002) (0.002) (0.001) 0.0783哪 0.0818·审 0.0494*率 00 0.002) 30画0072 (0.002)
9 Influence Learning • Learning influence in signed triads • And apply the triadic influence for prediction
Possible solution Influence features hand craft features E> predictive model Name Description oneness Pagerank [30 Hub score and authority score [8] Vertex Eigenvector Centrality [5] oo Class +1 Clustering Coefficient [46] Rarity(reciprocal of ego user's degree)[1] Network embedding(DeepWalk [31], 64-dim) The number/ratio of active neighbors [2] Class-1 Ego Density of subnetwork induced by active neighbors [40] edictive #Connected components formed by active neighbors [40] model But defining features is tedious and inefficient
10 Possible Solution • Influence features + Hand craft features predictive model + Class -1 Class +1 predictive model But defining features is tedious and inefficient…