Applied Science and Innovative Research 

ISSN 2474-4972 (Print) ISSN 2474-4980 (Online) 

Vol. 8, No. 1, 2024 

www.scholink.org/ojs/index.php/asir 

63 
 

Original Paper 

Learning Guarantee of SDP Relaxation on Directed Stochastic 

Block Models 

Yanlang Chen1 

1 Shenzhen College of International Education, Shenzhen, Guangdong, 518040, China 

 

Received: December 18, 2023    Accepted: January 27, 2024    Online Published: February 2, 2024 

doi:10.22158/asir.v8n1p63          URL: http://doi.org/10.22158/asir.v8n1p63 

 

Abstract 

Community detection in networks has been a focal point in various scientific domains, but the study of 

directed networks remains relatively under-explored despite their prevalence and importance in 

capturing real-world systems. This work addresses this research gap by focusing on Directed 

Stochastic Block Models (DSBMs), a natural extension of traditional Stochastic Block Models (SBMs) 

to directed graphs. The inherent complexity of directionality in DSBMs makes them challenging to 

analyze, requiring new mathematical frameworks and computational approaches. We introduce an 

augmented matrix to encapsulate the directional relationships within these networks, providing a 

nuanced perspective for further analysis. In this work, we prove the information-theoretical threshold 

for exact recovery in the DSBMs and propose an SDP relaxation that can achieve this threshold, 

thereby contributing to the theoretical understanding of community detection in the realm of directed 

graphs. 

Keywords 

Directed Stochastic Block Models, Semi-Definite Programming (SDP) Relaxation, clustering, random 

graph, unsupervised learning, community detection, directed graphs 

 

1. Introduction 

Community detection and clustering are pivotal challenges in an array of disciplines, ranging from 

machine learning and data science to the study of complex networks (Girvan & Newman, 2002; 

Newman, 2003). One of the most striking features of any network is its unique structure, which 

becomes evident through the patterns of interaction among its vertices. For instance, certain subsets of 

vertices in a vast network are tightly interlinked, while their connections to vertices outside this cluster 

are notably sparse. While substantial research has focused on undirected networks - such as 

geographical maps, friendship circles, and familial connections - there is a compelling yet 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

64 
Published by SCHOLINK INC. 

underexplored frontier in the realm of directed networks. Directed networks, evident in phenomena like 

social media interactions, web page hyperlinks, and aviation routes, more closely mimic the intricacies 

of real-world systems. Their inherent directionality not only makes them more relevant for practical 

applications but also significantly more challenging to analyze. This very novelty and complexity of 

directed networks serve as the driving force behind this thesis. 

Stochastic Block Models (SBMs) (Emmanuel, Afonso, & Georgina, 2014) have traditionally been 

employed to examine random block structures, originally formulated to scrutinize social networks. This 

model serves as a powerful benchmark for assessing the performance of clustering algorithms. 

However, its main limitation lies in its oversimplification of real-world networks, particularly due to its 

strong homogeneity and lack of community structure. Moreover, the burgeoning research in this area 

has disproportionately focused on undirected SBMs (Andrea, Santo, & Filippo, 2008; Santo, 2010), 

thus leaving a crucial gap in our understanding of Directed Stochastic Block Models (DSBMs). 

The challenge in DSBMs is not merely a replication of its undirected counterparts; it is profoundly 

exacerbated by the added complexity of directionality. In light of this, we leverage an augmented 

matrix to encapsulate these directional relationships, providing a nuanced mathematical framework to 

navigate this intricate landscape. 

DSBMs also possess desirable consistency properties similar to undirected SBMs, but obtaining exact 

parameter estimates in both is generally an NP-hard problem. Inspired by semi-definite programming 

(SDP) relaxation techniques (Afonso, 2015), our work aims to bypass this computational bottleneck. 

We offer a pioneering semi-definite relaxation approach to discern clustering thresholds in DSBMs, 

thereby overcoming the inherent NP-hardness. 

In this work, we prove the information-theoretical threshold for exact recovery in the Directed 

Stochastic Block Models and propose an SDP relaxation that can achieve the threshold, which fills the 

gap of the theoretical understanding of community detection in the context of directed graphs. 

1.1 Notations 

Let 𝑨 ∈ ℂ𝑛×𝑚 be a complex matrix and denote its (𝑖, 𝑗)-entry by 𝐴𝑖𝑗. We denote its transpose and 

conjugate transpose as 𝑨⊤  and 𝑨𝐻  respectively. The ℓ2 -norm of a vector 𝒗  is denoted by 

∥ 𝒗 ∥= √𝒗𝐻𝒗 = √∑𝑗=1
𝑛  |𝑣𝑗|

2
 and its ℓ∞ norm is denoted by ∥ 𝒗 ∥∞= max1≤𝑘≤𝑛  |𝑣𝑘|, where 𝑣𝑘 is 

𝒗's 𝑘-th entry. The inner product between two complex vectors 𝒖 and 𝒗 is defined as ⟨𝒖, 𝒗⟩ = 𝒖𝐻𝒗. 

For two vectors 𝒖 and 𝒗, we denote 𝒖 ∝ 𝒗 if they are parallel. We denote the operator 2-norm of 𝑨 

as ∥ 𝑨 ∥ which is the largest singular value of 𝑨. We denote the all-one vector in ℝ𝑛 as 𝟏𝑛 and the 

all-one matrix in ℝ𝑛×𝑛 as 𝑱𝑛. 

For 𝑨 ∈ ℝ𝑛×𝑛, if 𝑨 is symmetric and all its eigenvalues are non-negative, we say 𝑨 is positive 

semidefinite, denoted by 𝑨 ≽ 0. 

 

 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

65 
Published by SCHOLINK INC. 

2. Preliminaries 

In this section, we will introduce the problem settings and the core definitions for the paper. 

2.1 Directed Stochastic Block Models 

The Directed Stochastic Block Models (or DSBM in short) is a generative model for modeling the 

community structures in directed networks, which is a benchmark for comparing different community 

detection methods. First, we define the DSBM as follows. Given an even integer 𝑛 ≥ 2, and 

1 ≥ 𝑝 > 𝑞 ≥ 0, we say that a directed random graph 𝐺 is drawn from the Directed Stochastic Block 

Model with two communities (denoted as DSBM⁡(𝑛, 𝑝, 𝑞)) with ground-truth 𝒈, if 𝐺 has 𝑛 nodes, 

divided into two clusters of 𝑛/2 nodes each, and for each pair of vertices (𝑖, 𝑗), (𝑖, 𝑗) is an edge of 𝐺 

with probability 𝑝 if 𝑖 and 𝑗 are in the same cluster and with probability 𝑞 otherwise. The 𝑖-th 

entry of 𝒈 is ±1 indicating the cluster to which the 𝑖-th node belongs. In particular, let 𝑨 be the 

adjacency matrix of 𝐺. Each entry of 𝑨 is given by 

