# Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 45 references that are in the map.
- First posted on arXiv 5 Jan 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property](https://mlsanity.com/paper/1904.07174/) (2019)
- [Parallel Tempering for the planted clique problem](https://mlsanity.com/paper/1802.05903/) (2018)
- [Optimal link prediction with matrix logistic regression](https://mlsanity.com/paper/1803.07054/) (2018)
- [Topological based classification using graph convolutional networks](https://mlsanity.com/paper/1911.06892/) (2019)

## Built on by (most cited first, 1 of 1)

- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)

## Abstract (arXiv)

Multiple methods of finding the vertices belonging to a planted dense subgraph in a random dense G(n, p) graph have been proposed, with an emphasis on planted cliques. Such methods can identify the planted subgraph in polynomial time, but are all limited to several subgraph structures. Here, we present PYGON, a graph neural network-based algorithm, which is insensitive to the structure of the planted subgraph. This is the first algorithm that uses advanced learning tools for recovering dense subgraphs. We show that PYGON can recover cliques of sizes Thetaleft(√nright), where n is the size of the background graph, comparable with the state of the art. We also show that the same algorithm can recover multiple other planted subgraphs of size Thetaleft(√nright), in both directed and undirected graphs. We suggest a conjecture that no polynomial time PAC-learning algorithm can detect planted dense subgraphs with size smaller than Oleft(√nright), even if in principle one could find dense subgraphs of logarithmic size.