CS Paper Radar

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

Erfan Ahmadi, Mina Shirazi, Behnam Bahrak

cs.LG cs.SI ·submitted 2026-09-12 09:44 UTC · v1

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.

Comment
16 pages, 1 figure, 4 tables. Submitted to the International Journal of Data Science and Analytics

Closest papers

Nearest neighbours by meaning across the whole index.

Algorithmic Fairness for Influence Maximization: A Survey of Models, Metrics, and Optimization Techniques

cs.SI ·2026-10-14 ·Shashank Sheshar Singh, Sunil Kumar Meena, Kuldeep Singh, krati Saxena
survey similarity 0.67
Abstract

Influence maximization (IM) has become a basis of modeling information spread across social networks, with applications in viral marketing, public health, and political campaigns. However, classical IM algorithms often prioritize the spread of overall influence and ignore its fairness, resulting in disadvantages for marginalized or underrepresented communities. This survey provides a detailed look at fairness-aware influence maximization, focusing on important challenges, models, and methods designed to ensure fair influence maximization. We categorize existing methods into five groups based on their fairness objectives, including parity, diversity, and utility, and discuss how they handle biased network structure, protected attributes, and seeding constraints. We also examine how fairness-aware influence maximization methods perform on real-world data to highlight the importance of combining fairness with classical influence maximization methods. By bridging the gap between influence spread and social equity, this survey lays the foundation for designing fair algorithms that ensure fair representation in large-scale diffusion processes. The survey concludes by outlining emerging trends, open challenges, and prospective future directions in the domain, highlighting the need for expertise spanning multiple disciplines.

0.07

CSBA-Net: Learning Cross-Scale Structural Dependencies for Influential Node Identification in Complex Networks

cs.SI ·2026-10-13 ·Rihab Boukheche, Mohammed Lalou, Nardjes Bouchemal
similarity 0.63
Abstract

Identifying influential nodes is a fundamental task in complex network analysis, with applications in epidemic control, information diffusion, and network robustness. Existing centrality-based and learning-based methods often provide limited integration of structural information across different network scales. To address this limitation, we propose CSBA-Net, for Cross-Scale Structural BiGRU Attention Network, a multi-scale structural representation learning framework that jointly captures local, community-level, and global structural patterns. The extracted representations are processed by CNNs and integrated through a BiGRU with multi-head self-attention to model dependencies across structural scales. Influential-node scores are learned through regression using SIR-based diffusion simulations as reference targets. We conduct experiments on 24 real-world and 12 synthetic networks from social, biological, technological, and knowledge domains, and show that CSBA-Net achieves Kendall's tau=0.802, Spearman's rho=0.943, NDCG10 =0.898, and NDCG20 =0.916, outperforming the considered centrality-, CNN-, and GNN-based baselines. The results demonstrate the effectiveness of combining complementary structural scales for accurate influential-node ranking across diverse network structures.

0.12

Influence Ranking Improvement via Link Addition in Social Networks

cs.SI ·2026-09-29 ·Taiki Ikemoto, Sho Tsugawa
published similarity 0.62
Abstract · 15 pages; accepted at ASONAM 2026

Social media platforms increasingly rely on influential users for information dissemination in domains such as marketing and political campaigns. As the value of being recognized as influential grows, users may have incentives to strategically enhance their influence. In this study, we investigate whether and to what extent the influence ranking of a target node can be improved by adding a limited number of outgoing links in the context of influence maximization (IM). We formulate the Link Selection Problem for Influence Ranking Improvement (LSP-IRI) as the problem of selecting a fixed-size set of additional outgoing links from a target node in order to maximize its rank improvement. To examine this problem, we consider two representative heuristic strategies: a greedy method that directly optimizes rank improvement and a computationally efficient random search method. We conduct experiments on four real-world networks ranging from thousands to hundreds of thousands of nodes. The results show that even a few added links can substantially improve IM-based influence rankings. In particular, the greedy method improves the ranks of nodes initially ranked around 50 by several tens of positions on average with only three added links, sometimes moving them into the top 10. The random search method achieves smaller gains under strict budgets but reduces computation time by up to approximately 98% compared with the greedy method and becomes effective when larger budgets are allowed. These findings show that IM-based influence rankings are sensitive to limited local structural modifications and highlight a trade-off between ranking improvement and computational efficiency.

0.33

SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking

cs.SI cs.LG ·2026-09-09 ·Guilherme Henrique Messias, Mariana Caravanti de Souza, Sylvia Iasulaitis, Alan Demétrius Baria Valejo
benchmark similarity 0.61
Abstract · 15 pages

Graph Neural Networks (GNNs) are powerful models for handling attributed graphs in tasks such as classification, link prediction, and community detection, as they enable the aggregation of information from both structural and semantic sources. However, progress in community detection is hindered by the lack of high-quality datasets, since ground-truth community labels are often unavailable and most algorithms proposed in recent literature rely on the same benchmark datasets for model training and evaluation. To address this issue, attributed random graph generators are commonly employed to create synthetic graphs for assessing the strengths and limitations of GNN-based models. Nevertheless, most existing generators rely heavily on power-law degree distributions, despite recent evidence indicating that scale-free networks are rare, particularly in social network contexts. Moreover, state-of-the-art attributed graph generators provide limited flexibility, as they do not allow users to construct communities with varying densities, degree distributions, and sub-community structures. To overcome these limitations, we introduce the Synthetic Community-Aware Attributed Graph Generator (SynCo), a graph generation algorithm that allows users to control the node degree distribution and sub-community structure. We evaluate SynCo across three different tasks: graph mimicking, hyperparameter evaluation, and node clustering tuning. The results show that our model outperforms state-of-the-art approaches in synthetic graph generation and data augmentation, while preserving the original distributions of duplicated and augmented datasets, as confirmed by statistical tests well know in literature. We also demonstrate the ability of SynCo to generate nodes in large scale, up to 2.1 million nodes.

0.13

Efficient Influence Minimization via Source-Integrated Sampling

cs.SI cs.DS ·2026-11-11 ·Jingbang Chen, Junyao Wang
theory similarity 0.61
Abstract · 14 pages

Influence minimization by node blocking is a fundamental problem in graph data management that seeks a small set of vertices whose removal minimizes the expected spread from a fixed source set. It supports decisions about where to intervene in large interaction networks to control harmful propagation, such as the spread of rumors and infectious diseases. Under the Independent Cascade (IC) model, selecting blockers requires comparing a large number of candidate sets, and estimating their effects on propagation can be costly. We propose SIG (Source-Integrated Greedy), a sampling framework for efficiently finding high-quality approximate solutions. Our key idea is to group the possible sets of neighbors directly activated by the sources according to their effects on blocker selection. SIG represents these groups in a compact weighted tree and computes their probabilities directly, allowing each sample to account for all source outcomes without enumerating them. We prove that SIG produces unbiased estimates of the lower-bound objective without increasing variance for fixed blocking plans, and establish a high-probability quality guarantee through independent validation. Extensive experiments on real-world networks show that SIG has the lowest mean total running time in all main comparisons, with speedups of up to 583x over the fastest baseline. SIG produces solutions competitive with those of prior methods and achieves the highest influence reduction in multiple settings, including on many of the largest networks, where several baselines exceed the runtime limit. Additional experiments show that SIG maintains consistently low running times as graph size and the blocking budget increase, while delivering stronger blocking solutions at larger budgets.

0.18

Scaling Graph Similarity Learning with Graph Neural Networks

cs.LG cs.AI ·2026-11-06 ·Ahmet Tüzen, Helge Langseth, Kjetil Nørvåg
benchmark similarity 0.61
Abstract

Graph similarity computation is an important task in graph mining with many real-world applications, such as chemical compound analysis, program dependence comparison, and social network analysis. The problem is computationally challenging: Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), which quantify the distance between graphs and identify their largest shared subgraph, respectively, are NP-hard to compute exactly. To address these computational challenges, Graph Neural Networks (GNNs) have been applied to this problem. However, existing GNN-based approaches have primarily focused on small-scale graph datasets, while scalability to larger scales remains underexplored. In this work, we propose FiLSim, a scalable GNN-based framework, and investigate whether a simplified GNN pipeline can maintain competitive performance on standard benchmarks while scaling to large graphs. We additionally propose a sequential graph-editing strategy to construct large-scale graph datasets with reliable GED labels to evaluate scalability. The proposed framework is evaluated on four benchmark datasets and four newly created large-scale datasets, demonstrating its effectiveness and scalability. FiLSim remains accurate on graphs with more than 150{,}000 nodes, where the baseline methods run out of memory or fail to learn, and scores all test pairs within seconds on a single GPU.

0.25

Structural Entropy-Driven Graph Diffusion Generation for One-Shot Federated Graph Learning

cs.LG ·2026-09-06 ·Shutong Zheng, Lele Fu, Sheng Huang, Wei Yang Bryan Lim, Chuan Chen
similarity 0.59
Abstract · 11 pages, 5 figures

One-shot federated graph learning (FGL) requires the server to estimate client contributions from highly compressed information, yet conventional volume-based weighting captures the amount of client data while overlooking how its connectivity is organized. In this paper, we propose SPIRE, a Structural Entropy-Driven Graph Diffusion Generation method that introduces topology-aware client differentiation into one-shot FGL. Specifically, we employ first-order degree-distribution structural entropy as a compact descriptor of degree-mass dispersion and use it to derive structural client weights, providing an inductive bias that accounts for differences in graph topology beyond data volume. On the generation side, a graph diffusion model on the server synthesizes pseudographs conditioned on the weighted client prototypes, capturing both semantic and structural information without requiring additional client-side training. The generated pseudographs are then assembled via disjoint union fusion to train a global graph neural network. Extensive experiments on seven real-world graph datasets demonstrate that SPIRE consistently outperforms conventional and one-shot FGL methods, with particularly strong gains under highly heterogeneous (non-IID) and graph-perturbed settings.

0.18

Diffusion-Induced Spatial Attention Overlapping Community Detection

cs.SI cs.LG ·2026-09-22 ·Kosti Koistinen, Vesa Kuikka, Joni Herttuainen, Matthew Hendren, Brian Holt +1 more
benchmark similarity 0.59
Abstract

Detection of overlapping communities is essential for modelling networks in which nodes participate simultaneously in multiple structural or functional groups. Existing graph neural network approaches commonly rely on local message passing, which can obscure community boundaries through smoothing and limit the representation of structurally relevant long-range dependencies. We introduce Diffusion-Induced Spatial Attention Community Detection (DISCO), a deep-learning framework that combines a structural prior derived from influence spreading dynamics, sparse multi-head attention, and non-negative community-affiliation learning. The prior identifies candidate interactions beyond immediate graph neighbours and biases attention according to their structural proximity, while a Bernoulli-Poisson edge-reconstruction objective enables overlapping community inference from node attributes and structural profiles, or both. Benchmark experiments show that DISCO performs competitively against established graph convolutional and graph attention approaches across different input configurations. To demonstrate its practical applicability, we present a proof-of-concept cybersecurity use case in which changes between community assignments inferred from consecutive communication-network snapshots provide an interpretable anomaly signal. Temporal community similarity identifies structural deviations, while node-level contributions help locate the devices associated with them. DISCO therefore provides both a flexible method for overlapping community detection and a foundation for analysing structural change in dynamic networks.

0.07