ℙ(𝑨𝑖𝑗 = 1) = {
𝑝  if 𝑖 and 𝑗 are in the same community 

𝑞  otherwise 
⁡1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑛. 

Then the expected adjacency matrix 𝑨∗ = 𝔼𝑨 is given by 

𝑨∗ = 𝔼𝑨 = [
𝑝𝑱𝑛/2×𝑛/2 𝑞𝑱𝑛/2×𝑛/2
𝑞𝑱𝑛/2×𝑛/2 𝑝𝑱𝑛/2×𝑛/2

] 

This model can be seen as the concatenation of two directed Erdős-Rényi random graphs with 

parameter 𝑝 (as two clusters) and the connection probability between these two graphs is 𝑞. To 

theoretically understand community detection in directed networks, we are interested in the 

information-theoretical threshold for exact recovery in DSBM, that is, we want to find a threshold as a 

function of (𝑛, 𝑝, 𝑞), above which exactly recovering the membership of each node is possible with 

probability 1 − 𝑜(1), while impossible otherwise. 

The definition of exact recovery is stated as follows. Let Algo (⋅) be some community detection 

algorithm, and 𝑨 be the adjacency matrix of 𝐺 ∼ DSBM⁡(𝑛, 𝑝, 𝑞) with ground-truth membership 𝒈. 

Then we say Algo⁡(⋅)  exactly recovers the membership if Algo⁡(𝑨) = 𝒙 = 𝒈  where 𝒙  is the 

membership estimated by Algo⁡(⋅). Since it can be verified that connectedness is a sufficient condition 

for exact recovery in DSBM, we will choose the regime 𝑝 = 𝑎log⁡(𝑛)/𝑛, 𝑞 = 𝑏log⁡(𝑛)/𝑛 in the whole 

paper. In this work, we will propose the threshold of exact recovery for DSBM⁡(𝑛, 𝑎, 𝑏) and a 

clustering algorithm that can exactly recover the membership, and then prove the tightness of the 

threshold. 

2.2 Co-clustering: Community Detection in Directed Networks 

Co-clustering was a concept first proposed in 1972, where it clusters entries of a matrix ∈ ℝ𝑛×𝑑. In the 

past, co-clustering has been applied to matrices where the rows and columns represent different meanings, 

and it clusters rows of matrix 𝑀 into 𝑘𝑟 communities, and columns into 𝑘𝑐 communities. For example, 

in a matrix used for text processing, the rows represent documents, and the columns represent words. 

Therefore, each entry in (𝑖, 𝑗) indicates how many time word 𝑗 appears in document 𝑖. 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

66 
Published by SCHOLINK INC. 

However, in this thesis, we apply co-clustering to a matrix where the rows and columns index the same 

set of vertex. Specifically, the 𝑖th row of the matrix represents the connection of the 𝑖th vertex, where 

it shows the outgoing edges for vertex 𝑖. The 𝑖th column of the matrix represents the incoming edges 

of 𝑖th vertex. Therefore, each vertex 𝑖 is included in two communities, one for the row and one for the 

column. It is worth mentioning that due to the directedness of the DSBM, the connectedness of the row 

community and the column community of 𝑖th vertex is not necessarily the same. 

Specifically, we would like to find the Maximum Likelihood Estimation (MLE) to the communities in 

the DSBM. We assume 𝑢 and 𝑣 to be n by 1 matrix, where the first 
𝑛

2
 entries are 1, and others are 

-1. We have 𝑨 as our adjacency matrix, which reflects the realistic connection behavior. Then we have 

the following equation: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡max⁡⁡⁡⁡𝒖⊤𝑨𝒗

 s.t ⁡⁡⁡⁡𝑢𝑖 = ±1,1 ≤ 𝑖 ≤ 𝑛,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡（2.1）

⁡⁡⁡⁡𝑣𝑖 = ±1,1 ≤ 𝑖 ≤ 𝑛.

 

in this multiplication, vertices within the same community would give a positive value, and we try to 

maximize the value for all vertices. However, this still remains a very challenging problem to tackle as 

the conditions remain discrete. Therefore, we need to use semi-definite programming (SDP) algorithm 

to loosen the conditions and find the solution under that condition, and lastly check whether the 

solution would work under the initial condition. The detailed process will be further explained in the 

following section. 

2.3 SDP Relaxation for Co-clustering 

The programming (2.1) is indeed finding the maximum likelihood estimation to the membership of the 

nodes, but it is challenging due to NP-hardness. We can simplify the algorithm (2.1) into: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡max Tr⁡(𝒖⊤𝑨𝒗)

                                                                     s.t 𝑢𝑖 = ±1,1 ≤ 𝑖 ≤ 𝑛,

𝑣𝑖 = ±1,1 ≤ 𝑖 ≤ 𝑛.

                    （2.2） 

However, finding the row membership vector 𝒖  and column membership vector 𝒗  from this 

programming is NP-hard due to the following reasons: (1) 𝑨 is asymmetric, so there are limited linear 

algebra algorithms that can be used; (2) the problem is nonconvex; (3) there are limited prior 

knowledge about this model and there are no constraints in the model in (2.2). In order to tackle the 

third reason, we know that as defined, 𝒖 and 𝒗 are perpendicular to 𝟏 matrix, so their dot product 

would equal 0. Therefore, we can penalize algorithm (2.2) with 𝑢𝑇𝟏𝑛 and 𝑣𝑇𝟏𝑛 to the following 

function: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡max Tr⁡(𝒖⊤𝑨𝒗) − 𝜆(⟨𝒖, 𝟏𝑛/√𝑛⟩ + ⟨𝒗, 𝟏𝑛/√𝑛⟩)

                                           s.t 𝑢𝑖 = ±1,1 ≤ 𝑖 ≤ 𝑛,

𝑣𝑖 = ±1,1 ≤ 𝑖 ≤ 𝑛.

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡（2.3） 

Another key characteristic of DSBM is its directness, and in order to deal with the directness of 𝐺, we 

need to consider the symmetric augmented matrix defined below to represent the direction: 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

67 
Published by SCHOLINK INC. 

�̃� = [
𝟎𝑛×𝑛 𝑨⊤

𝑨 𝟎𝑛×𝑛
]. 

Given the singular value decomposition (SVD) of 𝑨 being 

𝑨 = 𝑼𝚺𝑽⊤, 

then the eigen-decomposition of �̃� can be formulated as 

�̃� =
1

√2
[
𝑽 𝑽
𝑼 −𝑼

] [
𝚺 𝟎𝑛×𝑛

𝟎𝑛×𝑛 −𝚺
]
1

√2
[𝑽

⊤ 𝑼⊤

𝑽⊤ −𝑼⊤]. 

It is worth noting that conditions for algorithm (2.3) is discrete, where the algorithm is unsolvable in 

polynomial time. Hence, we need to loosen the constraints using SDP, converting them into 

semi-definite constraints that would be solvable in polynomial time. Using the wellknown 

Goemans-Williams relaxation, we can formulate semi-definite programming to solve the NP-hardness: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡max⁡⁡⁡⁡⟨�̃�, 𝑿⟩ − 𝜆⟨𝑱2𝑛, 𝑿⟩
 s.t. ⁡𝑋𝑖𝑖 = 1,1 ≤ 𝑖 ≤ 2𝑛⁡⁡⁡⁡⁡⁡
⁡⁡⁡𝑿 ≽ 0
⁡𝜆 > 0

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡（2.4） 

(2.4) is a convex relaxation of (2.3). In order to recover the communities in the graph, we intend to 

maximize the difference between the in-community degree and the cross-community degree in rows 

and columns respectively. However, we don't want 𝒖 and 𝒗 to be too close to all-one vector or 

all-negative one vector. So we will take 𝜆 =
1

2
, and (2.4) becomes: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡max Tr⁡((2�̃� − 𝑱2𝑛)𝑿)

                                                     s.t. 𝑋𝑖𝑖 = 1

𝑿 ≽ 0

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡（2.5） 

Note that 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡2�̃� − 𝑱2𝑛 = [
−𝑱𝑛 𝑩𝑇

𝑩 −𝑱𝑛
]

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝐵𝑖𝑗 = {
1⁡ if 𝐴𝑖𝑗 = 1

−1⁡ if 𝐴𝑖𝑗 = 0

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡（2.6） 

 

3. Main Results 

Given the the DSBM⁡(𝑛, 𝑝, 𝑞) defined in Section 2.1, in the regime 𝑝 = 𝑎log⁡(𝑛)/𝑛, 𝑞 = 𝑏log⁡(𝑛)/𝑛, 

we will present the main argument that √𝑎 − √𝑏 = √2 is the information-theoretical threshold for 

exact recovery in the DSBM. To be more specific, the argument will be presented from two 

perspectives, namely the impossibility part and the achievability part. In the impossibility part, we will 

show that when √𝑎 − √𝑏 < √2, even the MLE fails to recover the correct membership of each node. 

In the achievability part, we will show that when √𝑎 − √𝑏 > √2 the SDP relaxation can correctly 

recover the membership of each node with high probability. We only provide a proof sketch in this 

section and the detailed proofs are deferred to Section A and B. 

3.1 Impossibility 

Our goal in this section is to provide a proof sketch of the condition for which the MLE algorithm fails 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

68 
Published by SCHOLINK INC. 

to recover the communities in DSBM, we first introduce the concept of bad vertices which is defined 

with respect to the connectedness of each node. Then using this concept of bad vertices, we will find 

under what condition this bad vertex definitely exists. Therefore, when this condition is met, the MLE 

will fail. 

Theorem 3.1. Let 𝐺 be a graph drawn from DSBM⁡(𝑛, 𝑝, 𝑞), let 𝑝 =
𝑎log⁡(𝑛)

𝑛
 and 𝑞 =

𝑏log⁡(𝑛)

𝑛
, then 

exact recover is impossible if 

√𝑎 − √𝑏 < √2                                     (3.1) 

The following steps are the proof sketch to the above main theorem. 

Definition 3.1. We define the likelihood function of the DSBM as: 

𝐿(𝑥, 𝑦) = ∏  𝑖,𝑗∈[𝑛]2 𝑃𝑖,𝑗
𝐴𝑖,𝑗(1 − 𝑃𝑖𝑗)

1−𝐴𝑖,𝑗
                        (3.2) 

where 𝑨 is the adjacency matrix and 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝑷 = [
𝑝𝑱𝑛/2 𝑞𝑱𝑛/2
𝑞𝑱𝑛/2 𝑝𝑱𝑛/2

]. 

Definition 3.2. We define the degree matrices for DSBM as the following: 

(𝑫𝑅
+)𝑖𝑖: = {

∑  
𝑛/2
𝑗=1  𝐴𝑖𝑗 ⁡𝑖 ∈ [1,

𝑛

2
]

∑  𝑛
𝑗=𝑛/2+1  𝐴𝑖𝑗 ⁡𝑖 ∈ [

𝑛

2
+ 1, 𝑛]

(𝑫𝑅
−)𝑖𝑖: = {

∑  𝑛
𝑗=𝑛/2+1  𝐴𝑖𝑗 ⁡𝑖 ∈ [1,

𝑛

2
]

∑  
𝑛

2
𝑗=1

 𝐴𝑖𝑗 ⁡𝑖 ∈ [
𝑛

2
+ 1, 𝑛]

(𝑫𝐶
+)𝑖𝑖: = {

∑  
𝑛/2
𝑖=1  𝐴𝑖𝑗 ⁡𝑖 ∈ [1,

𝑛

2
]

∑  𝑛
𝑖=

𝑛

2
+1

 𝐴𝑖𝑗 ⁡𝑖 ∈ [𝑛/2 + 1, 𝑛]

(𝑫𝐶
−)𝑖𝑖: = {

∑  𝑛
𝑖=

𝑛

2
+1

 𝐴𝑖𝑗 ⁡𝑖 ∈ [1,
𝑛

2
]

∑  
𝑛

2
𝑖=1

 𝐴𝑖𝑗 ⁡𝑖 ∈ [
𝑛

2
+ 1, 𝑛]

                     (3.3) 

where each entry represents the number of connections that satisfies the condition described above. 

Therefore, for each vertex's connectedness, Then the in-degree matrix and the out-degree matrix for 

DSBM respectively as: 

𝑫+: = [
𝑫𝐶
+ 0

0 𝑫𝑅
+] ⁡𝑫

−: = [
𝑫𝐶
− 0
0 𝑫𝑅

−] 

For each vertex's connectedness, we can use 𝑑(𝑖) to represent the ith vertex's degree. Then we have 

𝑑−(𝑖) to represent the degree with cross-community vertex, 𝑑+(𝑖) to represent the degree with the 

same community. 𝑑𝑅(𝑖) to represent the degree with the row, and 𝑑𝐶(𝑖) to represent the degree with 

the column. 

The concept of bad vertex and bad edges is essential in the proof of the impossibility part. It can be 

verified that the presence of bad edges and bad vertices implies the impossibility of exact recovery and 

the condition √𝑎 − √𝑏 < √2 is the sufficient condition for the existence of bad vertices. 

Definition 3.3. Bad vertices is a type of vertices pair, where the two vertices' community in the pair are 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

69 
Published by SCHOLINK INC. 

swapped, and the MLE of the swapped pair is larger than the MLE of the initial pair. Meaning that after 

the swap, vertices are connected better with their original community. 

Mathematically, we define a pair of bad vertices in rows, in columns, or in rows and columns 

respectively by: 

⁡𝐵𝑅(𝐺):= {(𝑢, 𝑣): 𝑢 ∈ 𝐶1
𝑅 , 𝑣 ∈ 𝐶2

𝑅 , 𝐿(�̃�, 𝑦) > 𝐿(𝑥, 𝑦)}

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝐵𝐶(𝐺): = {(𝑢, 𝑣): 𝑢 ∈ 𝐶1
𝐶 , 𝑣 ∈ 𝐶2

𝐶 , 𝐿(𝑥, �̃�) > 𝐿(𝑥, 𝑦)}

𝐵𝑅,𝐶(𝐺): = {(𝑢, 𝑣): 𝑢 ∈ 𝐶1, 𝑣 ∈ 𝐶2, 𝐿(�̃�, �̃�) > 𝐿(𝑥, 𝑦)}

                    (3.4) 

Then we are trying to prove that for √𝑎 − √𝑏 < √2, there exists at least one bad vertex in rows or 

columns, which would result in max{𝐿(�̃�, 𝑦), 𝐿(𝑥, �̃�), 𝐿(�̃�, �̃�) ≥ 𝐿(𝑥, 𝑦)}. We define a pair of bad 

vertex (𝑢, 𝑣), the relationship between degrees can be inferred from the following relationship between 

MLE: 

𝐿(�̃�, 𝑦) > 𝐿(𝑥, 𝑦) → 𝑑−
𝑅(𝑢) + 𝑑−

𝑅(𝑣) > 𝑑+
𝑅(𝑢) + 𝑑+

𝑅(𝑣)

𝐿(𝑥, �̃�) > 𝐿(𝑥, 𝑦) → 𝑑−
𝐶(𝑢) + 𝑑−

𝐶(𝑣) > 𝑑+
𝐶(𝑢) + 𝑑+

𝐶(𝑣)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(3.5)

𝐿(�̃�, �̃�) > 𝐿(𝑥, 𝑦) → 𝑑−
𝑅(𝑢) + 𝑑−

𝑅(𝑣) + 𝑑−
𝐶(𝑢) + 𝑑−

𝐶(𝑣) > 𝑑+
𝑅(𝑢) + 𝑑+

𝑅(𝑣) + 𝑑+
𝐶(𝑢) + 𝑑+

𝐶(𝑣)

 

Since if 𝐿(�̃�, 𝑦) > 𝐿(𝑥, 𝑦), then 𝐿(𝑥, �̃�) > 𝐿(𝑥, 𝑦)or⁡𝐿(�̃�, �̃�) > 𝐿(𝑥, 𝑦). Hence, it is enough to only 

study the bad vertices in rows or in columns. 

Definition 3.4. Using the concept of degree, we can define a set of bad vertices in rows: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝐵𝑖
𝑅(𝐺) = {∃𝑢: 𝑢 ∈ 𝐶𝑖

𝑅 , 𝑑+
𝑅(𝑢) ≤ 𝑑−

𝑅(𝑢) − 1}, 𝑖 = 1,2                     (3.6) 

where 𝑖 represents the community. 

Lemma 3.2. If 𝐵1
𝑅(𝐺) is non-empty and with high probability, then 𝐵𝑅(𝐺) is non-empty and with 

non-vanishing probability. 

3.2 Acheivability 

Recall that our goal is to show that √𝑎 − √𝑏 = √2 is the tight threshold for exact recovery. After 

showing that when √𝑎 − √𝑏 < √2 MLE fails to recover the communities, we will show that the SDP 

relaxation (2.5) can recover the communities otherwise. 

Theorem 3.3. Let 𝐺 be a graph drawn from DSBM⁡(𝑛, 𝑝, 𝑞), let 𝑝 =
𝑎log⁡(𝑛)

𝑛
 and 𝑞 =

𝑏log⁡(𝑛)

𝑛
, if 

√𝑎 − √𝑏 > √2,                                  (3.7) 

then the SDP relaxation in (2.5) can recover the communities with high probability. 

Without loss of generality, we suppose that the ground-truth community indicator, denoted by 𝒈 is 

(𝟏𝑛/2
⊤ , −𝟏𝑛/2

⊤ , 𝟏𝑛/2
⊤ , −𝟏𝑛/2

⊤ )
⊤

. Since we use the notion of co-clustering introduced Section 2.2, 𝒈 is the 

stack of the column communities and the row communities. Then we claim that when √𝑎 − √𝑏 > √2, 

(2.5) has a unique solution equal to 𝒈𝒈⊤. The following lemma uses a surrogate 𝚲 to quantify the 

condition under which 𝒈𝒈⊤ is the unique solution. 

Definition 3.5. Given a graph 𝐺 drawn from DSBM with two clusters, we can have: 

ΓDSBM = 𝑫+ −𝑫− − 𝑨∗                                 (3.8) 

Lemma 3.4. Let 𝚲 = 2ΓDSBM + 𝑰2𝑛 + [
2𝑱𝑛 𝑱𝑛 − 𝑰𝑛

𝑱𝑛 − 𝑰𝑛 2𝑱𝑛
], if 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

70 
Published by SCHOLINK INC. 

𝚲 ≽ 0, ⁡𝜆2(𝚲) > 0. 

then 𝒈𝒈⊤ is the unique solution to the SDP relaxation (2.5). 

Since 𝚲 is random, the second smallest eigenvalue of it is hard to calculate. However, thanks to Weyl's 

inequality, we can estimate it using its population counterpart, i.e., the second smallest eigenvalue of 

𝔼𝚲. The following lemma specifies the distance between the two quantities. 

Lemma 3.5. Let 𝑛 > 4 be even and 

𝜆max(−Γ𝑆𝐵𝑀 + 𝔼[Γ𝑆𝐵𝑀]) < 𝑛(𝑝 − 𝑞),                      (3.9) 

then the SDP relaxation for DSBM can achieve exact recovery, meaning that gg⊤ is the only solution. 

The following theorem finalizes the proof in this part by connecting the degree and community 

detection in DSBM. 

Theorem 3.6. Let 𝑛 ≥ 4 be even and 𝑮 be a graph of directed stochastic block model drawn from 

𝒢(𝑛, 𝑝, 𝑞), where 𝑝 > 𝑞. Only when 
log⁡(𝑛)

𝑛
< 𝑞 < 𝑝 <

1

2
, and for some constant 𝑐 > 1, then 𝚫 > 0 

such that, with high probability, the following equation holds: If 

min
𝑖∈[2𝑛]

 (𝒟𝑖𝑖
+ −𝒟𝑖𝑖

−) ≥
𝚫

log⁡(𝑛)
𝔼[deg𝐶

+⁡(𝑖) − deg𝐶
−⁡(𝑖)]                     (3.10) 

then the semidefinite program achieve exact recovery. Now we have the equation represented by degree, 

which is easier and more straightforward to solve than the previous lemma. 

Lemma 3.7. Let 𝐺 be a random graph with 𝑛 node drawn accordingly to the directed stochastic 

block model on two communities with in-community edge probability 𝑝 and cross-community edge 

probability 𝑞. Let 𝑝 = alog⁡(𝑛)/𝑛 and 𝑞 = 𝑏log⁡(𝑛)/𝑛, where 𝑎 > 𝑏 are constant. Then for any 

constant > 0 : 

If 

√𝑎 − √𝑏 > √2                                  (3.11) 

then with high probability 

min
𝑖∈[2𝑛]

 (𝒟𝑖𝑖
+ − 𝒟𝑖𝑖

−) ≥
𝚫

log⁡(𝑛)
𝔼[deg𝐶

+⁡(𝑖) − deg𝐶
−⁡(𝑖)]                     (3.12) 

 

4. Experiments 

The goal of the numerical experiments is to confirm our theoretical results above. Let 𝑛 = 100. For 

each (𝑎, 𝑏) pair we generate the DSBM 25 times and apply the SDP relaxation to recover the 

community. Figure 1 visualizes the accuracy v.s. (𝑎, 𝑏). The accuracy is calculated as follows 

1

2𝑛
∑  

𝑛

𝑖=1

𝟏{𝑔𝑖=𝑥𝑖} 

where 𝟏{⋅} is the indicator function and 𝒈 is the ground-truth and 𝒙 is the solution of SDP relaxation. 

As depicted in Figure 1, the empirical boundary between the success region and the failure region 

almost aligns with the curve √𝑎 − √𝑏 = √2, which suggests that our proved information-theoretical 

threshold is tight. 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

71 
Published by SCHOLINK INC. 

 

Figure 1. Accuracy of the SDP Relaxation under Different 𝒂 and 's. Each (𝒂, 𝒃) Pair is Subject 

to 25 Experiments 

 

A Proof for Theorem 3.1 

In this section, we are trying to discover the condition when MLE can not fully recover the 

communities in DSBM and the condition's proof. Let 𝐺  be a graph drawn from 𝒢(𝑛, 𝑝, 𝑞), let 

𝑝 =
𝑎log⁡(𝑛)

𝑛
 and 𝑞 =

𝑏log⁡(𝑛)

𝑛
, 𝑎 > 𝑏, if √𝑎 − √𝑏 < √2, then we need to prove that for this condition 

the exact recovery of DSBM is unsolvable, and therefore MLE fails. We define MLE for DSBM to be: 

𝐿(𝑥, 𝑦) = ∏  𝑖,𝑗 𝑃𝑖,𝑗
𝐴𝑖,𝑗(1 − 𝑃𝑖𝑗)

1−𝐴𝑖,𝑗
                          (A.1) 

Definition A.1. We define a pair of bad vertices in rows, in columns, or in rows and columns 

respectively by: 

𝐵𝑅(𝐺): = {(𝑢, 𝑣): 𝑢 ∈ 𝐶1
𝑅 , 𝑣 ∈ 𝐶2

𝑅 , 𝐿(�̃�, 𝑦) > 𝐿(𝑥, 𝑦)}

𝐵𝐶(𝐺): = {(𝑢, 𝑣): 𝑢 ∈ 𝐶1
𝐶 , 𝑣 ∈ 𝐶2

𝐶 , 𝐿(𝑥, �̃�) > 𝐿(𝑥, 𝑦)}

𝐵𝑅,𝐶(𝐺): = {(𝑢, 𝑣): 𝑢 ∈ 𝐶1, 𝑣 ∈ 𝐶2, 𝐿(�̃�, �̃�) > 𝐿(𝑥, 𝑦)}

                (A.2) 

Then we are trying to prove that for √𝑎 − √𝑏 < √2, there exists at least one bad vertex in rows or 

columns, which would result in max{𝐿(�̃�, 𝑦), 𝐿(𝑥, �̃�), 𝐿(�̃�, �̃�) ≥ 𝐿(𝑥, 𝑦)}. We define a pair of bad 

vertex (𝑢, 𝑣), the relationship between degrees can be inferred from the following relationship between 

MLE: 

𝐿(�̃�, 𝑦) > 𝐿(𝑥, 𝑦) → 𝑑−
𝑅(𝑢) + 𝑑−

𝑅(𝑣) > 𝑑+
𝑅(𝑢) + 𝑑+

𝑅(𝑣)

𝐿(𝑥, �̃�) > 𝐿(𝑥, 𝑦) → 𝑑−
𝐶(𝑢) + 𝑑−

𝐶(𝑣) > 𝑑+
𝐶(𝑢) + 𝑑+

𝐶(𝑣)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(A. 3)

𝐿(�̃�, �̃�) > 𝐿(𝑥, 𝑦) → 𝑑−
𝑅(𝑢) + 𝑑−

𝑅(𝑣) + 𝑑−
𝐶(𝑢) + 𝑑−

𝐶(𝑣) > 𝑑+
𝑅(𝑢) + 𝑑+

𝑅(𝑣) + 𝑑+
𝐶(𝑢) + 𝑑+

𝐶(𝑣)

 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

72 
Published by SCHOLINK INC. 

Since if 𝐿(�̃�, 𝑦) > 𝐿(𝑥, 𝑦), then 𝐿(𝑥, �̃�) > 𝐿(𝑥, 𝑦)or⁡𝐿(�̃�, �̃�) > 𝐿(𝑥, 𝑦). Hence, it is enough to only 

study the bad vertices in rows or in columns. 

Definition A.2. We define a set of bad vertices in rows: 

𝐵𝑖
𝑅(𝐺) = {∃𝑢: 𝑢 ∈ 𝐶𝑖

𝑅 , 𝑑+
𝑅(𝑢) ≤ 𝑑−

𝑅(𝑢) − 1}, 𝑖 = 1,2                  (A.4) 

where 𝑖 represents the community. 

Lemma A.1. If 𝐵1
𝑅(𝐺) is non-empty and with high probability, then 𝐵𝑅(𝐺) is non-empty and with 

non-vanishing probability. 

Proof. If 𝑢 ∈ 𝐶1
𝑅  and 𝑣 ∈ 𝐶2

𝑅  such that 𝑑+
𝑅(𝑢) ≤ 𝑑−

𝑅(𝑢) − 1  and 𝑑+
𝑅(𝑣) ≤ 𝑑−

𝑅(𝑣) − 1 , then 

combining these we get 𝑑−
𝑅(𝑢) + 𝑑−

𝑅(𝑣) > 𝑑+
𝑅(𝑢) + 𝑑+

𝑅(𝑣). Then we have: 

ℙ(∃𝑢 ∈ 𝐵𝑅 or ∃𝑣 ∈ 𝐵𝑅) = ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) + ℙ(∃𝑣 ∈ 𝐵1

𝑅(𝐺)) − ℙ(∃(𝑢, 𝑣) ∈ 𝐵𝑅(𝐺))

ℙ(∃(𝑢, 𝑣) ∈ 𝐵𝑅(𝐺)) = ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) + ℙ(∃𝑣 ∈ 𝐵1

𝑅(𝐺)) − ℙ(∃𝑢 ∈ 𝐵𝑅 or ∃𝑣 ∈ 𝐵𝑅)
      (A.5) 

because the possibility of node 𝑢 is a bad vertex is the same as node 𝑣 is a bad vertex, so we can 

write: 

ℙ(∃(𝑢, 𝑣) ∈ 𝐵𝑅(𝐺)) ≤ 2ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) − 1                    (A.6) 

Lemma A.2. Let 𝐺 be a graph drawn from 𝒢(𝑛, 𝑝, 𝑞), let 𝑝 =
𝑎log⁡(𝑛)

𝑛
 and 𝑞 =

𝑏log⁡(𝑛)

𝑛
, 𝑎 > 𝑏, if 

√𝑎 − √𝑏 < √2, then: 

ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) = 1 − 𝑜(1)                           (A.7) 

Proof. Note that ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) can be written as: 

ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) = 𝑛ℙ(𝑑−

𝑅 > 𝑑+
𝑅) = 𝑛ℙ(Bin⁡(

𝑛

2
, 𝑞) > Bin⁡(

𝑛

2
, 𝑝))              (A.8) 

 

