Community Detection in Degree-Corrected Block Models

Introduction

In many fields such as social science, neuroscience and computer science, it has become increasingly important to process and make inference on relational data. The analysis of network data, a prevalent form of relational data, becomes an important topic for statistics and machine learning. One central problem of network data analysis is community detection: to partition the nodes in a network into subsets. A meaningful partition of nodes can often uncover interesting information that is not apparent in a complicated network.

One way to accommodate degree heterogeneity is to introduce a set of degree-correction parameters $\left\{\theta_{i}:i=1,\dots,n\right\}$, one for each node, which can be interpreted as the popularity or importance of a node in the network. Then one could revise the edge distributions to $A_{ij}=A_{ji}\stackrel{{\scriptstyle ind.}}{{\sim}}\text{Bern}(\theta_{i}\theta_{j}B_{z(i)z(j)})$ for all $i>j$, and this gives rise to the Degree-Corrected Block Models (DCBMs) . In a DCBM, within the same community, a node with a larger value of degree-correction parameter is expected to have more connections than that with a smaller value. On the other hand, SBMs are special cases of DCBMs in which the degree-correction parameters are all equal. Empirically, the larger class of DCBMs is able to provide possibly much better fits to many real world network datasets . Since the proposal of the model, there have been various methods proposed for community detection in DCBMs, including but not limited to spectral clustering and modularity based approaches . On the theoretical side, provides an information-theoretic characterization of the impossibility region of community detection for DCBMs with two clusters, and sufficient conditions have been given in for strongly and weakly consistent community detection. However, two fundamental statistical questions remain unanswered:

What are the fundamental limits of community detection in DCBMs?

Once we know these limits, can we achieve them adaptively via some polynomial time algorithm?

The answer to the first question can provide important benchmarks for comparing existing approaches and for developing new procedures. The answer to the second question can lead to new practical methodologies with theoretically justified optimality. The present paper is dedicated to provide answers to these two questions.

Our main contributions are two-folded. First, we carefully formulate community detection in DCBMs as a decision-theoretic problem and then work out its asymptotic minimax risks with sharp constant in the exponent under certain regularity conditions. For example, let $k$ be a fixed constant. Suppose there are $k$ communities all about the same size $n/k$ and the average within community and between community edge probabilities are $p$ and $q$ respectively with $p>q$ and $p/q=O(1)$, then under mild regularity conditions, the minimax risk under the loss function that counts the proportion of misclassified nodes takes the form

as $n\to\infty$ whenever it converges to zero and the maximum expected node degree scales at a sublinear rate with $n$. The general fundamental limits to be presented in Section 2 allow the community sizes to differ and the number of communities $k$ to grow to infinity with $n$. To the best our knowledge, this is the first minimax risk result for community detection in DCBMs. The minimax risk (1) has an intuitive form. In particular, the $i{{}^{\rm th}}$ term in the summation can be understood as the probability of the $i{{}^{\rm th}}$ node being misclassified. When $\theta_{i}$ is larger, the chance of the node being misclassified gets smaller as it has more edges and hence more information of its community membership is available in the network. The term $n/k$ is roughly the community size. Since the community detection problem can be reduced to a hypothesis testing problem with $n/k$ as its effective sample size, a larger $k$ implies a more difficult problem. Furthermore, $(\sqrt{p}-\sqrt{q})^{2}$ reflects the degree of separation among the $k$ clusters. Note that $p$ and $q$ are the average within and between community edge probabilities and so $(\sqrt{p}-\sqrt{q})^{2}$ measures the difference of edge densities within and between communities. If the clusters are more separated in the sense that the within and between community edge densities differ more, the chance of each node being misclassified becomes smaller. When the degree-correction parameters are all equal to one and $p=o(1)$, the expression in (1) reduces to the minimax risk of community detection in SBMs in .

In addition, we investigate computationally feasible algorithms for adaptively achieving minimax optimal performance. In particular, we propose a polynomial time two-stage algorithm. In the first stage, we obtain a relatively crude community assignment via a weighted $k$-medians procedure on a low-rank approximation to the adjacency matrix. Working with a low-rank approximation (as opposed to the leading eigenvectors of the adjacency matrix) enables us to avoid common eigen-gap conditions needed to establish weak consistency for spectral clustering methods. Based on result of the first stage, the second stage applies a local optimization to improve on the community assignment of each network node. Theoretically, we show that it can adaptively achieve asymptotic minimax optimal performance for a large collection of parameter spaces. The empirical effectiveness of the algorithm is illustrated by simulation.

Connection to previous work

The present paper is connected to a number of papers on community detection in DCBMs and SBMs.

It is connected to the authors’ previous work on minimax community detection in SBMs . However, the involvement of degree-correction parameters poses significant new challenges. For the study of fundamental limits, especially minimax lower bounds, the fundamental two-point testing problem in DCBMs compares two product probability distributions with different marginals, while in SBMs, the two product distributions can be divided to two equal sized blocks within which the marginals are the same. Consequently, a much more refined Cramér–Chernoff argument is needed to establish the desired bound. In addition, to establish matching minimax upper bounds, the analysis of the maximum likelihood estimators is technically more challenging than that in due to the presence of degree-correction parameters and the wide range in which they can take values. In particular, we use a new folding argument to obtain the desired bounds. For adaptive estimation, the degree-correction parameters further increase the number of nuisance parameters. As a result, although we still adopt a “global-to-local” two-stage strategy to construct the algorithm, neither stage of the proposed algorithm in the present paper can be borrowed from the algorithm proposed in . We will give more detailed comments on the first stage below. For the second stage, the penalized neighbor voting approach in requires estimation of degree-correction parameters with high accuracy and hence is infeasible. We propose a new normalized neighbor voting procedure to avoid estimating $\theta_{i}$’s.

The first stage of the proposed algorithm is connected to the literature on spectral clustering, especially . The novelty in our proposal is that we cluster the rows of a low-rank approximation to the adjacency matrix directly as opposed to the rows of the matrix containing the leading eigenvectors of the adjacency matrix. As a result, the new spectral clustering algorithm does not require any eigen-gap condition to achieve consistency.

Organization

After a brief introduction to common notation, the rest of the paper is organized as follows. Section 2 presents the decision-theoretic formulation of community detection in DCBMs and derives matching asymptotic minimax lower and upper bounds under appropriate conditions. Given the fundamental limits obtained, we propose in Section 3 a polynomial time two-stage algorithm and study when a version of it can adaptively achieve minimax optimal rates of convergence. The finite sample performance of the proposed algorithm is examined in Section 4 on simulated data examples. Some proofs of the main results are given in Section 5 with additional proofs deferred to the appendices.

