LEARNING GUARANTEES FOR GRAPH CONVOLUTIONAL NETWORKS ON THE STOCHASTIC BLOCK MODEL
Authors: Wei Lu
Venue: ICLR 2022 Poster (2022)

Abstract: An abundance of neural network models and algorithms for diverse tasks on graphs have been developed in the past five years. However, very few provable guarantees have been available for the performance of graph neural network models. This state of affairs is in contrast with the steady progress on the theoretical underpinnings of traditional dense and convolutional neural networks. In this paper we present the first provable guarantees for one of the best-studied families of graph neural network models, Graph Convolutional Networks (GCNs), for semi- supervised community detection tasks. We show that with high probability over the initialization and training data, a GCN will efficiently learn to detect communities on graphs drawn from a stochastic block model. Our proof relies on a fine-grained analysis of the training dynamics in order to overcome the complexity of a non-convex optimization landscape with many poorly-performing local minima.

Published as a conference paper at ICLR 2022
LEARNING GUARANTEES FOR GRAPH CONVOLU- TIONAL NETWORKS ON THE STOCHASTIC BLOCK MODEL
Wei Department of Mathematics Brandeis University Waltham, MA 02453, USA seeeibbrande.e is s. edu
ABSTRACT
An abundance of neural network models and algorithms for diverse tasks on graphs have been developed in the past five years. However, very few provable guarantees have been available for the performance of graph neural network models. This state of affairs is in contrast with the steady progress on the theoretical underpinnings of traditional dense and convolutional neural networks. In this paper we present the first provable guarantees for one of the best-studied families of graph neural network models, Graph Convolutional Networks (GCNs), for semi- supervised community detection tasks. We show that with high probability over the initialization and training data, GCN will efficiently learn to detect communities on graphs drawn from stochastic block model. Our proof relies on a fine-graines analysis of the training dynamics in order to overcome the complexity of non- convex optimization landscape with many porllypperforming local minima.
INTRODUCTION
There presently large gap between what can be accomplished in practice using deep learning, and what can be satisfactorily explained and predicted by the theory of deep learning. Nevertheless, the past several years have seen substantial developments in the theory of deep learning (Ge et al. 2017]
Brutzkus & Globerson 2017 Zhang al. 2019a; Goel et al. 2020 Chen al. 2020a).
One factor contributing to the gap between the theory and practice of traditional NNs is that real- world data sets tend to have complex structure that is difficult to capture with formal definitions. For example, popular image classification models are capable of memorizing arbitrary data (Zhang et al.) 2016), and yet they exhibit astonishing generalization performance accurately-labeled natural images. Hence, any rigorous proof the observed generalization performance of deep learning models on image classification tasks will necessarily require assumptions about the data that sharp enough to separate random inputs from natural images. Because of the difficulty of giving an adequate characterization of real-world data, much of the recent progress in deep learning theory has instead focused on proving results using very simple (e.g. Gaussian) input distributions or in distribution- free settings (Ge et al. 2017 Brutzkus & Globerson, 2017 Zhang al. 2019a| Vempala
& Wilmes 2019).
Compared to traditional feed-forwarde (dense, convolutional, etc.) NNs, the theory of graph neural networks (GNNs) is still in its infancy. On the other hand, it appears substantially easier to give plausible descriptions of the combinatorial structure of real-world graph data sets than, e.g., to characterize the distribution of natural images (Drobyshevskiy & Turdakov 2019). We therefore believe that GNNs offer a natural setting for developing provable guarantees that are able to capture the power of deep learning on real-world datasets. In this paper, contribute to that goal by giving the first rigorous guarantees of efficient semi- suni-supervised learning of stochastic block models via GNN.

---