Then, we introduce a new definition. 

Definition A.3. Let 𝑚 be a natural number, 𝑝, 𝑞 ∈ [0,1], and 𝛿 ∈ ℝ, we define 

𝑇(𝑚, 𝑝, 𝑞, 𝛿) = ℙ[∑  𝑚
𝑖=1   (𝑍𝑖 −𝑊𝑖 ≥ 𝛿)]                        (A.9) 

where 𝑊1, … ,𝑊𝑚  are i.i.d. Bernoulli(p) and 𝑍1, … , 𝑍𝑚  are i.i.d. Bernoulli(q), independent of 

𝑊1, … ,𝑊𝑚. 

Definition A.4. We define: 

𝑉(𝑚, 𝑝, 𝑞, 𝑡, 𝑐)

⁡= (
𝑚

(𝑡 + 𝑐)
𝑚

𝑛
log⁡(𝑛)) (

𝑚

𝑡
𝑚

𝑛
log⁡(𝑛)) 𝑝

𝑡
𝑚

𝑛
log⁡(𝑛)𝑞(𝑡+𝑐)

𝑚

𝑛
log⁡(𝑛)(1 − 𝑝)𝑚−𝑡

𝑚

𝑛
log⁡(𝑛)(1 − 𝑞)(𝑡+𝑐)

