--- abstract: 'The stochastic block model is a canonical random graph model for clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among which the phase transition at the Kesten-Stigum threshold is particularly interesting both from a mathematical and an applied standpoint. It states that no estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below certain threshold. Nevertheless, if we slightly extend the horizon to the ubiquitous semi-supervised setting, such a fundamental limitation will disappear completely. We prove that with arbitrary fraction of the labels revealed, the detection problem is feasible throughout the parameter domain. Moreover, we introduce two efficient algorithms, one combinatorial and one based on optimization, to integrate label information with graph structures. Our work brings a new perspective to stochastic model of networks and semidefinite program research.' author: - 'Junda Sheng [^1]' - 'Thomas Strohmer [^2]' bibliography: - 'SSC.bib' title: | Semi-Supervised Clustering of Sparse Graphs:\ Crossing the Information-Theoretic Threshold --- <span> ***Keywords—*** clustering, semi-supervised learning, stochastic block model, Kesten-Stigum threshold, semidefinite programming </span> Introduction ============ Clustering on graphs -------------------- The basic task of *clustering* or *community detection* in its general form is, given a (possibly weighted) graph, to partition its vertices into several densely connected groups with relatively weak external connectivity. This property is sometimes also called assortativity. Clustering and community detection are central problems in machine learning and data science with various applications in scientific research and industrial development. A considerable amount of data sets can be represented in the form of a network that consists of interacting nodes, and one of the first features of interest in such a situation is to understand which nodes are "similar", as an end or as preliminary step towards other learning tasks. Clustering is used to find genetically similar sub-populations @10.3389/fgene.2014.00204, to segment images @868688, to study sociological behavior @doi:10.1073/pnas.012582999, to improve recommendation systems @1167344, to help with natural language processing @doi:10.1073/pnas.1221839110, etc. Since the 1970s, in different communities like social science, statistical physics and machine learning, a large diversity of algorithms have been developed such as: - Hierarchical clustering algorithms @hierarchy build a hierarchy of progressive communities, by either recursive aggregation or division. - Model-based statistical methods, including the celebrated EM algorithm. @https://doi.org/10.1111/j.2517-6161.1977.tb01600.x, fit the data with cluster-exhibiting statistical models. - Optimization approaches identify the best cluster structures in regard to carefully designed cost functions, for instance, minimizing the cut @HARTUV2000175 and maximizing the Girvan-Newman modularity @Newman2004FindingAE. Multiple lines of research intersect at a simple random graph model, which appears under many different names. In the machine learning and statistics literature around social networks, it is called the stochastic block model (SBM) @Holland1983StochasticBF, while it is known as the planted partition model @715914 in theoretical computer science and referred to as inhomogeneous random graph model @10.5555/1276871.1276872 in the mathematics literature. Moreover, it can also be interpreted as a spin-glass model @Decelle2011AsymptoticAO, a sparse-graph code @Abbe2015CommunityDI or a low-rank random matrix model@959929 and more. The essence of SBM can be summarized as follows: Conditioned on the vertex labels, edges are generated independently and the probability only depends on which clusters the pairs of vertices belong to. We consider its simplest form, namely the symmetric SBM consisting of two blocks, also known as the planted bisection model. \[Planted bisection model\]\[PBM\] For $n\in \mathbb{N}$ and $p,q \in (0,1)$, let $\operatorname{\mathcal{G}}(n,p,q)$ denote the distribution over graphs with $n$ vertices defined as follows. The vertex set is partitioned uniformly at random into two subsets $S_1, S_2$ with $|S_i|=n/2$. Let $E$ denote the edge set. Conditional on this partition, edges are included independently with probability $$\operatorname{P}\left((i,j)\in E | S_1, S_2\right)= \begin{cases} p & \text{~if~} \{i,j\} \subseteq S_1 \text{~or~} \{i,j\} \subseteq S_2, \\ q & \text{~if~} i \in S_1, j \in S_2 \text{~or~} i \in S_2, j \in S_1. \end{cases}$$ Note that if $p=q$, the planted bisection model is reduced to the so-called Erdős–Rényi random graph where all edges are generated independently with the same probability. Hence there exists no cluster structure. But if $p \gg q$, a typical graph will have two well-defined clusters. The SBMs generate labels for vertices before the graph. The ground truth allows us to formally discuss the presence of community structures and measure the performance of algorithms in a meaningful way. It also supplies a natural basis to rigorously define the semi-supervised clustering problem. But as a parametrized statistical model, one can only hope that it serves as a good fit for the real data. Although not necessarily a realistic model, SBM provides us an insightful abstraction and captures some of the key phenomena @MosselNS15 [@Chen2016StatisticalComputationalTI; @Banks2016InformationtheoreticTF; @Abbe2016ExactRI; @ASgen]. Given a single realization of the graph $G$, our goal is to recover the labels $x$, up to certain level of accuracy. Formally, the ground truth of the underlying community structure is encoded using the vector $x \in \{+1,-1\}^n$, with $x_i = +1$ if $i\in S_1$, and $x_i = -1$ if $i\in S_2$. An estimator is a map $\hat{x}: G_n \to \{+1,-1\}^n$ where $G_n$ is the space of graphs over $n$ vertices. We define the *overlap* between an estimator and the ground truth as $$\text{Overlap}(x,\hat{x}(G))=\frac{1}{n}| \langle x,\hat{x}(G) \rangle |.$$ <span>*Overlap*</span> induces a measure on the same probability space as the model, which represents how well an (unsupervised) estimator performs on the recovery task. To intuitively interpret the result, we put requirements on its asymptotic behavior, which takes place with high probability as $n\to\infty$. Let $G \sim \operatorname{\mathcal{G}}(n,p,q)$. The following recovery requirements are solved if there exists an algorithm that takes $G$ as an input and outputs $\hat{x}=\hat{x}(G)$ such that - Exact recovery: $\operatorname{P}\{\text{Overlap}(x,\hat{x}(G))=1\}=1-o(1)$ - Weak recovery: $\operatorname{P}\{\text{Overlap}(x,\hat{x}(G)) \geq \Omega(1) \}=1-o(1)$ In other words, exact recovery requires the entire partition to be correctly identified. Weak recovery only asks for substantially better performance than chance. In some literature, exact recovery is simply called recovery. Weak recovery is also called detection since as long as one can weakly recover the ground truth, there must exist community structure. Note that if $G$ is an Erdős–Rényi random graph ($p = q$) then the overlap will be $o(1)$ for all estimators. This can be seen by noticing that $x$ and $G$ are independent in this setting and then applying Markov's inequality. This has led to two additional natural questions about SBMs. On the one hand, we are interested in the distinguishability (or testing): is there a hypothesis test to distinguish random graph generated by Erdős–Rényi model (ERM) from random graph generated by SBMs that succeeds with high probability? One the other hand, we can ask about the model learnability (or parameter estimation): assuming that $G$ is drawn from an SBM ensemble, is it possible to obtain a consistent estimator for the parameters ($p,q$)? Although each of these questions is of independent interest, for symmetric SBMs with two symmetric communities (planted bisection model) the following holds@Abbe2017CommunityDA: $$\text{learnability}\iff\text{weak recovery}\iff\text{distinguishability}$$ The equivalence benefits the analysis of the model in turn. For example, direct analysis about weak recovery leads to the converse of phase transition theory @MosselNS15. While the achievability of the phase transition threshold @DBLP:journals/corr/Massoulie13 is proved by counting non-backtracking walks on the graph which gives consistent estimators of parameters. The recent work @montanari2015semidefinite on the analysis of SDP approaches the problem via the hypothesis testing formulation. SBMs demonstrate the 'fundamental limits' of clustering and community detection as some necessary and sufficient conditions for feasibility of recovery, information-theoretically or computationally. Moreover, they are usually expressed in the form of *phase transition*. Sharp transitions exist in the parameter regimes between phases where the task is resolvable or not. For example, when the average degree grows as $\log n$, if the structure is sufficiently obvious then the underlying communities can be exactly recovered @doi:10.1073/pnas.0907096106, and the threshold at which this becomes possible has also been determined @Abbe2016ExactRI. Above this threshold, efficient algorithms exist @Agarwal2015MultisectionIT [@Abbe2015CommunityDI; @Perry2017ASP; @Deng2021StrongCG] that recover the communities exactly, labeling every vertex correctly with high probability; below this threshold, exact recovery is information-theoretically impossible. Sparse regime and Kesten-Stigum threshold {#topo} ----------------------------------------- In the sparse case where the average degree of the graph is $O(1)$, it is more difficult to find the clusters and the best we can hope for is to label the vertices with nonzero correlation or mutual information with the ground truth, i.e. weak recovery. Intuitively, we only have access to a constant amount of connections about each vertex. The intrinsic difficulty can be understood from the topological properties of the graphs in this regime. The following basic results are derived from @Erdos1984OnTE: - For $a, b > 0$, the planted bisection model $\operatorname{\mathcal{G}}(n,\frac{a \log n}{n},\frac{b \log n}{n})$ is connected with high probability if and only if $\frac{a+b}{2}>1$. - $\operatorname{\mathcal{G}}(n,\frac{a}{n},\frac{b}{n})$ has a giant component (i.e. a component of size linear in $n$) with high probability if and only if $d\coloneqq\frac{a+b}{2}>1$. The graph will only have vanishing components if the average degree is too small. Therefore, it is not possible to even weakly recover the labels. But we will see in the next section that semi-supervised approaches amazingly piece the components together with consistent labeling. Although it is mathematically challenging to work in the sparse regime, real-world data are likely to have bounded average degrees. @Leskovec and @Strogatz:2001wc studied a large collection of the benchmark data sets, including power transmission networks, web link networks and complex biological systems, which had millions of nodes with average degree of no more than 20. For instance, the LinkedIn network they studied had approximately seven million nodes, but only 30 million edges. The phase transition for weak recovery or detection in the sparse regime was first conjectured in the paper by Decelle, Krzakala, Moore, Zdeborová @Decelle2011AsymptoticAO, which sparked the modern study of clustering and SBMs. Their work is based on deep but non-rigorous insights from statistical physics, derived with the cavity method (a.k.a. belief propagation). Since then, extensive excellent research has been conducted to understand this fundamental limit, see e.g. @MosselNS15 [@DBLP:journals/corr/Massoulie13; @Mossel2018APO; @Abbe2020GraphPA]. A key result is the following theorem. \[KS\]\[Kesten-Stigum threshold\] Let $\operatorname{\mathcal{G}}(n, a/n, b/n)$ be a symmetric SBM with two balanced clusters and $a, b = O(1)$. The weak recovery problem is solvable and efficiently so if and only if $(a-b)^2 > 2(a + b)$. In particular, if we denote the probability measures induced by the ERM $\operatorname{\mathcal{G}}(n, \frac{a+b}{2n}, \frac{a+b}{2n})$ and the SBM $\operatorname{\mathcal{G}}(n, \frac{a}{n}, \frac{b}{n})$ by $P_n^{(0)}$ and $P_n^{(1)}$ correspondingly, they are mutually contiguous, that is for any sequence of events $\{E_n\}$'s, $P_n^{(0)}(E_n) \to 0$ if, and only if, $P_n^{(1)}(E_n) \to 0$. Conventionally, the quantity $(a-b)^2/[2(a+b)]$ is called signal-to-noise ratio (SNR). It is worth noting that we only quoted the KS threshold for the two communities case ($k = 2$). For sufficiently large $k$, namely $k \geq 5$, there is a 'hard but detectable' area where the weak recovery is information-theoretically possible, but computationally hard @ASgen [@Banks2016InformationtheoreticTF]. This gap between the KS threshold and information-theoretic (IT) threshold only shows up in the constant degree regime, making it a fertile ground for studying the fundamental tradeoffs in community detection. We focus on the cardinal case, symmetric SBM with two balanced clusters, where two thresholds coincide and semi-supervised approach crosses them together. <span>0.3</span> ![The left image represents the adjacency matrix of one realization of $\operatorname{\mathcal{G}}(100, 0.12, 0.05)$, where the detection is theoretically possible. Yet the data is given non-colored (middle) and also non-ordered (right).](sbm_plt_nice.png "fig:"){width="\textwidth"} <span>0.3</span> ![The left image represents the adjacency matrix of one realization of $\operatorname{\mathcal{G}}(100, 0.12, 0.05)$, where the detection is theoretically possible. Yet the data is given non-colored (middle) and also non-ordered (right).](sbm_plt_uncolor.png "fig:"){width="\textwidth"} <span>0.3</span> ![The left image represents the adjacency matrix of one realization of $\operatorname{\mathcal{G}}(100, 0.12, 0.05)$, where the detection is theoretically possible. Yet the data is given non-colored (middle) and also non-ordered (right).](sbm_plt_unorder.png "fig:"){width="\textwidth"} The terminology 'KS threshold' can be traced back to the work of Kesten and Stigum concerning reconstruction on infinite rooted trees in 1966 @KS. The problem consists in broadcasting the root label of a tree with fixed degree $c$ down to its leaves, and trying to recover it from the leaves at large depth. We start with drawing the root label uniformly in $\{0,1\}$. Then, in a top-down manner, we independently label every child the same as its parent with probability $1-\epsilon$ and the opposite as its parent otherwise. Let $x^{(t)}$ denote the labels at depth $t$ in this tree with $t = 0$ being the root. We say the reconstruction is solvable if $\lim_{t\to \infty} \operatorname{E}|\operatorname{E}(x^{(0)}|x^{(t)}) - 1/2| > 0$ or, equivalently, $\lim_{t\to\infty} I(x^{(0)}; x^{(t)}) > 0$, where $I$ is the mutual information. Although it was shown in the original paper, reconstruction is solvable when $c(1-2\epsilon)^2 > 1$, the non-reconstruction was proved 30 years later, namely it is not solvable if $c(1-2\epsilon)^2 \leq 1$ @Bleher1995OnTP [@Evans]. Based on that finding, Mossel, Neeman, and Sly proved the converse part of Theorem \[KS\] by coupling the local neighborhood of an SBM vertex with a Gaton-Watson tree with a Markov Process @MosselNS15. Inspired by this elegant approach, we propose our 'census method' to solve the semi-supervised clustering problem, and we will see in Section \[Census method\] how it works by amplifying revealed information with tree-like neighborhoods. Basic algorithms ---------------- Information-theoretic bounds can provide the impossibility side of phase transitions, but we still need specific efficient algorithms for the achievability side. One straight forward approach is spectral method. Under the Definition \[PBM\], let $A$ be the adjacency matrix of the graph $G \sim \operatorname{\mathcal{G}}(n,a/n,b/n)$, $a>b$. Up to reordering indices, its expectation is a block matrix except for the diagonal, $$\operatorname{E}A \approx \frac{1}{n} \begin{pmatrix} a & b\\ b & a \end{pmatrix}\otimes I_{n/2 \times n/2}$$ which has three eigenvalues, $(a+b)/n > (a-b)/n>0$. $0$ has multiplicity $n-2$ and the eigenvector associated with the second largest eigenvalue is $({\mathbf{1}}^\top_{n/2},-{\mathbf{1}}^\top_{n/2})$ which is consistent with the ground truth of the labels. But we do not observe the expected adjacency matrix. Instead, we only have access to one realization of the model. In modern terms, community detection is a 'one-shot learning' task. But one can still hope that $A - \operatorname{E}A$ is small and the second eigenvector of $A$ gives a reasonable estimator. For example, denoting the ordered eigenvalues of $\operatorname{E}A$ and $A$ as $\{\lambda_i\}$'s and $\{\hat{\lambda}_i\}$'s respectively, the Courant-Fischer-Weyl min-max principle implies $$|\hat{\lambda}_i - \lambda_i | \leq \|A - \operatorname{E}A\|_{\text{op}}, \qquad i = 1,\dots,n.$$ Recall that the operator norm of a symmetric matrix $M$, with $\xi_i(M)$ being its $i$-th largest eigenvalue, is $\|M\|_{\text{op}} = \max(\xi_1(M), -\xi_n(M))$. If one can bound $\|A - \operatorname{E}A\|_{\text{op}}$ by half of the least gap between the three eigenvalues mentioned above, the order will be preserved. Then the Davis-Kahan theorem guarantees the eigenvectors are correlated. Namely, if $\theta$ denotes the angle between the second eigenvectors (spectral estimator and ground truth), we have $$\sin \theta \leq \|A - \operatorname{E}A\|_{\text{op}}/ \min\{\|\lambda_i - \lambda_2\|/2 : i\neq 2\}.$$ Thus, the key is to control the norm of the perturbation. Many deep results from random matrix theory come into play here @Vu2007SpectralNO [@Nadakuditi2012GraphSA; @Abbe2020ENTRYWISEEA]. This nice and simple approach stops working as we step into the sparse regime @Feige2005SpectralTA [@CojaOghlan2009GraphPV; @Keshavan2009MatrixCF; @Decelle2011AsymptoticAO; @Krzakala2013SpectralRI]. The main reason is that leading eigenvalues of $A$ are about the order of square root of the maximum degree. High degree vertices mess up the desired order of eigenvalues. In particular, for Erdős–Rényi random graphs ($\operatorname{\mathcal{G}}(n, d/n)$), we have $\hat{\lambda}_1 = (1+o(1))\sqrt{\log n / \log \log n}$ almost surely @Krivelevich2003TheLE. Furthermore, the leading eigenvectors are concentrated at these high degree 'outliers' and contain no structural information of the underlying model. Take the star graph for example, where we assume that only the first node is connected to $k$ neighbors. It is easy to see that the corresponding adjacency matrix has eigenvalue $\sqrt{k}$ and eigenvector $(\sqrt{k},1,\dots,1)$. Various interesting spectrum based methods are proposed to overcome this challenge @Mossel2018APO [@Massouli2014CommunityDT; @Bordenave2015NonbacktrackingSO]. The key idea is to replace adjacency with some combinatorically constructed matrices. However, they typically rely on model statistics and underlying probabilistic assumptions, which leads to the problem of adversarial robustness. For example, they are non-robust to 'helpful' perturbations. Namely, if we let an adversary to perform following changes on the graph: (1) adding edges within communities and/or (2) removing edges across communities, spectral approaches are going to fail. It is surprising since, intuitively, these changes help to emphasize community structures. Meanwhile, semidefinite programming (SDP) sheds the light on how we may be able to overcome the limitations of spectral algorithms, which is shown to be robust when SNR is sufficiently large @Moitra2016HowRA. In fact, it is another major line of work on clustering and community detection concerning performance of SDPs on SBMs. While a clear picture of the unbounded degree case is figured out in @Abbe2016ExactRI [@Hajek2016AchievingEC; @Amini2014OnSR; @Bandeira2018RandomLM; @Agarwal2015MultisectionIT; @Perry2017ASP], the results for sparse networks are more complicated. @Gudon2014CommunityDI proved a sub-optimal condition, SNR $\geq10^4$, using Grothendieck inequality. Then, with a Lindeberg interpolation process @TTao, Montanari et al. proved that SDP is nearly optimal for large bounded average degree by transferring analysis of the original SDPs to the analysis of SDPs of Gaussian random matrices. @montanari2015semidefinite Assume $G \sim G(n,a/n,b/n)$. If for some $\epsilon > 0$, $\text{SNR}\geq 1+\epsilon$ and $d>d^*(\epsilon)$ then the SDP estimator solves the weak recovery. If we fix $d$ and view $\epsilon$ as its function, the condition becomes $\text{SNR} \geq 1 +o_d(1)$. Numerical estimation and non-rigorous statistical mechanism approximation suggest that it is at most $2\%$ sub-optimal. This result seems to be the ceiling of SDP according to the preliminary non-rigorous calculation in @Javanmard2016PhaseTI. Moreover, they address the irregularity of high degree nodes by showing SDPs return similar results for Erdős–Rényi random graphs and random regular graphs, which appear to be sensitive only to the average degree. See Section \[CSDP\] for more discussion on the estimation. Following their work, we propose a natural modification of SDP to incorporate revealed labels in the semi-supervised setting and show that it not only achieves, but also crosses, the KS threshold. In turn, our result brings a new perspective to study the (non-)achievability and robustness of (unsupervised) SDPs. Semi-supervised learning ------------------------ Within machine learning there are three basic approaches: supervised learning, unsupervised learning and the combination of both, semi-supervised learning. The main difference lies in the availability of labeled data. While unsupervised learning (e.g. clustering, association and dimension reduction) operates without any domain-specific guidance or preexisting knowledge, supervised learning (e.g. classification and regression) relies on all training samples being associated with labels. However, it is often the case where existing knowledge for a problem domain doesn't fit either of these extremes. In real-world applications, unlabeled data comes with a much lower cost not requiring expensive human annotation and laboratory experiments. For example, documents crawled from the Web, images obtained from surveillance cameras, and speech collected from broadcast are relatively more accessible comparing to their labels which are required for prediction tasks, such as sentiment orientation, intrusion detection, and phonetic transcript. Motivated by this labeling bottleneck, the semi-supervised approach utilizes both labeled and unlabeled data to perform learning tasks faster, better, and cheaper. Since the 1990s, semi-supervised learning research has enjoyed an explosion of interest with applications like natural language processing @Qiu2019GraphBasedSL [@Chen2016StatisticalComputationalTI] and computer vision @Xie2020SelfTrainingWN [@Lee2013PseudoLabelT]. This paper is closely related to the subtopic called constrained clustering, where one has some must-links (i.e. two nodes belong to the same cluster) and cannot-links (i.e. two nodes are in different clusters) as extra information. Although constrained versions of classic algorithms have been studied empirically, such as expectation–maximization @Shental2003ComputingGM, k-means @Wagstaff2001ConstrainedKC and spectral method @Kamvar2003SpectralL, our methods take different approaches to enhance clustering outcomes instead of hard-coding these pairwise constraints into the algorithms and provide theoretically guarantees under SBM. 0 A recent development in semi-supervised learning that has attracted extensive attention is called graph convolutional network (GCN) @Kipf2017SemiSupervisedCW, which is based on an efficient variant of convolutional neural networks operating on graph structures directly. The objective functions of GCNs only involve labeled data while predictive information propagates through the graphs built in neural networks to cover unlabeled data. The benefit of integrating graph structures into deep learning approaches is twofold: (i) it efficiently embeds similarity between nodes to synchronize labeled and unlabeled samples; (ii) it significantly brings down the number of parameters by only considering the connections induced by underlying graphs. A prototypical example of a forward model of a two-layer GCN for semi-supervised node classification on a graph is given by $$\label{GCN} f(Z, A) = \text{softmax}\left( \hat{A}~ \text{ReLU} \left( \hat{A}Z W^{(0)}\right)~W^{(1)}\right)$$ where $W^{(i)},~ i \in \{0,1\}$ are weight matrices for the hidden layer and the output layer, softmax and Relu are both vector activation functions defined as $\text{softmax}(x) = \exp(x)/\sum_i \exp(x_i)$ and $\text{ReLU}(x) = \max(0,x)$. $Z$ stands for the features and $A$ is the adjacency matrix. The output of each layer of GCN goes through a smoothing process defined by the *propagation model matrix* $\hat{A}$. It can be a normalized adjacency matrix, a graph Laplacian, or even the identity matrix, which reduces the model to multi-layer perception. Existing frameworks are either directly based on the adjacency matrix $A$ @Ying2018GraphCN or run basic clustering algorithms on $A$ @Chiang2019ClusterGCNAE to design $\hat{A}$. But whenever GCN is applicable, some of the labels are always available. It is natural to consider making use of this label information to improve the decisive component $\hat{A}$, which can be realized directly from our semi-supervised clustering algorithms. We will discuss this interesting application further in Section \[conclusion\]. Our results {#summary} =========== The main goal of this paper is to answer the long-standing open question regarding the semi-supervised learning on probabilistic graph models. We would like to quote the version from @Abbe2017CommunityDA: > "How do the fundamental limits change in a semi-supervised setting, i.e., when some of the vertex labels are revealed, exactly or probabilistically?" In the previous section, we have discussed deep research related to the clustering/community detection problem on the SBM. Establishing the phase transition phenomenon at KS threshold is a major focal point. However, such a sharp and intrinsic limit totally disappears when an arbitrarily small fraction of the labels is revealed. This astonishing change is first observed in @PhysRevE.90.052802 where the authors provide non-trivial conjectures based on calculations of the belief propagation approach. The theory of semi-supervised clustering contains some fascinating and fundamental algorithmic challenges arising from both the sparse random graph model itself and the semi-supervised learning perspective. To address them rigorously, we first define the semi-supervised SBM in a way that it captures the essence of realistic semi-supervised learning scenarios and is a natural and simple generalization of unsupervised models. \[Semi-supervised planted bisection model\]\[SPBM\] For $n\in \mathbb{N}$, $p,q \in (0,1)$ and $\rho \geq 0$, let $\operatorname{\mathcal{G}}(n,p,q,\rho)$ denote the distribution over graphs with $n$ vertices and $n$-dimensional vectors defined as follows. The vertex set is partitioned uniformly at random into two subsets $S_1, S_2$ under the balance constraint $|S_1|=|S_2| = n/2$. Then conditional on the partition, two processes are undertaken independently: - Let $E$ denote the edge set of the graph $G$. Edges are included independently with probability defined as follows. $$\operatorname{P}\left((i,j)\in E | S_1, S_2\right)= \begin{cases} p & \text{~if~} \{i,j\} \subseteq S_1 \text{~or~} \{i,j\} \subseteq S_2, \\ q & \text{~if~} i \in S_1, j \in S_2 \text{~or~} i \in S_2, j \in S_1. \end{cases}$$ - An index set $\mathcal{R}$ of size $m \coloneqq 2\lfloor \rho \cdot \frac{n}{2} \rfloor$ is chosen uniformly at random such that $|\mathcal{R} \cap S_1| = |\mathcal{R} \cap S_2| = m/2$. The revealed labels are given as $$\Tilde{x}_i=\begin{cases} ~1, \quad &i \in \mathcal{R} \cap S_1,\\ -1, \quad &i \in \mathcal{R} \cap S_2,\\ ~0, \quad &\text{otherwise.} \end{cases}$$ The revealing process is independent from edge formation, i.e. $G \perp \tilde{x}|S_1,S_2$. Moreover, if we set $\rho = 0$ or simply ignore the revealed labels, the model is exactly the unsupervised SBM. In other words, the marginal distribution of the random graph is indeed $\operatorname{\mathcal{G}}(n,p,q)$ from Definition \[PBM\]. One can also consider revealing uniformly at random over the index set independent of $\operatorname{\mathcal{G}}(n,p,q)$ (instead of requiring revealed communities to have the same size), but this modification makes almost no difference in the context of this work. In practice, one can always achieve the balance requirement by either sampling a few more or dropping the uneven part. The definition is versatile in the sense that it keeps unsupervised setting as a special case (and with it all the interesting phase transitions). On the other hand, it can be easily generalized to the multiple and/or asymmetric communities case. Under semi-supervised setting, the weak recovery problem is naturally defined as finding an estimator to perform substantially better than chance *on the unrevealed vertices*. And the distinguishability can be expressed as finding a test that with high probability, tells $\operatorname{\mathcal{G}}(n,d/n,d/n,\rho)$ from $\operatorname{\mathcal{G}}(n,a/n,b/n,\rho)$ where $d=\frac{a+b}{2}, a>b$. We will discussion these items in more detail when it comes to the corresponding section. Based on the fact that a $\ln (n)$-neighborhood in $(G,x) \sim \operatorname{\mathcal{G}}(n,a/n,b/n)$ asymptotically has the identical distribution as a Galton-Watson tree with Markov process, we propose our first semi-supervised clustering algorithm, called *census method*. Namely, we decide the label estimation of a certain node according to the majority of its revealed neighbors, $$\hat{x}_v = \text{sgn}\left( \sum_{i \in \{u \in \mathcal{R}:~ d(u,v)=t\}} x_i \right)$$ where $d(u, v)$ is the length of the shortest path connecting $u$ and $v$. We conclude that when $\text{SNR} \leq 1$, the optimal choice of $t$ is indeed 1. \[thm:census\] The 1-neighbors census method solves the semi-supervised weak recovery problem with any reveal ratio $\rho>0$ for arbitrary $\text{SNR} >0$. Although this successfully solves the weak recovery problem, there are some limitations hindering the census method's utility in practice. Its performance depends on a sufficient amount of revealed labels, hence requiring $n$ to be really large. Besides, without an unsupervised counterpart, it is not applicable when the revealing is not reliable. To address these challenges, we propose our second semi-supervised clustering algorithm which performs well in practice and covers the unsupervised setting as special case. As discussed in the previous section, SDPs enjoy many nice properties, among which the monotone-robustness is particularly interesting to us. In the semi-supervised setting, the revealed labels are supposed to enhance the community structure. However, the work from @Moitra2016HowRA suggests such enhancement may not help with, but to the contrary can hurt the performance of many algorithms, which makes SDP an ideal starting point for us. We define the *Constrained Semidefinite Program* (CSDP) as $${\text{CSDP}}(M) = \max_{\substack{X \succeq 0 \\ X_{ii}=1, ~\forall i \in [n]}}\{{\langle}M,X{\rangle}:~ X_{ij} = x_i \cdot x_j, ~\forall i,j \in \mathcal{R}\}$$ and show that it solves the semi-supervised community detection problem. \[thm:CSDP\] Let $(G,x_\mathcal{R})\sim \operatorname{\mathcal{G}}(n,a/n,b/n,\rho)$ and $A$ be the adjacency matrix associated with $G$. For any $a > b$, there exists $\rho_0 < 1$ such that if $\rho \geq \rho_0$, the CSDP-based test $T(G, x_\mathcal{R};\Delta) = \mathbbm{1}_{\{{\text{CSDP}}(A - \frac{d}{n} \mathbf{1}\mathbf{1}^\top) \geq n[(a-b)/2 - \Delta]\}}$ will succeed with high probability for some $\Delta > 0$. Proof techniques ---------------- The technical challenges of establishing Theorem \[thm:census\] are mainly due to the fact that the advantage created by revealed labels can be easily blurred out by various approximations of the limit distribution. Instead of the central limit theorem, one needs a Berry–Esseen-type inequality to derive a more quantitative result of the convergence rate. Moreover, since the distribution of each underlying component also depends on $n$, the conventional sample mean formulation does not apply here. We overcome the difficulty above with a direct analysis of non-asymptotic distributions, which leads to a detailed comparison between two binomial variables with constant expectations. It is quite surprising that this calculation can be carried out in rather elegant manner, since many other applications of this method are much more technically involved. For example to establish the independence among estimators, one may need to consider the 'leave-one-out' trick. But in our case, it comes in a very natural way. Regarding CSDP, we first show it can be coupled to a SDP with the surrogate input matrices. Moreover, its optimal value lies in between two unsupervised SDPs associated with the same random graph model (different parameters). This means all the analytical results from SDP research can be transferred into the CSDP study. However, we notice that it is common to make assumptions on the average degree $d$ in the relevant literature. It is quite reasonable in the unsupervised setting since the graph topology is a strong indicator for the possibility of weak recovery, e.g. when $d\leq1$, there will not exist a giant component that is of size linear in $n$. To establish our result without such extra assumptions, we derive a probabilistic bound on the cut norm of centered adjacency matrix and then use Grothendieck's inequality to bound the SDP on ERMs from above. This idea follows from @Gudon2014CommunityDI; we give a slightly different analysis fitting for our purpose. A generalized weak law of large number is also derived to address the issue that distributions of the entries change as $n\to \infty$. Then we conclude the proof with a lower bound of the CSDP on SBMs considering a witness that consists of the ground truth of labels. Outline ------- The rest of the paper is organized in the following way. In Section \[Census method\], we formally derive the census method and prove that it can solve the weak recovery problem throughout the entire parameter domain. In section \[CSDP\], we introduce the constrained SDP and the associated hypothesis test, through which we show that even under the KS threshold (also the information-theoretic threshold), the ERMs and the SBMs become distinguishable in the semi-supervised setting. Section \[numexp\] includes some numerical simulation results. We end the paper with concluding remarks in Section \[conclusion\]. Notation -------- For any $n\in\mathbb{N}$, we denote the first $n$ integers by $[n] = \{1,2,\dots,n\}$. For a set $S$, its cardinality is denoted by $|S|$. We use lowercase letters for vectors (e.g. $v = (v_1,v_2,\dots,v_n)$) and uppercase letters for matrices (e.g. $M = [M_{ij}]_{i,j\in[n]}$). In particular, for adjacency matrices, we omit their dependency on underlying graphs. Instead of $A_G$, we simply write $A$. ${\mathbf{1}}_n = (1,\dots,1) \in \mathbb{R}^n$ stands for the all-ones vector and $I_n$ is the $n\times n$ identity matrix. $\mathbf{e}_i \in \mathbb{R}_n$ represents the $i$'s standard basis vector. For two real-valued matrices $A$ and $B$ with the same dimensions, we define the Frobenius inner product as ${\langle}A, B {\rangle}= \sum_{i,j}A_{ij}\cdot B_{ij} = \operatorname{Tr}(A^\top B)$. Vector inner product is viewed as a special case of $n\times 1$ matrices. Let $\|v\|_p = (\sum_{i=1}^p \|v_i\|^p)^{1/p}$ be the $\ell_p$ norm of vectors with standard extension to $p = \infty$. Let $\|M\|_{p\to q} = \sup_{\|v\|p \leq 1} \|Mv\|_q $ be the $\ell_p$-to-$\ell_q$ operator norm and $\|M\|_{\text{op}} \coloneqq \|M\|_2 \coloneqq \|M\|_{2\to 2}$. Random graphs induce measures on the product space of label, edge and revealed node assignments over $n$ vertices. For any $n\in \mathbb{N}$, it is implicitly understood that one such measure is specified with that graph size. The terminology *with high probability* means 'with probability converging to $1$ as $n \to \infty$'. Also, we follow the conventional Big-Oh notation for asymptotic analysis. Census method {#Census method} ============= Analysis of Model \[PBM\] is a challenging task since conditioned on the graph, it is neither an Ising model, nor a Markov random field. This is mainly due to following facts: (1) The balance requirement puts a global condition on the size of each cluster; (2) Even if conditioned on sizes, there is a slight repulsion between unconnected nodes. Namely, if two nodes do not form an edge, the probability of them being in the same community is different from them being in the opposite communities. Recent years have witnessed a series of excellent contributions on the phase transitions in the sparse regime. Our census method for semi-supervised clustering is mainly inspired by the natural connection between community detection on SBMs and reconstruction on trees, which is formally established in @MosselNS15. Intuitively, for a vertex $v$ in $\operatorname{\mathcal{G}}(n,a/n,b/n)$, it is not likely that a node from its small neighborhood has an edge leading back to $v$. Therefore, the neighborhood looks like a random labelled tree with high probability. Furthermore, the labelling on the vertices behaves like the broadcasting a bit from the root of a tree down to its leaves (see the survey @Mossel2001SurveyIF for a detailed discussion). In this section, we will first look into the census method of $t$-neighbors, i.e., deciding the label of a node by the majority on its neighbors at depth $t$. We shall see that when $\text{SNR}\leq 1$, $1$-neighbors voting is optimal in terms of recovering the cluster structure via informal calculation. Then we rigorously prove that census on $1$-neighbors solves the semi-supervised weak recovery problem for any $\text{SNR}>0$ with an arbitrarily small fraction of labels revealed. Majority of t-neighbors ----------------------- Let $(G,x)$ obey the planted bisection model $\operatorname{\mathcal{G}}(n,a/n,b/n)$. We denote the set of all vertices by $V(G)$. For a fixed vertex $v$ and $t\in\mathbb{N}$, let $N_t(v)$ denote the number of vertices which are $t$ edges away from $v$. $\Delta_t(v)$ is defined as the difference between the numbers of $t$-neighbors in each community. Namely, $$\begin{aligned} N_t(v) &= |K_t(v)| \\ \Delta_t(v) &= \sum_{u \in K_t(v)} x_{u} \end{aligned}$$ where $K_t(v)\coloneqq\{u \in V(G):~ d(u,v)=t\}$ denotes the $t$-neighbors of $v$. If one assume that the subgraph of $G$ induced by the vertices within $t$ edges of $v$ is a tree, the expected value of $N_t(v)$ is approximately $[(a+b)/2]^t$ and the expected value of $x_v \cdot \Delta_t(v)$, i.e., the expected number of these vertices in the same community as $v$ minus the expected number of these vertices in the other community, is approximately $[(a-b)/2]^t$. So, if one can somehow independently determine which community a vertex is in with an accuracy of $1/2 + \alpha$ for some $\alpha > 0$, one will be able to predict the label of each vertex with an accuracy of roughly $1/2 + [(a-b)^2/(2(a+b))]^{t/2}\cdot\alpha$, by guessing it as the majority of $v$'s $t$-neighbors. Under the unsupervised learning setting, one can get a small advantage, $\alpha \sim \Theta(1/\sqrt{n})$, by randomly initializing labels. It is guaranteed by the central limit theorem that such a fraction exists in either an agreement or disagreement form. ![Neighborhood of node $v$ with a tree structure. True clusters are coded in black and white. The shaded area indicates those nodes randomly guessed to be in the same community or the opposite community as $v$. The annulus represents the collection of its $t$-neighbors.<span data-label="fig:census"></span>](census.png){width="80.00000%"} To amplify this lucky guess, we need $t$ to be sufficiently large so that $[(a-b)^2/(2(a+b))]^{t/2} > \sqrt{n}$, which implies $[(a+b)/2]^t>n$. Note $d = (a+b)/2$ is the average degree. This means before the signal is strong enough for our purpose, not only our tree approximation will break down, but vertices will be exhausted. However, if we have access to some of the true labels, i.e., in the semi-supervised setting, we can leverage the tree structure for a non-vanishing advantage over random guessing. Let $A$ be the adjacency matrix associated with $G$. Consider the random variables $Y_u$ representing votes of directly connected neighbors, $$Y_u = \begin{cases} x_{u} &\text{if~} A_{uv} = 1 \\ 0 &\text{otherwise} \end{cases}$$ We have $$\begin{aligned} N_1(v) &= \sum_{u \in V(G)} |Y_u| \\ \Delta_1(v) &= \sum_{u \in V(G)} Y_u\end{aligned}$$ By definition of the planted bisection model, $$\operatorname{P}(Y_u=1 | x_v=1) = \frac{\operatorname{P}(Y_u=1, x_v=1)}{\operatorname{P}(x_v=1)} \approx \frac{a}{2n}$$ Similarly, $$\operatorname{P}(Y_u=-1 | x_v=1) \approx \frac{b}{2n}$$ It is not exact due to the balanced community constraint. But when $n$ is large, such an effect is negligible. Furthermore, if we consider the definition of the planted bisection model without balance constraint, the equation will be exact. Without loss of generality, we only consider the case where $x_v = 1$ and omit the condition on it. We have $$\Delta_1(v)=\sum_{u \in V(G)} Y_u \qquad\text{with~~} Y_u = \begin{cases} 1 & \text{w.p.~} \frac{a}{2n}\\ -1 & \text{w.p.~} \frac{b}{2n}\\ 0 & \text{w.p.~} 1-\frac{a+b}{2n} \end{cases}$$ where the $Y_u$'s are independent. Note that $\operatorname{E}(Y_u) = \frac{a-b}{2n}$ and $\operatorname{E}(Y_u^2) = \frac{a+b}{2n}$. Recall that $\rho \in [0,1]$ is the ratio of revealed labels. For the sake of simplicity, we assume the total number of revealed vertices $m = \rho n \in 2\mathbb{N}$ to be an even integer. The revealed vertices are chosen arbitrarily, denoted as $\mathcal{R} \coloneqq \{u_1,u_2,\dots,u_{n-m}\}$. The model also provides that the number of revealed vertices in each community is $\frac{\rho n}{2}$. Then the majority of revealed vertices among 1-neighborhood of $v$ can be written as $$\Tilde{\Delta}_1(v)=\sum_{u \in \mathcal{R}} Y_u$$ Therefore, $$\begin{aligned} &\operatorname{E}(\Tilde{\Delta}_1(v)) = \sum_{u\in \mathcal{R}} \operatorname{E}(Y_u) = \rho \frac{a-b}{2}\\ &\operatorname{Var}(\Tilde{\Delta}_1(v)) = \sum_{u\in \mathcal{R}} \operatorname{Var}(Y_u) = \rho \frac{a+b}{2}\\\end{aligned}$$ Locally tree-like structure --------------------------- Proceeding to the $t$-neighbors, we need to understand a bit better the structure of a small neighborhood in the SBM. The neighborhoods in a sparse network locally have no loops. So they have a nice tree-like structure. Moreover, the labels also obey some random broadcasting processes on trees. A broadcasting process transmit the information from the root of a tree to all the nodes. At each level, nodes inherit the information from its parent. But error could happen with certain amount of probability. Usually the edges are assumed to be identical and work independently. It was firstly considered in genetics @CAVENDER1978271 since it perfectly describes the propagation of a gene from ancestor to descendants. It can also be interpreted as a communication network that pass out the information from the root. So such processes were intensively studied in information theory and statistical physics @10.2307/2959462 [@Higuchi1977RemarksOT; @Bleher1995OnTP]. In particular, we are interested in the following Markov process since it can be identified with the labeling process of a small neighborhood in SBM. \[Galton–Watson tree with Markov process\] Let $T$ be an infinite rooted tree with root $v$. Given a number $0\leq\epsilon<1$ and the offspring rate $d>0$, we define a random labelling $\tau \in \{1,-1\}^T$. First, draw $\tau_v$ uniformly in $\{1,-1\}$. Then recursively construct the labelling as follows. - Generate children of each parent node according to a Poisson distribution with mean $d$. - Conditionally independently given $\tau_v$, for every child $u$ of $v$, set $\tau_u=\tau_v$ with probability $1-\epsilon$ and $\tau_u=-\tau_v$ otherwise. The following lemma shows that a $\ln (n)$-neighborhood in $(G,x)$ looks like a Galton-Watson tree with Markov process. For any $v \in G$, let $G_R$ be the induced subgraph on $\{u \in G : d(u, v) \leq R\}$. @MosselNS15 Let $R = R(n) = \frac{\ln n}{10\ln(2(a+b))}$. There exists a coupling between $(G, x)$ and $(T, \tau)$ such that $(G_R, x_{G_R} )$ = $(T_R, \tau_{T_R})$ a.a.s. Hence, for fixed $t \in \mathbb{N}$, $t \leq R$ and any $v \not\in \mathcal{R}$, we can denote the label of a vertex in $v$'s $t$-neighborhood as $Y_i^{(t)} \coloneqq \Pi_{k=1}^t \prescript{k}{}{Y_u}$, where $\{\prescript{k}{}{Y_u}\}_{k=1}^t$ are independent copies of $Y_u$. Then we have $\operatorname{E}(Y_i^{(t)}) = (\frac{a-b}{2n})^t$ and $\operatorname{E}((Y_i^{(t)})^2) = (\frac{a+b}{2n})^t$. Moreover, $\{Y_i^{(t)}\}$'s are independent. Therefore, the census of $v$'s revealed $t$-neighbors can be written as $$\Tilde{\Delta}_t(v)=\sum_{i \in [\rho \cdot n^t]} Y_i^{(t)} \quad \textit{a.a.s}$$ The central limit theorem suggests $$\Tilde{\Delta}_t(v) \to \mathcal{N}(\rho(\frac{a-b}{2})^t, \rho(\frac{a+b}{2})^t) \qquad \text{as~} n \to \infty$$ Hence, $$\begin{aligned} \operatorname{P}(\Tilde{\Delta}_t(v) >0 | x_v=1) &= \frac{1}{2}\left[1 + \text{erf}\left(\frac{\rho[(a-b)/2]^t}{\sqrt{\rho[(a+b)/2]^t}\sqrt{2}}\right)\right] + o(1)\\ &= \frac{1}{2}+ \frac{1}{2}\text{erf}\left(\sqrt{\frac{\rho~\text{SNR}^t}{2}}\right) + o(1)\end{aligned}$$ where $\text{erf}(x) = \frac{2}{\sqrt{\pi}} \int_0^x \exp(-t^2) \dif{t} $ is the Gauss error function. So one can see that once SNR is less than or equal to $1$, it is not beneficial to look into $t$-neighbors. The optimal choice of $t$ is $1$ in this situation. Since we also know that weak recovery is solvable when $\text{SNR}>1$, it makes the majority of $1$-neighbors particularly interesting. Suppose $\text{SNR}\leq 1$ and include the symmetric part of $x_v=-1$, we have $$\operatorname{P}(\text{sgn}(\Tilde{\Delta}_1(v)) = x_v)> \frac{1}{2} + \frac{1}{3}\sqrt{\rho~\text{SNR}}$$ Consider the estimator of unrevealed labels $$\hat{x}_{\mathcal{R}^\complement}\coloneqq \text{sgn}\left([\Tilde{\Delta}_1(u_1), \Tilde{\Delta}_1(u_2), \dots, \Tilde{\Delta}_1(u_{n-m})]^\top\right)$$ and the ground truth $x_{\mathcal{R}^\complement}=[x_{u_1},x_{u_2},\dots,x_{u_{n-m}}]^\top$. Recall that $$\text{Overlap}(x_{\mathcal{R}^\complement},\hat{x}_{\mathcal{R}^\complement})=\frac{1}{n-m}| \langle x_{\mathcal{R}^\complement},\hat{x}_{\mathcal{R}^\complement} \rangle |$$ We can conclude that $$\begin{aligned} \operatorname{E}[\text{Overlap}(x_{\mathcal{R}^\complement},\hat{x}_{\mathcal{R}^\complement})] &= \operatorname{E}\left[\frac{1}{n-m} \left|\sum_{i\in[n-m]}\text{sgn}(\Tilde{\Delta}_1(u_i))x_{u_i}\right|\right]\\ &\geq \frac{1}{n-m}\left|\sum_{i\in[n-m]} \operatorname{E}\left[\text{sgn}(\Tilde{\Delta}_1(u_i))x_{u_i}\right]\right|\\ &> \frac{2}{3}\sqrt{\rho~\text{SNR}}\end{aligned}$$ The expected overlap is not vanishing which suggests the weak recovery is solvable for any SNR. But it is technically impractical to rigorously describe the limit distribution of our census estimator without blurring this edge out. From Figure \[fig:rho\_overlap\], we can see that our calculation is close to the expectation. But the convergence rate depends on $\rho$. In particular, when both SNR and $\rho$ are small, the asymptotic behavior of our algorithm remains unclear. Hence we go through a direct analysis to establish the desired result. ![The simulation result of $\operatorname{\mathcal{G}}(3000, 5/3000, 2/3000)$, $\text{SNR}\approx0.64$. Horizontal coordinate is the ratio of revealed labels. The blue curve stands for the average overlap of 60 independent realizations of the random graph with the shaded area being its standard error band. The purple dashed curve stands for the asymptotic lower bound we conclude from our calculation.<span data-label="fig:rho_overlap"></span>](census_std.png){width="\textwidth"} Majority of 1-neighbors ----------------------- Since the algorithm is invariant under index reordering, without loss of generality, we let the adjacency matrix $A$ be a symmetric matrix with diagonal entries $A_{ii}=0,~ i=1,2, \dots, n$. For $1 \leq i < j \leq n$, $\{A_{ij}\}$'s are independent, $$\begin{aligned} &A_{ij} \sim \text{Bernoulli}\left(\frac{a}{n}\right) &\quad \left(i\leq \frac{n}{2} ~\text{and}~ j \leq \frac{n}{2} \right) &~\text{or}~ \left(i\geq \frac{n}{2} ~\text{and}~ j \geq \frac{n}{2} \right)\\ &A_{ij} \sim \text{Bernoulli}\left(\frac{b}{n}\right) &\quad i\geq \frac{n}{2} ~&\text{and}~ j \leq \frac{n}{2}\end{aligned}$$ The true label $x$ and revealed label $\Tilde{x}$ are, respectively, $$x_i=\begin{cases} 1, \quad &i=1,2,\dots,\frac{n}{2},\\ -1, \quad &i=\frac{n}{2},\frac{n}{2}+1,\dots,n, \end{cases} \quad \Tilde{x}_i=\begin{cases} 1, \quad &i=1,2,\dots,\frac{m}{2},\\ -1, \quad &i=\frac{n}{2},\frac{n}{2}+1,\dots,\frac{n+m}{2},\\ 0, \quad &\text{otherwise.} \end{cases}$$ For a unrevealed vertex, we consider the majority of its 1-neighbors, $$\Tilde{\Delta}_1(i) = \langle A[i,:],\Tilde{x} \rangle = \sum_{j:\Tilde{x}_j \neq 0} A_{ij}\Tilde{x}_j = \sum_{j:\Tilde{x}_j \neq 0} A_{ji}\Tilde{x}_j$$ Therefore, $\{\Tilde{\Delta}_1(i)\}$'s are independent for all $i:\Tilde{x}_i = 0$ since they have no common term. Notice it is not the case for all $i \in [n]$. But we only need to predict the unrevealed labels, hence the independence. The estimator given by majority voting of 1-neighbors is $$\hat{x}_i = \begin{cases} \Tilde{x}_i \quad &\text{if}~\Tilde{x}_i \neq 0\\ \text{sgn}^*(\Tilde{\Delta}_1(i)) \quad &\text{if}~\Tilde{x}_i = 0 \end{cases}$$ We toss a fair coin when $\Tilde{\Delta}_1(i)=0$ to break the tie, i.e. $$\operatorname{P}(\text{sgn}^*(\Tilde{\Delta}_1(i))=1|\Tilde{\Delta}_1(i)=0) = \operatorname{P}(\text{sgn}^*(\Tilde{\Delta}_1(i))=-1|\Tilde{\Delta}_1(i)=0) = \frac{1}{2}$$ Notice that it is only introduced for analysis purpose and is equivalent to the conventional sign function in practice. Suppose $(G,x)$ is an Erdős–Rényi random graph with revealed label $\Tilde{x}$, any estimator can only have vanishing correlation with the true label among the unrevealed vertices. So the semi-supervised weak recovery problem on SBM requires finding an estimator such that the correlation restricted on the unrevealed part is non-vanishing. Formally, we want to show that $$\operatorname{P}\left(\text{Overlap}(x|_{\Tilde{x}_i =0},\hat{x}|_{\Tilde{x}_i =0}) \geq \Omega(1) \right)=1-o(1)$$ \[constant gap\] Let $X$ and $Y$ be two independent binomial random variables with $X \sim \text{Binomial}(n,\frac{a}{n})$ and $Y \sim \text{Binomial}(n,\frac{b}{n})$, $a>b$. Denote $\delta = \delta(a,b) \coloneqq \frac{a-b}{2\exp{(a+b)}}$. Then, for sufficiently large $n$, $$\operatorname{P}(X>Y) - \operatorname{P}(X<Y) \geq \delta$$ By symmetry, we always have $\operatorname{P}(X>Y) - \operatorname{P}(X<Y) > 0$. This lemma guarantees the difference will not vanish as $n\to \infty$. By the law of total probability and independence, we have $$\begin{aligned} \operatorname{P}(X>Y)&=\sum_{x=1}^n \operatorname{P}(Y<x)\operatorname{P}(X=x)\\ &=\sum_{x=1}^n\sum_{y=0}^{x-1} \operatorname{P}(Y=y)\operatorname{P}(X=x)\\ &=\sum_{x=1}^n\sum_{y=0}^{x-1} \left[ \binom{n}{x}\left(\frac{a}{n}\right)^x \left(1-\frac{a}{n}\right)^{n-x} \binom{n}{y}\left(\frac{b}{n}\right)^y \left(1-\frac{b}{n}\right)^{n-y} \right]\end{aligned}$$ Let $\Delta \coloneqq \operatorname{P}(X>Y) - \operatorname{P}(X<Y)$, then $$\begin{gathered} \Delta=\sum_{x=1}^n \binom{n}{x} \left(\frac{a}{n}\right)^x\left(1-\frac{a}{n}\right)^{n-x}\left(\frac{b}{n}\right)^x\left(1-\frac{b}{n}\right)^{n-x}\\ \Bigg\{\sum_{y=0}^{x-1} \binom{n}{y} \left[ \left(\frac{b}{n}\right)^{y-x}\left(1-\frac{b}{n}\right)^{x-y} - \left(\frac{a}{n}\right)^{y-x} \left(1-\frac{a}{n}\right)^{x-y} \right]\Bigg\}\end{gathered}$$ $$\begin{gathered} \phantom{\Delta}=\sum_{x=1}^n \binom{n}{x} \left(\frac{ab}{n}\right)^x \left(1-\frac{a+b}{n}+\frac{ab}{n^2}\right)^{n-x}\\ \Bigg\{\sum_{y=0}^{x-1} \binom{n}{y}\frac{1}{n^y} \left[ \left(\frac{1}{b}-\frac{1}{n}\right)^{x-y} - \left(\frac{1}{a}-\frac{1}{n}\right)^{x-y} \right]\Bigg\}\end{gathered}$$ Let $f(x)= \alpha^x - \beta^x,~ \alpha > \beta >0$. Since $f'(x) = \alpha^x\ln{\alpha} - \beta^x\ln{\beta} >0$, we have $f(m)\geq f(1) = \alpha - \beta,~ \forall m\in \mathbb{N}$. So $\left(\frac{1}{b}-\frac{1}{n}\right)^{x-y} - \left(\frac{1}{a}-\frac{1}{n}\right)^{x-y}\geq \frac{a-b}{ab}$. Also notice that $\binom{n}{m}= \prod_{i=0}^{m-1}\frac{n-i}{m-i} \geq \left(\frac{n}{m}\right)^m,~ \forall 1\leq m\leq n$. We have, $$\begin{aligned} \Delta &\geq \sum_{x=1}^n \left(\frac{ab}{x}\right)^x \left(1-\frac{a+b}{n}\right)^{n-x} \left( \sum_{y=0}^{x-1} \frac{1}{y^y}\cdot\frac{a-b}{ab} \right)\\ &\geq (a-b) \left(1-\frac{a+b}{n}\right)^n\\ &\geq \frac{a-b}{2\exp{(a+b)}} \qquad (\text{for sufficiently large $n$})\end{aligned}$$ where we follow the convention that $0^0=1$. We resort to a classical concentration inequality to bound the overlap. \[Chernoff–Hoeffding theorem @Chernoff1952AMO\] \[Chernoff-Hoeffding\] Suppose $X_1, \dots, X_n$ are i.i.d. random variables, taking values in $\{0, 1\}$. Let $p = \operatorname{E}(X)$ and $\epsilon > 0$. Then $$\operatorname{P}\left(\frac{1}{n}\sum X_i \leq p-\epsilon \right) \leq \left( \left(\frac{p}{p-\epsilon}\right)^{p-\epsilon} \left(\frac{1-p}{1-p+\epsilon}\right)^{1-p+\epsilon} \right) ^n ={\mathrm{e}}^{-D(p-\epsilon\|p)n}$$ where $D(x\|y)=x\ln\frac{x}{y} + (1-x)\ln(\frac{1-x}{1-y})$ is the Kullback–Leibler-divergence between Bernoulli distributed random variables with parameters $x$ and $y$. We now convert the KL divergence to the total variation distance, which is easier to work with. Let $P_1$ and $P_2$ be two probability measures defined on the same sample space $\Omega$ and sigma-algebra $\mathcal{F}$. The total variation distance between them is defined as $d_{TV}(P_1,P_2) = \sup_{E \in \mathcal{F}}|P_1(E) - P_2(E)|$. Moreover, in the discrete case, we have following identity $d_{TV}(P_1,P_2) = \frac{1}{2}\|P_1-P_2\|_1 = \sum_{\omega\in \Omega} \frac{1}{2}\|P_1(\omega) - P_2(\omega)\|$. It is related to the KL divergence through Pinsker's inequality (see, eg. @Tsybakov2009IntroductionTN, Chapter 3). For completeness, we include an elementary proof of the Bernoulli special case. \[TV-KL\] Let $P_1$ and $P_2$ be two Bernoulli distributions, where $P_1(1) =x$ and $P_2(1) =y$. We have $$2(d_{TV}(P_1,P_2))^2 \leq D(x\|y)$$ We can manipulate both sides of the inequality as $$D(x\|y) = x\ln\frac{x}{y} + (1-x)\ln(\frac{1-x}{1-y})$$ $$2(d_{TV}(P_1,P_2))^2 = \frac{1}{2} \|P_1 - P_2\|_1^2 = 2(x-y)^2$$ We denote $f(x,y) = x \ln \frac{x}{y} + (1-x)\ln \frac{1-x}{1-y} - 2(x-y)^2$. Therefore, $$\begin{aligned} \frac{\partial f}{\partial y} &= -\frac{x}{y}+(1-x)\frac{1}{1-y}+4(x-y)\\ &= \frac{-x+y}{y(1-y)}+4(x-y)\\ &= (x-y)(4-\frac{1}{y(1-y)}) \end{aligned}$$ Notice that since $0 \leq y \leq 1$, $y(1-y) \leq \frac{1}{4}$. So $4-\frac{1}{y(1-y)}$ is always negative. Thus, for fixed $x$, $f(x,y) \geq f(x,x) = 0 ,~ \forall y$. Hence, $$D(x\|y) - 2(d_{TV}(P_1,P_2))^2 \geq 0$$ Now we prove the main result for the census method. \[Proof of Theorem \[thm:census\]\] Recall that for any $i$ such that $\Tilde{x}_i = 0$, our estimator is defined as $\hat{x}_i = \text{sgn}^*(\Tilde{\Delta}_1(i))$ and $$\Tilde{\Delta}_1(i) = \sum_{j:\Tilde{x}_j \neq 0} A_{ij}\Tilde{x}_j = \left(\sum_{\rho \frac{n}{2} <j \leq \frac{n}{2}} A_{ij} \right) - \left(\sum_{(1+\rho) \frac{n}{2} <j \leq n} A_{ij} \right)$$ It is indeed the difference between two independent binomial variables with parameters $(\rho n, \frac{\rho a}{\rho n})$ and $(\rho n, \frac{\rho b}{\rho n})$. By Lemma \[constant gap\], we have $$\operatorname{P}(\text{sgn}(\Tilde{\Delta}_1(i)) = x_i) - \operatorname{P}(\text{sgn}(\Tilde{\Delta}_1(i)) = - x_i) \geq \delta = \frac{\rho(a-b)}{2{\mathrm{e}}^{\rho(a+b)}}$$ for sufficiently large $n$. Also notice that $$\operatorname{P}(\text{sgn}(\Tilde{\Delta}_1(i)) = - x_i) = 1 - \operatorname{P}(\text{sgn}(\Tilde{\Delta}_1(i)) = x_i) - \operatorname{P}(\Tilde{\Delta}_1(i)=0)$$ Therefore, $$\operatorname{P}(\text{sgn}(\Tilde{\Delta}_1(i)) = x_i) \geq \frac{1+\delta}{2} - \frac{1}{2}\operatorname{P}(\Tilde{\Delta}_1(i)=0)$$ Then, by the law of total probability, we have $$\begin{aligned} \operatorname{P}(\hat{x}_i = x_i) &= \operatorname{P}(\text{sgn}^*(\Tilde{\Delta}_1(i)) = x_i)\\ &= \operatorname{P}(\text{sgn}(\Tilde{\Delta}_1(i)) = x_i) + \frac{1}{2}\operatorname{P}(\Tilde{\Delta}_1(i)=0)\\ &\geq \frac{1}{2} + \frac{\delta}{2} \end{aligned}$$ Since $\{\hat{x}_i\}$'s are independent for all unrevealed vertices as $\{\Tilde{\Delta}_1(i)\}$'s and $\operatorname{E}\left[\frac{\hat{x}_ix_i+1}{2}\right] = \operatorname{P}(\hat{x}_i = x_i)$, Lemma \[Chernoff-Hoeffding\] and Lemma \[TV-KL\] give us that $$\operatorname{P}\left(\frac{1}{(1-\rho)n}\sum_{i:\Tilde{x}_i = 0}\frac{\hat{x}_ix_i+1}{2}\leq \frac{1}{2} + \frac{\delta}{2} - \epsilon \right) \leq {\mathrm{e}}^{-2\epsilon^2 (1-\rho)n}$$ Taking $\epsilon = \frac{\delta}{4}$, we have $$\operatorname{P}\left(\text{Overlap}(x|_{\Tilde{x}_i =0},\hat{x}|_{\Tilde{x}_i =0}) \geq \frac{\delta}{2}\right) \geq 1 - {\mathrm{e}}^{-\frac{\delta^2 (1-\rho)n}{8}}$$ As long as $a>b$, we have $\delta > 0$, which concludes the proof. The semi-supervised SBM and ERM are not mutually contiguous for any given $a>b\geq 0$ and $\rho>0$. Let $P_n^{(0)} = \operatorname{\mathcal{G}}(n, \frac{a+b}{2n}, \frac{a+b}{2n}, \rho)$ and $P_n^{(1)}$ = $\operatorname{\mathcal{G}}(n, \frac{a}{n}, \frac{b}{n}, \rho)$. Then consider the same constant $\delta > 0$ from the proof of Theorem \[thm:census\] and denote the event sequence $E_n = \{\text{Overlap}(x|_{\Tilde{x}_i =0},\hat{x}|_{\Tilde{x}_i =0}) \geq \frac{\delta}{2}\}$ where $\hat{x}$ is our semi-supervised census estimator. We have $$\begin{aligned} P_n^{(0)}(E_n) \rightarrow 0 \quad &\text{(Law of large number)}\\ P_n^{(1)}(E_n) \nrightarrow 0 \quad &\text{(Bounded from below)} \end{aligned}$$ Semi-supervised SDP {#CSDP} =================== We have seen that the census method solves the semi-supervised community detection problem. But the algorithm is desirable in practice only when the amount of revealed labels is sufficient to support a reasonable performance. In other words, it has no unsupervised 'fallback' built in. Meanwhile, SDPs enjoy nice properties like optimality and robustness as mentioned earlier. It is also well known that approximate information about the extremal cuts of graphs can be obtained by computing the optimizer for SDP of their adjacency matrix, see for example @Goemans1995ImprovedAA. From both a practical and a mathematical point of view, we are interested in developing an SDP based semi-supervised clustering approach, and through which we shall be able to see the models, algorithms and phase transitions with a fresh perspective. In this section, we will focus on the hypothesis testing formulation of the community detection problem. We have discussed the equivalency between it and the non-vanishing overlap formulation under the unsupervised setting. In the semi-supervised scenario it is still an interesting question to ask whether there exists a test that can distinguish SBMs from ERMs. Here we understand ERM as the special case of SBM with $a = b$. It also has ground truth of labels, which is uniformly random under the balance constraint. Given that they are originally contiguous when $\text{SNR} \leq 1$, we want to show that revealed labels together with random graphs can separate them. SDP for community detection --------------------------- Under the Planted Bisection Model \[PBM\], the Maximum A Posteriori (MAP) estimator is equivalent to the Maximum Likelihood estimator, which is given by min-bisection, i.e., a balanced partition with the least number of crossing edges. Formally, it can be written the following optimization problem, $$\max_{\substack{x\in \{1,-1\}^n \\ x^\top {\mathbf{1}}= 0}} x^\top A x$$ By lifting the variable $X\coloneqq xx^\top$, we can rewrite it as $$\hat{X}_{MAP}(G)=\operatorname*{arg\,max}_{\substack{X \succeq 0 \\ X_{ii}=1, ~\forall i \in [n] \\ \text{rank} (X) = 1 \\ X \mathbf{1} = 0}} \langle A,X \rangle$$ Although min-bisection of $G$ is optimal (in the MAP sense) for exact recovery, finding it is NP-hard. Various relaxations have been proposed for the MAP estimator. Since the rank constraint makes the optimization difficult, we can remove it to make the problem convex. One can also get rid of the balance constraint by centralizing the adjacency matrix, $\tilde{A} \coloneqq A - \frac{d}{n} \mathbf{1}\mathbf{1}^\top$ with $d=(a+b)/2$ the average degree. This can also be justified using Lagrangian multipliers. And the resulting semidefinite relaxation is given by $$\label{eqn:SDP} \hat{X}_{\text{SDP}}(G)=\operatorname*{arg\,max}_{\substack{X\succeq 0\\ X_{ii}=1, ~\forall i\in [n]}}
{'source': 'arXiv_out/2205'}