Generative Flow Networks for Influence Maximization in Social Networks
摘要
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.