𝑚

𝑛
log⁡(𝑛) 

(A.10) 

Where 𝑐 = 𝑂(1). We also define the function: 

𝑔(𝑎, 𝑏, 𝑐) = (𝑎 + 𝑏) − 𝑐log⁡(𝑏) − 2√(
𝑐

2
)
2

+ 𝑎𝑏 +
𝑐

2
log⁡(𝑎𝑏

√(
𝑐

2
)
2
+𝑎𝑏+

𝑐

2

√(
𝑐

2
)
2
+𝑎𝑏−

𝑐

2

)      (A.11) 

Then we have the following results for 𝑇∗(𝑚, 𝑝, 𝑞, 𝑐) = max𝑡>0  𝑉(𝑚, 𝑝, 𝑞, 𝑡, 𝑐) : [7] For 𝑚 ∈ ℕ and 

∀𝑡 > 0: 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

73 
Published by SCHOLINK INC. 

−log⁡(𝑇∗(𝑚, 𝑝, 𝑞, 𝑐)) ≥
𝑚

𝑛
log⁡(𝑛) ∗ 𝑔(𝑚, 𝑛, 𝑐) − 𝑜 (

𝑚

𝑛
log⁡(𝑛)) ∀𝑚 ∈ ℕ           (A.12) 

In the following proof of this lemma, we will omit the ceiling symbol for clarity. In the case of the 

directed stochastic block model, recall definition A.3, we have: 

𝑇(𝑚, 𝑝, 𝑞, 0) = ℙ[𝑍 −𝑊 ≥ 0)]                     (A.13) 

where 𝑍 is a Binomial⁡(𝑚, 𝑞) and 𝑊 is a Binomial (𝑚, 𝑝), 𝑝 =
𝑎log⁡(𝑛)

𝑛
, 𝑞 =

𝑏log⁡(𝑛)

𝑛
. We can re-write 

(A.10) into: 

𝑇(𝑚, 𝑝, 𝑞, 0) = ∑  𝑚
𝑘1=0

(∑  𝑚
𝑘2=𝑘1

 ℙ(𝑍 = 𝑘2))ℙ(𝑊 = 𝑘1)              (A.14) 

Where each term in the double summation can be upper-bounded by 𝑇∗(𝑚, 𝑝, 𝑞, 0). Using 𝑐 = 0, we 

have 

𝑇(𝑚, 𝑝, 𝑞, 0)⁡≤ 𝑚2𝑇∗(𝑚, 𝑝, 𝑞, 0)

−log⁡(𝑇(𝑚, 𝑝, 𝑞, 0))⁡≥ −2log⁡(𝑚) − log⁡(𝑇∗(𝑚, 𝑝, 𝑞, 0))

⁡≥ −2log⁡(𝑚) +
2𝑚

𝑛
(
𝑎+𝑏

2
− √𝑎𝑏) log⁡(𝑛)

             (A.15) 

As long as 
𝑚

𝑛
> log⁡log⁡(𝑛) and 𝑚 ≤

𝑛2

4
, then we have log⁡(𝑚) = 𝑜 (

𝑚

𝑛
log⁡(𝑛)). Hence, 

−log⁡(𝑇(𝑚, 𝑝, 𝑞, 0)) ≥
2𝑚

𝑛
(
𝑎+𝑏

2
− √𝑎𝑏) log⁡(𝑛) − 𝑜 (

𝑚

𝑛
log⁡(𝑛))            (A.16) 

In this case, 𝑇(𝑚, 𝑝, 𝑞, 0) is equivalent to ℙ(Bin⁡(
𝑛

2
, 𝑞) > Bin⁡(

𝑛

2
, 𝑝)), and continuing (A.8), as 𝑛 

approaches infinity, we get: 

ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) = 𝑛ℙ(𝑑−

𝑅 > 𝑑+
𝑅) = 𝑛ℙ(Bin⁡(

𝑛

2
, 𝑞) > Bin⁡(

𝑛

2
, 𝑝)) = 𝑛

1−(
√𝑎−√𝑏

√2
)
2

+𝑜(1)
      (A.17) 

Therefore, when √𝑎 − √𝑏 < √2, ℙ(∃𝑢 ∈ 𝐵1
𝑅(𝐺)) = 1 − 𝑜(1), there exists a bad vertex and exact 

recovery is unachievable. 

B Proof for Theorem 3.3 

Proof for Lemma 3.4 Let 𝒈 = (1,… ,1, −1,… ,−1,1, . . ,1, −1,… ,−1). without loss of generality. By 

KKT condition, we obtain a sufficient condition for 𝒈𝒈⊤ to be the solution of the SDP relaxation (2.5). 

Therefore, we have 𝚲 ≽ 0, and 𝒈𝒈⊤ is guaranteed to be the optimal solution to SDP relaxation (2.5) 

if: 

1. 𝒈𝒈⊤ is a solution to the primal problem, 

2. There exists a matrix 𝒀 feasible for the dual problem such that Tr⁡((2𝑨∗ − 𝑱2𝑛)𝒈𝒈
⊤) = 

Tr⁡(𝒀). 

The first condition is already satisfied by the given background, then we need to find a 𝒀 (also known 

as dual certificate) that would satisfy the second condition. We can use 𝑪 to substitute 2𝑨∗ − 𝑱2𝑛, 

then we have: 

(𝑪𝒈𝒈⁡⊤)𝑖𝑖 = ⁡correct⁡edges⁡ + ⁡correct⁡non − edges⁡- incorrect edges - incorrect non-edges  

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= (𝑫𝐶
+)𝑖𝑖 + (

𝑛

2
− (𝑫𝐶

−)𝑖𝑖) − (
𝑛

2
− 1 − (𝑫𝐶

+)𝑖𝑖) − (𝑫𝐶
−)𝑖𝑖 + 1

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= 2((𝑫𝐶
+)𝑖𝑖 − (𝑫𝐶

−)𝑖𝑖) + 1
                    (B.1) 

for 𝑖 ∈ [𝑛 + 1,2𝑛], we let 𝑗 = 𝑖 − 𝑛, then we have: 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

74 
Published by SCHOLINK INC. 

(𝑪𝒈𝒈⊤)𝑖𝑖 = 2((𝑫𝑅
+)𝑗𝑗 − (𝑫𝑅

−)𝑗𝑗) + 1                     (B.2) 

Therefore, we get Tr⁡(𝑪𝒈𝒈⊤) = Tr⁡(2(𝑫𝐶
+ −𝑫𝐶

−) + 𝑰𝑛) + Tr⁡(2(𝑫𝑅
+ − 𝑫𝑅

−) + 𝑰𝑛), and we are able to 

