Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation
Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation
复制标题
DOI：
10.1007/s10957-015-0777-x
复制
发表时间：
2015-11-01
影响因子：
1.9
通讯作者：
Ames, Brendan P. W.
中科院分区：
文献类型：
--
作者：
Ames, Brendan P. W.
我们考虑在给定图中识别密度最大的k节点子图的问题。我们把这个问题写成一个秩约束的基数最小化的例子，然后使用核范数和一个范数进行松弛。虽然最初的组合问题是np困难的，但我们证明了对于某些程序输入，最密集的k子图可以从我们的凸松弛解中恢复。特别是，我们在输入图中包含单个种植的团和以损坏邻接关系形式存在的噪声的情况下建立了精确恢复。我们还建立了识别二部图中固定大小的最密集子图的类似恢复保证，并包括随机生成图的数值模拟结果，以证明我们的算法的有效性。
We consider the problem of identifying the densest k-node subgraph in a given graph. We write this problem as an instance of rank-constrained cardinality minimization and then relax using the nuclear norm and one norm. Although the original combinatorial problem is NP-hard, we show that the densest k-subgraph can be recovered from the solution of our convex relaxation for certain program inputs. In particular, we establish exact recovery in the case that the input graph contains a single planted clique plus noise in the form of corrupted adjacency relationships. We also establish analogous recovery guarantees for identifying the densest subgraph of fixed size in a bipartite graph, and include results of numerical simulations for randomly generated graphs to demonstrate the efficacy of our algorithm.