1 Introduction↩︎

Community detection or clustering refers to the task of gathering similar nodes into a few groups from the data that, most often, correspond to observations of pair-wise interactions between nodes [1]. A benchmark commonly used to assess the performance of clustering algorithms is the celebrated Stochastic Block Model (SBM) [2], where pair-wise interactions are represented by a random graph. In this graph, the vertices correspond to nodes, and the presence of an edge between two nodes indicates their interaction.

The SBM has been widely studied over the past two decades; for a detailed overview, see [3]. However, it offers a somewhat simplistic representation of how nodes interact. In real-world applications, interactions can vary in type—such as ratings in recommender systems or proximity levels in social networks. To capture this richer, more nuanced interaction data, the Labeled Stochastic Block Model (LSBM) was introduced and analyzed in [4]–[6]. LSBM represents interactions through labels drawn from an arbitrary set. The aim of this paper is to illustrate the tightest condition under which clustering is possible based on observing these labels. For that purpose, we develop a clustering algorithm that minimizes the expected number of misclassified nodes. In the following sections, we formally introduce LSBMs and summarize our results.

The Labeled Stochastic Block Model. In the LSBM, the set \(\mathcal{I}\) consisting of \(n\) items or nodes is randomly partitioned into \(K\) unknown disjoint clusters \(\mathcal{I}_1,\ldots, \mathcal{I}_K\). The cluster index of the node \(i\) is denoted by \(\sigma(i)\). Let \({\alpha} = (\alpha_1, \alpha_2, \ldots,\alpha_K)\) represent the probabilities of nodes belonging to each cluster, i.e., for all \(k \in [K]\) and \(i \in \mathcal{I}\), \(\mathbb{P}(i \in \mathcal{I}_k)= \alpha_k\). We assume that \(\alpha_1, \ldots, \alpha_K\) are strictly positive constants and that \(K\) and \(\alpha\) are fixed as \(n\) grows large. The number of clusters \(K\) is initially unknown. Without loss of generality, we also assume that \(\alpha_1 \leq \ldots \leq \alpha_K.\) Let \(\mathcal{L} = \{0,1, \ldots, L\}\) be the finite set of labels. For each edge \((v,w) \in \mathcal{I}_i \times \mathcal{I}_j\), the learner observes the label \(\ell\) with probability \(p(i, j, \ell)\), independently of the labels observed in other edges. We have \(\forall i,j \in [K]^2, \;\sum_{\ell \in \mathcal{L}} p(i, j, \ell) =1\). Without loss of generality, \(0\) is the most frequent label: \(0 = \mathop{\mathrm{arg\,max}}_\ell \sum_{i=1}^K \sum_{j=1}^K \alpha_i \alpha_j p(i,j, \ell)\). Let \(\bar{p} = \max_{i, j, \ell \ge 1} p(i,j, \ell)\) be the maximum probability of observing a label different from \(0\). We will mostly consider the challenging sparse regime where \(\bar{p} = \mathcal{O}((\log n)/n )\) and \(\bar{p} n \to \infty\) as \(n \to \infty\), but we will precise the assumptions made on \(n\) and \(\bar{p}\) for each of our results. We further assume for all \(i, j, k \in [K]\): \[\begin{align} &\text{(A1)} \quad \forall \ell \in \mathcal{L}, \; \frac{p(i,j,\ell)}{p(i,k,\ell)}\le \eta \quad \text{and} \\ & \text{(A2)} \quad \frac{\sum_{k=1}^K \sum_{\ell=1}^L( p(i,k, \ell) - p(j,k,\ell) )^2}{\bar{p}^2} \ge \varepsilon, \end{align}\] where \(\eta\) and \(\varepsilon\) are positive constants independent of \(n\). (A1) imposes some homogeneity on the edge existence probability, and (A2) implies a certain separation among the clusters. In summary, the LSBM is parametrized by \(\alpha\) and \(p \mathrel{\vcenter{:}}= (p(i, j, \ell))_{1 \le i,j \le K, 0 \le \ell \le L }\).

1.1 Notation↩︎

