Convex relaxations and the planted clique problem

Suppose G is a graph on N vertices, and H is a set of vertices on which someone has secretly “planted” a complete graph, or a graph whose edge-density is significantly greater than that of G. Can we efficiently and reliably find H, given G? This is called the “planted clique” or “community detection” problem — we have heard about various versions of this problem from Rob N., Karl R., and many others in various SILO talks.

I will talk about a convex relaxation of this problem, and explain why it doesn’t seem to do much better than standard methods in the usual case, where G is thought of as an Erdos-Renyi graph. (More or less: you can find H if |H| is bigger than the square root of N, otherwise, forget it.) However, the standard methods for planted clique have trouble when G is drawn from a more general, less homogeneous, more realistic random graph model (of course I have in mind the “graphons” I talked about in my last SILO talk) and it seems likely to me that the convex relaxation will be more robust to this change, and will still find cliques of square-root size.

A central theme will be the following theorem in graph theory: whenever you come up with an idea about graph theory, Lovasz has already thought of it.