Learning graph representations for influence maximization

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.