# A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 78 references that are in the map.
- First posted on arXiv 20 Jun 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [A Review of Graph Neural Networks and Their Applications in Power Systems](https://mlsanity.com/paper/2101.10025/) (2021)
- [Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency](https://mlsanity.com/paper/1404.0900/) (2014)
- [Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling](https://mlsanity.com/paper/1907.11625/) (2019)
- [Contingency-Aware Influence Maximization: A Reinforcement Learning Approach](https://mlsanity.com/paper/2106.07039/) (2021)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs](https://mlsanity.com/paper/1904.05300/) (2019)
- [Probability Learning based Tabu Search for the Budgeted Maximum Coverage Problem](https://mlsanity.com/paper/2007.05971/) (2020)
- [Effective Variable Depth Local Search for the Budgeted Maximum Coverage Problem](https://mlsanity.com/paper/2202.03093/) (2022)
- [Voting-based Opinion Maximization](https://mlsanity.com/paper/2209.06756/) (2022)
- [Optimal Preprocessing for Answering On-Line Product Queries](https://mlsanity.com/paper/2406.06321/) (2024)

## Abstract (arXiv)

Recent years have witnessed a growing trend toward employing deep reinforcement learning (Deep-RL) to derive heuristics for combinatorial optimization (CO) problems on graphs. Maximum Coverage Problem (MCP) and its probabilistic variant on social networks, Influence Maximization (IM), have been particularly prominent in this line of research. In this paper, we present a comprehensive benchmark study that thoroughly investigates the effectiveness and efficiency of five recent Deep-RL methods for MCP and IM. These methods were published in top data science venues, namely S2V-DQN, Geometric-QN, GCOMB, RL4IM, and LeNSE. Our findings reveal that, across various scenarios, the Lazy Greedy algorithm consistently outperforms all Deep-RL methods for MCP. In the case of IM, theoretically sound algorithms like IMM and OPIM demonstrate superior performance compared to Deep-RL methods in most scenarios. Notably, we observe an abnormal phenomenon in IM problem where Deep-RL methods slightly outperform IMM and OPIM when the influence spread nearly does not increase as the budget increases. Furthermore, our experimental results highlight common issues when applying Deep-RL methods to MCP and IM in practical settings. Finally, we discuss potential avenues for improving Deep-RL methods. Our benchmark study sheds light on potential challenges in current deep reinforcement learning research for solving combinatorial optimization problems.