Year: 2021

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 semisupervised 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 nonconvex optimization landscape with many poorly-performing local minima.

1 INTRODUCTION
There is presently a 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 et al., 2019a; Goel et al., 2020; Chen et al., 2020a).
One factor contributing to the gap between the theory and practice of traditional NNs is that realworld 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 on accurately-labeled natural images. Hence, any rigorous proof of the observed generalization performance of deep learning models on image classification tasks will necessarily require assumptions about the data that are 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 et al., 2019a; Vempala & Wilmes, 2019).
Compared to traditional feed-forward (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, we contribute to that goal by giving the first rigorous guarantees of efficient semi-supervised learning of stochastic block models via a GNN.
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, a 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., 2021); one of the most essential differences between different GNN models is whether they are meant to label the graph as a whole, or to label individual components of the graph, particularly vertices.
From a 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 Weisfeiler-Leman hierarchy1 (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 Kipf & Welling (2017). A single layer of such a model computes weights at each node by aggregating the weights at neighboring nodes and applying an activation function with learned parameters, e.g., a linear map followed by a ReLU. Many variations on this theme, including various sophisticated training regimes, have been proposed (Chen et al., 2017; Gao et al., 2018; Li et al., 2018; Zhang et al., 2019b; Chen et al., 2018), but no provable guarantees have been available for the performance of such models on natural data distributions, until the present work.
2 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 et al., 2000). Other graph models naturally capture community structures, the simplest of which is the Stochastic Block Model (SBM) (Holland et al., 1983). A graph is sampled from a SBM by first partitioning vertices into communities (with fixed or random sizes). Two vertices are 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 1 respectively. We denote the label of vertex x by ℓ(x) ∈ {0, 1}. The graphs are parameterized as SBM(n, p, q) where n is the number of vertices, p is the probability of an intra-community connection, and q is the probability of a cross-community connection. We allow n to vary (but will require it to be sufficiently large), while p and q are of the form p = a log
3 n n and
q = b log 3 n
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 λ. The input-layer features at a vertex x is (0, 0) if its label is not revealed, (1, 0) if its label is revealed to be 0, 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 log
3 n n and q = b log3 n n , where a > b are constants.
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
1Weisfeiler-Leman hierarchy is a polynomial-time iterative algorithms which provides a necessary but insufficient condition for graph isomorphism.
community structure, and experimental studies have been done in this setting (Chen et al., 2020b; Yadav et al., 2019). (Abbe et al., 2014) shows a sharp threshold in the task of community recovery: ( √ p −√q) √ n logn > √ 2. This threshold clearly holds for our case (at sufficiently large values of
n), since p = a log 3 n n , q = b log3 n
n and a > b. The contribution here is not to learn the community 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).
Our GNN models will be trained on a graph or several graphs generated by the SBM(n, p, q) model, and seek to understand their accuracy on arbitrary SBM(n, p, q) graphs not necessarily in the training set but with the same parameters a, b determining p and q (with n allowed to vary).
In particular, we study spatial-based graph convolutional models along the lines of the Graph Convolutional Networks (GCN) introduced in (Kipf & Welling, 2017). Each layer of the model computes a feature vector at every vertex of an input graph based on features of nearby vertices in the previous layer. A typical layer-wise update rule is of the form
X(k+1) = ϕ ( ÂX(k)W (k) ) ,
where
• Â is a suitably-normalized adjacency matrix of shape n × n where n is the number of vertices. Usually Â includes self-loops.
• X(k) gives the feature vector in the k-th layer at each vertex as a matrix of shape n×mk, where mk is the number of features in layer k.
• ϕ is an activation function, such as the ReLU.
• W (k) are the trainable weights in the k-th layer, a matrix of shape mk ×mk+1.
In our version of this model, we define Â = 1n 2 (p+q) Ã, where Ã = A+ I , A is the adjacency matrix of a given graph, and I is the identity matrix. For the given SBM(n, p, q), a randomly selected vertex has n2 (p + q) neighbors in expectation, so Â is obtained by normalizing each row of A + I with the average size of a neighborhood. Since very deep GCN models seem to provide little empirical benefit (Li et al., 2018), we use a 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:
f(X,A) = softmax ( Âϕ ( ÂXW (0) ) W (1) +B ) = softmax ( 4
n2(p+ q)2 Ãϕ ( ÃXW (0) ) W (1) +B ) , (1)
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 (0) and the number of rows of W (1).
We define the accuracy of the model as the probability of predicting correctly the label of a single vertex in a randomly generated SBM(n, p, q) graph where the label of each vertex is revealed with probability λ. We can now state our main result.
Theorem 2.2. For any ϵ > 0 and δ > 0, given a GCN model with 1δ ≤ h ≤ n hidden features and with parameters initialized independently from N(0, 1), if training graphs are sampled from SBM(n, p, q) with n ≥ max(Ω( 1ϵ )
2,Ω( 1δ )) and the label of each vertex revealed with probability λ, and if the model is trained by coordinate descent for k = O(log log 1ϵ ) epochs, then with probability ≥ 1− δ, the model achieves accuracy ≥ 1− 4ϵ. 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 as 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 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 we introduce the structure of the paper. Given a vertex y, denote the row of ÃX corresponding to y as (ty0, t y 1), so t y 0 and t y 1 give the numbers of neighbors of y (including perhaps y itself) with revealed labels in class 0 and class 1 respectively. Let
W (0) = ( α1 α2 · · · αh α′1 α ′ 2 · · · α′h ) , W (1) =  β1 β ′ 1 β2 β ′ 2 ... ...
βh β ′ h
 , B =  b0 b1 b0 b1 ...