Published as a conference paper at ICLR 2022
1.1 GRAPH NEURAL NETWORKS
Many natural datasets for diverse machine learning problems have a graph structure, including social networks, molecular structures, and transit networks. In order to efficiently exploit such combinatorial structure, variety of GNN models have been proposed, tuned for different kinds of tasks. A number of taxonomies of GNN models have been proposed (Zhou et al. 2018; Wu et al. [02T]; one of the most essential differences between different GNN models is whether they meant to label the graph as a whole, or to label individual components of the graph, particularly vertices.
From theoretical perspective, the best understood tasks for GNNs concern labeling the graph as a whole, for example for the task of classifying a graph by its isomorphism type (Sato) 2020). In particular, it has been established that many GNN models are of comparable power to various versions of the Neisfeiler-Lemaa hierarchy Xu et al. 2018 Morris et al. 2019).
Some progress has also been made on the theory of GNNs for vertex-labeling tasks. Recent works by Sato et al. describe the representational power of certain GNN models for tasks such as computing minimum vertex covers (Sato et al. 2019). Garg et al. also give bounds on the representational power of GNN models, as well as using Rademacher bounds to estimate the generalization ability of GNNs Garg et al.) 2020).
Our results concern the task of semi-supervised community detection. In this problem, each vertex belongs to one community, and some subset of the vertices are labeled according to their community membership. The task is to classify the community membership of the remaining vertices. This task has been one of the most intensively studied problems in the GNN literature, but there have not yet been any provable guarantees on the performance of proposed models.
We study (spatial-based) graph convolutional models similar to the GCN model proposed in Kipt & Welling 2017). A single layer of such model computes weights at each node by aggregating the weights at neighboring nodes and applying an activation function with learned parameters, e.g.. linear map followed by ReLU. Many variations on this theme. including various sophisticated training regimes, have been proposed (Chen et al. 2017] 7 Gao et al.) 2018 Li et al. 2018 Zhang et al. 2019b Chen et al., 2018), but provable guarantees have been available for the performance of such models on natural data distributions, until the present work.
MAIN RESULTS
One motivation for GNNs as a target for progress in deep learning theory is that there are well-studied graph distributions that plausibly capture some of the structure of real-world data (Drobyshevskiy & Turdakov] 2019). For example, even fairly simple preferential attachment models plausibly capture some of the essential structure of the web (Kumar al.) 2000). Other graph models naturally capture community structures, the simplest of which is the Stochastic Block Model (SBM) (Holland et al., 1983). graph is sampled from a SBM by first partitioning vertices into communities (with fixed or random sizes). Two vertices connected with probability p if they belong to the same community and probability q if they belong to different communities.
In this paper, we consider the case of an SBM with two equal-sized communities in which vertices have label 0 and respectively. We denote the label of vertex x by ((x) E 10. The graphs parameterized SBM(n, p, q) where is the number of vertices, p is the probability of an intra-community connection, and y is the probability of a cross-community connection. We allow
vary (but will require it to be sufficiently large), while p and q of the form p a log" and
q = blog" n for some fixed constants a > b. In the semi-supervised setting, the community labels of some portion of the labels are revealed. We assume the label of each vertex is revealed independently with probability X. The input-layer features at vertex x is (0, 0) if its label is not revealed, (1, 0) if its label is revealed to be O, and (0, 1) if its label is revealed to be 1.
Assumption 2.1 (Sparse Stochastic Block Model). The probabilities of intra and cross-community connections are p
a logg and q
b blog where a > b are constants.
7
Weeifeilerr-Lemaa hierarchy is a polynomial-time iterative algorithm which provides necessary but insufficient condition for graph isoorpphssm
2

---

Published as a conference paper at ICLR 2022
We study the problem of recovering the communities from such graphs using GNN models. Of course, recovering the communities of an SBM graph has been well-studied and its computational complexity is fully understood in most cases (Abbe & Sandon 2015 Kawamoto et al. 2019). SBM
models are therefore a natural test-case for understanding the power of GNN models for learning community structure, and experimental studies have been done in this setting (Chen al.) 2020b
Yadav et al. 2019). (Abbe et al. 2014) shows a sharp threshold in the task of community recovery:
(VP V9) log n
V2. This threshold clearly holds for our case (at sufficiently large values of n), since p = allog" n models. Rather it's showing that (multi-layer) GCNs solve the classification problem, which is very much not trivial (it is non-convex, and the training loss curve is empirically non- monotonic).
blog"n and a > b. The contribution here is not to learn the community n
Our GNN models will be trained on a graph or several graphs generated by the SBM(n. p. g) model, and seek to understand their accuracy on arbitrary (n,(n, P. 9) graphs not necessarily in the training set but with the same parameters a, determining p and (with allowed to vary).
In particular, we study spatial- graph convolutional models along the lines of the Graph Convolutional Networks (GCN) introduced in (Kipf & Welling (017). Each layer of the model computes a feature vector at every vertex of an input graph based on features of nearby vertices the previous layer. A typical layer-wise update rule is of the form
X
o (Ax(()
where
Å is suitably-normalized adjacency matrix of shape n x n where n is the number of vertices. Usually Á includes self-loops.
(*) gives the feature vector in the k-th layer at each vertex as a matrix of shape n X mk- where my is the number of features in layer l.
o is an activation function, such as the ReLU.
(k))) are the trainable weights in the k-th layer, matrix of shape ma X m
In our version of this model, we define À F(ttoj A, where À = A A A the adjacency matrix of given graph, and / the identity matrix. For the given SBM(n, p. q), a randomly selected vertex has 3/2 (pp + q) neighbors in expectation, so Å obtained by normalizing each row of A + I with the average size of neighborhood. Since very deep GCN models seem to provide little empirical benefit (Li et al. 2018), we use single hidden layer with a softmax output layer. Furthermore, we introduce a bias term B at the second layer. So the model has the following form:
S(x,) softmax (Áœ( ÁX W (1)) w(1) + B)
sootmax n² q)² Ao (AXW(()) ) +B),
4
where X is the input feature of the graph and W(0), W(1) and B are trainable parameters. Let h denote the number of hidden features, which equals the number of columns of W(") and the number of rows of W(!.
We define the accuracy of the model as the probability of predicting correctly the label of a single vertex in randomly generated SBM(n, p, graph where the label of each vertex is revealed with probability X. We can now state our main result.
Theorem 2.2. For any >> O and 8 > O, given a GCN model with 1/2 S h S n hidden features and with parameters initialized independently from N(0, 1), if training graphs are sampled from SBM(n, P, q) with n 2 max(S(( {)2 (2)) and the label of each vertex revealed with probability X. and if the model is trained by coordinate descent for k- = Ollo log }) epochs, then with probability
2 1 8, the model achieves accuracy 2 1- 4e.
Remark. We treat À as constants, so it is omitted in the big O and Ω notation in the sampling and training complexity.
We emphasize that the novelty of this theorem is not in learning two-class SBM models such; this is a long-solved problem. Instead, this is the first proof of efficient learning for a GCN on semi-supervised community detection tasks using a natural family of random graph models.
3

---

Published as a conference paper at ICLR 2022
3 PRELIMINARIES
In this section, we first introduce notations (a table of notations is also shown in the appendix for readers' convenience) and some interpretations. Then introduce the structure of the paper. Given vertex y, denote the row of AX corresponding to y (ty, tf). so thj and ti give the numbers of neighbors of y (including perhaps y itself) with revealed labels in class O and class respectively. Let
81
B
bo
b1 b
82
bo
a1 aj
a 02
ah d/p)
way=
B
Bh
bo
81
Then anly + aff < i < h gives h features of vertex y in the hidden layer. The inner product of the y-th row of ((XW(()) and the columns of W(1) gives weighted sums of features of y El Beolarl + a44)) and E 3'o(a,l + af1)), where & represents the ReLU function.
Given a vertex æ, the row of Ás(ÁxW corresponding to x is denoted by fi()) and is of the form
Σ DEG
1ly x] Σ Biolatt
4 "²(p + q)²
Σ
1ly
( 9)²
yEG
where 1/ ~ x] is equal to 1 if and x are connected, 0 otherwise. Denote
43:
4,,
fo(x) = (p q)2
1l mojoaaatt f1()) n² 9)2
E xlo
yEG
PEG
so fo(x) = -t 1b(x)) and [1xx) = f((x).
Denote 9, (z) = (x) by.j 1, where (0o(#), 91 (x:) represents the logit of the model
corresponding to x. Denote A(x) := : go(x) gi (z). In order to make correct predictions, we need (zz) 0 when ((x) 0 and A(x) < 0 when ((x) =
The bias term B is useful in our analysis because its derivative controls how imbalanced the current loss is between the classes. In training consider the cross-entropy loss denoted as L, and have
OL
aL ab,
- 1 ([())(()) 0J E 1]),
E
=
E
abg
exp (g ((i))
where Z exp (g) (g) (xx)- Z can be regarded measure of wrong prediction: the numerator
the exponential of the output corresponding the wrong label and the denominator is normalizer. It is easy to see that Z > z if the prediction is wrong; Z < if prediction is correct. When E @L]] 0, the model's loss is balanced in the sense of that E [(Z)((z)) = 0] E[Z]((z)) 1]] 0. In order to have balanced performance in every epoch, we train the model through coordinate descent instead of conventional gradient descent. Specifically, in each epoch we first update bo and b until E 0L is smaller than some threshold. Then we update the other parameters.
In order to make learning guarantee of the model, we need high probability estimation of (xx). In Section 4 we show that A (x)) is concentrated at one of two values, denoted by μl and μ41 for ((x) = 0 and respectively. The proof depends on different parameter regimes of hidden neurons. Furthermore, to avoid the overlap between the concentration range of A(r), we also show the separation between A4 and fr. In Section we analyze the dynamics of hidden neurons throughout training to show that the concentration and separation improve at a controlled rate. Based on this information, in Section 6 we prove the main theorem. Section 7 shows some experimental results to verify our theory. The paper ends with future directions in Section g
4 CONCENTRATION AND SEPARATION OF OUTPUT
In this section we show that A(x) is concentrated at A4n and μl and their separation. The difference of the logits is
4

---

Published as a conference paper at ICLR 2022
A A - 90(x)) fo())
f1(0) + bo b1 Σ (x( + bo b1.
where
Ax(x) fo(x) [((+) 4(3; -30 (p + q)²
Σ Ily 2|o(ant + of1
VEG
For brevity, we write (x) as A and (r()) A, In order to estimate A, we need to estimate each A,, issiiii isish. h.
We denote the high probability estimate of A as lo and μ4i for {(x) 0 and 1 respectively. Our fine-grained analysis of the dynamics of coordinate descent on GCNs relies on a classification of neurons into three families based the sign and scale of the parameters: "good type", "bad type" and "harmless type". The names also indicate whether the neuron has positive contribution to the value of μi /41- We show that "good type" neuron makes positive contribution; the contribution of "bad type" neuron is negative but lower bounded; "harmless type" neuron's 's contribution is non negative (see Corollary A.4 and the remark following it). We will specifically describe parameter regime of each type in the following subsections. We analyze the dynamics of these types throughout coordinate descent the next section. First we give some definitions.
Definition 1. For 1 S S h, we call (a;, a4, Br, 3) the i-th neuron of the model, where (a;; af) is the i-th column of W(0), (B,, 87) is the i-th row of W(),
Definition 2. We say that the i-th neuron is order-aligned if (a; a) - -3) > 0, otherwise we say is order-misaligned.
4.1 CLASSIFICATION OF NEURON PARAMETER REGIMES
We say the i-th neuron is of "good type" if it satisfies either G1 symmetric case obtained by switching a; with af and 3, with B For brevity, we only consider the cases that > a4. This applies to the "bad" and "harmless" types below as well). Neurons in this type are order-aligned and both ag and a are positive or the ratio between ag and of is large enough.
G2
below. (There is also the
a > a
0 and 3 $
(G1)
RI
0₂ 0 d
and 3 > 0
(G2)
We say the i-th neuron is of "bad type" if it satisfies either B are order-misaligned and as of are either both positive or have the opposite signs.
13
B3
Neurons in this type
0: a 0 and 3 8
(B,)
q (1 + log $ n) and 3 < 0
a, 0 di
(B₂)
p
a;
0
< ( log n)
(Bs)
p
We say that the i-th neuron is of "harmless type" it satisfies either
H or H2
a4 0
of.
a
E 2 log n), 1] and B, > 8
(H1)
0, S 0 and of < 0
(H₂)
4.2 CONCENTRATION AND SEPARATION
Theorem 4.1. If the i-th neuron is of goood type" satisfying G or of "bad type" satisfying then for E(x) = 0:
B
A| 1(3, 81
112 + 92)a; + 2pqafll s
(p + q)²
(as a() -3,)0(log n)]((()) = 2
1 1 1
5

---

Published as a conference paper at ICLR 2022
for {(x) = 1:
1(3
P|
[2pqa; + (v² + +g)aall -
(p 9)²
(as a -B)00oo33 n))((())
1|
Similar concentration hold for neurons satisfying rype."
G2
B2 and
Ba
and for neurons of "harmless
We apply the method bounded differences to show the concentration. The details are shown the appendix.
Given the concentration A, for each type of neurons, we estimate the concentration of the output A = > A, + bo b₁. For the i-th neuron, we denote the high-probability estimate of A; given in the statement of Theorem 4.1 as mù when f(x) and mi when {(x) = 1. By union bound, we have the following corollary.
Corollary 4.2. Given a vertex with label unrevealed, we have
PI - أبن - 81((x) = 5 1 0 - n
(3)
where
mf) + bu b1, j 0,1
8 Σ aas dl113, Ol1O n).
For any 0, we require the probability of concentration in 3 to be at least 1 - ē, where ē = o(e). we choose = 2 then we set ( e², i.en (t)). based on this condition.
Our following analysis will be
From Theorem 4.1
we have the following result about the value of m/ m
Corollary 4.3.
If the i-th neuron is of "good type" and satisfies
G then
mà mi a/a; afl1B: B/1
9
If the i-th neuron is of "bad type" and satisfies (B then
9 2
mb - mi = -X|a; a3l13 - B11
p
If the i-th neuron is of "harmless type" and satisfies H then
m m = x|3; A13:-611lpay + ga. + q)2
9
Similar results for neurons satisfying G2 the proof. Remark.
B2
B3
and 111 are stated in the appendix, along with
As we can see from Corollary 4.3 the value mb - mi is positive for "good type" neurons, non-negative for "harmless type" neurons and may be negative (but lower bounded) for "bad type" neurons. Since positive values of mb m decrease the loss the model, this explains the names for the types of neurons.
mb m4 is proportional of the parameters a; af, 8r, B/. Using our understanding of these dynamics, in Theorem 6.2 we present a refined result about the separation of output which only depends on the initialization of parameters.
0 B/]- In the next section, analyze the dynamics
Let e := μ4 μl = Σh (mb mf). By the two corollaries above, we have = o(Ic)). The balanced loss guaranteed by the bias term and the coordinate descent scheme ensure that μl = ((c) and μr 2(c). It then follows that if the loss is sufficiently small, both Ho and μ4 have correct sign. i.e. Mi > 0 > M1- (Otherwise, due to concentration of the output, the model makes wrong prediction and the loss is large). So we will eventually have 8 o(H)) and ă o((p1)).

---

Published as a conference paper at ICLR 2022
5 DYNAMICS OF PARAMETERS
In this section, we describe the dynamics of each type neurons through coordinate descent, which can be visualized in the following figure in which the arrows indicate movement between types that can happen with non-negligible probability.
good type
harmless type
bad type
Figure 1: Dynamics of hidden neurons
There are two noteworthy points from this figure. First, "good type" parameters are preserved under coordinate descent. Second, there are no arrows coming into "bad type" except from itself.
These dynamics are proved by estimating the gradient with respect to the loss function for each type of neuron. Because the non-linearity of the activation, we rely heavily on the concentration result proved above to get tight estimates. Without these concentration results, even estimating the sign of the gradient seems difficult. The proof and experiments about the dynamics of hidden neurons are deferred to the appendix.
LEARNING GUARANTEE
In this section, we prove our main result which states that with high probability a trained GCN can detect communities SBM with any desired accuracy. The proof is based on the following theorem which shows that if μu and μ1 are separated enough, then the model achieves high accuracy.
Theorem 6.1. Vr > provided that the difference between Ni and μr is large enough: 3. if [ (66)) < 1. then PIA < 0l((z) 0j PPA 0l((z)
a(- where a (z) = 1/(1 exp (-)) represents the sigmoid function.
4e,
Next we show that the model can achieve such separation between μ4 and μr through coordinate descent. In order to make constant update of parameters every epoch, set an adaptive learning rate 7/& k where (k) is the value of Z at the k-th epoch. We first refine Corollary 4.3 about
the separation of output for each type of neuron (m² m²) using the dynamics of parameters.
Theorem 6.2 (separation of output). Let mi and m be defined in Section train the model for
epochs by the defined coordinate descent with adaptive learning rate Tp 2
if the i-th neuron is of "good type", then
p p-9
'011011
(1
V2X 1+
mig m
A B
p
8
p + q
if the i-th neuron is of "bad type", ", then
m/ - (A4)) (B(0))
Ap(p g)
(p + 9)2
if the i-th neuron is of "harmless type". then m m 2
7

---

Published as a conference paper at ICLR 2022
(0) where A 0;
(0) 0i B 3,00 1,
Next we present a result about initialization, which shows that with high probability, there are enough "good type" neurons and parameters have appropriate scale.
Lemma 6.3. Suppose all parameters in W and W are initialized independently following
standard normal distribution. Then the number bg of neurons initialized as "good type" satisfies Flhg 2 [] 2 exe 61). Furthermore,
P aa + i=1
s 5hh] 11221-00
1
P
Σ
h |a.-c;118--112
2 1 -
80
the 5-th intzialarrd good type
Now we can prove the final result.
Proof of Theorem 2.2 First we show that if the loss E is small enough, the model achieves desired accuracy. Indeed, if E / 2c, since
E|Z]- = Z pred is wrong]|p(pred wrong] [Bng]++[22 +B pred is correct Correc|]Pppred Plpred is correct] z 2 Plppedd is wrong],
we have Pspred is wrong] S 4r, i.e., P(pred is correct]
4c.
Otherwise, E
[ 2 2c, since Z _ (E[Z]((2) = 0] + [[Z]((=) 1]). we have E[Z]((=) =
+ (]
2 4e. On the other hand, E Lab || implies that [[[Z][(=) 0, E[Z(((=)
1] < 2e.
By Theorem 6.2
(mg mi)
Σ
(mg
m2)
Σ
(m) m))
(mb mm)
11
1=1
"pod"
head
"e"harlless"
p 9
2
V2X
p 9
2 2k
Σ
A
Ap(p 9)
Σ (( + 13)
2
-k
2
+
(p + 9)2
"E"
"E"bal"
By Lemma 6.3 with probability
2 2 21-0(1)
Σ
A (0)
B(U)
h
Σ ((4(0)) + (B: < 5h.
80
VE" "g"godd"
Since h 2 1 8. then with probability 2 -, 6,
A
9
2
1+ V2A p 1 9
(p=
2k
- 5dp(p - 9) (p + 9)2
Po - 14 2 h
(p+g)
160
8
2 (1 + C²)
-Ckk),
(4)
where C1, C2 and C3 are constants determined by p. q and X.
By Theorem 6.1 if 4 > 2oo 2 (then a--te-1 2 W ) then the model achieves accuracy 2 1 4e.
It's sufficient to have
C1(1 C2k: > 2 log 2 7
ie. k = Olog log ))
EXPERIMENTS
We show some experiments verifying Theorem 2.2 In particular, our experiments demonstrate that accuracy increases with n, the probability of high-accuracy models increases with h, and coordinate descent is able to recovery high-accuracy models the sparse regime of Assumption [21] Additional plots demonstrating the dynamics of hidden neurons with their ratios and differences can be seen in the appendix.
8

---

Published as a conference paper at ICLR 2022
10
Experiment 1 In this experiment, plot the an estimate of the accuracy versus epoch for varying The parameters p, 9 of SBM follow Assumption 2.1 where we choose = 1.0 and b 0.7. We set h 20, À 0.3 and 40 independent experiments for n = 250, 500 and 1000 respectively. train the model for 100 epochs. The training has 40 randomly generated graphs from SBM p. q). We validate the performance by the percentage of correct predictions on 200 ran- dom vertices, each from randomly generated graph. The result is shown Figure 2 The shaded region for each is obtained from the max, min and mean percentage of the 40 experiments. The result verifies Theorem 2.2 which shows that the accuracy of the model increases with n.
0.6
0.4
each experiment we
1000
5-500
0.0
n=250
40 60
80
100
Figure 2: Display of accuracy versus epoch for varying n. Accuracy computed vertices drawn from random SBM graphs. The accuracy in- creases with epoch, and also see that the lower bound on the accuracy increases with n, as ex- pected from our theory.
Experiment In this experiment, effect of the number of hidden neurons h. The parameters of SBM are the same as Experiment 1. We set h = 2, 5, 20, For each pair of (n, h) run 40 independent experiments and show the distribution of validation in Figure 3 From the top row to the bottom, n increases from 250 to 1000. From the left column to the right, h in- creases from 2 to 20. each plot, the x-axis rep- resents the accuracy, while y-axis represents the count of experiments. According to Theorem 2.2 the probability of achieving high accuracy ((1/h) and the accuracy increases with that in each row of Figure 3 h increases, we have lager probability to achieve high accuracy; in each column, n increases, the model achieves higher accuracy. The results verify our theory in the paper.
show the
24 68
We
Figure 3: Display of accuracy for varying and h.
FUTURE DIRECTIONS
For each row, n is set to be 250 (top), 500 (middle), 1000 (bottom); for each column, is set be
Graph neural networks offer a promising setting for progress on the more general theory of deep learning, because random graph models more plausibly capture the structure of real-wor wolld data compared to, e.g., the Gaussian inputs often used to prove deep learning guarantees for traditional feed-forward neural networks. This paper has initiated the project of proving training guarantees for semi-sun suni-supervised learning using GCNs on SBM models, but much more work remains to be done. Arguably the sparsest SBM models (expected constant degree) the most compelling from the perspective modeling real-world communities, so would be interesting to extend these results to that setting. Models with more than two blocks, overlapping communities (Petti & Vempala 2018) would be even closer to real-world structure. We hope this initial step spurs further interest in provable guarantees for training neural networks using plausible models of real-world data as the input distribution.
(left), 5 (middle), 20 (right). Probability of failure decreases increases, and accuracy increases with n.
ACKNOWLEDGEMENN
This research was supported in part by NSF Grant 1849796. The author would like to thank Prof. John Wilmes for guiding the research, and also thank Prof. Tyler Maunu and Prof. Pengyu Hong for making the results more generalized and designing the experiments.

---

Published as a conference paper at ICLR 2022
REFERENCES
Emmanuel Abbe and Colin Sandon. Recovering communities in the general stochastic block model without knowing the parameters. arXiv preprint /rXiv:/506.00. 2015.
Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact recovery in the stochastic block model, 2014.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International conference on machine learning, pp. 605-614. PMLR, 2017.
Jianfci Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with
variance reduction. arXiv preprint arXiv:1710.10566. 2017. 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling, arXiv preprint arXiv:1801.10244 2018.
Sitan Chen, Adam R. Klivans, and Raghu Meka. Learning deep relu networks is sxed-parameter tractable, 2020a.
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks, 2020b.
Mikhail Drobyshevskiy and Denis Turdakov. Random graph modeling: A survey of the concepts. ACM Comput. Surv., 52(6);1-36, December 2019.
D.P. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009, ISBN 9781 179449998994 URL https
7/books. google....oo.....o..ooo https//ssppogll.ccooooooo/oe//e www.://ookkssii00ooaaaaa...
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424, 2018.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419-3430 PMLR, 2020.
Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. CoRR, abs/1711 1.005511 2017.
Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pp. 3587-3596. PMLR, 2020.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Tatsuro Kawamoto, Masashi Tsubaki, and Tomoyuki Obuchi. Mean-field theory of graph neural networks in graph partitioning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12): 124007, dec 2019. doi: 10.
URL httph: http::://oo...og/2....0. 1088/
1742-5468/ ab3456
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017.
R. Kumar, Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In Proceedings s1 Annual Symposium on Foundations Computer Science, pp. 57-65, 2000. doi: 10. 2000//FS.2000.8990
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- sumi-super learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
10

---

Published as a conference paper at ICLR 2022
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp.
2019.
Samantha Petti and Santosh S. Vempala. Approximating sparse graphs: The random overlapping communities model, 2018.
Ryoma Sato. survey on the expressive power of graph neural networks, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. arXiv preprini urXiv:1905. naai::9055.22... 10261, 2019.
Santosh Vempala and John Wilmes. Gradient descent for one- me-hidden-layee neural networks: Poly- nomial convergence and sq lower bounds. In Conference on Learning Theory, pp. 3115-3117. PMLR, 2019.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 24, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXiv:1810.00826, 2018.
Prateek Yadav, Madhav Nimishakavi, Naganand Yadati, Shikhar Vashishth, Arun Rajkumar, and Partha Talukdar. Lovasz convolutional networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1978-1987. PMLR, 2019.
Chiyuan Zhang, Samy Bengio, Moritz. Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-laye relu networks via gradient descent. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1524-1534. PMLR, 2019a.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):529-5536, 2019b.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint 1rXiv:1812.084333 2018.
A CONCENTRATION AND SEPARATION OF OUTPUT
Let N(x, 0), (z. 1) denote the neighborhood of vertex with label 0 and 1 respectively, i.e. N(x,0) 0) = fy E G, ~ x, Ely) = O,, (zx = {y E G,y x, {(v) = 1}. By the definition SBM, both [N(x, 0) and [2 1)I are binomial random variables. For f(x)
0, [N,,,, 0)| ~ B p), [N 1)] B(5,g) and for {(x) = [,,,( (xr B(G, [N 1)] ~ B(2 More- over, th and th are also binomial random variables, for {(v) 0, B(aA .p,
B(nd q).
similarly for f(y) = 1. Our following analysis is based on the condition that [N 0)f. [N(,
and ti are in their high probability range for all G. Specifically we require the condition that for all ((x) O, (similar conditions for ((x) = 1 are omitted):
[N(x, 0)]
np
S ((p))
NNxx 1)
nq
$ 8(
(Cond)
2
2
ndp
tt ndq
to
S (np))
< (nq))
2
By tail bound of binomial random variables and union bound, we have
1
IP[ Condg 2 1
n
Under this condition, show the concentration of A, for each type.
11

---

Published as a conference paper at ICLR 2022
A.1 "GOOD TYPE" NEURONS
For convenience, according to the activation pattern of olad)) + a444), we further divide G2
into subcases (22,1). (G2,2) and (G2,3) by to the ratio of e For example, in (G1 and 22.1
((a,t) a(tt)) active for both (gy and f(y) in 22 is only active for f(y)
R1
P (1 + log n)
(G2.1)
q
02
p (1
log $ n)
(G2.2)
9
P
(1 log
n)
VA
R
P (1 + log 3 n)
(G233)
q
q
We have the following estimation of A in "good type".
Theorem A.1 (concentration of output from "good type" neurons). If the i-th neuron is of good type", then
* in both G1 and G2.1
1(3 - (1)
P A.
I(p2 +g)));;; + 2pqaal| s a() 80) - n)][(r) -0] 0]
(p+ q)2
2 21 -1- 1
1(3; - -19
A
[2pras + (02 + +d])a(]]| S (ar -)) 30) - n)(((()) =
9)²
2 21- 0 1 -
in 22.2
A(3 105-3pp -,,p
P||A
(pox + gold) S (a; (a; 800(1lgg* m)]e(z) = 0]
9)+
1 n
2 21-
A(3:- - -31)9 (pa: + qal)l s (a; - at)(3; 300((log n)][(()= = =
2 21 - 0 1 n?
in G2.3
X(3x 12--3
PI|A,
(pos galdl (a; af)(3 3)) m)(((>) = 0]
g)+
2 1 - 0 1
n
A(32 - --:)9
A
(po; + qa()l (a; - a() 30)0(log' m))((x) = 1] (p+
21 0 n?
12

---

Published as a conference paper at ICLR 2022
Proof. We have A; (3, 8 Evec fyy bounded difference (Dubhashi & Panconesi, 2009) to estimate A, In different parameter regimes,
40 +o.t)) We apply the method of averaged
n [p++))"
Φ(a;t)) =(tt)) has different activation patterns.
In G1 and G2.1 (ba;"" + a417) is active with probability 1 1 0 for both E(v) 0 and fly)
For [[]]
= 0, at first we estimate B[A,]. By condition (Cond
1(3 8 1122 + +g²)a; + 2pqa' S (as - -3) - ()) n).
B|A.]
(w + q)²
Let Y 4 2/ +ait")
then A; (3, - B,) B,),, E, Y,. Based on condition (Cond). |Y,
(x+t))
2xpp a(pta)²
- (a; - a() & n) for {(y,) = O. For any ag. dx.
B[ Y Yv ax) [Y, Y Yv a'd] (a=== n).
Moreover, when the number of vertices with revealed labels are fixed,
V ... Y = ax] E|y,/, Vr-1, = d'l S -a; df)0(log n),
for j 2 k. By condition (Cndd.. there are at most O(log" n) non-zero terms for Yx. 1 S k S So
E Y, Yr-1, Y2 ag}
E Y,IY,.. YK-1, Yv dil (a: -
-a)=) (log 3 n).
for S h: S n. By the method of averaged bounded difference, we have
1 B1) [[p (p""+"")))) )a; S (a: (d): - =1((s) 0] 2 1-0 n1
P| A-
(p+ g)²
Other regimes can be proved similarly.
A.2 "BAD TYPE" NEURONS
For convenience of our analysis, we further divide according to the ratio of 2
B2
into subcases B2.1) B2.2
and
B2.3
a
P (1 + log n)
(B2,1)
q
0
(1 + log $ n)) "(1 -log" - [n]] p
(B2,)
a
- We have the following estimation of A; in "bad type".
Q; og
P 4
- (1-log 1 n). P log log- n)]
(B2a)
Theorem A.2 (concentration of output from "bad type" neurons). If the i-th neuron is of "bad type".
we have:
in B and B2.1
1(3, - B1)
A
1122 + +g))aa + 2pgalll s -a(118 3110(log - m)(e(x) 0]
(p+9)²
21- 1
A(3; (8)
A
12go, + +02² + S la; - 1 n))((()))))))))))))))))))))))[) = 1]
(p + q)²
2 21- n?
13

