Combinatorial optimization; Graph neural networks; Influence maximization; Social networks; Graph representation; Optimisations; Information Systems
Abstract :
[en] Finding the seed set that maximizes the influence spread over a network is a well-known NP-hard problem. Though a greedy algorithm can provide near-optimal solutions, the subproblem of influence estimation renders the solutions inefficient. In this work, we propose Glie, a graph neural network that learns how to estimate the influence spread of the independent cascade. Glie relies on a theoretical upper bound that is tightened through supervised training. Experiments indicate that it provides accurate influence estimation for real graphs up to 10 times larger than the train set. Subsequently, we incorporate it into three influence maximization techniques. We first utilize Cost Effective Lazy Forward optimization substituting Monte Carlo simulations with Glie, surpassing the benchmarks albeit with a computational overhead. To improve computational efficiency, we develop Pun, a provably submodular influence spread based on Glie’s representations, to rank nodes while building the seed set adaptively. Furthermore, we take a step towards an end-to-end learnable approach in Grim, a Q-learning model that learns how to choose seeds sequentially using Glie’s predictions. The proposed algorithms are inductive, meaning they are trained on graphs with a few hundred nodes and tested on graphs with millions. Our methods exhibit the most promising combination of time efficiency and influence quality, outperforming several benchmarks.
Disciplines :
Computer science
Author, co-author :
Panagopoulos, George; Department of Computer Science, University of Luxembourg, Esch-sur-Alzette, Luxembourg
Tziortziotis, Nikolaos; Jellyfish, Paris, France
Vazirgiannis, Michalis; École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France
PANG, Jun ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Malliaros, Fragkiskos D.; Université Paris-Saclay, CentraleSupélec, Inria, Gif-sur-Yvette, France
External co-authors :
yes
Language :
English
Title :
Learning graph representations for influence maximization
A.-L. Barabási R. Albert Emergence of scaling in random networks Science 1999 286 5439 509 512 2091634 10.1126/science.286.5439.509
I. Bello H. Pham Q.V. Le M. Norouzi Bengio 2016 CoRR S Neural combinatorial optimization with reinforcement learning
Borgs C, Brautbar M, Chayes J, Lucier B (2014) Maximizing social influence in nearly optimal time. In: SIAM symposium on discrete algorithms (SODA), pp. 946–957. SIAM
Boyd S, Boyd SP, Vandenberghe L (2004) Convex Optimization
Cautis B, Maniu S, Tziortziotis N Adaptive influence maximization. In: ACM international conference on knowledge discovery and data mining (SIGKDD) (2019)
W. Chen T. Lin Real-time topic-aware influence maximization using preprocessing Comput Soc Netw 2016 3 1 1 19 10.1186/s40649-016-0033-z
Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: ACM international conference on knowledge discovery and data mining (SIGKDD)
Chen H, Qiu W, Ou H.-C, An B, Tambe M (2021) Contingency-aware influence maximization: A reinforcement learning approach. In: internationbal conference on uncertainty in artificial intelligence (UAI)
Chen H, Wilder B, Qiu W, An B, Rice E, Tambe M (2023) Complex contagion influence maximization: a reinforcement learning approach. In: international joint conference on artificial intelligence (IJCAI), pp. 5531–5540
Dai H, Khalil EB, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. arXiv preprint arXiv:1704.01665
Duval A, Malliaros F (2022) Higher-order clustering and pooling for graph neural networks. In: acm international conference on information knowledge management (CIKM), pp. 426–435
C. Fan L. Zeng Y. Sun Y.-Y. Liu Finding key players in complex networks through deep reinforcement learning Nat Mach Intell 2020 2 6 317 324 10.1038/s42256-020-0177-2
D. Golovin Adaptive submodularity: theory and applications in active learning and stochastic optimization J Artific Intell Res 2011 42 427 486 2874807
P. Holme B.J. Kim Growing scale-free networks with tunable clustering Phys Rev E 2002 65 2 10.1103/PhysRevE.65.026107
James G, Witten D, Hastie T, Tibshirani R (2013) An Introduction to Statistical Learning
C.K. Joshi Laurent T 2019 CoRR Bresson X On learning paradigms for the travelling salesman problem
Jung K, Heo W, Chen W (2012) Irie: Scalable and robust influence maximization in social networks. In: IEEE international conference on data mining (ICDM)
Karalias N, Loukas (2020) A Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In: Advances in Neural Information Processing Systems (NeurIPS)
Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: ACM conference on knowledge discovery and data mining (SIGKDD)
Klicpera, J, Bojchevski, A, Günnemann, S (2019) Predict then propagate: Graph neural networks meet personalized pagerank. In: international conference on learning representations (ICLR)
Kool W, Van Hoof H, Welling M (2019) Attention, learn to solve routing problems! In: international conference on learning representations (ICLR)
J. Leskovec Snap: a general-purpose network analysis and graph-mining library ACM Trans Intell Syst Technol 2016 8 1 1 20 2900491 10.1145/2898361
Leskovec J Krause, A Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: ACM international conference on knowledge discovery and data mining (SIGKDD)
Li H, Xu M, Bhowmick SS, Sun C, Jiang Z, Cui J (2019) Disco Influence maximization meets network embedding and deep learning. arXiv preprint arXiv:1906.07378
Li Z, Chen Q, Koltun V (2018) Combinatorial optimization with graph convolutional networks and guided tree search. arXiv preprint arXiv:1810.10659
Ling, C, Jiang, J, Wang, J, Thai, M.T, Xue, R, Song, J, Qiu, M, Zhao, L (2023) Deep graph representation learning and optimization for influence maximization. In: International Conference on Machine Learning (ICML), pp. 21350–21361. PMLR
A.Y. Lokhov Saad 2019 CoRR D Scalable influence estimation without sampling
F.D. Malliaros C. Giatsidis A.N. Papadopoulos M. Vazirgiannis The core decomposition of networks: theory, algorithms and applications VLDB J 2020 29 1 61 92 10.1007/s00778-019-00587-4
S. Manchanda A. Mittal A. Dhawan S. Medya S. Ranu A. Singh Gcomb: learning budget-constrained combinatorial algorithms over billion-sized graphs Adv Neural Inf Process Syst (NeurIPS) 2020 33 20000 20011
Manchanda S, Michel, S, Drakulic D, Andreoli JM (2022) On the generalization of neural combinatorial optimization heuristics. In: Joint European conference on machine learning and knowledge discovery in databases (ECML-PKDD), pp. 426–442 Springer
N. Mathew S.L. Smith S.L. Waslander Planning paths for package delivery in heterogeneous multirobot teams IEEE Trans Autom Sci Eng 2015 12 4 1298 1308 10.1109/TASE.2015.2461213
A. Mirhoseini A. Goldie M. Yazgan J.W. Jiang E. Songhori S. Wang Y.-J. Lee E. Johnson O. Pathak A. Nazi A graph placement methodology for fast chip design Nature 2021 594 7862 207 212 10.1038/s41586-021-03544-w
G. Panagopoulos F. Malliaros M. Vazirgiannis Multi-task learning for influence estimation and maximization IEEE Trans Knowl Data Eng 2020 34 9 4398 4409 10.1109/TKDE.2020.3040028
Panagopoulos G, Tziortziotis N, Malliaros FD, Vazirgiannis M (2023) Maximizing influence with graph neural networks. In: IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM) (2023)
Panagopoulos G, Malliaros FD, Vazirgiannis M (2018) Diffugreedy: An influence maximization algorithm based on diffusion cascades. In: international conference on complex networks and their applications (CNA), pp. 392–404. Springer
Panagopoulos G, Malliaros FD, Vazirgianis M (2020) Influence maximization using influence and susceptibility embeddings. In: international AAAI conference on web and social media (ICWSM), pp. 511–521
Prates M, Avelar PH, Lemos H, Lamb LC, Vardi MY (2019) Learning to solve np-complete problems: a graph neural network for decision tsp. In: AAAI conference on artificial intelligence (AAAI)
Seyfi M, Banitalebi-Dehkordi A, Zhou Z, Zhang Y (2023). Exact combinatorial optimization with temporo-attentional graph neural networks. In: Joint European conference on machine learning and knowledge discovery in databases (ECML-PKDD), pp. 268–283 Springer
Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction
Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: ACM international conference on management of data (SIGMOD)
Y. Tian R. Lambiotte Unifying information propagation models on networks and influence maximization Phys Rev E 2022 106 3 10.1103/PhysRevE.106.034316
S. Tian S. Mo L. Wang Deep reinforcement learning-based approach to tackle topic-aware influence maximization Data Sci Eng 2020 5 1 1 11 10.1007/s41019-020-00117-1
N. Touati-Moungla Jost V Combinatorial optimization for electric vehicles management J Energy Power Eng 2012 6 5 738 743
Van Hasselt H, Guez A, Silver D (2016) Deep reinforcement learning with double q-learning. In: AAAI conference on artificial intelligence (AAAI)
Veličković, P, Badia AP, Budden D, Pascanu R, Banino A, Dashevskiy M, Hadsell R, Blundell C (2022) The clrs algorithmic reasoning benchmark. In: international conference on machine learning (ICML), pp. 22084–22102 PMLR
Vinyals O, Fortunato M (2015) Jaitly. Advances in Neural Information Processing Systems (NeurIPS), N Pointer networks. In
C. Wang W. Chen Y. Wang Scalable influence maximization for independent cascade model in large-scale social networks Data Min Knowl Disc 2012 25 3 545 576 2967886 10.1007/s10618-012-0262-1
Z. Wu S. Pan F. Chen G. Long C. Zhang S.Y. Philip A comprehensive survey on graph neural networks IEEE Trans Neural Netw Learn Syst 2020 32 1 4 24 4205495 10.1109/TNNLS.2020.2978386
Xia, W, Li, Y, Wu, J, Li, S (2021) Deepis: Susceptibility estimation on social networks. In: ACM international conference on web search and data mining (WSDM)
C. Zhou P. Zhang W. Zang On the upper bounds of spread for greedy algorithms in social network influence maximization IEEE Trans Knowl Data Eng 2015 27 10 2770 2783 10.1109/TKDE.2015.2419659