Notation

Fundamental Limits

In this section, we present fundamental limits of community detection in DCBMs. We shall first define an appropriate parameter space and a loss function. A characterization of asymptotic minimax risks then follows.

Recall that a random graph of size $n$ generated by a DCBM has its adjacency matrix $A$ satisfying $A_{ii}=0$ for all $i\in[n]$ and

We are mostly interested in the behavior of minimax risks over a sequence of such parameter spaces as $n$ tends to infinity and the key model parameters $\theta,p,q,k$ scale with $n$ in some appropriate way. On the other hand, we take $\beta\geq 1$ as an absolute constant and require the (slack) parameter $\delta$ to be an $o(1)$ sequence throughout the paper.

Therefore, $B_{uu}$ and $B_{uv}$ can be understood as the (approximate) average connectivity within the $u{{}^{\rm th}}$ community and between the $u{{}^{\rm th}}$ and the $v{{}^{\rm th}}$ communities, respectively. Under this interpretation, $p$ can be seen as a lower bound on the within community connectivities and $q$ an upper bound on the between community connectivities. We require the assumption $p>q$ to ensure that the model is “assortative” in an average sense. Finally, we also require the individual community sizes to be contained in the interval $[n/(\beta k)-1,\beta n/k+1]$. In other words, the community sizes are assumed to be of the same order.

As for the loss function, we use the following misclassification proportion that has been previously used in the investigation of community detection in stochastic block models :

where $H(\cdot,\cdot)$ is the Hamming distance defined as $H(z_{1},z_{2})=\sum_{i\in[n]}{\mathbf{1}_{\left\{{z_{1}(i)\neq z_{2}(i)}\right\}}}$ and $\Pi_{k}$ is the set of all permutations on $[k]$. Here, the minimization over all permutations is necessary since we are only interested in comparing the partitions resulting from $z$ and $\hat{z}$ and so the actual labels used in defining the partitions should be inconsequential.

2 Minimax Risks

Now we study the minimax risk of the problem

In particular, we characterize the asymptotic behavior of (5) as a function of $n,\theta,p,q,k$ and $\beta$. The key information-theoretic quantity that governs the minimax risk of community detection is $I$, which is defined through

Note that $I$ depends on $n$ not only directly but also through $\theta$, $p$, $q$ and $k$.

Given any parameter space ${\mathcal{P}}_{n}(\theta,p,q,k,\beta;\delta)$, we can define the following estimator:

If there is a tie, we break it arbitrarily. The estimator (7) is the maximum likelihood estimator for a special case of DCBM where $B_{uu}=p$ and $B_{uv}=q$ for all $u\neq v\in[k]$. In other cases, the objective function in (7) is a misspecified likelihood function. For any sequences $\{a_{n}\}$ and $\{b_{n}\}$, we write $a_{n}=\Omega(b_{n})$ if $a_{n}\geq Cb_{n}$ for some absolute constant $C>0$ for all $n\geq 1$. The following theorem characterizes the asymptotic behavior of the risk bounds for the estimator (7).

Consider any sequence $\{{\mathcal{P}}_{n}(\theta,p,q,k,\beta;\delta)\}_{n=1}^{\infty}$ such that as $n\to\infty$, $I\to\infty$, $p>q$, $\|\theta\|_{\infty}=o(n/k)$, $\min_{i\in[n]}\theta_{i}=\Omega(1)$ and $\log k=o(\min(I,\log{n}))$. When $k\geq 3$, further assume $\beta\in[1,\sqrt{5/3})$. Then the estimator in (7) satisfies

Before proceeding, we briefly discuss the conditions in Theorem 1. First, the condition $\min_{i\in[n]}\theta_{i}=\Omega(1)$ requires that all $\theta_{i}$’s are at least of constant order. One should note that this condition does not rule out the possibility that $\max_{i}\theta_{i}\gg\min_{i}\theta_{i}$, and so a great extent of degree variation, even within the same community, is allowed. Next, $\log k=o(\log n)$ requires that the number of communities $k$, if it diverges to infinity, grows at a sub-polynomial rate with the number of nodes $n$. Furthermore, $\beta\in[1,\sqrt{5/3})$ is a technical condition that we need for a combinatorial argument in the proof to go through when $k\geq 3$. Informed readers might find the result in Theorem 1 in parallel to that in . However, due to the presence of degree-correction parameters, the proof of Theorem 1 is significantly different from that of the corresponding result in . For example, a new folding argument is employed to deal with degree heterogeneity.

Minimax lower bounds

When $k=2$, there exists a disjoint partition $\mathcal{C}_{1},\mathcal{C}_{2}$ of $[n]$, such that $|\mathcal{C}_{1}|={\left\lfloor{n/2}\right\rfloor}$, $|\mathcal{C}_{2}|\in\{{\left\lfloor{n/2}\right\rfloor},{\left\lfloor{n/2}\right\rfloor}+1\}$ and $|\mathcal{C}_{u}|^{-1}\sum_{i\in\mathcal{C}_{u}}\theta_{i}\in(1-\delta/4,1+\delta/4)$ for $u=1,2$.

When $k\geq 3$, there exists a disjoint partition $\{\mathcal{C}_{u}\}_{u\in[k]}$ of $[n]$, such that $|\mathcal{C}_{1}|\leq|\mathcal{C}_{2}|\leq...\leq|\mathcal{C}_{k}|$, $|\mathcal{C}_{1}|=|\mathcal{C}_{2}|={\left\lfloor{n/(\beta k)}\right\rfloor}$ and $|\mathcal{C}_{u}|^{-1}\sum_{i\in\mathcal{C}_{u}}\theta_{i}\in(1-\delta/4,1+\delta/4)$ for all $u\in[k]$.

We note that the condition is only on $\theta$ (as opposed to the parameter space) and the actually communities in the data generating model need not coincide with the partition that occurs in the statement of the condition.

With the foregoing definition, we have the following result.

Consider any sequence $\{{\mathcal{P}}_{n}(\theta,p,q,k,\beta;\delta)\}_{n=1}^{\infty}$ such that as $n\to\infty$, $I\to\infty$, $1<p/q=O(1)$, $p\|\theta\|_{\infty}^{2}=o(1)$, $\log k=o(I)$, $\log(1/\delta)=o(I)$ and $\theta$ satisfies Condition N. Then

Compared with the conditions in Theorem 1, the conditions of Theorem 2 are slightly different. The condition $1<p/q=O(1)$ ensures that the smallest average within community connectivity is of the same order as (albeit larger than) the largest average between community connectivity. Such an assumption is typical in the statistical literature on block models. The condition $\|{\theta}\|^{2}_{\infty}p=o(1)$ ensures that the maximum expected node degree scales at a sublinear rate with the network size $n$. Furthermore, when $k=O(1)$, the condition $\log k=o(I)$ can be dropped because it is equivalent to $I\rightarrow\infty$, which in turn is necessary for the minimax risk to converge to zero.

Combining both theorems, we have the minimax risk of the problem.

Under the conditions of Theorems 1 and 2, we have

where $o(1)$ stands for a sequence whose absolute values tend to zero as $n$ tends to infinity.

Setting $\beta=1$ in Corollary 1 leads to the minimax result (1) in the introduction. We refer to Section 1 for the meanings of the terms in $I$.

When $\theta=1_{n}$, the foregoing minimax risk reduces to the corresponding result for stochastic block models in the sparse regime where $q<p=o(1)$. In this case, (6) implies that the minimax risk is

Note that when $q<p=o(1)$, the Rényi divergence of order $\frac{1}{2}$ used in the minimax risk expression in is equal to $(1+o(1))(\sqrt{p}-\sqrt{q})^{2}$.

An Adaptive and Computationally Feasible Procedure

Theorem 1 shows that the minimax rate can be achieved by the estimator (7) obtained via combinatorial optimization which is not computationally feasible. Moreover, the procedure depends on the knowledge of the parameters $\theta$, $p$ and $q$. These features make it not applicable in practical situations. In this section, we introduce a two-stage algorithm for community detection in DCBMs which is not only computationally feasible but also adaptive over a wide range of unknown parameter values. We show that the procedure achieves minimax optimal rates under certain regularity conditions.

The proposed algorithm consists of an initialization stage and a refinement stage.

To explain the rationale behind our proposal, with slight abuse of notation, let $P=(P_{ij})\in^{n\times n}$, where for all $i,j\in[n]$, $P_{ij}=P_{ji}=\theta_{i}\theta_{j}B_{z(i)z(j)}$. Except for the diagonal entries, $P$ is the same as in (3). For any $i\in[n]$, let $P_{i}$ denote the $i{{}^{\rm th}}$ row of $P$. Then for all $i$ such that $z(i)=u$, we observe that

are all equal. Thus, there are exactly $k$ different vectors that the normalized row vectors $\{\theta_{i}^{-1}P_{i}\}_{i=1}^{n}$ can be. Moreover, which one of the $k$ vectors the $i{{}^{\rm th}}$ normalized row vector equals is determined solely by its community label $z(i)$. This observation suggests one can design a reasonable community detection procedure by clustering the sample counterparts of the vectors $\{\theta_{1}^{-1}P_{1},\theta_{2}^{-1}P_{2},...,\theta_{n}^{-1}P_{n}\}$, which leads us to the proposal of Algorithm 1.

In Algorithm 1, Steps 1 and 2 aim to find an estimator $\hat{P}$ of $P$ by solving a low rank approximation problem. Then, in Step 3, we can use $\|{\hat{P}_{i}}\|_{1}^{-1}\hat{P}_{i}$ as a surrogate for $\theta_{i}^{-1}P_{i}$. Finally, Step 4 performs a weighted $k$-median clustering procedure applied on the row vectors of the $n\times k$ matrix $\begin{bmatrix}\|{\hat{P}_{1}}\|_{1}^{-1}\hat{P}_{1}\\ \cdots\\ \|{\hat{P}_{n}}\|_{1}^{-1}\hat{P}_{n}\end{bmatrix}$.

Refinement: normalized network neighbor counts

As we shall show later, the error rate of Algorithm 1 decays polynomially with respect to the key quantity $I$ defined in (6). To achieve the desired exponential decay rate with respect to $I$ as in the minimax rate, we need to further refine the community assignments obtained from Algorithm 1.

To this end, we propose a prototypical refinement procedure in Algorithm 2. The algorithm determines a possibly new community label for the $i{{}^{\rm th}}$ node by counting the number of neighbors that the $i{{}^{\rm th}}$ node has in each community normalized by the corresponding community size, and then picking the label of the community that maximizes the normalized counts. If there is a tie, we break it in an arbitrary way.

To see the rationale behind Algorithm 2, let us consider a simplified version of the problem. Suppose $k=2$, $n=2m+1$ for some integer $m\geq 1$, $B_{11}=B_{22}=p$ and $B_{12}=B_{21}=q$. Moreover, let us assume that the community labels of the first $2m$ nodes are such that $z(i)=1$ for $i=1,\dots,m$ and $z(i)=2$ for $i=m+1,\dots,2m$. The label of the last node $z(n)$ remains to be determined from the data. When $\left\{z(i):i=1,\dots,2m\right\}$ are the truth, the determination of the label for the $n{{}^{\rm th}}$ node reduces to the following testing problem:

The hypotheses $H_{0}$ and $H_{1}$ are joint distributions of $\{A_{n,i}\}_{i\in[n-1]}$ in the two cases $z(n)=1$ and $z(n)=2$, respectively. For this simple vs. simple testing problem, the Neyman–Pearson lemma dictates that the likelihood ratio test is optimal. However, it is not a satisfying answer for our goal, since the likelihood ratio test needs to use the values of the unknown parameters $p$, $q$ and $\theta$. While it is possible to obtain sufficiently accurate estimators for $p$ and $q$, it is hard to do so for $\theta$, especially when the network is sparse. In summary, the dependence of the likelihood ratio test on nuisance parameters makes it impossible to apply in practice. To overcome this difficulty, we propose to consider a simple test which

As we shall show later in Lemma 2 and Lemma 3, this simple procedure achieves the optimal testing error exponent. It is worthwhile to point out that it does not require any knowledge of $p$, $q$ or $\theta$, and hence the procedure is adaptive. A detailed study of the testing problem (10) is given in Section 5.1.

Inspired by the foregoing discussion, when $k=2$ and the two community sizes are different, we propose to normalize the counts in (11) by the community sizes. Moreover, when there are more than two communities, we propose to perform pairwise comparison based on the foregoing (normalized) test statistic for each pair of community labels, which becomes the procedure in (9) as long as we replace the unknown truth $z$ with an initial estimator $\hat{z}^{0}$. For a good initial estimator such as the one output by Algorithm 1, the refinement can lead to minimax optimal errors in misclassification proportion for a large collection of parameter spaces.

2 Performance Guarantees

