502. Finding a planted clique hidden among many dense subgraphs
Invited abstract in session WC-7: Numerical Methods and Applications II, stream Numerical Methods and Applications.
Wednesday, 14:00-16:00Room: B100/5015
Authors (first author is the speaker)
| 1. | Brendan Ames
|
| Mathematical Sciences, Operational Research, University of Southampton |
Abstract
Much recent research has focused on sufficient conditions for recovery of planted cliques or, more generally, dense submatrices, within random graphs. Although the maximum clique problem is NP-Hard, these results suggest that we can efficiently identify the maximum clique under certain assumptions on the input graph. Unfortunately, the overwhelming majority of this research focuses on the case where the input graph consists of a single large clique hidden by diversionary nodes and edges. On the other hand, many recent analyses have established recovery guarantees for stochastic block models via various graph clustering heuristics.
We build upon these earlier results and establish sufficient conditions for recovery of a single planted clique from the optimal solution of a certain convex optimization problem within a random graph containing many planted cliques obscured by diversionary edges and nodes. We also discuss strategies for solution of this optimization problem and extensions of these recovery guarantees to non-convex quadratic programming relaxations of the maximum clique and densest submatrix problems.
Keywords
- Applications of continuous optimization
- Linear and nonlinear optimization
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers