Grothendieck Inequality

Scribed by Neng Huang

In which we use the SDP relaxation of the infinity-to-one norm and Grothendieck inequality to give an approximation reconstruction of the stochastic block model.

1. A Brief Review of the Model

First, let’s briefly review the model. We have a random graph ${G = (V, E)}$ with an unknown partition of the vertices into two equal parts ${V_1}$ and ${V_2}$ . Edges across the partition are generated independently with probability ${q}$ , and edges inside the partition are generated independently with probability ${p}$ . To abbreviate the notation, we let ${a = pn/2}$ , which is the average internal degree, and ${b = qn/2}$ , which is the average external degree. Intuitively, the closer are ${a}$ and ${b}$ , the more difficult it is to reconstruct the partition. We assume ${a > b}$ , although there are also similar results in the complementary model where ${b}$ is larger than ${a}$ . We also assume ${b > 1}$ so that the graph is not almost empty.

We will prove the following two results, the first of which will be proved using Grothendieck inequality.

For every ${\epsilon > 0}$ , there exists a constant ${c_\epsilon}$ such that if ${a - b > c_\epsilon\sqrt{a+b}}$ , then we can reconstruct the partition up to less than ${\epsilon n}$ misclassified vertices.
There exists a constant ${c}$ such that if ${a-b \geq c \sqrt{\log n}\sqrt{a+b}}$ , then we can do exact reconstruct.

We note that the first result is essentially tight in the sense that for every ${\epsilon > 0}$ , there also exists a constant ${c_\epsilon'}$ such that if ${a-b < c_\epsilon'\sqrt{a+b}}$ , then it will be impossible to reconstruct the partition even if an ${\epsilon}$ fraction of misclassified vertices is allowed. Also, the constant ${c_\epsilon}$ will go to infinity as ${\epsilon}$ goes to 0, so if we want more and more accuracy, ${a-b}$ needs to be a bigger and bigger constant times ${\sqrt{a+b}}$ . When the constant becomes ${O(\sqrt{\log n})}$ , we will get an exact reconstruction as stated in the second result.