The parameter $\alpha$ is assumed to be a constant no smaller than $1$ that does not change with $n$. By studying the proofs of Theorem 2 and Theorem 1, the minimax lower and upper bounds do not change for the slightly smaller parameter space $\mathcal{P}_{n}^{\prime}(\theta,p,q,k,\beta;\delta,\alpha)$. Therefore, the rate $\exp(-(1+o(1))I)$ still serves as a benchmark for us to develop theoretically justifiable algorithms for the parameter space $\mathcal{P}_{n}^{\prime}(\theta,p,q,k,\beta;\delta,\alpha)$.

As a first step, we provide the following high probability error bound for Algorithm 1.

Assume $\delta=o(1)$, $1<p/q=O(1)$ and $\|{\theta}\|_{\infty}=o(n/k)$. Let $\tau=C_{1}(np\|{\theta}\|_{\infty}^{2}+1)$ for some sufficiently large constant $C_{1}>0$ in Algorithm 1. Then, there exist some constants $C^{\prime},C>0$, such that for any generative model in $\mathcal{P}_{n}^{\prime}(\theta,p,q,k,\beta;\delta,\alpha)$, we have with probability at least $1-n^{-(1+C^{\prime})}$,

Lemma 1 provides a uniform high probability bound for the sum of $\theta_{i}$’s of the nodes which are assigned wrong labels. Before discussing the implication of this result, we give two remarks.

Algorithm 1 applies a weighted $k$-medians procedure on the matrix $\hat{P}$ instead of its leading eigenvectors. This is the main difference between Algorithm 1 and many traditional spectral clustering algorithms. As a result, we avoid any eigengap assumption that is imposed to prove consistency results for spectral clustering algorithms .

The extra $(1+\epsilon)$ slack that we allow in Algorithm 1 is also reflected in the error bound.

The following corollary exemplifies how the result of Lemma 1 can be specialized into a high probability bound for the loss function (4) with a rate depending on $I$ under some stronger conditions. These conditions, especially $\min_{i}\theta_{i}=\Omega(1)$, can be relaxed in Theorem 4 stated in the next paragraph.

Error rate for the refinement stage

As exemplified in Corollary 2, the convergence rate for the initialization step is typically only polynomial in $I$ as opposed to the exponential rate in the minimax rate. Thus, there is room for improvement. In what follows, we show that a specific way of applying Algorithm 2 on the output of Algorithm 1 leads to significant performance enhancement in terms of misclassification proportion. To this end, let us first state in Algorithm 3 the combined algorithm for which we are able to establish the improved error bounds. Here and after, for any $i\in[n]$, let $A_{-i}\in\{0,1\}^{(n-1)\times(n-1)}$ be the submatrix of $A$ obtained from removing the $i{{}^{\rm th}}$ row and column of $A$.

The last step (12) of Algorithm 3 constructs a final label estimator $\hat{z}$ from $\hat{z}_{-1}^{0},\hat{z}_{-2}^{0},...,\hat{z}_{-n}^{0}$. Since the labels given by $\hat{z}_{-1}^{0},\hat{z}_{-2}^{0},...,\hat{z}_{-n}^{0}$ are only comparable after certain permutations in $\Pi_{k}$, we need this extra step to resolve this issue.

Algorithm 3 is a theoretically justifiable version for combining Algorithm 1 and Algorithm 2. In order to obtain a rate-optimal label assignment for the $i{{}^{\rm th}}$ node, we first apply the initial clustering procedure in Algorithm 1 on the sub-network consisting of the remaining $n-1$ nodes and the edges among them. Then, one applies the refinement procedure in Algorithm 2 to assign a label for the $i{{}^{\rm th}}$ node. The independence between the initialization and the refinement stages facilitates the technical arguments in the proof. However, in practice, one can simply apply Algorithm 1 followed by Algorithm 2. The numerical difference from Algorithm 3 is negligible in all the data examples we have examined.

In the special case where the community sizes are almost equal, we can show that $\hat{z}$ output by Algorithm 3 achieves the minimax rate.

Under the conditions of Lemma 1, we further assume $\beta=1$, $k=O(1)$, $\min_{i}\theta_{i}=\Omega(1)$, $\delta=o(\frac{p-q}{p})$, $\|{\theta}\|_{\infty}^{2}p\geq n^{-1}$, and $\frac{(1+\epsilon)\|{\theta}\|_{\infty}p^{3/2}}{\sqrt{n}(p-q)^{2}}=o(1)$. Then there is a sequence $\eta=o(1)$ such that the output $\hat{z}$ of Algorithm 3 satisfies

Theorem 3 shows that when the community sizes are almost equal, the minimax rate $\exp(-(1+o(1))I)$ can be achieved within polynomial time. We note that the conditions that we need here are stronger than those of Theorem 1. When $k=O(1)$, $\epsilon=O(1)$ and $\Omega(1)=\min_{i}\theta_{i}\leq\|{\theta}\|_{\infty}=O(1)$, Theorem 1 only requires $I\rightarrow\infty$, which is equivalent to $\frac{p^{1/2}}{\sqrt{n}(p-q)}=o(1)$, while Theorem 3 requires $\frac{p^{3/2}}{\sqrt{n}(p-q)^{2}}=o(1)$. Whether the extra factor $\frac{p}{p-q}$ can be removed from the assumptions is an interesting problem to investigate in the future.

We now state a general high probability error bound for Algorithm 3. To introduce this result, we define another information-theoretic quantity. For any $t\in(0,1)$, define

By Jensen’s inequality, it is straightforward to verify that $J_{t}(p,q)\geq 0$ and $J_{t}(p,q)=0$ if and only if $p=q$. As a special case, when $t=\frac{1}{2}$, we have

For a given $z\in[k]^{n}$, let $n_{(1)}\leq...\leq n_{(k)}$ be the order statistics of community sizes $\{n_{u}(z):u=1,\dots,k\}$. Then, we define the quantity $J$ by through

with $t^{*}=\frac{n_{(1)}}{n_{(1)}+n_{(2)}}$. With the foregoing definitions, the following theorem gives a general error bound for Algorithm 3.

Under the conditions of Lemma 1, we further assume that $\delta=o(\frac{p-q}{p})$, $\|{\theta}\|_{\infty}^{2}p\geq n^{-1}$,

Then there is a sequence $\eta=o(1)$ such that the output $\hat{z}$ of Algorithm 3 satisfies

Theorem 4 gives a general error bound for the performance of Algorithm 3. It is easy to check that the conditions (16) and (17) are satisfied under the settings of Theorem 3. Therefore, Theorem 3 is a special case of Theorem 4. Theorem 4 shows that Algorithm 3 converges at the rate $\exp(-(1+o(1))J)$. According to the properties of $J_{t}(p,q)$ stated in Appendix B, one can show that when $n_{(1)}=(1+o(1))n_{(2)}$, $J=(1+o(1))I$, and that in general

