论文标题
可以使用基于图的机器学习来恢复密集的随机图中的密集密集图
Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
论文作者
论文摘要
已经提出了多种方法，用于在随机致密的$ g（n，p）$图中找到属于植物的密集子图的顶点，重点是种植的集团。这种方法可以在多项式时间内识别种植的子图，但都限于几个子图结构。在这里，我们提出了一种基于图神经网络的算法Pygon，对种植的子图的结构不敏感。这是第一种使用高级学习工具来恢复密集子图的算法。我们表明，pygon可以恢复尺寸$θ\ left（\ sqrt {n} \ right）$的集团，其中$ n $是背景图的大小，可与先进的状态相媲美。我们还表明，在指示图和无向图中，相同的算法可以恢复大小$θ\ left的多个其他种植的子图（\ sqrt {n} \ right）$。我们建议一个猜想，即即使在原则上可以找到密集的对数大小的密集范围，也没有多项式时间学习算法可以检测到小于$ o \ left（\ sqrt {n} \ right）$的尺寸小于$ o \左的密集子图。
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 $Θ\left(\sqrt{n}\right)$, 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 $Θ\left(\sqrt{n}\right)$, 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 $O\left(\sqrt{n}\right)$, even if in principle one could find dense subgraphs of logarithmic size.
