Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
From MaRDI portal
(Redirected from Publication:896191)
Abstract: 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 and 11 norms. 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 consider two constructions for this noise. In the first, noise is introduced by an adversary deterministically deleting edges within the planted clique and placing diversionary edges. In the second, these edge corruptions are performed at random. Analogous recovery guarantees for identifying the densest subgraph of fixed size in a bipartite graph are also established, and results of numerical simulations for randomly generated graphs are included to demonstrate the efficacy of our algorithm.
Recommendations
- Convex optimization for the densest subgraph and densest submatrix problems
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation
- Nuclear norm minimization for the planted clique and biclique problems
- Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
Cites work
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 5485485 (Why is no real title available?)
- scientific article; zbMATH DE number 1303602 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Algorithms and Computation
- Clustering partially observed graphs via convex optimization
- Compressed sensing
- Convex optimization for the planted \(k\)-disjoint-clique problem
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Expected complexity of graph partitioning problems
- Fast alternating linearization methods for minimizing the sum of two convex functions
- Finding and certifying a large hidden clique in a semirandom graph
- Finding approximately rank-one submatrices with the nuclear norm and \(\ell_1\)-norm
- Finding hidden cliques in linear time
- Finding hidden cliques in linear time with high probability
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- Guaranteed clustering and biclustering via semidefinite programming
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Hiding cliques for cryptographic security
- How Hard Is It to Approximate the Best Nash Equilibrium?
- Large Cliques Elude the Metropolis Process
- Near-optimal sparse fourier representations via sampling
- Nuclear norm minimization for the planted clique and biclique problems
- Optimal detection of sparse principal components in high dimension
- Rank-Sparsity Incoherence for Matrix Decomposition
- Reducibility among combinatorial problems
- Relations between average case complexity and approximation complexity
- Robust principal component analysis?
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- The dense \(k\)-subgraph problem
- The highest dimensional stochastic blockmodel with a regularized estimator
- The maximum edge biclique problem is NP-complete
Cited in
(13)- Convex optimization for the planted \(k\)-disjoint-clique problem
- Recovering nonuniform planted partitions via iterated projection
- Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- Lovász theta function, SVMs and finding dense subgraphs
- Convex optimization for the densest subgraph and densest submatrix problems
- Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation
- On solving the densest \(k\)-subgraph problem on large graphs
- Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- Nuclear norm minimization for the planted clique and biclique problems
- Exact clustering of weighted graphs via semidefinite programming
- Guaranteed clustering and biclustering via semidefinite programming
This page was built for publication: Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896191)