Using this relation, we can state the convergence rate in Theorem 4 using the quantity $I$.

Under the conditions of Theorem 4, there is a sequence $\eta=o(1)$ such that the output $\hat{z}$ of Algorithm 3 satisfies

Therefore, when $k\geq 3$, the minimax rate $\exp(-(1+o(1))I)$ is achieved by Algorithm 3. The only situation where the minimax rate is not achieved by Algorithm 3 is when $k=2$ and $\beta>1$. For this case, there is an extra $\beta^{-1}$ factor on the exponent of the convergence rate.

If we further assume that $\min_{i\neq j}B_{ij}=\Omega(q)$, a careful examination of the proofs shows that we can improve the term $k^{5/2}$ in the conclusion of Lemma 1 and in the conditions (16) and (17) to $k^{3/2}$. Since it is unclear what the optimal power exponent for $k$ is in these circumstances, we do not pursue it explicitly in this paper.

Numerical Results

In this section, we present numerical experiments on simulated datasets generated from DCBMs. In particular, we compare the performance of two versions of our algorithm with two state-of-the-art methods: SCORE and CMM in two different scenarios. On simulated data examples, both versions of our algorithm outperformed SCORE in terms of misclassification proportion. The performance of CMM was comparable to our algorithm. However, our algorithm not only demonstrated slightly better accuracy on the simulated datasets when compared with CMM, but it also enjoys the advantage of easy implementation, fast computation and scalability to networks of large sizes since it does not involve convex programming.

We compare misclassification proportions of the following five algorithmsThe numerical performance of Algorithm 3 was indistinguishable from that of the second algorithm in the list in all the experiments conducted.:

The weighted $k$-medians procedure in Algorithm 1;

Refinement of the output of Algorithm 1 by Algorithm 2;

Iterate Algorithm 2 $10$ times after initialization by Algorithm 1.

We conducted the experiments with $100$ independent repetitions and summarize the performances of the five algorithms through boxplots of misclassification proportions. Fig. 1 shows that our refinement step (Algorithm 2) significantly improved the performance of the initialization step (Algorithm 1). Moreover, it helped to further reduce the error if we apply the refinement step for a few more iterations. Among the five algorithms, our proposed procedures give the best performance. The CMM algorithm performed slightly worse than our procedures with refinement, but was better than Algorithm 1 and SCORE.

Scenario 2

As in Scenario 1, we compare the performance of the five algorithms over $100$ independent repetitions. Fig. 2 shows the boxplots of the misclassification proportions. The overall message is similar to Scenario 1, except that CMM performed almost as good as our procedures with refinement, but all of them outperformed Algorithm 1 and SCORE. Despite its comparable performance on this task, CMM required noticeably longer running time than our procedures on the simulated datasets due to the involvement of convex programming. Therefore, its scalability to large networks is more limited.

Proofs

This section presents proofs for some main results of the paper. In Section 5.1, we first study a fundamental testing problem for community detection in DCBMs. The theoretical results for this testing problem are critical tools to prove minimax lower and upper bounds for community detection. We then state the proof of Theorem 1. Proofs of the other main results are deferred to the appendices.

As a prelude to all proofs, we consider the hypothesis testing problem (10) that not only is fundamental to the study of minimax risk but also motivates the proposal of Algorithm 2. To paraphrase the problem, suppose $X=(X_{1},\dots,X_{m},X_{m+1},\dots,X_{2m})$ have independent Bernoulli entries. Given $1\geq p>q\geq 0$ and $\theta_{0},\theta_{1},\dots,\theta_{2m}>0$ such that

We are interested in understanding the minimum possible Type I+II error of testing

In particular, we are interested in the asymptotic behavior of the error for a sequence of such testing problems in which $p$, $q$ and the $\theta_{i}$’s scale with $m$ as $m\to\infty$. First, we have the following lower bound result.

Suppose that as $m\to\infty$, $1<p/q=O(1)$ and $p\max_{0\leq i\leq 2m}\theta_{i}^{2}=o(1)$. If $\theta_{0}m(\sqrt{p}-\sqrt{q})^{2}\to\infty$,

Otherwise if $\theta_{0}m(\sqrt{p}-\sqrt{q})^{2}=O(1)$, there exists a constant $c\in(0,1)$ such that

According to Neyman-Pearson lemma, the optimal testing procedure is the likelihood ratio test. However, such a test depends on the values of $\{\theta_{i}\}_{i=1}^{2m},p,q$, and is not appropriate in practice. We consider an alternative test

This test is simple, but achieves the optimal error bound.

For the testing function defined above, we have

Combining Lemma 2 and Lemma 3, we find that the minimax testing error for the problem (19) is $e^{-(1+o(1))\theta_{0}m(\sqrt{p}-\sqrt{q})^{2}}$. This explains why the minimax rate for community detection in DCBM takes the form of $e^{-(1+o(1))I}$ in Corollary 1. Moreover, the simple testing function (20) serves as a critical component in Algorithm 2. The fact that (20) can achieve the optimal testing error exponent in Lemma 3 explains why our algorithm for community detection can achieve the minimax rate when the community sizes are equal (Theorem 3).

In order for Lemma 2 to be applied to lower bounding the performance of community detection in DCBM, we need a version of Lemma 2 that can handle approximately equal sizes. To be specific, suppose $X=(X_{1},\dots,X_{m},\\ X_{m+1},\dots,X_{m+m_{1}})$ have independent Bernoulli entries. Given $1\geq p>q\geq 0$ and $\theta_{0},\theta_{1},\dots,\theta_{m+m_{1}}>0$ such that

When $m$ and $m_{1}$ are approximately equal, we are interested in understanding the minimum possible Type I+II error of testing

The setting of Lemma 2 is a special case where $m=m_{1}$ and $\delta=0$.

Suppose that as $m\to\infty$, $1<p/q=O(1)$, $p\max_{0\leq i\leq 2m}\theta_{i}^{2}=o(1)$, $\delta=o(1)$ and $\left|\frac{m}{m_{1}}-1\right|=o(1)$. If $\theta_{0}m(\sqrt{p}-\sqrt{q})^{2}\to\infty$,

Otherwise, there exists a constant $c\in(0,1)$ such that

2 Proof of Theorem 1

In the last step, we supply the bounds obtained in the second step to (23) to establish the theorem. Indeed, the bounds we derive in the second step decay geometrically once $m$ is larger than some critical value which depends on the rate of the error bounds. Thus, we divide the final arguments here according to three different regimes of error rates.