---

Published as a conference paper at ICLR 2022
in (22.2
(po; + qa()) $ la; -,/113; 5110[log e(x) = 0] ()²
1
21 - 0
n2
A(3--399
P|
(po; + qal)l lay -4118, - B11O(log n)]((x)= = (p g)²
1 n2
2 1 - 0
12.3k
1(3: 1 -30p
4,
(po; + ga'd) la -a118: 310(1og" =1 ())((x)= = 0]
(p + 9)²
2 21-0 n
1(3 -3,0 (p+
A
(po; + qa!)l s laz af118: 3,10(log - n)]e(x)= =
2 - 0 1
n
in BB
A S aa; a4113, - O $ n))((() = or 1| 1 0 -
Proof. The proof is similar as Theorem A.I
A.3 "HARMLESS TYPE" NEURONS
We have the following estimation of A in "harmless type".
Theorem A.3 (concentration of output from "harmless type" neurons). If the i-th neuron is of "harmless type", we have:
in
1Ba-3,)p (po: + qald S (a, - a4)(3; =))0(log n)]((x) = 0]
P A,
(p 9)2
ス 1 2 -1-0 1
n?
A(3=-33) -319
A
(pa, + qat)) S (a; - a))(3 30)0(log n)]((z) = =1]
(p 9)
ス 1 21 0
n?
in H2 A; for both {(x) = 0 and 1.
A.4 SEPARATION OF OUTPUT
Previous subsections have shown the concentration of A for each type of neurons. For the i-th neuron, write the concentrated value as mi if f(x) 0 and mf if {(x) 1. From Theorem A.1 A.2 and A.3 we have the following result about the value of mb mi by straightforward computation.
14

---

Published as a conference paper at ICLR 2022
Corollary A.4. We have the following result about m) mm for 1 i S h:
if the i- neuron is of "good type":
p (P-9 2
in and G2.1 mo
mi = =Naa; - -ill3: - 3/1
p
in G2.2 mb
m
113;
B/ 2/ + -qa!l
4 (p 9)2
X
p (P-9- 2
2
2 a, all13; - B/
pp+
in G2.3
mg
mi
사|3; p/lpa: - qall p- 4 (p q)2
B1 (p - Aa
2 Ala; -,l13:
(p q)²
where As [1-log hn)p==''
(1-log" n)ptq
if the i-the neuron is of "bad type":
m -Xaa - a3l18, 311 (P-9 (1((pg
and B2.1 mg
p
in B2 mo
-113; - B'llpa, + ga! mi
p- 9
(p+ 9)2
2 -xla; - d4113 B11 (M - A34
(p
in B2
mo
mi
1113 3ilppa + ga'l
p-9
(p+ g)²
2 - aaa; d1118 B11 (p q)A1
(p 9)2
in B3
mm mi O,
where A [1+1og
n)p -2
Ag
(1-log n))p
(1+log"
w)pto
(1-10g n1p++9
if the i-the neuron is of "harmless type":
mi A|B; Allppa +qa'l p- q
mg
(p (p+0) q) (p 9)As
(p + 9) Alas of118: B1
in H2
my
mi
0,
where As
log
p+ (1+ 3g
B DYNAMICS OF PARAMETERS
We consider the cross-cntropy loss in training. The loss on a particular vertex r is
L(x) = - log (x),
where (z(x) and O (æ) are the first and second component the output respectively, i.e.
exp(go(x))
exp(g1(x))
Oo(x) = exp(go(x)) + (x))
01(x) = exp(so(x)) + exp(gi (x))
15

---

Published as a conference paper at ICLR 2022
For given graph G' generated by SBM, set the objective function L(G) the average loss all the vertices with revealed label ie.
L(G)= #( G: ((x) is revealed)
Σ
M(x).
a=f()) revealed
We first show the partial derivatives of parameters.
Theorem B.1 (derivatives of parameters). For Sis h let be vertex, f(x) its true label,
L(x) log Oz(z) (z), then
OL 4
(B: - ())
Σ 1ly x|Lla + af 2 0/6
0a;
"²(p (p 4)²
00
4
n²(p (p + q)2 (3: - -))
Σ
1ly x| + t 2 0]t?
da
8
0L
4
2( 2(-1) 10())
Σ 1ly (a, + +
03,
n²(p + 1)
7L
7( 1(-1)=-((1)
Σ
1ly 2) 2]o(an0 + +41)
03. (2(p + 9)2
9
OL
(- 1)a -((0))
Obo
aL (-1)
0bi
where Z =
explgo(z))+exxpl (oT) Cg and to are the numbers of neighbors of y(including perhaps
expl01 - (x))
itself) with revealed labels in class and class I respectively.
Proof. We compute Do: 08
0L aL and
others can be computed symmetrically, We have Bbo
BL
L(x) = - log (z) = log(exp(9o(x)) + exp(gi(x)) - IE(e) (x))
exp(gX(=) since O,(z) texploll . = 0, 1. So
0L egu(x) @gn(z)
+ (w)(w) (a)
0ge(z) (x)
da.
Da.
Do, (Bo(2)) + (0)(x)
Oos
(-1)) (-11)-((x)22 z 0go(z)
(x)
do:
da;
Since gy(x) = f5(x) + bj.
(gy(#)
015(x)
, = 0. By
do:
8o:
0f)
4
Σ 1ly ~ x 3:1111 + + 2 006
8o;
n²(p + q)z
(f)
4
Σ 1l 11 +afti 0/tg.
doy
n²(p + q)2
Therefore
ØL
4 n²(p + 2)2
(-1))- Z(B 8)) Σ 1ly [/] + +ff 2 0/1-.
da;
We abuse the notation J. for T(z)) and [G), but the meaning is clear from the context.
16

---

Published as a conference paper at ICLR 2022
AL Next compute a9,"
OL Similar as above,
(-1))-((x)2 (fff(a
8f((a)) ). By (
09:
83:
ff(())
4
1 2)0(0 + a,tt)
03;
n + q)²
(z) 0.
da;
So
0L
4 n² (p- + q)2
(-1) z > 1ly 2|0(art + dftt).
03,
Lastly,
ØL Obg
= (-1)²- [00(2))
3gi (x)
Obo
Obo
(-1)² 1)2-1()))
since 0ga(z) 0bo
1,
0gr (x) abg = 0.
will use Theorem B.1 to analyze the dynamics of neurons of each type. As have the form YZ. In order to estimate these derivatives, we show the concentration of Y and Z respectively. To estimate the concentration of Z. need the concentration of output obtained in Section 4 For any c > O, we require the probability of concentration in (3) to be at least č, where o(c). In particular, if we choose ? e² then set - ( Z i.e i.e.
In the following, we can see, all of da, do? 00, ăø.
BL. aL 8L 01. and
n ( 2
(5)
Our following analysis will be based on this condition.
Meanwhile in order to have balanced performance in each epoch of coordinate descent, we require
IE 96g
c. Since Ej Bbg ] ([[-E(z|e (x) 0) + (() 1])), we have
[[Z 0] [[Z]((z) 1] ट
We have the following relation between μll and Mr In the following, represents the sigmoid function: (x)) Ite-r-
Proposition B.2. If (E()((() oj E[Z((()) - < then la(- - d' 8)8 a'411 + 8)8 + 3č, where å is as shown in Corollary 4.2
Proof. We have
Z (o(-A),
((x:) = 0
(A))
((x) =1
For {(x) = 0, by Lagrange mean value theorem, ( Z = -(-A)) =
Mo), where { is between -Mo and -A By Corollary 4.2 and the condition of n, AA Mo S 0 with
probability > 1 - é. From the remark following Corollary A.4, we have a' (E) & d'(110 + 6)
o' d'uu 8) with probability 2 1 č. Then have
Pl[o(-Ho) - Z < o d' 8)81((x) 0 2-11-
Since
= = - 7 s d' - 8)0FF(10((1)) - 2 s o'(po - -8)0
+ (E|Z) Z > p'o - 6)01p(10(-H4)) - 0 o' o'(4 - 6)68,
(x:):) is even.
17

---

Published as a conference paper at ICLR 2022
then (note that 0 < < <<<> 1)
[| 0 < + t'00 - -66 6 +
and
[) = 0J 2 (o(- d'400 8)8)(1 - -E),
i.e.
[[Z](()) = 0] - ( - o' 0'440 - 6)6 +ē
and
B|z](())=0) = o(((o)) 2/2 -o' (HO - 6)6 E(o(-Ho) (w) - o' 6)6)
= o' we1) 5)0(1 -) - (0
2 04'( - 5jØ - ē.
So
B[z]e(=) = 0| - o o--wo) & o' d'110 - -815 +
Similarly
[[Z](())= = It - a(m) - o' (m + +566 +E.
By triangle inequality,
|o(- - o ((1) = (o(-H)) B[Z]e(0) = 01 + [[Z 0 B[Z]e(x) 1]
+ [[[(2((( = ((w)) ) s a' d'w 836 + d'un + 8)5 + 3E.
From the proof above, directly obtain the following corollary about Z. Corollary B.3.
P B[Z)((z) 0] 20 +)0+)(((z)) 0] 2 P 2 - B[Z]((x) 1] < 20 (w) + 5)6 + +(((()) = = 1-
In order obtain the concentration of Z, need to estimate o' 556 and a d'1 + 8)5. The following proposition is based on the condition that 140 + ا1 2 46. If 140 + م1 < 46, set c: 140 ft. we have 140 > - 20 and μ4 < - + 26. Then the concentration of output shown in Corollary 4.2 can guarantee 1 - accuracy of the model for any e > 0. In fact, from / - Pol <
we have pu 8 _ 38 > due to 5 o(c). So
PIA (z = 0) 2 PI pol < 8]((r) = 0] 2 2-E.
Similarly,
P|A < 0f((z) = 1] > PII Hol < 6|((r) = 1] 2 1 1-E.
Since == == o(e), the model achieves overall accuracy 2 6
Proposition B.4. If [g + Hnl 46, then of (Ho 8)5 0(²), d' + 6)8 0(²).
Proof. First, we estimate the lower bound of Io (-Ho) ((4)) via the Fundamental Theorem of Calculus. We have (-(-p)) a )1 ~ o'(1) di)
If - < μn < 0, since 140 + μn > 48, we divide the interval [-Mo, [i] into |- -10 + 28 U [-10 + 26, μi 26] U | 26, |i] and estimate the lower bound the integral. Since o'(x) is
increasing on (- 30, 0]. we have
(t) dt 2 d-(-)o) 25 + J + d' 25) 25,
(7)
where I = - o d'(t) dt. μ1 < 44 < 0, similarly we have
Hg
d'l1) dt > o' (m)) 28 12 a' (-po 25) 25,
(8)
18

---

Published as a conference paper at ICLR 2022
where /2 -p
2o-2 d'()) dl.
We have uniform lower bound from and (8
I
jk d'(t)
dt o'(- -66)- 28 o' d' 26) 26 I,
(9)
where =
Furthermore, by Proposition B.2
| po) o(1i) ( <' 6)6 o + 6)6 + 3E.
(10)
Combine 9 and 10
20 2o 26)8 + 20 (m1 26)8 - o' (-Ho + 8)8 + o (M) + +06 + 32.
(11)
By Lagrange mean value theorem,
d'(-o 26) = d'(-uo + 6) - (50)6
o' d'(n1 - 26) = (m) + 5) 30 (E1)6
where &o E (-140 - 26, -10 + 51 E (M) 26, μM 6). Plug these into
o' 0'100 8)5 + o (m1 + +666 - 65 (5o) + o(())) S 32.
Since (o)) o (E:)) = (po - 6)6) and ol (m + 8)8). we have o' d'o - 836 = (()) d' (m + +86 = 0(²)
Combine Proposition B.4 and Corollary B.3 we have the following concentration of Z. Proposition B.S.
P E| 0| < (())(()) 0) ē P E| ((x) = 1]] - 0())((x)) = 1] ē.
Under the condition balanced performance, we have the following corollary about the concentration of Z independent of the label of a. Corollary B.6. If
B
BL Dba S 5. then P E - 0()) 2 1
Proof. Since E
OL 8bg
(E|Z)(()) 0] [z) 1]), have
B[Z]e(x) 0] - E[Z = 1| ج
On the other hand,
B = 1
E[ = 11)
2
So we have
E [[Z 0|| < 2-2 By Proposition B.5 I - E[Z] s 0()) 2 1 - 7. L
Now we can derive the estimation of the derivatives.
Theorem B.7 (concentration of derivatives). For loss on the whole graph L L(G), with probability
2 O(2,, we have
1. Ifa; > of O 0; > 0>
2(1 + log $ n). then
0L
+ (0: B1
9
2
|8 B110 in)
(12)
da;
p + 9
aL
2
(8) - B))
2
< 8 11E 22)
(13)
da
+ 4
ØL
(a.
9
2
E
0; -
- o/ n).
(14)
033
+
Sinnee OL
0L
(see Theorem B.1
only need to estimate AL
85
05,
19

---

Published as a conference paper at ICLR 2022
2. If 04 0 d/1 1 [1 + 7),5(1 -log 3 n]], where 7 E [log 3 n1 (6)((1
log - 3 n) - 1]. then
aL
+ (3, - 8)) Ap(p - q)
B12]
$ 13, 8 (lz n)
(15)
da:
2(p + g)2
0L
Ap 9)
0 + (3: - B1) 2(p + 1)2
< 13 - E n)
(16)
0L
A(p (pas + qa())
+
B|2]
W | - d1 n).
(17)
08:
2(p + q)²
3. If > 0> 44
E (gg - log $ nn), (1 + log n)). then
0L
E 11 -2)
A(p - 9)A1
+ +Ollog 2 mn)
03;
2(p + g)2
A(p - () - A2) - O(log 1 2m) 1. (18)
(a: a())
2(p + 9)²
where A [1 à =02
.2 = po 3
(1-log 3 n)p²=q²
and A3
(1+log 3 nnppt
(1+1og 5 1nppt
(1~log n)ptg
if > By
ØL
Ap(p - 4) 2(p + +22 + +Ollg (0(og=$m))
&n))
E 11-
0o:
A 2
-OOlog $ -O(lo--m)) m))1 (19)
(3, 53)
2(pta) pp 9
aL
Ag(p 9)
+ +O(log - m))
E (B- - 10)[2
da
2(p + q)²
A12e PP-9 4
2
+ Ollog mi) (omm)=mm)) (20)
(3: - 1))
2 2 9
OL ÖL
E (B - 11)1 ( (>(PT))
+ +00log +m))
(p+9)
da; da
(
2 (P--9)
- -Olog 1 nm)) (21)
- -B, - 3
p +
if S 3,,
ØL da:
E (B - 1
X p (2-9) 2
-O(log 2 m)
2 p+ 4
Ap(p - 9)
+ O(log 3 m)) (22)
- -(s - 83EEE2
2(p + 9)²
aL
E (
- 8)1
\ p P-
2 p + +Olog -
2m) +(logg-2n)
Da?
(gq(= - 9) 2(p +
+ +Ollog 1 m))) (23)
(8, - 3))
9)² 9)2
aL
AL
E 1(3, 1ME42
X (p- (PP-9) )²
-O(oog-b10 =n))
Da:
dag
2 1 4
- - - )>)|Z|
2 (>p--g)
+ O(log 2 0llog=+n)) =m)) (24)
Apt
20