We denote \(p(i)\) as the \(K \times (L +1)\) matrix whose element on \(j\)-th row and \((\ell+1)\)-th column is \(p(i,j,\ell)\) and denote \(p(i,j) \in [0, 1]^{L + 1}\) the vector describing the probability of the label of a pair of nodes in \(\mathcal{I}_i\) and \(\mathcal{I}_j\). Let \(\mathcal{P}^{K \times (L + 1)}\) denote the set of all \(K \times (L+1)\) matrices such that each row represents a probability distribution. Define the divergence \(D({\alpha}, p)\) of the parameter \((\alpha, p)\) as: \(D({\alpha}, p) = \min_{i, j \in [K]: i \neq j } D_{L+} ({\alpha}, p(i), p(j))\), with \[\begin{align} & D_{L+} (\alpha, p(i), p(j)) = \min_{y \in \mathcal{P}^{K \times (L+1)}} \max \\ &\quad \Bigg\{\sum_{k =1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(y(k), p(i, k)), \sum_{k = 1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(y(k), p(j, k)) \Bigg\}, \end{align}\] and where \(\mathop{\mathrm{\textrm{kl}}}\) denotes the Kullback-Leibler divergence between two label distributions, i.e., \(\mathop{\mathrm{\textrm{kl}}}(y(k), p(i, k)) = \sum_{\ell =0}^L y(k, \ell) \log\frac{y(k, \ell)}{p(i,k, \ell)}\). \(D_{L+} (\alpha, p(i), p(j))\) can be interpreted as the hardness in distinguishing whether a node belongs to cluster \(i\) or cluster \(j\) based on the data. For any clustering algorithm \(\pi\), we denote by \(\varepsilon^\pi(n)\) the number of misclassified nodes under \(\pi\). This quantity is defined up to a permutation of the cluster IDs. Specifically, if \(\pi\) returns \((\hat{\cal I}_k)_k\), then \(\varepsilon^\pi(n)\) is calculated as \(\min_{\theta} |\cup_k \hat{\cal I}_k\setminus {\cal I}_{\theta(k)}|\), where the minimum is over all permutations \(\theta\) of \([K]\). To simplify the notation throughout the paper, we assume that the permutation achieving the minimum is given by \(\theta(k)=k\) for all \(k \in [K]\).

1.2 Main Results↩︎

We consider the problem of clustering, or recovering communities, in the LSBM as described above. We reveal the necessary and sufficient conditions for the asymptotic recovery of the communities. Specifically, we reveal that the necessary and sufficient condition on the parameters \((\alpha,p)\) to achieve \(\limsup_{n \to \infty}\frac{\mathbb{E}[\varepsilon^\pi(n)]}{s} \le 1\), for any \(s=o(n)\), is \[\begin{align} \liminf_{n\to \infty} \frac{nD(\alpha,p)}{\log(n/s)} \ge 1. \end{align}\]

To this aim, we design a computationally efficient algorithm that recovers the clusters in the LSBM with a minimal error rate. By minimal, we mean that for any given LSBM, the algorithm achieves the best possible error rate for this specific LSBM. In other words, the algorithm is instance-optimal and truly adapts to the hardness of the LSBM it faces. This contrasts with algorithms with minimax performance guarantees only: those algorithms provably perform well for the worst possible LSBM, but could potentially yield poor performance for most other instances of the LSBM.

Instance-specific lower bound. To reveal the necessary condition, we first need to revisit an instance-specific lower bound on the error rate satisfied by any algorithm. The following theorem from [6] provides a necessary condition as a lower bound on the expected number of misclassified nodes \(\mathop{\mathrm{\mathbb{E}}}[\varepsilon^\pi(n)]\).

The lower bound essentially states that under any algorithm, the expected number of misclassified nodes must be larger than \(n\exp(-nD(\alpha,p))\). The proof of Theorem 1 is based on the change-of-measure argument frequently used in online stochastic optimization and multi-armed bandit problems [7], [8].

An instance-optimal algorithm (upper bound). The main contribution of this paper is to provide a sufficient condition for cluster recovery. Specifically, we propose an algorithm with performance guarantees that match those of the above lower bound and with computational complexity scaling as \(n\text{polylog}(n)\). This algorithm, referred to as Instance-Adaptive Clustering (IAC) and presented in Section 3, first applies a spectral clustering algorithm to initially guess the clusters and then runs a likelihood-based local improvement algorithm to refine the estimated clusters. To analyze the performance of the algorithm, we make the following assumption. \[\begin{align} \text{(A3)}& \quad np(j,i,\ell) \ge (n\bar{p})^\kappa \text{ for all } i,j \text{ and } \ell \ge 1, \\ & \quad \text{for some constant } \kappa > 0. \end{align}\] Assumption (A3) excludes the existence of labels that are too sparse compared to \(\bar{p}\). The following theorem establishes the performance guarantee of IAC. Its full proof is given in Appendix 8.

As far as we are aware, IAC is the first algorithm achieving a performance that matches the lower bound presented in Theorem 1.

To obtain an instance-optimal guarantee in expectation, we had to (i) reshape parts of the algorithm, and (ii) develop new tools to analyze its performance. Specifically, to assess the expected number of misclassified nodes after the first spectral clustering phase, we needed a tighter guarantee for the probability of a failure event of the spectral clustering algorithm with the iterative power method and singular value thresholding. Analyzing the second phase (the likelihood-based improvement step) of the algorithm in expectation was also challenging. All intermediate statements had to hold with sufficiently high probability and quantify the number of misclassified nodes for any number \(s = o(n)\). Furthermore, as reflected in the definition of the divergence \(D(\alpha, p)\), the optimal clustering boundary is asymmetric, necessitating that both the improvement step and its analysis account for the nonlinear information geometry.

2 Related Work↩︎

In this section, we review existing literature on community detection in stochastic block models (SBMs) and their extensions, focusing on performance guarantees and optimal recovery rates relevant to our analysis.

2.1 Community Detection in the SBM↩︎

Community detection in the stochastic block model (SBM) and its extensions has received considerable attention over the last decade. We first briefly outline existing results below, and then focus on a few papers that are most relevant to our analysis. The results for the SBM can be categorized according to the type of performance guarantee targeted. We distinguish three types of guarantees: detectability, asymptotically accurate recovery, and exact recovery. Most results are concerned with the standard SBM, which can be obtained as a special case of the LSBM (with \(L=1\), where the intra- and inter-cluster probabilities are denoted by \(p(i,i,1)\) and \(p(i,j,1)\) for \(i\neq j \in [K]\)).

Detectability. Detectability refers to the requirement of returning clusters that are positively correlated with the true clusters. It is typically studied in the sparse binary SBM where \(K=2\), \(\alpha_1=\alpha_2\), \(p(1,1,1)=p(2,2,1)=a/n\) and \(p(1,2,1)=p(2,1,1)=b/n\), for some constants \(a>b\) independent of \(n\). For such SBM, detectability can be achieved if and only if \((a-b)>\sqrt{2(a+b)}\) [9]–[11]. Detectability conditions in more general sparse SBMs have been investigated in [12], [13]. In the sparse SBM, when the edge probabilities scale as \({\cal O}(1/n)\), there is a positive fraction of isolated nodes, and we cannot do much better than merely detecting the clusters. In this paper, we focus on scenarios where the edge probabilities are \(\omega(1/n)\), where an asymptotically accurate recovery of the clusters may be achieved.

Asymptotically accurate recovery. Our results can also be interpreted as a generalization of the necessary and sufficient condition for asymptotically accurate recovery of the communities in the labeled stochastic block model (LSBM), namely \(nD(\alpha, p) = \omega(1)\). Under this condition, we can achieve asymptotically accurate recovery of the clusters, meaning that the proportion of misclassified nodes tends to zero as \(n\) grows large. A necessary and sufficient condition for asymptotically accurate recovery in the SBM (with any number of clusters of different but linearly increasing sizes) has been derived in [14] and [15]. In our work, we performed a more precise analysis and succeeded in generalizing this condition. Our results are characterized by our divergence \(D(\alpha, p)\), which makes the condition instance-specific. Our analysis thus provides more accurate results than those derived in a minimax framework [16]–[19]. An extensive comparison with [16], where we also strengthen their analysis, is provided in Section 2.2.

Asymptotically exact recovery. An algorithm achieves an asymptotically exact recovery if no nodes are misclassified asymptotically. By choosing \(s= 1/2\) in our theorems, our results provide the necessary and sufficient condition for such exact recovery. Conditions for asymptotically exact recovery have also been studied in the binary symmetric SBM [15], [20]–[22]. For instance, when \(K=2\), \(\alpha_1=\alpha_2\), \(p(1,1,1)=p(2,2,1)=\frac{a \log n}{n}\) and \(p(1,2,1)=p(2,1,1)=\frac{b \log n}{n}\), where \(a\) and \(b\) are some constants with \(a>b\), cluster recovery is possible if and only if \(\frac{a + b }{2} - \sqrt{ab}\ge 1\). There are also extensions to more general SBMs [23]–[25]. Our results are in a form that generalizes these results.

2.2 Comparison with Previous Work on Optimal Recovery Rates↩︎

Next, we discuss three papers [16], [17], [26] that are directly related to our analysis. These papers study the standard SBM or homogeneous LSBM in the regime where asymptotically accurate recovery is possible. [16], [26] present the minimal expected number of misclassified nodes, but in a minimax setting, whereas [17] presents the instance-specific analysis.

The authors of [26] characterize the minimal expected number of misclassified nodes in the worst possible SBM within the class \(\Theta(n,a,b)\) of SBMs satisfying, using our notation, \(p(i,i,1) \ge \frac{a}{n}\) and \(p(i,j, 1)\le \frac{b}{n}\) for all \(i\neq j\in [K]\), where \(a\) and \(b\) are positive constants. To simplify the exposition here, we assume that all clusters are of equal size (refer to [26] for more details). The minimal expected number of misclassified nodes is defined through the Rényi divergence of order \(\frac{1}{2}\) between the Bernoulli random variables of respective means \(\frac{a}{n}\) and \(\frac{b}{n}\), given by \[I^*(n, a, b) = - 2 \log \left(\sqrt{\frac{a}{n}}\sqrt{\frac{b}{n}} + \sqrt{1 -\frac{a}{n}}\sqrt{1- \frac{b}{n}}\right).\] When \(nI^*(n,a,b)=\omega(1)\), \(\mathbb{E}[\varepsilon^\pi(n)]\) scales as \(n\exp(-(1+o(1)){ \frac{nI^*(n,a,b)}{ K}})\). [26] established that the so-called penalized Maximum Likelihood Estimator (MLE) achieves this minimax optimal recovery rate but does not provide any algorithm to compute it.

The authors of [16] present an algorithm that runs in polynomial time and achieves this minimax lower bound with high probability¹. Again, for simplicity, we assume that all clusters are of equal size and that \(K\) is a fixed constant. Their performance guarantee can be stated as follows (see Theorem 4 in [16]): \[\begin{align} & \sup_{(\alpha, p) \in \Theta(n, a, b)} \mathbb{P}_{(\alpha, p)} \\ & \quad \Bigg( \varepsilon^\pi(n) \ge n \exp\left( - (1+o(1)) \frac{n I^*(n, a,b)}{K}\right) \Bigg) \to 0, \end{align}\] where \(\mathbb{P}_{(\alpha, p)}\) denotes the distribution of the observations generated under the SBM \((\alpha,p)\). One could argue that the above guarantee does not match the minimax lower bound valid for the expected number of misclassified nodes. However, by carefully inspecting the proof of Theorem 4 in [16], it is easy to see that the guarantee also holds in expectation:

The proof is presented in Appendix 10.10. The assumptions of Corollary 1 are satisfied when our assumptions (A1) and (A2) hold.

The algorithm presented in [16], which has established performance guarantees, comes with a high computational cost. It requires applying spectral clustering \(n\) times, where for each node \(u\), the algorithm builds a modified adjacency matrix by removing the \(u\)-th column and the \(u\)-th row and then computes a spectral clustering of this matrix. In contrast, our algorithm performs spectral clustering only once. [16] also proposed an algorithm with reduced complexity (running in \(\Omega(n^2)\)), but without performance guarantees. Our algorithm not only performs spectral clustering once but also requires just \(\mathcal{O}(n (\log n)^3)\) operations. Additionally, our algorithm empirically exhibits better classification accuracy than the penalized local maximum likelihood estimation algorithm from [16] in several simple scenarios (see Appendix 11).

To conclude, compared to [16], our analysis provides an instance-specific lower bound for the classification error probability (rather than minimax) and introduces a low-complexity algorithm that matches this lower bound. Additionally, our analysis is applicable to the generic Labeled SBMs. It is worth noting, however, that [16] derives upper bounds for classification error probability under slightly more general assumptions than ours for the SBMs. Specifically, their high probability guarantee also holds for dense regimes (\(\bar{p} = \omega(\log n/n))\), and their number of clusters \(K\) can depend on \(n\), whereas we consider fixed \(K\).

[17] presents an instance-specific analysis for the homogeneous LSBM, in which the distribution of an edge depends solely on whether the corresponding nodes are in the same cluster or not. Specifically, there exist distributions \(P\) and \(Q\) such that for each edge label \(\ell\), the probabilities are defined as \(p(i, i, \ell) = P(\ell)\) for all \(i \in [K]\), and \(p(i, j, \ell) = Q(\ell)\) for all \(i \neq j\). In contrast, our model does not impose such restrictions; the edge label probabilities can vary heterogeneously depending on the cluster indices. Similar to the algorithm in [16], the algorithm proposed in [17] executes spectral clustering \(n\) times (see lines 8–10 in Algorithm 3 of [17]).

2.3 Other Related Work↩︎

Spectral methods. Recent studies also suggest that there are clustering instances where the spectral clustering algorithm alone is optimal without the improvement step. [27] provides a detailed analysis of the spectral method without any improvement steps in the setting of simple SBMs for asymptotically accurate recovery. Their work establishes lower bounds on the performance achievable by spectral clustering algorithms. However, these lower bounds are specific to the spectral method and thus do not represent the fundamental limits of community detection that we have been considering. As a result, the focus of their work is not on developing algorithms that achieve optimal rates but rather on providing a tight analysis of the spectral method’s performance. We also conjecture that in the general (L)SBM, spectral clustering alone cannot achieve the optimal rates due to the asymmetry of the optimal decision boundary, as reflected in the definition of the divergence \(D(\alpha, p)\). This necessitates the use of non-Euclidean distances within the algorithm. In [27], the \(k\)-means algorithm is based on the Euclidean distance (see Eq. (2) of Algorithm 1 in [27]), which would be insufficient to achieve our optimal result.

For the exact recovery regime, [28], [29] discuss the optimality of the spectral algorithm for the Censored SBM (which is an instance of LSBM) or LSBM. They only provided high-probability guarantees and the algorithms require weights that depend on the statistical parameters.

Related models. LSBM generalizes the SBM, the Censored SBM [28], [30], and signed networks [31]–[33], and has many applications. Our results provide necessary and sufficient conditions for cluster recovery in all of these models for any \(s = o(n)\). The Multiplex Stochastic Block Model [34] and the node-attributed Stochastic Block Model [35] are interesting because they can capture cluster structures that cannot be represented by the SBM or the LSBM. Extending our work to such models is an important future direction.

3 Instance-Adaptive Clustering Algorithm↩︎

In this section, we introduce the Instance-Adaptive Clustering (IAC) algorithm, outlined in Algorithm 1. The IAC algorithm is a two-step algorithm consisting of initial spectral clustering and iterative likelihood-based improvements. The algorithm aims to improve clustering performance by adapting to the instances.

3.1 Algorithms↩︎

The Instance-Adaptive Clustering (IAC), whose pseudo-code is presented in Algorithm 1, consists of two phases: a spectral clustering initialization phase and a likelihood-based improvement phase.

Spectral clustering initialization. The algorithm relies on simple spectral techniques to obtain rough estimates of the clusters. For details, refer to lines 1-4 in Algorithm 1 and Algorithm 2. The algorithm first constructs an observation matrix \(A^\ell=(A_{uv}^\ell)_{u,v}\) for each label \(\ell\) (where \(A_{uv}^\ell=1\) iff label \(\ell\) is observed on edge \((u,v)\)). After the trimming process, which eliminates rows and columns corresponding to nodes with an excessive number of observed labels (as these could distort the spectral properties of \(A^\ell\)) as \(A^\ell_\Gamma\), we apply spectral clustering to \((A^\ell_\Gamma)_{\ell\in [L]}\). Specifically, we concatenate the matrices \((A^\ell_\Gamma)_{\ell\in [L]}\) as \(\bar{A} = [A_\Gamma^1, A_\Gamma^2, \ldots, A_\Gamma^L]\) and use the iterative power method (instead of using a direct SVD) combined with singular value thresholding [36]. This approach allows us to control the computational complexity of the algorithm and to accurately estimate the number of clusters.

Notable differences compared to the spectral clustering phase of the algorithm presented in [6] include (i) a change in the number of matrix multiplications required in the iterative power method, which is now approximately \((\log n)^2\); (ii) an expansion of the set of centroid candidates in the k-means algorithm, which now includes \((\log n)^2\) randomly selected nodes; and (iii) the use of the concatenated matrix \(\bar{A} = [A_\Gamma^1, A_\Gamma^2, \ldots, A_\Gamma^L]\). In contrast, [6] uses a randomly weighted matrix \(\sum_{\ell \in [L]} w_\ell A^\ell_\Gamma\) with i.i.d. uniform distribution \(w_\ell\) for clustering, which prevents us from obtaining the guarantee in expectation. Our new approach allows for tighter control of the probability of failure events and provides guarantees in expectation.

Likelihood-based improvements. Using the initial cluster estimates \(S_i\), we can also estimate \(p\) from the data. For any \(i,j,\ell\), we calculate the empirical estimate: \[\hat{p}(i, j, \ell) = \frac{\sum_{u \in S_i} \sum_{v \in S_j} A^\ell_{uv}}{|S_i||S_j|}.\] Based on \(\hat{p}\), the log-likelihood of node \(v\) belonging to cluster \(S_k\) is computed as \(\sum_{i \in [\hat{K}]} \sum_{w \in {S}_{i}} \sum_{\ell=0}^L A_{vw}^\ell \log \hat{p}(k, i, \ell)\). Subsequently, \(v\) is assigned to the cluster that maximizes this log-likelihood over \([\hat{K}]\). This process is applied to all nodes and iterated \(\log n\) times. One iteration of this process is fast: by taking advantage of sparsity and computing by traversing only the node pairs for which a label exists, the computational complexity can be reduced to \(\mathcal{O}(\log n)\). The improvement step corresponds to improving the cluster assignment along the nonlinear decision boundary, as reflected in the definition of our divergence \(D(\alpha, p)\).

4 Theoretical Guarantees↩︎

In this section, we provide a sketch of the proof of its performance guarantees, with the full proof available in Appendix 8.2.

4.1 Spectral Clustering Initialization↩︎

The following theorem establishes performance guarantees for the cluster estimates returned by the spectral clustering algorithm (refer to Algorithm 2 for details). Specifically, we show that the number of clusters is correctly predicted as \(\hat{K}=K\), and the number of misclassified nodes is \({\cal O}(1/\bar{p})\), which is \(o(n)\) as \(n\bar{p} = \omega(1)\).

Proof Sketch of Theorem 3. Let \(M^\ell\) denote the expectation of the matrix \(A^\ell\): \(M^\ell_{uv} = p(i,j, \ell)\) when \(u \in \mathcal{V}_i\) and \(v \in \mathcal{V}_j\). Let \(M =[M^1, M^2, \ldots, M^L]\), and \(M_\Gamma = [M_\Gamma^1, M_\Gamma^2, \ldots, M_\Gamma^L]\in [0,1]^{n \times Ln}\) be the corresponding trimmed matrix, where \((M_\Gamma^\ell)_{wv} = M_{wv}^\ell\mathbb{1}_{\{ w,v \in \Gamma\} }\).

(a) The first ingredient of the proof is to use an upper bound on the norm of the noise matrix \(X_\Gamma^\ell = A_\Gamma^\ell - M_\Gamma^\ell\), which holds with sufficiently high probability, as stated in the following lemma from [37].

We note that such a tight guarantee was also observed in [16] for the simple SBM using different algorithms. We also note that proof techniques like the symmetrization argument (e.g., [22]) cannot be directly applied for the sparse regime (\(\bar{p} = \mathcal{O}((\log n )/n)\)). Recall that we defined the concatenated matrix \(\bar{A} = [A_\Gamma^1, A_\Gamma^2, \ldots, A_\Gamma^L]\). Based on the above lemma, we deduce that for any \(C>0\), there exists \(C'>0\) such that \[\|\bar{A} - M_\Gamma\| \le C' \sqrt{n\bar{p}},\] with probability at least \(1 - \exp(- Cn \bar{p})\).

(b) The second ingredient of the proof is the following lemma, whose proof is provided in Appendix 10.6. The lemma provides a lower bound on the distance between two columns of \(M_\Gamma\) corresponding to two nodes in distinct clusters.

(c) The final proof ingredient, which is proved in Appendix 10.7, concerns the performance of the iterative power method with singular value thresholding that outputs the rank-\(\hat{K}\) approximation \(\hat{A}\) (see Algorithm 2).

The challenge is that all these Lemmas require quantified high-probability guarantees. We are now ready to prove the theorem. We first explain why the number of clusters is accurately estimated. It is straightforward to verify that there exist two strictly positive constants, \(C_1\) and \(C_2\), such that with probability at least \(1-\exp(-\omega(n))\), \(C_1 \bar{p} \le \widetilde{p}\le C_2 \bar{p}\) (refer to Lemma 8). Consequently, from Lemma [lm:spectralresults], we deduce that for any \(C>0\), with probability at least \(1 - \exp(- Cn \bar{p})\), the \((K+1)\)-th singular value of \(A_\Gamma\) is significantly smaller than \(\sqrt{\widetilde{p}n}\log(n\widetilde{p})\). In conjunction with Lemma [lem:iterative95power95svt], this indicates that \(K=\hat{K}\) with probability at least \(1 - \exp(- Cn \bar{p})\). Therefore, we can assume in the remainder of the proof that \(K=\hat{K}\).

Without loss of generality, let us denote \(\gamma\) as the permutation of \([K]\) such that the set of misclassified nodes is \(\bigcup_{k=1}^K S_k \setminus \mathcal{I}_{\gamma(k)}\). Based on Lemma [lm:columndistance], we can prove that: with probability at least \(1-\exp(\omega(n))\), \[\begin{align} & \Big\vert \bigcup_{k=1}^K S_k \setminus \mathcal{I}_{\gamma(k)}\Big \vert C'n\bar{p}^2 \\ & \quad \le \sum_{k=1}^{K} \sum_{v \in {S}_{k} \setminus \mathcal{I}_{\gamma(k)}} ||M_{\Gamma, v} - M_{\Gamma,\gamma(k)}||_2^2 \\ & \quad \le 8||M_\Gamma - \hat{A}||_F^2 + 8 r_{t^{*}}, \end{align}\] where \(M_{\Gamma,\gamma(k)}=M_{\Gamma,w}\) for \(w\in {\cal I}_{\gamma(k)}\), and where \(r_{t^{*}}\) is defined in Algorithm 2. Furthermore, for any \(C>0\), using Lemmas [lm:spectralresults] and [lem:iterative95power95svt], we can establish that there exists a constant \(C_0>0\) such that \[||M_\Gamma - \hat{A}||_F^2\le C_0 n\bar{p}\] with probability at least \(1-\exp(-Cn\bar{p})\). Through a refined analysis of the k-means algorithm, we can also prove the existence of a constant \(C_1>0\) such that \(r_{t^{*}} \le C_1 n\bar{p}\). For details, please refer to Appendix 9.

4.2 Likelihood-Based Improvements↩︎

To complete the proof of Theorem 2, we analyze the likelihood-based improvement phase of the IAC algorithm. For this purpose, we define the set of well-behaved nodes \(H\). We denote the total number of node pairs with observed label \(\ell\) including the node \(v\) and a node from \(S\) by \(e(v, S, \ell) = \sum_{w \in S} A^{\ell}_{vw}\), and let \(e(v, S) = \sum_{\ell=1}^L e(v, S, \ell)\). Let \(H\) be the largest set of nodes \(v \in \mathcal{I}\) that meet the following three conditions with some constant \(C_{\text{H1}} > 0\):

• \(e(v,\mathcal{I}) \le C_{\text{H1}} n\bar{p}\);

• when \(v\in \mathcal{I}_k\), \(\sum_{i =1}^K \sum_{\ell =0}^L e (v,\mathcal{I}_i ,\ell ) \log \frac{p (k,i,\ell)}{p (j,i,\ell)} \ge \frac{n\bar{p}}{\log^4 n\bar{p}}\) for all \(j \neq k\);

• \(e(v, \mathcal{I} \setminus H) \le \frac{2 n\bar{p}}{\log^5(n \bar{p})}\).

We will show that all nodes in \(H\) are correctly clustered with high probability, and that the expected number of nodes not in \(H\) matches the lower bound on the expected number of misclassified nodes. Each condition in the definition of \(H\) can be interpreted as follows: (H1) imposes some regularity in the degree of the node, (H2) implies that \(v\in H\) is correctly classified when using the likelihood, and the last condition (H3) implies that the node does not have too many labels pointing outside of the set \(H\).

First, we show that the number of nodes not in \(H\) can be upper bounded by a number \(s\) that is of the same order as \(n\exp(-nD(\alpha, p))\), both in expectation and with high probability.

The proof of Proposition 4 can be found in Appendix 8.3. The proof reveals that the probability of a node satisfying (H2) is dominant compared to the probabilities of the other two conditions and is of the order of \(\exp(-nD(\alpha, p))\).

Next, we examine the performance of the likelihood-based improvement step (Line 6 in the IAC algorithm) for nodes in \(H\). In the following proposition, we quantify the improvement achieved with one iteration of this step.

The proof of Proposition 5 can be found in Appendix 8.4 and takes advantage of the fact that a likelihood-based test using the estimator \(\hat{p}(j, i, \ell)\) matches the test that would use the true likelihood, with high probability. Next, we present the sketch of the proof of Theorem 2 (refer to Appendix 8.2 for a complete proof).

Proof sketch of Theorem 2. we can now complete the proof by observing that from Proposition 5, after the \(\lceil \log n \rceil\) iterations of the likelihood-based improvement step, \[| \cup_{k=1}^K (S^{(\lceil \log n \rceil )}_k \setminus \mathcal{I}_k)\cap H|=0,\] with probability at least \(1 - \exp(-Cn \bar{p})\) for any constant \(C>0\). Combining this result with Proposition 4, when \(s \ge n \exp\left( -nD(\alpha, p) + \frac{n \bar{p}}{\log^3 n \bar{p}}\right)\), \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[\varepsilon^\text{IAC}(n)] & \le \frac{1}{1- o(1)}\mathop{\mathrm{\mathbb{E}}}[|\mathcal{I}\setminus H|] + o(1) \\ & \le \frac{s}{1- o(1)}\Big( 1 + \exp\Big(- \frac{3 n \bar{p}}{4 \log^3 n \bar{p}}\Big) \\ & \qquad + \exp( - \omega(n \bar{p}))\Big) + o(1) \end{align}\] and \(\varepsilon^\text{IAC}(n) \le s +o(1)\), with high probability.

4.3 Technical Challenges in Instance-Specific Analysis↩︎

The design principles behind IAC build upon existing studies that have proposed two-phase algorithms employing initial spectral clustering followed by iterative improvement steps [6], [16], [38], [39]. However, their analyses are either (i) minimax in nature or limited to the simple SBM—with no analysis for general number \(s = o(n)\) [16], [38], [39]—or (ii) provide only high-probability guarantees [6].

Most of the existing analyses are limited to the simple SBM or minimax frameworks and hence do not readily transfer to the instance-specific analysis. If we consider the general (L)SBM, the optimal decision boundary of the cluster assignment is asymmetric and should take into account the information geometry, as reflected in the definition of our divergence \(D(\alpha, p)\).

The exception is [6], who provided an instance-optimal analysis under the general LSBM. However, their analysis is limited to high-probability guarantees. More precisely, this algorithm misclassifies fewer than \(s\) nodes with a probability that tends to 1 as \(n\) grows large, provided that \(s\) and the parameters satisfy the condition 1 . The probability of the failure event (which corresponds to the case where the algorithm misclassifies more than \(s\) nodes) is not quantified, but is necessary if one wishes to derive guarantees in expectation.

5 Conclusion↩︎

In this paper, we investigate the problem of recovering hidden communities in the Labeled Stochastic Block Model (LSBM) with a finite number of clusters whose sizes grow linearly with the total number of nodes. We reveal the necessary and sufficient conditions under which the expected number of misclassified nodes is less than \(s\), for any number \(s = o(n)\): \[\liminf_{n\to \infty} \frac{nD(\alpha,p)}{\log(n/s)} \ge 1.\] To achieve this, we propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches these lower bounds both in expectation and with high probability. IAC is a novel two-phase algorithm that consists of a one-shot spectral clustering step followed by iterative likelihood-based cluster assignment improvements. Notably, this approach is based on an instance-specific nonlinear lower bound and does not require any knowledge of the model parameters, including the number of clusters. By performing the spectral clustering only once, IAC maintains an overall computational complexity of \(\mathcal{O}(n\, \text{polylog}(n))\), making it scalable and practical for large-scale problems. Our results bridge the gap between existing upper and lower bounds for cluster recovery in the LSBM, providing tight necessary and sufficient conditions.

Future work could explore extending these results to models with more complex cluster structures (e.g., the Multiplex Stochastic Block Model) or consider robustness to model misspecification and adversarial noise.

Acknowledgements↩︎

Kaito Ariu is supported by JSPS KAKENHI Grants No. 23K19986 and No. 25K21291. Alexandre Proutiere is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, the Swedish Research Council (VR) and Digital Futures. S. Yun is supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2022-II220311, Development of Goal-Oriented Reinforcement Learning Techniques for Contact-Rich Robotic Manipulation of Everyday Objects, No. RS-2024-00457882, AI Research Hub Project, and No. RS-2019-II190075, Artificial Intelligence Graduate School Program (KAIST)).

Impact Statement↩︎

This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

6 Notation Summary↩︎

Please refer to Table 1 for a summary of the notations we use.

We use \(\| \cdot \|\) to denote the \(\ell_2\)-norm, i.e., \(\|\boldsymbol{x}\| = \sqrt{\sum_{i} |x_i|}\). We use the standard matrix norm \(\| A\|=\sup\limits_{x:\| x\|_2=1}\| Ax\|_2\). We denote by \(M^\ell\) the expectation of the matrix of \(A^\ell\), i.e., \(M^\ell_{u,v} = p(i,j,\ell)\) when \(u\in \mathcal{I}_i\) and \(v\in \mathcal{I}_j\). Let \(M = [M^1, M^2, \ldots, M^L]\). We also denote by \(e(v,S,\ell) = \sum_{w \in S} A^{\ell}_{vw}\) the total number of node pairs with observed label \(\ell\) including the node \(v\) and a node from \(S\) and \(\mu(v,S,\ell) = \frac{e(v,S,\ell)}{|S|}\) the empirical density of label \(\ell\). Let \(e(v,S) = \sum_{\ell=1}^L e(v,S,\ell)\) and \(\mu(v,S) = [\mu (v,S,\ell)]_{0\le\ell\le L}\). In what follows, \(e(v,\mathcal{I})\) is referred to as the degree of node \(v\), which represents the number of observed labels that are different from 0 for pairs of nodes that include \(v\).

7 Lemmas Regarding the Divergence \(D(\alpha,p)\)↩︎

In this part, we present several lemmas in [6] related to the divergence \(D(\alpha,p)\).

Proof. Let us prove the existence of such a \(q\) by contradiction. Suppose that \[D(\alpha,p) = \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(q(k),p(i^*,k)) > \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(q(k),p(j^*,k)).\] In this case, there must be a \(k_0\) for which \(\mathop{\mathrm{\textrm{kl}}}(q(k_0),p(i^*,k_0)) > \mathop{\mathrm{\textrm{kl}}}(q(k_0),p(j^*,k_0))\). Noting the positive nature of the KL-divergence, \(q(k_0)\neq p(i^*,k_0)\). As a result of the KL-divergence’s continuity, we can create \(q'\) such that \(q(k)=q'(k)\) for all \(k\neq k_0\), and the following conditions hold: \(\mathop{\mathrm{\textrm{kl}}}(q(k_0),p(i^*,k_0))-\epsilon< \mathop{\mathrm{\textrm{kl}}}(q'(k_0),p(i^*,k_0)) < \mathop{\mathrm{\textrm{kl}}}(q(k_0),p(i^*,k_0))\) and \(\mathop{\mathrm{\textrm{kl}}}(q'(k_0),p(j^*,k_0)) < \mathop{\mathrm{\textrm{kl}}}(q(k_0),p(j^*,k_0))+\epsilon\) for some \(0<\epsilon < (\mathop{\mathrm{\textrm{kl}}}(q(k_0),p(i^*,k_0)) - \mathop{\mathrm{\textrm{kl}}}(q(k_0),p(j^*,k_0)))/2\). With this selection of \(q'\), we obtain: \[D(\alpha,p) > \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(q'(k),p(i^*,k)) > \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(q'(k),p(j^*,k)),\] which is in contradiction with the definition of \(D(\alpha,p)\). \(\blacksquare\)

Proof. Let \((i^*, j^*)\) be the pair that minimizes \(D_{L+}(\alpha,p(i),p(j))\) with \(i^*< j^*\). According to Lemma 1, there exists \(q\) such that \[D(\alpha,p) = \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(q(k),p(i^*,k)) = \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(q(k),p(j^*,k)).\] Following this, \[\begin{align} nD(\alpha,p) &=& n\frac{\sum_{k=1}^K \left(\alpha_k \mathop{\mathrm{\textrm{kl}}}(q(k),p(i^*,k))+\alpha_k \mathop{\mathrm{\textrm{kl}}}(q(k),p(j^*,k))\right)}{2} \cr &=&-n\sum_{k=1}^K \alpha_k \sum_{\ell=0}^L q(k,\ell)\log\left(\frac{\sqrt{p(i^*,k,\ell)p(j^*,k,\ell)}}{q(k,\ell)}\right)\cr &\ge &n\sum_{k=1}^K \alpha_k \sum_{\ell=0}^L \left( q(k,\ell)- \sqrt{p(i^*,k,\ell)p(j^*,k,\ell)}\right) \cr &= &n\sum_{k=1}^K \alpha_k \left( \frac{\sum_{\ell=1}^L (p(i^*,k,\ell)+p(j^*,k,\ell))}{2}- \sum_{\ell=1}^L\sqrt{p(i^*,k,\ell)p(j^*,k,\ell)}\right)\left(1-o(1)\right)\cr &=&n\sum_{k=1}^K \frac{\alpha_k}{2} \left( \sum_{\ell=1}^L (\sqrt{p(i^*,k,\ell)} - \sqrt{p(j^*,k,\ell)})^2\right)\left(1-o(1)\right). \end{align}\] \(\blacksquare\)

Proof. Based on the definition of \(D(\alpha,p)\), for any \(i\neq j\), we have: \[\begin{align} D(\alpha,p) &\le & \max\left\{ \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(p(i,k),p(i,k)), \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(p(i,k),p(j,k))\right\} \cr & =& \sum_{k=1}^K \alpha_k \mathop{\mathrm{\textrm{kl}}}(p(i,k),p(j,k)) \cr &\le & \sum_{k=1}^K \alpha_k \sum_{\ell=1}^L \frac{(p(i,k,\ell)-p(j,k,\ell))^2}{p(j,k,\ell)}(1+o(1))\cr &\le & \sum_{k=1}^K \alpha_k \sum_{\ell=1}^L \eta \bar{p}(1+o(1))\cr & = & \eta \bar{p} L(1+o(1)), \end{align}\] where we employ \(\log(1+x) = x(1+o(1))\) when \(x= o(1)\). \(\blacksquare\)

8 Performance Analysis of the IAC Algorithm – Proof of Theorem 2↩︎

8.1 Preliminaries↩︎

The proof is given in Appendix 10.1.

The proof is given in Appendix 10.2.

Regarding the estimation of \(\bar{p}\) as \(\widetilde{p}\), we show that \(\widetilde{p}\) has the same order as \(\bar{p}\) with high probability:

The proof is given in Appendix 10.3.

8.2 Proof of Theorem 2↩︎

For each \(k \in [K]\), from Chernoff-Hoeffding’s theorem and Pinsker’s inequality, for any constant \(C>0\), we get: \[\begin{align} \mathbb{P}\left( | |\mathcal{I}_k| - \alpha_k n | \le \sqrt{n} \log n | \right) &\le \exp\left( -n \mathop{\mathrm{\textrm{kl}}}\left(\alpha_k - \frac{\log n}{\sqrt{n}}, \alpha_k\right)\right) + \exp\left( -n \mathop{\mathrm{\textrm{kl}}}\left(\alpha_k + \frac{\log n}{\sqrt{n}}, \alpha_k\right)\right) \nonumber \\ & \le 2\exp\left( -2 (\log n)^2\right)\nonumber \\ & \le\frac{1}{n^C}. \label{eq:cluster95size95guarantee} \end{align}\tag{2}\] Hence, we make the assumption that for every \(k \in [K]\), the inequality \[\begin{align} \label{eq:first95event95ineq} | |\mathcal{I}_k| - \alpha_k n | \le \sqrt{n} \log n \end{align}\tag{3}\] is maintained throughout the remainder of the proof.

With a positive constant \(C_{H1}\), let \(H\) be the largest set of nodes \(v\in \mathcal{I}\) satisfying:

• \(e(v,\mathcal{I}) \le C_{\text{H1}} n\bar{p}\).

• When \(v\in \mathcal{I}_k\), \(\sum_{i =1}^K \sum_{\ell =0}^L e (v,\mathcal{I}_i ,\ell ) \log \frac{p (k,i,\ell)}{p (j,i,\ell)} \ge \frac{n\bar{p}}{\log (n\bar{p})^4}\) for all \(j \neq k\).

• \(e(v,\mathcal{I}\setminus H) \le \frac{2 n\bar{p}}{\log^5(n \bar{p})}.\)

(H1) controls degrees, (H2) implies that \(v \in H\) is accurately classified using the (true) log-likelihood, and (H3) indicates that \(v\) has a limited number of shared labels with nodes not in \(H\).

From Proposition 5 and Theorem 3, after the \(\lceil \log n \rceil\) iterations in the further improvement step (remember that \(n\bar{p}=\omega(1)\), so that \(1/\sqrt{n\bar{p}}\le e^{-2}\) when \(n\) is large enough), for any \(c>0\), there exists \(C>0\) such that \[\begin{align} | \bigcup_{k=1}^K (S^{(\lceil \log n \rceil )}_k \setminus \mathcal{I}_k)\cap H|& \le \frac{1}{(n \bar{p})^{\frac{\log n}{2}}}| \bigcup_{k=1}^K (S^{(0)}_k \setminus \mathcal{I}_k)\cap H| \nonumber \\ & \le \frac{1}{e^{ \log n}}\cdot \frac{C}{\bar{p}} \nonumber \\ & = o(1) \label{eq:second95event95ineq} \end{align}\tag{4}\] with probability at least \(1- \exp(- c n \bar{p})\), where the last equality is from \(n \bar{p} = \omega(1)\). Therefore, for any \(C>0\), no node in \(H\) can be misclassified with probability at least \(1 - \exp(-Cn \bar{p})\). Hence the number of misclassified nodes cannot exceed \(|\mathcal{I}\setminus H|\), when \(s \ge n \exp\left( -nD(\alpha, p) + \frac{n \bar{p}}{\log^3 n \bar{p}}\right)\) (the condition of Proposition 4 holds). When \(s \ge n \exp\left( -nD(\alpha, p) + \frac{n \bar{p}}{\log^3 n \bar{p}}\right)\), \[1 \le \liminf_{n\to \infty} \frac{n D(\alpha,p) - \frac{n\bar{p}}{\log (n\bar{p})^3} }{\log(n/s)} = \liminf_{n\to \infty} \frac{n D(\alpha,p)}{\log(n/s) },\label{eq:condition95}\tag{5}\] where we used \(D(\alpha, p)= \Omega(\bar{p})\) (from (A2) and Lemma 2).

Let \(\mathcal{A}\) be an event defined as: \[\begin{align} \mathcal{A} = \left\{| \cup_{k=1}^K (S^{(0)}_k \setminus \mathcal{I}_k)\cap H| \le C\frac{1}{\bar{p}}\text{ and \eqref{eq:first95event95ineq} hold} \right\}, \end{align}\] where \(C>0\) is some large enough constant. We upper bound the expected number of misclassified nodes as follows. \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[\varepsilon^\text{IAC}(n)] & = \mathop{\mathrm{\mathbb{E}}}[\varepsilon^\text{IAC}(n) | \mathcal{A}] \mathbb{P}(\mathcal{A}) + \mathop{\mathrm{\mathbb{E}}}[\varepsilon^\text{IAC}(n) | \bar{\mathcal{A}}] \mathbb{P}(\bar{\mathcal{A}}) \\ & \le \mathop{\mathrm{\mathbb{E}}}[\varepsilon^\text{IAC}(n) | \mathcal{A}] \mathbb{P}(\mathcal{A}) + n \mathbb{P}(\bar{\mathcal{A}}) \\ & \stackrel{(a)}{\le} \mathop{\mathrm{\mathbb{E}}}[\varepsilon^\text{IAC}(n) | \mathcal{A}] + o(1) \\ & \stackrel{(b)}{\le} \mathop{\mathrm{\mathbb{E}}}\left[|\mathcal{I} \setminus H | \middle| \mathcal{A}\right] + o(1) \\ & = \sum_{x = 0, \ldots, n} x \mathbb{P}(|\mathcal{I} \setminus H| = x | \mathcal{A}) + o(1) \\ & = \sum_{x = 0, \ldots, n} x \frac{\mathbb{P}(|\mathcal{I} \setminus H| = x, \mathcal{A})}{\mathbb{P}(\mathcal{A})} + o(1) \\ & \le \frac{1}{\mathbb{P}(\mathcal{A})}\sum_{x = 0, \ldots, n} x \mathbb{P}(|\mathcal{I} \setminus H| = x) + o(1) \\ & \stackrel{(c)}{\le} \frac{1}{1 - o(1)} \mathop{\mathrm{\mathbb{E}}}[|\mathcal{I} \setminus H|] + o(1) \\ & \stackrel{(d)}{\le} \frac{1}{1 - o(1)}s\left( 1 + \exp\left(- \frac{3 n \bar{p}}{4 \log^3 n \bar{p}}\right) + \exp( - \omega(n \bar{p}))\right) + o(1), \end{align}\] where \((a)\) is from Theorem 3, 2 , and \(\bar{p}=O(\log n /n)\); \((b)\) is from Proposition 5; \((c)\) is from Theorem 3; and \((d)\) is from Proposition 4. This concludes the proof.

\(\blacksquare\)

8.3 Proof of Proposition 4↩︎

We quantify the number of nodes satisfying (H1) and (H2) in 6 and 7 , respectively.

Number of nodes satisfying (H1): From Lemma 6, for any constant \(C_{\text{H1}}>0\), for each \(v \in \mathcal{I}\), \[\mathbb{P}\{ e(v,\mathcal{I}) \le C_{\text{H1}} n\bar{p}\} \ge 1-\exp(- (C_{\text{H1}} - e^L)n \bar{p}).\label{eq:h1}\tag{6}\]

Number of nodes satisfying (H2): We aim to prove that when \(v\) fulfills (H1), it also satisfies (H2) with a probability of at least \[1-\exp\left( -nD(\alpha,p)+ \frac{n \bar{p}}{ 2\log (n \bar{p})^3} \right) - \exp(-\omega(n \bar{p})).\label{eq:h2}\tag{7}\]

To achieve this, we first assert that if \(v\) meets the condition \[\sum_{i=1}^K |\mathcal{I}_i| \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i)) \le \left( 1- \frac{\log (n)^2}{ \sqrt{n}}\right) n D(\alpha,p) - \frac{n \bar{p}}{ \log (n\bar{p})^4},\label{eq:KLD}\tag{8}\] then \(v\) complies with (H2). In fact, assuming that 8 is true, we have the following:

• \(\sum_{i=1}^K \alpha_i n \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i)) \le \left( 1+ \frac{\log (n)^2}{ \sqrt{n}}\right)\sum_{i=1}^K |\mathcal{I}_i| \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i)) < n D(\alpha,p)\), because \(||\mathcal{I}_i|-\alpha_i n| \le \sqrt{n}\log(n)\) (from 2 ) and 8 holds with probability at least \(1 - \exp(-\omega(n \bar{p}))\);

• \(\sum_{i=1}^K \alpha_i n \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(j,i)) \ge n D(\alpha,p)\), since
  \(\max\left\{\sum_{i=1}^K \alpha_i \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(j,i)),\sum_{i=1}^K \alpha_i \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i))\right\} \ge D(\alpha,p)\) and
  \(\sum_{i=1}^K \alpha_i \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i)) < D(\alpha,p)\);

• \(\sum_{i=1}^K |\mathcal{I}_i| \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(j,i)) \ge \left( 1 - \frac{\log (n)^2}{ \sqrt{n}}\right)n D(\alpha,p)\), from (ii) and the fact that \(||\mathcal{I}_i|-\alpha_i n| \le \sqrt{n}\log(n)\);

• from 8 and (iii), for all \(j\neq i\), \[\begin{align} \sum_{i =1}^K \sum_{\ell =0}^L e (v, \mathcal{I}_i ,\ell ) \log \frac{p (k,i,\ell)}{p (j,i,\ell)} & =& \sum_{i=1}^K |\mathcal{I}_i| \left( \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(j,i)) -\mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i))\right) \cr &\ge& \frac{n \bar{p}}{ \log (n \bar{p})^4}. \end{align}\]

Therefore, \(v\) satisfies (H2). The remaining task is to assess the probability of event 8 , which can be done by applying Lemma 7 and proving 7 .

Based on 6 and 7 , the expected number of nodes that fail to meet either (H1) or (H2) can be upper bounded as follows. \[\begin{align} & \mathbb{E}[The number of nodes that do not satisfy either (H1) or (H2) ] \\ & \le n\exp(- (C_{\text{H1}} - e^L)n \bar{p}) + n\exp\left( -nD(\alpha,p)+ \frac{n \bar{p}}{ 2\log^3 n \bar{p}} \right) + n\exp(-\omega(n \bar{p})). \end{align}\]

From Markov’s inequality, \[\begin{align} & \mathbb{P}\left(The number of nodes that do not satisfy either (H1) or (H2) \ge \frac{1}{\bar{p}(n \bar{p})^5}\right) \\ & \le (n \bar{p})^6\exp(- (C_{\text{H1}} - e^L)n \bar{p}) + (n \bar{p})^6 \exp\left( -nD(\alpha,p)+ \frac{n \bar{p}}{ 2\log^3 n \bar{p}} \right) + (n \bar{p})^6\exp(-\omega(n \bar{p})) \\ & \le \exp\left( -nD(\alpha,p)+ \frac{n \bar{p}}{ 4\log^3 n \bar{p}} \right). \end{align}\]

We obtain the following upper bound on the expected number of \(|\mathcal{I} \setminus H|\). \[\begin{align} \frac{\mathbb{E}[|\mathcal{I} \setminus H|]}{s} & \le 1+ \frac{n \exp\left( -nD(\alpha,p)+ \frac{n \bar{p}}{ 4\log (n \bar{p})^3} \right) + n\exp\left( - \omega(n \bar{p})\right)}{s} \\ & \le 1 + \exp\left(- \frac{3 n \bar{p}}{4 \log^3 n \bar{p}}\right) + \exp( - \omega(n \bar{p})). \end{align}\] This concludes the proof of the guarantee in expectation as \(n \bar{p} = \omega(1)\).

Regarding the high probability guarantee, the subsequent Lemma 9 is instrumental in finalizing the proof, and its proof can be found in Appendix 10.4.

From Markov’s inequality, for a sufficiently large choice of \(C_{\text{H1}}\), \[\begin{align} & \mathbb{P}\left(The number of nodes that do not satisfy either (H1) or (H2) \ge s/3\right) \\ & \le \frac{\mathop{\mathrm{\mathbb{E}}}[The number of nodes that do not satisfy either (H1) or (H2)]}{s/3} \\ & \le \frac{n\exp(- (C_{\text{H1}} - e^L)n \bar{p}) + n\exp\left( -nD(\alpha,p)+ \frac{n \bar{p}}{ 2\log^3 n \bar{p}} \right) + n\exp(-\omega(n \bar{p}))}{s/3} \\ & \le \frac{n\exp(- (C_{\text{H1}} - e^L)n \bar{p}) + n\exp\left( -nD(\alpha,p)+ \frac{n \bar{p}}{ 2\log^3 n \bar{p}} \right) + n\exp(-\omega(n \bar{p}))}{\frac{n}{3} \exp\left( - n D(\alpha, p) + \frac{n \bar{p}}{\log^3 n \bar{p}}\right)} \\ & \le 6 \exp(- (C_{\text{H1}} - e^L )n \bar{p} + nD(\alpha,p)) + 3\exp\left( - \frac{n \bar{p}}{ 2\log^3 n \bar{p}} \right) + 3\exp(-\omega(n \bar{p})) \\ & \stackrel{(a)}{=} o(1), \end{align}\] where for \((a)\), we used \(nD(\alpha,p) = \mathcal{O}(n \bar{p})\) from Lemma 3. Combining with Lemma 9, \(|\mathcal{I} \setminus H| \le s\) with high probability. This concludes the proof.