After a brief introduction to some additional notation, we carry out these three steps in order. We denote $n_{\min}=\min_{u\in[k]}|\{i:z(i)=u\}|$, $n_{\max}=\max_{u\in[k]}|\{i:z(i)=u\}|$ and $\theta_{\min}=\min_{i\in[n]}\theta_{i}$. Note that $n_{\min}\geq n/(\beta k)$, $n_{\max}\leq\beta n/k$ and $\theta_{\min}=\Omega(1)$. For any $t\in(0,1)$, we define

where the second inequality is by Jensen inequality.

Similarly, when $z(i)\neq z(j)$ we also have

Let $M\geq 2$ be a large enough constant integer to be determined later. For each $\mathcal{C}_{u}$ we decompose it as $\mathcal{C}_{u}=\mathcal{C}_{u}^{+}\cup\mathcal{C}_{u}^{-}$ such that

Due to the approximate normalization of degree-correction parameters, for sufficiently large values of $n$,

Since $|\mathcal{C}_{u}^{+}|\leq(M-1)|\mathcal{C}_{u}^{-}|$, we can define a mapping $\tau_{u}:\mathcal{C}_{u}\rightarrow\mathcal{C}_{u}^{-}$ such that its restriction on $\mathcal{C}_{u}^{-}$ is identity. Moreover, we could require that for any $i\in\mathcal{C}_{u}^{-}$, $|\tau_{u}^{-1}(i)|\leq M$. Let $\tau$ be the mapping from $[n]$ to $\cup_{u=1}^{k}\mathcal{C}_{u}^{-}$ such that the restriction of $\tau$ on ${\mathcal{C}_{u}}$ is $\tau_{u}$. The main reason for introducing $\tau$ is to deal with the range of values the degree-correction parameters can take. The right side of (25) shows that the desired bounds depend crucially on quantities of the form $\sum_{i\in S}\theta_{i}$ for some set $S$. For any set $S$, the sum $\sum_{i\in S}\theta_{i}$ is not necessarily upper bounded by a constant multiple of the size of the set $|S|$. However, by (27), we can always upper bound $\sum_{i\in S}\theta_{\tau(i)}$ by a constant multiple of $|S|$. This gives us a way to relate the probability bounds and the number of misclassified nodes. Such a point can be seen more clearly as we go to explicit calculation below.

Here, the first inequality comes from direct application of (25) and the union bound. Since $\|\theta\|_{\infty}=o(n/k)=o(n_{\min})$ and $M$ is a constant, we have $\sum_{i\in\Gamma}\theta_{i}=o(n_{\min})$. This, together with the monotonicity of the function $x(1-x)$ when $x$ is in the right neighborhood of zero, implies the second inequality. The third inequality is due to (27). Since $M$ is a constant and $M/n_{\min}$ can be upper bounded by $\eta$ for large values of $n$, we further have

In this case, we cannot directly apply the argument in case 1 since we can no longer guarantee that $\sum_{i\in\Gamma}\theta_{i}=o(n_{\min})$ and so the second inequality of the last display no longer holds. To proceed, we can further bound the rightmost side of (25) by $B_{1}\times B_{2}$, where

In what follows, we focus on upper bounding $B_{1}$ and the same upper bound holds for $B_{2}$ by essentially repeating the arguments. For $B_{1}$, we have

Fig. 3 illustrates why the inequality in (30) holds. Furthermore, we notice that

To further bound the right side of (31), recall that $\theta_{\min}=\min_{i}\theta_{i}=\Omega(1)$. Then

Here the last inequality holds since $|\Gamma_{u}|\leq|\Gamma|\leq m^{\prime}=o(n_{\min})\leq\frac{1}{2}|\mathcal{C}_{u}|$. Together with the property of the function $x(1-x),x\in$, when $M\geq\frac{5}{\theta_{\min}}$, we have

Here, the first inequality holds since $\sum_{i\in\tau_{u}(\Gamma_{u})}\theta_{i}\leq|\tau_{u}(\Gamma_{u})|\max_{i\in\mathcal{C}_{u}^{-}}\theta_{i}\leq 2(M^{-1}|\mathcal{C}_{u}|+1)\leq\frac{1}{2}|\mathcal{C}_{u}|\theta_{\min}$. The second inequality is due to (27), $n_{\min}\geq\frac{n}{\beta k}-1$ and the fact $|\tau_{u}(\Gamma_{u})|\leq|\Gamma_{u}|\leq\eta n/k$ in the current case. Thus

Since for any $i\in\mathcal{C}_{u}^{-}$, $|\tau_{u}^{-1}(i)|\leq M$, we obtain that $|\tau(\Gamma)|\geq m/M$, and so we have

Here, the second inequality is based on counting and the details are as follows. Note that each term in $\prod_{i\in\tau(\Gamma)}$ is a product of at least $m/M$ terms. First, there are at most ${m\choose m/M}$ of sets $\tau(\Gamma)$ that map to the same $m/M$-product. Then, there are at most ${mM\choose m}$ of sets $\Gamma$ that map to the same $\tau(\Gamma)$ (recall that for any $i\in\mathcal{C}_{u}^{-}$, $|\tau_{u}^{-1}(i)|<M$). For each $m/M$-product, it appear at most $(m/M)!$ times from the expansion of $nR_{\delta+2\eta}$, and that explains the existence of $1/(m/M)!$. The last inequality holds since \binom{n}{m}\leq\big{(}\frac{en}{m}\big{)}^{m} and $n!\geq\sqrt{2\pi}n^{n+1/2}e^{-n}$.

In each $\Gamma_{u,u^{\prime}},\forall 1\leq u,u^{\prime}\leq k$ we can find an arbitrary subset $\Gamma^{\prime}_{u,u^{\prime}}\subset\Gamma_{u,u^{\prime}}$ such that $|\Gamma^{\prime}_{u,u^{\prime}}|=\eta|\Gamma_{u,u^{\prime}}|$. In this way $\Gamma^{\prime}\triangleq\cup_{u\in[k]}\cup_{u^{\prime}\neq u}\Gamma^{\prime}_{u,u^{\prime}}$ satisfies $|\Gamma^{\prime}|=\eta|\Gamma|\leq\eta m$ and $\sum_{i\in\Gamma^{\prime}_{u,u^{\prime}}}\theta_{i}\leq 2|\Gamma^{\prime}_{u,u^{\prime}}|\leq 2\eta|\mathcal{C}_{u}|$.

Together with the property of the function $x(1-x),x\in$, we have

Thus with the same bound on $B_{2}$ we get

Note we have an extra $1/2$ factor inside the exponent compared with Case 2. Since for each $\Gamma$ we can find a subset $\Gamma^{\prime}$ with $|\Gamma^{\prime}|=\eta|\tau(\Gamma)|\geq\eta m/M$ satisfying the above inequality, we have

