Effects of Graph Convolutions in Multi-layer Networks
Authors: Aseem Baranwal
Kimon Fountoulakis
Aukosh Jagannath
Venue: ICLR 2023 notable top 25% (2023)
Keywords: graph neural networks
node classification
classification threshold
contextual stochastic block model

Abstract: Graph Convolutional Networks (GCNs) are one of the most popular architectures that are used to solve classification problems accompanied by graphical information. We present a rigorous theoretical understanding of the effects of graph convolutions in multi-layer networks. We study these effects through the node classification problem of a non-linearly separable Gaussian mixture model coupled with a stochastic block model. First, we show that a single graph convolution expands the regime of the distance between the means where multi-layer networks can classify the data by a factor of at least $1/\sqrt[4]{\rm deg}$, where ${\rm deg}$ denotes the expected degree of a node. Second, we show that with a slightly stronger graph density, two graph convolutions improve this factor to at least $1/\sqrt[4]{n}$, where $n$ is the number of nodes in the graph. Finally, we provide both theoretical and empirical insights into the performance of graph convolutions placed in different combinations among the layers of a neural network, concluding that the performance is mutually similar for all combinations of the placement. We present extensive experiments on both synthetic and real-world data that illustrate our results.

Published as a conference paper at ICLR 2023
EFFECTS OF GRAPH CONVOLUTIONS IN MULTI-LAYER NETWORKS
Aseem Baranwal*
Kimon Fountoulakis'
Aukosh Jagannath'
ABSTRACT
Graph Convolutional Networks (GCNs) are one of the most popular architectures that are used to solve classification problems accompanied by graphical infor- mation. We present rigorous theoretical understanding of the effects of graph convolutions in multi-layer networks. We study these effects through the node classification problem of a non-linearly separable Gaussian mixture model coupled with stochastic block model. First, we show that a single graph convolution expands the regime of the distance between the means where multi-layer networks can classify the data by factor of at least 1/ deg, where deg denotes the expected degree node. Second, we show that with a slightly stronger graph density, two graph convolutions improve this factor to at least 1/ /n, where is the number of nodes in the graph. Finally, we provide both theoretical and empirical insights into the performance of graph convolutions placed in different combinations among the layers of a neural network, concluding that the performance is mutually similar for all combinations of the placement. We present extensive experiments both synthetic and real-world data that illustrate our results.
INTRODUCTION
large amount of interesting data and the practical challenges associated with them are defined in the setting where entities have attributes well information about mutual relationships. Tra- ditional classification models have been extended to capture such relational information through graphs (Hamilton, 2020), where each node has individual attributes and the edges of the graph capture the relationships among the nodes. A variety of applications characterized by this type of graph-structured data include works in the areas of social analysis (Backstrom & Leskovec 201 1), recommendation systems (Ying et al. (2018). computer vision (Monti et al.) 2017). study of the prop- erties of chemical compounds (Gilmer al. 2017 Scarselli al. 2009), statistical physics (Bapst ct al. 2020 Battaglia et al. 2016), and financial forensics (Zhang et al. 2017 Weber et al. (011)).
The most popular learning models for relational data use graph convolutions (Kipf & Welling 2017 where the idea is to aggregate the attributes of the set of neighbours of a node instead of only util utilizing its own attributes. Despite several empirical studies of various GCN-type models (Chen al. 2019 Ma et al. 2022) that demonstrate an improvement in the performance of traditional classification methods such as MIPs,, there has been limited progress in the theoretical understanding of the benefits of graph convolutions in multi-layer networks in terms of improving node classification tasks.
Related work. The capacity of a graph convolution for one-layer networks is studied in Baran wal et al. (2021). along with its duitr--distriuution (OoD) generalization potential. A more recent work (Wu et al. 2022) formulates the node-level OoD problem, and develops a learning method that facilitates GNNs to leverage invariance principles for prediction. In Gasteiger al. (2019), the authors utilize a propagation scheme based on personalized PageRank to construct model that outperforms several GCN-like methods for suni-supervieed classification. Through their algorithm, APPNP, they show that placing power iterations at the last layer of an MLP achieves state of the art performance. Our results align with this observation.
David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada.
(a seem. ba ranwal, mon. Fountoull i | @eeawwerrr 1oo.c ca Department of Statistics and Actuarial Science, Department of Applied Mathematics, University of Waterloo, Waterloo, Canada, a aesgaanntt@wwater11

---

Published as a conference paper at ICLR 2023
There exists large amount of theoretical work on unsupervised learning for random graph models where node features are absent and only relational information is available (Decelle et al. 2011
Massoulie 2014 Mossel et al. 20188; 2015; Abbe & Sandon 2013 Abbe et al.. 2015] Bordenave
et al.
2015; Deshpande et al.) 2015; | Montanari & Sen 2016 Banks et al. 2016; Abbe & Sandon 2022). For a comprehensive survey,
2018
Li et al. 2019| Kloumann et al. 2017 Gaudio et al.
see Abbe (2018) Moore (2017). For data models which have node features coupled with relational information, several works have studied the semi-supervised node classification problem, see, for example, SScaseell et al. ) Cheng et al. (201T); Gilbert et al. [ Dang & Viennet (2012); Günnemann al. (2013) ; Yang et al. (201 3 Hamilton et (201)) : [im et al. (2019); Mehta et al.]
(2019); Chien et al. (2022); Yan et al. (2021). These papers provide good empirical insights into
the merits of graph structure the data. We complement these studies with theoretical results that
explain the effects of graph convolutions in multi-layer network.
In Deshpande et al. (2018): 8): Lu & Sen (2020), the authors explore the fundamental thresholds for the classification of a substantial fraction of the nodes with linear sample complexity and large but finite degree. Another relatively recent work (Hou et al. 2020) proposes two graph smoothness metrics for measuring the benefits of graphical information, along with new attention-based framework. In Fountoulakis et al. (2022). the authors provide a theoretical study of the graph attention mechanism (GAT) and identify the regimes where the attention mechanism is (or is not) beneficial to node- classification tasks. Our study focuses on convolutions instead of attention-based mechanisms. Several works have studied the expressive power and extrapolation of GNNs, along with the oversmoothing phenomenon (see, for c.g., Balciiaa et al. (2021); Xu et al. (2021): Oono & Suzuki] (020)) Li et al. (2018). Some other works have also studied the homophily and heterophily problem GNNs (Luan et al., 2021 Ma et al. 2022). However, our focus is to draw comparison of the benefits and limitations of graph convolutions with those of a traditional MLP that does not utilize relational information. Similar to Wei et al. (2022). our setting is immune to the heterophily problem, and the focus of our study is on regimes where oversmoothing does not occur.
To the best of our knowledge, this area of research still lacks theoretical guarantees that explain when and why graphical data, and in particular, graph convolutions, can boost traditional multi- layer networks to perform better nods-classification tasks. To this end, we study the effects of graph convolutions in deeper layers of a multi-layer network. For node classification tasks, we also study whether one can avoid using additional layers in the network design for the sole purpose of gathering information from neighbours that are farther away, by comparing the benefits of placing all convolutions in single layer versus placing them in different layers.
Our contributions. We study the performance of multi-layer networks for the task of binary node classification on a data model where node features are sampled from Gaussian mixture, and relational information is sampled from a symmetric two-block stochastic block mode [ (see (Scttin 2. for details). The node features are modelled after XOR data with two classes, and therefore, has four distinct components, two for each class. Our choice of the data model is inspired from the fact that it is non-linearly separable. Hence, a single layer network fails to classify the data from this model. Similar data models based on the contextual stochastic block model (CSBM) have been used extensively in the literature, see, for example, Deshpande et al.] (2018); [Binkiewizz et al. (2017); Chien et al. 12021 2022): Baranwal et al. (2021). D. We now summarize our contributions below.
1. We show that when node features are accompanied by graph, a single graph convolution enables a multi-layer network to classify the nodes in a wider regime as compared to methods that do not utilize the graph, improving the threshold for the distance between the means of the features by a factor of at least 1/ //Eegg Furthermore, assuming a slightly denser graph, we show that with two graph convolutions, multi-layer network can classify the data in an even wider regime, improving the threshold by a factor of at least 1/ Vn, where n is the number of nodes in the graph.
2. We show that for multi-layer networks equipped with graph convolutions, the classification capacity is determined by the number of graph convolutions rather than the number of layers in the network. In particular, we study the gains obtained by placing graph convolutions in a layer, and compare the benefits of placing all convolutions in a single layer versus
'Our analyses generalize to non-symmetric SBMs with more than two blocks. However, we focus the hinary symmetric case for the sake of simplicity in the presentation of our ideas.
2

---

Published as a conference paper at ICLR 2023
placing them in different combinations across different layers. We find that the performance is mutually similar for all combinations with the same number of graph convolutions.
3. We verify our theoretical results through extensive experiments on both synthetic and real-world data, showing trends about the performance of graph convolutions in various combinations across multiple layers of a network, and in different regimes of interest.
The rest of our paper organized as follows: In InSection 2 data model and the network architecture that is central to our study, followed by our analytical results Finctin,Secction 4 presents extensive experiments that illustrate our theoretical findings.
we provide a detailed description of the
Section 3 Finally, Section
PRELIMINARIES
2.1 DESCRIPTION OF THE DATA MODEL
Let n, d be positive integers, where denotes the number of data points (sample size) and d denotes the dimension of the features. Define the Bernoulli random variables En ~ Ber(4/2 and " Th Ber(1/2). Further, define two classes C. - (i [m] e = b} for b 10.
Let f and v be fixed vectors in R4, such that | = ||||| and (n,, v) = oF Denote by X E Ruxd the data matrix where each row-vector X; E Rd is an independent Gaussian random vector distributed as X3 ~ (2n,; - 1)((1 - ε + E, )²). We use the notation X XOR-GMM(n, d, μt, V, o²) to refer to data sampled from this model.
Let us now define the model with graphical information. In this case, in addition the features X described above, we have graph with the adjacency matrix, A = (aj())) that corresponds to an undirected graph including self-loops, and sampled from a standard symmetric two-block stochastic block model with parameters and g, where p is the intra-block and is the inter-block edge probability. The SBM(n, p. q) then coupled with the XOR (ER--MM(n, n, d. μr, v, o²) in the way that aij Ber(p) if E; Ej and aij Ber(g) i + Ej. For data (A, X) ((ar) J.jE))) (Xi)e)))) sampled from this model, we say XA XOR-CSBM(C d, v, 0², .p.9).
We will denote by D the diagonal degree matrix of the graph with adjacency matrix A, and thus, deg(i) = D Eド= Oij denotes the degree of node i. We will use N, i E [n] aij 1} to denote the set of neighbours of node i. We will also use the notation ~ j or ~ j throughout the paper to signify, respectively, that i and are in the same class, or in different classes.
2.2 NETWORK ARCHITECTURE
Our analysis focuses on MLP architectures with ReLU activations. particular, for a network with L layers, we define the following:
( X,
1 (X) = (D- (D- + +b()) for E (Z),
O = ReI.U(((()))
8 = =(F()(()))
Here, X E Raxd is the given data, which is an input for the first layer and yp(x:) = sig = I+e-x, applied element-wise. The final output of the network is represented by ÿ = [6e hern) Note that D A is the normalized adjacency matrix and k denotes the number of graph convolutions placed in layer 1. In particular, for simple MI.P with no graphical information, we have
I,..
We will denote by 0, the set of all weights and biases, (W(), b(o) )e(2). which are the learnable parameters of the network. For a dataset (X. y). denote the binary cross-entropy loss obtained by
We take js and v to be orthogonal and of the same magnitude for keeping the calculations relatively simpler, while clearly depicting the main idcas behind our results.
'Our results rely on degree concentration for each node, hence, they readily generalize other normalization methods like D + ADD (see Appendix A for proofs).
3

---

Published as a conference paper at ICLR 2023
multi-layer network with parameters 0 by (o(A, - EiEl Us log((:)) + 1og) log(1 (.). and the optimization problem is formulated
(P,
min to ()) BEC
where C' denotes a suitable constraint set for 0. For our analyses, we take the constraint set C to impose the condition |W S R and | < 1 for all <I< L, ie., the weight parameters of all layers / > are normalized, while for = I, the norm is bounded by some fixed value R. This is necessary because without the constraint, the value of the loss function can go arbitrarily close to O. Furthermore, the parameter R helps concisely provide bounds for the loss in our theorems for various regimes by bounding the Lipschitz constant of the learned function. In the rest of our paper, we use ( () to denote Eg (In, X), which the loss in the absence of graphical information.
RESULTS
We now describe our theoretical contributions, followed by a discussion and a proof sketch.
3.1
SETTING UP THE BASELINE
Before stating our main result about the benefits and performance of graph convolutions, we set up comparative baseline in the setting where graphical information is absent. In the following theorem, we completely characterize the classification threshold for the XOR-GM RM-MMM data model in terms of the distance between the means of the mixture model and the number of data points n. Let (b-) denote the cumulative distribution function of standard Gaussian, and F.(.) = ((.).
Theorem 1. Let X E Rnxd XOR- (OR-GMM(n, d, p.v, v²?) and define y = || 1ll2 to be the distance between the means. Then we have the following:
1. Assume that & S Ka and let h(x) RRd {0, 13 be any binary classifier. Then for any K > O and any E (0, 1), at least a fruction 24. (K/2)² O(n ((/2)) of all data points are misclassified by h with probubility at least 1 - exp( (oap(-2n==2 2-)
2. For any e >> O, if the distance between the means is (log n) + then any >> O, with probubility at least O(n ((, there exist a two-layer and a three-layer network that perfectly classify the data, and obtain a cross-entropy loss given by
(-B
R
(x(X) exp
(-3
(1=
where Ce [1/2, 1] an absolute constant and R. is the optimality constraint Eq. (1)
Part of Theorem shows that if the means of the features of the classes most ((a) apart then with overwhelming probability. there is a constant fraction of points that are misclassified. Note that the fraction of misclassified points is 2 [ 22)2),, which approaches 0 as K oc and approaches 1/2 as K + O, signifying that if the means are very far apart then we successfully classify all data points, while they coincide then we always misclassify roughly half of all data points. Furthermore, note that if K co/lo for some constant E [0, 1), then the total number of points misclassified
is 2n (K)² R-C e 1-
log 9(1). Thus, intuitively, K x Vlog ri is the threshold beyond
which learning methods are expected to perfectly classify the data. This is formalized in part two of the theorem, which supplements the misclassification result by showing that if the means are roughly w(o Vlog n) apart then the data is classifiable with overwhelming probability.
3.2 IMPROVEMENT THROUGH GRAPH CONVOLUTIONS
We now state the results that explain the effects of graph convolutions in multi- multi-layer networks with the architecture described in /eectiin 2.2 We characterize the improvement in the classification threshold in terms of the distance between the means of the node features. Let erf(t) = 2tv(t - 1 be the Gauss error function and ((1) eer((() (1 exp( (ss((-1)))/or
4

---

Published as a conference paper at ICLR 2023
Theorem 2. Let (A,X) ~ XOR- (n, d. V. ...p.)) 7 1|u- -1l2. and (p),g) = =p lp(pp + q). There exist a two-layer network and a three-layer network with the following properties:
If the intra-class and inter-class edge probabilities are p. p= 22 lo""""" "), and it holds that [(p ()((7/2)) = - (V log n2
n(ptq) ). then for any <> 0, with probability at least 1 - (n )
the networks equipped with graph convolution in the second the third layer perfectly classify the data, and obtain the following loss:
(o X)= = C' exp (-CoRT (1(1/22) vehwgg))
where C > O and C" E [1/2, 1] are constants and R is the constraint from Eq. (1)
lf 52( logn ( and [pp, .) ()/((22)) - (V log v/ at least 1 1 O(nnn,,, the networks with any combination of two graph convolutions in the second and/or the third layers perfectly classify the data, and obtain the following loss:
then for any >> 0, with probubility
Co X) C' exp (-CoRT(p, ((((/)))(1 v</ogn))
where C > and C" E [1/2,]] are constants and R is the constraint from Eq. (I)
To understand Theorem 2
it helps to consider the regime where [(p, g) = 21().. Part one of the theorem shows that under the assumption that p, q = 22 n/n), single graph convolution improves the classification threshold for % the distance between the means by factor of at least 1/ Vn(p+t)) as compared to the case without the graph. Part two then shows that with a slightly stronger assumption on the graph density, we observe further improvement in the threshold up to factor of at least // $7. We refer to Appendix f.8 a comprehensive explanation of this simpler case.
Note that although the regime of graph density is different for part two of the theorem, the result itself is an improvement. In particular, if p, 22 n/vR) then part one of the theorem states that one graph convolution achieves an improvement of at least 1/ 8/. while part two states that two convolutions improve it to at least 1/ V/n However, we also emphasize that in the regime where the graph dense, i.c., when p. q (1), two graph convolutions do not have a significant advantage over one graph convolution. Our experiments in Snction 4.1 demonstrate this effect.
The XOR-CSBM data model also demonstrates why graph convolutions in the first layer can severely hurt the classification accuracy. Hence, for Theorem 2] our analysis only considers networks with no graph convolution in the first layer, i.e., k = O. This effect is visualized in Fig. 1, and is attributed to the averaging of data points in the same class but different components of the mixture that have means with opposite signs. We defer the reader to to/Appendix A.3 for a more formal argument, and to/Appendix for experiments that demonstrate this phenomenon. As (the sample size) grows. the difference between the averages of node features over the two classes diminishes Figs. la and lb In other words, the means of the two classes collapse the same point for large However, in the last layer, since the input consists of transformed features that are linearly separable, a graph convolution helps with the classification task (see Figs. Ic Id].
3.3 PLACEMENT OF GRAPH CONVOLUTIONS
We observe that the improvements in the classification capability of a multi-layer network depends on the number of convolutions, and does not depend on where the convolutions are placed. In particular, for the XOR-CSBM data model, putting the same number of convolutions among the second and/or the third layer in any combination achieves mutually similar improvements in the classification task.
Corollary 2.1. Consider the data model COR-CSBM((1, d, u, o², p. q) and the network architec- ture from Section 2.2
Assune that p. 9 = (1og n/x), and consider the three-layer network characterized by part one of Theorem 2) with one graph convolution. For this network, placing the graph convolution in the second layer (k2 = 1, kg = 0) obtains the same results as placing it in the third layer (k2 0, ka =
5

---

Published as a conference paper at ICLR 2023
(a) Original node features at the first layer.
(b) Feature representation after GC the first layer.
Feature representation the last layer.
Feature representation after GC the last layer.
Placement of a graph convolution (GC) in the first layer versus the last layer for data sampled from the XOR-CSBM. For this figure we used 1000 nodes in each class and randomly sampled stochastic block-model graph with p = 0.8 and 0.2.
Figure 1:
Assume that p. q = 12(1ognn/ and consider the three-layer network characterized by part two Theorem with two graph convolations. For this network, placing both convolutions the second layer (k2 = 2, K3 = 0) or both of them in the third layer (k2 = O, K3 2) obtains the same results placing convolution in the second layer and one in the third layer (k2 = 1, =
Corollary 2.1 immediate from the proof of Theorem (see Appendices A.6 and In Section 4 we also show extensive experiments on both synthetic and real-world data that demonstrate this result.
3.4 PROOF SKETCH
In this section, we provide an overview of the key ideas and intuition behind our proof technique for the results. For comprehensive proofs, see Appendix A
For part one Theorem T we utilize the assumption on the distribution of the data. Since the find the (Bayes) optimal classificr") which takes the form h (x) 1( (x, v) - (x. (1) [). where 1(.) is the
underlying distribution of the mixture model is known, h (x), for the indicator function. We then compute lower bound the probability that h² fails to classify one data point from this model, followed by a concentration argument that computes a lower bound on the fraction of points that h fails classify with overwhelming probability. Consequently, a negative result for the Bayes optimal classifier implies a negative result for all classifiers.
For part two of Theorem 1 we design two-layer and three-layer network that realize the (Bayes) optimal classifier. We then use a concentration argument to show that in the regime where the distance between the means is large enough, the function representing our two-layer or three-layer network roughly evaluates to a quantity that has a positive sign for one class and negative sign for the other class. Furthermore, the output of the function scales with the distance between the means. Thus, with suitable assumption on the magnitude of the distance between the means, the output of the
A Bayes classifier makes the most prohable prediction for data point, Formally, such classifier is of the form h" (æ) argmax (0,1) Pr (y b x].

---

Published as a conference paper at ICLR 2023
networks has the correct signs with overwhelming probability. Following this argument, we show that the cross-entropy loss obtained by the networks can be made arbitrarily small by controlling the optimization constraint R (see Eq. (1), implying perfect classification.
For Theorem 2, we observe that for the (Bayes) optimal networks designed for Theorem I placing graph convolutions in the second or the third layer reduces the effective variance of the functions representing the network. This stems from the fact that for the data model we consider, multi-layer networks with ReLU activations are Lipschitz functions of Gaussian random variables. First, we compute the precise reduction in the variance of the data characterized by K > 0 graph convolutions (see Lemma A.3). Then for part one of the theorem where we analyze one graph convolution, we use the assumption on the graph density to conclude that the degrees of each node concentrate around the expected degree. This helps us characterize the variance reduction, which further allows the distance between the means to be smaller than in the case of a standard MIP, hence, obtaining an improvement 5
in the threshold for perfect classificatior convolutions using very similar argument. In this case, the variance reduction is characterized by the number of common neighbours of a pair of nodes rather than the degree of a node, and is stronger than the variance reduction offered by a single graph convolution.
Part two of the theorem studies the placement of two graph
EXPERIMENTS
In this section we provide empirical evidence that supports our claims in Secciion 3] analyzing the synthetic data models XOR-GMM and XOR-CSBM that are crucial to our theoretical results, followed by a similar analysis on multiple real-world datasets tailored for node classification tasks. We show a comparison of the test accuracy obtained by various learning methods in different regimes, along with a display of how the performance changes with the properties of the underlying graph, i.e., with the intra-class and inter-class edge probabilities p and
We begin by
For both synthetic and real-world data, the performance of the networks does not change significantly with the choice of the placement of graph convolutions. In particular, placing all convolutions in the last layer achieves a similar performance as any other placement for the same number of convolutions. This observation aligns with the results in Gasteiger et al. (2019).
4.1 SYNTHETIC DATA
In this section, we empirically show the landscape of the accuracy achieved for various multi-layer networks with up to three layers and up to two graph convolution Fo In Fig. 2) we show that as claimed in Theorem 2 a single graph convolution reduces the classification threshold by factor of 1/ yyddg and two graph convolutions reduce the threshold by factor of V5, where E dege- = _ (p + q)-
We observe that the placement of graph convolutions does not matter as long as it is not in the first layer. [igs. 2a] show that the performance is mutually similar for all networks that have one graph convolution placed in the second or the third layer, and for all networks that have two graph convolutions placed in any combination among the second and the third layers. In Figs. 2c 2d we observe that two graph convolutions do not obtain a significant advantage over one graph convolution in the setting where and are large, i.e., when the graph is dense. We observed similar results for various other values of p and q (see (ppeendxxx B. for some more plots).
Furthermore, in Appendix B we verify that if graph convolution is placed in the first layer of a network, then difficult to learn a classifier for the XOR-CSBM data model. In this case, test accuracy is low even for the regime where the distance between the means is quite large.
4.2 REAL-WORLD DATA
For real-world data, we test our results on three graph benchmarks: CORA, CiteSeer, and Pubmed citation network datasets (Sen et al. 2008). Results for larger datasets are presented in Appendix B.2 We observe the following trends: First, claimed in Theorem 2) networks that utilize the graph
We note that although scaling the parameters a network scales the output the network, yet, it does not affect the accuracy, which is determined by the sign of the outputs. We defer to Appendix B.1 for experiments with networks having graph convolutions in the first layer.
7

---

Published as a conference paper at ICLR 2023
Test Accuracy
Test Accuracy
MP ar
Zige 2tbullew??
44-
K
Two-layer networks with (p, = (0.2, 0.02).
(b) Thrce-layer networks with (p. () (0.2,
Test Accuracy
Test Accuracy
cit
cipares em s0 sctteee
lover nit wit 2 56. learr
(c) Two-layer networks with (p. (0.5. 0.1).
(d) Three-layer networks with (p, q) = (0.5, 0.1).
Figure 2: Averaged test accuracy (over 50 trials) for various networks with and without graph convolutions on the XOR-CSBM data model with n 400, d 4 and の² = 1/a. The x-axis denotes the ratio K = || v/ll /or on a logarithmic scale. The vertical lines indicate the classification thresholds mentioned in part of Theorem (red), and in Theorem 2 (violet and pink).
perform remarkably better than traditional MLP that does not relational information. Second, all networks with one graph convolution any layer achieve a mutually similar performance, and all networks with two graph convolutions in any combination of placement achieve mutually similar performance. This demonstrates a result similar to Corollary 2.1 real-world data. Finally, networks with two graph convolutions perform better than networks with one graph convolution.
In Fig. 3
we present for all networks, the maximum accuracy over 50 trials, where each trial corresponds
random initialization of the networks. For 2-layer networks, the hidden layer has width 16, and for 3-layer networks, both hidden layers have width 16. We use a dropout probability of 0.5 and a weight decay of 10-5 while training.
For this study, we attribute minor changes in the accuracy to hyperparameters involving dropout and weight decay. This helps clearly observe the important difference in the accuracy of networks with one graph convolution versus two graph convolutions. For example. in Fig. 3al we note that there are differences in the accuracy of the networks with one graph convolution (red and blue). However, these differences are minor compared to the networks with one convolution (red and blue) and networks with two convolutions (green and yellow). We also show the averaged accuracy in (Appendix B.2 Note that the accuracy slightly differs from well-known results in the literature due to implementation differences. In particular, the GCN implementation in Kipf & Welling (2017) uses Á = D AAD-
as the normalized adjacency matrix, however, use A D D In Appendix B.2 we also show
empirical results for the normalization À D 3 AD 4.
CONCLUSION AND FUTURE WORK
We study the fundamental limits of the capacity of graph convolutions when placed beyond the first layer of a multi-layer network for the -OR-CSBM data model, and provide theoretical guarantees for their performance in different regimes of the signal in the data. Through our experiments on both synthetic and real-world data, we show that the number of convolutions is more significant
Our proofs rely degree concentration, and thus, generalize the other type of normalization well.
8

---

Published as a conference paper at ICLR 2023
77.2
73.2
77.4
$2.4
20.3
$9.3
Accuracy (max)
69.1
21.10
21-01
1L-100
XL-000
3L-011
21-20
21:02
21-11
3L-20
3L-020
3L-022
31-130
3L-131
3L-011
Model
(a) Accuracy of various learning models on the CORA dataset.
79.7
$9.0
79.4
Accuracy
40-
20
20.00
30250
Model
(b) Accuracy various learning models on the Pubmed dataset.
60.7
68.9
67.9
70.5
70.6
68.9
71.5
Accuracy (max)
70-
30-
3L022
Model
Accuracy of various learning models the CiteSeer dataset.
Figure 3: Maximum accuracy (percentage) over 50 trials for various networks. A network with layers and Ji.....JJ convolutions in each of the layers is represented by the label kL-j1 J..
factor for determining the performance of a network, rather than the number layers in the network. Furthermore, we show that placing graph convolutions in any combination achieves mutually similar performance enhancements for the same number of them. We observe that multiple graph convolutions advantageous when the underlying graph relatively sparse. Intuitively, this is because in dense graph, a single convolution can gather information from a large number of nodes, while in sparser graph, more convolutions are needed to gather information from larger number of nodes.
Our analysis is limited to a positive result and we only provide a minimum guarantee for improve- ment in the classification threshold. To fully understand the limitations graph convolutions, complementary negative result (similar to part one of Theorem 1} for data models with relational information required, showing the maximum improvement that graph convolutions can realize in multi-layer network. This problem is hard because graph convolution transforms an iid set of features into highly correlated set of features, making difficult to apply classical high- high-dimensional concentration arguments. Another potential line of work is to generalize results for arbitrary data models. However, since our arguments rely heavily on the concentration measure, it is hard to extend the analysis to arbitrary distributions. Therefore, require distribution-agnoste tools.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
K.F. would like to acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Cette recherche été financée par le Conseil de recherches sciences naturelles et en génie du Canada (CRSNG), RGGPN-2019-04000 the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), EXGPIN-2020-04599) AGEER-2020-000
DGECR-2019-007
A.J. acknowledged
REFERENCES
E. Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18:1-86, 2018.
E. Abbe and C. Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 670-688, 2015, doi: 10. 10.110900 110/000C.2005.555
E. Abbe and C. Sandon. Proof of the achievability conjectures for the general stochastic block model. Communications on Pure and Applied Mathematics, 71(7):133-1406, 2018
E. Abbe, S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. IEEE Transactions Information Theory, 62(1))471-495 2015.
Lars Backstrom and Jure Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining, pp. 635-644, 2011.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference Learning Representations, 2021.
Banks, Moore, J. Neeman, and P. Netrapalli. Information -heeortion-theoretiic thresholds for community detection in sparse networks. In Conference on Learning Theory, pp. 383-416. PMLR, 2016.
Victor Bapst, Thomas Keck, A -arbskika,ai Craig Donner, Ekin Dogus Cubuk, Samuel S Schoenholz, Annette Obika, Alexander WR Nelson, Trevor Back, Demis Hassabis, et al. Unveiling the predictive power of static structure in glassy systems. Nature Physics, 16(4):448-454, 2020.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribttion generalization. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proc. of Mach. Learn. Res., pp. 684-693. PMLR, 18-24 Jul 2021.
P. Battaglia, R. Pascanu, M. Lai, D. J. Rezende, and K. Kavukcuoglu. Interaction Networks for Learning about Objects, Relations and Physics. In Advances Neural Information Processing Systems (NeurIPS), 2016.
N. Binkiewicz, J. T. Vogelstein, and K. Rohe. Covariate-ussisted spectral clustering, Biometrika, 104: 361-377, 2017.
C. Bordenave, M. Lelarge, and L. Massoulié. bonttrakkra spectrum of random graphs: com- munity detection and non-regular ramanujan graphs. In 2015 IEEE 56th Annual Symposium Foundations of Computer Science, pp. 1347-1357. IEEE, 2015.
Z. Chen, L. Li, and J. Bruna. Supervised community detection with line graph neural networks. In International Conference Learning Representations (ICLR), 2019.
H. Cheng, Y. Zhou, and J. X. Yu. Clustering large attributed graphs: A balance between structural and attribute similarities. ACM Transactions on Knowledge Discovery from Data, 12, 2011.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations, 2021.
10

---

Published as a conference paper at ICLR 2023
Eli Chien, Wei-Cheng Chang, Cho-Jui Hsich, Hsiang-Fu Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit Dhillon. Node feature extraction by self-supervised multi-scale neighborhood prediction. In International Conference on Learning Representations, 2022.
T. A. Dang and E. Viennet. Community detection based structural and attribute similarities. In The Sixth International Conference on Digital Society (ICDS), 2012.
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 8466))066106. 2011.
Y. Deshpande, E. Abbe, and A. Montanari. Asymptotic mutual information for the two-groups stochastic block model. ArXiv, 2015, arXiv: 107.v.150..08655.
Y. Deshpande, A. Montanari S. Sen, and E. Mossel. Contextual stochastic block models. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
M. Fey and E. Lenssen. Fast graph representation learning with Py PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Kimon Fountoulakis, Amit Levi, Shenghao Yang. Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. arXiv preprini arXiv:2202. 13060, 2022.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations, 2019,
Julia Gaudio, Miklos Z. Racz, and Anirudh Sridhar. Exact community recovery in correlated stochastic block models. arviv preprint arXiv:2203. 15736, 2022.
J. Gilbert, E. Valveny, and H. Bunke. Graph embedding in vector spaces by node attribute statistics. Pattern Recognition, (5(9):0072-300 2012.
Gilmer, S.S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning, 2017.
S. Günnemann, Färber, S. Raubach, and T. Seidl. Spectral subspace clustering for graphs with feature vectors. In IEEE 13th International Conference on Data Mining, 2013.
W. L. Hamilton, R. Ying, and Leskovec. Inductive representation learning on large graphs. NIPS' 17: Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
William Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159 2020.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma. Richard T. B. Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference Learning Representations, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs arXiv preprint w.Xiv:2005.00685 2020.
D. Jin, Z. Liu, W. Li. D. He, and W. Zhang. Graph convolutional networks meet markov random fields: Semi-supervised community detection in attribute networks. Proceedings of the AAAI Conference on Artificial Intelligence, 311) 2019,
T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
I. M. Kloumann, J. Ugander, and J. Kleinberg. Block models and personalized pagerank. Proceedings of the National Academy of Sciences, 14(1):33-38, 2017.

---

Published as a conference paper at ICLR 2023
P. Li, (Eli) Chien, and O. Milenkovic. Optimizing generalized pagerank methods for seed- expaasion community detection. In Advances in Neural Information Processing Systems (NeurIPS), pP- 11705-11716, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for
semi-supervised learning. In Thirty-Second AAAI conference artificial intelligence, 2018.
Chen Lu and Subhabrata Sen. Contextual stochastic block model: Sharp thresholds and contiguity,
ArXiv, 2020. arXiv:201 111111.0988 1.09841..
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Is heterophily real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.0566 2021.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference on Learning Representations, 2022.
Laurent Massoulié. Community detection thresholds and the weak ramanujan property. Pro- ceedings of the Forty-Sixth Annual ACM Symposium Theory of Computing, pp. 694-703, 2014.
N. Mehta, C. Duke, and P. Rai. Stochastic blockmodels meet graph neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 6464,447, 2019.
A. Montanari and S. Sen. Semidefinite programs sparse random graphs and their application to community detection. In Proceedings of the forty-eighth anmual ACM Symposium on Theory of Computing, pp. 814-827, 2016.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M. Bronstein. Geometrie deep learning on graphs and manifolds using mixture model enns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
C. Moore. The computer science and physics of community detection: Landscapes, phase transitions, and hardness. Bulletin of The European Association for Theoretical Computer Science, 1(121), 2017.
E. Mossel, J. Neeman, and A. Sly. Consistency thresholds for the planted bisection model. In Proceedings of the forty-seventh annual ACM Symposiun on Theory of computing, pp. 69-75, 2015.
E. Mossel, J. Neeman, and A. Sly. A proof of the block model threshold conjecture. Combinatorica, 38(3):665-708, 2018.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
D. B. Owen. A table of normal integrals. Communications in Statisicss-Simllttion and Compulation, 9(4):389-419, 1980.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1), 2009.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93, 2008
R. Vershynin. High- Diggeniimessinnll Probability: An Introduction with Applications in Data Science, volume 47, Cambridge University Press, 2018.
Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I Weidele, Claudio Bellei, Tom Robin- son, and Charles E Leiserson. Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensies. arXiv preprint arXiv: 1908. 2019.
12

---

Published as a conference paper at ICLR 2023
Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R. Benson, and Pan Li. Understanding non non-linearity in graph neural networks from the bayesian-inference perspective. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Towards distribution shift of node- level prediction graphs: An invariance perspective. In International Conference on Learning Representations, 2022.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarahayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations, 2021.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks, 2021.
J. Yang, J. McAuley, and J. Leskovee. Community detection in networks with node attributes. In 2013 IEEE 13th International Conference on Data Mining, pp. 1151-1156, 2013.
R. Ying, He, K. Chen, P. Eksombatchai, W. L. Hamilton, and Leskovec. Graph convolutional neural networks for web-scale recommender systems. KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974-983, 2018.
Si Zhang, Dawei Zhou, Mehmet Yigit Yildirim, Scott Alcom, Jingrui He, Hasan Davuleu, and Hanghang Tong. Hidden: hierarchical dense subgraph detection with application to financial fraud detection. In Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 570-578. SIAM, 2017.
A PROOFS
A.1 ASSUMPTIONS AND NOTATION
Assumption 1. For the XOR-GMM data model, the means of the Gaussian mixture such that (), 0 and ||,4||2 = ||1]
We denote [x]++ = ReLU(x)) and ()x)) sigmoid = 1/1+0-", applied element wise on the inputs. For any vector v, Tīv|aa denotes the normalized v. We use y = || wi12 to denote the distance between the means of the inter-class components of the mixture model, and 7 to denote the norm of the means, 7 = 7/v2 || |22
Given intra-class and inter-class edge probabilities and we define [(p, g) = p-ol We denote the ptg probability density function of standard Gaussian by Φ(z), and the cumulative distribution function by (xx). The complementary distribution function denoted by (x(x) = (xx).
A.2 ELEMENTARY RESULTS
In this section, state preliminary results about the concentration of the degrees of all nodes and the number common neighbours for all pairs of nodes, along with the effects graph convolution on the mean and the variance of some data. Our results regarding the merits of graph convolutions rely heavily on these arguments.
Proposition A.1 (Concentration of degrees). Assume that the gruph density is p, 2 los"" "), Then for any constant 0, with probability at least 2n have for all i [n]] that
deg(i) ) = マ (p + 4)(1 (1)),
(1 + (1)),
deg(i)
n(p + g)
Σ
Oij
Σ
Oij = (2s;
1) P- 9 (1 + on (1)),
deg
p q
JECr
JECo
where the error term o, 0 (V log
13

---

Published as a conference paper at ICLR 2023
Proof. Note that (ig(i) (i) is sum of Bernoull random variables, hence, have by the Chernoff bound (Vershynin 2018 Section 2) that
n (p + 4) -), 2 2) + 20]9 & 2exp(-Cn(p g)8²),
Pr (eg(() E
2
for some 0. We now choose = (o+1) log for large constant c > 0. Note that since Cm(ptg)
P, q [2(logg n/n), have that 5 0
log On (1). Then following a union bound over
i [n]. we obtain that with probability least 2n
n2 deg
70 4)
1
for all i [n],
2
log
2
1 0 log n
for E [n].
deg(i) n(p + q)
Note that deg(A] Ejec, Oij for any b E (0, 1} is sum of independent Bernoulli random variables. Hence, by a similar argument, we have that with probability at least 1 - 1-2n
1
Σas
aij
Σ aij
(22,
1)2-_11 (1 on)) for all [n]. p
deg(i)
JEC1
jECo
Proposition A.2 (Concentration of the number of common neighbours). Assume that the graph
density is 9 Q
logn
). Then for any constant with probability at least 1 -2n v
n1 (p² + 9²) (1 (1))
IN; n N
for all i ~~ j,
2
IN N1 = mpp + (1))
for all i & j,
where the error term (1)(1) O (V log
Proof. For any two distinct nodes i,j E [xx] we have that the number of common neighbours of and j is N, = Σ EE]jn Ozk- This is sum of independent Bernoulli random variables, with mean N n N₁I = (p² + q²) for ~ and N, n N₂
npg for j. Denote Pij E N, N₁J-
Therefore, by the Chernoff bound (Vershynin, 2018 Section 2), we have for fixed pair of nodes (i.j) that
Pr [[N, N E jung(1 51z). Mly(1 6tt)1 < 2exp(-C
for some constant C' O. We now choose dij
(c+22) log for any large c >> Note that since Cpis
P, q (2(logn//)) we have that 6,z Ol log
o, (1). Then following union bound over all
pairs (i, E [n]] [n], we obtain that with probability least 2n for all pairs of nodes (i. j) we have
IN:ON1 Th "00 + (1
for all i im j.
NN r1 + (1))
for all i 0 j.
Lemma A.3 (Variance reduction). Denote the event from Proposition A. to be B. Let (Xiheen E Raxd be an iid sample of data. For graph with adjacency matrix A (including self-loops) and fixed integer K > 0, define a K K-convolution to be X (D (D'AA)*s 'A)xx. Then we have
X.
Cov(X, B) (oV))Cov(X)), where p(K)= = (1 11+0p oz
2K
A
A
JEJN
Here, A A (i.j) is the entry in the ith row and jth column of the exponentiated matrix K and A F.de (p 9).
14

---

Published as a conference paper at ICLR 2023
Proof. For matrix M, the ith convolved data point is X, M, X. where M, denotes the ith row of M. Since X; are iid, we have
Cov = Σ
(M,)) Cov(()))
JE(N]
remains to compute the entries of the matrix M = (D-IA)A Note that we have D-1A(i, = as)/deg((), obtain that
Mj = (D (D- ())
Σ
aij aih Ojx 1ijx2ik-11 20x ajK-1j
deg( (eg(()) ... deg(jk-1)
==
jk-1=1
Recall that on the event B, the degrees of all nodes are A(1 + on (1)), and hence, we have that
+ on (1))
"
Mj
A R
ΣΣ Σ
Oij
jjx-2jk-1 (jx-15
Jk-1=1
where the (1) ( Vlog The sum of these products of the entries of A is simply the number of length- K paths from node i to j. i.e., A A (i.j). Thus, we have
(1+
2K
Cov(X; B) Σ jE(m]
(ov,))))
Σ
(1,)
A
JE(n)
Since Xy are rid, we obtain that p(K) - [+tnll1)
ESE(n) A K (2,j)3
Consider sample (A, X) drawn from COR-CSBM(n, d, p. v. o² .P, q) for the symmetric case where exactly n/2 nodes are in each of the two classes. We have that
Let briefly discuss the implications of Lemma A.3
(pIn/2 gIn/2 pI,/2)
EA
Tln/2
This gives us Ep(K) +1 [p. 2) for any K 2. Recall that single graph convolution reduces the distance between the means by factor of [[p, g). Hence, to comment on the performance of an arbitrary number convolutions, K, we might hope to compare the reduction in this distance, ['(p, 4)* with the reduction in the variance (p(K) to obtain condition on K in terms of p, and q. The challenge, however, lies in the fact that in deeper layers, computing p(K) is non-trivial due to node features being highly correlated. Moreover, argument to claim that p(K) EEp( K) is needed for this approach, which seems to require strong density assumptions on the graph.
We now state result about the output of the (Bayes) optimal classifier for the XOR-GMM data model that is used in several of our proofs.
Lemma A.4. Ler h(x) (zx P) (z, ps) for all Idd and define
((t) = erf((t)
V (1-ett)
1
Then we have
- (20((122)
i Co
1. The expectation EX.).) = { 120 (1/20)
i Ci
2. For any VV, a > 0 such that 7 Ω2 (o), we have that {( = (2
3. For any N, o > 0 such that y o,,(a) we have that (()) 22 (22))
Proof. For part one, observe that (X,, j and (X,, 1)) are Gaussian random variables with variance
o² and means 1/vz, 0 if 0 and 0, 7/v2 if 1, respectively. Thus, (X,, pi) and (X,, D) are folded-Gaudd Gaussian random variables and we have Eh(X,) -V2((1/22) if Co and Eh(X,) (2/(2/) otherwise.
15

---

Published as a conference paper at ICLR 2023
We now write
N/ (1- (1- =IH(), 1V
((() er((l)
where (t) = erf(t) - 1/
For part two, note that (t) is increasing function in the range [-1, 1] and (tt) 0 for > 0. Hence, for t 2 C for some positive constant C, (t) 2 H(CC) = C", therefore, ((t) = (t 2 Ctt.
For part three when / = on, (1), we use the series expansion of h(() about / 0 to obtain that
L
13
h(t)= =
+ O(t))
(t()).
V
RVT
6/T
Hence, ((t)= = th((t) = (2(tt). Putting = 7/0 completes the proof.
Fact A.5. For any x E [0, 1]. 2 & log(1 + x) S x.
A.3 PROOF OF THEOREM 1 PART ONE
In this section prove our first result about the fraction of misclassified points in the ab- sence of graphical information. We begin by computing the Bayes optimal classifier for the data model XOR-GMM (see (Section 2.1 A Bayes classifier, denoted by h" h*()),, maximizes the posterior probability of observing a label given the input data æ. More precisely, h h2x))
argmax (0.1) Pr b x= z), where
R represents a single data point.
Lemma A.6. For some fixed p. E Rd and a² > O, the Bayes optimal classifier, (x:) Rd. {0, 1) for the data model XOR-GMM(n,, pr v, a is given by
(x) = (1( wل < (xx, = (0
{1
[x p 2 (x, v) x p < (x, v
where 1. is the indicator funcitioo
Pr ly 1] Let fx(x)) denote the density function of continu- ous random vector x. Therefore, for any b E (0, 1}.
Proof. Note that Pr ly= =
Pr [y fxi (ar y b) Pr ly = xx= Ece(o.)) Pr = c| fxl (x y c)
Exity La la Sxlv (cly=b)
1 +
Let's compute this for b = O. We have
fx y = 1) cosh (xx, v) /02) fxly (x y 0)
|||| |22
cosh (I, v\ /02) coshi (x, n1) /02)
cosh( (xx, 11) /02)
exp
20
where in the last equation we used the assumption that ||||||| = |||| The decision regions are then identified by: Pr ly 0 x] 2 1/2 for label 0 and Pr [y = 0 x] < 1/2 for label 1.
Thus, for label O, we need
fa (= Jx (0
< 1, which implies that cosh((a,w)//a) tosh((2,11/0")
S 1. Now we note that
cosh(r) < cosh(y) (y) = |ar| S lyl for all x, y E R, hence, we have (xx, p.) 2 [.. Similarly, we have the complementary condition for label 1.
Next, we design a two-layer and a three-layer network and show that for particular choice of parameters 0 = (W(1), b(0) for E 21, for the two-layer case and E [1,2,3} for the three-layer case, the networks realize the optimal classifier described in Lemma A.6
Proposition A.7. Consider two-layer and three-layer networks of the form described in Section 2.2 without biases (i.e., (l1) 0 for all layers 1), for parameters W()) and some RR as follows.
1. For the two-layer network,
W(1) R (fe
- f D -D),
(-1 -1 1)
16

---

Published as a conference paper at ICLR 2023
2. For the three-layer network,
-1
w Ri -P is - w
-1
1
W
(11)
(1
Then for any a > O, the defined networks realize the Bayes optimal classifier for the data model XOR-GMM(n, d, μr V, )²).
Proof. Note that the output of the two-layer network is se( (x(W)) W which is interpreted as the probability with which the network believes that the input is in the class with label 1. The final prediction for the class label is thus assigned to be 1 the output is 2 0.5, and 0 otherwise. For each i [n), we have that the output of the network data point is
p R ( [)]++ |- (X,, A)]++ [X;, 0] +1 (X,, 2))+))
= = (X, 211 - (X R)))
where we used the fact that [t] [-t]+
|t| for all t E R. Similarly, for the three-layer network, the output is (([[WU)) W W W (3)) So we have for each E [r] that
9: 18 (1 (0)++ - X 0 + (X,, p) + (X, +M1+++
II(x, 1 1- (X; M3) 1X +/ - (X; (9)+))))))))
= (X][) D) (X,, A II A3l - 1X:, 1)
o (H(( | (X,, 1)))
where in the last equation we used the fact that [t] 1- for all E R.
The final prediction is then obtained by considering the maximum posterior probability among the class labels and 1, and thus,
pred X.) = (R (X, A) RI x(X,
which matches the Bayes classifier in Lemma A.6
We now restate the relevant theorem below for convenience.
Theorem (Restatement of part one Theorem 1p. Let X E Ruxd XOR-GMM(n, d, p, u,v, a²) Assume that || - U112 < Ka and let h(x) Rd + {0, 1 be any binary classifier. Then for any K 0 and any E (0, least fraction 24 (k/2)² O(n=(22) of all data points are misclassified by with probability at least 1 exp(-2n -c).
Proof. Recall from Lemma A.6
that for successful classification, we require for every E [n].
(X,, p1) (X,, m (X, 14) [X, P)
E Co. i C1.
Let's try to upper bound the probability of the above event, i.e., the probability that the data is classifiable. We consider only class Co, since the analysis for Ci is symmetric and similar. For
i Co.
write X, le + og., where gi (N, I). Recall that 7 = +| 2112 and
n = 7/VI = ||ll/2 = 22. Then we have for any fixed Co that
Pr 11) 1X,, 1 = Pr(h' + (gi, A 2 la (g;, D]
< Pr(y ( + kg. A 2 a (g., []
(by triangle inequality)
< Pr (gg b) Kg,, p) K/Val
(using 7 S Ko).
17

---

Published as a conference paper at ICLR 2023
We now define random variables Z1 (g: 1) and Ze (gi, (i) and note that Z1. Z2 NN and 2 0. Let K' = K/v2.
2. We now have
Pr || - / - K 4Pr [Z Zz S K" 21, 22 2
=
Pr Z1 = - K3 d(2)dz
((2 + K¹) - 1 / ol2)d2 = / Φ(2 + K") o(z)dz
(223 2 2 B. (K/2) -1 2 (K/2)²
To evaluate the integral above, we used Owen 1980 Table 1:10,010.6 and Table 2:2.3). Thus, the probability that point E Co is misclassified is lower bounded as follows
Pr X is misclassified] > 2 (K/2)² TK-
Note that this is decreasing function of K. implying that the probability of misclassification decreases as we increase the distance between the means, and is maximum for K O.
Define M (n) for a fixed K to be the fraction of misclassified nodes in Co. Define z, to be the indicator random variable 1 (X; is misclassified). Then x; are Bernoulli random variables with mean at least TK, and (n) = Etec, Ex; 2 тк- Using Hoeffding's inequality (Vershynin 2018 Theorem 2.2.6), we have that for any >
Pr (n)) TK Pr [M()) 2 EM(n) 2 exp(-nt²))
Choosing 1= n for any E (0, yields
Pr M(n) TK n- 1/22 2 - -1-xp(-nnt-))
A.4 PROOF OF THEOREM 1 PART TWO
In this section, we show that in the positive regime (sufficiently large distance between the means), there exists a two-layer MLP that obtains an arbitrarily small loss, and hence, successfully classifies sample drawn from the XOR-GMM model with overwhelming probability.
Theorem (Restatement of part two of Theorem 1. Let X E Raxd ~ XOR-GMM(n, d, (,,,
For any O, if the distance between the means is || - ll (lo[)og (logn) m))+t), then for any e > with probability at least O(n the two-layer and three-layer networks described in Proposition A.7 classify all data points, and obtain cross-entroph loss given by
(-h 11 11u-
(x(X) = Ceep
ui--vll2 (1 + ve((lon))))
V2
where C' E [2/2, 1] is an absolute constant.
Proof. Consider the two-layer and three-layer MI.Ps described in Proposition A.7] for which we have = 10 (X, 1) (X,, ( ()). We now look at the loss for a single data point X,,
(X 0) = - yi log(U)) - (1 - y.) log(1 - 9s)
= log (1 + exp ((1 2y, R( XX, e\ [X, P)))
Note that (X EX,, p and (X; EX,, D) are mean 0 Gaussian random variables with variance ²². So for any fixed [n] and m. E {M,, v), use (Vershynin 2018 Proposition 2.1.2) to obtain
t2
Pr [ EX;, m
++] < 2
exp
20
Then by union bound over all i [n] and m. E {1,, v) have that
Pr [1 (X; - f.), & E [n], m E (n, 2
no
t
π
2
exp
20
t²
18

---

Published as a conference paper at ICLR 2023
no We now set t o 1) for any large constant 0. We now have with probability
least 1 V=(o+1) log
n
that
() = (EX,, ()) + Oloog))
(X = (EX, D) + Ola Ola clog n) Vi E [n].
Thus, we can write
(X,, (3) = (110
V logn )
(X,,)) = = (V
( log
vi Co. (2)
(), = (1+ (v log
(X,, (i) -0
vi Ci. (3)
log
Using Eqs. (2) and (3) in the expression for the loss, we obtain for all i E [n].
& (X, 0) log(1 + exp(-Rx/p o, (1))))
where the error term On (1) = v 9/log The total loss is then given by
Eg X
Σ 4 (X. log(1 + exp( Ry (1 o,,()))))
Next, Fact A.5 implies that for 0, c'/2 - log(1 et) e², hence, have that there exists
constant C' [1/2, 1] such that
(x( = Cexp (-R on (1))))
Note that by scaling the optimality constraint R, the loss can go arbitrarily close to 0.
A.5 GRAPH CONVOLUTION IN THE FIRST LAYER
this section, we show precisely why graph convolution operation in the first layer is detrimental to the classification task.
Proposition A.8. Fix a positive integer > 0, a E R+ and μ.v E Rd. Let (A, XOR-C (n, d, V, 0² p. 9). Define X to be the transformed data after applying graph convo- lution on X, i.e. D- AX. Then in the regime where p.q D log2 "), with probability least 1 - 1/ (o) we have that
pu qu + q)
On (1)
ie Co
EX:-
pv + qu
On (1) i
2(p q
Hence, the distance between the means of the convolved data, given by 2674 || vl12 on (1) diminishes to 0 for n + 20.
Proof. Fix μ, V E Rdd and define the following sets:
C-p {i E, 0, 0}: C- {il 1, 0}.
C₁ {i 8; 0, 1},
C, = e 1. 1}.
Denote X = D -1 AX and note that for any E [n]. the row vector
X, deg(i)
Σ
XijX,
Oiy EX, + og,)
dig(i)
jE(n)
jE(n)
Σ Oij
Σ
Σ
Σ
Σ
deg(i)
aij
+
Bij
aij
+o
aryg
JECμ
JEC
JEC,
JEC_.
jE[m
where we used the fact that X, = (2mz - 1)((1 - E, ) t og,) for set iid Gaussian random vectors g, NO, I2).
19

---

Published as a conference paper at ICLR 2023
Note that since c; 77, Bernoulii random variables, using the Chernoff bound (Vershynin 2018 Section 2), we have that with probability at least 1 - 11))oy(n)),
CC-pl 1C = |C- = |C2l = " o1
4
We now argument similar Proposition A. to obtain that for any > with probability least 1 - (n ") the following holds for all i E [
dig(i)
1
Σ HEE
Oij
Σ JEC-
dij
= 0
(1 E.) + 8q9
2(p + 9)
log
c
deg(1) (i)
1
aij
E
aij
=0
Esp+ + (1 (1-E:)
2(p + 9)
V log
JEC
JEC
Hence, we have that for all [n],
EX,-
(1 Es )p + E:9
1 + 5, (1 E:19
/ 0
(
c log
2 + ②)
2(p + 9)
pj + qu
(1) iE Co
2(p + q)
pv + qu
On (1) i i Ci
2(p + 9)
Using the above result, we obtain the distance between the means, which is of the order on (1) and thus, diminishes 0 as + 0C.
A.6 PROOF OF THEOREM 2 PART ONE
We begin by computing the output of the network when one graph convolution is applied at any layer other than the first.
Lemma A.9. Let h((x== (x. D) - (ar, (x) for any Rdd Consider the two-layer and three- layer networks in Proposition A.7 where the weight parameter of the last layer, W(L), is scaled by factor of = sgn (p- - q). If graph convolution is added to these networks in either the second or the third layer then for sample (A,X) ~ XOR- --OR-CSMM (n, d. μ., u. 2 P, p,9), the output of the networks for a point E [n] is
Rsgu(p - 9) deg(1)
ús = x(1 =
Σ axy)(X))
JEIm
Proof. The networks with scaled parameters are given as follows.
1. For the two-layer network,
w(1) = (f -a i -D),
=
-1 1 T)T.
2. For the three- network,
= -1))
w RE (ft
- i D) W
W
1
-1
1
When a graph convolution is applied at the second layer of this two-layer MLP, the output of the last 3''A(XX())) W(2), Then we have
layer for data (A, X) is f (X) D
R
RE
XX) deg(i)
Σ (X,, - X A
Σ an)((X))
deg(i)
JE(x)
JE[N]
20

---

Published as a conference paper at ICLR 2023
Similarly, when the graph convolution is applied the second layer of the three-layer MLP, the output f (X) [D- A[X(()]] w W(3), and we have
1 (X) =
RE
Σ jEIn]
(xyh(X))
Σ (x))(,))))) JE(N
R
Σ ag)((X))
deg(i)
deg(1
JE(m]
Finally, when the graph convolution is applied at the third layer of the three-layer MLP, the output is
(30 (X) = D-X w w(s), and we have
RE
(X) = deg(
Σ dij (1( 1X P - 114
i)
jE(n)
R
RE
an
- 1 (
Σ ax))(X)).
deg(
deg(i) jE(m)
jE(M)
Therefore, in all cases where we have single graph convolution, the output of the last layer is
Rsgn(p - ②) deg(i)
1100 (X)
Σ
aiyh(X;),
jE(N]
where L E (2 is the number of layers.
Theorem (Restatement of part of Theorem 2). Let (A, XOR- COR-CSBM((2) n, d. p.v, 0² ... 9)
Assume that p,q S2( log" and it holds that (p, 4)C(r/20) = w (V log n(p+g) then for any >> with probability at least (n,,), the networks equipped with graph convolution in the second or the third layer perfectly classify the data, and obtain the following loss:
(o(A, = CC' exp (-CoRT ()((1/20) vefloRn))
where C' > 0 and C" E [2/2, 1] are constants and R is the constraint Eg. (1)
(()) Proof. First, we analyze the output conditioned on the adjacency matrix A. Note that 1 (X) in Lemma A.9 is Lipschitz with constant
2
and h(X,) are mutually independent for j E [m].
deg(i)*
Theretore, by Gaussian concentration (Verhyyin
2018 Theorem 5.2.2) we have that for a fixed
i [n].
(- d'deg(i)
Pr R x - EEf X)]
(x)
> 8 A
< 2 exxp
We refer to the event from Proposition A. as B and define Q(t) to be the event that
1 (X) - EES! (X)] S t for all i e [n].
Then we can write
Pr (Q(t) Pr (Q(t)) n nB
Pr (Q()) S n B
En(p q)
< 2n exp
+ Pr [B*]
802
pn(p+ 1 9)
2n exp
+ 2n
802
21

---

Published as a conference paper at ICLR 2023
Let ş = sgn(p g) and note that 6(p-9) = 1Ø-gl l(p. q). We now choose t = 20 obtain that with probability at least 1 - -n the following holds for all E [nz]
2(c++)) log to n(ptg)
( x -E[
(x)) (x)00t
R
clogn n n(p + q)
RE
clog n n(p + 9)
Ooj (X(X))
3) + 0
R
deg
JE(m]
V2REC(7/20)
Σ
Σ
aij
+
R
c clog n n' + 4)
Lemma A.4
deg(()
JEC₁
JECa
clog n n(p 9)
V2(2e; 1) (p. ()(((/2))( + on (1) + +0
R1
Proposition A.
-2(22, (p. ()((())))(((LL))))))))))) (1)..
where in the last equation we used the assumption that [p, x)((722)) = (V obtain that with probability at least 1 4n
log <(p+a)
Overall, we
X = (2s,
ol for all e [n].
Recall that the loss for node is given
A, x) log(1 (2-20))) (x1) log (1 + exp (-Coall(g.(((222((LLo.)))
The total loss is given by 1 n Lig(n] 4 (A, X). Next, Fact A.5 log(1 + et) e", hence, we have for some C E [/2, that
implies that for any < 0, e 5
(,(A, = C' exp (-Co (1.00
A.7 PROOF OF THEOREM 2 PART TWO
We begin by computing the output of the networks constructed in Proposition A.7 when two graph convolutions are placed among any layer in the networks other than the first.
= (x. D) - (x., p Consider the networks constructed in Proposition A.7 equipped with two graph convolutions in the following combinations:
Lemma A.10. Let h(x) Rd
1. Both convolutions in the second layer of the two-layer network.
2. Both convolutions in the second layer of the three-layer network.
3. One convolution in the second layer and one in the third layer of the three-layer network.
4. Both convolutions in the third layer of the three-layer network.
Then for a sample (A,X) COR-CSBM(nn , d, μ. v, o², p. 9), the output of the networks in all the above described combinations for point E [n] is
0: = = (X) = deg(i)
R
Σ JEIn]
Tigh( (igh(s))
where Túj =
askakk deg(k)
kE
Proof. For the two-layer network, the output of the last layer when both convolutions are the second layer is given by f.2 (X) =
(2)) Then we have
X
R
aijatk (Xx)) deg(j)
R
Σ
TXy)(X,)).
(i
deg(i)
JEIn] kE
JE(m)
22

---

Published as a conference paper at ICLR 2023
Next, for the three-layer network, the output of the last layer when both convolutions at the second layer is given by s!
(X) (D-IA) w(()]) W(3),
hence, we have
1)
aij
Σ
Oij deg(j)
Σ axah((sa))
aznh(Xa)
deg(i)
deg(j)
jE[n]
jeInl
kE|ml
(zth(Xa))
(using [+] - [-t]+ t for any t E R)
deg( (
deg() (j)
jE(n]
kE[m)
R
Tiy Tx)
deg(1)
JEIn]
Similarly, the output of the last layer when one convolution is the second layer and the other one is at the third layer given by p!0) (X) = -D- LAAAAA--AAAWWWW A(x(()) w W hence, we have
(3)
X
R
Oij deg(j)
Σ (xx)(Xe))
Σ aga (Xx))())))))))))))))())))) kE(n)
deg
:E(n]
kE(
R
Oij
(Xs)(Xs)
(using [t]+ [-t]+ t for any t R)
deg(i)
deg(j
jE(n]
kE(n]
Tx))(X,).
deg(i)
jE/u]
Finally, the output of the last layer when both convolutions are at the third layer is given by f.¹) (X) = (D- ( w W(3), hence, we have
(3)
X
R
aij
Σ aje (Ih(X))]+
- (-)(Xx))+)
deg(i)
deg(ī)
jE(m]
kE[m]
R
aij deg())
R
axnh(X+))
Tx)
deg(i
= deg
jE(n)
kE(x)
jEIm]
Hence, the output for two graph convolutions the same for any combination the placement of convolutions, as long convolution is placed at the first layer.
We are now ready to prove the positive result for two convolutions.
Theorem (Restatement of part two of Theorem 2). Let (A,X) XOOR-SSM(nn, d, μ. v, 0² g).
Assume that p. 9 = 2 logn) and [p, q) ()((()/)) = (V logn
Then for any c 0, with probabil-
vn
iry least (n 9) the networks with any combination of two graph convolutions in the second and/or the third layers perfectly classify the data, and obtain the following loss:
(o(A, = CC'
-C''pp=CCC (-CooR 9) ((7/))(1 veflugn))
where and C' (1/2, 1) are constants and the constraint from Eq. (1)
(x) Proof. The proof strategy is similar to that of part one of the theorem. Note that 1,1 (xx) in Lemma A.10 is Lipschitz with constant
2
X
<
-
R
deg(i)²
Lip
jE(m)
23

---

Published as a conference paper at ICLR 2023
Since h(X,) are mutually independent for [n], by Gaussian concentration Vershynin 2018
Theorem 5.2.2) we have that for a fixed E [n].
8 degg(1) 4a jjE(n] 71)
L) (X) E R
Pr
A
< exxp
We refer to the event from Proposition A.2 as B. Note that since the graph density assumption is stronger than D 2(1oos") "). concentrate strongly around
Proposition A. trivially holds in this regime, hence, the degrees also
a
IPP + qJ. On event B, we have that
Σ
azkliik deg( (k)
Σ JE(m]
Σ RENN
(1=
A
JE(n]
jE[n]
kE
1
Σ
N N
+ Σ
1NN
(1+
2
jovs
joms
1
2 (p- + 9-)) + Σ (mpg)?
(1+
(using Proposition A.2)
2
jui
2
n
2A2
n
4
(p²
+
922 + n n²²²²0²
(1 (1=0n(1))
= 8A2
(p* + xr +6p (1 o,,
Therefore, under this event we have that
1 (L)
A(p² + 92 + 6p2
(x)
(1 o,,
R
deg(1)2
n(p + 9)*
Lip
jE(m)
Note that K = K(p, q) 4(p 4(p'tg +6p +6p"d" 2
< 4. We now define Q(t) be the event that (x)
(p+g)*
EfJ X:]] S for all [m]. Then we have
nt?
Pr[Q(t) = Pr (Q(t) n Pr n B < 2n exp
+ 2n -c
2K2
We now choose / = V
2k(o+1)logn
to obtain that with probability at least - 4n the following
holds for all E [n]:
log Ro
R
log
x
E
(X) 0
Try
Eh(x,) +
Ro
n
deg(1)
n
jEin]
Note that we have
V2((1/20)
Σ Tr,,(XX))
Σ Tij
Σ Téj
(using Lemma A.4
deg(i)
deg(i)
jEIm]
JECr
iECo
V2((1/20)
Σ
asaayk
Σ
a.s Oyk
dog(1)
(k)
dog(k)
JEC, kE(m)
JECa kE(n)
V2((7/20)
Osk deg(k)
Σ
ajk Σ
ajk
deg(i)
kE(mi
jEC,
jECo
(2(()
Σ ask
Σ
aik
(1 on (1))
deg(i)
kEC,
KECo
(1
24

---

Published as a conference paper at ICLR 2023
In the last two equations above, used Proposition A.1
replace, respectively,
1
Okj
Σ
Okj
= (2Ex - () +
deg(k)
IEC1
JECa
Σ
Oik
Σ jECr
0ik
(25x -
deg(1 i)
JECr
Therefore, we obtain that
log n n
1 (x)= Co) on + +0
Roy
= [C on(1));
where in the last equation we used (p, ((7/20) = (Vles //ogm
Recall that the loss for node i is given by
4 4 (A.X) log(1 exp((1 f1 (x)))
log (1 + exp (-CoR((1/22)IIi) 21 o,
The total loss E
EiE(n) ( (A, X). Now, using Fact A.5 we have for some O' E [/2, 1] that lo X) = C" exp (-Ca
oI))
A.8 ANALYSIS FOR A SIMPLER CASE
Although Theorem encapsulltess the general condition for networks with up to two graph convolu- tions to achieve perfect classification, let us discuss the meaning of the theorem in a simplified setting where (p, q) (2).. In this regime, one can analyze two cases for both parts of the theorem:
1. Case M(r): Using part two of Lemma A. implies that C(7/o) 52(2). Hence, for one graph convolution, the condition ['p, (1/22))))))))))))))))))))))))))) (V
log n((+イ))
is satisfied when 2
w
log n((+)g)) implying that 7 (ov
log n(p+q)
Similarly, for two graph convolutions,
the condition T(p, (2222))))2)))))))))) w
is satisfied when y = w
oov log
n
2. Case 7 o(o): Using part three of Lemma A.4 implies that ((7/O) 2 2(²) Hence, for one graph convolution, the condition I'(p, 4)((1/20)
log x(p+4)
is satisfied when
(2) 2 = w (v
log n(pto)
implying that 7 = w (a
log n m(p+g)
Similarly, for two graph convo-
lutions, the condition l'(p, q) ((T/2)))))) w (v log
is satisfied when 7 = w at
Combining both cases, find that the theorems imply perfect classification if the following holds:
52 avoog Va(pto) ayllgn Vn
for networks wth one graph convolution,
2112
for networks with two graph convolutions.
B ADDITIONAL EXPERIMENTS
For all synthetic and real-data experiments, we used PyTorch Geometric (Fey Lenssen 2019). using public splits for the real datasets. The models were trained Nvidia Titan Xp GPU, using the Adam optimizer with learning rate 10-3 -3 weight decay 10 - and 50 to 500 epochs varying among the datasets.
25

---

Published as a conference paper at ICLR 2023
B.1 SYNTHETIC DATA
In this section we show additional results on the synthetic data. First, we show that placing graph convolution the first layer makes the classification task difficult since the means the convolved data collapse towards 0. This is shown in Fig.
14
42-
Accuracy
Test
abhor
Thessood ML.
(a) Test accuracy.
(b) Test loss.
Figure 4: Comparing the accuracy and loss for various networks with and without graph convolutions, averaged over 50 trials. Networks with graph convolution in the first layer (red and orange) fail to generalize even for large distance between the means the data. For this experiment, we set 400 and d 4, with o² 1/d.
Next, show experiments for sets of values of < to demonstrate that graph convolutions also work in this setting. In Figs. 55b we have [ q) x 0.82, while in Figs. 5e and 5d we have a lower signal in the graph, T(p.g q) 0.66. We observe that in the latter case that there is less gap in the performance of networks with one graph convolution and those with two graph convolutions. In comparison to Fig. 2 we observe similar trends about the performance all the networks different regimes of interest. In particular, networks with one graph convolution perform mutually similarly, and networks with two graph convolutions perform mutually similarly, claimed in Theorem 2
Test Accuracy
Test Accuracy
ne will
Stae was de les?
Lig on with
dislgro"" tvancptrraod
M-
(a) Two-layer networks with (p. g) = (0.02,
(b) Three-layer networks with (p. (0.02,0.2)
Test Accuracy
Test Accuracc
UiF aithii lowe se nit Lu snteer)
Eiperaat eit sclpel
lipel se not 2id stlapel
M-
(c) Two-layer networks with (p. = 0.51.
(d) Three-layer networks with (p. = (0.1,0.5).
Figure Averaged accuracy (over 50 trials) for various networks with and without graph convolutions on the data model with 400, d 4 and o² = 1/a for p < q. The x-axis denotes the ratio K = || Ø/ly /a on a logarithmic scale. The vertical lines indicate the classification thresholds mentioned in part of Theorem (red), and in Theorem 2 (violet and pink).
26

---

Published as a conference paper at ICLR 2023
Finally, in Fig. show the trends for the accuracy of various networks with and without graph convolutions, for different values of [p, q). For cases where [p, q) is relatively larger, networks (seeFFigs. cases where (p) is much smaller, the networks with graph convolutions degrade in performance (see Figs. 6e to 6h). The intuition behind this behaviour is that smaller value of (pp,)) q) represents more noise in the data, thus, networks with graph convolutions gather roughly an equivalent amount of information from nodes both the classes, making the feature representations noisy.
with graph convolutions perform much better than standard MLP (see Figs. 6a to (d). while for the
Test Accuracy
Test Accuracy
loar net wit Go leer
Me Whattes 66
joai rit 2 G60 lear
Eieired ws connleerr
lysir zit wot (i ind)
light
Si Threeen 2.5
K 14
Two layers, (p. q) (0.1,0.01), 0.82.
(b) Three layers, [(p 9) 0.82.
Test. Accuraty
Accuracy
2 20 lovr
10
(c) Two layers, (p, (0.8,0.1), g() 0.78.
(d) Three layers, L(p 2) 0.78.
Test Accuracy
Test Accuracy
17
di
(e) Two layers, (p. ạ) (0.2, [(p,)) g) ss 0.33.
(f) Three layers, T(p. 9) R 0.33.
Test Accuracy
Tes Accuracy
lolr nat wit
Whrreass 66
loir nit act 2 Go lee
Zigaree es coleleer)
juorii wet 00 wo mne).
St ligh
K 14-Vi:
(g) Two layers, (p.g) (0.5, 0.4), (()) 0.11.
(h) Three layers, ['(p, 9) 0.11.
Test accuracy of various networks with with and without graph convolutions (GCs) for various values of p and q, on the XOR-CSBM data model. Note that networks with graph convolutions degrade in performance as ['(p, q) (attributed to the signal in the graph) decreases.
Figure 6:
27

---

Published as a conference paper at ICLR 2023
B.2 WORLD DATA
This section contains additional experiments real-world data. In Fig. 7 of the networks measured on the three benchmark datasets, averaged across 50 different trials (random initialization of the network parameters). This corresponds to the plots in Fig. that show the maximum accuracy across all trials. Next, we evaluate the performance of the original GCN
we plot the accuracy
Accuracy (avg)
40-
73.2
75.8
73.4
78.8
79.8
76.2
76.3
60-
32.8
21.10
21-01
3L:100
3L.000
5L-031
20-20
21-11
31-200
31.020
3L-032
3L-110
31-101
3L-011
Model
(a) CORA.
72.9
75.9
75.9
75.7
75.8
Accuracy (avg)
40
20
3L0:0
2L:Z Model
SL420
3L031
(b) Pubmed.
66.2
64.2
47.3
66.2
65.5
Accuracy (avg)
$2.3
50
40
20
21.30
Model
(c) CiteSeer.
Figure 7: Averaged accuracy (percentage) over 50 trials for various networks, A network with layers and ji....: convolutions each of the layers is represented by the label kLL ... jk.
normalization Kipf Welling 2017) D AD instead D 'A, and show that we observe the
same trends about the number of convolutions and their placement. These results are shown in Figs. 8 and Note the two general trends that are consistent: first, networks with two graph convolutions perform better than those with graph convolution, and second, placing all graph convolutions in the first layer yields worse accuracy as compared to networks where the convolutions are placed in deeper layers.
Similar to the results in the main paper, we observe that there are differences within the group of networks with the same number of convolutions, however, these differences smaller in magnitude as compared to the difference between the two groups of networks, one with one graph convolution and the other two graph convolutions. We also note that in cases, three-layer networks obtain
28

---

Published as a conference paper at ICLR 2023
worse accuracy, which attribute the fact that three layers have lot more parameters, and thus may either overfitting, or may not be converging for the number of epochs used.
73.0
$2.4
#1.5
$2.4
#1.5
02.4
#2.2
Accuracy (max)
40-
$8.6
60-
40-
MIP
21:30
21:01
10.00
310000
0L.01
21.20
22 Model
21:11
300200
91, 020
OL0022
30101
(a) CORA.
Accuracy (max)
40
74.7
77.9
78.3
79.1
60-
21-30
2L-01
3L-100
2L-00
3L-011
2L-00
2L-02 Model
21-11
2L-200
2L-020
2L-022
AL-100
2L-121
3L-011
(b) Pubmed.
30
69.7
69.0
69.5
$9.4
70.2
Accuracy (max)
$8.1
10
10-
N:470
11-031
21.00
31.200 11-000
31-022
M1-10
31-011
Model
(c) CiteSeer.
Figure 8: Maximum accuracy (percentage) 50 trials for various networks with the original GCN normalization D AD- network with & layers and ji,..., convolutions in each of the layers represented by the label kl--i Jk.
Furthermore, we perform the same experiments on relatively larger datasets, OGBN-arXiv and OGBN-products (Hu et al.) (2020). We observe similar trends in these experiments. First, we observe that networks with graph convolution perform better than a simple MLP, and that two convolutions perform better than single convolution. Furthermore, three graph convolutions do not have significant advantage over two graph convolutions. This observation agrees with Lemma A.3] where with|emma
compute p(2) and p(3) and realize that they of the same order in i.e., the variance reduction offered by two graph convolutions is of the same order as three graph convolutions for sufficiently dense graphs. We present the results of these experiments in Fig. 10
29

---

Published as a conference paper at ICLR 2023
10
73.9
78.4
76.5
75.3
79.3
78.0
76.8
Accuracy (avg)
$2.8
Model
(a) CORA.
76.5
78.7
76.8
76.7
75.3
75.7
78.3
Accuracy [avg)
20
3L-011
3L-200
Model
(b) Pubmed.
70-
63.9
63.2
F3.1
65.5
65.5
63.9
Accuracy (avg)
$1.8
50
21.10
3L.100
3L.00
3L.011
21-20
21.00
3L.200
3L.020
3L.022
3L-100
36111
3L.011
Model
(c) CiteSeer.
Figure 9: Averaged accuracy (percentage) over 50 trials for various networks with the original GCN normalization D - AD- A network with & layers and j1y-.., convolutions each of the layers represented by the label KL-ji ...
30

---

Figure 10: Averaged accuracy (percentage) for OGB datasets arXiv and products, over 10 trials for various networks. A network with layers and j....., J& convolutions in each of the layers is represented by the label kL-ji .e. while MLP3 denotes a three-layer MLP. Note that models Published as a conference paper at ICLR 2023
68.11
$8.01
71.46
71.31
71.43
71.43
71.61
71.51
71.3
Accuracy (avg)
70-
50-
40
20-
41.2
20-00
20:1
2L:05
2012
Model
(a) OGBN Xiv with two-layer networks.
80-
68.4
60.08
71.04
71.68
71.68
71.93
71.04
71.8
72.06
71.97
71.83
72.37
71.6
Accuracy (avg)
70
50-
42
30-
20
MIP
31.003
1L.110
36.100
3L-011
31-110
3L.022
3L-020
3L-111
36-023
1L.022
31-102
3L.033
31-300
3L-302
Model
(b) OGBN-arXiv with three-layer networks.
80-
69.16
72.34
Accuracy (avg)
70
30-
20
MUP
2L
2030
2L.22
21:20
2.11
2L:03
2030
2012
2621
Model
(c) OGBN-
OGBN-Groductt products with two-layer networks.
70.76
73.65
73.39
74.02
73.05
Accuracy (avg)
60-
30
20
MIP3
36-011
1L-010
36-000
11-011
36-10
3L-002
3L-200
31-111
36-22 11-012
36-22
11-003
3L-30
3L-303
Model
(d) OGBN-products with three-layer networks.
with one GC (in red) perform mutually similarly, while models with two GCs (in blue) and three GCs (in green) perform mutually similarly and better than models with one GC.
31


Reviews:
[{"review_id": "wHAQRAoWYFk", "reviewer": "Reviewer_k2Qb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work provides a solid theoretical understanding of the role of graph convolutions (GC) in multi-layer neural nets. The theoretical analysis is based on the node classification problem of a non-linearly separable Gaussian mixture model coupled with a stochastic block model (SBM). Under some mild assumptions, the authors proved theoretically that, from various perspectives, GC is beneficial for improving the capability of multi-layer nets for the node classification task. Extensive experimental studies on both synthetic and real-world data are provided to validate the theoretical results.", "summary_of_the_review": "Overall, I vote for accepting. The theoretical results and associated proofs are solid. The experimental results verify well their theories. ", "strength_and_weaknesses": "Strengths:\n+ The motivation to study theoretically the function of graph convolution operators in multi-layer networks is interesting;\n+ The theoretical findings as well as the corresponding analysis are beneficial for GNN researchers to get a better understanding on the effects of graph convolution layers; \n+ The authors show that for multi-layer networks equipped with graph convolutions, the classification capacity is determined by the number of graph convolutions rather than the number of layers in the network. This is also interesting and can motivate more future work toward a more profound understanding of the capability of deep GNNs.\n\nWeaknesses:\n+ The assumption behind the theoretical analysis should be clarified. To what extent can the theoretical results be generalized to broader cases, instead of a non-linearly separable Gaussian mixture model coupled with a stochastic block model?\n+ Potential limitation of the current theoretical analysis is not clear\n+ As mentioned in the first point of contributions, a single graph convolution, and two graph convolutions both improve the threshold by a certain factor. What are the key differences between the theoretical analysis for these two cases? Is there any space to further expand the theoretical results to multiple graph convolutions? This may help interested readers have a clear mind on this line of research.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "mR0z6Knmx8_", "reviewer": "Reviewer_Wv5W", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors try to prove that the performance of graph convolutions placed in different combinations among the layers of a neural network is mutually similar for all combinations of the placement.", "summary_of_the_review": "The theoretical analysis looks fancy, but some claims and conclusions seem trivial. The significance of this paper is not as strong as its analysis. It is a borderline paper. ", "strength_and_weaknesses": "## Strength\nThe analysis is comprehensive.\n\n## Weaknesses\n1. The assumption of the analysis is over-simplified.\n2. Some claims and experimental results are only valid for homophilic graphs, but not for heterophilic graphs. But I think it has the potential to be extended to homophily/heterophily problem.\n\n## Questions and Comments\n\n1. The 4th line in the first equation in section 2.2, is that f^L or H^L?\n\n2. How is your assumption over p,q related to homophily/heterophily problem identified in [1,2], e.g. heterophily is not always harmful and homophily is not always necessary for GNNs.\n\n3. How is your analysis generalized to more complex settings, e.g. multi-class classification or more general conditions on data generation distributions.\n\n4. “the placement of graph convolutions does not matter as long as it is not in the first layer”. Why the graph convolutions cannot be put into the first layer? How does this align with your previous analysis?\n\n5. “as claimed in Theorem 2, networks that utilize the graph perform remarkably better than a traditional MLP that does not use relational information.” I don’t think this conclusion is still valid on heterophilic graphs, see [2].\n\n6. Why not do more convolutions, e.g. 5 or 10? Do your claim and analysis still hold?\n\n[1] Ma Y, Liu X, Shah N, et al. Is homophily a necessity for graph neural networks?[J]. arXiv preprint arXiv:2106.06134, 2021.\n\n[2] Luan S, Hua C, Lu Q, et al. Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?[J]. arXiv preprint arXiv:2109.05641, 2021.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Jq1nT_QBg-", "reviewer": "Reviewer_vTDa", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the impact of graph convolutions on a binary node classification problem. In this setting, the relationships among nodes are sampled from a given stochastic block model and node features are associated with a Gaussian mixture model. Theoretical results on the performance of a two or three layer graph convolutional network on the node classification task are provided. Additionally, the performance is characterized in terms of number of graph convolutions and their placement. Interestingly, it is shown that placement of graph convolution in the first layer jeopardizes the node classification performance. Theoretical results are validated via experiments on synthetic and real world datasets. ", "summary_of_the_review": "This paper provides a solid theoretical contribution on the learnability of graph convolutional networks for a node classification task. My initial recommendation is accept. ", "strength_and_weaknesses": "Strengths:\n\nThis paper enhances the understanding of graph convolutions in learnability. Although the considered node classification problem is parametric and simpler than what is usually encountered in practice, the results in this paper are backed by rigorous theoretical analyses. Experimental validations on synthetic and real-world datasets are also provided.\n\nWeaknesses:\nI did not identify any major weaknesses. However, I could not understand how the hyper-parameters in the experiments were selected. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Jccv69dsov", "reviewer": "Reviewer_4qct", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides some theoretical conclusions, including:\n- GNNs are better than MLPs on graph data provided that node features are sampled from XOR-GNN (though it may be a little strong). \n- Any combinations of graph convolutions have similar performance as long as the number/order of graph convolutions is the same. \nSome experiments are also conducted to verify the theoretical conclusions. ", "summary_of_the_review": "I would like to update my score after reading other reviews and the response from the authors. ", "strength_and_weaknesses": "### Strength\n\n- The paper is well-written and easy to follow. The mathematical notations are clarified. \n- The paper theoretically shows that GNNs are better than MLPs for graph data under some preconditions (even though it may be a little strong).\n- The provided insight about \"what really matters is the number of graph operations rather than the way to combine it\" is interesting and impressive. \n\n### Weakness\n\n- The fundamental assumption of $X$ is that each feature vector is sampled from the XOR mixture of Gaussian models, XOR-GMM. Maybe it is strong for most cases. In particular, the graph is usually used for non-Euclidean data. What's more, why do we need the random variable $\\eta$ in XOR-GMM? \n- As the discussion is limited to XOR-GMM (Part-1 of Theorem 1), the authors only discuss the two-layer and three-layer cases, which is a little tricky.\n- It might be inadequate to use the same bound of both $p$ and $q$, since there should be a difference between the inter-class and intra-class probability. \n- The theoretical conclusion concentrates on the binary classification. Could the theory be generalized into the multi-class case? \n- In the footnotes of Page-3, the authors claimed that \" they readily generalize to other normalization methods\". Could the authors provide more discussions about how to generalize the shown proof to other normalization methods? I'm curious about this question but I could not check the proof very carefully due to the tight review deadline. \n- The readability could be further improved. For example, \n    - The definition of $\\gamma$ could be introduced in Theorem 1, so that the readers could find the variation of $\\gamma$ in both Theorem 1 and Theorem 2. \n    - At the end of the 3rd paragraph in Section 2.1, the subscript of $\\{X_i\\}$ should be $i\\in[n]$. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%