---

Published as a conference paper at ICLR 2022
4. af; >
[1 log
n)), Br < By then
0L
AL
2 -1; - (2)((2)
(25)
da;
0a
0L 03, 0()).
(26)
Proof. We show the proof for item 1, other items can proved similarly. Since L(G) is the average of the losses over revealed vertices, we first show the concentration of @L(x) then we show the concentration of (L(G) using union bound. Since den
da.
@L(r) (-1) -)) da;
10 ~ (arty + + 2 0,gg n²(p + q)²
Σ y
we first show the concentration of Y = (-1)1_(a)) Eynz
43 41 + 2016" n² (p+
using the
method of averaged bounded difference. Similar as the proof Theorem A.I let Y =
(-1)1-((x) 11 [a,d +a 201"" Based on Condition (Cond), for {(x) = 0,
2Ap
S
n((p+0)²
O(log n) for E(U;) 0. Similar results hold for E(yy) 1, 1,((x) 1. So for any ag. d'.
YIlY,,.. ... YY ax) E Σ YilY,,". Y Yv =ov] s (a: (a:-a() n).
E
By method of averaged bounded difference, for f(x) 0,
P Σ Yy + A(
)²
< Olog _ nn] 2 - exp (-2 n) 2 n²
p
=l
Similarly
P Σ
Yj A( 2 1
< <0 n)] 2 n²
p+
f(w))=1
Hence
Pl Y + A(p2+ + 9²)
< =n) n
(n q)²
By Corollary B.6 PI|Z |[2]| - {((E)] 2
-- ē, so we have
[T.(x)
+ (3: - 8)} 12 +
< 1 - AElZ] [n]((()) = 2 0 n?
P
E
da;
(p + g)²
For
((x) 1, similarly we have
0L(x)
2pg
P
(B:
8,)
E
< |8: B1IE[2]0(log m))((((()))))))))>>))))))))))))) m))[(=)
do;
(p
+
q)2
By union bound, we have 12
13 and
14 can be proved similarly.
Using Theorem B.7 we can analyze dynamics of neurons of each type. First, we introduce some notations. Let 7/x denote the learning rate at the k-th epoch, (k) be the value of Z the k-th
(k) be the value of a; at the k-th epoch, similar for a; ((K) g(k) and g((k) In particular,
epoch, a;
a o y(()) and g((0) represent the values at initialization.
(0) v00)
21

---

Published as a conference paper at ICLR 2022
B.1 "GOOD TYPE" NEURONS
In this section, we show that "good type" newrons stay in the "good type" regime throughout coordinate descent (Theorem B.8p using Theorem (B.7
Theorem B.8. "Good type" neurons are preserved in the "good type" throughout coorlinate descent with probability 2 1 - 0( (1) over the SBM randomness.
Proof. As shown in Section "good type" regime is composed of G1 and
(G2
we show the
dynamics of neurons in (1 and G2) respectively.
Assume that neuron (a: (R) (
(((h)) is in (G1.. we show that it either stays in
G1
moves
into G2 throughout coordinate descent. In fact, by 14), with probability 2 1 0
ar.
n1
a1 a
so
8
[(++1) B(t), 5 (((++)
g((b)) and hence 3((+1) - 3/ 3((h+1) > -1( g/(()) >
By
12
and (13),
aL
< 0 <<<
aL so a;
(--1) aj a; < a; aa; (k++)
(k) 1(k+1) (kk)
> 0. this neuron
aa
da a
stays in G1 If ai
(k+1)
< 0, since
(k)
aL
(k+1)
0;
1/k Day
[tj
> 1,
(k+1)
((k)
AL
1) Da,
the neuron moves into (G2).
Assume that neuron is in
G2
we also show that it either moves into (G1
or stays in (2 As
shown in section 3.2,
22
G2.1
U
G2.22
U
22.3
.. If the neuron is in G2.1
again by 12
[3
and (14 0g
(k+1)
a:
(k)
0
>>>>>>>>> ai
(k)
1(++1)
1, (b++1
3
(R)
(k+
so the neuron stays in 22.2 If the neuron is in
G2.2 by 15
16 and
17
ar
<
0r
D3
03
so
8
g((+1)
> 8 g((+11)
Also,
Da (RT
9L
Do. KET
aL
< 0, so a;
(k+1)
a;
(k+1)
(k-1)
(AT
(k)
> 1.
If a
(k+1))
<
0, the neuron stays in G2
If 0
(k+1)
>
0, it moves into
G
If the neuron is in
G2,3 by
18 and 21
OL (
OL
aL
0, so
3(k)
((())
0
Da!
aa AA
3 g
(++1)
+1++1
a
(k)
- a
(k))
0. By
19 and
20
aL
< - -B, 8)
- Ollog 1 m))
da.
2
p 9
0L
< (0. - B)B[Z(
P
p
2
O(log - 2 m))
dn
2
p+g
Similar as in 22.2 if a
(k+1) < 0, the neuron stays in
G2 If a (k+1)
0, it moves into G
B.2 "BAD TYPE" NEURONS
As shown in Section neurons of "bad type" consist of two cases: and 13 where B3
B2.1
[2.2 |B.3 U B3 Since the output in B3 concentrated at 0 (see Theorem A.2), we don t need to worry if neurons move into this region. Neurons in Bi U B2
B2
B2.3 might exit "bad
type" regime and become "harmless" or "good" (if the neuron becomes order alignedd which will do
B2.3 the following theorem shows that the separation mi mm can be upper bounded by initialization. In fact, Theorem shoss that mi mi is proportional to las; - a1 B% The next theorem shows that both la.- aa and |3, --35 311 shrink throughout coordinate descent. The worst situation is that the magnitude of la, - all and B. - {81 of neurons in By iicrease and move into B or Bg at certain epoch. From Theorem B. we we see that the magnitude can only increase by a limited rate (we can see this more
no harm to the performance of the model. If they stay in B1
B2.1 B2.2
explicitly in Theorem 6.2.
22

---

Published as a conference paper at ICLR 2022
Theorem B.9. If (a) 04 , p ) is in
(K) (K) 2 21 (1-0 over the SBM randomness,
Bi
U
B2.1 11
B2 I {
B2.3
then with probability
|a; (1+1)
a,
a
[[5]
|
5, 1
5
(8/h)
5 (
Proof.
In
B
and
1
by 112 and (13)
aL > > dai"
(k)
(R)) aj
aL then (k+1)
<
a,
1(k+1)
((k)
so
|a;
(++1)
a;
I la
(k)
a;
(()) Similarly, by 14).
aL
8L
< 0, so
[g(k+11)
1
S l,0((t)
(k)
(7(
(Note that (k)
oi
> 02
(())
(k)
$3/00
In
B2
from
15) and 16), we have
>
パ,ス > 0, so |a,
(b+1))
0 (k+1))
S 1a 02
(k) 100)
Da,
aa:
On the
other hand, 0r.
a
at
So
B.
(k+1)
> $1 , p((++())
< (k( and 13! (3( - -B, g((h+1) 1) S
[k)
In
B2,3 by 224,
au (A)
aL
0a (6)
aL
> 0, so |a;
(k+1)
a
1k+1) S a a2
(k) ((k)
By 18
OL
0
aL
|3
g
I 10, (k) B, (k)
B.3 "HARMLESS TYPE" NEURONS
Section 4 shows that there are two cases of "harmless type": H and H2 For neurons in H1 the
derivatives of parameters are estimated in (15) (66) and (17) (same as in 22.2) can can have similar
analysis as in G2.2 and show that the inequality a, > a B, > 3 can be preserved. Moreover increases. So the neurons either stay in H or become "good type" if
In particular,
neurons in H1 do no harm to the performance the model.
For neurons in My [a,t"" + att 2 0j 0, so the derivatives are all equal to 0. Therefore they are never updated. Meanwhile they don't 't affect the performance of the model since o(a,t) + aftt)= = 0 and A; = 0.
C LEARNING GUARANTEE
In this section, we prove Theorem 6.1
6.2 and Lemma 6.3
Proof of Theorem 6.1 We prove by contradiction. Suppose
P|A < 0|((z) = 0] 2 4c,
(27)
then
ElZ(e(r)= = = E[Z = 0, < OJP[A < 0/((x) = 0)
+ (EZZ(((x) = 0, A > // > 01((z) 0J
2 2
4c = 26.
(28)
Furthermore, we claim that 140 < 8. In fact, if pA 2 8, since PIIA - Hal S 5)((()) = 0] 2 - e by
Corollary 4.2 and A P po 8 222 0, we have
P 2 0/((z) = 0 2 PIA pol - 8)((z) 0) 2 1-c,
i.e. P(A < 01((x) = 0] s 6, which contradicts
27
Let c == 14g - /1, then μ = 140 < 5 - c. Again, by Corollary
4.2 for f(x) = A < M1 +8
with probability 2 1 c, we have Z = oA) < ((1) + 5) < < Then
ElZ]((x) = 1] = E|Z
= 1 (
m1 < 6PI m1 < 81((x) 1]
+ (1] = A mll 2 A| - m1l 2 8)((2) = 1]
<ol-ct 28) - 1.
<<( C
2 +
23

---

Published as a conference paper at ICLR 2022
The last step is due to 8 = o(c). Since (0-)))) < {. = 1] < 3e Combine with 28
-0] =1I| 2
On the other hand,
| ØL 7bp
implies
E [[))(())= = -] = 1]| < 2'
which is a contradiction. So P/A < 0/((z) 0] < de. Similarly, P/A > 0/((x) 1] 4e.
Proof of Theorem 6.2 If the i-th neuron is of "good type", from Corollary
A.4
we find uniform
lower bound of mb mi in "good type" regimes. We have min
_ As]
Next we estimate
2
a; - of and 8. 8y. Let A A := ag! a; .B(b) = 3/(h)
(())
8,th) We have
(k) a a a, 11--1) 1k
(1)) (1-1)
OL
OL
da (--1)
da
(q((
1)
1,(h) x(()
8
(k)
Bf4-1) 8((h-11 1/k
0L
aL
0,3!h-1)
0
By Theorem B.7 in G1 and G2.1
with probability 21 1 ((,),
0L
0L
< -B8 8))E1
(P--0) q
2
A- 10O(log- ni) S - 3]) X
p P-9 9
2
da;
da!
(p q
p + 4
0L 0L
< -a; af)
((--g) q
x - Ollog 2 2n) s -(ai- - a2)
A
p
03 086
(p+g)
2
p q
so
1/t0 1!-11) 1) - mi
OL
ØL
2 Att (1-11) + m BiZ(()
///a///
A A
p p- q
(1k-1)
do: 1k-1)
da,
1k-
2 /p q
2
1(111) 1) + 2
p 9
B!A-11)
p+ + 9)
B B(*-1) 17
ØL
OL
2 B( mE d (p=1
A
00
2 (p
2
= ((( 1) + 2 + q
p !
A 111 1)
In matrix form:
(())
(( 2
)
(a
(()
M
(((
(29)
Similarly, in G2.2
(k)
(( ))
4 (A(t-))
B
( 2
((1-11)
(30)
in G2.3
A (1)
1
1 (pt9))
A (k-1)
Bi(b)
p
B
((
(31)
2(p-q)
(1-log 3 n)p²
where Ag
pg log
Ag
uniform relation among (9).. (30) and (31
(1+Ing n))
(1- & n)ppo
can be given by (30). By eigenvalue decomposition, we have
1/t0 B
N 4
1
1+
22A
p (p-9)
1
2 2k )
(2 (0) 2 ())
pp+0 4
1 (0)
B3.0/
1+
V2A
p 2 2h
8
p + q
24

---

Published as a conference paper at ICLR 2022
Therefore have uniform lower bound of mb mi the k-th epoch in "good type" regime:
p P- 2 2 p + 9
(1+
V2A
p 9 p + )
2 2h
mb mi 2
8
Next we consider the "bad type" regime. By Corollary A.4 we have lower bound of my. m in B
B2 and B3 respectively. By Theorem B.9 in B1 and
B2
Jos
o/l
and 13, B1 shrink. Moreover,
since A we have uniform lower bound mo
mi
in
and
B2
A(p 9)A1 - 14 (0)
Ap(p ②)
m4 m -1
B
q)²
(p g)²
since A1 (1+log 2))p2-4
2p -9
S p.
(1+1og n)pta
2p+4
Next we show that lo;- -a/1 and 134 8 can only increase by limited rate in
B3 From item 4 of
Theorem B.7 we have
aL
OL
2 -1; - 3(((())
da da
aL ØL
OL
S O(i)
03 03 05;
Therefore (note that 3r < 8
A S A (1-11) + mh B1 O(E))
[B!a|| s |1
Since E[Z(0] 2 (e and o(c), 2 (
so ny n S mE
Suppose
A O(1), otherwise, A and |B increase by an even smaller rate. So we have
A (k) [
1
1
1
(B(
By eigenvalue decomposition, we have
R8) - ( | (14, B("))" < (4 + (B!o))) (n o0).
LA
B
We obtained the result for "harmless type" neurons directly from Corollary 4.3
Proof of Lemma 6.3
Since all parameters are independent standard normal random variables,
have
Bi(a a') = B[(B -²) = 2, Varl(a 21 = Varl(B - 3 8.
By Chebyshev's inequality have
h
(as - 8,)² s 5h 21 -
is monotonically increasing.
2p-4
Otherwise, the model already achieves high accuracy, the proof of Theorem 2.2
25

---

Published as a conference paper at ICLR 2022
For neurons initialized as "good type", we have
- a'a-a'la>dnn >0 2
VT
1
- aara-a''a>a',a 0 =
4m
1
- 31 > 81 = VT
Var 31 81 = π
Let p denote the probability that neuron is initialized as "good type". By G1 G2 and symmetry, P = 22 > a',a a > 0, > 37) Since
P| [13>B1= - ~¹ Pla > d' aa] 1
1
we have p = 7. By Chernoff bound. Plhy 2 gh) 2 expepp (- 2 h), so Plg 2 [1 2121 11-exp (-
Also by Chebyshev's 's inequality,
P Σ
la--a/113: 3/1 hg
-
2T
1
h 1)
g
21
hgg
4x
the i initialized "good type
Set k = 10n
P Σ
a113 -
z
1 121-0(
2
80
8
the i-th neurnn initialized as "gond type"
So we have
P
Σ
|a: - la--61133 - B 2 80
the i-th neuron inilialized as "good type"
h
> P Σ
Ja: a
-811 8/1 2
hg
z
1P
2
mm
80
the i-th neuron initialized "good type"
(1 01-0 22) exp (-
11) (1
2 11- (
D EXPERIMENTS ON DYNAMICS OF HIDDEN NEURONS
This experiment verifies our argument Sections B. B.2 B.3 and Theorem 6.2 about the dynamics of hidden neurons. We set h 5, x = 0.3 and train the model on graphs sampled from SBM with n = 1000, a = 1.0, b = 0.7. The plot of accuracy and its distribution can be seen in Section 7 Here we plot the dynamics of all the 5 hidden neurons in Figure with each row corresponding hidden neuron. In each plot, .r-axis represents epoch and y-axis represents the value neurons. The first column depicts a; and a/, the second column a the third column |a; - -a;1, the fourth column
one
3/ and the last column |3 K| As shown in the figure, the first, second and fourth neurons are of "good" type satisfying they're re order-aligned, |
Throughout training these neurons are preserved "good" type: is lowered bounded by 1, and both Ja; af. {3 - B1 keeps increasing. All of these verify our argument in B.1 The third neuron is "harmless" satisfying (22). As shown
26

---

Published as a conference paper at ICLR 2022
in B.3 this neuron isn't updated and doesn' make contribution to the output. The fifth neuron is of "bad" type satisfying [2). Although |a; a²l and [3, By increase, but by comparing with the first,
second and fourth row ("good" neurons), they increase much smaller rate. This verifies result
in Theorem 6.2
jrphia JiHiphrr 21
1.5
pisha
3-bela
Jisha 21ephor
pisha 2-dpphl
2-teta
450
Mohhu Stabpha'
jdpha, 3-ajphu 31
Dsta 3-bedal
0.64
063
-10
082
1350
-11
2.00
1325
0.99
15
0-
12
1.5
j4gha, 4-apha 4
2.5
Datta 4-beta
100
150
150
100
1.0
2.0
abth''
0
18
jagna Staphh
1.4
5 Iatal
-10
12
-10
1.0
100
50
130
330
100
Figure 4: Dynamics of neurons of different types. The 1st, 2nd and 4th correspond to neurons of "good" type satisfying (G2). The 3rd row corresponds to "harmless" satisfying Hz).. The 5th row corresponds to "bad" type satisfying (.). Their dynamics verify our results in Sections B. B.2
and Theorem
E TABLE OF NOTATIONS
list the notations used this paper for readers' convenience.
27

---

Published as a conference paper at ICLR 2022
Notation
Definition
n
number of vertices in a graph
p
probability of intra-community connection
g
probability of cross-comnunity connection
parameter for p with p alogg
6
parameter for with q = blog
X
probability of revealing the label of vertex label of vertex adjacency matrix of a graph
((x)
A
Á
normalized adjacency matrix with self loop
m(p+o) (A 1)+1)
X
input feature of a graph trainable weights in the first layer of GCN trainable weights in the second layer of GCN bias matrix of GCN with each row of B being [6u. by]
W
W(1)
B
bo
bias in the first component bias in the second component
b h
number of hidden features logit in the first component without bias logit in the second component without bias logit in the first component, go fo + bo
fo
fi
go
91
logit in the second component, 91 = fi + b
A
difference between logit, A 9o 91 = fo + bo bj
28


Reviews:
[{"review_id": "wU7WtG6QZwt", "reviewer": "Reviewer_Pgr4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper presents an interesting technical approach studying the concentration or separation of GCN outputs by understanding the dynamics of three parameter settings (good, bad, harmless). However, currently, the paper faces two major issues:\n\nThe main result is not informative enough and may contain erroneous claims. The probability $1 - O(1/h)$ is implicit and does not depend on $\\epsilon$. It’s hardly (or impossible) to represent $h$ under both $n$ and $\\epsilon$. It is because $n \\geq A^2/\\epsilon^2$ and $h \\leq B n $ ($A, B are some constants$), we cannot say anything about the relation between $h$ and $\\epsilon$. For example, given that $n$ is very big, $1/\\epsilon^2$ is very small, we can pick $h$ any value that is either greater or smaller than $1/\\epsilon^2$ but still smaller than $n$. Therefore, without establishing the result in PAC manners, the claim can not be convincing.\n\nThe experiments cannot justify the theoretical results. Clearly, the assumption states that $a, b$ are constant, $p, q$ are the function of $n$. It is expected to fix $a, b$ and consider multiple settings of $n$.  However, the experiment setup varies both $a$ and $b$ and seems to keep $p, q$ similar between configurations.", "summary_of_the_paper": "The paper presents a theoretical analysis of two-layer graph convolutional networks (GCN). The main goal is to study the behaviors of GCNs when the inputs are random graphs generated by stochastic block models. The stochastic block models are constructed by three components: the number of vertices, intra-connection probability, and cross-connection probability. The paper assumes that intra-connection probability, and cross-connection probability should be functions of the number of vertices. The paper tries to establish the error bound w.r.t the number of vertices for the case that GCNs have the number of hidden features bounded by the number of vertices.", "summary_of_the_review": "The main theorem seems interesting but can be problematic in the way it is interpreted. The experiments are designed in a way that does not support the theoretical claims. Since authors corrected the statement which fixes the condition of n and (especially) h, I raise the score to 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "vltI-fnWj1P", "reviewer": "Reviewer_EjwU", "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": "\nThe contribution is interesting although some of the aspects of the paper could be improved (see my comments below). Not all the sections are clear (e.g. the need for coordinate descent could be better explained). All in all, I think it can get published after some minor revisions.  ", "summary_of_the_paper": "The authors provide guarantees (in term of the probability of correctly labelling any given vertex) regarding the learning of communities in the stochastic block model.  The proof technique relies on the analysis of three types of neurons : the so-called \"good\" neurons which contribute positively to the correct labelling, the so-called \"harmless\" neurons, whose effect on the classification can be neglected and the \"bad\" neurons which contribute negatively to the classification. The authors show that when initializing the paramters from a standard normal distribution, the number of neurons of the good type is sufficiently large to guarantee exact recovery of the missing label with high probabilty. ", "summary_of_the_review": "===============================\nGeneral comment\n===============================\n\nThe transition between the general result of Theorem connecting the values of the neurons and the prediction accuracy on the one hand, and the result of Theorems 7.1 and 7.2 could be made more clear. It would be better to explain in plain english somewhere that you are interested in (1) deriving a bound on the prediction accuracy based on the value of the neurons and (2) show how that bound can be controled from the initialization. As an example, instead of section 4, which is useless and does not clearly introduce section 7, I would put a short paragraph, in the general introduction explaining the two aforementioned steps. In a few lines, I think that would clarify the whole paper. \n\n===============================\nDetailed comments \n===============================\n\nAbstract:\n- I would be careful (remove or expand) with the sentence “This state of affairs is in contrast with the steady progress on the theoretical underpinnings of traditional dense and convolutional neural networks ”. It is not clear to me that a lot of progress has been made on the understanding of traditional convolutional neural networks\n\nIntrodution:\n \n- Perhaps provide a word of explanation on the “Weisfeiler-Leman hierarchy” \n\nSection 2:\n\n- Your definition of the SBM is not very clear. I would say something like “In the setting of the SBM, the graph is built as follows. Two communities C_0 and C_1 are first created. , For any two vertices v_i and v_j, those vertices are then connected with probability q they belong to different communities and p if the belong to the same community”\n- When you introduce b_0 and b_1 you should introduce b as well. In particular, the notations of section 3 (or at least some of those notations such as b) should already appear in section 2 when you introduce the model of the GNN. \n- In section 2, page 3, when you discuss the balanced loss, the connection between the average of the derivative of the loss with respect to each of the b_0 and b_1 weights and the averages of Z over the vertices labeled as 0 and 1 is not clear.\n- In your definition of Z, g0 and g1 are not defined. Are g_0 and g_1 defined as in section 3? then those definitions should appear earlier\n- You initially mention parameters W^{(0)}, W^{(1)} and b as the trainable parameters but then only discuss coordinate descent for b0 and b1 which are not defined. This is not clear\n- In Theorem 2.2, when you describe the accuracy, as correctly predicting the label of a single sample, I would recall the definition of lambda. In fact, lambda should be defined in the statement of Theorem 2.2\n- The sentence “bigger λ generates bigger gap” is unclear. What do you mean? remove or expand\n- generally speaking, the definition of g_0 and g_1 is not very clear. I would start by saying that g_j is defined from f_j and b_j. Then you can say g_0(x) denote the logit so that g_0(x) = log(p_0) + c  and  g_1(x) = log(p_1) +c  where p_0 and p_1 denote the probabilities of the vertex being classified in either of the two classes C_0 or C_1\n- Don’t you make your life overly complicated by taking the softmax while you only have two communities ? Why not take the sigmoid with a single output p_0=p, assuming p_1 = 1-p ?\n\nSection 4 : \n\n- it does not really make sense to have a whole section to describe the paper structure. Put section 4 as the last paragraph of section 3, or add it as a subsection in 5\n\nSection 5\n\n- It would be good to have some additional intuition on conditions G_1 to H_2\n- What if p=q in Corollary 5.3. Is that the reason why you take a>b in assumption 2.1. You should state that clearly. Why is that a problem ?\n- The third remark is not very clear to me. I understand that we don’t want mu_0 and mu_1 to have the same sign as this would mean that the network is unable to discriminate between the classes but the output to the network is encoded in Delta not in mu so it is not clear to me that a small loss necessarily implies a small difference mu_0 - mu_1\n\nSection 7\n\n- In the statement of Theorem 7.1 I would explain the condition on mu_0 - mu_1 by adding a sentence of the form : “provided that the difference mu_0-mu_1 is large enough”, …\n- The distinction between Theorem 7.2 and Corollary 5.3 is not clear. In particular, I want to make sure I understand the following: What do Theorem 5.1 and Corollary 5.3 assume in terms of the training ? Do they assume a 0 loss. This should be stated somewhere. The ambiguity also comes from the fact that you say that Theorem 7.2 refines Corollary 5.3. in what sense is Theorem 7.2 a refinement of Corollary 5.3? From what I understand Theorem 7.2 is just the application of corollary 5.3 to the dynamics of the neurons. \n-  The sum in the second probability in the statement of lemma 7.3 is unclear. I guess you mean the sum over all neurons whose initialization satisfies G1 and G2 ?\n- Proof of Theorem 2.2. Why can you assume that P(\\ell(x) = 0) is 1/2 ? doesn’t that depend on the probabilities p and q ?\n\nSection 8\n- Figure 3 is not very intuitive. Why not add axes labels? Also why not indicate on the figure that n increases with the rows and h with the columns\n\nA couple of additional typos and comments \n\n- page 3, right above Theorem 2.2: “It is easy to see that Z > 1 if prediction is wrong “ —> “if the prediction is wrong”\n- page 3, right above Theorem 2.2: “Then we update other parameters” —> “Then we update the other parameters”\n- In the statement of corollary 5.3, you should replace the “i-the” neuron in each line with ”ith neuron”\n- section 7: “In this section, we prove our main result that with high probability ” should be replaced with something like “In this section, we prove our main result which states that …” or “according to which ..”\n- Section 8, first paragraph: “is able to recovery” —> “to recover”\n\n", "strength_and_weaknesses": "", "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": "vDkeYWjTb0x", "reviewer": "Reviewer_15hz", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The result is quite interesting and leveraging well-established graph models to provide guarantees for graph neural networks is certainly a promising direction.\n\nI have the following comments for the authors:\n1) The notation and presentation can be improved. For example:\n- in page 3, the term $b$ is used first to determine the probabilities of the SBM and then to denote the bias.\n- b_0 and b_1 are not introduced in page 3.\n- The function $g$ is used in page 3 but introduced in page 4.\n- A “bad type” neuron is mentioned in page 5 as satisfying B1 or B2 … what is B3 then?\n\n2) Relation with classical detectability limits in SBMs.\nThe authors mention a few times that the problem of recovering the communities in an SBM has been well studied, but there are not direct connections between the regime of $p$ and $q$ studied here and what are the classical results for that case. Moreover, here the setting is different since in the classical setting one is given only a single SBM realization and here we are training with many realizations and then solving a semi-supervised problem. In principle, this means that a GCN could go beyond the classical detectability limits because the problem being solved is actually different. This is similar to the discussion in Section VII-C of “Exact Blind Community Detection from Signals on Multiple Graph” by Roddenberry et al. (although there are no GCNs involved there and indirect measurements of the topology are observed).\n\n3) The main body of the paper is not self-contained.\nTo follow the logical flow of the paper one has to flip multiple times between appendix and the main text. The main text has corollaries of results in the appendix, there are several references to equations in the appendix, in page 6 there is even a reference to the fact that some of the results are stated in the \"full version of the paper\", and is unclear to me what the authors are referring to here.\n\n4) In the experiments, the choices for $a$ and $b$ seem to be quite specific, is there any reason for these?\nAlso, in figure 3, from the description it looks like these histograms should sum up to 40, but they don't, what is going on here? E.g., for the center column, if we sum the are under the curve in the the top and middle plots these are very different, what is exactly being plot here then?", "summary_of_the_paper": "This paper presents a theoretical result on performing label propagation in a stochastic block model (SBM) using a trained graph convolutional neural network (GCN). The idea is that by training a GCN to learn the community labels on several graphs drawn from an SBM, one can then claim some theoretical guarantees on the semi-supervised problem of determining the community labels of the nodes on a new graph (drawn from the same model) where only a subset of the nodes is labeled.\n", "summary_of_the_review": "The main result of the paper is interesting, novel, and can motivate follow-up work. The presentation, on the other hand, should be improved.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UFJ-NSiDDF9", "reviewer": "Reviewer_suTC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths :-\n1) The problem the authors address in this work is highly significant. They provide the first provable guarantees for GCNs for semi-supervised community detection tasks. This paper can accelerate much needed theoretical work in the graph neural networks.\n\nWeaknesses :-\n1) The presentation of the paper is bad and really hard to follow. \ni) The same variable name is used in multiple avenues to mean different meanings which makes it hard to ascertain what it means when used i.e. b. \nii) The notation about stochastic block models (SBMs) is unclear. SBMs are specified via providing the partition of nodes which I could not find in the description. \niii) Some of the references were confusing. \nThe authors should have added a table for their notations which would have it much easier to follow. In case they were short on space. they could have added it in the appendix/supplementary materials. The current version of the draft needs some work to make it more digestible and easier to follow. \n\n2) The experiments were unclear to me i.e. why did the authors choose the values of a and b and where did they get these values from. Will any values of a and b work as long as a > b i.e. Assumption 2.1 or are there only specific values we can use. \n3) The experiments lack any discussion or analysis with regards to the results and how they are tied to the theory introduced in the paper.\n", "summary_of_the_paper": "In this paper, the authors present the first provable guarantees for Graph Convolutional Networks (GCNs) for semi-supervised\ncommunity detection tasks. The authors demonstrate that with high probability over the initialization and training data used, a GCN will efficiently learn to detect communities on graphs drawn from a stochastic block model (SBM). Empirical results demonstrate the efficacy of their results.", "summary_of_the_review": "In this work, the authors provide the first provable guarantees for the performance of GCNs for semi-supervised community detection tasks, which is highly significant. The presentation and notations used in the paper requires quite a bit of work to make them easier to follow for readers. The experiments were unclear to me as well as lack discussion or analysis. My recommendation was split between 5: marginally below the acceptance threshold and 6: marginally above the acceptance threshold and ultimately I decided to go with the former.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows that (under some parameter range) graph convolutional networks learns communities in the stochastic block model. The result is clean, the proof techniques rely on partitioning neurons of three types and seems applicable to more general settings. The reviewers agree that the main theorems are interesting. There are some concerns among reviewers about the presentation of the paper, but many of them seem to be already addressed in the revised version, and I would recommend the authors to continue to improve the writing. There are also some concern about experiments, but the experiments are mostly used to validate the theorems, so clarifying how they are related would suffice. Overall the paper seems to have an interesting theoretical result on GCN.
Decision: Accept (Poster)