Planted clique detection below the noise floor using low-rank sparse PCA

Alexis B. Cook; Benjamin A. Miller

ICASSP 2015accepted0 citations

Planted clique detection below the noise floor using low-rank sparse PCA

Abstract

Detection of clusters and communities in graphs is useful in a wide range of applications. In this paper we investigate the problem of detecting a clique embedded in a random graph. Recent results have demonstrated a sharp detectability threshold for a simple algorithm based on principal component analysis (PCA). Sparse PCA of the graph's modularity matrix can successfully discover clique locations where PCA-based detection methods fail. In this paper, we demonstrate that applying sparse PCA to low-rank approximations of the modularity matrix is a viable solution to the planted clique problem that enables detection of small planted cliques in graphs where running the standard semidefinite program for sparse PCA is not possible.

BibTeX

@inproceedings{icassp2015_plantedcliquedet,
  title = {Planted clique detection below the noise floor using low-rank sparse PCA},
  author = {Alexis B. Cook and Benjamin A. Miller},
  booktitle = {ICASSP 2015},
  year = {2015}
}