\(\blacksquare\)

8.4 Proof of Proposition 5↩︎

Recall that \(\{ S^{(t)}_j\}_{1\le j\le K}\) represents the partition after the \(t\)-th improvement iteration. Note that without loss of generality, we assume the set of misclassified nodes in \(H\) after the \(t\)-th step to be \(\mathcal{E}^{(t)}=\left(\cup_k (S_k^{(t)}\setminus \mathcal{I}_k)\right)\cap H\) (it should be defined through an appropriate permutation \(\gamma\) of \(\{1,\ldots,K\}\) as \(\mathcal{E}^{(t)}=(\cup_k (S_k^{(t)}\setminus \mathcal{I}_{\gamma(k)}))\cap H\), but we omit \(\gamma\)). With this notation, we can define \(\mathcal{E}_{jk}^{(t)} = (S^{(t)}_j \cap \mathcal{I}_k)\cap H\) and \(\mathcal{E}^{(t)}= \bigcup_{j,k:j \neq k} \mathcal{E}_{jk}^{(t)}\). During each improvement step, nodes move to the most likely cluster (according to the log-likelihood defined in the IAC algorithm). As a result, for all \(i \in [K]\), \[\begin{align} 0\le &\sum_{j,k:j\neq k}\sum_{v \in \mathcal{E}_{jk}^{(t+1)}} \sum_{i=1}^K\sum_{\ell =0}^L e(v, S^{(t)}_i,\ell) \log \frac{\hat{p}(j,i,\ell)}{\hat{p}(k,i,\ell)} \cr \le &\sum_{j,k:j\neq k}\sum_{v \in \mathcal{E}_{jk}^{(t+1)}} \sum_{i=1}^K\sum_{\ell =0}^L e(v, S^{(t)}_i,\ell) \log \frac{p(j,i,\ell)}{p(k,i,\ell)} + |\mathcal{E}^{(t+1)}|(n\bar{p})^{1-\kappa}\log(n\bar{p})^3 \tag{9} \\ \le &\sum_{j,k:j\neq k}\sum_{v \in \mathcal{E}_{jk}^{(t+1)}} \sum_{i=1}^K\sum_{\ell =0}^L e(v, \mathcal{I}_i,\ell) \log \frac{p(j,i,\ell)}{p(k,i,\ell)} \cr & + \sum_{w\in \mathcal{E}^{(t+1)}} e(w, \mathcal{E}^{(t)})\log (2\eta) + 5|\mathcal{E}^{(t+1)}|\frac{n \bar{p}}{\log^5 n \bar{p}}\tag{10} \\ \le &-\frac{n\bar{p}}{\log^4 n\bar{p}} |\mathcal{E}^{(t+1)}| + \sum_{w\in \mathcal{E}^{(t+1)}} e(w, \mathcal{E}^{(t)},\ell)\log (2\eta) +5|\mathcal{E}^{(t+1)}|\frac{n \bar{p}}{\log^5 n \bar{p}}\tag{11} \\ \le &-\frac{n\bar{p}}{\log^4 n\bar{p}}|\mathcal{E}^{(t+1)}| + \sqrt{ |\mathcal{E}^{(t)}||\mathcal{E}^{(t+1)}|n\bar{p} \log n\bar{p}} + 6|\mathcal{E}^{(t+1)}|\frac{n \bar{p}}{\log^5 n \bar{p}}. \tag{12} \end{align}\] Hence, based on the aforementioned inequalities, we deduce that \[\frac{|\mathcal{E}^{(t+1)}|}{|\mathcal{E}^{(t)}|} \le \frac{\log^{11} n\bar{p}}{n\bar{p}} \le \frac{1}{\sqrt{n\bar{p}}}.\] Subsequently, we will validate each step involved in the prior analysis.

Utilizing the inequality \(\log(1+x)\le x\), when \(p(j,i,\ell)-|\hat{p}(j,i,\ell)-p(j,i,\ell)| >0\), \[\left|\log \frac{\hat{p}(j,i,\ell)}{p(j,i,\ell)} \right|\le\frac{|\hat{p}(j,i,\ell)-p(j,i,\ell)|}{p(j,i,\ell)-|\hat{p}(j,i,\ell)-p(j,i,\ell)|}.\] Therefore, to prove 9 , we merely need to present an upper bound for \(|\hat{p}(j,i,\ell)-p(j,i,\ell)|\). Applying the triangle inequality, \[\begin{align} & |\hat{p}(j,i,\ell)-p(j,i,\ell)| \nonumber \\ & = \frac{\left|e(S^{(0)}_i, S^{(0)}_j ,\ell) - p(j,i,\ell) |S^{(0)}_i| |S^{(0)}_j| \right|}{|S^{(0)}_i| |S^{(0)}_j|} \nonumber \\ &\le \frac{\left|e(S^{(0)}_i, S^{(0)}_j ,\ell) -\mathbb{E}[e(S^{(0)}_i, S^{(0)}_j,\ell)] \right| + \left| \mathbb{E}[e(S^{(0)}_i, S^{(0)}_j,\ell)] - p(j,i,\ell) |S^{(0)}_i| |S^{(0)}_j| \right|}{|S^{(0)}_i| |S^{(0)}_j|}. \label{eq:tpp} \end{align}\tag{13}\]

Firstly, we determine an upper bound for \(\left|e(S^{(0)}_i, S^{(0)}_j ,\ell) -\mathbb{E}[e(S^{(0)}_i, S^{(0)}_j,\ell)] \right|\). Let \(\mathcal{S}\) represent a partition such that \[\left|\bigcup_{k=1}^K \mathcal{I}_k \setminus S_k \right| \le \xi = O\left(\frac{\log(n\bar{p})^2}{\bar{p}} \right)\quad \text{for all} \quad \{S_k \}_{1\le k \le K} \in \mathcal{S}.\] Following this, \[\begin{align} \left|\mathcal{S} \right| & \le \binom{n}{\xi} K^{\xi} \nonumber \\ &\le \left(\frac{K e n}{\xi}\right)^\xi \nonumber \\ & = \exp\left(O\left(\frac{\log(n\bar{p})^3}{\bar{p}} \right) \right).\label{eq:sizeS} \end{align}\tag{14}\] For every \(\{S_k \}_{1\le k \le K} \in \mathcal{S}\) and for all \(\ell \ge 1\) and \(1\le i,j \le K\), \(e(S_i, S_j ,\ell)\) represents the sum of \(|S_i||S_j|\) (or \(\frac{|S_i|^2}{2}\) when \(i=j\)) independent Bernoulli random variables. Given that the variance of \(e(S_i, S_j ,\ell)\) is less than \(n^2\bar{p}\), by applying the Chernoff inequality (for example, Theorem 2.1.3 in [41]), with a probability of at least \(1-\exp\left(-\Theta\left(\frac{\log (n\bar{p})^4}{\bar{p}}\right) \right)\), \[\left|e(S_i, S_j ,\ell) - \mathbb{E}[e(S_i, S_j,\ell)]\right| \le n \log (n\bar{p})^2 \quadfor all\quad i,j,\ell.\label{eq:chernoffS}\tag{15}\]

From 14 and 15 and union bound, with probability at least \(1 - \exp\left( - \Theta\left( \frac{\log(n \bar{p})^4}{\bar{p}} \right)\right)\), \[\left|e(S_i, S_j ,\ell) - \mathbb{E}[e(S_i, S_j,\ell)]\right| \le n \log (n\bar{p})^2 \quadfor all\quad i,j,\ell \quadand\quad \{S_k \}_{1\le k \le K} \in \mathcal{S}.\] Since \(\{S^{(0)}_k \}_{1\le k \le K} \in \mathcal{S}\), from the above inequality, \[\left|e(S^{(0)}_i, S^{(0)}_j ,\ell) - \mathbb{E}[e(S^{(0)}_i, S^{(0)}_j,\ell)]\right| \le n \log (n\bar{p})^2 \quadfor all\quad i,j,\ell,\label{eq:6}\tag{16}\] with at least probability \(1 - \exp\left( - \Theta\left( \frac{\log(n \bar{p})^4}{\bar{p}} \right)\right)\).

We now devote to the remaining part of 13 . Since for any \(C>0\), \(|\mathcal{E}^{(0)} | = O\left( \frac{\log (n\bar{p})^2}{\bar{p}}\right)\) with at least probability \(1 - \exp\left( - C n \bar{p}\right)\) from Theorem 3, \[\left|\mathbb{E}[e(S^{(0)}_i, S^{(0)}_j,\ell)] - |S^{(0)}_i||S^{(0)}_j|p(i,j,\ell)\right| \le \eta |\mathcal{E}^{(0)} |n p(i,j,\ell) =O(n \log (n\bar{p})^2). \label{eq:7}\tag{17}\]

Observe that since \(\bar{p} = \mathcal{O}(\frac{\log n}{n})\) and \(n \bar{p} = \omega(1)\), \[\begin{align} \frac{n \bar{p}}{\left(\frac{\log (n \bar{p})^4}{\bar{p}}\right)} & = \mathcal{O}\left(\frac{(\log n)n \bar{p}}{n \log(n \bar{p})^4} \right) \nonumber \\ & = \mathcal{O} \left(\frac{\log n^2}{n \log (\log n)^4}\right) \nonumber \\ & = o(1). \label{eq:comp95prob} \end{align}\tag{18}\] Considering 13 , 16 , 17 , and \(\eqref{eq:comp95prob}\), for any \(C>0\), with a probability of at least \(1 - \exp\left( - C n \bar{p}\right)\), \[|\hat{p}(j,i,\ell)-p(j,i,\ell)| = O(\log (n\bar{p})^2/n) \quad\text{for all}\quad i,j,\ell,\] which leads to the conclusion that: \[\begin{align} \left|\log \frac{\hat{p}(j,i,\ell)}{p(j,i,\ell)} \right| &\le&\frac{|\hat{p}(j,i,\ell)-p(j,i,\ell)|}{p(j,i,\ell)-|\hat{p}(j,i,\ell)-p(j,i,\ell)|} = O\left(\frac{\log (n\bar{p})^2}{np(j,i,\ell)} \right) \quadfor all\quad i,j,\ell. \end{align}\] Given that \(e(v, S^{(t)}_i,\ell) \le e(v,\mathcal{I}) \le 10 \eta n\bar{p}L\) as per (H1) and \(np(j,i,\ell) \ge (n\bar{p})^\kappa\) according to (A3), for all \(v\in \Gamma\) and \(i,j,k\), \[\sum_{\ell=0}^L e(v, S^{(t)}_i,\ell)\left| \log \frac{\hat{p}(j,i,\ell)}{\hat{p}(k,i,\ell)} - \log \frac{p(j,i,\ell)}{p(k,i,\ell)} \right| = O\left(\log (n\bar{p})^2 (n \bar{p})^{1-\kappa} \right).\]

As \(\log\frac{p(j,i,0)}{p(k,i,0)} = O(\bar{p})\) holds for all \(i,j,k\) and \(|\mathcal{E}^{(t)}| = O(\log (n\bar{p})^2/\bar{p})\), \[\begin{align} & \sum_{i=1}^K\sum_{\ell =0}^L e(v, S^{(t)}_i,\ell) \log \frac{p(j,i,\ell)}{p(k,i,\ell)} \\ & =\sum_{i=1}^K \left(|S^{(t)}_i|\log\frac{p(j,i,0)}{p(k,i,0)}+ \sum_{\ell =1}^L e(v, S^{(t)}_i,\ell) \log \frac{p(j,i,\ell)p(k,i,0)}{p(k,i,\ell)p(j,i,0)} \right) \cr & \le\sum_{i=1}^K \left(|\mathcal{I}_i|\log\frac{p(j,i,0)}{p(k,i,0)}+ \sum_{\ell =1}^L e(v, S^{(t)}_i,\ell) \log \frac{p(j,i,\ell)p(k,i,0)}{p(k,i,\ell)p(j,i,0)} \right) + \log( n \bar{p})^3 \cr & \le \sum_{i=1}^K\sum_{\ell=0}^L e(v,\mathcal{I}_i,\ell)\log\frac{p(j,i,\ell)}{p(k,i,\ell)}+ \sum_{i=1}^K\sum_{\ell =1}^L e(v, \mathcal{I}_i \setminus S^{(t)}_i,\ell)\log (2\eta ) + \log( n \bar{p})^3 \cr &=\sum_{i=1}^K\sum_{\ell=0}^L e(v,\mathcal{I}_i,\ell)\log\frac{p(j,i,\ell)}{p(k,i,\ell)}+ \left( e(v, \mathcal{E}^{(t)}) + e(v,\mathcal{I}\setminus H) \right)\log (2\eta ) + \log( n \bar{p})^3 \cr &\le\sum_{i=1}^K\sum_{\ell=0}^L e(v,\mathcal{I}_i,\ell)\log\frac{p(j,i,\ell)}{p(k,i,\ell)}+ \log(2\eta ) e(v, \mathcal{E}^{(t)}) + \frac{4 n \bar{p}}{\log^5 n \bar{p}}, \end{align}\] where the last inequality arises from (H3), specifically, from the condition \(e(v,\mathcal{I}\setminus H) \le \frac{2 n\bar{p}}{\log^5n \bar{p}}\) when \(v\) belongs to \(H\).

Given that \(\mathcal{E}^{(t+1)} \subset H\) and all \(v \in H\) fulfill (H2), every \(v\) in \(\mathcal{E}_{jk}^{(i+1)}\) meets the following condition: \[\sum_{i =1}^K\sum_{\ell=0}^L e(v, \mathcal{I}_i , \ell ) \log \frac{p(j,i,\ell)}{p(k,i,\ell)} \le -\frac{n\bar{p}}{\log^4 n\bar{p}} .\]

Define \(\bar{\Gamma}=\{v: e(v,\mathcal{I}) \le C_{\text{H1}} n\bar{p} \}\) and let \(A^{\ell}_{\bar{\Gamma}}\) represent the modified matrix of \(A^{\ell}\) with elements in rows and columns corresponding to \(w \notin \bar{\Gamma}\) set to 0. \(\bar{\Gamma}\) consists of all nodes that meet (H1), and \(H\) is a subset of \(\bar{\Gamma}\). Consider \(X_{\bar{\Gamma}} = \sum_{\ell=1}^L (A^{\ell}_{\bar{\Gamma}} - M_{\bar{\Gamma}}^{\ell})\). We obtain: \[\sum_{v \in \mathcal{E}^{(t+1)}} (e(v, \mathcal{E}^{(t)})-\mathbb{E}[e(v,\mathcal{E}^{(t)})]) \le 1_{\mathcal{E}^{(t)}}^{T} \cdot X_{\bar{\Gamma}}\cdot 1_{\mathcal{E}^{(t+1)}},\] where \(1_S\) denotes a vector where the \(v\)-th component is 1 if \(v \in S\) and 0 otherwise. Given that \(\mathbb{E}[e(v,\mathcal{E}^{(t)})] \le \bar{p} L |\mathcal{E}^{(t)}|\) and for any \(C > 0\), the \(\| X_{\bar{\Gamma}}\|_2 \le \sqrt{n\bar{p}\log n \bar{p}}\) holds with a probability of at least \(1 - \exp(- Cn \bar{p})\) according to Lemma [lm:spectralresults], \[\begin{align} \sum_{v \in \mathcal{E}^{(t+1)}} e(v, \mathcal{E}^{(t)})=& \sum_{v \in \mathcal{E}^{(t+1)}} \left(e(v, \mathcal{E}^{(t)})-\mathbb{E}[e(v, \mathcal{E}^{(t)})]\right) + \bar{p} L |\mathcal{E}^{(t)}||\mathcal{E}^{(t+1)}|\cr \le & \;\|1_{\mathcal{E}^{(t)}}^{T} \cdot X_{\bar{\Gamma}} \cdot 1_{\mathcal{E}^{(t+1)}}\|_2 + |\mathcal{E}^{(t+1)}|\log(n\bar{p})\cr \le& \;\|1_{\mathcal{E}^{(t)}}^{T}\|_2 \| X_{\bar{\Gamma}}\|_2 \| 1_{\mathcal{E}^{(t+1)}}\|_2 + |\mathcal{E}^{(t+1)}|\log(n\bar{p})\cr \le& \;\sqrt{ |\mathcal{E}^{(t)}||\mathcal{E}^{(t+1)}|n\bar{p} \log (n\bar{p})}+ |\mathcal{E}^{(t+1)}|\log(n\bar{p}). \end{align}\] This concludes the proof. \(\blacksquare\)

9 Proof of Theorem 3↩︎

First, we show a spectral analysis on \(A_\Gamma^\ell - M_\Gamma^\ell\) by extending the technique by [42], [43]. The proof of Lemma [lm:spectralresults] is given in Appendix 10.5.

Therefore, for any \(C>0\), there exists \(C'>0\) such that: \[\begin{align} \| \bar{A} - M_\Gamma\| & \le \sum_{\ell=1}^L \|X_\Gamma^\ell\| \\ & \le C' \sqrt{n\bar{p}}, \end{align}\] with probability at least \(1 - \exp(- Cn \bar{p})\). Next, we prove the lower bound on the column distance of \(M_\Gamma\). The proof of Lemma [lm:columndistance] is given in Appendix 10.6.

Furthermore, we can show that the iterative power method with the singular value thresholding procedure estimates the number of clusters correctly and the matrix \(\hat{A}\) is an accurate rank-\(K\) approximation of the matrix \(\bar{A}\) with sufficiently high probability. The proof is in Appendix 10.7.

