# FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks

arXiv: https://arxiv.org/abs/2111.00463 · HTML: https://mlsanity.com/paper/2111.00463/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 22 references that are in the map.
- First posted on arXiv 31 Oct 2021.

## Builds on (most cited first, 6 of 6)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning](https://mlsanity.com/paper/2010.05627/) (2020)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks](https://mlsanity.com/paper/1605.07990/) (2016)

## Built on by (most cited first, 4 of 4)

- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Metaheuristics and Large Language Models Join Forces: Toward an Integrated Optimization Approach](https://mlsanity.com/paper/2405.18272/) (2024)
- [Multi-perspective Memory Enhanced Network for Identifying Key Nodes in Social Networks](https://mlsanity.com/paper/2403.15235/) (2024)
- [Non-Progressive Influence Maximization in Dynamic Social Networks](https://mlsanity.com/paper/2412.07402/) (2024)

## Abstract (arXiv)

Finding influential users in social networks is a fundamental problem with many possible useful applications. Viewing the social network as a graph, the influence of a set of users can be measured by the number of neighbors located within a given number of hops in the network, where each hop marks a step of influence diffusion. In this paper, we reduce the problem of IM to a budget-constrained d-hop dominating set problem (kdDSP). We propose a unified machine learning (ML) framework, FastCover, to solve kdDSP by learning an efficient greedy strategy in an unsupervised way. As one critical component of the framework, we devise a novel graph neural network (GNN) architecture, graph reversed attention network (GRAT), that captures the diffusion process among neighbors. Unlike most heuristic algorithms and concurrent ML frameworks for combinatorial optimization problems, FastCover determines the entire seed set from the nodes' scores computed with only one forward propagation of the GNN and has a time complexity quasi-linear in the graph size. Experiments on synthetic graphs and real-world social networks demonstrate that FastCover finds solutions with better or comparable quality rendered by the concurrent algorithms while achieving a speedup of over 1000x.