... b0 b1  . Then αit y 0 + α ′ it y 1, 1 ≤ i ≤ h gives h features of vertex y in the hidden layer. The inner product of the yth row of ϕ(ÃXW (0)) and the columns of W (1) gives weighted sums of features of y :∑h i=1 βiϕ(αit y 0 + α ′ it y 1) and ∑h i=1 β ′ iϕ(αit y 0 + α ′ it y 1), where ϕ represents the ReLU function.
Given a vertex x, the row of Âϕ(ÂXW (0))W (1) corresponding to x is denoted by (f0(x), f1(x)) and is of the form(
4
n2(p+ q)2 ∑ y∈G 1[y ∼ x] h∑ i=1 βiϕ(αit y 0+α ′ it y 1),
4
n2(p+ q)2 ∑ y∈G 1[y ∼ x] h∑ i=1 β′iϕ(αit y 0+α ′ it y 1) ) ,
(2) where 1[y ∼ x] is equal to 1 if y and x are connected, 0 otherwise. Denote
f i0(x) := 4βi
n2(p+ q)2 ∑ y∈G 1[y ∼ x]ϕ(αity0+α′it y 1) f i 1(x) := 4β′i n2(p+ q)2 ∑ y∈G 1[y ∼ x]ϕ(αity0+α′it y 1),
so f0(x) = ∑h i=1 f i 0(x) and f1(x) = ∑h i=1 f i 1(x).
Denote gj(x) := fj(x) + bj , j = 0, 1., where (g0(x), g1(x)) represents the logit of the model corresponding to x. Denote ∆(x) := g0(x)− g1(x). In order to make correct predictions, we need ∆(x) > 0 when ℓ(x) = 0 and ∆(x) < 0 when ℓ(x) = 1.
The bias term B is useful in our analysis because its derivative controls how imbalanced the current loss is between the classes. In training we consider the cross-entropy loss denoted as L, and have
E[ ∂L ∂b0 ] = −E[ ∂L ∂b1 ] = −1 2 (E[Z|ℓ(x) = 0]− E[Z|ℓ(x) = 1]),
where Z = exp (g1−ℓ(x)(x))exp (g0(x))+exp (g1(x)) . Z can be regarded as a measure of wrong prediction: the numerator is the exponential of the output corresponding to the wrong label and the denominator is a normalizer. It is easy to see that Z > 12 if the prediction is wrong; Z <
1 2 if prediction is correct. When∣∣E[ ∂L∂b0 ]∣∣ ≈ 0, the model’s loss is balanced in the sense of that ∣∣E[Z|ℓ(x) = 0]−E[Z|ℓ(x) = 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 b0 and b1 until∣∣E[ ∂L∂b0 ]∣∣ is smaller than some threshold. Then we update the other parameters. The performance of the model depends on the concentration and separation of ∆(x) for ℓ(x) = 0 and ℓ(x) = 1 respectively. In Section 4 we show that ∆(x) is concentrated at one of two values, denoted by µ0 and µ1, depending only on whether the label ℓ(x) is 0 or 1. The proof depends on different parameter regimes of hidden neurons. In Section 5, 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 8.
4 CONCENTRATION AND SEPARATION OF OUTPUT
The difference of the logits is
∆(x) = g0(x)− g1(x) = f0(x)− f1(x) + b0 − b1 = h∑
i=1
∆i(x) + b0 − b1,
where
∆i(x) = f i 0(x)− f i1(x) = 4(βi − β′i) n2(p+ q)2 ∑ y∈G 1[y ∼ x]ϕ(αity0 + α′it y 1).
For brevity, we write ∆(x) as ∆ and ∆i(x) as ∆i. In order to estimate ∆, we need to estimate each ∆i, 1 ≤ i ≤ h. Our fine-grained analysis of the dynamics of coordinate descent on GCNs relies on a classification of neurons into three families based on 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 µ0 − µ1, where µ0 and µ1 are high probability estimate of ∆(x) for ℓ(x) = 0 and 1 respectively. We show that “good type” neuron makes positive contribution; the contribution of “bad type” neuron is negative but lower bounded; “harmless type” neuron’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 in the next section. First we give some definitions.
Definition 1. For 1 ≤ i ≤ h, we call (αi, α′i, βi, β′i) the i-th neuron of the model, where (αi, α′i)⊤ is the i-th column of W (0), (βi, β′i) is the i-th row of W (1). Definition 2. We say that the i-th neuron is order-aligned if (αi − α′i)(βi − β′i) > 0, otherwise we say it 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) or (G2) below. (There is also the symmetric case obtained by switching αi with α′i and βi with β ′ i. For brevity, we only consider the cases that αi > α′i. This applies to the “bad” and “harmless” types below as well). Neurons in this type are order-aligned and both αi and α′i are positive or the ratio between αi and α ′ i is large enough.
αi > α ′ i > 0 and βi > β ′ i (G1)
αi > 0 > α ′ i, ∣∣∣∣αiα′i ∣∣∣∣ > 1 and βi > β′i (G2)
We say the i-th neuron is of “bad type” if it satisfies either (B1), (B2) or (B3). Neurons in this type are order-misaligned and αi, α′i are either both positive or have the opposite signs.
αi > α ′ i > 0 and βi < β ′ i (B1)
αi > 0 > α ′ i, ∣∣∣∣αiα′i ∣∣∣∣ > qp (1 + log− 13 n) and βi < β′i (B2)
αi > 0 > α ′ i, ∣∣∣∣αiα′i ∣∣∣∣ ≤ qp (1 + log− 13 n) (B3)
We say that the i-th neuron is of “harmless type” if it satisfies either (H1) or (H2):
αi > 0 > α ′ i, ∣∣∣∣αiα′i ∣∣∣∣ ∈ (qp (1 + log− 13 n), 1] and βi > β′i (H1)
αi ≤ 0 and α′i ≤ 0 (H2)
4.2 CONCENTRATION AND SEPARATION
Theorem 4.1. If the i-th neuron is of “good type” satisfying (G1) or of “bad type” satisfying (B1), then for ℓ(x) = 0:
P[ ∣∣∆i − λ(βi − β′i)
(p+ q)2 [(p2 + q2)αi + 2pqα
′ i] ∣∣ ≤
(αi − α′i)(βi − β′i)O(log − 12 n)|ℓ(x) = 0] ≥ 1−O ( 1 n2 ) ,
for ℓ(x) = 1:
P[ ∣∣∆i − λ(βi − β′i)
(p+ q)2 [2pqαi + (p
2 + q2)α′i] ∣∣ ≤
(αi − α′i)(βi − β′i)O(log − 12 n)|ℓ(x) = 1] ≥ 1−O ( 1 n2 ) .
Similar concentration hold for neurons satisfying (G2), (B2) and (B3), and for neurons of “harmless type.”
We apply the method of bounded differences to show the concentration. The details are shown in the appendix.
Given the concentration of ∆i for each type of neurons, we estimate the concentration of the output ∆ = ∑h i=1 ∆i + b0 − b1. For the i-th neuron, we denote the high-probability estimate of ∆i given in the statement of Theorem 4.1 as mi0 when ℓ(x) = 0 and m i 1 when ℓ(x) = 1. By union bound, we have the following corollary. Corollary 4.2. Given a vertex x ∈ G with label unrevealed, we have
P[|∆− µj | ≤ δ|ℓ(x) = j] ≥ 1−O( 1
n ), (3)
where
µj = ( h∑ i=1 mij) + b0 − b1, j = 0, 1 δ = h∑ i=1 |αi − α′i||βi − β′i|O(log − 12 n) .
For any ϵ > 0, we require the probability of concentration in (3) to be at least 1− ϵ̃, where ϵ̃ = o(ϵ). If we choose ϵ̃ = ϵ2, then we set 1−O( 1n ) ≥ 1− ϵ 2, i.e.n ≥ Ω( 1ϵ ) 2. Our following analysis will be based on this condition.
From Theorem 4.1, we have the following result about the value of mi0 −mi1. Corollary 4.3. • If the i-th neuron is of “good type” and satisfies (G1), then
mi0 −mi1 = λ|αi − α′i||βi − β′i| ( p− q p+ q )2 .
• If the i-th neuron is of “bad type” and satisfies (B1), then mi0 −mi1 = −λ|αi − α′i||βi − β′i| ( p− q p+ q )2 .
• If the i-th neuron is of “harmless type” and satisfies (H1), then
mi0 −mi1 = λ|βi − β′i||pαi + qα′i| p− q
(p+ q)2 .
Similar results for neurons satisfying (G2),(B2),(B3) and (H1) are stated in the appendix, along with the proof. Remark. • As we can see from Corollary 4.3, the value of mi0 − mi1 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 mi0 −mi1 decrease the loss of the model, this explains the names for the types of neurons.
• mi0 −mi1 is proportional to |αi −α′i||βi − β′i|. In the next section, we analyze the dynamics of the parameters αi, α′i, βi, β ′ i. 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.
• Let c := µ0 − µ1 = ∑h i=1(m i 0 −mi1). By the two corollaries above, we have δ = o(|c|).
The balanced loss guaranteed by the bias term and the coordinate descent scheme ensure that µ0 = Ω(c) and µ1 = Ω(c). It then follows that if the loss is sufficiently small, both µ0 and µ1 have correct sign, i.e. µ0 > 0 > µ1. (Otherwise, due to concentration of the output, the model makes wrong prediction and the loss is large). So we will eventually have δ = o(µ0) and δ = o(|µ1|).
5 DYNAMICS OF PARAMETERS
In this section, we describe the dynamics of each type of 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.
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 of 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.
6 LEARNING GUARANTEE
In this section, we prove our main result which states that with high probability a trained GCN can detect communities in SBM with any desired accuracy. The proof is based on the following theorem which shows that if µ0 and µ1 are separated enough, then the model achieves high accuracy. Theorem 6.1. ∀ϵ > 0, provided that the difference between µ0 and µ1 is large enough: σ(−µ0−µ12 ) < ϵ 2 , if
∣∣E[ ∂L∂b0 ]∣∣ < ϵ4 , then P[∆ < 0|ℓ(x) = 0] < 4ϵ,P[∆ > 0|ℓ(x) = 1] < 4ϵ, where σ(x) := 11+exp (−x) represents the sigmoid function.
Next we show that the model can achieve such separation between µ0 and µ1 through coordinate descent. In order to make constant update of parameters at every epoch, we set an adaptive learning rate ηk = 1E[Z(k)] where Z
(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 (mi0 −mi1) using the dynamics of parameters. Theorem 6.2 (separation of output). Let mi0 and mi1 be defined as in Section 4, train the model for k epochs by the defined coordinate descent with adaptive learning rate ηk = 1E[Z(k)] ,
• if the i-th neuron is of “good type”, then
mi0 −mi1 ≥ A (0) i B (0) i
λ
2 ( p− q p+ q )2( 1 + √ 2λ 8 ( p− q p+ q )2)2k • if the i-th neuron is of “bad type”, then
mi0 −mi1 ≥ −k (( A (0) i )2 + ( B (0) i )2)λp(p− q) (p+ q)2 ,
• if the i-th neuron is of “harmless type”, then
mi0 −mi1 ≥ 0,
where A(0)i = α (0) i − α ′(0) i , B (0) i = β (0) i − β ′(0) i .
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 (0) and W (1) are initialized independently following standard normal distribution. Then the number hg of neurons initialized as “good type” satisfies P[hg ≥ h8 ] ≥ 1− exp (− h 64 ). Furthermore,
P[ h∑
i=1
(αi−α′i)2+(βi−β′i)2 ≤ 5h] ≥ 1−O ( 1 h ) , P[ ∑ the i-th neuron initialized as “good type” |αi−α′i||βi−β′i| ≥ h 80 ] ≥ 1−O ( 1 h ) .
Now we can prove the final result.
Proof of Theorem 2.2. First we show that if the loss E[Z] is small enough, the model achieves desired accuracy. Indeed, if E[Z] < 2ϵ, since
E[Z] = E[Z|pred is wrong]P[pred is wrong]+E[Z|pred is correct]P[pred is correct] ≥ 1 2 P[pred is wrong], we have P[pred is wrong] ≤ 4ϵ, i.e., P[pred is correct] > 1− 4ϵ. Otherwise, E[Z] ≥ 2ϵ, since E[Z] = 12 (E[Z|ℓ(z) = 0] + E[Z|ℓ(z) = 1]), we have E[Z|ℓ(z) = 0]+E[Z|ℓ(z) = 1] ≥ 4ϵ. On the other hand,
∣∣E[ ∂L∂b0 ]∣∣ < ϵ implies that ∣∣E[Z|ℓ(z) = 0]−E[Z|ℓ(z) = 1] ∣∣ < 2ϵ.
By Theorem 6.2, µ0 − µ1 = h∑
i=1
(mi0 −mi1) = ∑
i∈“good” (mi0 −mi1) + ∑ i∈“bad” (mi0 −mi1) + ∑ i∈“harmless” (mi0 −mi1)
≥ λ 2 ( p− q p+ q )2( 1 + √ 2λ 8 ( p− q p+ q )2)2k ∑ i∈“good” A (0) i B (0) i − k λp(p− q) (p+ q)2 ∑ i∈“bad” (( A (0) i )2 + ( B (0) i )2) .
By Lemma 6.3, with probability ≥ 1−O( 1h ),∑ i∈“good” A (0) i B (0) i ≥ h 80 , ∑ i∈“bad” (( A (0) i )2 + ( B (0) i )2) ≤ 5h. Since h ≥ 1δ , then with probability ≥ 1− δ,
µ0 − µ1 ≥ h ( λ
160 ( p− q p+ q )2( 1 + √ 2λ 8 ( p− q p+ q )2)2k − k 5λp(p− q) (p+ q)2 ) ≥ h(C1(1 + C2)2k − C3k), (4)
where C1, C2 and C3 are constants determined by p, q and λ.
By Theorem 6.1, if (4)≥ 2 log 2ϵ (then σ(− µ0−µ1 2 ) ≤ ϵ 2 ), then the model achieves accuracy ≥ 1− 4ϵ. It’s sufficient to have C1(1 + C2) 2k − C3k ≥ 2 log 2
ϵ ,
i.e. k = O(log log 1ϵ ).
7 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 in the sparse regime of Assumption 2.1. Additional plots demonstrating the dynamics of hidden neurons with their ratios and differences can be seen in the appendix.
Experiment 1 In this experiment, we plot the an estimate of the accuracy versus epoch for varying n. The parameters p, q of SBM follow Assumption 2.1, where we choose a = 1.0 and b = 0.7. We set h = 20, λ = 0.3 and run 40 independent experiments for n = 250, 500 and 1000 respectively. In each experiment we train the model for 100 epochs. The training set has 40 randomly generated graphs from SBM(n, p, q). We validate the performance by the percentage of correct predictions on 200 random vertices, each from a randomly generated graph. The result is shown Figure 2. The shaded region for each n 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.
Experiment 2 In this experiment, we show the 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) we 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 increases from 2 to 20. In each plot, the x-axis represents the accuracy, while y-axis represents the count of experiments. According to Theorem 2.2, the probability of achieving high accuracy is 1−O(1/h) and the accuracy increases with n. We can see that in each row of Figure 3, as h increases, we have lager probability to achieve high accuracy; in each column, as n increases, the model achieves higher accuracy. The results verify our theory in the paper.
8 FUTURE DIRECTIONS
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-world 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-supervised learning using GCNs on SBM models, but much more work remains to be done. Arguably the sparsest SBM models (expected constant degree) are the most compelling from the perspective of modeling real-world communities, so it would be interesting to extend these results to that setting. Models with more than two blocks, or 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.
REFERENCES Emmanuel Abbe and Colin Sandon. Recovering communities in the general stochastic block model
without knowing the parameters. arXiv preprint arXiv:1506.03729, 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 a convnet with gaussian inputs. In International conference on machine learning, pp. 605–614. PMLR, 2017.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710.10568, 2017.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247, 2018.
Sitan Chen, Adam R. Klivans, and Raghu Meka. Learning deep relu networks is fixed-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.
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.00501, 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.1088/1742-5468/ab3456. URL https://doi.org/10.1088/ 1742-5468/ab3456.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017.
R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 57–65, 2000. doi: 10.1109/SFCS.2000.892065.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
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 on Artificial Intelligence, volume 33, pp. 4602–4609, 2019.
Samantha Petti and Santosh S. Vempala. Approximating sparse graphs: The random overlapping communities model, 2018.
Ryoma Sato. A 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 preprint arXiv:1905.10261, 2019.
Santosh Vempala and John Wilmes. Gradient descent for one-hidden-layer neural networks: Polynomial 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 are 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-layer 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):5829–5836, 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 arXiv:1812.08434, 2018.
A CONCENTRATION AND SEPARATION OF OUTPUT
Let N(x, 0), N(x, 1) denote the neighborhood of vertex x with label 0 and 1 respectively, i.e. N(x, 0) = {y ∈ G, y ∼ x, ℓ(y) = 0}, N(x, 1) = {y ∈ G, y ∼ x, ℓ(y) = 1}. By the definition of SBM, both |N(x, 0)| and |N(x, 1)| are binomial random variables. For ℓ(x) = 0, |N(x, 0)| ∼ B(n2 , p), |N(x, 1)| ∼ B( n 2 , q) and for ℓ(x) = 1, |N(x, 0)| ∼ B( n 2 , q), |N(x, 1)| ∼ B( n 2 , p). Moreover, ty0 and t y 1 are also binomial random variables, for ℓ(y) = 0, t y 0 ∼ B(nλ2 , p), t y 1 ∼ B(nλ2 , q), similarly for ℓ(y) = 1. Our following analysis is based on the condition that |N(x, 0)|, |N(x, 1)|, tx0 and tx1 are in their high probability range for all x ∈ G. Specifically we require the condition that for all ℓ(x) = 0, (similar conditions for ℓ(x) = 1 are omitted):∣∣∣∣|N(x, 0)| − np2
∣∣∣∣ ≤ O(np) 56 , ∣∣∣∣|N(x, 1)| − nq2 ∣∣∣∣ ≤ O(nq) 56 ; (Cond)∣∣∣∣tx0 − nλp2 ∣∣∣∣ ≤ O(np) 56 , ∣∣∣∣tx1 − nλq2 ∣∣∣∣ ≤ O(nq) 56 .
By tail bound of binomial random variables and union bound, we have
P[(Cond)] ≥ 1− 1 n2 .
Under this condition, we show the concentration of ∆i for each type.
A.1 “GOOD TYPE” NEURONS
For convenience, according to the activation pattern of ϕ(αit y 0 + α ′ it y 1), we further divide (G2) into subcases (G2,1), (G2,2) and (G2,3) by to the ratio of ∣∣αi α′i ∣∣. For example, in (G1) and (G2,1), ϕ(αit y 0 + α
′ it y 1) is active for both ℓ(y) = 0 and ℓ(y) = 1; in (G2,1), it is only active for ℓ(y) = 0.∣∣∣∣αiα′i ∣∣∣∣ > pq (1 + log− 13 n) (G2,1) 1 <
∣∣∣∣αiα′i ∣∣∣∣ < pq (1− log− 13 n) (G2,2)
p q (1− log− 1 3 n) ≤ ∣∣∣∣αiα′i ∣∣∣∣ ≤ pq (1 + log− 13 n) (G2,3)
We have the following estimation of ∆i 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):
P[ ∣∣∆i− λ(βi − β′i)
(p+ q)2 [(p2+ q2)αi+2pqα
′ i] ∣∣ ≤ (αi−α′i)(βi−β′i)O(log− 12 n)|ℓ(x) = 0]
≥ 1−O( 1 n2 )
P[ ∣∣∆i− λ(βi − β′i)
(p+ q)2 [2pqαi+(p
2+ q2)α′i] ∣∣ ≤ (αi−α′i)(βi−β′i)O(log− 12 n)|ℓ(x) = 1]
≥ 1−O( 1 n2 )
• in (G2,2):
P[ ∣∣∆i − λ(βi − β′i)p
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ (αi − α′i)(βi − β′i)O(log− 12 n)|ℓ(x) = 0]
≥ 1−O( 1 n2 )
P[ ∣∣∆i − λ(βi − β′i)q
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ (αi − α′i)(βi − β′i)O(log− 12 n)|ℓ(x) = 1]
≥ 1−O( 1 n2 )
• in (G2,3):
P[ ∣∣∆i − λ(βi − β′i)p
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ (αi − α′i)(βi − β′i)O(log− 12 n)|ℓ(x) = 0]
≥ 1−O( 1 n2 )
P[ ∣∣∆i − λ(βi − β′i)q
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ (αi − α′i)(βi − β′i)O(log− 12 n)|ℓ(x) = 1]
≥ 1−O( 1 n2 ).
Proof. We have ∆i = (βi − β′i) ∑ y∈G 1[y ∼ x] 4ϕ(αit y 0+α ′ it y 1)
n2(p+q)2 . We apply the method of averaged bounded difference [book] to estimate ∆i. In different parameter regimes, ϕ(αit y 0 + α ′ it y 1) has different activation patterns.
In (G1) and (G2,1), ϕ(αit y 0 + α ′ it y 1) is active with probability 1 − O( 1n2 ) for both ℓ(y) = 0 and ℓ(y) = 1. For ℓ(x) = 0, at first we estimate E[∆i]. By condition (Cond):∣∣∣∣E[∆i]− λ(βi − β′i)(p+ q)2 [(p2 + q2)αi + 2pqα′i] ∣∣∣∣ ≤ (αi − α′i)(βi − β′i)O(log−1 n).
Let Yj = 4ϕ(αit
yj 0 +α ′ it yj 1 ) n2(p+q)2 , then ∆i = (βi − β ′ i) ∑ j Yj . Based on condition (Cond), ∣∣Yj −
2λ(pαi+qα ′ i)
n(p+q)2 ∣∣ ≤ (αi − α′i)O(log− 72 n) for ℓ(yj) = 0. For any ak, a′k, ∣∣∣∣E[Yk|Y1, · · · , Yk−1, Yk = ak]− E[Yk|Y1, · · · , Yk−1, Yk = a′k]∣∣∣∣ ≤ (αi − α′i)O(log− 72 n).
Moreover, when the number of vertices with revealed labels are fixed,∣∣∣∣E[Yj |Y1, · · · , Yk−1, Yk = ak]− E[Yj |Y1, · · · , Yk−1, Yk = a′k]∣∣∣∣ ≤ (αi − α′i)O(log−6 n), for j ≥ k. By condition (Cond), there are at most O(log3 n) non-zero terms for Yk, 1 ≤ k ≤ n. So∣∣∣∣E[∑
j Yj |Y1, · · · , Yk−1, Yk = ak]− E[ ∑ j Yj |Y1, · · · , Yk−1, Yk = a′k] ∣∣∣∣ ≤ (αi − α′i)O(log− 72 n),
for 1 ≤ k ≤ n. By the method of averaged bounded difference, we have P[ ∣∣∆i−λ(βi − β′i)
(p+ q)2 [(p2+q2)αi+2pqα ′ i] ∣∣ ≤ (αi−α′i)(βi−β′i)O(log n)− 12 |ℓ(x) = 0] ≥ 1−O( 1n2 ).
Other regimes can be proved similarly.
A.2 “BAD TYPE” NEURONS
For convenience of our analysis, we further divide (B2) into subcases (B2,1), (B2,2) and (B2,3) according to the ratio of ∣∣αi α′i ∣∣ ∣∣∣∣αiα′i ∣∣∣∣ > pq (1 + log− 13 n) (B2,1)∣∣∣∣αiα′i
∣∣∣∣ ∈ (qp (1 + log− 13 n), pq (1− log− 13 n)] (B2,2)∣∣∣∣αiα′i ∣∣∣∣ ∈ (pq (1− log− 13 n), pq (1 + log− 13 n)] (B2,3)
We have the following estimation of ∆i in “bad type”. Theorem A.2 (concentration of output from “bad type” neurons). If the i-th neuron is of “bad type”, we have:
• in (B1) and (B2,1):
P[ ∣∣∆i − λ(βi − β′i)
(p+ q)2 [(p2 + q2)αi + 2pqα
′ i] ∣∣ ≤ |αi − α′i||βi − β′i|O(log− 12 n)|ℓ(x) = 0]
≥ 1−O( 1 n2 )
P[ ∣∣∆i − λ(βi − β′i)
(p+ q)2 [2pqαi + (p
2 + q2)α′i] ∣∣ ≤ |αi − α′i||βi − β′i|O(log− 12 n)|ℓ(x) = 1]
≥ 1−O( 1 n2 )
• in (B2,2):
P[ ∣∣∆i − λ(βi − β′i)p
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ |αi − α′i||βi − β′i|O(log− 12 n)|ℓ(x) = 0]
≥ 1−O( 1 n2 )
P[ ∣∣∆i − λ(βi − β′i)q
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ |αi − α′i||βi − β′i|O(log− 12 n)|ℓ(x) = 1]
≥ 1−O( 1 n2 )
• in (B2,3):
P[ ∣∣∆i − λ(βi − β′i)p
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ |αi − α′i||βi − β′i|O(log− 12 n)|ℓ(x) = 0]
≥ 1−O( 1 n2 )
P[ ∣∣∆i − λ(βi − β′i)q
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ |αi − α′i||βi − β′i|O(log− 12 n)|ℓ(x) = 1]
≥ 1−O( 1 n2 ).
• in (B3): P[ ∣∣∆i∣∣ ≤ |αi − α′i||βi − β′i|O(log− 12 n)|ℓ(x) = 0 or 1] ≥ 1−O( 1n2 ).
Proof. The proof is similar as Theorem A.1
A.3 “HARMLESS TYPE” NEURONS
We have the following estimation of ∆i 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 (H1):
P[ ∣∣∆i − λ(βi − β′i)p
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ (αi − α′i)(βi − β′i)O(log− 12 n)|ℓ(x) = 0]
≥ 1−O( 1 n2 )
P[ ∣∣∆i − λ(βi − β′i)q
(p+ q)2 (pαi + qα
′ i) ∣∣ ≤ (αi − α′i)(βi − β′i)O(log− 12 n)|ℓ(x) = 1]
≥ 1−O( 1 n2 )
• in (H2): ∆i = 0 for both ℓ(x) = 0 and 1.
A.4 SEPARATION OF OUTPUT
Previous subsections have shown the concentration of ∆i for each type of neurons. For the i-th neuron, we write the concentrated value as mi0 if ℓ(x) = 0 and m i 1 if ℓ(x) = 1. From Theorem A.1, A.2 and A.3, we have the following result about the value of mi0 − mi1 by straightforward computation.
Corollary A.4. We have the following result about mi0 −mi1 for 1 ≤ i ≤ h:
• if the i-the neuron is of “good type”: in (G1) and (G2,1) : mi0 −mi1 = λ|αi − α′i||βi − β′i| ( p− q p+ q )2 in (G2,2) : mi0 −mi1 = λ|βi − β′i||pαi + qα′i|
p− q (p+ q)2
≥ λ 2 |αi − α′i||βi − β′i| ( p− q p+ q )2 in (G2,3) : mi0 −mi1 = λ|βi − β′i||pαi + qα′i|
p− q (p+ q)2
≥ λ|αi − α′i||βi − β′i| (p− q)Λ3 (p+ q)2 ,
where Λ3 = (1−log− 1 3 n)p2−q2
(1−log− 1 3 n)p+q
.
• if the i-the neuron is of “bad type”: in (B1) and (B2,1) : mi0 −mi1 = −λ|αi − α′i||βi − β′i| ( p− q p+ q )2 in (B2,2) : mi0 −mi1 = −λ|βi − β′i||pαi + qα′i|
p− q (p+ q)2
≥ −λ|αi − α′i||βi − β′i| (p− q)Λ3 (p+ q)2
in (B2,3) : mi0 −mi1 = −λ|βi − β′i||pαi + qα′i| p− q
(p+ q)2
≥ −λ|αi − α′i||βi − β′i| (p− q)Λ1 (p+ q)2
in (B3) : mi0 −mi1 = 0,
where Λ1 = (1+log− 1 3 n)p2−q2
(1+log− 1 3 n)p+q
,Λ3 = (1−log− 1 3 n)p2−q2
(1−log− 1 3 n)p+q
.
• if the i-the neuron is of “harmless type”:
in (H1) : mi0 −mi1 = λ|βi − β′i||pαi + qα′i| p− q
(p+ q)2
≥ λ|αi − α′i||βi − β′i| (p− q)Λ5 (p+ q)2
in (H2) : mi0 −mi1 = 0,
where Λ5 = pq log − 1 3
p+(1+log− 1 3 )q
.
B DYNAMICS OF PARAMETERS
We consider the cross-entropy loss in training. The loss on a particular vertex x is
L(x) = − logOℓ(x)(x),
where O0(x) and O1(x) are the first and second component of the output respectively, i.e.
O0(x) = exp(g0(x))
exp(g0(x)) + exp(g1(x)) , O1(x) =
exp(g1(x))
exp(g0(x)) + exp(g1(x)) .
For a given graph G generated by SBM, we set the objective function L(G) as the average loss over all the vertices with revealed labels2, i.e.
L(G) = 1 #{x ∈ G : ℓ(x) is revealed} ∑
x:ℓ(x) revealed
L(x).
We first show the partial derivatives of parameters.
Theorem B.1 (derivatives of parameters). For 1 ≤ i ≤ h, let x be a vertex, ℓ(x) its true label, L(x) = − logOℓ(x)(x), then
∂L ∂αi =
4
n2(p+ q)2 (βi − β′i)Z(−1)1−ℓ(x) ∑ y 1[y ∼ x]1[αity0 + α′it y 1 ≥ 0]t y 0
∂L ∂α′i =
4
n2(p+ q)2 (βi − β′i)Z(−1)1−ℓ(x) ∑ y 1[y ∼ x]1[αity0 + α′it y 1 ≥ 0]t y 1
∂L ∂βi =
4
n2(p+ q)2 Z(−1)1−ℓ(x) ∑ y 1[y ∼ x]ϕ(αity0 + α′it y 1)
∂L ∂β′i = − 4 n2(p+ q)2 Z(−1)1−ℓ(x) ∑ y 1[y ∼ x]ϕ(αity0 + α′it y 1)
∂L ∂b0 = (−1)1−ℓ(x)Z
∂L ∂b1 = (−1)ℓ(x)Z,
where Z = exp(g1−ℓ(x)(x))exp(g0(x))+exp(g1(x)) , t y 0 and t y 1 are the numbers of neighbors of y(including perhaps y itself) with revealed labels in class 0 and class 1 respectively.
Proof. We compute ∂L∂αi , ∂L ∂βi and ∂L∂b0 , others can be computed symmetrically. We have
L(x) = − logOℓ(x)(x) = log(exp(g0(x)) + exp(g1(x)))− gℓ(x)(x),
since Oj(x) = exp(gj(x))
exp(g0(x))+exp(g1(x)) , j = 0, 1. So
∂L ∂αi =
eg0(x) ∂g0(x)∂αi + e g1(x) ∂g1(x) ∂αi
eg0(x) + eg1(x) −
∂gℓ(x)(x)
∂αi = (−1)1−ℓ(x)Z (∂g0(x)
∂αi − ∂g1(x) ∂αi
) .
Since gj(x) = fj(x) + bj , ∂gj(x) ∂αi = ∂fj(x) ∂αi , j = 0, 1. By (2)
∂f0(x)
∂αi =
4
n2(p+ q)2 ∑ y 1[y ∼ x]βi1[αity0 + α′it y 1 ≥ 0]t y 0
∂f1(x)
∂αi =
4
n2(p+ q)2 ∑ y 1[y ∼ x]β′i1[αit y 0 + α ′ it y 1 ≥ 0]t y 0.
Therefore
∂L ∂αi =
4
n2(p+ q)2 (−1)1−ℓ(x)Z(βi − β′i) ∑ y 1[y ∼ x]1[αity0 + α′it y 1 ≥ 0]t y 0.
2We abuse the notation L for L(x) and L(G), but the meaning is clear from the context.
Next we compute ∂L∂βi . Similar as above, ∂L ∂βi
= (−1)1−ℓ(x)Z (∂f0(x)
∂βi − ∂f1(x)∂βi
) . By (2)
∂f0(x)
∂βi =
4
n2(p+ q)2 ∑ y 1[y ∼ x]ϕ(αity0 + α′it y 1)
∂f1(x)
∂αi = 0.
So ∂L
∂βi =
4
n2(p+ q)2 (−1)1−ℓ(x)Z ∑ y 1[y ∼ x]ϕ(αity0 + α′it y 1).
Lastly,
∂L ∂b0 = (−1)1−ℓ(x)Z
( ∂g0(x)
∂b0 − ∂g1(x) ∂b0 ) = (−1)1−ℓ(x)Z,
since ∂g0(x)∂b0 = 1, ∂g1(x) ∂b0 = 0.
In the following, we will use Theorem B.1 to analyze the dynamics of neurons of each type. As we can see, all of ∂L∂αi , ∂L ∂α′i , ∂L∂βi and ∂L ∂β′i
have the form Y Z. In order to estimate these derivatives, we show the concentration of Y and Z respectively. To estimate the concentration of Z, we need the concentration of output obtained in Section 4. For any ϵ > 0, we require the probability of concentration in (3) to be at least 1− ϵ̃, where ϵ̃ = o(ϵ). In particular, if we choose ϵ̃ = ϵ2, then we set 1−O( 1n ) ≥ 1− ϵ 2, i.e.
n ≥ Ω ( 1
ϵ
)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∣∣E[ ∂L∂b0 ]∣∣ < ϵ̃2 . Since E[ ∂L∂b0 ] = 12 (−E[Z|ℓ(x) = 0] + E[Z|ℓ(x) = 1])), we have∣∣E[Z|ℓ(x) = 0]− E[Z|ℓ(x) = 1]∣∣ < ϵ̃. (6) We have the following relation between µ0 and µ1. In the following, σ represents the sigmoid function: σ(x) = 11+e−x .
Proposition B.2. If ∣∣E[Z|ℓ(x) = 0]−E[Z|ℓ(x) = 1]∣∣ < ϵ̃, then |σ(−µ0)−σ(µ1)| ≤ σ′(µ0− δ)δ+ σ′(µ1 + δ)δ + 3ϵ̃, where δ is as shown in Corollary 4.2.
Proof. We have
Z = { σ(−∆), ℓ(x) = 0 σ(∆), ℓ(x) = 1
For ℓ(x) = 0, by Lagrange mean value theorem, |σ(−µ0)−Z| = |σ(−µ0)− σ(−∆)| = σ′(ξ)(∆− µ0), where ξ is between −µ0 and −∆. By Corollary 4.2 and the condition of n, |∆− µ0| ≤ δ with probability ≥ 1 − ϵ̃. From the remark following Corollary A.4, we have σ′(ξ) ≤ σ′(−µ0 + δ) = σ′(µ0 − δ),3 with probability ≥ 1− ϵ̃. Then we have
P[|σ(−µ0)− Z| ≤ σ′(µ0 − δ)δ|ℓ(x) = 0] ≥ 1− ϵ̃.
Since
E[Z|ℓ(x) = 0] = E[Z||σ(−µ0)− Z| ≤ σ′(µ0 − δ)δ]P[|σ(−µ0)− Z| ≤ σ′(µ0 − δ)δ] + E[Z||σ(−µ0)− Z| > σ′(µ0 − δ)δ]P[|σ(−µ0)− Z| > σ′(µ0 − δ)δ],
3σ′(x) is even.
then (note that 0 < Z < 1)
E[Z|ℓ(x) = 0] ≤ σ(−µ0) + σ′(µ0 − δ)δ + ϵ̃ and E[Z|ℓ(x) = 0] ≥ (σ(−µ0)− σ′(µ0 − δ)δ)(1− ϵ̃), i.e. E[Z|ℓ(x) = 0]− σ(−µ0) ≤ σ′(µ0 − δ)δ + ϵ̃ and
E[Z|ℓ(x) = 0]− σ(−µ0) ≥ −σ′(µ0 − δ)δ − ϵ̃(σ(−µ0)− σ′(µ0 − δ)δ) = −σ′(µ0 − δ)δ(1− ϵ̃)− ϵ̃σ(−µ0) ≥ −σ′(µ0 − δ)δ − ϵ̃.
So ∣∣E[Z|ℓ(x) = 0]− σ(−µ0)∣∣ ≤ σ′(µ0 − δ)δ + ϵ̃. Similarly ∣∣E[Z|ℓ(x) = 1]− σ(µ1)∣∣ ≤ σ′(µ1 + δ)δ + ϵ̃. By triangle inequality,∣∣σ(−µ0)− σ(µ1)∣∣ ≤ ∣∣σ(−µ0)− E[Z|ℓ(x) = 0]∣∣+ ∣∣E[Z|ℓ(x) = 0]− E[Z|ℓ(x) = 1]∣∣
+ ∣∣E[Z|ℓ(x) = 1]− σ(µ1)∣∣ ≤ σ′(µ0 − δ)δ + σ′(µ1 + δ)δ + 3ϵ̃.
From the proof above, we can directly obtain the following corollary about Z. Corollary B.3.
P[ ∣∣Z − E[Z|ℓ(x) = 0]∣∣ ≤ 2σ′(µ0 − δ)δ + ϵ̃|ℓ(x) = 0] ≥ 1− ϵ̃
P[ ∣∣Z − E[Z|ℓ(x) = 1]∣∣ ≤ 2σ′(µ1 + δ)δ + ϵ̃|ℓ(x) = 1] ≥ 1− ϵ̃.
In order to obtain the concentration of Z, we need to estimate σ′(µ0 − δ)δ and σ′(µ1 + δ)δ. The following proposition is based on the condition that |µ0 + µ1| ≥ 4δ. If |µ0 + µ1| < 4δ, set c := µ0 − µ1, we have µ0 > c2 − 2δ and µ1 < − c 2 + 2δ. Then the concentration of output shown in Corollary 4.2 can guarantee 1− ϵ accuracy of the model for any ϵ > 0. In fact, from |∆− µ0| < δ, we have ∆ > µ0 − δ > c2 − 3δ > 0, due to δ = o(c). So
P[∆ > 0|ℓ(x) = 0] ≥ P[|∆− µ0| < δ|ℓ(x) = 0] ≥ 1− ϵ̃. Similarly, P[∆ < 0|ℓ(x) = 1] ≥ P[|∆− µ0| < δ|ℓ(x) = 1] ≥ 1− ϵ̃. Since ϵ̃ = o(ϵ), the model achieves overall accuracy ≥ 1− ϵ. Proposition B.4. If |µ0 + µ1| ≥ 4δ, then σ′(µ0 − δ)δ = O(ϵ̃), σ′(µ1 + δ)δ = O(ϵ̃).
Proof. First, we estimate the lower bound of |σ(−µ0) − σ(µ1)| via the Fundamental Theorem of Calculus. We have |σ(−µ0)− σ(µ1)| = ∣∣ ∫ µ1 −µ0 σ ′(t) dt ∣∣.
If −µ0 < µ1 < 0, since µ0 + µ1 ≥ 4δ, we divide the interval [−µ0, µ1] into [−µ0,−µ0 + 2δ] ∪ [−µ0 + 2δ, µ1 − 2δ] ∪ [µ1 − 2δ, µ1] and estimate the lower bound of the integral. Since σ′(x) is increasing on (−∞, 0], we have∫ µ1
−µ0 σ′(t) dt ≥ σ′(−µ0) · 2δ + I1 + σ′(µ1 − 2δ) · 2δ, (7)
where I1 = ∫ µ1−2δ −µ0+2δ σ
′(t) dt. If µ1 < −µ0 < 0, similarly we have∫ −µ0 µ1 σ′(t) dt ≥ σ′(µ1) · 2δ + I2 + σ′(−µ0 − 2δ) · 2δ, (8)
where I2 = ∫ −µ0−2δ µ1+2δ
σ′(t) dt. We have a uniform lower bound from (7) and (8):∣∣∣∣ ∫ µ1 −µ0 σ′(t) dt ∣∣∣∣ ≥ σ′(−µ0 − 2δ) · 2δ + σ′(µ1 − 2δ) · 2δ + I, (9) where I = min{I1, I2}. Furthermore, by Proposition B.2,
|σ(−µ0)− σ(µ1)| ≤ σ′(µ0 − δ)δ + σ′(µ1 + δ)δ + 3ϵ̃. (10) Combine (9) and (10):
2σ′(−µ0 − 2δ)δ + 2σ′(µ1 − 2δ)δ ≤ σ′(−µ0 + δ)δ + σ′(µ1 + δ)δ + 3ϵ̃. (11) By Lagrange mean value theorem,
σ′(−µ0 − 2δ) = σ′(−µ0 + δ)− 3σ′′(ξ0)δ σ′(µ1 − 2δ) = σ′(µ1 + δ)− 3σ′′(ξ1)δ,
where ξ0 ∈ (−µ0 − 2δ,−µ0 + δ), ξ1 ∈ (µ1 − 2δ, µ1 + δ). Plug these into (11): σ′(µ0 − δ)δ + σ′(µ1 + δ)δ − 6δ2(σ′′(ξ0) + σ′′(ξ1)) ≤ 3ϵ̃. Since δ2(σ′′(ξ0) + σ′′(ξ1)) = o(σ′(µ0 − δ)δ) and o(σ′(µ1 + δ)δ), we have σ′(µ0 − δ)δ = O(ϵ̃) σ′(µ1 + δ)δ = O(ϵ̃).
Combine Proposition B.4 and Corollary B.3, we have the following concentration of Z. Proposition B.5.
P[ ∣∣Z − E[Z|ℓ(x) = 0]∣∣ ≤ O(ϵ̃)|ℓ(x) = 0] ≥ 1− ϵ̃
P[ ∣∣Z − E[Z|ℓ(x) = 1]∣∣ ≤ O(ϵ̃)|ℓ(x) = 1] ≥ 1− ϵ̃.
Under the condition of balanced performance, we have the following corollary about the concentration of Z independent of the label of x. Corollary B.6. If ∣∣E[ ∂L∂b0 ]∣∣ ≤ ϵ̃2 , then P[∣∣Z − E[Z]∣∣ ≤ O(ϵ̃)] ≥ 1− ϵ̃. Proof. Since E[ ∂L∂b0 ] =
1 2 (E[Z|ℓ(x) = 0]− E[Z|ℓ(x) = 1]), we have∣∣E[Z|ℓ(x) = 0]− E[Z|ℓ(x) = 1]∣∣ ≤ ϵ̃.
On the other hand,
E[Z] = 1
2
( E[Z|ℓ(x) = 0] + E[Z|ℓ(x) = 1] ) .
So we have ∣∣E[Z]− E[Z|ℓ(x) = 0]∣∣ ≤ ϵ̃2 . By Proposition B.5, P[|Z − E[Z]| ≤ O(ϵ̃)] ≥ 1− ϵ̃.
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 ≥ 1−O( 1n ), we have 4
1. If αi > α′i > 0 or αi > 0 > α ′ i, |αiα′i | ≥ p q (1 + log − 13 n), then∣∣∣∣ ∂L∂αi + (βi − β′i)λ2 ( p− q p+ q )2 E[Z] ∣∣∣∣ ≤ |βi − β′i|E[Z]O(log− 12 n) (12)∣∣∣∣ ∂L∂α′i − (βi − β′i)λ2 ( p− q p+ q )2 E[Z]
∣∣∣∣ ≤ |βi − β′i|E[Z]O(log− 12 n) (13)∣∣∣∣ ∂L∂βi + (αi − α′i)λ2 ( p− q p+ q )2 E[Z]
∣∣∣∣ ≤ |αi − α′i|E[Z]O(log− 12 n). (14) 4Since ∂L
∂β′i = − ∂L ∂βi (see Theorem B.1), we only need to estimate ∂L ∂βi .
2. If αi > 0 > α′i, |αiα′i | ∈ [ q p (1 + γ), p q (1 − log − 13 n)], where γ ∈ [log− 1 3 n, (pq ) 2(1 −
log− 1 3 n)− 1], then∣∣∣∣ ∂L∂αi + (βi − β′i)λp(p− q)2(p+ q)2 E[Z] ∣∣∣∣ ≤ |βi − β′i|E[Z]O(log− 12 n) (15)∣∣∣∣ ∂L∂α′i + (βi − β′i)λq(p− q)2(p+ q)2 E[Z] ∣∣∣∣ ≤ |βi − β′i|E[Z]O(log− 12 n) (16)∣∣∣∣ ∂L∂βi + λ(p− q)(pαi + qα ′ i) 2(p+ q)2 E[Z]
∣∣∣∣ ≤ |αi − α′i|E[Z]O(log− 12 n). (17) 3. If αi > 0 > α′i, |αiα′i | ∈ ( p q (1− log − 13 n), pq (1 + log − 13 n)), then
∂L ∂βi ∈ [−(αi − α′i)E[Z] ( λ(p− q)Λ1 2(p+ q)2 +O(log− 1 2 n) ) ,
− (αi − α′i)E[Z] ( λ(p− q)(Λ3 − Λ2)
2(p+ q)2 −O(log− 1 2 n)
) ], (18)
where Λ1 = (1+log− 1 3 n)p2−q2
(1+log− 1 3 n)p+q
,Λ2 = pq log− 1 3 n
(1+log− 1 3 n)p+q
and Λ3 = (1−log− 1 3 n)p2−q2
(1−log− 1 3 n)p+q
;
• if βi > β′i,
∂L ∂αi ∈ [−(βi − β′i)E[Z] ( λp(p− q) 2(p+ q)2 +O(log− 1 2 n) ) ,
− (βi − β′i)E[Z] ( λ
2 ( p− q p+ q )2 −O(log− 1 2 n) ) ] (19)
∂L ∂α′i ∈ [−(βi − β′i)E[Z] ( λq(p− q) 2(p+ q)2 +O(log− 1 2 n) ) ,
(βi − β′i)E[Z] ( λ
2 ( p− q p+ q )2 +O(log− 1 2 n) ) ] (20)
∂L ∂αi − ∂L ∂α′i ∈ [−(βi − β′i)E[Z]
( λ ( p− q p+ q )2 +O(log− 1 2 n) ) ,
− (βi − β′i)E[Z] ( λ
2 ( p− q p+ q )2 −O(log− 1 2 n) ) ], (21)
• if βi ≤ β′i,
∂L ∂αi ∈ [−(βi − β′i)E[Z]
( λ
2 ( p− q p+ q )2 −O(log− 1 2 n) ) ,
− (βi − β′i)E[Z] ( λp(p− q) 2(p+ q)2 +O(log− 1 2 n) ) ] (22)
∂L ∂α′i ∈ [−(βi − β′i)E[Z]
( λ
2 ( p− q p+ q )2 +O(log− 1 2 n) ) ,
(βi − β′i)E[Z] ( λq(p− q) 2(p+ q)2 +O(log− 1 2 n) ) ] (23)
∂L ∂αi − ∂L ∂α′i ∈ [−(βi − β′i)E[Z]
( λ
2 ( p− q p+ q )2 −O(log− 1 2 n) ) ,
− (βi − β′i)E[Z] ( λ ( p− q p+ q )2 +O(log− 1 2 n) ) ] (24)
4. If αi > 0 > α′i, ∣∣αi α′i ∣∣ ≤ qp (1 + log− 13 n), βi < β′i, then ∂L
∂αi − ∂L ∂α′i ≥ −|βi − β′i|O(ϵ̃) (25)
∂L ∂βi ≤ O(ϵ̃). (26)
Proof. We show the proof for item 1, other items can be proved similarly. Since L(G) is the average of the losses over revealed vertices, we first show the concentration of ∂L(x)∂αi , then we show the concentration of ∂L(G)∂αi using union bound. Since
∂L(x)
∂αi = (−1)1−ℓ(x)4(βi − β′i)Z ∑ y 1[y ∼ x]1[αity0 + α′it y 1 ≥ 0]t y 0 n2(p+ q)2 ,
we first show the concentration of Y := (−1)1−ℓ(x) ∑
y∼x 41[αit
y 0+α ′ it y 1≥0]t y 0
n2(p+q)2 using the method of averaged bounded difference. Similar as the proof of Theorem A.1, let Yj = (−1)1−ℓ(x) 41[αit yj 0 +α ′ it yj 1 ≥0]t yj 0
n2(p+q)2 . Based on Condition (Cond), for ℓ(x) = 0, |Yj + 2λp n(p+q)2 | ≤ O(log−
7 2 n) for ℓ(yj) = 0. Similar results hold for ℓ(yj) = 1, ℓ(x) = 1. So for any ak, a′k,∣∣∣∣E[∑
j Yj |Y1, · · · , Yk−1, Yk = ak]− E[ ∑ j Yj |Y1, · · · , Yk−1, Yk = a′k] ∣∣∣∣ ≤ (αi − α′i)O(log− 72 n).
By method of averaged bounded difference, for ℓ(x) = 0, P[ ∣∣∣∣ ∑ ℓ(yj)=0 Yj + λ ( p p+ q )2∣∣∣∣ ≤ O(log− 12 n)] ≥ 1− exp (−2 log3 n) ≥ 1− 1n2 . Similarly
P[ ∣∣∣∣ ∑ ℓ(yj)=1 Yj + λ ( q p+ q )2∣∣∣∣ ≤ O(log− 12 n)] ≥ 1− 1n2 . Hence
P[ ∣∣∣∣Y + λ(p2 + q2)(p+ q)2 ∣∣∣∣ ≤ O(log− 12 n)] ≥ 1− 1n2 . By Corollary B.6, P[|Z − E[Z]| ≤ O(ϵ̃)] ≥ 1− ϵ̃, so we have
P[ ∣∣∣∣∂L(x)∂αi + (βi − β′i)λ p 2 + q2 (p+ q)2 E[Z] ∣∣∣∣ ≤ |βi − β′i|E[Z]O(log− 12 n)|ℓ(x) = 0] ≥ 1−O( 1n2 ). For ℓ(x) = 1, similarly we have
P[ ∣∣∣∣∂L(x)∂αi − (βi − β′i)λ 2pq(p+ q)2E[Z] ∣∣∣∣ ≤ |βi − β′i|E[Z]O(log− 12 n)|ℓ(x) = 0] ≥ 1−O( 1n2 ). 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 ηk denote the learning rate at the k-th epoch, Z(k) be the value of Z at the k-th epoch, α(k)i be the value of αi at the k-th epoch, similar for α ′(k) i , β (k) i and β ′(k) i . In particular, α (0) i , α ′(0) i , β (0) i and β ′(0) i represent the values at initialization.
B.1 “GOOD TYPE” NEURONS
In this section, we show that “good type” neurons stay in the “good type” regime throughout coordinate descent (Theorem B.8) using Theorem B.7.
Theorem B.8. “Good type” neurons are preserved in the “good type” throughout coordinate descent with probability ≥ 1−O( 1n2 ) over the SBM randomness.
Proof. As shown in Section 4, “good type” regime is composed of (G1) and (G2), we show the dynamics of neurons in (G1) and (G2) respectively.
Assume that neuron (α(k)i , α ′(k) i , β (k) i , β ′(k) i ) is in (G1), we show that it either stays in (G1) or moves into (G2) throughout coordinate descent. In fact, by (14), with probability ≥ 1− O( 1n2 ), ∂L
∂β (k) i
<
0 < ∂L ∂β
′(k) i
, so β(k+1)i > β (k) i , β ′(k+1) i < β ′(k) i and hence β (k+1) i − β ′(k+1) i > β (k) i − β ′(k) i > 0. By
(12) and (13), ∂L ∂α
(k) i
< 0 < ∂L ∂α
′(k) i
, so α(k+1)i > α (k) i , α ′(k+1) i < α ′(k) i . If α ′(k+1) i > 0, this neuron
stays in (G1). If α ′(k+1) i < 0, since∣∣∣∣ α(k+1)i
α ′(k+1) i
∣∣∣∣ = ∣∣∣∣∣ α (k) i − ηk ∂L∂α(k)i
α ′(k) i − ηk ∂L∂α′(k)i ∣∣∣∣∣ > 1, the neuron moves into (G2).
Assume that neuron is in (G2), we also show that it either moves into (G1) or stays in (G2). As shown in section 3.2, (G2) = (G2,1) ∪ (G2,2) ∪ (G2,3). If the neuron is in (G2,1), again by (12), (13) and (14), α(k+1)i > α (k) i > 0 > α ′(k) i > α ′(k+1) i , ∣∣ α(k+1)i α
′(k+1) i ∣∣ > 1, β(k+1)i > β(k)i > β′(k)i > β′(k+1)i , so the neuron stays in G2,2. If the neuron is in G2,2, by (15), (16) and (17), ∂L
∂β (k) i
< 0 < ∂L ∂β
′(k) i
,
so β(k+1)i > β ′(k+1) i . Also, ∂L
∂α (k) i
< ∂L ∂α
′(k) i
< 0, so α(k+1)i > α ′(k+1) i , ∣∣ α(k+1)i α
′(k+1) i
∣∣ > ∣∣ α(k)i α
′(k) i ∣∣ > 1. If α′(k+1)i < 0, the neuron stays in G2. If α ′(k+1) i > 0, it moves into G1. If the neuron is in G2,3, by (18) and (21), ∂L ∂β
(k) i
< 0 < ∂L ∂β
′(k) i
, ∂L ∂α
(k) i
− ∂L ∂α
′(k) i
< 0, so β(k+1)i > β (k) i > β ′(k) i >
β ′(k+1) i , α (k+1) i − α ′(k+1) i > α (k) i − α ′(k) i > 0. By (19) and (20),
∂L ∂αi ≤ −(βi − β′i)E[Z]
( λ
2 ( p− q p+ q )2 −O(log− 1 2 n) ) ,
∂L ∂α′i ≤ (βi − β′i)E[Z]
( λ
2 ( p− q p+ q )2 +O(log− 1 2 n) ) .
Similar as in (G2,2), if α ′(k+1) i < 0, the neuron stays in (G2). If α ′(k+1) i > 0, it moves into (G1).
B.2 “BAD TYPE” NEURONS
As shown in Section 4, neurons of “bad type” consist of two cases: B1 and B2, where B2 = B2,1∪ B2,2 ∪ B2,3 ∪ B3. Since the output in B3 is concentrated at 0 (see Theorem A.2), we don’t need to worry if neurons move into this region. Neurons in B1 ∪ B2,1 ∪ B2,2 ∪ B2,3 might exit “bad type” regime and become “harmless” or “good” (if the neuron becomes order-aligned), which will do no harm to the performance of the model. If they stay in B1 ∪ B2,1 ∪ B2,2 ∪ B2,3, the following theorem shows that the separation mi0 −mi1 can be upper bounded by initialization. In fact, Theorem A.4 shows that mi0 −mi1 is proportional to |αi − α′i||βi − β′i|. The next theorem shows that both |αi−α′i| and |βi−β′i| shrink throughout coordinate descent. The worst situation is that the magnitude of |αi − α′i| and |βi − β′i| of neurons in B3 increase and move into B1 or B2 at certain epoch. From Theorem B.7 we see that the magnitude can only increase by a limited rate (we can see this more explicitly in Theorem 6.2).
Theorem B.9. If (α(k)i , α ′(k) i , β (k) i , β ′(k) i ) is in B1 ∪ B2,1 ∪ B2,2 ∪ B2,3 then with probability ≥ 1−O( 1n2 ) over the SBM randomness, ∣∣α(k+1)i −α′(k+1)i ∣∣ ≤ ∣∣α(k)i −α′(k)i ∣∣, ∣∣β(k+1)i −β′(k+1)i ∣∣ ≤∣∣β(k)i − β′(k)i ∣∣.
Proof. In B1 and B2,1, by (12) and (13), ∂L ∂α
(k) i
> 0 > ∂L ∂α
′(k) i
, then α(k+1)i < α (k) i , α ′(k+1) i >
α ′(k) i , so |α (k+1) i − α ′(k+1) i | ≤ |α (k) i − α ′(k) i |. Similarly, by (14), ∂L∂β(k)i = − ∂L ∂β ′(k) i < 0, so |β(k+1)i − β ′(k+1) i | ≤ |β (k) i − β ′(k) i | (Note that α (k) i > α ′(k) i , β (k) i < β ′(k) i ).
In B2,2, from (15) and (16), we have ∂L ∂α
(k) i
> ∂L ∂α
′(k) i
> 0, so |α(k+1)i − α ′(k+1) i | ≤ |α (k) i − α ′(k) i |.
On the other hand, ∂L ∂β
(k) i
< 0 < ∂L ∂β
′(k) i
, so β(k+1)i > β (k) i , β ′(k+1) i < β ′(k) i and |β (k+1) i − β ′(k+1) i | ≤
|β(k)i − β ′(k) i |. In B2,3, by (24), ∂L∂α(k)i − ∂L ∂α ′(k) i > 0, so |α(k+1)i −α ′(k+1) i | ≤ |α (k) i −α ′(k) i |. By (18),
∂L
∂β (k) i
< 0 < ∂L ∂β
′(k) i
, so |β(k+1)i − β ′(k+1) i | ≤ |β (k) i − β ′(k) i |.
B.3 “HARMLESS TYPE” NEURONS
Section 4 shows that there are two cases of “harmless type”: H1 and H2. For neurons in H1, the derivatives of parameters are estimated in (15), (16) and (17) (same as in G2,2). We can have similar analysis as in G2,2 and show that the inequality αi > 0 > α′i, βi > β
′ i can be preserved. Moreover∣∣αi
α′i ∣∣ increases. So the neurons either stay in H1 or become “good type” if ∣∣αiα′i ∣∣> 1. In particular, neurons in H1 do no harm to the performance of the model.
For neurons in H2, 1[αit y 0 + α ′ it y 1 ≥ 0] = 0, so the derivatives are all equal to 0. Therefore they are never updated. Meanwhile they don’t affect the performance of the model since ϕ(αit y 0 + α ′ it y 1) = 0 and ∆i = 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[∆ < 0|ℓ(x) = 0] ≥ 4ϵ, (27)
then
E[Z|ℓ(x) = 0] = E[Z|ℓ(x) = 0,∆ < 0]P[∆ < 0|ℓ(x) = 0] + E[Z|ℓ(x) = 0,∆ ≥ 0]P[∆ ≥ 0|ℓ(x) = 0]
≥ 1 2 · 4ϵ = 2ϵ. (28)
Furthermore, we claim that µ0 < δ. In fact, if µ0 ≥ δ, since P[|∆− µ0| ≤ δ|ℓ(x) = 0] ≥ 1− ϵ by Corollary 4.2, and ∆ ≥ µ0 − δ ≥ 0, we have
P[∆ ≥ 0|ℓ(x) = 0] ≥ P[|∆− µ0| ≤ δ|ℓ(x) = 0] ≥ 1− ϵ,
i.e. P[∆ < 0|ℓ(x) = 0] ≤ ϵ, which contradicts (27). Let c := µ0 − µ1, then µ1 = µ0 − c < δ − c. Again, by Corollary 4.2, for ℓ(x) = 1,∆ < µ1 + δ with probability ≥ 1− ϵ, we have Z = σ(∆) < σ(µ1 + δ) < σ(−c+ 2δ). Then
E[Z|ℓ(x) = 1] = E[Z|ℓ(x) = 1, |∆− µ1| < δ]P[|∆− µ1| < δ|ℓ(x) = 1] + E[Z|ℓ(x) = 1, |∆− µ1| ≥ δ]P[|∆− µ1| ≥ δ|ℓ(x) = 1] < σ(−c+ 2δ) · 1 + 1 · ϵ
< σ ( − c
2
) + ϵ.
The last step is due to δ = o(c). Since σ(− c2 ) < ϵ 2 ,E[Z|ℓ(x) = 1] < 3ϵ 2 . Combine with (28),∣∣E[Z|ℓ(x) = 0]− E[Z|ℓ(x) = 1]∣∣ > ϵ
2 . On the other hand, ∣∣E[ ∂L∂b0 ]∣∣ < ϵ4 implies∣∣E[Z|ℓ(x) = 0]− E[Z|ℓ(x) = 1]∣∣ < ϵ
2 ,
which is a contradiction. So P[∆ < 0|ℓ(x) = 0] < 4ϵ. Similarly, P[∆ > 0|ℓ(x) = 1] < 4ϵ.
Proof of Theorem 6.2. If the i-th neuron is of “good type”, from Corollary A.4, we find a uniform lower bound of mi0 −mi1 in “good type” regimes. We have min{ p−q 2 ,Λ3} = p−q 2 . Next we estimate αi − α′i and βi − β′i. Let A (k) i := α (k) i − α ′(k) i , B (k) i := β (k) i − β ′(k) i . We have
A (k) i = α (k) i − α ′(k) i = α (k−1) i − α ′(k−1) i − ηk
( ∂L
∂α (k−1) i
− ∂L ∂α
′(k−1) i ) B
(k) i = β (k) i − β ′(k) i = β (k−1) i − β ′(k−1) i − ηk
( ∂L
∂β (k−1) i
− ∂L ∂β
′(k−1) i
) ,
By Theorem B.7, in G1 and G2,1, with probability ≥ 1−O( 1n ),
∂L ∂αi − ∂L ∂α′i ≤ −(βi − β′i)E[Z] (( p− q p+ q )2 λ−O(log− 1 2 n)) ) ≤ −(βi − β′i)E[Z] λ 2 ( p− q p+ q )2 ∂L
∂βi − ∂L ∂β′i ≤ −(αi − α′i)E[Z] (( p− q p+ q )2 λ−O(log− 1 2 n) ) ≤ −(αi − α′i)E[Z] λ 2 ( p− q p+ q )2 so
A (k) i = A (k−1) i − ηk
( ∂L
∂α (k−1) i
− ∂L ∂α
′(k−1) i
) ≥ A(k−1)i + ηkE[Z (k)] λ
2 ( p− q p+ q )2 B (k−1) i
= A (k−1) i +
λ
2 ( p− q p+ q )2 B (k−1) i
B (k) i = B (k−1) i − ηk
( ∂L
∂β (k−1) i
− ∂L ∂β
′(k−1) i
) ≥ B(k−1)i + ηkE[Z (k)] λ
2 ( p− q p+ q )2 A (k−1) i
= B (k−1) i +
λ
2 ( p− q p+ q )2 A (k−1) i .
In matrix form: ( A
(k) i B (k) i
) ⪰ ( 1 λ2 ( p−q p+q )2 λ 2 ( p−q p+q )2 1 )( A (k−1) i B (k−1) i ) (29)
Similarly, in G2,2: ( A
(k) i B (k) i
) ⪰ ( 1 λ4 ( p−q p+q )2 λ 8 ( p−q p+q )2 1 )( A (k−1) i B (k−1) i ) (30)
in G2,3: ( A
(k) i B (k) i
) ⪰ ( 1 λ4 ( p−q p+q )2 λ(Λ3−Λ2) 2(p−q) ( p−q p+q )2 1 )( A (k−1) i B (k−1) i ) (31)
where Λ2 = pq log − 1 3 n
(1+log− 1 3 n)p+q
, Λ3 = (1−log− 1 3 n)p2−q2
(1−log− 1 3 n)p+q
. A uniform relation among (29), (30) and (31)
can be given by (30). By eigenvalue decomposition, we have
A (k) i B (k) i ≥
1
4
( 1 + √ 2λ
8 ( p− q p+ q )2)2k( 2− 1 8A (0) i + 2 1 8B (0) i )2 ≥ A(0)i B (0) i ( 1 + √ 2λ
8 ( p− q p+ q )2)2k .
Therefore we have a uniform lower bound of mi0 −mi1 at the k-th epoch in “good type” regime:
mi0 −mi1 ≥ A (0) i B (0) i
λ
2 ( p− q p+ q )2( 1 + √ 2λ 8 ( p− q p+ q )2)2k .
Next we consider the “bad type” regime. By Corollary A.4, we have lower bound of mi0 −mi1 in B1, B2 and B3 respectively. By Theorem B.9, in B1 and B2, |αi − α′i| and |βi − β′i| shrink. Moreover, since Λ1 > Λ35, we have a uniform lower bound of mi0 −mi1 in B1 and B2:
mi0 −mi1 ≥ − ∣∣A(0)i B(0)i ∣∣λ(p− q)Λ1(p+ q)2 ≥ −∣∣A(0)i B(0)i ∣∣λp(p− q)(p+ q)2 ,
since Λ1 = (1+log− 1 3 n)p2−q2
(1+log− 1 3 n)p+q
≤ 2p 2−q2
2p+q ≤ p.
Next we show that |αi − α′i| and |βi − β′i| can only increase by a limited rate in B3. From item 4 of Theorem B.7, we have
∂L ∂αi − ∂L ∂α′i ≥ −|βi − β′i|O(ϵ̃)
∂L ∂βi − ∂L ∂β′i = 2 ∂L ∂βi ≤ O(ϵ̃).
Therefore (note that βi < β′i)
A (k) i ≤ A (k−1) i + ηk|B (k−1) i |O(ϵ̃)
|B(k)i | ≤ |B (k−1) i |+ ηkO(ϵ̃).
Since E[Z(k)] ≥ Ω(ϵ)6, and ϵ̃ = o(ϵ), ϵ2 = O( 1n ), so ηkO(ϵ̃) ≤ ηkE[Z (k)] 1n = 1 n . Suppose A (k) i ≥ O(1), otherwise, A (k) i and |B
(k) i | increase by an even smaller rate. So we have(
A (k) i
|B(k)i | ) ⪯ ( 1 1n 1 n 1 )( A (k−1) i |B(k−1)i | ) .
By eigenvalue decomposition, we have
|A(k)i B (k) i | ≤
1 2 (1 + 1 n )2k ( |A(0)i |+ |B (0) i | )2 ≤ k((A(0)i )2 + (B(0)i )2) (n → ∞).
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, we have
E[(α− α′)2] = E[(β − β′)2] = 2, Var[(α− α′)2] = Var[(β − β′)2] = 8.
By Chebyshev’s inequality we have
P[ h∑
i=1
(αi − α′i)2 + (βi − β′i)2 ≤ 5h] ≥ 1−O ( 1 h ) .
5 xp2−q2 xp+q
is monotonically increasing. 6Otherwise, the model already achieves high accuracy, see the proof of Theorem 2.2
For neurons initialized as “good type”, we have
E[α− α′|α > α′, α+ α′ > 0] = 2√ π
Var[α− α′|α > α′, α+ α′ > 0] = 2− 1 4π
E[β − β′|β > β′] = 1√ π
Var[β − β′|β > β′] = 2− 1 π .
Let ρ denote the probability that a neuron is initialized as “good type”. By G1, G2 and symmetry, ρ = 2P[α > α′, α+ α′ > 0, β > β′]. Since
P[α > α′, α+ α′] = 1
4 , P[β > β′] =
1 2 ,
we have ρ = 14 . By Chernoff bound, P[hg ≥ ρ 2h] ≥ 1−exp (−
ρ2
4 h), so P[hg ≥ h 8 ] ≥ 1−exp (− h 64 ).
Also by Chebyshev’s inequality,
P[ ∑
the i-th neuron initialized as “good type”
|αi − α′i||βi − β′i| ≥ hg ( 1 2π − k )∣∣hg ≥ h 8 ] ≥ 1− 4− 14π2 hgk2 .
Set k = 110π ,
P[ ∑
the i-th neuron initialized as “good type”
|αi − α′i||βi − β′i| ≥ h
80 ∣∣hg ≥ h 8 ] ≥ 1−O ( 1 h ) .
So we have
P[ ∑
the i-th neuron initialized as “good type”
|αi − α′i||βi − β′i| ≥ h
80 ]
≥ P[ ∑
the i-th neuron initialized as “good type”
|αi − α′i||βi − β′i| ≥ h
80 ∣∣hg ≥ h 8 ]P[hg ≥ h 8 ]
≥ ( 1−O ( 1 h )) (1− exp ( − h 64 ) )
≥ 1−O ( 1 h ) .
D EXPERIMENTS ON DYNAMICS OF HIDDEN NEURONS
This experiment verifies our argument in Sections B.1, B.2, B.3 and Theorem 6.2 about the dynamics of hidden neurons. We set h = 5, λ = 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 4, with each row corresponding to one hidden neuron. In each plot, x-axis represents epoch and y-axis represents the value of neurons. The first column depicts αi and α′i, the second column |αiα′i |, the third column |αi −α ′ i|, the fourth column βi, β ′ i and the last column |βi − β′i|. As shown in the figure, the first, second and fourth neurons are of “good" type satisfying (G2). Throughout training these neurons are preserved as “good" type: they’re order-aligned, |αiα′i | is lowered bounded by 1, and both |αi − α ′ |, |βi − β ′ i| keeps increasing. All of these verify our argument in B.1. The third neuron is “harmless" satisfying (H2). As shown
in B.3, this neuron isn’t updated and doesn’t make contribution to the output. The fifth neuron is of “bad" type satisfying (B2). Although |αi −α′i| and |βi − β′i| increase, but by comparing with the first, second and fourth row (“good" neurons), they increase at a much smaller. This verifies our result in Theorem 6.2.
E TABLE OF NOTATIONS
We list the notations used in this paper for readers’ convenience.
Notation Definition
n number of vertices in a graph p probability of intra-community connection q probability of cross-community connection a parameter for p with p = a log
3 n n
b parameter for q with q = b log 3 n n λ probability of revealing the label of a vertex
ℓ(x) label of vertex x A adjacency matrix of a graph Â normalized adjacency matrix with self loop Â = 2n(p+q) (A+ I) X input feature of a graph W (0) trainable weights in the first layer of GCN W (1) trainable weights in the second layer of GCN B bias matrix of GCN with each row of B being [b0, b1] b0 bias in the first component b1 bias in the second component h number of hidden features f0 logit in the first component without bias f1 logit in the second component without bias g0 logit in the first component, g0 = f0 + b0 g1 logit in the second component, g1 = f1 + b1 ∆ difference between logit, ∆ = g0 − g1 = f0 − f1 + b0 − b1

Review summaries:
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.

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. 

In this paper, the authors present the first provable guarantees for Graph Convolutional Networks (GCNs) for semi-supervised community 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.