We can prove the theorem as follows. The proof draws inspiration from the proof of Theorem 4 in [14]. However, we obtain a high probability certificate of \(1 - \exp(-Cn \bar{p})\) for any \(C > 0\). Throughout this section, we assume \(\hat{K} =K\) (for any \(c>0\), the event occurs with probability at least \(1 - \exp(- c n \bar{p})\) from Theorem 3) and let \(\gamma(k):=\arg \min_{\theta} \left| \bigcup_{k=1}^{K} {S}_{k} \setminus \mathcal{I}_{\theta(k)} \right|\). Define \(M_{\Gamma,\gamma(k)}\) as \(M_{\Gamma,\gamma(k)}:= M_{\Gamma, v}\), where \(v\) is a node that satisfies \(v \in \mathcal{I}_{\gamma(k)}\). According to Lemma [lm:columndistance], there exists a constant \(C'>0\) such that, with probability at least \(1 - \exp(- \omega(n))\), \[\begin{align} \varepsilon^\pi(n) \cdot C' n \bar{p}^2 &= \left| \bigcup_{k=1}^{K} {S}_{k} \setminus \mathcal{I}_{\gamma(k)} \right| \cdot C' n \bar{p}^2 \\ & \leq \sum_{k=1}^{K} \sum_{v \in {S}_{k} \setminus \mathcal{I}_{\gamma(k)}} ||M_{\Gamma, v} - M_{\Gamma,\gamma(k)}||_2^2\\ & \leq 2 \sum_{k=1}^{K} \sum_{v \in {S}_{k} \setminus \mathcal{I}_{\gamma(k)}}\left(||M_{\Gamma, v} - \xi_{k}||_2^2 + ||\xi_{k} - M_{\Gamma,\gamma(k)}||_2^2 \right)\\ & \leq 4 \sum_{k=1}^{K} \sum_{v \in {S}_{k} \setminus \mathcal{I}_{\gamma(k)}} ||M_{\Gamma, v} - \xi_{k}||_2^2\\ & \leq 8 \sum_{k=1}^{K} \sum_{v \in {S}_{k} \setminus \mathcal{I}_{\gamma(k)}} \left( ||M_{\Gamma,v} - \hat{A}_v||_2^2 + ||\hat{A}_v - \xi_{k}||_2^2\right)\\ & \leq 8||M_\Gamma - \hat{A}||_F^2 + 8 r_{t^{*}}, \end{align}\] where \(||\cdot||_F\) denotes the Frobenius norm of a matrix. To complete the proof, we need: \[\begin{align} ||M_\Gamma - \hat{A}||_F^2 & = \mathcal{O} \left(n \bar{p}\right) \tag{19}\\ r_{t^{*}} &= \mathcal{O} \left( n \bar{p}\right) \tag{20}, \end{align}\] with the high probability guarantee.

We first prove 19 . From the equation (1.4) of [44], \[\begin{align} \sigma_{k+1} = \min_{\text{rank}(X) \le k} \|A - X\|_2, \end{align}\] where \(\sigma_{k}\) is the \(k\)-th largest singular value of the matrix \(A\).

For any matrix \(A\) of rank \(K\), it holds that \(||A||_F^2 \leq K||A||_2^2\). Since the rank of the matrix \(\hat{A}\) and \(M_\Gamma\) are \(K\), the rank of the matrix \(\hat{A} - M_\Gamma\) is at most \(2 K\). Then, Lemma [lem:iterative95power95svt] implies, for any \(c>0\), there exist constants \(C_1, C_2>0\) such that with probability at least \(1 - 1/n^c\), \[\begin{align} ||M_\Gamma - \hat{A}||_F^2 & \le 2 K \| M_\Gamma - \hat{A}\|_2^2 \\ & \le 4K\| M_\Gamma -A_\Gamma\|_2^2 + 4K\| A_\Gamma - \hat{A}\|_2^2 \\ & \le 4K\| M_\Gamma -A_\Gamma\|_2^2 + 4K C_1 \sigma_{K+1}^2, \\ & = 4K\| M_\Gamma -A_\Gamma\|_2^2 + 4KC_1 \left(\min_{\text{rank}(X) \le K} \|A_\Gamma - X\|_2\right)^2 \\ & \le4K\| M_\Gamma -A_\Gamma\|_2^2, + 4KC_1 \| M_\Gamma -A_\Gamma\|_2^2 \\ & \le C_2 K\| M_\Gamma -A_\Gamma\|_2^2. \end{align}\] Therefore, together with Lemma [lm:spectralresults], for any \(c>0\), there exists a constant \(C>0\) such that \[||M_\Gamma - \hat{A}||_F^2 \leq C n \bar{p}\] with probability at least \(1 - \exp(-cn \bar{p})\).

Next, we prove 20 . It is sufficient to show that there exists \(i_t \in \{1,2,...,\lfloor \log n \rfloor \}\) such that \(r_t = \mathcal{O}\left( n \bar{p}\right)\). First, by Lemma [lm:spectralresults], for any \(C>0\), there exists a positive constant \(D_1>0\) such that \[\begin{align} ||\hat{A} - M_\Gamma ||_2^2 \leq 8 D_1 n \bar{p} \label{eq:bound95on95frobenius} \end{align}\tag{21}\] with probability at least \(1 - \exp\left(-Cn \bar{p}\right)\). By Lemma 8, for any constant \(D_2> \frac{20 K}{\alpha_1}\), there exists \(i_t \in \{1,...,\lfloor \log n \rfloor \}\) such that with probability at least \(1 - \exp\left( - \omega(n)\right)\), \[\begin{align} 32 {D_2} D_1 \bar{p}\leq i_t \frac{\widetilde{p}}{100} \leq \frac{64 \eta}{1 - 1/e}D_2 D_1 \bar{p} \end{align}\]

Define sets of nodes \(I_k\) and \(W\) as \[\begin{align} I_k &= \left\{ v \in \mathcal{I}_k \cap \Gamma : ||\hat{A}_v - M_{\Gamma, k}||_2^2 \leq \frac{1}{4} i_t \frac{\widetilde{p}}{100}\right\}\\ W &= \left\{ v \in \Gamma : ||\hat{A}_v - M_{\Gamma, k}||_2^2 \geq 4 i_t \frac{\widetilde{p}}{100}, \textrm{ for all } k \in [K]\right\}. \end{align}\] These sets have the following properties:

• For all \(v \in I_k\), \(I_k \subset Q_v^{(i_t)}\)

• For all \(v, v' \in I_k\), \(||\hat{A}_v - \hat{A}_{v'}||_2^2 \leq 2 ||\hat{A}_v - M_{\Gamma,k}||_2^2 + 2||\hat{A}_{v'} - M_{\Gamma,k}||_2^2 \leq i_t \frac{\widetilde{p}}{100}\)

• For all \(v \in W\), \((\bigcup_{k=1}^{K} I_k ) \cap Q_{v}^{(i_t)} = \emptyset\)

  • since for all \(v' \in \cup_{k=1}^K I_k\), \(||\hat{A}_v - \hat{A}_{v'}||_2^2 \geq \frac{1}{2} ||\hat{A}_v - M_{\Gamma,\sigma(v')}||_2^2 - ||\hat{A}_{v'} - M_{\Gamma,\sigma(v')}||_2^2 > i_t \frac{\widetilde{p}}{100}\).

From (21 ), we have \[\begin{align} \left|\Gamma \setminus \left(\bigcup_{k=1}^{K} I_k\right)\right| \left(\frac{1}{4} i_t \frac{\widetilde{p}}{100}\right) &\leq \sum_{v \in \Gamma \setminus \left(\bigcup_{k=1}^{K} I_k\right)} \|\hat{A}_v - M_{\Gamma, \sigma(v)}\|_2^2 \\ & \leq \| \hat{A} - M_\Gamma\|_F^2 \\ & \leq 2 K \| \hat{A} - M_\Gamma\|_2^2 \\ & \leq 16 K D_1 n \bar{p}, \end{align}\] with probability at least \(1 - \exp(-Cn \bar{p})\). Thus, we have \[\begin{align} \left|\Gamma \setminus \left(\bigcup_{k=1}^{K} I_k \right)\right| &\leq 16 K D_1 n \bar{p} \left(\frac{1}{4} i_t \frac{\widetilde{p}}{100}\right)^{-1} \\ &\leq \frac{2nK}{D_2} \\ &< n\frac{\alpha_1}{10}, \end{align}\] with probablity at least \(1 - \exp(-Cn \bar{p}(1 + o(1)))\). Therefore, we can deduce that

• For all \(v \in W\), \(|Q_v^{(i_t)}| \leq n\frac{\alpha_1}{10}\)

• For all \(v \in \bigcup_{k=1}^{K} I_k\), \(|Q_v^{(i_t)}|\geq \alpha_1 n - \lfloor n \exp(-n\widetilde{p})\rfloor - n\frac{\alpha_1}{10}\geq \frac{4}{5}\alpha_1 n\)

with probability at least \(1 - \exp(-Cn \bar{p}(1 + o(1)))\).

For each \(k \in [K]\), the probability that \(\mathcal{V}_R \cap I_k = \emptyset\) is at most: \[\begin{align} \left(1 - \frac{4}{5} \alpha_1\right)^{\lceil (\log n)^2 \rceil} \le \frac{1}{n^{C \log n}}, \end{align}\] where \(C>0\) is a constant depends only on \(\alpha_1\). Thus, for any \(c'>0\), \(\mathcal{V}_R\) contains at least one node from \(I_k\) for all \(k\in [K]\) with probability at least \(1 - \exp(-c' n \bar{p}(1+ o(1)))\). Therefore, any \(v \in W\) will not be assigned as \(v_k^{*}\), with probability at least \(1 - \exp(-Cn \bar{p}(1 + o(1)))\). It implies that \(||\hat{A}_{v_{k}^{*}}- M_{\Gamma, \gamma(k)}||_2^2 \leq 4 i_t \frac{\widetilde{p}}{100}\) for all \(k \in [K]\) with probability at least \(1 - \exp(-Cn \bar{p}(1 + o(1)))\). Regarding the centroid \(\xi_{k}^{i_t}\) of the clusters, since \(\hat{A}_v\) is within \(\sqrt{5 i_t \frac{\widetilde{p}}{100}}\) from \(M_{\Gamma, \gamma(k)}\) in the Euclidean distance for all \(v \in T_k^{i_t}\), \[\begin{align} ||\xi_{k}^{i_t} - M_{\Gamma, \gamma(k)}||_2^2 &\leq 5 i_t \frac{\widetilde{p}}{100} \\ &= \frac{320 \eta D_1 D_2 }{1 - 1/e} \bar{p}, \quad \forall k \in [K], \end{align}\] with probability at least \(1- \exp(-Cn \bar{p}(1+o(1)))\). Thus, \[\begin{align} r_{i_t} &= \sum_{k=1}^K \sum_{v\in T_{k}^{(i_t)}} ||\Hat{A}_v - \xi_{k}^{(i_t)}||^2_2 \\ & \leq \sum_{k=1}^K \sum_{v\in \mathcal{I}_k \cap \Gamma} ||\Hat{A}_v - \xi_{k}^{(i_t)}||^2_2 \\ & \leq 2 \sum_{k=1}^K \sum_{v\in \mathcal{I}_k \cap \Gamma} \left( ||\Hat{A}_v - M_{\Gamma,v}||_2^2 + ||\xi_{k}^{(i_t)} - M_{\Gamma,v}||_2^2\right) \\ & \leq \left(32 K D_1 + \frac{640 \eta D_1 D_2 }{1 - 1/e}\right) n \bar{p} \;, \end{align}\] with probability at least \(1 - \exp(-Cn \bar{p}(1+o(1)))\). This concludes the proof of Theorem 3. \(\blacksquare\)

10 Proofs of Lemmas and Corollary↩︎

10.1 Proof of Lemma 6↩︎

Let \(\{X_i\}\) be Bernoulli i.i.d. random variable with mean \(\bar{p}\). First, for any \(C_1>0\) and for every \(v\in \mathcal{I}\), by Markov’s inequality, \[\begin{align} \mathbb{P}\left\{ e(v, \mathcal{I}) \geq C_1 n \bar{p} \right\} & \leq \inf_{\lambda \geq 0} \frac{\mathop{\mathrm{\mathbb{E}}}[\exp(\lambda e(v, \mathcal{I}))]}{\exp(\lambda C_1 n \bar{p})} \\ & \leq \inf_{\lambda \geq 0} \frac{\mathop{\mathrm{\mathbb{E}}}\left[ \exp(\lambda L \sum_{i=1}^n X_i ) \right]}{\exp(\lambda C_1 n \bar{p}) } \\ & = \inf_{\lambda \geq 0} \frac{ \prod_{i=1}^n \left( \bar{p} (\exp(\lambda L ) -1) +1\right) }{\exp(\lambda C_1 n \bar{p})} \\ & \leq \inf_{\lambda \geq 0} \frac{ \prod_{i=1}^n \left( \bar{p} \exp(\lambda L ) +1 \right) }{\exp(\lambda C_1 n \bar{p})} \\ & \leq \inf_{\lambda \geq 0} \frac{ \prod_{i=1}^n \exp( \bar{p} \exp(\lambda L ) }{\exp(\lambda C_1 n \bar{p})} \\ & \leq \inf_{\lambda \geq 0} \frac{ \exp( n \bar{p} \exp(\lambda L)) }{\exp(\lambda C_1 n \bar{p})} \\ & \leq \exp (- (C_1 - e^L) n \bar{p})\; \end{align}\] This concludes the proof. \(\blacksquare\)

10.2 Proof of Lemma 7↩︎

Consider \(\mathcal{X}\) as a collection of \(K \times (L+1)\) matrices, defined as follows: \[\mathcal{X} = \left\{\boldsymbol{x}\in \mathbb{Z}^{K\times (L+1)}:\quad \sum_{i=1}^{K}\sum_{\ell=1}^{L} x_{i,\ell} \le 10 \eta n\bar{p}L ,\quadand\quad \sum_{\ell=0}^{L} x_{i,\ell} = |\mathcal{I}_i| \quadfor all\quad 1\le i\le K \right\}.\] To simplify notation, we employ \([\frac{x_{i,\ell}}{|\mathcal{I}_i|}]\) in place of \([\frac{x_{i,\ell}}{|\mathcal{I}_i|}]_{0\le \ell \le L}\) to denote the probability mass vector for labels defined by \(x_{i}\). We also use \(e(v)\) to represent the \(K \times (L+1)\) matrix, where the \((i,\ell)\)-th element corresponds to \(e(v,\mathcal{I}_i,\ell)\). Consequently, for \(v \in \mathcal{I}_k\), \[\begin{align} \mathbb{P}&\left\{ \left( \sum_{i=1}^K |\mathcal{I}_i| \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i) ) \ge nD \right)\cap\bigg( e(v,\mathcal{I}) \le 10 n\bar{p}L\bigg) \right\} \cr = & \;\sum_{\boldsymbol{x}\in \mathcal{X}} \mathbb{P}\left\{e(v)=\boldsymbol{x} \right\} \mathbb{P}\left\{ \sum_{i=1}^K |\mathcal{I}_i| \mathop{\mathrm{\textrm{kl}}}(\mu(v,\mathcal{I}_i),p(k,i) ) \ge nD \bigg| e(v)=\boldsymbol{x} \right\} \cr \le& \;\sum_{\boldsymbol{x}\in \mathcal{X}} \mathbb{P}\{e(v)=\boldsymbol{x} \}\frac{\exp\left(\sum_{i=1}^K |\mathcal{I}_i| \mathop{\mathrm{\textrm{kl}}}([\frac{x_{i,\ell}}{|\mathcal{I}_i|}],p(k,i) )\right)}{\exp(n D)} \cr \le& \;\sum_{\boldsymbol{x}\in \mathcal{X}} \mathbb{P}\{e(v)=\boldsymbol{x} \}\frac{\prod_{i=1}^{K}\prod_{\ell=0}^{L}\left(\frac{x_{i,\ell}}{|\mathcal{I}_i| p(k,i,\ell)} \right)^{x_{i,\ell}}}{\exp(n D)} \cr \stackrel{(a)}{\le}&\;\frac{1}{\exp(n D)} \sum_{\boldsymbol{x}\in \mathcal{X}} \prod_{i=1}^K\left( \left(1-\frac{\sum_{\ell=1}^L x_{i,\ell}}{|\mathcal{I}_i| }\right)^{x_{i,0}}\exp( \sum_{\ell =1 }^L x_{i,\ell} ) \right)\cr =&\;\frac{1}{\exp(n D)} \sum_{\boldsymbol{x}\in \mathcal{X}} \prod_{i=1}^K\exp\left((|\mathcal{I}_i|-\sum_{\ell=1}^L x_{i,\ell}) \log\left(1-\frac{\sum_{\ell=1}^L x_{i,\ell}}{|\mathcal{I}_i| }\right) + \sum_{\ell =1 }^L x_{i,\ell} \right)\cr \le \;& \frac{1}{{\exp(n D)}}\sum_{\boldsymbol{x}\in \mathcal{X}} \prod_{i=1}^K\exp\left( \frac{(\sum_{\ell=1}^L x_{k,\ell})^2}{|\mathcal{I}_i|} \right) \cr \le\;& \frac{(10\eta n\bar{p}L)^{KL} \exp(100 \eta^2 n\bar{p}^2L^2/\alpha_1)}{\exp(n D)} \cr =&\; \exp \left(-nD + KL\log(10\eta Ln\bar{p}) +\frac{100 \eta^2 n\bar{p}^2L^2}{\alpha_1} \right), \end{align}\] where \((a)\) comes from the subsequent inequality: \[\begin{align} \mathbb{P}\{e(v,\mathcal{I}_i,\ell)=x_{i,\ell} \quadfor all\quad i,\ell \} \le&\prod_{i=1}^K\left( p(k,i,0)^{x_{i,0}} \prod_{\ell=1}^L \binom{|\mathcal{I}_i|}{ x_{i,\ell}} p(k,i,\ell)^{x_{k,\ell}}\right) \cr \le&\prod_{i=1}^K\left( p(k,i,0)^{x_{i,0}} \prod_{\ell=1}^L \left(\frac{e |\mathcal{I}_i| }{x_{i,\ell}}\right)^{x_{i,\ell}} p(k,i,\ell)^{x_{i,\ell}}\right). \end{align}\] This concludes the proof. \(\blacksquare\)

10.3 Proof of Lemma 8↩︎

First, we evaluate the probability of the event \(\widetilde{p} \leq C_2 \bar{p}\) does not hold. Let \(\{X_i\}\) be Bernoulli i.i.d. random variables with mean \(\bar{p}\). We have: \[\begin{align} \mathbb{P}\left\{\widetilde{p} \geq C_2 \bar{p}\right\} & = \mathbb{P}\left\{ \frac{2}{n(n-1)} \sum_{\ell=1}^L \sum_{ v,w \in \mathcal{I} : v>w} A_{vw}^\ell \geq C_2 \bar{p} \right\} \nonumber \\ & \leq \mathbb{P}\left\{ \frac{2L}{n(n-1)} \sum_{ i=1}^{n(n-1)/2} X_i \geq C_2 \bar{p} \right\} \nonumber \\ & \leq \inf_{\lambda \geq 0}\frac{\mathop{\mathrm{\mathbb{E}}}\exp\left( \lambda L \sum_{ i=1}^{n(n-1)/2} X_i \right)}{\exp\left( \lambda \frac{n (n-1)}{2} C_2 \bar{p} \right)} \nonumber \\ & = \inf_{\lambda \geq 0}\frac{\prod_{i=1}^{n(n-1)/2} \left( p (\exp(\lambda L) -1) + 1 \right)}{\exp\left( \lambda \frac{n (n-1)}{2} C_2 \bar{p} \right)} \nonumber\\ & \leq \inf_{\lambda \geq 0} \frac{\prod_{i=1}^{n(n-1)/2} \left( p \exp(\lambda L) + 1 \right)}{\exp\left( \lambda \frac{n (n-1)}{2} C_2 \bar{p} \right)} \nonumber\\ & \leq \inf_{\lambda \geq 0} \frac{\exp\left(\frac{n(n-1)}{2} p \exp(\lambda L) \right)}{\exp\left( \lambda \frac{n (n-1)}{2} C_2 \bar{p} \right)} \nonumber \\ & \leq \exp\left( - (C_2 - e^L)\frac{n(n-1)}{2} \bar{p} \right) \nonumber \\ & \leq \exp\left(-\frac{C_2 -e^L}{4} n^ 2 \bar{p}\right)\;. \label{eq:Lemma95phat95ubineq} \end{align}\tag{22}\]

Next, we evaluate the probability that the event \(C_1 \bar{p} \leq \widetilde{p}\) does not hold. Let \(\underline{p} \mathrel{\vcenter{:}}= \min_{i,j, \ell \ge 1} p(i,j,\ell)\). Let \(\{Y_i\}\) be Bernoulli i.i.d. random variables with mean \(\underline{p}\). We have: \[\begin{align} \mathbb{P}\left\{ \widetilde{p} \leq C_1 \bar{p} \right\} & = \mathbb{P}\left\{ - \frac{2}{n(n-1)}\sum_{\ell = 1}^L \sum_{v,w \in \mathcal{I}: v>w} A_{vw} \geq - C_1 \bar{p} \right\} \nonumber \\ & \leq \mathbb{P}\left\{ - \frac{2}{n(n-1)} L \sum_{i=1}^{n(n-1)/2} Y_i \geq - C_1 \bar{p} \right\} \nonumber \\ & \leq \inf_{\lambda\geq 0} \frac{\mathop{\mathrm{\mathbb{E}}}\exp\left(- \lambda L \sum_{i=1}^{n(n-1)/2} Y_i \right) }{\exp\left( -\lambda \frac{n(n-1)}{2} C_1 \bar{p} \right)} \nonumber \\ & \leq \inf_{\lambda\geq 0} \frac{\prod_{i=1}^{n(n-1)/2} \left( \underline{p} \left(\exp(-\lambda L) -1 \right) +1\right) }{\exp\left( -\lambda \frac{n(n-1)}{2} C_1 \bar{p} \right)} \nonumber \\ & \leq \inf_{\lambda\geq 0} \frac{\exp\left( \frac{n(n-1)}{2} \underline{p} \left(\exp(-\lambda L) -1 \right) \right) }{\exp\left( -\lambda \frac{n(n-1)}{2} C_1 \bar{p} \right)} \nonumber \\ & \leq \exp\left( - \left(1 - \frac{1}{e^L}\right)\frac{n(n-1)}{2} \underline{p} + \frac{n(n-1)}{2} C_1 \bar{p} \right) \nonumber \\ & \leq \exp\left( - \left(1 - \frac{1}{e^L}\right) \frac{n(n-1)}{2} \frac{1}{\eta} \bar{p} + \frac{n(n-1)}{2} C_1 \bar{p} \right) \nonumber \\ & = \exp\left( -\left( \left(1 - \frac{1}{e^L}\right)\frac{1}{\eta} -C_1\right) \frac{n(n-1)}{2} \bar{p} \right) \nonumber \\ & \leq \exp\left( -\left( \left(1 - \frac{1}{e^L}\right)\frac{1}{\eta} -C_1\right) \frac{n^2}{4} \bar{p} \right)\;.\label{eq:Lemma95phat95lbineq} \end{align}\tag{23}\] Combining (22 ) and (23 ), we conclude the proof. \(\blacksquare\)

10.4 Proof of Lemma 9↩︎

Define \(e(S,S) = \sum_{v\in S} e(S,S)\). We now aim to prove the following intermediate assertion: with high probability, no subset \(S \subset \mathcal{I}\) exists such that \(e(S,S) \ge \phi \frac{n \bar{p}}{\log^5 n \bar{p}}\) and \(|S| = \phi\). For any subset \(S \subset \mathcal{I}\) with \(|S| = \phi\), using Markov’s inequality, \[\begin{align} \mathbb{P} \left\{ e(S,S) \ge \phi \frac{n \bar{p}}{\log^5 n \bar{p}} \right\} & \le \inf_{t\ge 0} \frac{ \mathbb{E}[ \exp (e(S,S)\phi) ] }{ \phi t \frac{n \bar{p}}{\log^5 n \bar{p}} } \nonumber \\ &\le \inf_{t\ge 0} \frac{ \prod_{i=1}^{\phi^2/2} ( 1+ L\bar{p} \exp(t) ) }{ \phi t \frac{n \bar{p}}{\log^5 n \bar{p}} } \nonumber \\ &\le \inf_{t\ge 0} \exp \left( \frac{\phi^2L\bar{p}}{2} \exp (t) - \phi t \frac{n \bar{p}}{\log^5 n \bar{p}} \right) \nonumber \\ & \stackrel{(a)}{\le} \exp\left( -\frac{\phi n \bar{p}}{\log^5 n \bar{p}}\left(\log \left(\frac{2 n}{\phi L \log^5 n \bar{p}}\right)-1\right)\right) \nonumber \\ & \stackrel{(b)}{\le} \exp\left( -\frac{\phi n \bar{p}}{2 \log^5 n \bar{p}}\log \left(\frac{2 n}{\phi L \log^5 n \bar{p}}\right)\right), \label{eq:bndss} \end{align}\tag{24}\] where we set \(t= \log (2n/(\phi L \log^5 n \bar{p}))\) for inequality \((a)\) and utilize \(\log \left(2 n/(\phi L \log^5 n \bar{p})\right) = \omega(1)\) derived from \(\phi \le 1/(\bar{p}(n \bar{p})^5)\) for inequality \((b)\). Considering the number of subsets \(S \subset \mathcal{I}\) having size \(\phi\) is \(\binom{n}{\phi} \le (\frac{e n}{\phi})^{\phi}\), we can infer the following from 24 : \[\begin{align} \mathbb{E}\left[\left| \left\{S : e(S,S) \ge \frac{\phi n \bar{p}}{(\log n\bar{p})^5} ~and~|S|= s \right\} \right|\right] &\le \left(\frac{e n}{\phi}\right)^{\phi} \exp\left( -\frac{\phi n \bar{p}}{2 \log^5 n \bar{p}}\log \left(\frac{2 n}{\phi L \log^5 n \bar{p}}\right)\right) \\ & \le \exp\left(\phi \log \left( \frac{e n}{\phi}\right) - \frac{\phi n \bar{p}}{2 \log^5 n \bar{p}}\log\left( \frac{2 n}{\phi L \log^5 n \bar{p}}\right) \right) \\ & \le \exp\left(- \frac{\phi n \bar{p}}{4 \log^5 n \bar{p}}\log\left( \frac{2 n}{\phi L \log^5 n \bar{p}}\right) \right). \end{align}\] Hence, applying the Markov inequality, there are no subsets \(S \subset \mathcal{I}\) such that \(e(S,S) \ge \phi n \bar{p}/(\log n\bar{p})^5\) and \(S = \phi\) with a probability of at least \(1 - \exp\left(- \frac{\phi n \bar{p}}{4 \log^5 n \bar{p}}\log\left( \frac{2 n}{\phi L \log^5 n \bar{p}}\right) \right)\).

In order to complete the proof of the lemma, we construct the following series of sets. Let \(Z_1\) represent the set of nodes that do not fulfill at least one of (H1) and (H2). Generate the sequence \(\{ Z(t) \subset \mathcal{I}\}_{1\le t \le t^{*}}\) as follows:

• \(Z(0)=Z_1\).

• For \(t \ge 1\), \(Z(t) = Z(t-1) \cup \{v_t \}\) if \(v_t \in \mathcal{I}\) exists such that \(e(v_t , Z(t-1)) > \frac{2 n \bar{p}}{\log^5(n\bar{p})}\) and \(v_t \notin Z(t-1)\). If no such node exists, the sequence terminates.

The sequence concludes after constructing \(Z(t^*)\), which, according to the definition of (H3), is equivalent to \(\mathcal{I} \setminus H\). We now demonstrate that if we assume the number of nodes that do not satisfy (H3) is strictly greater than \(\phi/2\), then one of the sets in the sequence \(\{ Z(t) \subset \mathcal{I}\}_{1\le t \le t^{*}}\) contradicts the claim we just established.

Suppose the number of nodes that do not meet (H3) is strictly greater than \(\phi/2\). At some point, these nodes will be incorporated into the sets \(Z(t)\), and according to the definition, each of these nodes contributes over \(\frac{2 n \bar{p}}{\log^5(n\bar{p})}\) to \(e(Z(t),Z(t))\). Therefore, if we start with \(Z_1\) and add \(\phi/2\) nodes that do not satisfy (H3), we obtain a set \(Z(t)\) with a cardinality smaller than \(\phi/3+\phi/2\) and such that \(e(Z(t),Z(t))> \frac{2 n \bar{p}}{\log^5(n\bar{p})}\). We can further include arbitrary nodes to \(Z(t)\) so that its cardinality becomes \(\phi\), resulting in a set that contradicts the claim. \(\blacksquare\)

10.5 Proof of Lemma [lm:spectralresults]↩︎

We remark that the statement is taken directly from [37], but here we present an alternative proof which may be of independent interest. We will extend the proof strategy of [42]. Let us define a discretized space \(T\) that approximates the continuous unit sphere. Let \(\varepsilon \in (0,1)\) be a fixed constant. \[\begin{align} T := \left\{ x \in \left(\frac{\varepsilon}{\sqrt{n}} \mathbb{Z} \right)^n : \sum_{i}^{n} x_i = 0, \|x\|_2 \leq 1 \right\}, \end{align}\] where \(\mathbb{Z}\) is the set of integers. From Claim 2.9 in [42], \(|T| \leq \exp(C(\varepsilon) n)\) where \(C(\varepsilon)\) is a constant only depends on \(\varepsilon\).

We first aim to prove that for all \(x, y \in T\), for any constant \(C>0\), there exists a constant \(C'>0\) such that \[|x^\top (A_\Gamma^\ell - M_\Gamma^\ell) y| = C' \sqrt{n \bar{p}} \;,\] with probability at least \(1 - \exp(-Cn \bar{p})\). Using this result and Claim 2.4 in [42], we can deduce that for any \(C>0\), there exists a constant \(C'>0\) such that \[\begin{align} \| A_\Gamma^\ell - M_\Gamma^\ell\|_2 &= \sup_{\|x\|_2 = 1, \|y\|_2 = 1} |x^\top (A_\Gamma^\ell - M_\Gamma^\ell) y| \\ & \leq \frac{1}{(1-\varepsilon)^2} C' \sqrt{n \bar{p}}\;, \end{align}\] with probability at least \(1 - \exp(-Cn \bar{p})\).

Define a set of light couples as: \[\mathcal{L} = \left\{ (v,w) \in \mathcal{I} \times \mathcal{I} : |x_v y_{w}| \leq \sqrt{\frac{\bar{p}}{n}}\right\}.\] Also define a set of heavy couples as its complement: \[\mathcal{L}^c = \left\{ (v,w) \in \mathcal{I} \times \mathcal{I} : |x_v y_{w}| > \sqrt{\frac{\bar{p}}{n}}\right\}.\] Finally, let we define a subset of edges \(\mathcal{K}:= (\Gamma^c \times \mathcal{I}) \cup (\mathcal{I} \times \Gamma^c)\)². Using these sets, by the triangular inequality, \[\begin{align} & |x^\top (A_\Gamma^\ell - M_\Gamma^\ell) y| \\ &= | x^\top (A_\Gamma^\ell - M^\ell) y + x^\top (M^\ell - M_\Gamma^\ell) y| \\ & = | \sum_{(v,w) \in \mathcal{L}} x_v A_{vw}^\ell y_w -\sum_{(v,w)\in \mathcal{K} \cap \mathcal{L}} x_v A_{vw}^\ell y_w + \sum_{(v,w)\in \mathcal{L}^c } x_v A_{\Gamma, vw}^\ell y_w - x^\top M^\ell y + x^\top (M^\ell - M_\Gamma^\ell) y| \\ & \leq P_1(x, y) + P_2(x,y) + P_3(x,y) + P_4(x,y)\;, \end{align}\] where \[\begin{align} P_1(x, y) & = \left|\sum_{(v,w)\in \mathcal{K} \cap \mathcal{L}} x_v A_{vw}^\ell y_{w} \right| \\ P_2(x, y) & = \left| \sum_{(v,w) \in \mathcal{L}}x_v A_{vw}^\ell y_{w} - x^\top M^\ell y \right| \\ P_3(x, y) & = \left| \sum_{(v,w) \in \mathcal{L}^c} x_v A_{\Gamma,vw}^\ell y_{w}\right| \\ P_4(x, y) & = | x^\top (M^\ell - M_\Gamma^\ell) y |\;. \end{align}\]

We will show that for each fixed \(x, y \in T\), for any constant \(C_1>0\), \[\begin{align} P_1(x, y) & \leq 2 C_1\sqrt{n \bar{p}}, \end{align}\] with probability at least \(1 - \exp(-C_1n)\). We will also show that for each fixed \(x, y \in T\), for any \(C_2>3\), \[\begin{align} P_2(x, y) & \leq C_2 \sqrt{n \bar{p}} \end{align}\] with probability at least \(1 - \exp\left(- \frac{C_2 -3}{2}n\right)\). Therefore, as \(|T| \leq \exp(C(\varepsilon)n)\), taking the union bound over \(T\) yields, \[\begin{align} P_1(x, y) & \leq 2 C_1\sqrt{n \bar{p}} \quad \text{and} \\ P_2(x, y) & \leq C_2 \sqrt{n \bar{p}}, \end{align}\] with probability at least \(1 - \exp(-(C_1 - C(\varepsilon))n) - \exp\left(- \frac{C_2 - 3 - 2 C(\varepsilon)}{2} n\right)\). Therefore, for any constant \(C>0\), there exists constants \(C_1\) and \(C_2\) such that for all \(x,y \in T\), \[\begin{align} P_1(x, y) & \leq C_1 \sqrt{n \bar{p}} \\ P_2(x, y) & \leq C_2 \sqrt{n \bar{p}}, \end{align}\] with probability at least \(1 - \exp(-Cn)\). Moreover, by extending the argument in [42], we will prove that for any constant \(C>0\), there exists a constant \(C_3>0\) such that \[\begin{align} P_3(x,y) & \leq C_3 \sqrt{n \bar{p}}\;, \end{align}\] with probability at least \(1 - \exp(-Cn \bar{p})\). Furthermore, we will prove that for any constant \(C_4 > e\), for all \(x,y \in T\), \[\begin{align} P_4(x, y) & \leq n \bar{p} \exp(-C_4n \bar{p})\;, \end{align}\] with probability at least \(1 - \exp(- \omega(n))\). Summarizing the bounds altogether using the union bound, we get the statement of the lemma.
From now on, we will focus on proving each bound with the probability guarantees.

Bound on \(P_1(x, y)\): By Lemma 8, with constant \(c > e\), we have \(\lfloor n \exp(- n\widetilde{p})\rfloor \leq n \exp(- c n \bar{p})\) with probability at least \(1 - \exp(-\omega(n))\). Let \(\{X_i\}\) be i.i.d. Bernoulli random variables with mean \(\bar{p}\). When, \(\lfloor n \exp(- n\widetilde{p})\rfloor \leq n \exp(- cn \bar{p})\), the following inequalities hold: \[\begin{align} &\mathbb{P}\left\{ \sum_{(v,w) \in \Gamma^c \times \mathcal{I}} A_{vw}^\ell \geq C_1 n \;\middle\vert\; \lfloor n \exp(- n\widetilde{p})\rfloor \leq n \exp(- cn \bar{p})\right\} \\ & = \mathbb{P}\left\{ 2 \sum_{(v,w) \in \Gamma^c \times \mathcal{I} : v >w} A_{ vw}^\ell \geq C_1 n \;\middle\vert\; \lfloor n \exp(- n\widetilde{p})\rfloor \leq n \exp(- cn \bar{p})\right\} \\ & \leq \mathbb{P}\left\{ \sum_{i=1}^{n^2 \exp( - c n\bar{p})} X_i \geq C_1 \frac{n}{2} \right\} \\ & \leq \inf_{\lambda \geq 0} \frac{\mathop{\mathrm{\mathbb{E}}}\left[ \exp( \lambda \sum_{i=1}^{n^2 \exp( - c n \bar{p})} X_i )\right]}{\exp\left( \lambda C_1 \frac{n}{2}\right)} \\ & = \inf_{\lambda \geq 0} \frac{\prod_{i=1}^{n^2 \exp( - c n \bar{p})} \mathop{\mathrm{\mathbb{E}}}\left[ \exp(\lambda X_i)\right]}{\exp\left( \lambda C_1 \frac{n}{2}\right)} \\ & = \inf_{\lambda \geq 0} \frac{\prod_{i=1}^{n^2 \exp( - c n \bar{p})} \left( (e^\lambda -1) \bar{p} + 1\right) }{\exp\left( \lambda C_1 \frac{n}{2}\right)} \\ & \stackrel{(a)}{\leq } \inf_{\lambda \geq 0} \frac{ \exp\left( {n^2 \exp( - c n \bar{p})} (e^\lambda -1) \bar{p} \right)}{\exp\left( \lambda C_1 \frac{n}{2}\right)} \\ & \leq \frac{ \exp\left( {n \cdot n \bar{p} \exp( - C n \bar{p})} (e^5 -1) \right)}{\exp\left( C_1\frac{5n}{2}\right)} \\ & \stackrel{(b)}{\leq } \exp(-2C_1n)\;, \end{align}\] where \((a)\) and \((b)\) are from the inequality \(1 + x \leq e^x \;\forall x \in \mathbb{R}\) and the fact that \(x \exp(-Cx) = o(1)\) when \(x = \omega(1)\), respectively. Thus, we have \[\begin{align} \mathbb{P}\left\{ \sum_{(v,w) \in \Gamma^c \times \mathcal{I}} A_{vw}^\ell \geq C_1 n \right\} & \leq \exp(-2C_1n) + \exp(-\omega(n)) \\ & \leq \exp(-C_1n)\;. \end{align}\] Note that \(|x_v y_w| \leq \sqrt{\frac{\bar{p}}{n}}\) for all \((v,w) \in \mathcal{L}\). Therefore, with probability at least \(1 - \exp(-C_1n)\), we have \[\begin{align} P_1(x, y) & = \left|\sum_{(v,w) \in \mathcal{K}\cap \mathcal{L}} x_v A_{vw}^\ell y_{w} \right| \\ & \leq \sum_{(v,w) \in \mathcal{K}\cap \mathcal{L}} A_{vw}^\ell |x_v y_{w}| \\ & \leq 2 \sqrt{\frac{\bar{p}}{n}}\sum_{(v, w) \in (\Gamma^c \times \mathcal{I}) \cap \mathcal{L} } A_{ vw}^\ell \\ & \leq 2 C_1 \sqrt{n \bar{p}}\;. \end{align}\]

Bound on \(P_2(x, y)\): Using \(\lambda = \frac{1}{2}\sqrt{\frac{n}{\bar{p}}}\), a positive constant \(C\), and \(\beta_{vw}: = x_v y_w \mathbb{1}\left\{(v,w) \in \mathcal{L}\right\} + x_w y_v \mathbb{1}\left\{(w,v) \in \mathcal{L}\right\}\) for all \((v,w) \in \mathcal{I} \times \mathcal{I}\), we have \[\begin{align} \mathbb{P}\left\{ \sum_{(v,w) \in \mathcal{L}} x_v A_{vw}^\ell y_{w} - x^\top M^\ell y \geq C \sqrt{n \bar{p}}\right\} & \leq \frac{\mathop{\mathrm{\mathbb{E}}}\left[\exp\left(\lambda \left( \sum_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} A_{vw}^\ell \beta_{vw}\right)\right)\right]}{\exp\left(\lambda \left(C\sqrt{n \bar{p}} + x^\top M y \right)\right)} \nonumber \\ & = \frac{\prod_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} \left( M_{vw}^\ell \left(\exp(\lambda \beta_{vw}) - 1\right) + 1 \right)}{\exp\left(\lambda \left(C\sqrt{n \bar{p}} + x^\top M^\ell y \right)\right)}\nonumber \\ & \leq \frac{\prod_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} \exp \left( M_{vw}^\ell \left( \exp(\lambda \beta_{vw}) - 1\right)\right)}{\exp\left(\lambda \left(C\sqrt{n \bar{p}} + x^\top M^\ell y \right)\right)} \nonumber \\ & \leq \frac{\prod_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} \exp \left( M_{vw}^\ell \left( \lambda\beta_{vw} + 2 (\lambda \beta_{vw})^2\right) \right) }{\exp\left(\lambda \left(C\sqrt{n \bar{p}} + x^\top M y \right)\right)}\nonumber \\ & = \frac{ \exp \left( \sum_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} M_{vw}^\ell \left( \lambda \beta_{vw} + 2 (\lambda\beta_{vw})^2 \right)\right) }{\exp\left(\lambda \left(C\sqrt{n \bar{p}} + x^\top M^\ell y \right)\right)}\nonumber \\ & = \underbrace{\exp\left( \sum_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} M_{vw}^\ell \lambda \beta_{vw} - \lambda x^\top M^\ell y \right)}_{\text{(i)}}\nonumber \\ & \cdot \underbrace{ \exp \left( 2 \sum_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} M_{vw}^\ell (\lambda \beta_{vw})^2 \right)}_{\text{(ii)}}\cdot { \exp\left( -\lambda C \sqrt{n \bar{p}}\right)} \label{eq:P295global} \end{align}\tag{25}\] For (i) and (ii), we have following bounds.