where the last equality is due to Cauchy-Schwarz.

As we have pointed out in the proof outline, we shall combine (23) with (33) in this step to finish the proof. To this end, we divide the argument into three cases according to different possible growth rates of $R_{\delta+2\eta}$.

for some constant $C_{1}>1$ where the last inequality is due to the properties of power series. For $m>m^{\prime}$ we have

We are to show that the above ratio is upper bounded by $e^{-m}$. This is because $e^{2}Mn/(\eta^{2}m/M)\leq\eta^{-3}e^{2}M^{2}k$ since $m\geq\eta n/k$ and $e^{2}MnR_{\delta+2\eta}/(\eta^{2}m/M)\leq 1/(2(kM)^{M}\eta^{3}n)$ since $nR_{\delta+2\eta}\leq 1/(2(eM)^{M})$. Then for some constant $C_{2}>0$ we have

where the last inequality is due to the fact that $k\leq n^{\eta}$. By the property of power series we have

for some constant $C_{3}>0$. Finally by Jensen’s inequality and the assumption $\log k=o(I)$,

To obtain the last display, we divide both sides of (23) by $n$, replace all the $m$’s in front of the probabilities in the summation by $n$ and then upper bound the first $m_{0}$ probabilities by one. To further bound the right side of the last display, we have

Since $m_{0}\geq 2M\log n$, we have $2^{-m/M}\leq 2^{-2\log n}\leq m_{0}/n$. Thus

Since $R_{\delta+2\eta}\leq\exp(-(1-\delta-2\eta)I)$ by Jensen’s inequality, $\log k=o(I)$ and $\eta^{-1}=o(I)$, we have $\eta^{-3}(ekM)^{\frac{M}{\eta}+3}R^{1/2}_{\delta+2\eta}\leq 1/2$. Then

Appendix A Additional Proofs of Main Results

Denote $m^{\prime}=\eta n$ for some $\eta=o(1)$ satisfying $\eta^{-1}=o(I)$. We define $\tau$ exactly the same way as in Section 5.2. We use the notation

Recall the constant $M$ used in Section 5.2. Case 1: $1\leq m\leq M$. By (34), we have

Using the argument in Section 5.2, we have

Case 3: $m>m^{\prime}$. Under this scenario, we can take an arbitrary subset $\Gamma^{\prime}\subset\tau(\Gamma)$ such that $|\Gamma^{\prime}|=\eta m/M$, which leads to $\sum_{i\in\Gamma^{\prime}}\theta_{i}\leq 2\eta n$. Recall $n-\sum_{i\in\Gamma}\theta_{i}=\sum_{i\in\Gamma^{c}}\theta_{i}\geq|\Gamma^{c}|\theta_{\min}\geq n\theta_{\min}/2$. Using (34), together with the property of $x(1-x)$ for $x\in$, we have

By the argument used in Section 5.2, we have

A.2 Proof of Theorem 2

We only state the proof for the case $k\geq 3$. The proof for the case $k=2$ can be derived using essentially the same argument. For a label vector, recall the notation $n_{u}(z)=|\{i\in[n]:z(i)=u\}|$. Under Condition N, there exists a $z^{*}\in[k]^{n}$ such that $n_{1}(z^{*})\leq n_{2}(z^{*})\leq n_{3}(z^{*})\leq\cdots\leq n_{k}(z^{*})$ with $n_{1}(z^{*})=n_{2}(z^{*})={\left\lfloor{n/(\beta k)}\right\rfloor}$, and that $(n_{u}(z^{*}))^{-1}{\sum_{i:z^{*}(i)=u}\theta_{i}}\in(1-\frac{\delta}{4},1+\frac{\delta}{4})$ for all $u\in[k]$.

$1^{\circ}$ As a first step, we define a community detection problem on a subset of the parameter space such that we can avoid the complication of label permutation. To this end, given $z^{*}$, for each $u\in[k]$, let $T_{u}\subset\{i:z^{*}(i)=u\}$ with cardinality ${\left\lceil{n_{u}(z^{*})-\frac{\delta n}{4k^{2}\beta}}\right\rceil}$ collect the indices of the largest $\theta_{i}$’s in $\{\theta_{i}:{z(i)=u}\}$. Let $T=\cup_{u=1}^{k}T_{u}$. Define

Since $z^{*}\in Z^{*}$, the latter is not empty. By the definition of $T$ and Condition N, $\max_{i\in T^{c}}\theta_{i}$ is bounded by a constant. Thus, for any $z$ such that $z(i)=z^{*}(i)$ for all $i\in T$, we have

Therefore, we can define a smaller parameter space ${\mathcal{P}}_{n}^{0}={\mathcal{P}}_{n}^{0}(\theta,p,q,k,\beta;\delta)\subset{\mathcal{P}}_{n}(\theta,p,q,k,\beta;\delta)$ where

$2^{\circ}$ We now turn to lower bounding the rightmost side of (36), which relies crucially on our previous discussion in Section 5.1. To this end, observe that

for some constant $c>0$. Here, $\operatorname*{\operatorname{ave}}$ stands for arithmetic average. The first inequality holds since minimax risk is lower bounded by Bayes risk. The second inequality is due to the fact that for any $z\in Z^{*}$, $z(i)=z^{*}(i)$ for all $i\in T$, and so infimum can be taken over all $\hat{z}$ with $\hat{z}(i)=z^{*}(i)$ for $i\in T$. The last inequality holds because $|T^{c}|\geq c\frac{\delta n}{k}$ for some constant $c$ by its definition.

Note that for any $u\neq v$, there is a 1-to-1 correspondence between the elements in $Z^{*}_{u}$ and $Z^{*}_{v}$. In particular, for each $z\in Z^{*}_{u}$, there exists a unique $z^{\prime}\in Z^{*}_{v}$ such that $z(i)=z^{\prime}(i)$ for all $i\neq 1$. Thus, we can simultaneously index all $\{Z^{*}_{u}\}_{u=1}^{k}$ by the second to the last coordinates of the $z$ vectors contained in them. We use $z_{-1}$ to indicate the subvector in $[k]^{n-1}$ excluding the first coordinate and collect all the different $z_{-1}$’s into a set $Z_{-1}$. Then we have

Note that by the definition of $z^{*}$ and $Z^{*}$, it is guaranteed that for either $(1,z_{-1})$ or $(2,z_{-1})$, $|\frac{n_{1}}{n_{2}}-1|=o(1)$. Therefore, we can apply Lemma 4 to bound from below each term in the summation of the rightmost side of the last display by $\exp\left(-(1+\eta)\theta_{1}\frac{n}{\beta k}(\sqrt{p}-\sqrt{q})^{2}\right)$ for some $\eta=o(1)$. Together with (36) – (38), this implies that

