Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

DOI10.1007/S10957-015-0777-XzbMATH Open1327.90189arXiv1305.4891OpenAlexW1572312821MaRDI QIDQ896191FDOQ896191

Brendan P. W. Ames

Publication date: 14 December 2015

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1305.4891

zbMATH Keywords

densest subgraphnuclear norm minimizationplanted clique\(l_1\) norm minimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Robust principal component analysis?
• Fast alternating linearization methods for minimizing the sum of two convex functions
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Hiding cliques for cryptographic security
• Convex optimization for the planted \(k\)-disjoint-clique problem
• Rank-Sparsity Incoherence for Matrix Decomposition
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Relations between average case complexity and approximation complexity
• Optimal detection of sparse principal components in high dimension
• Guaranteed clustering and biclustering via semidefinite programming
• Reducibility among Combinatorial Problems
• Finding Hidden Cliques in Linear Time with High Probability
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Compressed sensing
• Nuclear norm minimization for the planted clique and biclique problems
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Near-optimal sparse fourier representations via sampling
• The dense \(k\)-subgraph problem
• Large Cliques Elude the Metropolis Process
• Finding Approximately Rank-One Submatrices with the Nuclear Norm and $\ell_1$-Norm
• The maximum edge biclique problem is NP-complete
• Expected complexity of graph partitioning problems
• How Hard Is It to Approximate the Best Nash Equilibrium?
• The highest dimensional stochastic blockmodel with a regularized estimator
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Finding and certifying a large hidden clique in a semirandom graph
• Algorithms and Computation

Cited In (7)

• Recovering nonuniform planted partitions via iterated projection
• Exact Clustering of Weighted Graphs via Semidefinite Programming
• Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics
• On solving the densestk-subgraph problem on large graphs
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Convex optimization for the densest subgraph and densest submatrix problems
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

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)