• This term can be alternatively expressed as follows: \[\begin{align} \exp\left( \sum_{(v, w) \in \mathcal{I} \times\mathcal{I} : v > w} M_{vw}^\ell \lambda \beta_{vw} - \lambda x^\top M^\ell y \right) & = \exp\left( \sum_{(v, w) \in \mathcal{L}} M_{vw}^\ell \lambda x_v y_w - \sum_{(v,w) \in \mathcal{I} \times \mathcal{I}} M_{vw}^\ell \lambda x_v y_w\right) \\ & = \exp \left( - \sum_{(v, w) \in \mathcal{L}^c} \lambda x_v y_w M_{vw}^\ell \right) \;.\label{eq:Lc95bound950} \end{align}\tag{26}\] Note that \(|x_v y_w| > \sqrt{\frac{\bar{p}}{n}}\) for all \((v,w) \in \mathcal{L}^c\) and \(\sum_{(u,w) \in \mathcal{I} \times \mathcal{I}} x_u^2 y_w^2 =1\). Therefore, \[\begin{align} \sqrt{\frac{\bar{p}}{n}} \sum_{(u,v) \in \mathcal{L}^c} |x_v y_w| & \leq \sum_{(u,v) \in \mathcal{L}^c} x_v^2 y_w^2 \\ & \leq 1\;. \end{align}\] It implies \[\begin{align} \sum_{(u,v) \in \mathcal{L}^c} |x_v y_w| \leq \sqrt{\frac{n}{\bar{p}}} \;. \end{align}\] Thus, \[\begin{align} \left|\sum_{(v, w) \in \mathcal{L}^c} \lambda x_v y_w M_{vw}^\ell \right| & \leq \sum_{(v, w) \in \mathcal{L}^c} \lambda | x_v y_w |M_{vw}^\ell \nonumber \\ & \leq \sum_{(v, w) \in \mathcal{L}^c} \lambda | x_v y_w | \bar{p} \nonumber \\ & = \frac{1}{2} \sqrt{n \bar{p}} \sum_{(v, w) \in \mathcal{L}^c} | x_v y_w | \nonumber \\ & \leq \frac{n}{2}\;. \label{eq:Lc95bound951} \end{align}\tag{27}\] From (26 ) and (27 ), we have \[\begin{align} \exp\left( \sum_{(v, w) \in \mathcal{I} \times \mathcal{I} : v > w} M_{vw}^\ell \lambda \beta_{vw} - \lambda x^\top M^\ell y \right) & \leq \exp\left(\frac{n}{2} \right)\;. \end{align}\]

