Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning. (arXiv:2201.01825v1 [cs.LG])

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 …

arxiv graph graph-based graphs learning machine machine learning random