Graph neural networks speed up finding key influencers in social networks
Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach
Machine LearningSocial and Information Networks
Summary
Finding the smallest group of people who can influence everyone in a social network is very hard and slow. The authors use a kind of AI called graph neural networks to quickly find these key influencers without needing example answers to learn from. Their method works much faster than previous approaches and still finds very good groups on real social networks. It also works well on different kinds of networks it hasn't seen before.
What this means in practice
- •For social media marketing teams: Identify small groups of users who can spread marketing campaigns widely and quickly using a fast AI-based method.
- •For public health planners: Find minimal sets of individuals to target for health interventions that will cover entire communities efficiently.
Authors
Erfan Ahmadi, Mina Shirazi, Behnam Bahrak
Abstract
The Minimum Dominating Set (MDS) problem is a classic NP-hard combinatorial optimization problem with critical applications in social network analysis, including viral marketing, influence maximization, public health interventions, and information dissemination. Identifying a minimal set of influential individuals whose reach covers an entire social network is central to these applications, yet remains computationally challenging at scale. Graph neural networks (GNNs) have emerged as powerful tools for learning over graphs, and recent work explores their application to hard combinatorial problems. This paper presents a novel unsupervised GNN framework for the MDS problem that eliminates the need for ground-truth solutions during training. Trained on 12,000 synthetic graphs with diverse structural properties, our method achieves up to 55x faster inference than metaheuristic baselines and up to 14x faster inference than supervised learning approaches, while finding optimal or near-optimal dominating sets on real-world social network benchmarks. Our learned heuristic generalizes effectively to unseen graph distributions, demonstrating strong practical applicability for large-scale social network analysis.