• Note that from the definition, \[\begin{align} |\beta_{vw}|^2 \leq 2 (x_v y_w)^2 \mathbb{1} \left\{ (v,w) \in \mathcal{L}\right\} + 2 (x_w y_v)^2 \mathbb{1} \left\{ (w,v) \in \mathcal{L}\right\} \end{align}\] holds. Thus, we have \[\begin{align} & 2 \sum_{(v, w) \in \mathcal{I}\times \mathcal{I} : v > w} M_{vw}^\ell (\lambda \beta_{vw})^2 \\ & \leq 2 \sum_{(v, w) \in \mathcal{I} \times \mathcal{I} : v > w} \bar{p} \cdot \frac{n}{4 \bar{p}} \cdot \beta_{vw}^2 \\ & = \frac{n}{2} \sum_{(v, w) \in \mathcal{I} \times \mathcal{I} : v > w} \beta_{vw}^2 \\ & \leq \frac{n}{2} \sum_{(v, w) \in \mathcal{I} \times \mathcal{I} : v > w} \left( 2 (x_v y_w)^2 \mathbb{1} \left\{ (v,w) \in \mathcal{L}\right\} + 2 (x_w y_v)^2 \mathbb{1} \left\{ (w,v) \in \mathcal{L}\right\} \right) \\ & = n \sum_{(v, w) \in \mathcal{L}} (x_v y_w)^2 \\ & \stackrel{(a)}{\leq} n\;, \end{align}\] where in \((a)\) we used \(\sum_{(v, w) \in \mathcal{L}} (x_v y_w)^2 \leq \sum_{(v, w) \in \mathcal{I} \times \mathcal{I}} (x_v y_w)^2 = 1\). Taking exponential of the previous inequalities, we have: \[\begin{align} \exp\left( 2 \sum_{(v, w) \in \mathcal{I} \times \mathcal{I} : v > w} M_{vw}^\ell (\lambda \beta_{vw})^2\right) \leq \exp(n) \end{align}\]

Combining the bounds on (i) and (ii) with (25 ), we have: \[\begin{align} \mathbb{P}\left\{ \sum_{(v,w) \in \mathcal{L} } x_v A_{vw}^\ell y_{w} - x^\top M^\ell y \geq C \sqrt{n \bar{p}}\right\} & \leq \exp\left(\frac{3-C}{2}n \right)\;. \end{align}\] Taking any \(C_2>3\), we have: \[\begin{align} \sum_{(v,w) \in \mathcal{L}} x_v A_{vw}^\ell y_{w} - x^\top M^\ell y \leq C_2 \sqrt{n \bar{p}}, \end{align}\] with probability at least \(1 - \exp\left(-\frac{C_2-3}{2}n\right)\).

Bound on \(P_3(x, y)\): We extend the proofs in [42]. For any \(A, B \subset \mathcal{I}\), let we define \(e(A, B) \mathrel{\vcenter{:}}= \sum_{v \in A} \sum_{w \in B} A_{vw}^\ell\) to be the number of positive labels between the nodes in \(A\) and the nodes in \(B\) and \(\mu(A,B): = |A||B| \bar{p}\). \(\mu(A,B)\) is an upper bound of the expected number of labels between \(A\) and \(B\). We call the adjacency matrix \(A_\Gamma^\ell\) has the bounded degree property with a positive constant \(c_1>0\) if for all \(v \in \mathcal{I} \cap \Gamma\), \(e(v, \mathcal{I} \cap \Gamma) \leq c_1 n \bar{p}\) holds. Furthermore, we state that the adjacency matrix \(A_\Gamma^\ell\) has the discrepancy property with constants \(c_2>0\) and \(c_3>0\) if for every \(A, B \subset \mathcal{I} \cap \Gamma\), one of the following holds: \[\begin{align} \text{(i)} \quad & \frac{e(A,B)}{\mu(A,B)} \leq c_2 \\ \text{(ii)} \quad & e(A,B) \log \left(\frac{e(A,B)}{\mu(A,B)} \right) \leq c_3 |B| \log \left(\frac{n}{|B|}\right)\;. \end{align}\] By Corollary 2.11 in [42], if the graph with the adjacency matrix \(A_\Gamma\) satisfies the discrepancy and the bounded degree properties, there exists a constant \(C'\) which depends on \(c_1\), \(c_2\), and \(c_3\) such that \[\begin{align} P_3(x, y) \leq C' \sqrt{n \bar{p}}, \end{align}\] for all \(x, y \in T\).

First, we have the following lemma that guarantees the probability that the bounded degree property holds.

The proof is given in Appendix 10.8.

Next, we have the following lemma that guarantees the probability that the discrepancy property holds.

The proof of Lemma 11 is given in Appendix 10.9. Therefore, for any \(C>0\), there exists \(c_1\), \(c_2\), and \(c_3\) such that the bounded degree property and discrepancy property hold with probability at least \(1 - \exp(-Cn \bar{p}))\).

Bound on \(P_4(x, y)\): We have, with a constant \(C>e^L\), for all \(x,y \in T\), with probability at least \(1 - \exp( - \omega(n))\), \[\begin{align} P_4(x, y) & = | x^\top (M^\ell - M_\Gamma^\ell) y | \\ & \leq \| M^\ell - M_{\Gamma}^\ell\|_2 \\ & \leq \| M^\ell - M_{\Gamma}^\ell\|_F \\ & \leq \sqrt{\sum_{(v,w) \in \mathcal{K}} \bar{p}^2 } \\ & = \sqrt{ (\lfloor n \exp ( - n \widetilde{p})\rfloor)^2 \bar{p}^2} \\ & \stackrel{(a)}{\leq} \sqrt{ ( n \exp ( - Cn \bar{p}) )^2 \bar{p}^2} \\ & = n \bar{p} \exp ( - Cn \bar{p}) \end{align}\] where we used Lemma 8 in \((a)\). This concludes the proof. \(\blacksquare\)

10.6 Proof of Lemma [lm:columndistance]↩︎

For all \(v, w \in \Gamma\) such that \(\sigma(v) \neq \sigma(w)\), there exists a constant \(C>0\) that depends on \(\varepsilon\) in (A2) such that with probability at least \(1 - \exp(-\omega(n))\), \[\begin{align} \|M_{\Gamma, v}- M_{\Gamma, w} \|_2^2 & = \sum_{i \in \mathcal{I} \cap \Gamma} \sum_{\ell=1}^L (p(\sigma(v), \sigma(i), \ell) - p(\sigma(w), \sigma(i), \ell))^2 \\ & = \sum_{k \in [K]}\sum_{i \in \mathcal{I}_k \cap \Gamma}\sum_{\ell=1}^L (p(\sigma(v), \sigma(i), \ell) - p(\sigma(w), \sigma(i), \ell))^2 \\ & \stackrel{(a)}{\ge} \sum_{k \in [K]} ( \alpha_k - \exp(-C_1 n \bar{p}))n \sum_{\ell=1}^L (p(\sigma(v), \sigma(i), \ell) - p(\sigma(w), \sigma(i), \ell))^2 &\\ & \stackrel{(b)}{\ge} C \varepsilon n \bar{p}^2, \end{align}\] where for \((a)\), we used Lemma 8 to replace \(\widetilde{p}\) with \(\bar{p}\) in the cardinality of \(\Gamma\); and for \((b)\), we used (A2).

\(\blacksquare\)

10.7 Proof of Lemma [lem:iterative95power95svt]↩︎

First, from Lemma [lm:spectralresults], for any \(c>0\), there exists constants \(C_1, C_2>0\) such that \(\sigma_K \ge C_1 n \bar{p}\) and \(\sigma_{K+1} \le C_2 \sqrt{n \bar{p}}\) with probability at least \(1 - \exp(-c n \bar{p})\). Therefore, for any \(c>0\), we have \(\hat{K} =K\) with probability at least \(1 - \exp(-c n \bar{p}(1 + o(1)))\). From the analysis of the iterative power method in [44] (Theorem 9.2 and Theorem 9.1 in [44]), for any \(c>0\), with probability at least \(1 - \exp(-c n \bar{p}(1 + o(1)))\), \[\begin{align} \| \bar{A} - \hat{A}\|_2 \le (1 + \|\Omega_2 \Omega_1^{-1}\|_2^2)^{\frac{1}{4 \lceil (\log n)^2 \rceil +2}} \sigma_{K+1}, \end{align}\] where \(\Omega_1\) is a \(K \times K\) standard Gaussian random matrix, \(\Omega_2\) is an \(Ln-K \times K\) Gaussian random matrix, \(\sigma_{K+1}\) is the \(K+1\)-th largest singular value of the matrix \(A_\Gamma\). We use the following proposition from [44].

From this proposition, for any \(c>0\), there exists a constant \(C>0\) such that \(\|\Omega_1^{-1}\|_2 \le Cn^c\) with probability at least \(1-1/n^c\).

Therefore, for any \(c>0\), there exist constants \(C_1, C_2>0\) such that \[\begin{align} \| \bar{A} - \hat{A}\|_2 & \le (1 + \|\Omega_2\|_2^2 \| \Omega_1^{-1}\|_2^2)^{\frac{1}{4 \lceil (\log n)^2 \rceil +2}} \sigma_{K+1} \\ & \le (1 + Cn \cdot n^c)^{\frac{1}{4 \lceil (\log n)^2 \rceil +2}} \sigma_{K+1} \\ & \le C_2 \sigma_{K+1}, \end{align}\] with probability at least \(1 - 1/n^c\). This concludes the proof. \(\blacksquare\)

10.8 Proof of Lemma 10↩︎

Recall that from Lemma 10, for each \(v \in \mathcal{I}\), for any \(C>0\), we have \[\begin{align} \label{eq:degreebound} e(v, \mathcal{I}) \le C n \bar{p}, \end{align}\tag{28}\] with probability at least \(\exp( -(C -e^L) n \bar{p})\). Also, from Lemma 8, for any constant \(C_2 > e^L\), we have \(\widetilde{p} \leq C_2 \bar{p}\) with probability at least \(1 - \exp(-\omega(n))\). The number of trimmed nodes is larger than \(n\exp(-C_2n \bar{p})\) with probability at least \(1 - \exp(-\omega(n))\). With these \(C\) and \(C_2\), by Markov’s inequality, \[\begin{align} \mathbb{P}\left\{ \text{The number of nodes that do not satisfy (\ref{eq:degreebound})} \geq n \exp(-C_2 n \bar{p}) \right\} & \leq \frac{\mathop{\mathrm{\mathbb{E}}}\left[\sum_{v \in \mathcal{I}} \mathbb{1} \left\{ e(v, \mathcal{I}) > C'n \bar{p} \right\} \right]}{n \exp(-C_2n \bar{p})} \\ & = \frac{\sum_{v \in \mathcal{I}} \mathbb{P}\left\{ e(v, \mathcal{I}) > C'n \bar{p}\right\} }{n \exp(-C_2n \bar{p})} \\ & \leq \exp \left( - (C - C_2 - e^L) n \bar{p}\right)\;. \end{align}\] Therefore, by the union bound, for any \(C>0\), there exists a constant \(C'>0\) such that any \(v \in \mathcal{I} \cap \Gamma\) satisfies \(e(v, \mathcal{I}) \leq C' n \bar{p}\), with probability at least \(1 - \exp(-Cn \bar{p}) - \exp(-\omega(n))\). This concludes the proof.

10.9 Proof of Lemma 11↩︎

Let \(A\) and \(B\) be subsets of \(\mathcal{I} \cap \Gamma\). Without loss of generality, we assume that \(|A|\leq |B|\). We prove the lemma by dividing it into two cases.

when \(|B| \geq n /5\). By Lemma 10, for any constant \(C>0\), there exists a constant \(c_1\) such that for all \(v \in \mathcal{I} \cap \Gamma\), \(e(v, \mathcal{I} \cap \Gamma) \leq c_1 n \bar{p}\) holds with probability at least \(1 - \exp(-Cn \bar{p})\). Therefore, for any constant \(C>0\), there exists a constant \(c_2>0\) such that with probability at least \(1 - \exp(-Cn \bar{p})\) for all \(A,B \subset \mathcal{I} \cap \Gamma\) such that \(|B| \geq |A|\), \[\begin{align} e(A, B) & \leq e(A, \mathcal{I} \cap \Gamma) \\ & \leq |A| c_1 n \bar{p} \\ & = 5c_1 |A| \frac{n}{5} \bar{p} \\ & \leq 5c_1 |A| |B| \bar{p} \\ & \stackrel{(a)}{\leq} c_2 \mu(A, B), \end{align}\] where in \((a)\) we put \(c_2 \geq 5 c_1\).

when \(|B| \leq n/5\). Let we define \(\eta(A, B) = \max(\eta^0 , c_2 )\) where \(\eta^0\) is the solution that satisfies \(\eta^0 \mu (A, B) \log \eta^0 = c_3 |B| \log ( n /|B|)\). As \(c_3 |B| \log ( n /|B|) >0\), it implies \(\eta^0 >1\). Furthermore, as \(x\log x\) is an strictly increasing function when \(x \geq 1\), \(\eta^0\) is unique for fixed \(A\) and \(B\).

When \(e(A, B) \leq \eta(A,B) \mu(A, B)\) and \(\eta(A, B) = c_2\), the condition (i) is satisfied. When \(e(A, B) \leq \eta(A,B) \mu(A, B)\) and \(\eta(A, B) = \eta^0\), using the definition of \(\eta^0\), we have \[\begin{align} e(A, B) & \leq \eta^0 \mu(A, B) \\ & = \frac{1}{\log \eta^0} c_3 |B| \log \left( \frac{n}{|B|}\right)\;. \end{align}\] From \(\log (e(A, B) / \mu(A,B)) \leq \log \eta^0\), we have \[\begin{align} e(A,B) \log \left( \frac{e(A,B)}{\mu(A,B)}\right) \leq c_3 |B| \log \left(\frac{n}{|B|}\right)\;. \end{align}\] Hence, the condition (ii) is satisfied. Therefore, when \(e(A, B) \leq \eta(A,B) \mu(A,B)\), the discrepancy property holds. We quantifies the probability that \(e(A, B) \leq \eta(A,B) \mu(A,B)\) holds for any \(A, B \subset \mathcal{I} \cap \Gamma\).

First, by Markov’s inequality, \[\begin{align} \mathbb{P}(e(A, B) > \eta(A,B) \mu(A,B)) & \leq \inf_{\lambda \geq 0} \frac{\mathop{\mathrm{\mathbb{E}}}[\exp(\lambda e (A, B))]}{\exp(\lambda \eta(A,B) \mu(A,B)) } \\ & \leq \inf_{\lambda \geq 0} \frac{\left( \bar{p}(\exp(\lambda) -1) +1\right)^{|A||B|} }{\exp(\lambda \eta(A,B) \mu(A,B)) } \\ & \leq \inf_{\lambda \geq 0} \frac{\left( \bar{p} \exp(\lambda) +1\right)^{|A||B|} }{\exp(\lambda \eta(A,B) \mu(A,B)) } \\ & \leq \inf_{\lambda \geq 0} \frac{ \exp(|A||B| \bar{p} \exp(\lambda) ) }{\exp(\lambda \eta(A,B) \mu(A,B)) } \\ & = \inf_{\lambda \geq 0} \exp\left( \exp(\lambda) \mu(A, B) - \lambda \eta(A,B) \mu(A,B)\right) \\ & \stackrel{(a)}{\leq} \exp\left( - \eta(A,B) \mu(A, B) \left( \log\eta(A, B) -1 \right)\right), \end{align}\] where in \((a)\), we set \(\lambda = \log \eta(A,B)\).

Next, we compute the probability as follows. \[\begin{align} & \mathbb{P}\left\{e(A,B) > \eta(A,B) \mu(A,B) \text{ for some } A, B \in \mathcal{I} \cap \Gamma, |B|\leq \frac{n}{5} , |A| \leq |B |\right\} \\ & = \mathbb{P}\left\{ \cup_{b=1}^{n/5} \cup_{a=1}^{b} \cup_{A, B \subset \mathcal{I} \cap \Gamma: |A| =a, |B| = b} \left\{ e(A,B) > \eta(A,B) \right\} \right\} \\ & \stackrel{(a)}{\leq} \sum_{b=1}^{n/5} \sum_{a=1}^{b} \binom{n}{a} \binom{n}{b} \exp \left( - \eta(A, B) \mu(A,B) \left( \log \eta(A,B) -1 \right) \right) \\ & \stackrel{(b)}{\leq} \sum_{b=1}^{n/5} \sum_{a=1}^{b} \left( \frac{n e}{b} \right)^{2b} \exp \left( - \eta(A, B) \mu(A,B) \left( \log \eta(A,B) -1 \right)\right) \\ & = \sum_{b=1}^{n/5} \sum_{a=1}^{b} \exp \left( 2b + 2b \log \left(\frac{n}{b}\right) - \eta(A, B) \mu(A,B) \left( \log \eta(A,B) -1 \right)\right) \\ & \stackrel{(c)}{\leq} \sum_{b=1}^{n/5} \sum_{a=1}^{b} \exp \left( 4b \log \left(\frac{n}{b}\right) - \eta(A, B) \mu(A,B) \left( \log \eta(A,B) -1 \right)\right) \\ & = \sum_{b=1}^{n/5} \sum_{a=1}^{b} \exp \left(- (C+2)\log n +(C+2) \log n + 4b \log \left(\frac{n}{b}\right) - \eta(A, B) \mu(A,B) \left( \log \eta(A,B) -1 \right) \right) \\ & \stackrel{(d)}{\leq} \sum_{b=1}^{n/5} \sum_{a=1}^{b} \exp \left(- (C+2)\log n +(C+6) b\log \left( \frac{n}{b} \right) - \eta(A, B) \mu(A,B) \left( \log \eta(A,B) -1 \right)\right) \\ & \stackrel{(e)}{\leq} \sum_{b=1}^{n/5} \sum_{a=1}^{b} \exp \left(- (C+2)\log n +(C+6) b\log \left( \frac{n}{b} \right) - \frac{\eta(A,B) \mu(A,B)}{2} \log \eta(A,B) \right) \\ & \stackrel{(f)}{\leq} \sum_{b=1}^{n/5} \sum_{a=1}^{b} \exp \left(- (C+2)\log n +(C+6) b\log \left( \frac{n}{b} \right) - \frac{\eta^0 \mu(A,B)}{2} \log \eta^0 \right) \\ & \stackrel{(g)}{\leq} \sum_{b=1}^{n/5} \sum_{a=1}^{b} \exp \left(- (C+2)\log n \right) \\ & \leq \frac{1}{n^C}, \end{align}\] where for \((a)\) is from the union bound; for \((b)\), we used \(b\leq n/5\) and \(a \leq b\); for \((c)\), we again used \(b\leq n/5\); for \((d)\), we used the fact that \(x\log(n/x)\) is an increasing function in \([1, n/e]\) (Lemma 2.12 in [42]); for \((e)\), we used \(\eta(A,B) \geq c_2\) with sufficiently large constant \(c_2\); for \((f)\), we used the fact that \(x \log x\) is a strictly increasing function when \(x\geq1\); \((g)\) stems from the definition of \(\eta^0\) with \(c_3 \geq 2(C+6)\).

From the assumption \(\bar{p} = \mathcal{O}(\log n/n)\), for any \(C>0\), there exist constants \(c_2\) and \(c_3\) such that the discrepancy property with constants \(c_2\) and \(c_3\) holds with probability at least \(1 - \exp(-Cn \bar{p})\). This concludes the proof. \(\blacksquare\)

10.10 Proof of Corollary 1↩︎

Let \(\varepsilon^\text{init}(n)\) represent the number of misclassified nodes in the initial spectral clustering \(\text{USC}(\tau)\) as described in [16]. Based on the node-wise refinement guarantee provided in the proof of Theorem 4 in [16] (specifically, Lemma 17 of [16]), when \(K = \mathcal{O}(1)\), \[\begin{align} & \sup_{(p, \alpha) \in \Theta(n, a, b)} \max_{i \in \mathcal{I}} \mathbb{P}_{(p, \alpha)} (\text{node } i \text{ is misclassified}) \nonumber \\ & \le \underbrace{\exp \left(- (1+o(1))\frac{nI^*}{K}\right)}_{(a)} + C \mathbb{P}_{(p, \alpha)}( \varepsilon^\text{init}(n) \le \gamma_n), \label{eq:docomposition95nodewise95error} \end{align}\tag{29}\] where \(\gamma_n\) is a positive sequence that satisfies \(\lim_{n\to \infty} \gamma_n = 0\). According to Theorem 6 in [16], for any \(C'>0\), we obtain \[\begin{align} \mathbb{P}_{(p, \alpha)}( \varepsilon^\text{init}(n) \le \gamma_n) \le \frac{1}{n^{C'}}, \end{align}\] with an appropriate choice of the sequence \(\gamma_n\) in 29 . Since \(I^* \asymp \frac{(a-b)^2}{n a}\) according to [16], using the assumptions \(a/b = \Theta(1)\) and \(a=\mathcal{O}(\log n)\), we obtain \[\begin{align} (a) \ge \exp \left( -C'' \log n\right) = \frac{1}{n^{C''}}, \end{align}\] for some constant \(C''>0\). Therefore, since we can choose any constant \(C'>0\), \[\begin{align} C \mathbb{P}_{(p, \alpha)}( \varepsilon^\text{init}(n) \le \gamma_n) = o \left(\exp \left(- (1+o(1))\frac{nI^*}{K}\right) \right) \end{align}\] and \[\begin{align} \sup_{(p, \alpha) \in \Theta(n, a, b)} \max_{i \in \mathcal{I}} \mathbb{P}_{(p, \alpha)} (\text{node } i \text{ is misclassified}) \le \exp \left(- (1+o(1))\frac{nI^*}{K}\right). \end{align}\] Thus, we obtain \[\begin{align} \sup_{(p, \alpha) \in \Theta(n, a, b)} \mathop{\mathrm{\mathbb{E}}}_{(\alpha, p)}[\varepsilon^{\text{PLMLE}} (n)] & = \sup_{(p, \alpha) \in \Theta(n, a, b)} \sum_{i \in \mathcal{I}} \mathbb{P}_{(p, \alpha)} (\text{node } i \text{ is misclassified}) \\ & \le \sup_{(p, \alpha) \in \Theta(n, a, b)} n \max_{i \in \mathcal{I}} \mathbb{P}_{(p, \alpha)} (\text{node } i \text{ is misclassified}) \\ & \le n \exp \left(- (1+o(1))\frac{nI^*}{K}\right). \end{align}\] This concludes the proof. \(\blacksquare\)

11 Numerical Experiments↩︎

In this section, we present numerical evaluations of the proposed algorithm. Our experiments are based on the code of [25], and we consider the three scenarios proposed in [16], as well as an additional scenario. The main focus of our comparison is the IAC algorithm (Algorithm 1) and a computationally efficient version of the penalized local maximum likelihood estimation (PLMLE) algorithm (Algorithm 3 in [16]). Note that this version of PLMLE does not have performance guarantees, but it still requires \(\Omega(n^2)\) floating-point operations. As shown in Section 4 of [16], PLMLE and its simplified version (Algorithm 3) exhibit nearly identical performance in all considered scenarios. In all experiments, we consider simple SBMs with \(L=1\).

Model 1: Balanced Symmetric. First, consider the SBM corresponding to the “Balanced case” in [16]. Assume that \(n= 2500\), \(K=10\), and \(L=1\). We fix the community size to be equal as \(\forall k \in [10], |\mathcal{I}_k| = 250\). We set the observation probability as \(p(k, k, 1) = 0.48\) for all \(k\) and \(p(i, k, 1) = 0.32\) for all \(i \neq k\).

Model 2: Imbalanced. The next SBM corresponds to the “Imbalanced case” in [16]. We set \(n = 2000\), \(K=4\), and \(L=1\). The sizes of the clusters are heterogenous: \(| \mathcal{I}_1| = 200\), \(|\mathcal{I}_2| = 400\), \(|\mathcal{I}_3| = 600\), and \(|\mathcal{I}_4| = 800\). We set the observation probability matrix \((p(i, k, 1))_{i, k}\) as in [16]: \[\begin{align} (p(i, k, 1))_{i, k} = \begin{pmatrix} 0.50 \text{ } & 0.29\text{ } & 0.35\text{ } & 0.25 \\ 0.29\text{ } &0.45\text{ } & 0.25\text{ } & 0.30 \\ 0.35\text{ } & 0.25\text{ } & 0.50\text{ } & 0.35 \\ 0.25\text{ } & 0.30\text{ } & 0.35\text{ } & 0.45 \end{pmatrix}. \end{align}\]

Model 3: Sparse Symmetric. The last experimental setting from [16] is the sparse and symmetric case. We generate networks with \(n=4000\), \(K=10\), and \(L=1\). Clusters are of equal sizes: \(\forall k \in [10]\), \(|\mathcal{I}_k| = 400\). We set the statistical parameter as \(p(k, k, 1) = 0.032\) for all \(k\) and \(p(i, k, 1) = 0.005\) for all \(i \neq k\).

Model 4: Sparse Asymmetric. Lastly, we consider the cluster recovery problem with a sparse and asymmetric statistical parameter. We set \(n=1200\), \(K=4\), and \(L=1\). Clusters are of equal sizes: \(\forall k \in [4], |\mathcal{I}_k| =300\). We fix the statistical parameter \((p(i, k, 1))_{i, k}\) as \[\begin{align} (p(i, k, 1))_{i, k} = \begin{pmatrix} 0.032 \text{ } & 0.005 \text{ } & 0.008 \text{ } & 0.005\\ 0.005 \text{ } & 0.028 \text{ } & 0.005 \text{ } & 0.008\\ 0.008 \text{ } & 0.005 \text{ } & 0.032 \text{ } & 0.005\\ 0.005 \text{ } & 0.008 \text{ } & 0.005 \text{ } & 0.028 \end{pmatrix}. \end{align}\] The simulations presented in this paper were conducted using the following computational environment.

• Operating System: macOS Sonoma

• Programming Language: MATLAB

• Processor: Apple M3 Max

• Memory: 128 GB

The average running time of our IAC algorithm is \(0.177 \pm 0.037\) seconds, while that of PLMLE is \(0.915 \pm 0.752\) seconds for Model 4.

The results of our experiments are summarized in Table 2. The IAC algorithm consistently performs slightly better than Algorithm 3 in [16]. Figures 3, 4, 5, and 6 display boxplots representing the number of misclassified nodes for each Model and method.

11.1 Experiments with Real-World Dataset↩︎

We applied our algorithm to a real-world dataset, the DBLP citation network dataset [46]. In this dataset, the nodes represent researchers. We focused on 246 researchers who have authored 20 or more papers, selected from a corpus of 50,000 papers. The edges represent co-authorship relationships: two researchers are connected if they have co-authored at least one paper. There are 1,118 such co-authorship connections in the network.

The researchers in this network were clustered using both IAC and PLMLE, with the number of clusters set to 8 for simplicity. Network visualizations and statistics (community size distributions and the distributions of publications per author in each community) are shown in Figures 7 and 8, respectively. Interestingly, our IAC algorithm discovered larger communities without excessively small ones, resulting in a more continuous community size distribution.

References↩︎

---

1. Refer to [16] for the class of SBMs considered. Compared to our assumptions (A1)-(A2)-(A3) specialized to SBMs, this class of SBMs is slightly more general.↩︎

2. Note that this set is the complement of \(\Gamma \times \Gamma\)↩︎