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
Quick verdict
Unsupervised GNN for MDS with a novel loss; results are honest but Dynamic-Greedy beats it on speed and error at n≤77, so large-scale claims outrun evidence.
Summary
The paper proposes an unsupervised graph neural network framework for the Minimum Dominating Set (MDS) problem, motivated by influence-maximization applications in social networks. A two-layer GCN outputs per-node probabilities trained with a three-term loss: a size penalty, a coverage term using an independence approximation of domination probability computed in log-space, and an 'equalizer' term pushing probabilities toward 0/1. At inference, four decoding strategies (3-Phase, Prune-Greedy, Threshold-Greedy, Neighbor-Greedy) run in ensemble and the smallest resulting valid dominating set is returned. Training uses 12,000 synthetic graphs of 10–40 nodes (trees, ER, dense ER, near-complete); exact CP-SAT solutions are used only for evaluation. On seven real-world benchmarks (16–77 nodes), the method averages 7% relative error versus 0% for Simulated Annealing and the supervised Kothapalli approach, and 6% for Dynamic-Greedy, which is also faster on every instance tested — the paper states this candidly. Claimed advantages are inference speed (under 50 ms; up to 55× faster than SA, 2–14× faster than Kothapalli) and label-free training, with an ablation showing the EGN-MDS baseline without equalizer/ensemble reaches 170% error. Key limitations: training and evaluation are confined to tiny graphs, so the 'large-scale social network analysis' claims remain untested; no seed variance or statistical uncertainty is reported; code is only promised upon publication.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- A three-term unsupervised loss (size, log-space coverage under an independence assumption, equalizer) trains a GCN for MDS without any ground-truth solutions.
- Running four decoding strategies in ensemble and keeping the smallest valid set yields 7% average relative error on seven real social-network benchmarks.
- Inference takes under 50 ms per benchmark graph — up to 55× faster than Simulated Annealing and 2–14× faster than the supervised Kothapalli method.
- The equalizer term plus ensemble decoding account for the entire gap from 170% (EGN-MDS ablation) to 7% average relative error.
- The heuristic generalizes from synthetic training graphs to unseen real-world distributions without fine-tuning.
Strengths
Candid self-assessment rare in this literature
Section 5.3 and the Discussion state outright that Dynamic-Greedy achieves lower average error (6% vs 7%) and is faster on every benchmark instance including the two largest (|V|=70, 77); the S2V-DQN reimplementation failure and the GCON comparison gap are disclosed rather than hidden (Section 5.1.3).
Clean contribution-isolating ablation
EGN-MDS (Section 5.1.3, Table 2) shares the unsupervised paradigm and GCN but omits the equalizer and ensemble, reaching 170% average relative error vs 7% for the full method — a direct test of the two claimed additions.
Reimplementation-grade method specification
Internally consistent results tables
Weaknesses
Evaluation scale contradicts headline framing
Pareto-dominated by a simple baseline on the entire test suite
No uncertainty quantification anywhere
Novelty framing overstated
Counterintuitive loss weighting unexplored
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper proposes an unsupervised graph neural network (GNN) framework for the Minimum Dominating Set (MDS) problem, positioned as a tool for influence maximization in social networks. Central claims: (1) a three-term probabilistic loss (size, coverage, equalizer) removes the need for ground-truth solutions; (2) an ensemble of four decoding strategies turns node probabilities into valid, near-optimal sets; (3) inference is fast — under 50 ms on all benchmarks, up to 55× faster than metaheuristics and 2–14× faster than the supervised baseline; (4) the model generalizes to unseen real-world networks.
The scope reality is narrower than the framing. All evaluation is on graphs of 16–77 nodes; training uses 10–40-node synthetic graphs. Influence maximization proper (Kempe-style diffusion) is never optimized — MDS is a proxy, and the PIDS variant discussed at length (Sections 1, 4.1.1) is deferred to future work. The abstract's large-scale ambition is aspiration, not evidence; the Discussion concedes very large graphs are untested.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What problem does this paper solve?
It trains a graph neural network, without any labeled solutions, to find small near-minimum dominating sets — subsets of nodes that cover every node of a graph within one hop. Minimum dominating set is NP-hard and is used as a proxy for choosing seed individuals in viral marketing or information-spread campaigns on social networks.
How does this GNN method compare to a simple greedy algorithm?
On the seven real networks tested (16–77 nodes), the GNN averages 7% relative error while the classical Dynamic-Greedy heuristic achieves 6% and runs faster on every single instance. The paper states this openly; its argued advantages are label-free training and single-pass sub-50ms inference, which are only advantages against the slower metaheuristic and supervised baselines at these scales.
Is code or data available for this paper?
Not at review time. The declarations state code will be made available upon publication and data upon reasonable request. The method is, however, specified in enough detail (architecture, loss weights, training schedule, decoder logic, synthetic graph mixture) that a reimplementation with PyTorch Geometric, NetworkX benchmarks, and OR-Tools CP-SAT is feasible.
What is the equalizer loss term in this paper?
It is a penalty p(1−p) summed over nodes, which is largest when a predicted probability is 0.5 and zero at 0 or 1, pushing the model toward decisive binary predictions that the downstream decoding heuristics can resolve. In the paper's ablation, removing it (the EGN-MDS baseline, along with ensemble decoding) causes average relative error to jump from 7% to 170%.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Mathematical notation is flattened by PDF extraction (loss/product formulas in Section 3.2 appear as garbled glyph runs); formulas were reconstructed from surrounding text, so symbol-level details carry mild reading uncertainty, though all numeric values (α, β, γ, ε, equations' semantics) are unambiguous in the prose.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.