Here, the first inequality is simple algebra. The second inequality holds since $T^{c}$ only contains within each community defined by $z^{*}$ the nodes with the smallest $\theta_{i}$’s. The third inequality is a direct application of Jensen’s inequality, and the last equality holds since $\log k=o(I)$ and $\log\frac{1}{\delta}=o(I)$. This completes the proof.

A.3 Proofs of Lemma 1 and Corollary 2

We now prove Lemma 1 and Corollary 2, which characterize the performance of Algorithm 1. To prove Lemma 1, we need two auxiliary lemmas, whose proofs will be given in Appendix C. In the rest of this part, we let $P=(P_{ij})=(\theta_{i}\theta_{j}B_{z(i)z(j)})$ for notational convenience.

The following lemma characterizes the connection between measure on misclassification and geometry of the point cloud. The result is not tied to any specific clustering algorithm or choice of norm.

Under the settings of Lemma 1, let $\tau=C_{1}\left(np\|{\theta}\|_{\infty}^{2}+1\right)$ for some sufficiently large $C_{1}>0$ in Algorithm 1. Then, for any constant $C^{\prime}>0$, there exists some $C>0$ only depending on $C_{1},C^{\prime}$ and $\alpha$ such that

with probability at least $1-n^{-(1+C^{\prime})}$ uniformly over ${\mathcal{P}}_{n}^{\prime}(\theta,p,q,k,\beta;\delta,\alpha)$.

under the conditions $\delta=o(1)$ and $\|{\theta}\|_{\infty}=o(n/k)$.

Note that $\bar{P}_{i}=\bar{P}_{j}$ when $z(i)=z(j)$. Our first task is to lower bound $\|{\bar{P}_{i}-\bar{P}_{j}}\|_{1}$ when $z(i)\neq z(j)$, which serves as the separation condition among different clusters. For any $i$ and $j$ such that $z(i)=u\neq v=z(j)$, we assume $\|{P_{i}}\|_{1}/\theta_{i}\leq\|{P_{j}}\|_{1}/\theta_{j}$ without loss of generality. Then,

Here, (41) holds since $\frac{\|{P_{j}}\|_{1}/\theta_{j}}{\|{P_{i}}\|_{1}/\theta_{i}}B_{uu}\geq p$ and $B_{uv}\leq q$, and (42) is due to (40). By switching $i$ and $j$, the foregoing argument also works for the case where $\|{P_{i}}\|_{1}/\theta_{i}>\|{P_{j}}\|_{1}/\theta_{j}$. Hence,

In order to bound $\sum_{i\in S}\theta_{i}$, we first derive a bound for $\sum_{i\in S}\|{\hat{P}_{i}}\|_{1}$. That is,

where (A.3) uses the definition of $S$, (47) is by the inequality (45), and (48) is by the inequality $\|{\|{x}\|_{1}^{-1}x-\|{y}\|_{1}^{-1}y}\|_{1}\leq\frac{2\|{x-y}\|_{1}}{\|{x}\|_{1}\vee\|{y}\|_{1}}$ which in turn is due to the triangle inequality.

Now we are ready to bound $\sum_{i\in S}\theta_{i}$ as

where (50) is by the inequality (40), (51) is due to the triangle inequality, (52) uses (49) and Cauchy-Schwarz, and (53) holds since $\alpha,\beta,k\geq 1$.

We now turn to bounding $\sum_{i\in S_{0}}\theta_{i}$. To this end, simple algebra leads to

where (54) is by the inequality (40), (55) uses the definition of $S_{0}$ and (56) is due to the Cauchy-Schwarz inequality.

Combining the bounds in (53), (56) and (44), we have

where we have absorbed $\alpha$ and $\beta$ into the constant $C$. By Lemma 6, we have

with probability at least $1-n^{-(1+C^{\prime})}$. This completes the proof. ∎

A.4 Proofs of Theorem 3, Theorem 4 and Corollary 3

Now we are going to give proofs of Theorem 3, Theorem 4 and Corollary 3. Note that both Theorem 3 and Corollary 3 are direct consequences of Theorem 4. The main argument in the proof of Theorem 4 is the following lemma.

Suppose $1<p/q=O(1)$ and $\delta=o\left(\frac{p-q}{p}\right)$. If there exist two sequences $\gamma_{1}=o\left(\frac{p-q}{kp}\right)$ and $\gamma_{2}=o\left(\frac{p-q}{k^{2}p}\right)$, a constant $C_{1}>0$ and permutations $\{\pi_{i}\}_{i\in[n]}\subset\Pi_{k}$ such that

uniformly for all probability distributions in $\mathcal{P}_{n}^{\prime}(\theta,p,q,k,\beta;\delta,\alpha)$. Then, we have for all $i\in[n]$,

uniformly for all probability distributions in $\mathcal{P}_{n}^{\prime}(\theta,p,q,k,\beta;\delta,\alpha)$, where $\eta=o(1)$.

Define independent random variables $X_{i}\sim\text{Bernoulli}(\theta_{1}\theta_{i}q)$, $Y_{i}\sim\text{Bernoulli}(\theta_{1}\theta_{i}p)$, and $Z_{i}\sim\text{Bernoulli}(\theta_{1}\theta_{i}p)$ for all $i\in[n]$. Then, a stochastic order argument bounds the right hand side of (59) by

Using Chernoff bound, for any $\lambda>0$, we upper bound (60) by

We are going to give bounds for the four terms (64), (64), (64) and (64), respectively. On the event $E_{1}$,

which is a bound for (64). A similar argument leads to a bound (64), which is

Finally, we need a bound for (64). With the current choice of $\lambda$,

where $\tau=\frac{n_{1}}{n_{1}+n_{2}}$ and $\hat{\tau}=\frac{m_{1}}{m_{1}+m_{2}}$. We will give a bound for $\left|J_{\tau}(p,q)-J_{\hat{\tau}}(p,q)\right|$. Since $\left|\frac{\partial}{\partial\tau}J_{\tau}(p,q)\right|=\frac{1}{2}\left|(p-q)-p^{t}q^{1-t}\log\frac{p}{q}\right|\leq\frac{1}{2}|p-q|+\frac{1}{2}p|\log p-\log q|\leq|p-q|$, we have $\left|J_{\tau}(p,q)-J_{\hat{\tau}}(p,q)\right|\leq|p-q||\tau-\hat{\tau}|\leq\beta k\gamma_{2}(p-q)$. Hence, we have a bound for (64), which is