find a matrix 𝒀 that is feasible for the dual problem and satisfies the proposed condition: 

𝒀 = [
2(𝑫𝐶

+ −𝑫𝐶
−) + 𝑰𝑛 0

0 2(𝑫𝑅
+ −𝑫𝑅

−) + 𝑰𝑛
]. 

As a result, if 𝚲 ≽ 0, then 𝒈𝒈⊤ is the optimal solution to the SDP. 

In addition, 𝜆2(𝚲) > 0 ensures that 𝒈𝒈⊤ is the only solution to SDP. Imagine there is another 

optimal solution 𝑿∗  to the SDP, then we get Tr⁡(𝑿′𝚲) = 0  by complementary slackness. By 

assumption, the second smallest eigenvalue of 𝚲 is non-zero, together with the complementary 

slackness, the fact that 𝑿′ ≽ 0  and 𝚲 ≽ 0 , we have 𝑿′ = 𝑘𝒈𝒈⊤ . Since 𝑿𝑖𝑖
′ = 1,𝑿′ = 𝒈𝒈⊤  by 

contradiction. 

Then we need to estimate 𝔼𝚲, then we have the following: 

𝔼[𝚲]⁡= 𝔼 [2Γ𝑆𝐵𝑀 + 𝑰2𝑛 + [
0 𝑱𝑛 − 𝑰𝑛

𝑱𝑛 − 𝑰𝑛 0
] + 2 [

𝑱𝑛 0
0 𝑱𝑛

]]

⁡= 2(
𝑛

2
(𝑝 − 𝑞)𝑰2𝑛 − (

𝑝+𝑞

2
[
0 𝑱𝑛
𝑱𝑛 0

] +
𝑝−𝑞

2
𝒈𝒈⊤))

⁡+ [
0 𝑱𝑛
𝑱𝑛 0

] + 𝑰2𝑛 − [
0 𝑰𝑛
𝑰𝑛 0

] + (𝑝 − 𝑞) [
𝒈′𝒈′⊤ 0

0 𝒈′𝒈′⊤] + 2 [
𝑱𝑛 0
0 𝑱𝑛

]

⁡= 𝑛(𝑝 − 𝑞)(𝑰2𝑛 −
[

0 𝒈′𝒈′⊤

𝒈′𝒈′⊤ 0
]

𝑛
) + (1 − (𝑝 + 𝑞)) [

0 𝑱𝑛
𝑱𝑛 0

] + 𝑰2𝑛 − [
0 𝑰𝑛
𝑰𝑛 0

] + 2 [
𝑱𝑛 0
0 𝑱𝑛

]

  

(B.3) 

Suppose 𝑝 <
1

2
 and 𝜆2 = 𝑛(𝑝 − 𝑞), whose eigenvector is perpendicular to (𝒈′, 𝒈′)⊤ and (𝟏, 𝟏)⊤𝚫 

can be re-written as: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝚲 = 2ΓDSBM + 𝑰2𝑛 + [
0 𝑱𝑛 − 𝑰𝑛

𝑱𝑛 − 𝑰𝑛 0
] + 2 [

𝑱𝑛 0
0 𝑱𝑛

]                 (B.4) 

Using Weyl's inequalities, we get: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝜆2 > 𝜆max(𝔼[𝚲] − 𝚲) =∥ 𝔼[𝚲] − 𝚲 ∥

⁡≥ 𝜎2(𝔼[𝚲] − 𝜎2(𝚲))

⁡= 𝜆2(𝔼[𝚲] − 𝜆2(𝚲))

⁡≥ 𝜆2(𝔼[𝚲] − 𝜆2(𝚲))

                         (B.5) 

This implies that 𝒈𝒈⊤ is the unique solution to the semidefinite programming. 

Proof for Theorem 3.6 The method to approach the problem is by applying spectral approximation of 

random Laplacian matrix algorithm. However, ΓDSBM is not a Laplacian matrix. Therefore, we will try 

to construct a Laplacian matrix ΓDSBM
′  to help solve the problem. W.L.O.G. we let 

𝒈 = (𝟏𝑛/2, −𝟏𝑛/2, 𝟏𝑛/2, −𝟏𝑛/2), and we define: 

ΓDSBM
′ = diag⁡(𝒈)ΓDSBMdiag⁡(𝒈)                         (B.6) 

Both the eigenvalue and the diagonal elements of 𝔼[ΓDSBM
′ ] − ΓDSBM

′  are the same as those of 

𝔼[ΓDSBM] − ΓDSBM . The off-diagonal entries of ΓDSBM
′ = −𝑨𝑖𝑗𝑔𝑖𝑔𝑖 . Then we apply spectral 

approximation of random Laplacian matrix algorithm, we let 𝑳 = 𝔼[ΓDSBM
′ ] − ΓDSBM

′ , where 𝑳 has 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

75 
Published by SCHOLINK INC. 

independent off-diagonal entries. Then we have: 

∑  𝑗∈[2𝑛]/𝑖 𝔼[𝑳𝑖𝑗
2 ] = (

𝑛

2
− 1)𝑝(1 − 𝑝) +

𝑛

2
𝑞(1 − 𝑞) ≤

𝑛

2
∗
1

4
(𝑝 + 𝑞) >

𝑛

8

2log⁡𝑛

𝑐𝑛
(1 − 𝑞)2 =

log⁡𝑛

4𝑐
max
𝑖≠𝑗

 ∥∥𝑳𝑖𝑗∥∥∞
2

  (B.7) 

Where it exists a constant 𝚫′ such that with high probability, 

𝜆max(𝔼[ΓDSBM
′ ] − Γ𝐷𝑆𝐵𝑀

′ ) ≤ (1 +
𝚫′

√log⁡𝑛
) max
𝑖∈[2𝑛]

 [𝔼[(ΓDSBM
′ )𝑖𝑖] − (ΓDSBM

′ )𝑖𝑖]             (B.8) 

and it is the same as the following: 

𝜆max(𝔼[ΓDSBM] − Γ𝐷𝑆𝐵𝑀) ≤ (1 +
𝚫′

√log⁡𝑛
) max
𝑖∈[2𝑛]

 [𝔼[(ΓDSBM)𝑖𝑖] − (ΓDSBM)𝑖𝑖]              (B.9) 

It is worth mentioning that 

⁡⁡⁡⁡⁡⁡ min
𝑖∈[2𝑛]

 ((𝒟+)𝑖𝑖 − (𝒟−)𝑖𝑖)⁡≥ (1 +
𝚫′

√log⁡𝑛
) max
𝑖∈[2𝑛]

 [𝔼[(ΓDSBM)𝑖𝑖] − (ΓDSBM)𝑖𝑖]

⁡= (1 −
𝚫′

√log⁡𝑛
) (

𝑛

2
(𝑝 − 𝑞) − 𝑝)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 10)

⁡≥ max
𝑖∈[2𝑛]

 (𝔼[(ΓDSBM
′ )𝑖𝑖] − (ΓDSBM 

′ )𝑖𝑖

 

Therefore we have: 

𝜆max(𝔼[ΓDSBM
′ ] − Γ𝐷𝑆𝐵𝑀

′ ) ≤ (1 +
𝚫′

√log⁡𝑛
)(1 −

𝚫′

√log⁡𝑛
) (

𝑛

2
(𝑝 − 𝑞) − 𝑝)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 11) 

