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 with an unknown partition of the vertices into two equal parts
and
. Edges across the partition are generated independently with probability
, and edges inside the partition are generated independently with probability
. To abbreviate the notation, we let
, which is the average internal degree, and
, which is the average external degree. Intuitively, the closer are
and
, the more difficult it is to reconstruct the partition. We assume
, although there are also similar results in the complementary model where
is larger than
. We also assume
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
, there exists a constant
such that if
, then we can reconstruct the partition up to less than
misclassified vertices.
- There exists a constant
such that if
, then we can do exact reconstruct.
We note that the first result is essentially tight in the sense that for every , there also exists a constant
such that if
, then it will be impossible to reconstruct the partition even if an
fraction of misclassified vertices is allowed. Also, the constant
will go to infinity as
goes to 0, so if we want more and more accuracy,
needs to be a bigger and bigger constant times
. When the constant becomes
, we will get an exact reconstruction as stated in the second result.