Semi-supervised Community Detection via Structural Similarity Metrics
Authors: Yicong Jiang
Tracy Ke
Venue: ICLR 2023 poster (2023)
Keywords: Semi-supervised
Community Detection
Network
DCBM
Degree Heterogeneity
Non-Assortative

Abstract: Motivated by the interests of social network analysis and network-based recommendation systems, we consider a semi-supervised community detection problem, where the goal is to estimate the community label of a new node by leveraging on the network structure and partially observed community labels of existing nodes. 
We model the network with a degree-corrected stochastic block model, which allows for severe degree heterogeneity and potentially non-assortative communities. 
We propose a fast algorithm that computes a `structural similarity metric' between the new node and each of the $K$ communities, aggregating information in labeled and unlabeled data. The estimated label of the new node is equal to the value of $k$  that maximizes this similarity metric. Our method is computationally fast and compares favorably with existing semi-supervised algorithms on numerical performance. In theory, we derive explicit bounds for the misclassification error and show the efficiency of our method by comparing it with an ideal classifier. To our best knowledge, our results provide the first semi-supervised community detection algorithm with theoretical guarantees.  

Published as a conference paper at ICLR 2023
SEMI-SUPERVISED COMMUNITY DETECTION VIA STRUCTURAL SIMILARITY METRICS
Yicong Jiang, Tracy Ke
Department of Statistics Harvard University Cambridge, MA 02138, USA
ABSTRACT
Motivated by social network analysis and network- -ased recommendation systems, we study a cemi-super community detection problem in which the objective is to estimate the community label of new node using the network topology and partially observed community labels of existing nodes. The network is modeled stochastic block model, which allows for severe degree
using a degree-correcee heterogeneity and potentially non assortttteee communities. We propose algo- rithm that computes a 'structural similarity metric' between the new node and each of the K communities by aggregating labeled and unlabeled data. The estimated label of the new node corresponds to the value of & that maximizes this similarity metric. Our method is fast and numerically outperforms existing semi-supervised algorithms. Theoretically, we derive explicit bounds for the misclassification error and show the efficiency of our method by comparing it with an ideal classifier. Our findings highlight, to the best of our knowledge, the first semi- cami-supervised community detection algorithm that offers theoretical guarantees.
INTRODUCTION
Nowadays, large network data frequently observed social media (such Facebook, Twitter, and LinkedIn), science, and social science. Learning the latent community structure in a network of particular interest. For example, community analysis useful in designing recommendation systems (Debnath et al.] 2008), measuring scholarly impacts (Ji et al. 2022), and re-constructing pseudo-dynamies in single-cell data (Liu et al. 2018). this paper, we consider a semi-supervised community detection setting: we are given symmetric network with nodes, and denote by A E R the adjacency matrix, where A,g E {o, 1} indicates whether there is an edge between nodes i and j. Suppose the nodes partition into K non-overlapping communities C₁, C2....,Cra For a subset C {1, 2..,,...... nI. we observe the true community label y/ E (1,2..... K) for each E L. Write m L] and Y2- (y))iec In this context, there are two related semi-supervised community detection problems: (i) in sample classification, where the goal is to classify all the existing unlabeled nodes; (ii) prediction, where the goal is to classify a new node joining the network. Notably, the in-sample classification problem can be easily reduced to prediction problem: we can successively single out each existing unlabeled node, regard it as the "new node". and then predict its label by applying an algorithms for the prediction problem. Hence, for most of the paper, we focus on the prediction problem and defer the study of in-sample classification problem, let X E 13" denote the vector consisting of edges between the new node and each of the existing nodes. Given (A, Yc, X). our goal to estimate the community label of the new node,
...
Section 3 In the prediction
This problem has multiple applications. Consider the news suggestion or online advertising push for new Facebook user (Shapira et al. (003)). Given big Facebook network of existing users, for a small fraction of nodes (e.g., active users), we may have good information about the communities to which they belong, whereas for the majority of users, we just observe who they link to. We are interested in estimating the community label of the new user in order to personalize news or ad recommendations. For another example, in a co-citation network of researchers (Ji et al. 2022), each community might be interpreted as group of researchers working clear understanding of the research areas of some authors (c.g., senior authors), and we intend to use this knowledge to determine the community to which new node (e.g., junior author) belongs.
the same research area. We frequently have

---

Published as a conference paper at ICLR 2023
The statistical literature community detection has mainly focused on the wnsupervised setting (Bickel & Chen 2009; Rohe et al., [011]] Jin. 2015| Gao et al.] 2018 Li et al. (021). The semi- supervised setting is less studied. Leng & Ma (2019) offers a comprehensive literature review of semi-supervised community detection algorithms. Liu et al. (2014) and et al. (2016) derive systems of linear equations for the community labels through physics theory, and predict the labels by solving those equations. Zhou et al. (2018) leverages on the belief' function to propagate labels across the network, so that one can estimate the label of a node through its belief. [etzell al. (2018) extracts several patterns in size and structural composition across the known communities and search for similar patterns in the graph. Yang et al. (2015) unifies a number of different community detection algorithms based on non-negative matrix factorization or spectral clustering under the unsupervised setting, and fits them into the semi-supervised scenario by adding various regularization terms to encourage the estimated labels for nodes in L to match with the clustering behavior of their observed labels. However, the existing methods still face challenges. First, many of them employ the heuristic that node tends to have more edges with nodes in the same community than those in other communities. This is true only when communities are assortative. But assoortrteeevve communities also seen in real networks (Goldenberg et al.) 2010; Betzel et al.) 2018); for instance, Facebook users sharing similar restaurant preferences are not necessarily friends of each other. Second, real networks often have severe degree heterogeneity (i.e., the degrees of some nodes can be many times larger than the degrees of other nodes), but most semi-supervised community detection algorithms do not handle degree heterogeneity. Third, the optimization-basee algorithms (Yang et al. 2015) solve non-convex problems and face the issue of local minima. Last, to our best knowledge, none of the existing methods have theoretical guarantees.
Attributed network clustering is problem related to community detection, for which many algorithms have been developed (please see CCunaev et al. (2019) for nice survey). The graph neural networks (GNN) reported great successes in attributed network clustering. Kipf & Welling (2016) proposes a graph convolutional network (GCN) approach to semi-supervised community detection, and Din let al. 2019) combines GNN with the Markov random field to predict node labels. However, GNN is designed for the setting where each node has a large number of attributes and these attributes contain rich information of community labels. The key question in the GNN research is how utilize the graph to better propagate messages. In contrast, we are interested in the scenario where it is infeasible or costly collect node attributes. For instance, it is easy to construct co-authorship network from bibtex files, but collecting features of authors is much harder. Additionally, a number of benchmark network datasets do not have attributes (e.g. Caltech (Red et al., 2011 Traud al. 2012). Simmons (Red et al., 2 Traud et al., 2012), and Polblogs (Adamic & Glance, 2005)). It is unclear how to implement GNN on these data sets. In Section 4 we briefly study the performance of GNN with self-created nodal features from 1-hop representation, graph topology and node embedding. Our experiments indicate that GNN often not suitable for the case of no node attributes.
We propose a new algorithm for semi-supervised community detection to address the limitations of existing methods. We adopt the DCBM model (Karrer & Newman [01 for networks, which models degree heterogeneity and allows for both assortative and non-assortative communities. Inspired by the viewpoint of Goldenberg et al. (2010) that a 'community' is a group of 'structurally equivalent" nodes, design a structural similar metric between the new node and each of the K communities. This metric aggregates information in both labeled and unlabeled nodes. We then estimate the community label of the new node by the ie that maximizes this similarity metric. Our method is easy implement, computationally fast, and compares favorably with other methods in numerical experiments. In theory, we derive explicit bounds for the misclassification probability of our method under the DCBM model. We also study the efficiency of our method by comparing its misclassification probability with that of an ideal classifier having access to the community labels of all nodes.
2 SEMI-SUPERVISED COMMUNITY DETECTION
Recall that A is the n x n adjacency matrix on the existing nodes and Yz contains the community labels of nodes in L. Write [n] = {1,2, 2,...... .......... n. and let = [n)] \ L denote the set of unlaheled nodes. We index the new node by n + and let X E R² be the binary vector consisting of the edges between the new node and existing nodes. Denote by A the adjacency matrix for the network of (n + 1) nodes.
2.1 The DCBM model and structural equivalence of communities We model with the degree- corrected block model (DCBM) (Karrer & Newman 2011). Define a K-ddimenionnal membership
2

---

Published as a conference paper at ICLR 2023
matrix fei,e2,... e2,...,,kkk where e 's are the standard basis vectors of R We encode the community labels by Ty, where Tे = c if and only if y = k. For a symmetric nonnegative matrix P E R and a degree parameter 0; (0, 1] for each node we assume that the upper triangle of A contains independent Bernoulli variables, where
P(A, = 1) 0.0, -
for all 1 isifjin=
When 0: are equal, the DCBM model reduces to the stochastic block model (SBM). Compared with SBM, DCBM more flexible as accommodates degree heterogeneity. For a matrix M or a vector let (M) and diag(v) denote the diagonal matrices whose diagonals are from the diagonal of M or the vector v, respectively. Write B (81,02,... 1...0.,.,,................. 8n+1)', θ diag(f), and
II [T,, 22. +T+1 E I Model 1
yields that
A = Ω diag(12) + W. where Q = ÓTIPIT' and W = A E.A
(2)
Here, 92 is low-rank matrix that captures the 'signal', W is generalized Wigner matrix that captures "noise", and diag(S2) yields a bias to the 'signal' but its effect is usually negligible.
The DCBM belongs to the family of block models for networks. In block models, it is not necessarily true that the edge densities within a community are higher than those between different communities. Such communities appear in many real networks (Goldenberg et al. 2010)Betzel et al. 2018). For instance, in news and ad recommendation, we interested in identifying a group of users who have similar behaviors, but they may not be densely connected to each other. Goldenberg et al. (2010) introduced an intuitive notion of structural equivalence similar nodes is similar. They argued that a 'community" in block models is group of structurally cquivalent nodes. This way of defining communities is more general than assortative communities.
called assortative communities. However, non assortative communities also
nodes structurally equivalent if their connectivity with
We introduce a rigorous description of structural equivalence in the DCBM model. For two vectors u a and v, define (u, v) = arccos ||all [rrj) which the angle between these two vectors. Let A, be the ith column of A. This vector describes the 'behavior' of node i in the network. Recall that Ωi is as in 2). When the signal-to-noise ratio is sufficiently large, A, RS 9. where Q2 is the ith column of Q. We approximate the angle between A, and A, by the angle between S2 and 22 By DCBM model, for node i in community k, S2 0, OT Peg. where es is the kth standard basis of K It follows that for i E C2 and j E Ct, the degree parameters 0g and 0g cancel out in our structural similarity:
(MOIIPES, H/IIPP)) cos (14, 2,) |16e1elN |0/eeMeell VMRaMMee
MRe
with M == PIT
(3)
It is seen that cos (S2, 22) does not depend on the degree parameters of nodes and is solely determined by community membership. When k = (i.e., i and j are in the same community). cos (92 12,) = 1, which means the angle between these two vectors is zero. When k & f, as long as P non non--onnnuuuu singular and II has a full column rank, M is a positive- desiiive-effiite matrix. It follows that cos (S2, 12)) < and that the angle between Ω2 and Q2 is nonzero.
Example 1. Suppose K = P Tx222 is such that the diagonal entries are I and off-diagonal entries are b, for some > O and b + 1, and max; {0.) < min (1 /b. 1} (to guarantee that all entries Q are smaller than 1). For simplicity, we assume Liec, 03 = =iic,, 07. It can be shown that M is proportional to the matrix whose diagonal entries are (1 + IP) and off-diagonal entries are 2b. When b- < 1, the communities are assortative, and when b > 1, the communities are non aon-assortative. However, regardless of the value of b, the off- aff-diagonal entries of M are always strictly smaller than the diagonal entries, so that cos (),, 22y) for nodes in distinct communities.
2.2 Semi-supervised community detection Inspired by (3) propose assigning a community
label to the new node based on its 'similarity' to those labeled nodes. For each < k S K, assume that L Cr + 0 and define vector (1)) E R. by Alt = Aij. for 1 S j S n. The vector A (A) describes the 'aggregated behavior' of all labeled nodes community k. Recall that X E IR" contains the edges between the new node and all the existing nodes. We can estimate the community label of the new node by
arg min (A(k), X).
I<kCK
3

---

Published as a conference paper at ICLR 2023
We call 4 the AngleMin estimate. Note that each (4)) is n-dimensional vector, the construction of which uses both Ace and Acu- Therefore, A aggregates information from both labeled and unlabeled nodes, and so AngleMin is indeed a supe-vupee approach.
The estimate in (4) still has space to improve. First, (1)) and X are high-dimensional random vectors, each entry of which is a sum of independent Bernoulli variables. When the network is very sparse or communities are heavily imbalanced in size or degree, the large-deviation bound for ab (AA(),, X) can be unsatisfactory. Second, recall that our observed data include A and X. Denote by Acc the submatrix of A restricted on L x L and X5 the subvector of X restricted on L; other notations are similar. In (4) only (Ace, Acu, X) are used, but the information in Aua is wasted. We now propose a variant of (4). For any vector I E IR", let IC and zy be the sub-vectors restricted to indices in L and U, respectively. Let (4)) denote the [cl-dimension vector indicating whether each labeled node is in community k. Given any [24] x K matrix H- = [bi, h2, lxc, define
fx:: = [2'c .... 2'cl(x). syyn ................................ =hukl' E RR2K
(5)
The mapping f(:; (f) creates low-dimensional projection x. Suppose we now apply this mapping to A In the projected vector, each entry is a weighted sum of a large number of entries of A Since (kk) contains independent entries, follows from large-deviation inequalities that each entry of f (A(k), H)) has a nice asymptotic tail behavior. This resolves the first issue above. We then modify
the AngleMin estimate in (4) to the following estimate, which we call 3
(HH) arg min & (f(A() H), f(x;
(6)
AngleMin+ requires imput of H. Our theory suggests that H has to satisfy two conditions: (a) The spectral norm of H' H is ((24)). In fact, given any H, we can always multiply it by a scalar so that |[ H|l is at the order of [2[]. Hence, this condition says that the scaling of H should be properly set to balance the contributions from labeled and unlabeled nodes. (b) The minimum singular value of H'Quully ITy has to be at least constant times Qual where Oua is the submatrix of θ restricted to the (4 block and Bly is the sub-matrix of II restricted to the rows in U. This condition prevents the columns of H from being orthogonal the columns of Orn/lly and guarantees that the last K entries of fx: H) retain enough information of the unlabeled nodes.
We construct a data-driven H from Aut,. by taking advantage of the existing unsupervised community detection algorithms such as Gao al. (2018); Jin et al. (2021). Let ily kew be the community labels obtained by applying a community detection algorithm on the sub-network restricted to
unlabeled nodes, where मं = ex if and only if node k is clustered to community We propose using
H Nlu-
(7)
This choice of И always satisfies the aforementioned condition (a). Furthermore, under mild regularity conditions, as long as the clustering error fraction is bounded by constant, this H also satisfies the aforementioned condition (b). We note that the information in Auxi has been absorbed into H, so it resolves the second issue above. Combining ( with 33) gives two-stage algorithm for estimating y.
Remark 1: A nice property of AngleMin+ is that it tolerates an arbitrary permutation of communities in Tly In other words, the communities output by the unsupervised community detection algorithm do not need to have a one-to-one correspondence with the communities on the labeled nodes. To see the reason, we consider an arbitrary permutation of columns of fly. By (12). this yields a permutation of the last K entries of (a; H), simultaneously for all x. However, the angle between ʃ( (()()) H) and f(X; H)) is still the same, and so i H) is unchanged. This property brings lot of practical conveniences. When K is large or the signals are weak, it is challenging (both computationally and statistically) to mathh the communities in Il with those in IIc. Our method avoids this issue.
Remark 2: AngleMin+ is flexible to accommodate other choices of H. Some unsupervised commu- nity detection algorithms provide both Ny and θuu (Jin al. 2022). We may use H x trastiu
In AngleMin+, H serves to reduce noise. For example, let X,Y E R 2m be two random Bernoulli vectors, where E. = EY = (.I,... .I, 4, ................................ 4)). As m + co, it can be shown that (X Y) + 0.34 f 1 almost surely. If we project X and Y into R2 by summing the first coordinates and last m coordinates separately, then + oc, 2 X Y) + 1 almost surely.
4

---

Published as a conference paper at ICLR 2023
(subject to re-scaling satisfy the aforementioned condition (a)). This H down down-weights the contribution of low-degree unlabeled nodes in the last K entries of 12 This is beneficial the signals are weak and the degree heterogeneity is severe. Another choice is x Exu) (11) where
Au is diagonal matrix containing the K largest eigenvalues (in magnitude) of Asu and Exe, is the associated matrix of eigenvectors. For this Hl, we do not even need to perform any community detection algorithm on Azu We may also use spectral embedding (Rubin-Delanchy et al. 2017).
The local refinement algorithm (Gao et al. 2018) may be adapted to the semi-supervised setting, but it requires prior knowledge on assortativity or dis-assortativity and strong balance condition on the average degrees of communities. When these conditions are not satisfied, we can construct examples where the error rate of AngleMin+ is o(1) but the error rate of local refinement is 0.5. See Section C
Remark 3:
2.3 The choice of the unsupervised community detection algorithm We discuss how to obtain Tz. In the statistical literature, there are several approaches to unsupervised community detection. The first modularity maximization (Girvan & Newman 2002). It exhaustively searches for all cluster assignments and selects the one that maximizes an empirical modularity function. The second is spectral clustering (Jin 2013). applies k-means clustering to rows of the matrix consisting of empirical eigenvectors. Other methods include post-processing the output of spectral clustering by majority vote (Gao et al. 2018). Not every method deals with degree heterogeneity and non- assortative communities as in the DCBM model. We use recent spectral algorithm SCORE+ (Jin) et al. 2021 which allows for both severe degree heterogeneity and non-assortative communities.
SCORE+: We tentatively write Aua=AA and [ and assume the network (on unlabeled nodes) is connected (otherwise consider its giant component). SCORE+ first computes I==D; 1/2 AD, 1/2 ...... du magnitude) of I, and let & be the associated eigenvector. Let r=K or r=K+1 (see Jin et al. (2021) )
where D,=diag(d1- (ciiiaggd1......
Ln. and d; is degree of node i. Let dS be the Atth eigenvalue (in
for details). Let R E (r-)( by Rutk- (7641/11) (Ex+1 Run k-means on rows of R.
3 THEORETICAL PROPERTIES
We assume that the observed adjacency matrix A follows the DCBM model in [-2 From now on, let 0, denote the degree parameter of the new node n + 1. Suppose k E (I,2, K} is its true community label, and the corresponding K K-dimensional membership vector is x = Cg. In 2 and P are not identifiable. To have identifiability, we assume that all diagonal entries of are equal to 1 (if this is not true, we replace P by [diag(P)] P[diag(P)] and each 0g in community k by P.e/ while keeping 52 OIIPII unchanged). In the asymptotic framework, we fix K and assume n - oc. We need some regularity conditions. For any symmetric matrix B, let [| ||max denote its entry-wise maximum norm and Amin (B) denote its minimum eigenvalue (in magnitude). We assume for a constant C₁ > 0 and positive sequence 3n (which may tend to 0),
(8) For < k < K, let (00) E R" be the vector with 0(4) 0, Hiū E CR and let (0) and 0(0) be the sub-vectors restricted to indices in and U, respectively. We assume for a constant C2 > 0 and a properly small constant c3 0,
|| < C1,
Dmmin (P) 2 Bn.
max |1000]| S C2 min [|0 ||,, k
110 S c33,110 (1 |1 for all 1 k S K.
(9)
These conditions are mild. Consider (8.. For identifiability, P is already scaled to make PAA 1 for all k. It is thus a mild condition to assume P| < C. The condition of [Amin (P) 2 3, is also mild, because we allow 8n - Here, fn captures the 'dissimilarity' of communities. To see this, consider special P where the diagonals are 1 and the oif--iagonals are all equal to b; in this example, [1 b| captures the difference of within-community connectivity and netween-communti connectivity, and it can be shown that |Amin (P)l = |1 6). Consider 9 The first condition requires that the total degree in different communities are balanced, which is mild. The second condition is about degree heterogeneity. Let max and Ø be the maximum and average of 6,, respectively. In the second inequality of (9). the left hand side is (n -1 0mmx/00), so this condition is satisfied as long as 0max/ 1 O..3.). This is very mild requirement.
5

---

Published as a conference paper at ICLR 2023
3.1 The misclassification error of AngleMin+ For any [4] x K matrix H, let (H) (f((()) H), f(X; be as in (3). AngleMin+ estimates the community label to the new node by finding the minimum of 1h1 (H), (H)..... ..... vxx(H) with H fl. We first introduce coun- terpart of (H). Recall that Q as in ( which is the 'signal" matrix. Let 12() E R by
2 = Eieene, Pij. for 1 j S and define
S/ H)) = v (f((()) H), ((EX;H))
for Ikkk K.
(10)
The next lemma gives the explicit expression of t/a ()) for an arbitrary H.
Lemma 1. Consider the DCBM model where (8) 2 are salisfied. We define three K x K matrices:
Gec = cr'',, Guu = II Fralky, and Q = Guidlhy G OuuH. For I k S K, (b( =
Max arccos /Maxy
where M = P( + GuaQQ' P.
The choice of H is flexible. For convenience, we focus on the class of H that is an eligible community membership matrix, i.e., H- Eiu Our theory can be easily extended to more general forms of H. Definition 1. For any by E (0, 1), we say that il is by bo-correct if miny (Ereu 0, 1[T + n. S bo [0][,, where the minimum is taken over all permutations of K columns of Tuu.
The next two theorems study the (H) and the respectively, for = -iu-- Theorem 1. Consider the DCBM model where (8-1 hold. Let k- denote the true community label of the new node, Suppose Ilu is bo-correct, for a constant bo E (0, 1). When by is properly small, there exists a constant co >> O, which does not depend on bo, such that the- (Tzz) 0 and mink t (1le)} 2 cuBn. Theorem 2. Consider the DCBM model where (8-1 hold. There exists constant C > 0, such that for any d E (0, 1/2), with probability 5, simultaneously for 1 S S K, ( 3h (Hlw) s
1/8(1/8)
| 112
11011-min 110 111)
110
10111
Write &he = Sy. (flz) and t/h - tha (flx) for short. When maxx<lva - xx1) < (1/2) ming (vhn
the community label of the new node is correctly estimated. We can immediately translate the results in Theorems 1 to an upper bound for the misclassification probability.
Corollary 1. Consider the DCBM model where 84-1 hold. Suppose for some constants by (0, 1) and e E (0, 1/2). Ll is borrert with probability 1 e. When by is properly small, there exist constants Co > 0 and C > O, which do not depend on (bo, such that P(ğ # k*) S E
CΣK exp - 11001 min(0" [10( l1)))
Remark 4: When ming [10(0) 2 O the stochastic noise in X will dominate the error, and the misspecificatioon probability in Corollary I will not improve with more label information. Typically, the error rate will be the same as in the ideal case that 11 is known (except there is no in the ideal case). Hence, only little label information can make AngleMin+ perform almost as well as fully supervised algorithm that possesses all the label information. We will formalize this in Section 3
Remark 5: Notice that miny (Ereu 0: 1(T + m.)) S I 0, 1(T + m S K-1 || Therefore, if |0cll 2 ドー is always true. In other words, long the information the labels is strong enough, AngleMin+ would not require any assumption on the unsupervised community detection algorithm.
kb> ||8li, then mint(Erru 11T # n,)) bol1011
For AngleMin+ to be consistent, we need the bound in Corollary to be o(1). It then requires that for small constant by. fl is bo-correct with probability 1 o11). This is mild requirement and can be achieved by several unsupervised community detection algorithms. The next corollary studies the specific version of AngleMin+, when Nl is from SCORE+:
Corollary 2. Consider the DCBM model where (8- hold. We apply SCORE+ to obtain ih and plug it into AngleMin+. As n + oc, suppose for some constant qo > 0, minigu 0, 2 4o max,eu Oz. Ba |1 2 go 80 Ilg(()), 02 6 + 20. and B², || 0|] ming {| [1] + cc. Then, P0O # k*) - 0,
so the AngleMin+ estimate is consistent.

---

Published as a conference paper at ICLR 2023
3.2 Comparison with an information theoretical lower bound We compare the performance of AngleMin+ with an ideal estimate that has access to all model parameters, except for the community label k of the new node. For simplicity, first consider the case of K = 2. For any label predictor
y for the new node, define Risk(ū) = >'-eele E|K] Plù # k f=1 = = 6
Lemma 2. Consider DCBM with K = 2 and P = (1 -b) + b121/2 Suppose 0* = =(11,
o" ming 2 o(1), - b o11,,
102 1l: 10 II1 1. There exists constant C4 > 0 such that
1 Il 10/211 Il
0 (110ll + [10ulli) where the infimum is taken over all measurable functions of A, X, and parameters cTc N1, θ, P, 0" In AngleMin+, suppose
infy i [Risk(])) 2 C4 exp -2[1 + o(1] (-
the second part of condition 9 holds with c3 = o(1), illy is bo-correct with bo 33 0. There is a
constant C2 > 0 such that, Risk(ý) S C. exp exp(-1 [-1 - o(1) (ل-ي) O" [1 100 12) 0c 1 S
Lemma 2 indicates that the classification error of Angle is almost the same as the information theoretical lower bound of an algorithm that knows all the parameters except 'T" apart from a mild difference of the exponents. This difference comes from two sources. The first is the extra "2" in the exponent of Risk(ū), which is largely an artifact of proof techniques, because we bound the total variation distance by the Hellinger distance (the total variation distance is hard to analyze directly).
The second is the difference of ||0=|1a + ||0z) 1 in inf (Risk(ū)) and <1dec 110u in Risk(ÿ). 1|0x117+00u]?
Note that [10e11++0u1133 S 110=11 + 110ulla S 1.125 (110=111+ + 10 ||0c 1 ||
so this difference is quite mild. It arises from the fact that AngleMin+ does not aggregate the information in labeled and unlabeled data by adding the first and last K coordinates of fx; H) together. The reason we do not do this is that unsupervised community detection methods only provide class labels up to permutation, and practically it is really hard to estimate this permutation, which will result in the algorithm being extremely unstable. To conclude, the difference of the eπror rate of method and the information theoretical lower bound is mild, demonstrating that our algorithm is nearly optimal. For a general K, have similar conclusion:
||_c]]
| -
Theorem 3. Suppose the conditions of Corollary hoold where bo is properly small, and suppose that Ne is by-correct. Furthermore, we assume for sufficiently large constant Cz. l I c 0" s
(0 minke[k] (3 C [12. and for a constant To > 0, ming PLt} 2 To- Then, there is a constant 22 = C1, C2, C3, C3, vo) > 0 such that [-
g (f (Risk(T))) 2 o2.
3.3 In-sample Classification In this part, we briefly discuss the in-sample classification problem. Formally, our goal is to estimate x, for all i E U. As mentioned in section I an in-sample classification algorithm can be directly derived from AngleMin+: for each i U. predict the label (f(A H²), (,, H.)). where (8) is the subvector of ((k) by removing the vth entry, A_ix is the subvector of A; by removing the ith entry, and H, is (21) 1 1) x K projection matrix which may be different across distinct i. As discussed in subsection 2] the choices of H, are quite flexible. For purely theoretical convenience, we would focus on the
of as Uz (H) = arg mini SASK 16
case that H, = (6). For any in- in-sael classifier ğ = (ūt)aeu E [K]11), define the in sampee risk Riskme (i) = [ि EiEu Exe(KK) (T * kT|T,,
T = cx- ). For the above in in-sap classification algorithm, we have similar theoretical results as in section on consistency and efficiency under some very mild conditions:
Theorem 4. Consider the DCBM model where 81-19 hold. We apply SCORE+ to obtain [ and plug it into the above algorithm. As n + 20, suppose for some constant qu > 0, mingeu 6, 2 go maxieu Oz, Bn 100lll 2 go (n), 3 [00| minseu 0; + 30, and 3% |10] ming I {
[11] (
(k)
oo. Then, [. Eieu P( + k.) 0, so the above in-sample classification algorithm is consistent.
Theorem 5. Suppose the conditions of Corollary hoold where by is properly small, and suppose that Ueriz1)) is bo-correct for all i E U. Furthermore, we assume for sufficiently large constant Ca. maxieu 0, S C maxieu 02 S minkE]K] Ca| (a log((Z()) < C2 minjeu On and for constant Fo > 0, minuye [Px)] 2 ro- Then, there is a constant ट21 = E2 (K, Ci, C2, Ca, Cz, ro) > O such that [- log(Ez Risk,ns ine (t)))/( log(inl, (Risk (ū) 2 T21 so the above in in-sumple classifi- cation algorithm is efficient.
7

---

Published as a conference paper at ICLR 2023
Method
AngleMin+ (subnetwork)
AngleMin
AngleMin+
SNMF
Unsupervised (SCORE+)
0.25
Cles ett
0.30-
Confertmeen
Obortaton
0.15
0..0
0.30
2.09
0.00
N_L
200
+000
1.00
N
N_L
(a) [n))
Gamma, bal.
(b)
(x)
Gamma, imbal.
(c) 71
0.25
Gamma, hal.
(d) 0.25 Gamma, imbal.
2.5
Clas fodion ener
0.2
Clss
0.3
100
2100
4000
1.00
N_1
402
200
200
(c)
(ng(n))
Pareto, bal.
(f)
log(n) Pareto, imbal.
(g) 71
Pareto, bal.
T6
0.20 Pareto, imbal.
Figure 1: Simulations (n 500, K = 3; data are generated from DCBM). In each plot, the x-axis is the number of labeled nodes, and the y-axis the average misclassification rate over 100 repetitions.
EMPIRICAL STUDY
We study the performance of AngelMin+, where Nue is from SCORE+ Jin et al. 2021 We compare our methods with SNMF (Yang et al. (2015) (a representative of semi-supervised approaches) and SCORE+ fully unsupervised approach). We also compare our algorithm to typical GNN methods (Kipf & Welling 2016) in the real data part.
Simulations: To illustrate how information in Aue will improve the classification accuracy, we would consider AngleMin in (4) in simulations. Also, to cast light on how information on unlabeled data will ameliorate the classification accuracy, we consider a special version of AngleMin+ in simulations by feeding into the algorithm only Acc and Xe. It ignores information on unlabeled data and only uses the subnetwork consisting of labeled nodes. We call it (aggleeinn(ubbeewworr)) This method is practically uninteresting, but serves as representative of the fully supervised approach that ignores unlabeled nodes. We simulate data from the DCBM with (n, K) = (500, 3).
To generate P. draw its (off diagonal) entries from Uniform(O, 1), and then symmetrize it. We generate the degree heterogeneity parameters 0, i..dd. from one of the 4 following distributions: n -0.25 (Gamma(3.5) n 0.5 /log(())Paret((33 Pareto(3.5) n -0.2 Pareto(3 (3.5). They cover most scenarios: Gamma distributions have considerable mass near O, the network has severely low degree nodes; Pareto distributions have heavy tails, so the network has severely high degree nodes. The scaling n - 10000./ooo(/ (lg((n) corresponds to the sparse regime, where the average node degree is x Iog(n)2 and n 00.25 corresponds to the dense regime, with average node degree Vn. We consider two cases of 11: the balanced case (bal.) and the imbalanced case (inbal.). In the former, (i) are i.i.d. from Multinomial(1 Multinomial 0.2, 0.6). We repeat the simulation 100 times. Our results are presented in Figure I which shows the average classification error of each algorithm as the number of labeled nodes, Ny increases. The plots indicate that AngleMin+ outperforms other methods all the cases. Furthermore, though AngleMin is not so good as AngleMin+ when N,, is small, it still surpasses all the other approaches except AngleMin+ in most scenarios. Compared to supervised and unsupervised methods that AngleMin+ gains great amount of accuracy by
n n0055 Vlog(n) ()amn)))a3ma333
1/3, 1/3), and in the latter, xii) are i.i.d. from
which only use part of the data, we leveraging on both the labeled and unlabeled data.
Real data: We consider three benchmark datasets for community detection, Caltech (Traud et al.) 2012) Simmons (Traud et al. 2012) and Polblogs (Adamic & Glance 2005). For each data set, separate nodes into 10 folds and treat each fold as the test data at time, with the other 9 folds as training data. In the training network, we randomly choose n,, nodes as labeled nodes. We then estimate the label of each node in the test data and report the misclassification error rate (averaged
8

---

Published as a conference paper at ICLR 2023
over 10 folds). We consider ng/n E {0.3, 0.5, 0.7), where is the number of nodes in training data. The results are shown in Table []] In most cases, AngleMin+ significantly outperforms the other methods (unsupervised or semi-supervised). Additionally, standard deviation of the error of SCORE+ is quite large, indicating that its performance is unstable. Remarkably, even though AngleMin+ uses SCORE+ initialize, the performance of AngleMin+ is nearly unaffected: It still achieves low means and standard deviations in misclassification error. This consistent with our theory in Section 3 We also compare the running time of different methods (please see Section B of the appendix) and find that AngleMin+ is much faster than SNMF.
notice that in the Polblogs data, the
Table I: Average misclassification error over 10 data splits, with standard deviation in the parentheses.
Datract
Ag///
SCORE+
AugleMin+
SNMF
GNN (eats))
GNN (ransken)
GNNN (xlj))
GINN (L.P)
CIN (oook2voo))
GINN (AII))
Caltehh
0.237
0.207 (0.059)
0.351 (0.040)
0.310 (0.02)
0.312
(0054)
(0033)
0:559 (0:085)
0,595 (0:025)
0.875 (0003))
0.839 (0.04l0)
0.561 (0:043)
0,859 (0.055)
0,859 yo
0,550 (Q.126)
0,856 (0.94)
0.7
0.137 (0,006)
0.264 (0.05))
0.561 (0:004)
0,889 (00011
0,880
(0.277)
0.5
0.128 (0/024)
0.266 (0,04))
0.691 (0.022)
0.502 (0:0099
(0/036)
0,655
0,706 (0.029)
0.696 (QU02))
Simmons
1137
0.5
(0.064)
0.8% (0.024)
0.253 (0,03))
0.691
0:711 (0.064)
(01125)
0.081 (0.022)
0,710 (0.18)
0.691 (0.022)
0.7
0,892 (0.015)
0:220
(0.022
0,0M2 (0:022)
0.691 (0M122
0,091 (0.022)
0,007 (0.043)
0,698
Polblogs
1222
2
0.3
0.7
0.5
(0.165)
0.165
0.074 (0.035)
0,066 (0.025)
01092 (0.04))
0 (0,033)
0,073 (0.019)
0.863 (0.025)
0.899 (00044)
0.983 (0.041)
0.517 (00540)
0.492 (0,0433
0.515 (0.005)
0.502 (0.085)
0. 455 (0.156)
0. 430 (QL0522
0,439 (0.048)
0,482 (0.007)
0,488 (0.044)
0,493 (0,041)
0,502 (0.089)
0,492 (0.080)
0.499 (0.0611
9,501 (Q.044)
0.484 (0.041)
0.486 (0.019)
GNN a popular approach for attributed node clustering, Although it is not designed for the case of no node attributes, we are still interested in whether GNN can be easily adapted to our setting by self-created features. We take the GCN method in Kipl' & Welling 2016) and consider schemes of creating a feature vector for each node: i) 30-dimensional constant vector of 1 I's, ii) 50-dimensional randomly generated feature vector, iii) the n-dimensional adjacency vector, iv) the vector of landing probabilities (LP) (Li et al. (019) (which contains network topology information), v) the embedding vector from node2vec (Grover& Leskovec 2016), and vi) a practically infeasible vector eç ATT E R (which uses the true Il). The results are in Table I GCN performs unsatisfactorily, regardless of how the features are created. For example, propagating messages with all-1 vectors seems to result in over-smoothing: and using adjacency vectors node features means that the feature transformation linear layers' size changes with the number of nodes in a network, which could heavily overfit due to too many parameters. We conclude that it is not easy to adapt GNN to the case of no node attributes.
For a fairer comparison, we also consider a real network, Citeseer (Sen et al. 2008), that contains node features. We consider two tfte-offthhe-at semi-supervised GNN algorithms, GCN (Kipf & Welling, 2016) and MasG (Jin et al. 2019). Our methods can also be generalized to accommodate node features. Using the "fusion" idea surveyed in Chunaev et al. (2019), we "fuse" the adjacency matrix A (on +1 1 nodes) and node features into weighted adjacency matrix Afuse (see the appendix for details). We denote its top left block by Auue E < and its last column by Xiuse E R and apply AngleMin+ by replacing (A, X) by (Aruee X The misclassification error averaged over 10 data splits is reported in Table 2 The error rates GCN and MasG are quoted from those papers, which are based on 1 particular data split. We also re-run GCN on our 10 data splits.
Table 2: Error rates on Citeseer, where node attributes are available. If the error rate has * is quoted from literature and based on one particular data split; otherwise, it is averaged over 10 data splits.
Dataset n
K
Rg/0
GCN
GCN'
MusGG
AngleMine
Citesser 3312
0.036
0.321
0.297
0.268
0.334
Conclusion and discussions: In this paper, we propose a fast semi-supervised community detection algorithm AngleMin+ based on the structural similarity metric of DCBM. Our method is able to address degree heterogeneity and non-assortative network, is computationally fast, and possesses favorable theoretical properties on consistency and efficiency. Also, our algorithm performs well on both simulations and real data, indicating its strong usage in practice.
There are possible extensions for our method, Our method does not directly deal with soft label (a.k.a mixed membership) where the available label information is the probability of a certain node being in each community. We are currently endeavoring to solve this by fitting our algorithm into the degree-corrected mixed membership model (DCMM), and developing sharp theories for it.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work is partially supported by the NSF CAREER grant DMS- 1943902.
ETHICS STATEMENT
This paper proposes novel semi-supervised community detection algorithm, AngleMin+, based on the structural similarity metric of DCBM. Our method may be maliciously manipulated to identify certain group of people such as dissenters. This is a common drawback of all the community detection algorithms, and we think that this can be solved by replacing the network data by their differential private counterpart. All the real data and we do not think that they will raise any privacy issues or other potential problems.
come from public datasets which we have clearly cited,
REPRODUCIBILITY STATEMENT
We provide detailed theory on our algorithm AngleMin+. we derive explicit bounds for the misclassi- fication probability of our method under DCBM, and show that is consistent. We also study the efficiency of our method by comparing its misclassification probability with that of an ideal classifier having access to the community labels of all nodes. Additionally, we provide clear explanations and insights of our theory. All the proofs, together with some generalization of our theory, are available in the appendix. Also, we perform empirical study on our proposed algorithms under both simulations and real data settings, and consider a large number of scenarios in both cases. All the codes are available in the supplementary materials.
REFERENCES
Lada A Adamic and Natalic Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pp. 36 43, 2005.
Richard F Betzel, Maxwell A Bertolero, and Danielle S Bassett. Non-assortative community structure in resting and task-evoked functional brain networks. bioRxiv, pp. 355016, 2018.
Peter Bickel and Aiyou Chen. nonparametric view of network models and newman-girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068-2107, 2009.
Petr Chunaev, Ivan Nuzhdenko, and Klavdiya Bochenina. Community detection in attributed social networks: unified weight-based based model and its regimes. In 2019 International Conference on Data Mining Workshops (ICDMW), pp. 455-464. IEEE, 2019.
Souvik Debnath, Niloy Ganguly, and Pabitra Mitra. Feature weighting content based recommenda- tion system using social network analysis. In Proceedings of the 17th international conference on World Wide Web, pp. 1041-1042, 2008
Chao Gao, Zongming Ma, Anderson Y Zhang, and Harrison H Zhou. Community detection in degree-corrected block models. The Annals of Statistics, 46(5):2153-2185, 2018.
Michelle Girvan and Mark EJ Newman. Community structure social and biological networks. Proceedings of the national academy of sciences, 99(12):7821-7828 2002.
Anna Goldenberg, Alice Zheng, Stephen Fienberg, Edoardo M Airoldi, et al. survey of statistical network models. Foundations and Trends9 in Machine Learning, (12):129-2333 2010.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Karl E Gustafson and Duggirala KM Rao. Numerical range. Numerical range, pp. 1-26. Springer, 1997.
10

---

Published as a conference paper at ICLR 2023
Min Ji, Dawei Zhang, Fuding Xie, Ying Zhang, Yong Zhang, and Jun Yang. Semisupervised community detection by voltage drops. Mathematical Problems in Engineering. 2016, 2016.
Pengsheng Ji, Jiashun Jin, Zheng Tracy Ke, and Wanshan Li. Co-citation and co-authorship networks of statisticians. Journal of Business Economic Statisties, 40(2):469 485, 2022.
Di Jin, Ziyang Liu, Weihao Li, Dongxiao He, and Weixiong Zhang. Graph convolutional networks meet markov random fields: Semi-supervised community detection in attribute networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 152-159, 2019.
Jiashun Jin. Fast community detection by score. The Anmals of Statistics, 43(1):57-89, 2015.
Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Improvements SCORE, especially for weak signals. Sankhya A, 14(1):127-162, mar 2021. doi: 10. 10.11077//3377-020000000011 URL
fttps://doi.orr wttp://...1111221.11.
22240022--1
Jiashun Jin, Zheng Tracy Ke, Shengming Luo,, and Minzhe Wang. Optimal estimation of the number of network communities. Journal of the American Statistical Association, pp. 1-16, 2022.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):01617,, 2011.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprini arXiv: 160.:060900000 0099000997,... 2016.
Mingwei Leng and Tao Ma. Semi-supervised community detection: A survey. Proceedings of the 2019 7th International Conference Information Technology: loT and Smart City, pp. 137-140, 2019.
Pan Li, I Chien, and and Olgica Milenkovic. Optimizing generalized pagerank methods for exppassonno community detection. Advances in Neural Information Processing Systems, 32, 2019.
Xiaodong Li, Yudong Chen, and Jiaming Xu. Convex relaxation methods for community detection. Statistical Science, 36(1):2-15, 2021.
Dong Liu, Xiao Liu, Wenjun Wang, and Hongyu Bai. Semi-supervised community detection based on discrete potential theory. Physica A: Statistical Mechanics and its Applications, 416:173-182, 2014.
Fuchen Liu, David Choi, Lu Xie, and Kathryn Roeder. Global spectral clustering in dynamic networks. Proceedings of the National Academy of Sciences, 1 115559927-933,, 2018.
Veronica Red, Eric D Kelsic, Peter Mucha, and Mason A Porter. Comparing community structure to characteristics in online collegiate social networks. SIAM review, 53(3):526-543, 2011.
Karl Rohe, Souray Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4):1878-1155 2011.
Patrick Kubin-Delanche Joshua Cape, Minh Tang. and Carey E Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. arXiv preprint arXiv: 1709.0570, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93 93, 2008
Bracha Shapira, Lior Rokach, and Shirley Freilikhman. Facebook single and cross domain data for recommendation systems. User Modeling and User-Adapted Interaction, 23(2):211-2477 2013.
Amanda L Traud, Peter J Mucha, and Mason Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 991(16):165-4168 2012.
Alexandre B Tsybakov. Introduction Nonparametric Estimation. Springer Series in Statistics. Springer New York Imprint: Springer, New York, NY, 1st ed. 2009. edition, 2009. ISBN 1-283-07270-X.
11

---

Published as a conference paper at ICLR 2023
J. V Uspensky. Introduction mathematical probability. McGraw-Hill, New York, 1937.
Liang Yang, Xiaochun Cao, Di Jin, Xiao Wang, and Dan Meng. A unified sumi-supervised community detection framework using latent space graph regularization. IEEE Transactions on Cybernetics, 45(11))2585-2598 2015. doi: 10.1109/TCYB.221422277
Kuang Zhou, Arnaud Martin, Quan Pan, and Zhunga Liu. Selp: Semi-supervised evidential label propagation algorithm for graph data clustering. International Journal of Approximate Reasoning. 92:139-154, 2018.
12

---

Published as a conference paper at ICLR 2023
APPENDIX
Pseudo code of the algorithm
13
Running Time
13
Comparison with Local Refinement Algorithm
13
D Generalization of Lemma 2
15
Preliminaries
15
Proof of Lemmall
17
G Proof of Theorem
19
G. Proof of Lemma
H Proof of Theorem 2
25
Proof of Lemma
28
H.2 Proof of Lemma
33
Proof of Corollary|1] 1
36
L. Proof of Corollary
36
Proof of Corollary
38
J Proof of Lemma
38
J.1 Proof of Lower Bound (55
39
J.2 Proof of Upper Bound 776'
K Proof of Theorem 3
48
Proof of Aiheorem445
52
Proof of Theorem
52
Proof of Theorem
53
13

---

Published as a conference paper at ICLR 2023
A
PSEUDO CODE OF THE ALGORITHM
Below are the pseudo code of AngleMin+ which is deferred the appendix due to the page limit.
Algorithm 1: AngleMin+
Input: Number of communities K, adjacency matrix A Rux=, community labels y; for nodes in L, and the vector of edges between a new node and the existing nodes X E F Output: Estimated community label ğ of the new node.
Unsupervised community detection: Apply a community detection algorithm (e.g.. SCORE+ in Section 2 on Auu. and let IL, = [Ry]ee store the estimated community labels, where म. Ex if and only if node &o is clustered to community k. S k K.
2. Assigning the community label to a new node: Let C [Ta]eE contain the community memberships of labeled nodes, where n, e and only if y: = k. 1 S k < K. Let
il. Compute
[Xellc, Xy1l]', us [<ll'cAcclle. A 1 Isksk K.
Suppose k- minimizes the angle between Uy and æ, among 1 s k S K (if there is a tie, pick the smaller k). Output 9 k..
B RUNNING TIME
Table exhhibis the running time of the algorithms considered in Table It can be seen from the result that our algorithm AngleMin+ is much faster than all the other algorithms. This is one of the merits of our method.
Table 3: Running time on Caltech, Simons, and Polblogs networks. The quantities outside and inside the parentheses are the means and standard deviations of the running time, respectively.
Duraett
sp/n
AsgleMior
GNN (c0n5))
(randor)
(ad))
(LP)
(wnde2ee4)
Caltech
590
0..
8.5
(0.00%)
0.083
0.034 (0.033)
BJ86 (1-95)
0J122 (1/00))
0.211 (0.069)
0.175 (0.01))
0.311 (0.054)
0.575 (0.133)
11277 (A 154)
01861 (0L099)
0.369 (0.049)
0,535 (0.061)
0.897 (0.116)
0.620 (0.135)
0.511 1000
1855 (0.2115
0.71W (0:064)
0,509 (3.067)
0.049 (0.049)
0.536 (0.090)
(1:55 (U001)
1.704 (0 1865
0.64P (0D45)
1190% (8 (8.055)
0.995 (BUNT)
0,075
0.515 (0.03))
0.334 (0.066)
(0.094)
(0.690)
0.541
0.985
Pulllogs
1222
2
113
(00044)
00833
03332 (0004)
8854 (1100)
0331 (0.04)
0.411 (0.088)
0.356 (0:034)
0.351 (0.057)
1:402 (0 127)
0.780 (0) 147)
1.135 (1.108
0,353 (0.0953
0.700 (0.1811
1,152 (0.314)
0.444 (0.154h
0.955 (0.179)
1,430 00.1099
0,311 (9:055)
0.540 (0.054)
0.986 140
0.510 (0
1.081 (0. 1900
1.488 (0.2100
U.343 (LL131)
0.644 (0 (0.044)
11990 (8.100)
C COMPARISON WITH LOCAL REFINEMENT ALGORITHM
We would first illustrate why local refinement may not work with an example and then explain our insight behind it.
Consider network with 4m nodes and K = 2 communities. Suppose that there are 2m labeled nodes, m of them are in community C, and have degree heterogeneity 0.8, and the other m of them are in community C2 and have degree heterogeneity 0 0.5. There are 2m unlabeled nodes, m of them are in community C and have degree heterogeneity = 0.6, and the other mn of them are in community C2 and have degree heterogeneity 0 0.7. The P matrix is defined follows:
0.9
P
0.9
Under this setting, all the assumptions in our paper are satisfied.
On the other hand, recall that the prototypical refinement algorithm, Algorithm 2 of Gao et al. (2018) defined as follows:
arg max WE [ {i: (j) w.]
Σ
Aij
[)=
14

---

Published as a conference paper at ICLR 2023
where jº is vector of community label and is the refined community label.
For sumi-superrised setting, one may consider the following modification of local refinement algo- rithm:
(i) Apply local refinement algorithm, with known labels to assign nodes in U.
(ii) With the labels of all nodes, one updates the labels of every node by applying the same refinement procedure.
Under the setting of our toy example, for step (i), all the unlabeled nodes which are actually in community C2 will be assigned to community C1 with probability converging to 1 as > 00. The reason that for any unlabeled node which is actually in community C2. when
(4u j E Uj Vj = u are iid ~ Bern(0,0, P21) Bern(0, 0.8 0.9) Bern(0.720:)) when # = 2, {Aig J E C, yj = u} are iid Bern(0,0,Pa)) = Bern(0; 0.5 1) = Bern(0.50.).
Hence, by law of large numbers.
[0.720, 0.50,
E
Auj o
[A j E C. Uj = =u}
u u=
[Au.tEC.g.uut
Consequently, the prototypical refinement algorithm will incorrectly assign all the unlabeled nodes which are actually in the community C2 to Ci with probability converging to I as co. This will cause a classification eπror of at least 50%.
Based on the huge classification error in step (i), step (ii) will also perform poorly. Similar to the reasoning above, by law of large numbers, can be shown that after step (ii). the algorithm will still assign all the unlabeled nodes which actually in the community C2 to C1 with probability converging to 1 as n - co. In other words, even the local refinement algorithm is applied to the whole network, classification emrrr of at least 50% will always remain.
Even if all the labels of the nodes are known, applying the local refinement algorithm still can cause severe errors. Still consider our toy example. Suppose and we perform the local refinement algorithm on these known labels in an attempt to purify them. By the law of large numbers, however, hard to show that for any node i which is actually in community C2.
that know the label of all the nodes,
Σ AA :j L, [Ag:),=u}
Agj a.g. 50.630,
u 1
0.60 u 2
Consequently, similar the previous cases, the local refinement algorithm will incorrectly assign all the unlabeled nodes which are actually in the community C2 to C₁ with probability converging to I as + co. This will cause classification error of least 50% even though the input of the algorithm is actually the true label vector.
To conclude, general, the local refinement algorithms may not work under the broad settings of our paper. Intrinsically, label refinement is quite challenging when there is moderate degree heterogeneity. not to mention the scenarios where non-assortative networks occur. Local refinement algorithm works theoretically because strong assumptions degree heterogeneity are imposed. For instance, is required that the mean of the degree heterogeneity parameter in each community which means that the network is extremely dense and that the degree heterogeneity parameters across communities are strongly balanced. Both these two assumptions are hardly true in the real world, where most of the networks sparse and imbalanced. Gao et al. (2018) is very good paper, but we think that local refinement algorithm or similar algorithms might not good choices for our problem.
+ o(1),
15

---

Published as a conference paper at ICLR 2023
D GENERALIZATION OF LEMMA 2
In the main paper, for the smoothness and comprchensibility of the text, we do not present the most
general form of Lemma 2
We have more general version of the lemma by relaxing the condition
10 1h
10 lh 1. Please see Section for more details.
10 II
E PRELIMINARIES
For any positive integer N, Define [N] 21.,....
For matrix D and two index sets SI, S2, define Ds, be the submatrix (Di))iEs,.Ess, Ds. to be the submatrix (Dee)s and D.s, to be the submatrix (Du))secue,
The two main assumptions 8), in the main paper are presented below for convenience.
||| max I C1.
Amiin (P)) 2 Bn.
(8)
max (110000111
11
110 12 | |1
I Cz.
max ISRSK
S
cyPn.
(9)
minigagK ( (1(0)))
where constant Cg is properly small. We would specify this precisely in our proofs.
A number of lemmas used in our proofs will be presented as follows.
The following lemma shows that sin æ and x have the same order.
Lemma 3. Let IR. When 2 0, sin x; when x E [0, } sin 2 2.
Lemma is quite obvious, but for the completeness of our work, provide proof for it.
Proof. Let (x)) sin
Then
cos 15 [1
da
Hence @1 (z) is monotonously decreasing on As a result, when x 2 0, (1 2 91( = Therefore, when 2 0, sin S
Let 92(x)= = sin x 2x. Then
d dx
92(x) = COS x
Since cos is monotonously decreasing 00 3) de (x)) 2 0 when E [0, arccos 2 and (1)) < 0 when E [arccos 3, 3. Hence, g2(x) monotonously increasing on [0, arccos 2 and is monotonously decreasing on jarccos 2 # 7] As result, when x E [0, 7].
g2(x) 2 min (0). g2 2 =0
-
Therefore, when [0, H sin L..
The following lemma demonstrates that the angle (u, in Definition satisfies the triangle inequality, so that it can be regarded as sort of "metric". Lemma 4 (Angle Inequality). Let x, y, be three real vectors. Then,
(x,,)) < (b(x. u) (v.2))
16

---

Published as a conference paper at ICLR 2023
The proof of Lemma can be seen in Gustafson & Rao (997). pg 56. Also, for completeness of our work, we provide a proof of Lemma
Proof. Let
TeT
| then cos (a,
(T, 1) cos (yy 2)
(ÿ. 2).
cos (x, 2) = (i, 2). Consider the following matrix
cos ((r,))
cos (1, z) cos (1,,
(i, a)
(7. 1)
(7,
G = cos (xx v) cos 1b x2 COs (1,,)
(j. T
7.
(2, ()
(2.0)
(2
For any vector c = (c1, C2 cz)² ER,
Go (clē + czÿ + cz c₁ 02ÿ + c3ă) 20
Also, G is symmetric. Therefore, is positive semi-definite. As a result, det(G) 2 In other word,
- cos² (xx y) - cos? wb 2) cos² (xx 2) + cos (z v) cos (y 2) cos (x 2) 2 0 The above inequality can be rewritten as
(1 cos² (1x, u)) cos² v)y, 2 (cos (/ y) cos (v, (or,
or
(sin (b y) sin (u =))² 2 (cos (1, y) cos (os, cos (xr,
By definition of arccos, cba y), (vv =) [0, mr, so sin wba y) sin vb(u, 2 0. Therefore,
sin (6., y) sin (yy 2) s cos (2x v) cos (v, 2) cos (2,, s sin (bx v) sin #)y,2)
cos (2, cos (x v) cos (y 2) sin (0x v) sin (y, cos (xx, cos(v)(z,)) v) + (v)
If ([ v) + 2), > x, because by definition of arccos, (xx 2) E [0, w). it is immediate that
(Φx < (/x (v,
(xx 3) vyy,, z) < ग, recall that vxx y), wh z) E [0, T]. hence vx v) + (4y, E [0,z]. Also, (xx,2) 2) [0, x). Since cos is monotone decreasing on [0, T.. obtain
(0 2) < (1x 3) (1,,2) 2)
In all,
(xx=)) S (b(,,)) (vu. z)
The following lemma relates angle to Euclidean distance. Lemma 5. Suppose that x, y E Th ||v|| ||=||| Then.
|| [x]]
(a x y) aresin
The equality holdy if and only (y, 0
17

---

Published as a conference paper at ICLR 2023
||a|| Proof. p ||]|| thu (). Then (x, v) ||>||||||| cos c/o Notice that
p cos vo) 2 0
This can be rewritten as
(1 + pcos 22 (1 p² - 2pcos x²)
Since lylll ||-||| so p < 1, pco8 1/u 0. Hence
+ pcos to
v1 /²
v1 + p² 2pcos v/0
Plugging in p
[y]| |
have
a 2 + | cos di
3
|0:|
+ | 1 + 2|1xr
||
cos who
x
1
Since (z. v) = ||>|||lv| cos v/o.
|x 12 (xr,
|
[2] 2 + |1y/12 + 2(20. V2
|
(x, x + 9)
|1v/1 ||=|| 2
||||||
(x + y. x + 11
In other words,
cos (2x x + 3) 2 |1v|1
|lvil ||>|||
cos arcsin
|
Since
Ivll - 2 0, arcsin
[v] -
E [0, 5..
Therefore, by monotonicity of cos on [0, g..
|
(x + v) aresin
[
The equality holds if and only if (p + cos 2/ 2 0, or equivalently,
(112 + || cos v0) 0
This can reduced to
(v =0
F PROOF OF LEMMA 1
Lemma 1. Consider the DCBM model where 88-
99 are satisfied. We define three K x K matrices: Gec = 1Tl. Giu = Orad and Gr H. For S S
MRK-
where M = p(G2c + GraQQ' Gen
2/x (H) arccos
/MRR /M
18

---

Published as a conference paper at ICLR 2023
Proof. Recall that
(x(H) = 1b (((1)()) ((EX;
for 1 1 K.
(11)
where
[(:; H) ('c ... 10) (1)) f
(12)
and
0 E
Gi c.ll'
ieene,
which indicates
2 = (c
Hence
5(120); H) = )()
1l'ADcelle, H' Oua] Pu
[Gcc, ('aui Pul
(13)
Notice that
110% I1.,
k
(I'OOcllle) = 100 Occ1
k x
In other words,
1T'OcclTC diag (108 |1...... 100200 111
Hence
1(2(#) H) = -1105")1 |1 Q'Guil' Pek
Similarly,
f(EX; H) = (G Gruul
Therefore.
11)
(0 Q' Guull
or 110 Ilece, Gee. Q' Pex-
- llet P G2c Gun PeN-
= = Mex
(11()( Ma.
(14)
Similarly,
( H)ll ()( H)) = (10(4) / Mr
(15)
|S(X; H|| (J(EX; (IX; 0" MM+k
(16)
19

---

Published as a conference paper at ICLR 2023
Hence,
xx - (S(D))) H), S(EX;H)
(F(S2)) H., F(EXHH) (I((S))) H)III HII
arссos
0-110 1 M
arссos
( 11 MuR VM
MRN-
arccos
(17)
MMN / /M
G PROOF OF THEOREM
Theorem Consider the DCBM model where 8 hold. Let k. denote the true community label of the new node, Suppose Nh is bo-correct, for a constant by (0, 1). When by is properly small, there exists a constant co > O, which does not depend on bo, such that the (Ilu) and ming 13 (Ilu)) 2 co
Proof. Define Gee 0 Gru
Oraell. Q Grillhy Orailly and M
p P(GEc + QuaQQ'Guun Gum) P in Lemma
According Lemma
M
wu (fiz) = arccos
MMAVMMe
Hence,
Ma-k.
vu- (ilx) = arccos
arccos
VM VM
When i + k.,"" according Lemma 3
uk (TTz) 2 the (Th))
sin 2/x (Tlee)
v'n (Ilx)
21
MEL MR
cos arccos
MMRR v Ma-k
2(1
(18)
MER MMARVM-E M
Let DM = (iiagMMn...... MKk), M D MD Then
(ex ex. Y'M Cx-)
Man Ma+K. MaK- Mr
MaR +
M
ME
M
"MMR VMRk VMR--
VM MM-K
V M / Mas
=2(1- MM
MR
(19)
20

---

Published as a conference paper at ICLR 2023
Hence,
2 (Itu) 2 v (ex ex. (M - ek-)
(20)
M is affected by Ily and is complicated to evaluate directly. Hence, we would first evaluate its oracle version and then reduce the noisy version to the oracle version.
Define the oracle version of M follow, where IT is replaced by Il
M =P((2e + GiRs) P
Similarly, define the oracle version of DM, M diag(MM1 ..., Mkk). and the oracle version of M, (0) Diio M D M)())
Oracle Case We first study the oracle case la a))
Since Gcc = Oclll = diag [102 (1) l1....,, 110 11)) Gua =
IT Trulle =
diag (1022111.111 Il..... 10 1111 which indicates that Gec + Gias = diag (1105) + /10//) 113 for any vector E R
K k=1
la (1 = la' Ia'D (0) D D axl
Mío)
Mio
|a D Moo
P(G2c + Gia) PD PD al
> PP
alI min( (-) 112 + |10%/ 112)
Min)
k
(Cauchy-Schward) Inequality)
> la D
Min)
PP
M
a
min (110 || + 1004)110 l11)
&
IV
Amin (P)
D
a ( 1112
Mioy
(Condition 8
3 a D-1 ( ||1)
1
aa
min (10 (3) |/ ||0 - ()o((())())] |1
2
|
3
min (110 || + | |1)3]] -1
(min (10(k) 1)
2
minx |10( 2
1
2
max [10(R]]]]
32 |a
(Condition 9
(21)
2C
It remains to study the noisy case. We reduce the noisy case to the oracle case through the following lemma. Lemma 6. Denote
10
C = SK8
(22)
|01
Suppose that Cs $ }. Then, for any vector a E IR.
1- 3C,
Ja'Ma| 2 1- Cs
a M (0) al
2 3
(0)
(23)
The proof of Lemma 6 is quite tedious and we would defer it to the end of this section.
21

---

Published as a conference paper at ICLR 2023
Set bu 32K2VKC3 then Cs for any vector R
10ulla 4
3. As result, combining 21 with Lemma 6 have
a Mal 2
2
1 a a
(24)
6C2
Hence, take ck ee-- in 24 and combine with
20 we obtain that for any & [K]
th (TTrr) V (ex ex M ex-)
V
6C²
1
lex
ex- -ex-112 1a-112=0
- 1/32
1
3n
(25)
Therefore, co V 303' we have
((xx) 2 co.n kekk
min
(26)
In all, when by is properly small such that 6o - /2K there exists constant co = not depending on by such that the (lbx) = and zina (vh (Ue)) 2 co
30
G.1 PROOF OF LEMMA 6
Proof. For any vector R.
la'Ma a' 17(000 = =Ia' MD M a D'D M( D-
Mio al
Mios
= =la'D (M - (0) ) Diit
+ ta'D M M (0) D a' D'D
Mio)
M (0) D D
Mio a
<la'D (M (0 > al
+ la' (Dir 10) DJr D M(
Mio:
Mio1 )al
(27)
The first part on the RHS of (27
la'D (2' (M - (D))
= |a' a''D pul (un - )un
< || a ||' Orn Tea
s VKIIPD, M all | Orar Oran II ) Oral (28)
Denote (id) = Orr ILI1,, Orully Define Th = ,. 0. In other words, Mi is the sum of the degree heterogeneity parameters of all the nodes in li with true label and estimated label i.
(
Then,
Σ
0 1_ Σ
M sE[K]
where 1,- is the indicator function of event (1 = 17.
Hence,
22

---

Published as a conference paper at ICLR 2023
( = Ora - Ow (tallll
(TV
Σ .E[K]
MhTl - 4 Σ ms)
(29)
KE[K]
Since Uu is by correct, there exists permutation T of K columns of Th such that (Ere O. 11T + TH)) bo | 1-
Let rl) satisfies e, T-
When = 7, have
(G(L
2
Mit }1
KE
SE[K]
M m
Σ
Mss
SE [K]
<
$
m 2
<E[R]
Mh (Tr
Σ
mis)
sE[K]
$ 2(
n Σ me)
(30)
sE[K]
When 1 + 7, we have
|G(0|
Σ
Mi
11
KE[K]
= Σ
Mi
(31)
KE[K]
Therefore,
|[((d)
1000 S
Gld)
[
Σ G
+
[E[K]
Σ
2
m
Σ mcm)
+ Σ Σ
Malls
[K[K]
efr
sE|K]
148 sE[K]
max
Σ Tie
ns + Σ
MeTls
sE(K]
(E(K],s{r())
#E[K] lti
2 max
Σ
Its
Σ
MsS
Σ
Mss
Σ
Me.
2
sE[K]
(E]K),
SЕ[K]
[E
TE[k]
2 mamx
Σ Mi
Σ
M
+
Σ
Σ
Msl
2
sE(K]
(E(
#E[K]
[E(
r())=
2
Σ 1sss)
Σ
m
+
Σ
Σ
ms)
Σ
MAi +
Σ
ms)]
sE[K]
(E(
SE[K]
r())fs
[E[K]
<()=x
23

---

Published as a conference paper at ICLR 2023
< 2aax max
Σ me
Σ
Mhs +2 Σ
1(
Σ
Ms)
Σ
met)
sE[K]
(x((),
sE(K]
r(1)
KE(K]
max
Σ
Tits) + max
Σ
Σ
E
sE(K]
(E(
[E[K]
xE[K]
=2(
Σ
mis)
maxx Σ
max
Σ
Vite)
1x((1
sE|K]
[E|K]
2(
Σ ms)
Σ
E
Σ
E
Mi
[E[K]
SE[K]]E[K]
= =4|10ull
Σ
mss)
(32)
(E(K),
Recall that 7 satisfies
CEieu 1(T + nz}) S bo 10l10111. hence
Σ Te
Σ ( =
0== Σ 0: 1[T#; * me} S bu bo110
(E(K),
Therefore,
|| 1100 S 4bb 4b011021l:11011
(33)
Plugging
33 into 28 we obtain
aa' D' (M ( t S 4v 4hhha//aaal110011P177770
(34)
On the other hand,
la lo'D>' 11 Dıtal=
1r(0)
j' | P (C + +in) PDatal
Since Gcc Occlle diag(1) (1100000011111110. ||...., 1104 11)).
diag(1l(()) 11. ll. (io....|[(k]]] 11)) Guu
Orailly
Ia'D M M (0)
D M
al 2 |P M all min (k) ||? + 110(")11 (13)
(Cauchy-Schwartz Inequality)
2 PP M
min all
(10(()
(k) || + 1
& 2
1 コタ
ID
al min | |?
M
Recall condition ( in the main paper,
maxigisk ||0((k) 13
I C2
minigagk (110()))11) [1]
Hence
la' DzT M(0) D > PP M a11²(
1
max [100()
C2 k
PD
(1
KC₂ |011))²
PPD a 1007
(35)
2k
Comparing
35 with
34
we obtain
a D (M ()(0)DTT
24

---

Published as a conference paper at ICLR 2023
<8K2 &Kkb
10ull
aa D M D al
1811
M
$ Ctlla'
Min M
D- al
+ +Cola' M
D M D )al
(36)
M
M
M
Consequently, we bound the first part of (27 by the second part of (27 remains to bound the second part of (27)
Since DM. Da Ml are all diagonal matrices, we can rewrite the second part on the LHS of (27
as follows:
la
(D M (0) DMT - Nioo
- M (0) D Jal
Arios
la'D Mio (1) - i Drd ( NN Ar (1)
-100))+-10000 1) ar al
la' D Mio) (0) (Diro - 1) (MI D D al
(MMOODDT DMr - -1)1((A711))+ D a11
S Amax
ME
-1((((0)) D
max k
Mik
max kE(K]
(D)
1
la D 150 M (0) D Mr: al
(37)
(O)
M)²k
Notice that for any k E [K]
M (0) (M M)RR
leg.0r10ee
(M -M)EN
4 C CPcc + +CRen
Pek
|exl "minx (110 112 (10(() 132)
|Pex|13||G(d)) ||2
mink =(110(=) |11 + |10//) 11
(Cauchy-Schward Inequality)
VK]|G lloo
minx(( 1/1)
(Plugging in 33
8v 8vbbollo 100e0//0elll 1 |
(max: T [|0(()) ||1)
(Condition
8yKboll |
|10111)2
C2k
8/ K Ko |10z 1/11111
1
C5
2 4>>
(38)
Plugging
38
into 37
we have
la' D M04) M - -
Mio) (0) D-1 )al
Mio
25

---

Published as a conference paper at ICLR 2023
max k[|K]
M (M - M Jan
la'
Mi0) M 11
D D
Mo
0
max kE[K]
la'D Mris Mr(0) D
Arios al
Cs
C
la'
D
M
M1 D-
Mio
(39)
C5
Mils
Combining 27
36
and
39
we have
a'Ma a' (M S a (M - ) al
+ +1a +a'(DD 1 - P M (0) D (D) )al
CGla'' Mioo M D P al
+ +Csla' (Di M (0) Did D asio:
M (0)
D-
al
+ +1a (D M (0) D - aeio) M(1) D-
-
Mi0o )al
Miio al + +Cs +1)aa' D M
Cala'D M (0) D
M000
D
D D Mno M( D Mroos )ol
S CGlla'D
M D
M al
M10)
(Cs + 1)
C2
J'D
Mil: M
M1 M
Mo
1 1- O3
20s
la (0)
(40)
1- Cs
Hence for any vector a E Tick
d MM 2 |a'M(0)a - la'Ma o' 1- 30g
a (1
(41)
1 - Cs
To conclude, in this subsection, we successfully reduce the noisy case Ja Mal to the oracle case Ja' (T) Result (41) will also be used in the proof of other claims.
H PROOF OF THEOREM 2
Theorem 2. Consider the DCBM model where (8)-9) hold. There exists constant C' >>> 0, such that for any 8 E (0, 1/2), with probability 1 - ô, simultaneously for S k K,
( |011 min 1103
log(1/8) 1/8)
110 1|2
(h uu ((t)) S
11
[ 11
To prove Theorem 2 we need famous concentration inequality, Bernstein inequality:
Lemma 7 (Bersteei inequality). Suppose X1, X1..., X,, independent random variables such that
E.X; = 0, [&| & and Var(X.)) S of for all i. Let 0² = n "in of. Then, for any > O,
X1 21 < 2exp (- nt2
P P n
1
(-oz bt/3
26

---

Published as a conference paper at ICLR 2023
The proof of Lemma Bernstein inequality, can be seen in most probability textbooks such as Uspensky 1937).
Proof. Recall that for k E [K].
Sn ((le) = v(f(A (le, f(;
wu ((lu) w (S(D (lu), S(EX; (k)))
Denote V by Lemma
f(A(h); fll), [(x; fllx), in - 1(2((), o = -[EX; [K]. Then,
(Tle) vi(0k, 0²) s vi(K 0x) + (0 v²)
I (UK, (x)) + (0z. 10) ) + 1b(0",
v ( Un) (/" v²)
Similarly,
vi((le S &n ((lr - viek, Ux) + v²)
Therefore,
(Tw)) th s mx) + "00","""
(42)
For any $1,..,, Φx 2 O.
vk E [K], U2 ((tu)) S oxx)
P (ak [K], 15 (TTe) ((terl > ox
K
2 p (flrr)))) - (l > oxz)
(43)
By definition of 4h, ((e)) th =0. Hence, ((l() thx ((tw) E [0, As a result,
when d& 2 n,
(()x)((le)) sha (fx)) > Φxx) =
When de < n. by 442
IP (((xx(())) - a'a ((u)) ox) s P ((b( Tk) + +000, v²) > 6x))
1
1
< (VN: (k) >
2 th or v0ō"" w²) >
2 T
$ (1k: 06) > 0x) + PP (0" , > 1 0/
(44)
2
By lemma 5 when ||2g - Txll < |0001l
Vuun, Tx) < arcsin |/u 0z
Hence, for any o E [0, 5). |10 - U사ll & sin( 0xll implies (kk. 01) S o. As result, for any o [0, }), (, 0x) implies 1|uk uull > [l)
Similarly, for any ò E [0, }) (vv", ūt) > implies ||0- - 5* > sin( 1*||
By definition of Φ2. dx 2 0. Hence, when dx < n. f E [0, F). Plugging the above results into have
27

---

Published as a conference paper at ICLR 2023
IP (Tw) 1/2 (TTx)) > 2x)
- P (ex ūx) > 1 )x) + P 15(0",
-(((((0' .0) > 200)
2
$ SP (11) - اx1l 2 sin( xx)) 2 ( ||) + P P(1e* - -8"11 2 sin( 2 0
S <P(3 E [2K], (0v oz)11 2 VK sin( 2 Φ l|öx/l)
+
P
I E [2 100" - 8y)r z VK sin
2 )
2K
1
<
IP
(vv ox}il 2
vk sinl 2 )ba) |āsll)
1=1
2k
(1(0* - -0')11 VK sin( 2bx (
+
(45)
Since when dhe < <T, 10x E [0, 3. by Lemma sin( (b))) 2 2 2/ 1 Plugging back to (5)). we have when Øk <
PP (Ti) - 2hx (ftte) > ox)
2K
2K
Σ P ((KU - ox)ul 2 x / SR (1xll
Σ P 00"'l // 2x xxx10*) 1001)) (46)
TVK
remains to evaluate P ((002 uk){ 2 N are illustrated in the following two lemmas.
ballēx and IP (I(o- 5r)a 2 1 ox 11011)
which
When du 2 2 Lemma 8. Define Co 16v2
C²
10 1 2
10 I
P (((VE-- - To)i 2
th l S 2eex
(- (-c² 02
Co
TVK
Lemma 9, Define C7 = 222nnC2 Then,
C2
(-
C7
P((0--0'))
@xllū"1) < 2exp
C2 (-c2
02 (101)
TVK
The proof of Lemma g and 9 are quite tedious. We would defer their proof's to the end of this section.
Choose
log(1/6) Φe (c, = C (v/ |001 mnin(0,,110% [1]
1 12
[ 1h |101)
Then leveraging on Lemma and
we have when C 2/2K2
exxp ( 1o (ogglo))))1)) 110000001111100000 11100111 de 112
P P((e2-
8x)ol2 2
1
TV
K
C2110112 min [ [1}
2xx ( logg(g))))
25
(47)
28

---

Published as a conference paper at ICLR 2023
C₂C² Logg9800188800
PP P(((0--00) -0"),1
2n 0xl(0*11
exp
TVK
C3110||2 min 110 11)
S 2exp (- (og((16)))
-
(48)
Plugging (7 and 48
back (46
leveraging on the fact that < 1, we obtain when di < n,
and C 2 2v 2m k
P ([w) ((lx)) > 6x) s 4K8 + 4K0 28K8'b
Recall that when n
P (((a((Tt)) va > ox) =
In all, we have that when C' 2/2K2?
IP (( - tha (Tx() > 0x 58K50
(49)
Substituting 44
into 43 obtain that when C 222V2TK?
P vk [K], ((te) - (a(ltl s 6b)) 21-8K20
(50)
Hence, it suffices make 8K 8. Choose
16v2T"C, (1 + log(8K?)
C m2x
}}
(51)
log
Then Cs 1
log(8k3) log
> 1. Since 8 S 2.
C6-1
806-1 <
lox ( 2
8K2
lox
As result, 2K2 <
Hence, choose C' as in 51) then C' >), and for any E (0, 1/2),
Vk E [K], ((.))) via (ūعr) s Φx 2 1 1 8
(52)
To conclude, there exists constant C > 0, such that for any ā E 1/2), with probability simultaneously for 1 < k < K,
log(1/8)
(a(()t)) (ftaal s C,
|10|) min((r [10( |1
H.1
PROOF OF LEMMA 8
Proof. When / [K].
(kx) ((()(()))))))))) =2(
Σ Zi
rECunC jEcinG
29

---

Published as a conference paper at ICLR 2023
When / E {K + 1.... 2 define
Ć f t; = ec-kt
then
(ūx)) = (f(2 = (2(00 (in))
Σ
Σ
SECuNC jeC;
Hence
0 1l
(ūx)
LE|2K]
1
(Cauchy-Schward
2
(ūx))²²
2K
1E|2K]
(ūx)+l
2K
[E|2K]
K
2K
Σ
Σ
E
Dy E
Σ
Σ
V2K
1=1 iEC jECINE
I= sECunL
Σ
Σ
Sayl
v2K
SECENL JEC
VECENC jEú
Σ
Qi
V2K
LEC+OL JE(m)
Σ
Σ Dij
V2K
VECANL JECK
1
Σ
Pg0
VKK
iECArL JECK
(Identifiability condition)
Σ
Σ
0:8,
VKK TECANRjECS
110%)
11211000011
2K
1
[10(%)
1l2 [E[K]
min
110011 112
v 2K
(Condition 9
2
1
(10( || max
1000
C2 C2
K
110% | |1
(53)
C2Kv2K
When E [K].
(ve) (((A())) [u)): 1
Σ
Aij
VECANL JECinL
Recall that,
(Tx): (f(2(()) (()))) = 1000
Σ
Σ Rig
rECuriC fECine
So
((ve 0k]1l= Σ Σ (Aij Riy
JECine
30

---

Published as a conference paper at ICLR 2023
When / E [K], since Hy only depends Aua. it is independent of Agc. Hence, given Nu. {A, - Pay : Cx DC E C L} are a collection of [C& n C| n 2 independent random
variables. Furthermore, given Nu, for any i E C₁ n L e
E Ais - Riy [u]]
E AAj - -ag = S2g Qis =
Also,
- S As Oii S AAi $1
So |Ai -0--4p Piyl S 1. Additionally,
var (Ag S115) = warl (As = 14 S2i)) s S2i
Therefore, denote n&
|Cx EI|C n C). by Lemma 7
IP [10 Tw)il=
1
Φx ukll)
TVK K
E P (vv - ux)il 2
tb | lite|
xV TVK
E
Σ Σ JECinE
(Ais - -ciil1
1
de |1xe Mar
nkki
TV Knni
TVKnz Øx @xl(ūall) 2
1 nkll
2
$ exp
E Eiec&r Esecinc Oig =VKns 2 @x|1tell
Til
|
2E exp
2T K
A Eiecune Ejec Sii + foulluull
2
| 112
2E exp
2T 2TV K K
Jo 1
1
2E exp
2T K
TV
+ 1
$ |
$ 2E exp
(54)
2TV (T K
When / - k {A. Ply i,j E C&nC, i < j} are collection of random variables. Furthermore, for any i.j E C2 n L, < j.
- independent
E[Ai; 22j)) E.A. Qig 2ig
Qij
0
Also,
-15 -lg S Au - 2ig $ AAg $
So |Ai- Payl 5 1.
Additionally,
war( (Ai 223) var(An,) = O1 22y) s 224
Denote R&g = C n G) - 1), we have
(1(1k Ux)il 2
2x (ellixel)
=P =P( L E Σ (Aig Rijil1 2
1
nikk VECENIC JECANC
31

---

Published as a conference paper at ICLR 2023
2
Σ
(A, - -Ri)) +
Σ
Qai 2
@xelBael)
Klkk
evKnae
KESECAAL
iECuNC
E
(Ag- -S(-))1 2
1
0xl1ūx|1
1
E Qm1)
Tikk
TT TV Knkk
nokk RECorL
i<JECENE
E
(Aij -91))1
1
Σ
223
nikk
2T Knek
2n iEC&NR
i<jECEnC
1
=
E
(As - -22))1 2
0x
Se liuu
(55)
2 BTvKnw
2TRR
i<jEC,ne
RECEnC
Notice that
|10( 11
ΦK 2 C
110 (k)
2 1 1
12
Since Φx 2 22/2TC2k²
10 1110111 11
2v K2
100(
2
1111 1
2T v K niR
2 K nER
100
C2K V2K
(By 53
100 (8)
11
11 1011
CoKv2K
21l kmkk
(K)) 1|2
1
Σ 02
2nak
VECANe
(Identifiability condition)
Σ
PRk
V2TK2 211
sECuNe
(56)
2n
iECANe
Therefore, by Lemma]
7
P P(((Kk un))l 2
1
du 11xxll)
TV K
E PP
Σ
(Aij - -Riil1
1
dx T
1
Nikk
2T Knek
2 2T / K R
i<jECAne
2 Tiikk JnvKnu
1
< expexp
Eiejecinc Di + 2nvKnus dx fxll
2nac Eiecine
Aikk
(bullūzel)
< expexp
16TV K T K 2 2i Oi + I0ull
(xxl(x/l)
< 2E exp
16TV K T WV E Eijecanc Dig + tc
1 112
2xEexp
16mV K T TV
81 del + 1
||
32

---

Published as a conference paper at ICLR 2023
0% u
exp
16TT K TV K
((t))
16 I|
o 0
$ 22E 22EEepp exp
(57)
16TV 1 ( 3)
When E {K + ...,,,,.,000 2K), recall
= क. = =e-K}
So
(ok) = (f(A = 1
Σ
Ad
iECENC jECi
Recall that
(ix) = (1(22(()) = -2(00) (fxx)
E SECENC jeC,
Σ
Di
So
1(uk - -k)d= (Ai
SECANL
Since Ih only depends Auu it is independent of Agu. Hence, given llg {Ag Qu : e C& C.C.jj ( are a collection of [C n ClCc independent random variables. Furthermore, given ily for any i E C. n Ci
E Aij R4j [u]
E [[Ass - -laj = -Ωi -2i = 0
Also,
-15 -si S Aij - -2is s Aij 1
So |Ai - Diyl I 1. Additionally,
var (Ai - S255) = var (os(ltttt)) = Pay(1 -sis)) S Siy
Therefore, denote uu = 1Cx n El(C,,, by Lemma 7
TP [1v - oz)xl 2 TVK 2h | uxll
E
(uy - -xx)il
Sb 10x1 Ii4
TVK
=
E
Σ
(Ai - 1uy12
dx | iiee
fiat
TV Kinu
sECunL jec
2 AvKin Φx [all"ll"
Auul
< exp
1411 Eiecore Ejec, Digj BVVKN 2x |u
|
2E exp
2m K TV K K Eiecine Ejec, Oaz + f
1x 1|
exp
2m / K
TV (5x) )ol
+ th |
2 [x
exp
2 TV
K
[Bx)
33

---

Published as a conference paper at ICLR 2023
$ 1 2TV 2TVK K + 3)
S exp
(58)
In all, for any E [2K].
0f uK (
P (((0x - ūxhil 2 #vK
2x 01011111) < 22
(59)
Plugging
53 into (5 we obtain
2210 111101
PP (((( - tc)1l 2 IT TVK 2b 1(/al))
s 2exp
16 C2
Co
= =2xxp
&7 11 111110112 2
(60)
That concludes the proof.
H.2 PROOF OF LEMMA y
The proof of Lemma is nearly the same Lemma 8 For the completeness of our paper, will present a proof of Lemma 9 as follows.
Proof. When / E [K].
(v")== = (((: X10)= = E X2
jECinE
Similarly,
(6*), = (I(E =
E
[[X₁]
jEciNe
So
1(0" (w---0)) -*) E(,
JECINE
When E [K]. since fl only depends on Auas it is independent of X. Hence, given fu. (X, B[X,) j C, n L} collection of |C] O L) independent random variables. Furthermore, given
fy, for any j E C2 C
X, E[x,|[ux] = E =[x, [u - E[x,] = E[X,] B[X,] 0
E
Also,
-1 s X, - xX, 1
So XX - -[Xx]] 1. Additionally,
var Xx - -[(x,) var (X,lit) - E|XX (1 B[x,)) < B[X,]
Therefore, denote = |Ic, n L), by Lemma
P 11"0=~ 2 TVK" 2 p
= P (I((0- - -0))
Sxll ll 0+ M
34

---

Published as a conference paper at ICLR 2023
E
P 1
Σ
(xy- - B|X,D12
1
Φu | 1
MI
T KVKu
JECI22
1/1 TvKn
ON |0 )²
2 exp
Ejecin [[[x]] +
2& 00
3 WvKKI
18"0
2E exp
2 V K TVKE Jecine
B[X;)
3 tx 10
2
100112
21 exp
2 TT K (8*) )ol + 0 |5+
1
2E exp
2T K
T
K
|6-1 |
2 1 |
S 2EEexp
(61)
2T 2T ( +
When E {K 1, .,., 2K), define
fieie t. = =e_k]
Then
(u = (f(: X1 Ex,
JEC.
Similarly,
(ō"); ((E[[X]Ilx)) =[X]1 Σ E[X;]
SEC
So
16-- 00))==)+1== Exx,-
jEC.
When E [K]. since fl only depends on Aua, it is independent of X. Hence, given fuu (X,
E[X,] : j ci} are collection of [C n LI independent random variables. Furthermore, given Ni.
for any j E C..
E X, E[X
= E EE[x,ILL
- E[1,] = E[x,] - B[X,] = 0
Also,
-B s X, - B[X,]| S X, S 1
So XX, [[X,]| & 1. Additionally,
var (5]-_[x,)) = var (x,lii) = EIX -1 (1- & E[X,]
Therefore, denote ñq = =1Crl. by Lemma 7
P P((00- - -5n11 TVK K
E
(1(0* - -r)= N
TvK 2x @x1(011| IiTz
1
1
E
Σ (X, - E(x,)||
fu
<VKin
JEC.
35

---

Published as a conference paper at ICLR 2023
TvKi Φ -100
< 2E exp
1
Ejee,
[[X]]
aV Kig 2N 80
?i
10a1 1|2
exp
2 / K
K Σ jEC,
B[X,]
/ 110
1 11
exp
2 BTvK K
K (6+) )1l + _
$ 0
exp
2T K
क K
( 11l
< exp
(62)
2TVK(TVV + +3))
In all, for any / E [2K].
2 px|l0=1) 2Bexx
(T K +
(63)
xV K
Notice that
Σ (o-)
[E(2K]
(Cauchy-Schwartz)
(T*)))²
2K
LE [E(2K]
(0")xl
22
[E(2K]
K
E[X,I+ +
Σ >ΣEX B(X,I|
V2K
JECI
1= K= jed,
1
[X(x,] + Σ EXX1]
V2K
JEL
jEú
Σ
B[X,]
V2K
JE[n
Σ [[
2K
JEC+
Σ
000,
PE-K-
V2K
JECK
(Identifiability condition)
1
Σ 000,
V2K
jECK
1
0'10009111
|||
V2K
1
0r
min IE[K]
|0000
V2K
(Condition 9 2
0*
max [K(
|000
C2v2K
36

---

Published as a conference paper at ICLR 2023
07 1011111
(64)
C2K 2
Plugging into 63 we obtain
2 00111
P P(((o* - 87)a 2 TVK 0x110*11) s exxp
-
+ +
2 1100111111
C7
eex
(65)
That concludes the proof.
I PROOF OF COROLLARY 2
1.1 PROOF OF COROLLARY I
Corollary 1. Consider the DCBM model where 8 8 hold. Suppose for some constants by E (0, and e E (0, 1/2), The is by-correct with probability
When bo is properly small, there exist
constants Co > and C > O, which do not depend on (bo, c), such that P(ğ # k*) S c
C C'K exp (-Co, min (10(( l11b).
Proof. Let Bo be the event that il is co-rerr,ct. Then,
P(O# **)
= PP( + K. BB) + P 8 + kk, ,B))
P(BB) + 3k & k", Uu (ftee) S vx- ((te) Bo)
$ se+Po P 3k # ki, (w' (Itee - Sn (itu))
+ dx (ftee) vhe (Tt)) 2 (fTe) the (ft)) Bo)
S SE+P ( 3k + k", 11 - (Llre)
+ J (fiz) the (ftw) 2 ((l()) the (it)) Bu)
(66)
By Theorem] [ when by is properly small, By implies that there exists a constant co 0, which does not depend on bo. such that thk- (iiz) and mingze (vlx))))) 2 c,Bn.
Substituting this result into (66). we have P # R²))
5 6 +
3k # k²t
(T En (fx)
+
xx (ft) - 2/- (Th)) 2 copn) Bo)
3k # k0,
Wh (1le) S2 (1lx)) )
+
54 (Lle) - -x- (itu) 2 co3r)
<ct P
33 [K].
A4 (f Ex (fte)
S PP
3k E [K].
sh (fTw) Shx (ftz)
3 cn
(67)
According to Theorem 2 there exists a constant C > 0, such that for any 8 E (0, 1/2), with probability 1 - 8, simultancously for 1 < k K,
log(1/8)
_ I|2
(Tx)) Vu (ft)) =
(
+ (1002) 11
110111 min (10((())) 111
37

---

Published as a conference paper at ICLR 2023
ci
Take Co 36C
8 = exp(-Co8%110) min 0r, min
E 2012111 kE(K] [
Then
log 1/expp -C, min 0r, minkelk 1102
(1/()
C
C
|00l min 1
||0||2 min [100 1113
Co 0ll min or, minkelk] [10221 11
=c -
|101| min _ 111
(68)
On the other hand, take C3 in condition (9 properly small such that c3 S ca. then according to condition
1
1
C 100h 11
SC cz
6 c0nnn
(69)
Combining 668 and (69). have
|1011: min(0" "10 (v
log(1/5)
| 1|2
+
-
CoBn
100 (k) 11011
3
Therefore, when 8 < 2. by Theorem 2 with probability - 8, simultaneously for S S K,
(ft)) wix (ft) s co.nu.
As result, when d < 1
1 TP ak E [K], (a - (atttt { s
When d 2 2
PP P(K E [K], (z - 3xx (fz))
1 g0oßm)
s S
Hence in total, we have
P 3k E [K], - (flel)
>
3 g008mn
1
S 28
(70)
Plugging
70 into
67
we obtain
P P k²) S e + 25
= =c 2exp -Coss min
0r min
( 11a
ke[K]
<
exp -Co min 010 1113
(71)
k=1
Choose Ō= 2, we obtain
K P( **) cc+ +(++))++++ Σ
exp - Co,32 [0]] min min [10(())1)))
k=1
38

---

Published as a conference paper at ICLR 2023
To conclude, when by is properly small, there exist constants Cp do not depend on (bo, e), such that P2 # k*) - c+ c+ exp (c 0f", -000 l1b)
36C > and C -= 2 2>> 0. which
c/
1.2 PROOF OF COROLLARY 2
Corollary 2. Consider the DCBM model where 81-19 hold. We apply SCORE+ to obtain The and plug it into AngleMin+. As n + oc, suppose for some constant qu > 0, min.eu 8, 2 qu maX 0g. So (oul 2 9o hov/og(),, 0 | - co, and (2 ming {1le so the AngleMin+ estimate is consistent.
C [1} + cc. Then, Più + k*) - 0,
Proof. By Corollary let be the probability that Hu obtained through SCORE+ is not bo-correct, then
P( sc+ Σ exp (-Co 1011
Since 1211011 0
( oc, and 3 mink (100 [11] x.,
C exp C, min 1133) - 0
By Theorem 2.2 in Jin al. (2021), when go is sufficiently large, minigu Og 2 go maxieu 0g and Ba Ball0ul1 2 40 / /lo((n) imply that 0.
Hence, in all, we have P(O + k*) + O, so the AngleMin+ estimate is consistent.
J PROOF OF LEMMA 2
As mentioned in section D in the main paper, for the smoothness and comprehensibility of the text, we do not present the most general form of Lemma 2 Here, present both the original version, Lemma
2 and the generalized version, Lemma [ below, where we relax the assumption that
16 ln 0
0 hn
1 to the much weaker assumption: the first part of condition (9) in the main text,
10th
1 h
which only assumes that ||0(2)|12 and ||0(2)||, 1 are of the same order.
Lemma 2. Consider DCBM with K
and P (1 b) + b1212. Suppose 0* o(1), | [|:
ming 11 = o(1), 1- o(.) 1022 lh 10 Ih:
= 1. There exists constant C4 > 0 such that
6) 0 (110cl1 + 110llll)
inf (Risk(ū)) 2 ci exp 2[1 + o(1) 9
(12)
where the infimum is laken over all measurable functions of A, X, and parameters IIc lu, O, P. gr. In AngleMin+. suppose the second part of condition holds with = o(1), Ik is bo-correct with by $ 0. There is constant C4 > 0 such that,
Risk(ū) S Cs exp{ - o(1) - 6)2
(1 + 1 12)2 0+ 10 + | 1i
(13)
Lemma 2. Consider a DCBM with K = 2 and P = P=(1- -)-b + b1,14. Suppose b = o(1).
There exists constant C4 0 such that
-2 + o(1) (1 b)²
inf (Risk(i)) 2 cxp{ 2[1
0 (1102111 + [10ull:).
(75)
where the infimum laken over all measurable functions of A, X, and parameters TT. Nu. Q, P. Or. In AngleMin+, suppose condition 9 holds with e o(1), 0* o(1),
ming 110 (11, 11
9r
39

---

Published as a conference paper at ICLR 2023
by borcerrect with bu "3 O. There is constant C2 > 0 such that,
b)2
Risk(() & C₁ exp
-[1 -[1-o(1)]
o[1)
(76')
8
10 11 110
1 1 IR
2 11 01 11f)
(1102 11 11f)
When conditions Lemma 2 hold, conditions of Lemma 2 hold. Also, with 1
1
1
assumed Lemma [2] the results of Lemma
2 imply the results
of Therefore, suffices to prove
the generalized version, Lemma 2
prove the lower bound
75) and upper bound (76) separately.
J.1 PROOF OF LOWER BOUND
75
Proof. Let L(1) and p(2) be the joint distribution of A and X given R² 61 and n² c2, respecttivy For random variable or vector or matrix Y, ( and p(2) be distribution of Y given n e1 and π² respectively.
According to Theorem 2.2 Section 2.4.2
Tsybakov 2009)..
inf(Ris((ū)) 2. (1 HP((()), P(()) H2(P(), ((2))/4)))
2
(1 1 H2 (p(() (lcaa taraa
1 (1 H2(()))
((iaa
2
2
1 ( 112 (p(1), ((l))) )²
2
(76)
2 2
where
(1((((1) p(?)) = / dP(2)
is the Hellinger distance between PP1) and P(2).
As in Section 2.4 of Tsybakov (2009). one key property of Hellinger distance is that if Q(() and Q(2)
product measures, ( @ Q(2)
@ then
N
H²
H2(00)00)) =
II
(77)
2
Notice that for & = 1,2, since according to DCBM, X1, X ....,,, Xn are independent,
pp(k) (k) A
x - 1 (k)
(78)
Combining (77) and (78). we obtain
(P(()))) p(2) A
H² (P() X.i
P(P))
(P()11), p(2)) = 2(1 (111111- (1-
(79)
Given x² = E1 and N" = e2, according to DCBM, the distribution of A remains the same. As result, (P())) p(2)) 0.
On the other hand, for = 1,2 and E [n]. according to DCBM model
(kk
Bern(O 0, PrK.)
40

---

Published as a conference paper at ICLR 2023
where & is the true label of node i.
As a result,
2 H ( X, P(.
_ 1000.Pik -0-0.P2). )² + (V1 0T0,PiN; v1 0 020 P2k:
(
27
V 820, + V(I- 0- 8-0,P2k))
(80)
For 2, R. denote g(z, v) log(ry + v(1 x²) y21).
Then, (3 K.
PR) exp /000, v (00
Hence, by 79
11 2 ,02)), = (1- (2(p()) pp(2)
pp(
x,
2
2
2
exp Σ o OV000,PPks V0.),
(81)
Substituting 81 into (7).. we obtain
Pike, inf (Risk(()))) 2 exp (50(2) (2> g 0r Pike, 00-0, Pak.)
(82)
To reduce the RHS of 82 we need to evaluate g. The following lemma shows that g(x, y) - (x: y)?.
Lemma 10. Suppose that S x. S < 1. Then,
g(z,8) v) 2 2(1 a2) (x y)²
Proof. We first prove short inequality on log. For z > 0, define ga(z) log(z) 2-1 8
Then
93(2)
2
Therefore, when < 1, d d
d2 gx() < 0, gz(2) is monotonously deceasing, hence ga(z) 2 93(1) = 0; when 2 2 1, de (3(2)) 2 0. g2(2) is monotonously increasing, hence ga(2) 2 gs(() 0.
In all, g2(2) 2 0, so
log(2) 2 --1
(83)
Since v, [0, 1]. we could define o, aresin 2 E [0, Fl. 0, arcsin E [0, 3]. Then,
g(x,y)
(sin Φ2, sin Φy)
log sin &2 sin Φ, + ((1 sin dz)(1 >in² sin? ov))
log(sin Φe sin Φy + cos dr cos (b,)
log(cos(12: 2)))
41

---

Published as a conference paper at ICLR 2023
cos(Os Qyy
(y 83
cos( 0r Fyy
2 sin (ox Ób)
cos(1b (r Q1y)
1 4sin² (0.- 00,
(sin 0x -sin 0y)
2 (sin Os sin 0y) 2 cos(Or 0y)
1 4 4sin² (d--
(0, (o )2 cos(ther -byy (00 - 11)
2 (2sin (da-Oy)
COS
2
(x y)
(84)
2
cos(1
Φyl) cos² (t.t
Since z, y E [0, a). or, Oy E [0, aresin a) As a result, 10x - -Byl (dut this result back into (84). we have
E [0, arcsin a]. Plugging
2
g(x, v) 2 2
y)²
2(1 a2) (x y)
(85)
cos(arcsin a) cos? arcsin
This concludes the proof.
Back the proof of lower bound (75). Define 0 -0r
- [maxie (1, then for any
/0-
k E (1,2), [n), v S 8". Therefore, applying Lemma
10 82
we have when 0"
inf inf(Risk(0)) 2 2
exp 2 i=1
2(1 (04)2)3 (V818,PLk. - 0 Pak.
n
000: VPkk v P2kee) ?
exp
(1 - (00)2) &
exp
0" vb)²)
(1 - (00)2)
2
1=1
(1 - 6)3
exp
0'110111
[1 - (00)2)
(1 vb)2
4
(1- b)2
= 2
exp -2
(1 + vb)(11 - (
(1100ll + (10ulli)
(86)
Since 0" = o(1), o(1), and by DCBM model, max 0: S. we have 0a oo (mxxi(()] 0:) [max(1,b) = o(1). Since b = 1 o(1). (1 + vb)2 - 4. Therefore, o(1). Substituting these results into (86). we obtain
(I+v))((--(0))))
inf (Risk(())) ス exp{ ( 2[1 o(1)] 6)2
0 (110ell + 11Bulli)3:
(87)
This concludes proof of lower bound 75 with C1 2
J.2 PROOF OF UPPER BOUND 76"'
Proof. When K 2. Risk(() P(O = 2/ e1) + P(O 1| ez). The evaluation of
Fi 2/ = E1 and PPO = 1/T" = 62) are exactly the same. Without the loss of generosity, we would focus P( 2/ e1).
42

---

Published as a conference paper at ICLR 2023
Recall that in the proof of we define uk f(A(W) v- f(X; in 8" S(EX; Mu), k E [K].
2
We have
P( 2/ = =1)= = P(b((12))) v²) 2 (111, v² | = =(1)
P {u',02) 02)
{0 v1)
vil T"" = =e1)
P (o", ||22||
1/2
U1
2 0 T" e1)
|
(88)
Recall that in proof of Lemma 8 9 we define Ca = (i E : म. = ex =x K +1, 1,..... 2K. Let
12
Since when
[]]
P2
||l]||
- ((x; x1 = E X
jEcine
; when / E {K 1,, ..., 2K}.
(=²)= = ([(; =1 Ex,
JEC.
we have
K
2
P(ý=2/m
e1) PP
Wkkk
Σ DC
X; +
Σ
Wk Σ x x²' =a)
iECx
k=
K+1
iECi
K
2K
wx(X; EX,)
Σ
wh(X, EX)) N
k= VECANC
k= +1+11 iEC,
K
2K
Σ
Σ
WEEX, Σ
wy WxX T = ===== =eq
k= 1E
k=K
iECh
K
2K
SP(
<
Σ
wa(X; EX,) +
Σ
wx(X, - -EX,) N
k=1 iECanE
k= K+ sECx
2K
Σ
Σ
W&EXx
Σ
Σ
w& WxE.,, 7" =ei=
k=K+1 ied
K
2K
E
Σ wx(X, - EX) +
Σ
Σ wx EXX,)
k=
k=
2K Σ
wrEX,,+ +
wy wrY.,,
A, =e)====))
ei)]
(89)
R= TECone
Am K+1 iec
Since A and X are independent and for k E [2K]. we is measurable with respect to A, given A, (wx (X, EX,)) k E [K], i C. n L) U (we((( E.X,) A E [K]] E d& are collection of independent random variables. Also, for any k E [2K] E [n].
E E/ (X, EX wy E X
|||
EX;))
we (EX, EX,) 0
Furthermore,
-1 -15 < X, EX, S 8:51
So |wn (X, EXX)) maxxe[2k] |wk/-
43

---

Published as a conference paper at ICLR 2023
Additionally,
var(wa(X; (X = wfvar(Xi) = (1 - EX;) S n
Let
K
2K
t WxEX, +
Σ
Σ wxlEX,
1 [20, 5ー)
T k=1 TEC,NC
n
k=K+1 +1 veCe
0²
K
W Ex +
Σ
2K
Σ
1 myEX;)
(w w. 0*)
iECANL
k= ki
where is defined as (w?, w2x)
Then by Lemma 7
K
2K
Pg = 2/ = e1) s E
Σ Σ
wx(X; EX,) +
Σ wx(X, - -EX,) 7
k= iECAnE
b= k==+1 iECx
K
2K
Σ wxEX, ( (())
W,E.,, +
A= LECLNR
A K+ sECx
nt
< 2EE exp
02 + 1/S maxke [|2K] |
1/2 (w, 0²
21E exp
(90)
(10 o w, σ*) maxxele]] | Kw, 6*)
(0 1
By Lemma when @ 2 22/2TC2K2
I1 1010"
P P(((E= ūk){ 2
-ix)xl
Co s 2xep
c2 03110 11110111
TvK K
Take
|
0*
0.25
Φ max (nax(2V22) (2V22 C2K²
}
110
|011
min 110[%)11 |||
Then because min (x] 110 o(1) and by condition 9
S caB,, o(11 - bl), we have
110
11
o(|1 - 61). Also,
IP P(3k [K],EE [2K], ((vh- -xx)r 2
TV K
S Σ Σ
P
(1 - Tx)al 2
1
KE|K] [E2K]
Σ
2xxp
Co
2010 [100211110011)
C
AE(K] LE 2K]
Co
-0.5
110(a) ||
Σ Σ
2 2exp
C2 (1 6)3
0
0010011
minsetk] [10(2)11
110%%) |||
minkE(K]
LE (E
< 4K² exp
(
(1 b)20)110111
o(1)
< inf (Risk())) y
(91)
44

---

Published as a conference paper at ICLR 2023
Hence, can focus the case where for all ls [K]. E [2K], 1(ox Bx)sl o[11 b6)11 Until the end of the proof, we assume that we are under this case.
We first evaluate (w, ).). Let i-
8n
Then,
||
16
-
(wx, Ø*) (w, 6*> = 1((
12
U1
(
02 1022
|
||
||
||ā^||
KK
1/2
222
01
| |l } |000 )
01
| ||
|022||
|eal
= ||
Kcos
x>( U2, 80)
- cos xb (22 (0))
(cos (11,
(1, 80) cos (6) (*))
(122,, 6*) 4 (12, x*)
sin (/222 (²) + 1b(52, 0*)
||8*||
2in
2
2
15(11, 8*)
- (011 8*)
sin (11, x*) + (01 8*))
+ 2 sin
2
2
sin [1/22, 07) (02, 8*)
sin (12, 8*) + (122 8*)
$ 2|1001| ||
2
2
[v(,,, 8*)
(b1,, U*)
sin ((11, (*) + Ú")
+ 2|
sin
2
2
(V2, 02)
sin (0, 8*) + (02, 02)
(By Lemma 4
s 2| sin
2
2
+ 1| sin (11, 81)
21, 0*) + vi111, 01)
sin
(92)
2
2
Since n² 1. by - 0, by Theorem (b) 7*) 1/1 = 0. (02 x*) = 1/2 > co.n = col 1 b/.
On the other hand, that for all & E [K], E [2K]. 117% ux)ul = a( - b1) indicates that
||lg o = o(11 Rx]l By lemma 5 this implies that (11 01) o 1 b1), k 1,2. Therefore.
(022, 8*)
(w, 8*) - (w. .*> s o(1)
||10*|| sin
sin (02,
2
( 5t)
sin ((22
0*)
(62 0*)
= o(1) || || sin
cos
2
2
2
8*)
202
o(1) ||0 sin 2
COS
2
2
sin (02 8")
< o(1) ||0
2
< o(1) |55 [1 cos v (ū2, t²))
o(1) |60" [cos (ū), 5*)
cos ( 5*))
01
02
o(1) ||
|
1 ll
i+
o(1) (-(w,
S o(1) ((5,
(93)
Therefore, (w, (7)) = (x),0))((1))) (1 + (1)) 8*).
Let Mht = - 0: Let Há (k) = 10th)) 11, E [C,U3, k E [K]. Then,
i = (4 (1 bu .uu
(1) - 1/22 + b1p21, b1r + 1/12 br21))
82 = m (bpl) 4e bull
(2)
(1) bmp + 721, Mu
(2) + by 1/21)
8- = 6r (12) buc .uu ma + b121, bp + 1/12 b1p1)
(2) (1)
(2)
Hence,
(0,5))
(I2ū+)
- (10, 5*) = || (1
6+
12 6*
45

---

Published as a conference paper at ICLR 2023
|| (1- / 1 (1 63) 200 () 212 413
(94)
| 2 i22 12
where
I =2 + (wi)) 1112)) + 121
L2 (2 + (pt) 72122² + T2
Is (1/) 72) + (ul)) (2)
7/21 M2
Notice that
11 4I3 - (
22222)
(x (14 (2)
( + n (2)
+ 2m22 (1) ((+2))++(1))
2/ ((1 (1) + (1()))
+ +43
S ((42 + (14 (1)) + 22 + (1/ 12) (7112 + 1/212 )²
2m12l (1) ((12 (2 (1/) )2) + 21/21/2 (1/ )2) + (1 )2)
)( + 8((() (2) )
[10] 721 1 2 20 10 (m1 + m21) 81101 + +121)²
I (90g + 2b.) 10|
o(1) ||0|1
(95)
On the other hand,
(2 + (()))))))))))))))))))))))))))))) + (1))))))
2
4 (122)
1
1 + 14 ( + 11u 12
1 1111020011
1
min [|0(
IP?
max |10()) ke[k]
4
kE[K]
(By condition 9 2
max KE[K]
||0(0)
4C₂
64C² |011
(96)
Therefore,
I,I2 - 4Iz = -1+ (100)))))))))))
(2) + -1 (1)
Similarly,
1 (1 (1) 2()))
(1 (1+ (1)
(1)) + (2 + (2 + 22
||o*|| = (1 + o()))0' V (1 (1 12 + 12
46

---

Published as a conference paper at ICLR 2023
Therefore,
(1+ (1)) b2)2 (12 (,)))+ (4
-wū, = - 1|00|| 1 11-1 1
(4 + (14 1 )2)2
= / (1 12)2 (2 ((
(2)
((x2))2 (Hu (2 (1z (2)1
2(1 (11+0 (1- b)2 (3) (Nz (4)))) )3)
(97)
((u22)) (447))2 (u(2)) + (Mz 22)1.
(2)
We turn to (w o w, 8*).
Denote that
1/
1
01
(122
(1)
byc Pu 122 b1221 by (2) + 1/12 b121)
(2) (1)
[1]
8/2
1
8/2
(bIl
(1) (2)
12 bpu (1) bm2 + 921, Hu + bmp2 122))
(2)
12
One simple but useful fact is that || ||, |ل21 0(110))). The reason is that for &s E [K]
| = O(1exx)) = 044 + byz (2) + + (1) + bbu = ((10))2)
Notice that
byu
b1i12 + 721
Mu
1712 + b1221
3333
|22l
|1111
(bpuy (1)
bb112 + m22)
| (Mi
(1) - 1/12 m21)
|122|
| ||
butt
(1)
by/12 + 1/21
(1
||02|||
1-
(1)
+ o(1 - b)
||:5]] ||
|| |
|
buud
-b912 + 1721
|| 112
|| 113
1 1- (1)
1 1
[1 Mi + o(1 - 6)
(98)
||01|
|
Since
|0
|| 20011~11i-)
(1 (2)(() (1 -1212 -02-2222)
(1)
(11 (1) 112)2)
(1 (1-b3) (1-b))((u()) (1 -112 (1() + o(1) (1013)
(99)
We have
bur + o(1) |101
1
(1 - (1)
(2) (111) - (122))2 (1())) o(1) -101)
|
2
1 (1)
||ا,||| Pi
+ o(1 - b)
(4 12) + (14 (2)) (H 1112 1000-(000))
b (1)
10 Pia
1+
+ o(1 -6)
(100)
132 |2
47

---

Published as a conference paper at ICLR 2023
Since for all & [K]. E [2K], (t) 8k)]( o{ [[]1--)]]l bl)l 11. we have wx ارg o(11 - b()),
( (2 (() --(42)
2. 2K. Hence, denote y
we obtain
| 1=
1 1-b b
W3 =
Mu (1 + + t
(1)
(101)
|1²11
Similarly, we can show that
1 1 b (1)
W1
|| 11 (1 +
+ o - b)
(102)
U2
b
14 (1 7) o1 b)
(2)
(103)
|12
b (2)
W/4 =
|1 Pu (1 7) + o1 - b)
(104)
As result,
(w w. )²)
b
Σ
Pa (1 (-1)* + o01 - -))) pM
[ix
aE(C,
(1 -1-1)8n)
|106 20(1) (ue (1-)))111 (-1))8g
Ma (K)
8" 00 -[1 b)2
+ o(1)²
11
|
aE CE/C
(105)
When |0||| = o(1), the bounds
75 and 76
both become trivial so we can focus on the case
where [011 O(1).
(1- 7)
In this case,
I 011),
I O(1). On the other hand, for k [K].
12 1
(po
(
(4())) )3 + (pt 14)
|2
|
(k) + Mix
(10) 33
(42
(Holder Inequality)
4 A| II?
|100k) l|
4||02A 112
minke[K] (10(k) 1
4 |
|
maX [K]
(By 9
408 || & 2
110113
2 0(1)
(106)
Since 1 - 7 and 1 + cannot be both o(1), we have
K
3
(-
1))
2 0(1)
|i
OE (E(C))) k=1
48

---

Published as a conference paper at ICLR 2023
Therefore,
K
13 - (-1)
(w w, (*) = -1 (1+)))))))))00 b)² Σ
(ua
|ix
ac (C.M) k=1
= =1 b)2
(146)) + ) 2 )2 (2)2 )3 (1)
(2
(122 )2 + (14 12 + (ml )2 (Hz )2y3
(107)
By 101 102
(03) (04). [ [tp| 0(1 b) o1). Substituting this result together
with 97 and 107) into 190). we obtain
P(ÿ = nT = =e1)
-(1 o(1)) (1-b)²
4
2exp
(108)
8
01 II
1 IF
2
11 11
2 "1
(10
- 110 119)
Similarly,
PD 1|TT =e2)
(1 6)2
4
$ 2exp
-(1 - o(1))
(109)
8
1 I1 + IR
100 8
(1102 If
110
113)
IR + 110 113)?
Therefore,
(1 bb)
4
Risk(g) < 4 exp
-(1 (o))
0"
(110)
8
10 11 (1 1
110
113
(110 + 00 11))
(1102
110
Taking C4 = 4, we conclude the proof.
K PROOF OF THEOREM
Theorem 3. Suppose the conditions of Corollary hold, where bo is properly small, and suppose that il is bo-correct. Furthermore, we assume for sufficiently large constant Cz, 0" I c 0- s
minke(k] (2 [12. and for a constant ro > 0, mingze Put] 2 ro- Then, there is a constant 02 = (K,, C1, C22 C3, c3,ro) vo) > 0 such that log(oo Ro(k log(inf, (((ski(((( 2 02.
Proof. On one hand, for any k 1st [K], k + k., using exactly the same proof as in Section J.1 can show that when C3 C1.
inf
(IP(
k|mT
ek P(ù 1= kk)
8
2
1
exp
i=1 2(1 (00)2) (V000PPt.. - v Pk-
2
(111)
2
where h; is the true label of node i, gr maxte(n) maX /800PPkk. According to DCBM model and condition (8) da &. Hence take C3 2 V2C, then
inf (Risk(ū)) N max inf = 1//T"* = ex-) ) + P(j = 1'177" = =e)))
E[K]
49

---

Published as a conference paper at ICLR 2023
1 exp -2v2 _
V0+0:PA: 1000;P5- )
max kith E[K] 2
V Pai v P 2
2 exp -22/20
min lo
1000 |1
(112)
Let Bo be the event that i7 is bo-correct. When (Risk(j)) is replaced by the version condi- tioning on Bg, since X and are independent, and Bn E (A), conditioning on Bo or not does not affect the distribution of X. On the other hand, for any k; k² since x does not affect the distribution of A, the distribution of B π = e₁ and A n- = eg* are the same, so their Hellinger distance is still O. Hence, all the proofs in Section Jand above remain unaffected. In other words, one does not gain a lot information from Bo-
On the other hand, notice that proof of Theorem still works conditioning Bg. In other words, there exists constant C > O. such that given By, for any E 10,, with probability 1 simultaneously for < k < K,
(1
log(1/5) |001] 1101l2-min min
| 1|?
((Te) 2h (Tu)) SC C
111
| 11 1111011>
Define 34 = Sh (Tlu). Replacing co by By and replicating the proof of Corollary we can show that
Co c
P(ù + Bo xT" = =kk) S exp
11) min(0", .110 l2)
k=1
Since 0* < min C3 11,, minf0" -10( 111} 2 min c5 Jo, therefore,
K
Co
P(O * k* Bo, n- = -ex) < C
exp
min (1, C3
} 0 11011)
(113)
k=1
Recall that in 20 of Section G show that
3x = vl(( 2 V(ex ex- ) - - -x-)
(114)
By Lemma denote
10ze111
Cs =K=8K² K
VKK K
(115)
|1011
Suppose that C3 < 4. Then, for any vector R*
1 1 3Cs
1 C35 la 1T al
la' 1a
(116)
where recall that in Section define
M( = P P(Ccc + Cha) P
(0) Dapo; = ! ..... M ). and M, (7 = =D
2gio) M0) D
2g(0)
Hence, when by is sufficiently small,
3 z (ex ex- ex-) -ex-)e 2 3
(ex - (e -ex-
M
1
(117)
3
v M0 V M
50

---

Published as a conference paper at ICLR 2023
Define A V110 110 11,1 E [K]. Then,
M Σ Pe Σ PM
K
K
PIP = Σ
X
P
kk
1=1
1=1
K
K
M
X
Pa-
Xp
P
=
Therefore, plugging the above result into 117
we have
M
RK-
1 lk
M k-
Σ PA
3
XPP E Xp
L==
E X PEE XPP - x XPPuPPrnDD
3
E XP X2
EE K
XI
APpp) C K PPI
(118)
Notice that
XPR) K
XPP.. E PPPMPp.1)2
Σ
X2 .k. -
[[E[]]
( PA + Σ X (PHPPe- Pk-i2 [E[K]
(Identification Condition)
Σ
X
(P Par Pu--aPP-a Pa-1)² + X%x (PM - PR Pk-1)2)
IE K]
(Cauchy-Schwaal 2
X2
1
(Pes- Pst Pk-t + Pks - PR Pa-1)
1
+
16 [E
X2
X?
Σ
X
1
(1
+ ) -Pk-1)2
LE K]
X7
X2.
Σ
XP Ps.1)2
minre
minjeiK] LE[K]
=
min
X
Σ
XP(PM 12.1)2
(119)
2 [E[ [E[K]
Substituting 119 into 118). we have
minee[]] X7 EiE(K) XP(Pt) P2-1)2
6
EK XP (P2-))
51

---

Published as a conference paper at ICLR 2023
m X7 Eie(n \/ Pk-1)2
1
(By Condition (8)
2
(120)
6C
(E==1 1))= 17)2
On one hand, by Cauchy-Schwand inequality.
x
110% lf + 10 1l
1
(110
111 110 111)
2
110001
(121)
So
min
X
2 2
min 11000) [E(R]
11009)1))
(E(K]
1 1
(By Condition
max |10(0) 111)²
C2
KE[K]
1
2 _
11011,)2
2
KC2
|1013
(122)
2k²C2
On the other hand,
K
K
X
(10( (1)
112
1100113 (l
1=1
1=1
K
$
1
111
+ Σ 10 111)
||0li
(123)
Plugging 121
122
[23
into 120
we obtain
1
min A2 Σie(K] A7 Pk-1)2
3
6C4
(E Xp)2
2K!C 10112 Die(x] (1Pss PR-1)2
1
2
604
(11017))
EiE(K] (10(0)
[P7 PA-1)2
24K²C/C
110177
minie[K] [10(0) ||2 ELEKKI II(PPI VP
24K²C/C
1101( + VP--i)
maxie[K] 11000 1/2 ΣiE(K] |000) (1 - PP-1)²
(By 9 min
T0)
kef
24K=C4C2
1101122/70
100 Σie(K] 11000)
(I(PPr - PP-r122
RCC
24
101222/ro
ΣiEK]
11 VPk-1)2
48 4T
||0112
(124)
Substituting 112 into 113), we obtain
P(ÿ # ka' Bo, x²" = - ) < Σ
K
cxp
Co
min
f 1,30010011
1
c
C3
k=1
52

---

Published as a conference paper at ICLR 2023
k S
K
exp
- C2B²
Σ
|100) 11 [11(VP PM v Pw-1)²)
(125)
k=1
1=1
where Cs = Co min Co BBokkic0c = min
[1, C5
Co
As result,
K
Risk (5)
P(ù + h: BB, x== = ex-)
CK2
CK2
k==1
K
K
K
exp
-C30
Σ
11000)
[iVPPP PM PP.i)))
CK2
koml
k=
1=1
C58 Σ
11010
PPi v PP-i)2)
exp
k=
K Σ
max exp Ai [[K]
-C3g0
110 - PA--1)))
exp -C500
min k
1001| v P
(126)
Comparing 112 and 126 have
log( 1 20
Risk Bo)) log(inf, (Risk(
log(2) CsI
(127)
log(2) + 2V21
where I = 8" ming [[K] K |1000 [li(VPM / P denotes the efficient information in the data.
Notice that since I 2 0, when Cs 2 2,2
log(2)+C,Z 1og(2)+2V2Z
2 1; when Cs S 2v2,
log (2)+ 1og(2)+2v3)
2
(og(2) 200 +C4I C. 2 1og(2)+2v2I
Therefore,
log( 20K2 Risk (o))
log(2) + C&I
Cs
log(inf, (Risk(ū))) 2 (2) + 22/2 2 min 2/2
(128)
Co Take ह2 min 2/2' 20K2 J. Then o2 only depends on K, C1, C22 C3, c3, ro (recall that both Co and co only depend on K, C1, C2, Ca, C3 To. and = 2), and
log( Bo)) log(inf (Risk(j)))
2 log( 2 Risk Bo))
Ca 2/2
log(inf (Risk (7))) (Risk(ū))) 2 min (1,
} 2 8z
(129)
This concludes our proof.
L PROOF OF THEOREM 4
L. PROOF THEOREM
Theorem 4. Consider the DCBM model where 8 hold. We apply SCORE+ obtain T2g and plug it into the above algorithm. As n - co, suppose for some constant qo > 0, min 0g 2 qu max 0r Ba Bull Z qu Ilo((n), 3 [ | mingeu 0, oo, and /3 [0]]]] min ( [11) co.
Then, TV Eieu P(O k.) - O, the in- in-saelle classification algorithm in section 3 iis consistent.
53

---

Published as a conference paper at ICLR 2023
Proof. Let i" arg max,eu P(ù, + kz). Then
Σ KEW
P(ús
ks)
s P(0-- o ki-)
U
Notice that the assumptions of theorem dirrecly imply the assumptions of Corollary 2 when taking i" as the new node. Hence, regard i* as the new node and leveraging on Corollary we have
P(ù # kis)) -
Therefore,
Σ
P(u k2) +
U
REU
In other words, the in-sample classification algorithm in section i consistent.
L.2 PROOF THEERRM 5
Theorem 5, Suppose the conditions of Corollary D where bo is properly small, and suppose that Mun is bo-correct for all i E U. Furthermore, we assume for sufficiently large constant C3.
maXieu 0, S 1.
C3' maxieu 0g < min (2 11, log([<() < C35% minjeu 6, and for constant ro > 0, mink Pke 2 ro. Then, there is constant ē21 ह2 (K, C1, C2, C2, C3, ro) O
such that [- log((2) Riskins (t)) log(inf; (Riskans (7) 2 821. so the in-sample classification
algorithm in section 3 is efficient.
Proof. For U. define individual risk Risk(ū:) EmeE(K] P(u: + k* n. ex-). Then the in-sample risk Riskine (5)
[7 Eisu Risk((:).
The minimizer of Riskins (1) may not exist, so we define j(() to be an approximate minimizer such that Risk (f ()) < 2 inff (Risk:ns(i) By the definition of infimum, such z( always exists as long as g Riskin (ύ)} > O. Notice that for any i E U, inf g [Riskins (ū)} 2 infg, Ter {Risk (ū.)). (12). know that inf (Risk(j:)) 0. not taking [M]]
Regarding node i as the new node and leveraging Hence, inf, (Riskins (ū)) 2 infy, [ि7] (Risk(ū.)) 0 (note that here), and (()) is well-defined.
of Let i" arg max Risk(D.). and let k* be the true label of t" Regard [m]][t*} as the existing
nodes in the network and i* as the new node. By (112) and (126), we have
1
log(
20K² Risk((:)) 2 log(2) + CsI
(130)
log( (Risk (i.()))
inf log( (Risk (ū) )}} < log(2) 22,2I.
(131)
where I,- 0,- min 1-1 efficient information in the data for classifying node i*
||@0| (vPP: VPw-i)2 01- ?2) denotes the
As result, have
- log( ZCK= Risk in (i))
log( 1 Risk (0))
2 log( Riskin (f(11))
log(inf, y (Riskins(())
log( L0O= lil Eieu Risk(ūt))
-log(zu) Eiey Risk(ū)) (")
54

---

Published as a conference paper at ICLR 2023
log(
Risk (i+.) ))
ICK?
log(
1 (2t4]
Risk (z),-)
log(4) + CRII-
(By 130
131
2
(132)
log (4) 2V.2 log(((())
Notice that
I+-
-, min
Σ |1000) 11(1/M -PK--)2 -1,- PPK..)9
E(K)
01- min E(K)
(110(*)) 11( Pks PPxxx) + -10(05) [//(VP PA ) -0s V P
(By identification condition that PRL = P =1
0,- min [(K]
((I10()) + 11006"))| 0,+)(1 P
(The true label of node i" is k*)
0:- min k
(I10(())) |1 VP
(133)
By assumption 8 for any [K].
(1 p)
(1 v px-x))
(1 + / PP
(2 2Ppxk)2 )²
4(1 + v2
(By identification condition that Pis PE 1)
(PRE + Pk* 2Ph-n)²
4(1 + P)
(lex ex- - PP(e ex-))2
4(1 + v p2
((Amin (P)llles Cx. 112)2
4(1 + 22
(134)
VC12
By assumption 9 for any [K]
||0(0) 11 > min
|| lla
E
|1000)
> C2 ky k(K]
max
||00/3
KC2 k(
KC2 |10111
(135)
From the assumption, log((()) < Ca 0|1 minseu 0:. Plugging 134
135
into
133
we obtain
I4 2 0,-
min
KC2(1 + VOT)² 1101))
1z)
k[K]
3010011 min 0, xell
KC2(1 + vT)²
55

---

Published as a conference paper at ICLR 2023
KC2Ca(1 (osc
log (og(
(136)
In other words,
log((U() S KC2Ca(1+ I.
(137)
Substituting 137
into 132
we have
log( 4CK2 Riskine (0))
log(4) + CgI..
(138)
log(inf y (Risk (7)))
log(4) (4) - (2V2+ +C VC)32
Similar to the proof of Theorem notice that since I,- 2 0, when Cg 2 2 (C:C
log(4)+ CCI,
log(4) + (2v2+ +C,C,(1+VC)))1)) 21
(139)
; when C8 2 KC2C3(1 + V
log(4) + CsIz-
log(4) 2/2+KC. + CzI
+ (202+ VC)))I= log(4) + (2v2 + +
C3
(140)
2/2 + KC2Cs(1 + V
Therefore,
log( TCK= Riskins (i))
log(4) (4) CsI
log(inf [Riskins (7)})
log(4) (2V2 + KC2Cs(1 + V
Cs
2 minf1, 2 KC
(141)
Take ε21 min(L, 222+ Cssss _0K=]. Then ह2 only depends on K, C1, C2, C3, co (recall that both Cp and co only depend on K, C1, C22 Cz, C3, Fo. and C 2), and
log (21 Riskins (f))
log(Tck< ICKT Riskins (i))
2 log(inf &f [Riskino (7)})
bog(infg) Riskins (i))
Cs
min(1, 2/2 + KC,C,(1+ V
N 121
(142)
This concludes proof.
56


Reviews:
[{"review_id": "YEC0rSd61lV", "reviewer": "Reviewer_VCTg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a semi-supervised community detection method based on the idea that \"a community is a group of structurally equivalent nodes\". To this end, the authors propose structural similarity metrics, which enable the model to handle non-assortative networks and degree heterogeneity. Theoretical guarantees are also provided to support the proposed approach.", "summary_of_the_review": "This paper proposes a well-grounded solution to an interesting problem with theoretical guarantees. Though I appreciate this work, I have some reservations about the empirical experiments. I look forward to discussing with the authors to revisit my review and/or score. :)", "strength_and_weaknesses": "Strengths:\n+ the proposed approach is well motivated\n+ solid theoretical analysis\n\nWeaknesses:\n- major issues in the empirical experiments on real-world networks\n- minor issues such as citation format and ethics statement", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VVY8GO-MeI", "reviewer": "Reviewer_1PMk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the a semi-supervised community detection problem on a degree-corrected stochastic block model. Given some known labels of the nodes in the network, the authors propose a method to classified the new node based on cosine similarity with the in-sample data. ", "summary_of_the_review": "This paper is well written. However, the proposed method is too simple and the theoretical result cannot support the output of the algorithm can achieve the optimal error rate. ", "strength_and_weaknesses": "Strength\n\nThis paper is easy to read. I can understand the algorithm and theorems without any trouble. \n\nWeaknesses\n\n1. The problem can be easily solved by existing algorithms with slight modification. For example, we can run the community detection algorithm again on the whole network. If we are only allowed to apply local refinement on the network to reduce computational complexity, the following steps will also work. \n\n(i) Apply prototypical refinement, e.g., Algorithm 2 of Gao et al. (2018), with known labels, then we can assign labels to nodes in $\\mathcal U$.\n\n(ii) Now we have labels for all nodes. we update the labels for every node by applying the same refinement procedure with initial labels for all node. \n\nNote that the reason we update the labels in step (ii) is to use the information in $A_{\\mathcal U\\mathcal U}$. The method in Gao et al. (2018) may not be applied to non-assortative block models, but it is not hard to replace their procedure by a local likelihood ratio classifier. \n\n2. The authors propose a method based on the cosine distance. This classifier may be equivalent to likelihood ratio classifier. If this is the case, it should achieve the information theoretical lower bound, but the authors fail to show this in Lemma 2. It is claimed in the paper that \"we bound the total variation distance by the Hellinger distance (the total variation distance is hard to analyze directly)\". It can be shown that the exponent of total variation distance and Hellinger distance are the same up to a $1+o(1)$ factor. See [1] for details. If the connectivity matrix is more general, you can use Chernoff information to bound the total variation distance. See Section 11 of [2] for more details. \n\n[1] Zhang, Anderson Y., and Harrison H. Zhou. \"Minimax rates of community detection in stochastic block models.\" The Annals of Statistics 44.5 (2016): 2252-2280.\n\n[2] Thomas, M. T. C. A. J., and A. Thomas Joy. Elements of information theory. Wiley-Interscience, 2006.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "42KoNxRifB", "reviewer": "Reviewer_wECN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors created a semi-supervised approach for the crucial and challenging subject of community detection. \nTo solve the problem, they are facing the following challenges: (1) Non-assortative communities exist in real networks; (2) Degree heterogeneity exists in the network; (3) Optimization-based techniques may obtain local minima; and (4) No existing solution offers theoretical assurances. \nTheir method can give the predicted labels of unlabeled nodes in a graph based on the structural similarity metric between the new node and the observed labeled communities. In this work, their contributions include (1)Their new semi-supervised method models degree heterogeneity; (2) The authors' method allows for both assortative and non-assortative communities; (3) The authors designed a structural similar metric to measure the similarity between a new node and the other observed communities. (4) They first showed the theoretical guarantees of their method.\nTheir efforts do aid in the advancement of community label prediction.", "summary_of_the_review": "Based on the innovations in their work as well as their strengths and weaknesses. Their work is, in my opinion, above the standard for acceptance. But it falls short of becoming strongly accepted.", "strength_and_weaknesses": "Strength:\n(1) They propose a fast method.\n(2) Their method is more generalized because their semi-supervised method models degree heterogeneity and can handle both assortative and non-assortative communities.\n(3) The authors first offer theoretical guarantees on the community detection problems.\n\nWeaknesses:\n(1) In the Introduction part, The authors suppose that \"the nodes partition into K non-overlapping communities\". It could be clearer if they can explain how to process the unlabeled nodes. It means it is not clear how to decide the unlabeled nodes to which community C_i. I believe the way, how to initiate the unlabeled nodes, may influence their equation (4) which needs to consider the labeled and unlabeled nodes in each community.\n(2) On page 3, if we look at equation (3), it would be clearer if the authors can add a notation on \"𝛳/i\" and \"𝛳/j\".\n(3) The authors claimed that their method is fast. However, they didn't give an analysis of time complexity or a comparison of running time. I think it would be better if the authors can give a comparison of running time.\n(4)It would be clearer if the authors can offer a pseudo code or a figure of their algorithm.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "41RWk_NzYV", "reviewer": "Reviewer_Rg2A", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the semi-supervised community detection problem. In particular, they consider the degree-corrected block model (DCBM) where each node belongs to one of K communities and has a degree parameter. Then, the edges are generated between nodes according to the degree parameter of the two nodes and community connection probability.  The problem is given the label of a subset of nodes, to find the label of the remaining nodes. They propose two new algorithms Anglemin and Anglemin+ for this problem. They provide a misclassification error bound for their algorithm and show their algorithm is nearly optimal by comparing it with the information-theoretical lower bound. Finally, their experimental results show their algorithms achieve smaller classification errors than the unsupervised method.", "summary_of_the_review": "This paper provides a solid contribution to a semi-supervised community detection problem, They provide theoretical guarantees and convincing experimental results. Thus, I tend to accept this paper.", "strength_and_weaknesses": "Strengths:\n1. This paper considers a new semi-supervised community detection problem, which can be used in many applications with partially observed labeled data. \n2. This paper provides an explicit misclassification error bound for the proposed algorithm. \n\nWeaknesses:\n(Minors): The label for equations (8),(9), and (10) seems unmatched with the lemmas and theorems below. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster