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

Erfan Ahmadi; Mina Shirazi; Behnam Bahrak

cs.LGSep 12, 2026

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

Authors: Erfan Ahmadi, Mina Shirazi, Behnam Bahrak

Organizations: Computer Engineering Department, Tehran Institute for Advanced Studies (TeIAS), Tehran, Iran. · University of Tehran, Tehran, Iran.

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.

Figures & tables

Figure 1: Ground truth versus model prediction on a representative 19-node test graph, using the 3-Phase decoding strategy. Left: the optimal dominating set (orange, 4 of 19 nodes). Right: predicted selection probabilities, with node fill shaded from light (low probability) to dark navy (high probability); a green outline marks the four nodes selected during Phase 1 (outlier detection) and a red outline marks the one additional node added during Phase 3 (greedy completion), giving a 5-node predicted set. Two of the four optimal nodes are recovered exactly (2/4 match), and the predicted set fully dominates all 19 vertices.

Graph	$\|V\|$	Opt	Trivial-G	Static-G	Dynamic-G
dolphins	62	14	25	19	16
florentine families	16	4	7	4	4
high tech company	21	1	3	1	1
highschool	70	11	19	14	12
Les Misérables	77	10	22	23	10
Klas12b	26	5	8	7	6

Table 1: DS size on benchmark instances: classical baselines. Bold = optimal solution achieved. Bottom row reports average relative error across all graphs for these methods.

Graph	$\|V\|$	Sim-Ann	EGN-MDS	Kothapalli	Ours
dolphins	62	14	31	14	16
florentine families	16	4	14	4	4
high tech company	21	1	2	1	1
highschool	70	11	23	11	14
Les Misérables	77	10	36	10	11
Klas12b	26	5	15	5	5

Table 2: DS size on benchmark instances: metaheuristic and learning-based methods. Bold = optimal solution achieved. Bottom row reports average relative error across all graphs for these methods.

Graph	$\|V\|$	Trivial-G	Static-G	Dynamic-G
dolphins	62	0.07	0.09	6.05
florentine families	16	0.02	0.02	0.10
high tech company	21	0.01	0.02	0.04
highschool	70	0.09	0.08	0.89
Les Misérables	77	0.03	0.06	0.72
Klas12b	26	0.03	0.05	0.35

Table 3: Inference time (ms) per graph instance: classical baselines. SA runs 5,000 iterations per graph.

Graph	$\|V\|$	Sim-Ann	EGN-MDS	Kothapalli	Ours
dolphins	62	1017.7	53.6	405	41.3
florentine families	16	226.5	29.6	52	20.9
high tech company	21	407.2	9.1	83	15.4
highschool	70	1123.8	72.1	618	44.7
Les Misérables	77	1116.9	90.7	456	46.0
Klas12b	26	445.4	11.8	106	27.9

Table 4: Inference time (ms) per graph instance: metaheuristic and learning-based methods. GNN times include single forward pass and ensemble decoding. Bold = fastest among methods with

\leq 10\%

average relative error.

Explore similar work

Enhancing Discrete Particle Swarm Optimization for Hypergraph-Modeled Influence Maximization
Apr 17, 2026Qianshi Wang, Xilong Qu, Wenbin Pei +2Metaheuristic Optimization Particle Swarm Optimization
International School of Information Science & Engineering, Dalian University of Technology, Dalian 116024, China · School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China; Key Laboratory of Social Computing and Cognitive Intelligence (Dalian University of Technology), Ministry of Education, Dalian 116024, China · School of Artificial Intelligence, Shanxi University, Taiyuan 237016, China +1
Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search
Aug 9, 2026Yiqiao Liao, Parinaz NaghizadehNeural Surrogate Modeling
UC San Diego
Revealing graph bandits for maximizing local influence
May 1, 2026Alexandra Carpentier, Michal ValkoMulti-Armed Bandits Graph Bandits
Universität Potsdam · SequeL team, Inria Lille - Nord Europe

Apr 17, 2026, cs.SIJ/K move · Enter open · S save

Enhancing Discrete Particle Swarm Optimization for Hypergraph-Modeled Influence Maximization

Qianshi Wang, Xilong Qu, Wenbin Pei, Nan Li+1

International School of Information Science & Engineering, Dalian University of Technology, Dalian 116024, China · School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China; Key Laboratory of Social Computing and Cognitive Intelligence (Dalian University of Technology), Ministry of Education, Dalian 116024, China · School of Artificial Intelligence, Shanxi University, Taiyuan 237016, China+1

Metaheuristic Optimization Particle Swarm Optimization Graph Diffusion

Open paper AskPDF arXiv

Influence maximization (IM) is a fundamental problem in complex network analysis, with a wide range of real-world applications. To date, existing approaches to influential node identification in IM have predominantly relied on standard graphs, failing to capture higher-order intrinsic interactions embedded in many real-world systems. Hypergraphs can be employed to better capture higher-order interactions. However, using hypergraphs may lead to an excessively large search space and increased complexity in modeling cascading dynamics, making it challenging to accurately identify influential nodes. Therefore, in this study, we propose a new hypergraph-modeled IM method, based on the Discrete Particle Swarm Optimization algorithm and the threshold model. In the proposed method, a particle (i.e., a candidate solution) represents the selection information of seed nodes, and the fitness function is designed to accurately and efficiently evaluate the influence of seed nodes via a two-layer local influence approximation. We also propose a degree-based initialization strategy to improve the quality of initial solutions and develop rules for updating particles' velocity and position, incorporated with a local search to drive particles toward better solutions. Experimental results demonstrate that the proposed method outperforms baseline methods on both synthetic and real-world hypergraphs. In addition, ablation studies validate the effectiveness of both the local search and the initialization strategies.

Abstract

Explore similar work

Enhancing Discrete Particle Swarm Optimization for Hypergraph-Modeled Influence Maximization

Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search

Revealing graph bandits for maximizing local influence