For each 𝚫′, there exists at least one 𝚫′ > 0 such that: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(1 −
𝚫′

√log⁡𝑛
)(1 +

𝚫′

√log⁡𝑛
) < 1⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 12) 

Hence 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝜆max(𝔼[ΓDSBM
′ ] − Γ𝐷𝑆𝐵𝑀

′ ) <
𝑛

2
(𝑝 − 𝑞)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 13) 

can guarantee the exact recovery of DSBM. 

Proof for Lemma 3.7 

Lemma B.1. Recall definition 𝐴. 3, let 𝑎, 𝑏 and 𝚫′ be constants. We have, 

⁡⁡⁡⁡𝑇 (
𝑛

2
,
𝑎log⁡(𝑛)

𝑛
,
𝑏log⁡(𝑛)

𝑛
, −Δ′√log⁡(𝑛)) ≤ exp⁡[− (

𝑎 + 𝑏

2
− √𝑎𝑏 − 𝛿(𝑛)) log⁡(𝑛)]⁡⁡⁡⁡⁡(B. 14) 

with lim𝑛→∞  𝛿(𝑛) 

Proof of this lemma can be found in [2]. We are now ready to prove Lemma 3.7 Let 𝑎 > 𝑏 be 

constants and satisfy √𝑎 − √𝑏 > √2. Given Δ > 0, we want to prove that with high probability 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ min
𝑖∈[2𝑛]

 (𝒟𝑖𝑖
+ − 𝒟𝑖𝑖

−) ≥
𝚫

log⁡(𝑛)
𝔼[deg𝐶

+⁡(𝑖) − deg𝐶
−⁡(𝑖)] =

𝚫

log⁡(𝑛)

𝑛

2
(𝑝 − 𝑞)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 15) 

For fixed 𝑖 throughout the proof. We can write 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

76 
Published by SCHOLINK INC. 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(𝐷+)𝑖𝑖 − (𝐷−)𝑖𝑖 = ( ∑  

𝑛/2−1

𝑖=1

 𝑊𝑖) − (∑ 

𝑛/2

𝑖=1

 𝑍𝑖) = ∑  

𝑛/2−1

𝑖=1

(𝑊𝑖 − 𝑍𝑖) + 𝑍𝑛/2⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 16) 

Hence, we substitute 𝑝 and 𝑞 with 
𝑎log⁡(𝑛)

𝑛
 and 

𝑏log⁡(𝑛)

𝑛
 respectively 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡
𝚫

√log⁡(𝑛)
(
𝑛

2
(𝑝 − 𝑞)) = Δ√log⁡(𝑛) (

𝑎 − 𝑏

2
)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 17) 

We have the probability of degin ⁡(𝑖) − degout ⁡(𝑖) <
𝚫

√log⁡(𝑛)
(𝑛/2(𝑝 − 𝑞)) is equal to 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡

ℙ( ∑  

𝑛/2−1

𝑖=1

  (𝑊𝑖 − 𝑍𝑖) + 𝑍𝑛/2 < Δ√log⁡(𝑛) (
𝑎 − 𝑏

2
))

=ℙ( ∑  

𝑛/2−1

𝑖=1

  (𝑍𝑖 −𝑊𝑖) − 𝑍𝑛/2 > −Δ√log⁡(𝑛) (
𝑎 − 𝑏

2
))

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 18) 

which is upper bounded by, 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ℙ [∑  

𝑛/2

𝑖=1

  (𝑍𝑖 −𝑊𝑖) > −Δ√log⁡(𝑛) (
𝑎 − 𝑏

2
)]⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 19) 

We let 𝚫′ = 𝚫(
𝑎−𝑏

2
) + 1, then using the previous definition, we can obtain the following inequalities: 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ℙ((𝒟𝑖𝑖
+ −𝒟𝑖𝑖

−) <
𝚫

log⁡(𝑛)
𝔼[deg𝐶

+⁡(𝑖) − deg𝐶
−⁡(𝑖)])

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡≤ 𝑇 (
𝑛

2
,
𝑎log⁡(𝑛)

𝑛
,
𝑏log⁡(𝑛)

𝑛
, −𝚫′√log⁡(𝑛))

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡≤ exp⁡[− (
𝑎 + 𝑏

2
− √𝑎𝑏 − 𝛿(𝑛)) log⁡(𝑛)]

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 20) 

By using union bound, we can have: 

⁡⁡⁡ℙ [ min
𝑖∈[2𝑛]

 (𝑫𝑖𝑖
+ −𝑫𝑖𝑖

− <
𝚫

√log⁡(𝑛)

𝑛

2
(𝑝 − 𝑞))]

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡≤ exp⁡[− (
𝑎 + 𝑏

2
− √𝑎𝑏 − 1 − 𝛿(𝑛)) log⁡(𝑛)]

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B21) 

from this, if we have 
𝑎+𝑏

2
− √𝑎𝑏 > 1, which can be re-written into √𝑎 − √𝑏 > √2, then this means 

that the probability of ℙ [min𝑖∈[2𝑛]  (𝑫𝑖𝑖
+ −𝑫𝑖𝑖

− <
𝚫

√log⁡(𝑛)

𝑛

2
(𝑝 − 𝑞))] is negative. Then when 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡√𝑎 − √𝑏 > √2⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 22) 

it holds true with high probability that 

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ min
𝑖∈[2𝑛]

 (𝒟𝑖𝑖
+ − 𝒟𝑖𝑖

−) ≥
𝚫

log⁡(𝑛)
𝔼[deg𝐶

+⁡(𝑖) − deg𝐶
−⁡(𝑖)]⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(B. 23) 

 

 



www.scholink.org/ojs/index.php/asir             Applied Science and Innovative Research                  Vol. 8, No. 1, 2024 

77 
Published by SCHOLINK INC. 

References 

Afonso S. Bandeira. (2015). Random Laplacian matrices and convex relaxations. 

https://doi.org/10.1007/s10208-016-9341-9 

Andrea Lancichinetti, Santo Fortunato, & Filippo Radicchi. (2008). Benchmark graphs for testing 

community detection algorithms. In Physical Review E 78.4. 

https://doi.org/10.1103/PhysRevE.78.046110 

Emmanuel Abbe, Afonso S. Bandeira, & Georgina Hall. (2014). Exact Recovery in the Stochastic 

Block Model. In CoRR abs/1405.3267.  

Emmanuel Abbe, Afonso S. Bandeira, & Georgina Hall. (2014). Exact Recovery in the Stochastic Block 

Model.  

Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. In 

Proceedings of the National Academy of Sciences 99.12 (pp. 7821-7826). 

https://doi.org/10.1073/pnas.122653799 

Newman, M. E. J. (2003). The Structure and Function of Complex Networks. In SIAM Review 45.2 (pp. 

167-256). https://doi.org/10.1137/S003614450342480 

Santo Fortunato. (2010). Community detection in graphs. In Physics Reports 486.3-5 (pp. 75-174). 

https://doi.org/10.1016/j.physrep.2009.11.002