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

• URL: http://arxiv.org/abs/2609.13836v1
• Date: Sat, 12 Sep 2026 09:44:36 GMT
• Title: Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach
• Abstract summary: The Minimum Dominating Set (MDS) problem is a classic NP-hard optimization problem with critical applications in social network analysis.<n>This paper presents a novel unsupervised GNN framework for the MDS problem that eliminates inference for ground-truth solutions during training.<n>Our method achieves up to 55x faster than metaheuristic baselines and up to 14x faster than supervised learning approaches.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs [81.39865232674413]
  Graph Neural Networks (GNNs) have emerged as a powerful tool for wireless resource allocation.<n>This work establishes theoretical results for transferability of GNNs over graphs derived from sparse Random Geometric Graphs (RGGs)
  arXiv  Detail & Related papers  (2026-06-02T15:42:14Z)
• A Distributed Training Architecture For Combinatorial Optimization [0.0]
  We propose a distributed graph neural network (GNN)-based training framework for optimization.<n>Experiments are conducted on both real large-scale social network datasets and synthetically generated high-complexity graphs.<n>Our framework outperforms state-of-the-art approaches in both solution quality and computational efficiency.
  arXiv  Detail & Related papers  (2025-11-12T12:22:10Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  We propose ScaleGNN, a novel framework that adaptively fuses multi-hop node features for scalable and effective graph learning.<n>We show that ScaleGNN consistently outperforms state-of-the-art GNNs in both predictive accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2025-04-22T14:05:11Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
  Combinatorial optimization (CO) is the fundamental problem at the intersection of computer science, applied mathematics, etc. In this paper, we design a family of non-autoregressive neural networks to solve CO problems under positive linear constraints. We validate the effectiveness of this framework in solving representative CO problems including facility location, max-set covering, and traveling salesman problem.
  arXiv  Detail & Related papers  (2024-09-06T14:58:31Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• Network Interdiction Goes Neural [26.308933674471895]
  Network interdiction problems are optimization problems involving two players. One aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives.
  arXiv  Detail & Related papers  (2024-05-26T02:34:26Z)
• Finding Influencers in Complex Networks: An Effective Deep Reinforcement Learning Approach [13.439099770154952]
  We propose an effective reinforcement learning model that achieves superior performances over traditional best influence algorithms. Specifically, we design an end-to-end learning framework that combines graph neural network algorithms as the encoder and reinforcement learning as the decoder, named DREIM.
  arXiv  Detail & Related papers  (2023-09-09T14:19:00Z)
• ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning [4.266866385061998]
  We propose a novel end-to-end DRL framework, ToupleGDD, to address the Influence Maximization (IM) problem. Our model is trained on several small randomly generated graphs with a small budget, and tested on completely different networks under various large budgets.
  arXiv  Detail & Related papers  (2022-10-14T03:56:53Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Graph Neural Networks for Wireless Communications: From Theory to Practice [10.61745503150249]
  Graph neural networks (GNNs) can effectively exploit the domain knowledge, i.e., the graph topology in wireless communication problems. For theoretical guarantees, we prove that GNNs achieve near-optimal performance in wireless networks with much fewer training samples than traditional neural architectures. For design guidelines, we propose a unified framework that is applicable to general design problems in wireless networks.
  arXiv  Detail & Related papers  (2022-03-21T08:39:44Z)
• FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks [39.86798194955807]
  Finding influential users in social networks is a fundamental problem with many possible useful applications. 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. 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.
  arXiv  Detail & Related papers  (2021-10-31T10:49:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.