Influence maximization (IM) involves selecting a set of initial users from a social network to maximize the expected number of influenced users. In recent years, learning-based combinatorial optimization (CO) methods have emerged to develop generalized policies for specific CO problems on graphs. However, these algorithms struggle to manage diversified diffusion patterns, which directly limits their generalization ability. In this paper, we use a reverse influence sampling technique to simplify influence maximization to stochastic maximum coverage on hyperedges. We subsequently formulated the stochastic maximum coverage problem as a generative process, called GFlowIM. This model generates various samples through sequential actions, with probabilities precisely proportional to a predefined reward function. By training on multiple graphs, we learn a transferable seed selection policy that can generalize to unseen test graphs. Extensive experiments demonstrate that our method outperforms recent learning-based and traditional methods on both real and synthetic datasets for the IM problem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Generative Flow Networks for Influence Maximization in Social Networks

  • Zizhen Zhang,
  • Deying Li,
  • Yongcai Wang,
  • Wenping Chen,
  • Yuqing Zhu

摘要

Influence maximization (IM) involves selecting a set of initial users from a social network to maximize the expected number of influenced users. In recent years, learning-based combinatorial optimization (CO) methods have emerged to develop generalized policies for specific CO problems on graphs. However, these algorithms struggle to manage diversified diffusion patterns, which directly limits their generalization ability. In this paper, we use a reverse influence sampling technique to simplify influence maximization to stochastic maximum coverage on hyperedges. We subsequently formulated the stochastic maximum coverage problem as a generative process, called GFlowIM. This model generates various samples through sequential actions, with probabilities precisely proportional to a predefined reward function. By training on multiple graphs, we learn a transferable seed selection policy that can generalize to unseen test graphs. Extensive experiments demonstrate that our method outperforms recent learning-based and traditional methods on both real and synthetic datasets for the IM problem.