DeepIS: Susceptibility Estimation on Social Networks

被引:25
作者
Xia, Wenwen [1 ]
Li, Yuchen [2 ]
Wu, Jun [1 ]
Li, Shenghong [1 ]
机构
[1] Shanghai Jiao Tong Univ, Shanghai, Peoples R China
[2] Singapore Management Univ, Singapore, Singapore
来源
WSDM '21: PROCEEDINGS OF THE 14TH ACM INTERNATIONAL CONFERENCE ON WEB SEARCH AND DATA MINING | 2021年
关键词
Influence Estimation; Graph Neural Networks; Social Networks; INFLUENCE MAXIMIZATION; SYSTEMS;
D O I
10.1145/3437963.3441829
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Influence diffusion estimation is a crucial problem in social network analysis. Most prior works mainly focus on predicting the total influence spread, i.e., the expected number of influenced nodes given an initial set of active nodes (aka. seeds). However, accurate estimation of susceptibility, i.e., the probability of being influenced for each individual, is more appealing and valuable in real-world applications. Previous methods generally adopt Monte Carlo simulation or heuristic rules to estimate the influence, resulting in high computational cost or unsatisfactory estimation error when these methods are used to estimate susceptibility. In this work, we propose to leverage graph neural networks (GNNs) for predicting susceptibility. As GNNs aggregate multi-hop neighbor information and could generate over-smoothed representations, the prediction quality for susceptibility is undesirable. To address the shortcomings of GNNs for susceptibility estimation, we propose a novel DeepIS model with a two-step approach: (1) a coarse-grained step where we estimate each node's susceptibility coarsely; (2) a fine-grained step where we aggregate neighbors' coarse-grained susceptibility estimations to compute the fine-grained estimate for each node. The two modules are trained in an end-to-end manner. We conduct extensive experiments and show that on average DeepIS achieves five times smaller estimation error than state-of-the-art GNN approaches and two magnitudes faster than Monte Carlo simulation.
引用
收藏
页码:761 / 769
页数:9
相关论文
共 51 条
[1]  
[Anonymous], 2002, KDD 2002, DOI DOI 10.1145/775047.775057
[2]  
[Anonymous], 2012, MLG
[3]  
Borgs C., 2014, P 24 ANN ACM SIAM S, P946, DOI [DOI 10.1137/1.9781611973402.70, 10.1137/1.9781611973402.70]
[4]  
Burden R.L., 2010, Numerical analysis, V9
[5]   DeepHawkes: Bridging the Gap between Prediction and Understanding of Information Cascades [J].
Cao, Qi ;
Shen, Huawei ;
Cen, Keting ;
Ouyang, Wentao ;
Cheng, Xueqi .
CIKM'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON INFORMATION AND KNOWLEDGE MANAGEMENT, 2017, :1149-1158
[6]   Online Topic-Aware Influence Maximization [J].
Chen, Shuo ;
Fan, Ju ;
Li, Guoliang ;
Feng, Jianhua ;
Tan, Kian-lee ;
Tang, Jinhui .
PROCEEDINGS OF THE VLDB ENDOWMENT, 2015, 8 (06) :666-677
[7]   Efficient Influence Maximization in Social Networks [J].
Chen, Wei ;
Wang, Yajun ;
Yang, Siyu .
KDD-09: 15TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 2009, :199-207
[8]  
Chen Wei, 2010, P KDD, P1029, DOI DOI 10.1145/1835804.1835934
[9]   OCTOPUS: An Online Topic-Aware Influence Analysis System for Social Networks [J].
Fan, Ju ;
Qiu, Jiarong ;
Li, Yuchen ;
Meng, Qingfei ;
Zhang, Dongxiang ;
Li, Guoliang ;
Tan, Kian-Lee ;
Du, Xiaoyong .
2018 IEEE 34TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE), 2018, :1569-1572
[10]   Talk of the network: A complex systems look at the underlying process of word-of-mouth [J].
Goldenberg, J ;
Libai, B ;
Muller, E .
MARKETING LETTERS, 2001, 12 (03) :211-223