# Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 12 Sep 2026.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs](https://mlsanity.com/paper/2405.20543/) (2024)
- [Theoretical guarantees for the advantage of GNNs over NNs in generalizing bandlimited functions on Euclidean cubes](https://mlsanity.com/paper/2206.05904/) (2022)
- [Minimum Dominating Sets in Scale-Free Network Ensembles](https://mlsanity.com/paper/1302.2518/) (2013)

## Abstract (arXiv)

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.