Deep Graph Representation Learning and Optimization for Influence Maximization
Deep Graph Representation Learning and Optimization for Influence Maximization
复制标题
DOI：
10.48550/arxiv.2305.02200
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Chen Ling;Junji Jiang;Junxiang Wang;M. Thai;Lukas Xue;James Song;M. Qiu;Liang Zhao
中科院分区：
文献类型：
--
作者：
Chen Ling;Junji Jiang;Junxiang Wang;M. Thai;Lukas Xue;James Song;M. Qiu;Liang Zhao
影响力最大化(IM)是指从社交网络中选择一组初始用户以最大化预期的受影响用户数量。研究人员在设计各种传统方法方面取得了很大进展，其理论设计和性能增益都接近极限。在过去的几年里，出现了基于学习的IM方法，它比传统的方法对未知图形具有更强的泛化能力。然而，基于学习的IM方法的发展仍然受到根本障碍的限制，包括1)有效地求解目标函数的困难；2)描述多样化的潜在扩散模式的困难；3)解决方案在各种节点中心性约束的IM变体下的适应困难。为了应对上述挑战，我们设计了一个新的框架DeepIM来产生性地刻画种子集的潜在表示，并提出以数据驱动和端到端的方式学习多样化的信息扩散模式。最后，我们设计了一种新的目标函数来推断灵活节点中心性预算约束下的最优种子集。对合成数据集和真实数据集进行了广泛的分析，以演示DeepIM的整体性能。代码和数据可在以下网址获得：https://github.com/triplej0079/DeepIM.
Influence maximization (IM) is formulated as selecting a set of initial users from a social network to maximize the expected number of influenced users. Researchers have made great progress in designing various traditional methods, and their theoretical design and performance gain are close to a limit. In the past few years, learning-based IM methods have emerged to achieve stronger generalization ability to unknown graphs than traditional ones. However, the development of learning-based IM methods is still limited by fundamental obstacles, including 1) the difficulty of effectively solving the objective function; 2) the difficulty of characterizing the diversified underlying diffusion patterns; and 3) the difficulty of adapting the solution under various node-centrality-constrained IM variants. To cope with the above challenges, we design a novel framework DeepIM to generatively characterize the latent representation of seed sets, and we propose to learn the diversified information diffusion pattern in a data-driven and end-to-end manner. Finally, we design a novel objective function to infer optimal seed sets under flexible node-centrality-based budget constraints. Extensive analyses are conducted over both synthetic and real-world datasets to demonstrate the overall performance of DeepIM. The code and data are available at: https://github.com/triplej0079/DeepIM.