Optimality of Message-Passing Architectures for Sparse Graphs
Authors: Aseem Baranwal
Kimon Fountoulakis
Aukosh Jagannath
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
message passing
bayesian inference
node classification
contextual stochastic block model
TL;DR: We show that message-passing neural networks are optimal node classifiers on sparse feature-decorated graphs.

Abstract: We study the node classification problem on feature-decorated graphs in the sparse setting, i.e., when the expected degree of a node is $O(1)$ in the number of nodes, in the fixed-dimensional asymptotic regime, i.e., the dimension of the feature data is fixed while the number of nodes is large. Such graphs are typically known to be locally tree-like. We introduce a notion of Bayes optimality for node classification tasks, called asymptotic local Bayes optimality, and compute the optimal classifier according to this criterion for a fairly general statistical data model with arbitrary distributions of the node features and edge connectivity. The optimal classifier is implementable using a message-passing graph neural network architecture. We then compute the generalization error of this classifier and compare its performance against existing learning methods theoretically on a well-studied statistical model with naturally identifiable signal-to-noise ratios (SNRs) in the data. We find that the optimal message-passing architecture interpolates between a standard MLP in the regime of low graph signal and a typical convolution in the regime of high graph signal. Furthermore, we prove a corresponding non-asymptotic result.

Optimality of Message-Passing Architectures for Sparse Graphs
Aseem Baranwal
David R. Cheriton School of Computer Science University of Waterloo, Waterloo, Canada aseem. baranwal @wwrtarroawttrroooooooooo
Kimon Fountoulakis
David R. Cheriton School of Computer Science University of Waterloo, Waterloo, Canada kimon. www.:ootooookkiiituttteeeeeeeeee ca
Aukosh Jagannath
Department of Statistics and Actuarial Science,
Department of Applied Mathematics,
David R. Cheriton School of Computer Science University of Waterloo, Waterloo, Canada a. w..aaanathhuuutttroooocco
Abstract
We study the node classification problem feature-decorated graphs in the sparse setting, i.c., when the expected degree of a node is O(1) in the number of nodes, the fixed-dimensional asymptotic regime, i... the dimension of the feature data is fixed while the number nodes is large. Such graphs are typically known to be locally tree-like. We introduce notion of Bayes optimality for node classification tasks, called asymptotic local Bayes optimality, and compute the optimal classifier according to this criterion for fairly general statistical data model with arbitrary distributions the node features and edge connectivity. The optimal classifier implementable using
pesssag-paasiing graph neural network architecture. We then compute the generalization error of this classifier and compare its performance against existing learning methods theoretically well-studied statistical model with naturally identifiable signal-to-now the optimal pressage-passingg architecture interpolates between standard MLP in the regime of low graph signal and a typical convolution in the regime of high graph signal. Furthermore, we prove corresponding non-asymptotic result.
ratios (SNRs) in the data. We find that
Introduction
Graph Neural Networks (GNNs) have rapidly emerged powerful tool for learning graph- structured data, where along with features the entities, there also exists a relational structure among them. They have found numerous applications wide range of domains such social networks [Backstrom and Leskovec, 2011], recommendation systems [Ying et al., 2018, Hao et al., 2020], chip design [Mirhoseini et al., 2021]. bioinformatics [Scarselli et al., 2009, Zhang al., 2021]. computer vision [Monti et al., 2017], quantum chemistry [Gilmer et al., 2017], statistical physics [Battaglia al., 2016, Bapst al., 2020], and financial forensics [Zhang al., 2017, Weber et al., 2019]. Most of the success with these applications has been possible due to the advent of the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

message--assiin paradigm in GNNs, however, designing optimal GNN architectures for such a wide variety of applications still remains a challenging task.
In this work, we are interested in the node classification problem on very sparse feature-decorated graphs that are locally tree-like. We focus the regime where the dimension of the node features is fixed and the number of nodes is large. Our motivation for considering this regime is that many major benchmark datasets for node classification appear to scale in this fashion. For example, in the popular Open Graph Benchmark collection [Hu et al., 2020], the medium and large-scale node-property prediction datasets have roughly 10t nodes probunppodduss..... ogbn-mag) to about 10a nodes (ogbn-pan) peoonnpaprrsaee 100M), each with roughly 102 features. Graphs with such properties exist naturally in social, informational and biological networks: for motivational examples, see Stelzl et al. [2005], Adcock et al. [2013]. We present a precise definition of optimality for node classification tasks on locally tree-like graphs this scaling regime and compute the optimal classifier according to this definition, for a multi-class statistical data model where node features can have arbitrary continuous or discrete distributions. Subsequently, we show that message- message-passsng GNN architecture is able to realize the optimal classifier. Furthermore, we provide a theoretical analysis, comparing the generalization error of the optimal classifier with other architectures like GCN and simple MLPs. Our results support recent work [Veličković, 2022] in the context of classification sparse graphs. In particular, we show that when node features are accompanied by sparse graphical side information, message- meesagg-passing graph neural networks are able to realize the optimal classification scheme, and as such, there does not exist a better architecture beyond the message- paaggenggainggggg paradigm.
Related Work. There has been tremendous amount of work on GNN architecture design, where the most popular designs are based on a convolutional architecture, with each layer of the neural network performing a weighted convolution (averaging) operation with immediate neighbours, e.g., graph convolutional networks (GCN) [Kipf and Welling, 2017, Chen et al., 2020] or graph attention networks (GAT) [Veličković et al., 2018). These architectures are known to have several limitations regarding their expressive power (see, for e.g.. Li al. [2018], Oono and Suzuki [2020], Balcilar et al. [2021], Xu et al. [2021], Keriven [2022]).
An interesting line of research consists of both theoretical and empirical works that attempt to address these limitations by developing an understanding of GNN architectures within the scope of message-passing [Rong et al., 2020, Liu et al., 2022, Maskey et al., 2022], as well as beyond [Maron et al., 2019, Murphy et al., 2019, Chen et al., 2019]. For example, Xu et al. [2018] propose an architecture with a technique called skip-connections, that flexibly leverages different ranges of neighbourhoods for each node to enable structure-ad awareness in node representations, Chen et al. [2020] propose modification of the vanilla GCN with an initial residual that effectively relieves the problem of oversmoothing [Oono and Suzuki, 2020]. and Keriven et al. [2021] study the universality of structural GNNs in the large random graph limit. However, this area of research still lacks a clear understanding of optimality in the context of graph learning problems, making it hard to design architectures for which a well-defined notion of optimality can be theoretically justified.
Several works have studied traditional message-passing GNN architectures like GCN and GAT using the binary contextual stochastic block model, see for example, Baranwal al. [2021], Chien et al. [2022], Fountoulakis et al. [2022a,b]. Javaloy et al. [2022], Baranwal et al. [2023]. These analyses rely heavily on two assumptions: first, the graph is not too sparse, i.e., for graph with n nodes, the expected degree of node is S. (log" n v//n), and second, the node features are modelled Gaussian mixture. The work by Wei et al. [2022] is of particular interest to us, where the authors take a Bayesian inference perspective investigate the functions of non-lincarity in GNNs for binary node classification. They characterize the max-a--ooterior estimation of a node label given the features of itself and its immediate neighbours. A similar perspective that of Wei et al. [2022] is discussed in Gosch et al. [2023], where the latter authors derive insights into the robustness- accuracy tra in GNNs for node classification. In contrast to these inspiring works, we study the highly sparse regime where the expected degree of a node is (I) and consider nodes beyond the immediate neighbours, at any fixed distance. (In fact, our non-asymptotic results allow distances of order c clog n for small enough > 0, see Section 3.5 below.) Furthermore, our main result holds for a general multi-class statistical model with arbitrary continuous or discrete feature distributions and arbitrary edge-connectivity probabilities between all pairs of classes.

---

Our Contributions. In this paper, we use multi-class statistical model with arbitrary node features and ddge-connectivity profiles among all pairs of classes to study the node classification problem in the regime where the graph component of the data is very sparse, i.e., the expected degree is O(1). The data model is described Section 3.2. We state the following main results and findings:
1. We introduce family of graph neural network architectures that are asymptotically (in the number of nodes - oo) Bayes optimal in local sense for general multi-class data model with arbitrary feature distributions. The optimality is stated precisely in Theorem 1,
2. We analyze the architecture in the simpler two-class setting with Gaussian features, explicitly characterizing the generalization error in terms of the natural signal-to-noise ratio (SNR) in the data, and perform comparative study against other learning methods analyzed using the same statistical model (Theorems 2 and 3). We find two key insights:
When the graph SNR is very low, the architecture reduces to a simple MLP that does not consider the graph, while if it is very high, our architecture reduces typical convolutional network that averages information from all nodes in the local neighbourhood. In the regime between the low and high SNRs, the architecture interpolates and performs better than both a simple MLP and a typical GCN.
If the information in the graph is larger than a threshold, then a simple convolution is able to perform better than all methods that do not utilize the graph. Not surprisingly, this threshold aligns with the Sesten--tigum weak-recovery threshold for community detection in sparse networks [Massoulie, 2014, Mossel et al., 2018].
3. In the non-asymptotic setting with fixed number of nodes, we show that even for logarithmic depth, the neighbourhoods of an overwhelming fraction of nodes are tree- like with high probability. Subsequently, we show that the optimal classifier in the non- asymptotic setting obtains an error that is close to that incurred by the optimal classifier in the asymptotic setting. This is formalized in Theorem 4.
Let us end this section by reiterating that we work in the fixed -ied-dimeniional regime. It is natural to wonder as to the performance of this architecture as compared to optimal algorithms in the high- dimensional setting. We present numerical comparison of our work to the AMP-BP algorithm from Deshpande et al. [2018] in low and high-dimensional settings in Appendix B.
2
Architecture
This section explains the design of our GNN architecture for node classification. We perform two modifications to existing message-passing architectures. First, we decouple the layers in the neural network from the neighbourhood radius in the message-passing framework. This style of decoupled architecture has previously been studied, see for example, Nikolentzos et al. [2020], Feng et al. [2022], Baranwal et al. [2023]. Second, we introduce learnable parameter that models edge connectivity between each pair of classes and helps construct the messages to propagate. In the following, for any matrix M, we denote row i of M by M.,, and column i of M by M..-
Before stating our architecture, we need the following additional notation and pre-processing. Let é ' 0 and L, >> 0 be fixed integers. Let C 2 be the number of classes. For given data (A,X) where A E R is the adjacency matrix of an unweighted undirected graph, and X E R is the node feature matrix, we perform pre-computation on the graph to construct tensor À as follows:
(-r(E (<Aa)
)) for k E (1....,e).
A (k) S(A
)
where ((M) for matrix M returns the entry-wise flattened matrix with S(M)s = 1(M > 0). and (A, -) denote the entry-wise bit- bit- operators ('and', 'negation') respectively. Note here that A (R) an n x n binary matrix with À (b) 1 if and only if u is present in the distance neighbourhood of u but not within the distance (k- 1) neighbourhood. The idea behind this proceescesnng step is the following: for each node u and each & E [e]. we want to divide the radius neighbourhood of into l groups of nodes, where each group A E [e] consists of nodes that are within discovered the neighbourhood at each distance from given node. Á (k) models a non- banbbacktra walk of length k that considers new nodes in the distance-k neighbourhood that were not discovered.
3

---

We can now define the graph neural network architecture as follows.
Architecture 1. Given input data (A, where A E [0,1)axm is the adjacency matrix and X E Raxd is the node feature matrix, define:
(0) X,
H or (H + 1,, 1,)
for [4],
Q = sigmoid (Z),
(h) mn M max jE(C)
+ log (t,) for & E [q E [n], e [C].
u,
Then the predicted label is given by y = (Du (uejn where
0u = argmax
(L) u, +
Σ A M R=1
.E[c]
Let us pause here to comment on the interpretation the terms arising in this architecture. Here, HLL) is viewed as the output of a simple I--layer MI.P with (at)e being set of non-linear functions. We have (W()), b"") as the learnable parameters of this MLP, with suitable dimensions that ( R=xC, In addition, we introduce the learnable parameter Z E RCxC which is used model
edge connectivity among all pairs of classes. The quantity (k)
M (k) Eve(n ( M is viewed
(A)
as the sum of messages v, passed by all distance k neighbours of node
Although Architecture 1 follows the style of convolutional architectures like GCN and GAT for collecting messages within a local neighbourhood, the novelty lies in the construction of the messages M. Intuitively, Q = sigmoid(ZZ) learns the probabilities of edge connectivity between all pairs of classes so that Q models the probability of observing distance i path between pair of nodes in two classes. To predict the label of node u, the messages from other nodes v are constructed based on their features X,, their distance k from node u, and the path probabilities Q* We show in Theorem I that this architecture in sense (made precise in Definition 3.2) universally optimal among all node-classification schemes for sparse graphs. Our result thus aligns with the observations in Veličković [2022], showing that optimal neural network architectures for node classification on sparse graphs are implementable using the message-passing paradigm.
Theoretical Analysis and Discussion
In this section, present theoretical analysis of the message-passing GNN given in Architecture 1. We begin by defining a natural notion of optimality in our setting and show that among local learning methods on graphs, Architecture is optimal according to this definition on very general statistical model. We then compute the generalization error and compare the architecture to other well-studied methods like simple MLP and a GCN.
3.1 Asymptotic Local Bayes Optimality
For classification tasks, it is natural to use a notion of generalization error in a "per sample" or online sense. Without graphical side information, the natural choice is the Bayes risk. With graphical information, however, there is important obstruction: the number of samples is equal to the size of corresponding graph. As such, a naive extension of the Bayes risk does not have this property.
A natural approach would be to consider the Bayes risk for estimators that take in the node, the data set, and the graph, i.c., d.- fv, (X, G)). In this case, however, the risk necessarily implicitly depends on the sample size, n, through G. One might try to remove this dependence by taking the infinite sample size limit, but for a class of estimators this general, is not clear that such limit is well defined. To circumvent this issue, we restrict attention to node classifiers that are only allowed "local" information around the node. The large graph limit of the generalization error is then naturally interpreted via local weak convergence. (For the convenience of the reader, we briefly recall the notion of local weak convergence of sparse graphs in Appendix A. See also Ramanan [2021, Chapter I] or Bordenave [2016, Section 3] for more detailed expositions.) In this limit, one can then interpret the generalization error as per-sample error for the randomly rooted graph (G, u) where is a uniform random vertex in V V(G). (Here and in the following a rooted graph is a pair of graph G

---

and distinguished vertex, called the root.) With these observations, we are led to natural notion of Bayes optimality, namely asymptotic local Bayes optimality which we define presently."
Before turning to this definition, we must first recall the notion of l-local classifiers. For a node e in graph G, let ()= = {u V(G)= d(u, v) S k) denote the ball of radius for the canonical graph distance metric.
Definition 3.1 (f-local classifier). Let G = (A, be a feature-decorated graph of n vertices with d-dimensional features X., for each vertex u. For fixed radius é > O, an ê-local node-classifier is function f that takes as input a root vertex u E [n], the adjacency matrix A and the features of all nodes within the ě-neighbourhood of u, i.e., {X, (x)(()(())) and outputs classification label for u.
Suppose now that we have a sequence of (random) feature decorated graphs (X,, G.) with V(G)) n. Let uh denote a uniform at random vertex in G.. Suppose finally that the rooted feature-decoratee graphs (X,, G, M,,) locally weakly converge to (X, G. We can then define the notion of asymptotically f-locally Bayes optimal classifiers for this sequence of problems.
Definition 3.2. We say that a classifier hi E Ce is asymptotically Ê-locally Bayes optimal classifier of the root for the sequence {(X,, n. Gny "n if it minimizes the probability of misclassification of the root of the local weak limit, (X, G, u), over the class Ct, i.c.,
h = arggiin Pr [h(u,, (Xx) (Xo)vEm(u.G)) # uu]
hEC,
Before turning to our data model, we note here that the reader may ask whether or not the asymptoti- cally é-locally Bayes optimal classifier is in any sense the limit of optimal Ê-local classifier of the random root, uh. We show this in an appropriate sense in Theorem 4.
3.2
Data Model
Let us now turn the data model that use for our analysis. We work with the general multi-class contextual stochastic block model (CSBM) where each node belongs to one of C' different classes labelled 1, ...... C, and the node features have arbitrary continuous discrete distributions. This model with C = 2, along with a specialization to Gaussian features has been extensively studied in several works
(semi)-sppervise node classification and unsupervised community detection, see, for example, Deshpande et al. [2018]. Lu and Sen [2020], Baranwal et al. [2021], Wei et al. [2022], Fountoulakis et al. [20226], Baranwal et al. [2023]. Informally, CSBM consists of a coupling of stochastic block model (SBM) [Holland et al., 1983] with mixture model where the components of the mixture have arbitrary distributions and are associated with the blocks of the SBM.
More formally, let n, d be positive integers such that n denotes the number of nodes and d denotes the
dimension of the node features. Define ........ Vn {1...., C)} as the latent variables (class labels) to be inferred. We will assume that the latent variables have a uniform prior, i.c., Vu ~ Unif ([CC) for all u. For the relational part of the data, we have an undirected unweighted graph of nodes, G = (V. F) with adjacency matrix = (auv) (Qur)).ee(n) ~ SBM(n, Q). where Q = (7g) ) E [0, 1 is the edge-probability matrix, meaning that
Pr(ane = 1 yu i, 5) 4.j.
The node attributes, X E Rix are sampled from mixture of C' arbitrary continuous or discrete distributions, IP- = Jveey, where corresponding to the ya. we have X,, ~ Py,, for all u E [n]].
We will view n as large and study the setting where d is fixed (does not grow with n). We note here that in previous related works [Baranwal et al., 2021, Wei al., 2022. Baranwal et al., 2023], crucial assumptions have been made about the distribution of the node features and the sparsity of the graph, i.c., 4t = Ω2, (log" 12/1 n.) In contrast, we work in the extremely sparse setting where qúj bn/// for constants 61z- > 1, so we write Q = B/n where B {bty J. Furthermore, the only assumption we need about the distributions P; is that I, are absolutely continuous with respect to some base measure, in which case their densities exist, denoted by ps. For ease of reading, we encourage the
'It is also desirable for the empirical misclassification error to converge to the generalization error. If one works with the stronger notion of local convergence in probability, then this will hold as well. This later mode will hold in our examples but we leave this to future work.
5

---

reader to consider the case where P, are continuous or discrete, therefore, the base measure is simply the Lebesgue measure on R the counting measure on Z respectively.
For a feature-decorated graph G = (A, X) = (f (unee described above, we say that G CSBMM(n d, P, Q) or (x,hven) sampled from the model
(.aM(n,,,,BBII
3.3 Optimal Classifier
We are now ready to state our first main result that characterizes the asymptotically E-locally Bayes optimal classifier on the CSBM data described in Section 3.2.
Theorem 1 (Bayes optimal message-passen paaagee-aassigg.... For any 8 > 1, the asymptotically E-locally Buyes optimal classifier of the root for the sequence (Gn, Un) ~ CSBM(n, P, Q) is
hg (Xu (Xulven(()) = argmax { log (X.) +
Σ
Mid(u.a) (x.la,))(..)::
(E[C]
"EnE(M)) (1)
where (pilvetay are the densities associated with the distributions P, E e.P and
Mx((x= = -max flog p,(x) + log Q jE(C]
Let us briefly discuss the meaning of Theorem 1. It states that universally among all é-local classifiers, hū is asymptotically Bayes optimal for the sparse CSBM data. We view MaxXX, as the message gathered from node v that is distance i away from node u. In particular, Mx(X.,) naturally maximizes the likelihood of observing node v in class j at distance from node class i, over all j E [C]. Furthermore, this optimal classifier is realizable using Architecture 1 (see for example, Lu al. [2017, Theorem 1], where it is shown that any Lebesgue measurable function can be approximated arbitrarily closely by standard neural networks). Consequently, this result shows that in the sparse setting, the mnessage-passing paradigm can realize the optimal node classification scheme irrespective of the distributions of the node features or the inter-class edge probabilities.
For an intuitive understanding of Theorem it helps consider two extreme cases. First, if Q = pI for some E [0, 1]. then the classifier reduces to a simple convolution, h2(u) argmax,etc] (Even((u) log p: (X.)). Second, if Q pl1T, then Q; = for all i.j E [C], meaning that the graph component of the data is Erdös Réndi, and hence, completely uninfor- mative for the purposes of node classification. In this case, the classifier reduces to hī( [[ {log px(X..,), i.e., it is optimal to look at only the features of node u to predict its label since the neighbourhood does not provide any meaningful information. We formalize this intuition later for a simpler case (see Theorem 3).
3.4 Comparative Study
In this section, we perform theoretical analysis of the classifier in Theorem I using a well-studied specialization of the CSBM data model described in Section 3.2. For ease of discussion, let us restrict ourselves to the setting where there are two classes. Formally,
have C 2, and without loss of generality, the class labels yo E {+1} for all u E [n]. The distributions of the node features are given by X,,
P,,, with corresponding density Py..- Furthermore, Q {grh } is 2 x 2 matrix with Qú p = a/n. and Oiş q b/n with constants a > 1.b 2 for classes i + j. For a data sample G (A,X) from this model, we write G CSBM(n, d, [P+), Q) or G ~ CS,M(n, d, [P+), n. h). We also recognize the quantity associated with the signal-to-noise ratio (SNR) in the graph structure for this case, which is given by
p 1 p p+4 q
la bl b
r
Note that the quantity I' has been recognized as the meaningful SNR in several related works where the underlying random graph model is the binary symmetric stochastic block model, for example, Baranwal et al. [2021], Fountoulakis al. [2022b), Wei et al. [2022], Baranwal et al. [2023].
Let us now state Theorem in the case of two classes. For given input x E and > 0, let (0(z, c) min(max(2, -c), e) denote the value of clipped between the range [-c, cl.

---

Corollary 1.1 (Optimal classifier for binary symmetric CSBM), For any 8 2 1, the asymptotically
E-locally Bayes optimal classifier of the root for the sequence (Gn, Un) ~ CSBM(n, d, P, n n is
h2 (Xolvene(w)) sgn (vx(
Σ
Ma(no)) (X.)),
(Enu(a)
where Mx(x)= = sgu(a - b) (p(1((x), with Cj
log
1+rk 1-
and (x(x) log (x [x]
In this simplified setting, we note that the messages propagated from nodes in the é-local neighbour- hood of node u are clipped proportional to a function of their distance k from node u. In particular, the clip threshold ej. can be expressed in terms of the graph SNR [ from (1). It is interesting to observe in Corollary 1.1 that decreases rapidly as k increases. Since I < 1, this means that to predict the label of node u. the value of the message propagated from node at distance from decreases exponentially in k.
The above simplification helps us interpret the classifier in terms of the graph SNR Г. We will now impose an assumption on the distribution of node features. This will help us analyze the generalization error in terms of the SNR in both the features and the graph, and enable us compare the performance with other learning methods that are well-studied in the same statistical settings. We will resort to the setting where the features of the CSBM follow a Gaussian mixture. Note that this specialized statistical model has been studied extensively in previous works for benchmarking existing GNN architectures, see for example, Baranwal et al. [2021], Fountoulakis et [2022b], Wei et al. [2022], Baranwal et al. [2023].
In principle, one could compute the generalization error of hū for arbitrary distributions on the node features (see Appendix A.3.2), however, we report the error for Gaussian features for expository reasons. The generalization error is defined for classifier h to be the probability of disagreement between the true label yu and the output of the classifier h, for node u. We characterize the error for hū in the case where P P.. correspond the Gaussian mixture with components (V-u,, I2I and (i,, (T) for fixed la Rd and 02.
In this case, a notion of the signal-to-noise ratio of the features naturally exists, i.e., 7 = || /a, quantity proportional to the ratio of the distance between the means of the mixture and the standard deviation. The log- likelihoodd ratio in this setting is vx( log
P (x)
p- (x) (x,
Consider a sequence {(G,, un) (22) with Gn = (V(G.,,, E(G.)) from this model where un ~ Unif(V(G,, (G.)). ). In this setting, in the absence of features, is known that (G,, un) converges locally Galton-Watson
weakly to a Poisson Galton- Watson tree (see for example, Mossel al. [2015, Section 4J). Here, for every node, additionally have features that independent of the graph, and hence, straightforward consequence of Mossel et al. [2015, Section 4), (Gn, Un) in our case converges to a (cature-decoratee Poisson Galton- Watson tree (G, u).
For the root node u, let ag and 3a denote the number of children at generation in class yo and - Yu respectively, where Ya denotes the label of node u. Then {ax) and {5x J.20 are characterized by
ag 1, 30 O,
0g Poi [00k + bBx-1 , BR Poi (aBx-1 box for [[].
(2)
For a classifier h acting on G. let ((h denote the probability of misclassification of the root u in
G, i.e., E(h) Pr(halla < 0). Correspondingly, in the case of finite n, we denote by &, (h) the probability of misclassification of a uniform random node un in G.. We are now ready to state the generalization error of hi.
Theorem (Generalization error). For any l. 2 1, the generalization error of the asymptotically t-locally Bayes optimal classifier of the root for the sequence (Gns un) CSBM(n, d, P. Q) with Gaussian features given by
(h;) Pr
g
Σ
Σ
bb) k.
>
2-
kEle]
|E|aul
IIn principle, it is easy to analyze arbitrarily fixed means, say instead of keeping them symmetric, i.c., +4, with only minor changes in calculations.
7

---

where ok By are as in (2), 4 = = + 27 c.), --1 = ( + +Yggk,6 Cx), and g, {gk.s
are mutually independent standard Gaussian random variables.
Let us now understand how the error described in Theorem 2 behaves in terms of the two SNRs 7 (for the features), and I' (for the graph). Note that {(h;) - as 7 - oo, and {(;;) + 1/2 as 7 + O. This means that if the signal in the features is large, the number of mistakes made by the classifier vanishes, while if the signal is very small, then roughly half of the nodes are misclassified (equivalent to making a uniform random guess for each node).
To how I affects the error, we begin by looking at two extreme settings: first, where the graph is complete noise, i.e., r = 0, and second, where the graph signal is very strong, i.e., P - 1, followed by discussion how h interpolates between these extremes. Let Φ+ denote the Gaussian density functions with means z and variance o²Ia Define the random variable
1+ Ei= lau- 3xl
= Ec(aa),
V1 Ei=r(ak + 3kk
where agg, By follow (2). In the following, denote the vanilla GCN classifier from Kipf and Welling [2017] by lggen We then have the following result.
Theorem 3 (Extreme graph signals). Let hū be the classifier from Corollary 1.1, hi (u) sgn((X,, pi)) be the Bayes optimal classifier given only the feature information of the root node u, and Agen be the one-layer vanilla GCN classifier. Then we have that for any fixed E:
1. IfT = 0 then E(hT) = E(h)) = ((-7), where is the standard Gaussian CDE.
2. IʃT + then &r 2 1 a.s. and (h;)) - Pr(g >> TEt). where g 1),
3. (hhccu) Pr (g > 751).
Theorem 3 shows that in the regime of extremely low graph SNR, the optimal classifier hü reduces to a linear classifier (u) = Sggn(X.., 11)), which can be realized by a simple MLP that does not use the graph component of the data at all. On the other hand, in the regime of extremely strong graph SNR, h3 reduces to a simple convolution over all nodes in the é-neighbourhood and is comparable to a typical GCN. Furthermore, we note that in the strong graph SNR regime I - 1. E(h2) - Pr(g > rEt) S ((-7) since & 2 1. The clip operation during the propagation of messages makes things interesting between these two extremes, where hy interpolates between simple MLP and an ε-hop convolutional network. This interpolation is characterized by the graph
signal I, since the messages are clipped in the range [-ck, cx). where C+ = =log 1-1e
1+r
In addition, Theorem 3 concludes that if (1 b) > 1, then a GCN can perform better than every classifier that does not see the graph. On the other hand, if & (a, < 1, then a GCN incurs more errors the data than the best methods that do not use the graph. Interestingly, but not surprisingly, this result aligns with the Kesten-Stigum weak recovery threshold for the community-detedd problem the sparse stochastic block model [Massoulié, 2014, Mossel et al., 2018], meaning that if weak recovery is possible on the graph component of the data, then a GCN is able to exploit it to perform better than methods that do not use the graph, e.g., a simple MLP.
We now demonstrate our results through experiments using pytorch and pytorch-geometric [Fey 10000 and d = 4 for binary
and Lenssen, 2019]. The following simulations are for the setting classification on the CSBM. We implement Architecture for the binary case, and perform full-batch training graph sampled from the CSBM with certain signals (mentioned in the figures), followed by an evaluation of the architecture on a new graph sampled from the same distribution.
In Fig. 1, we show that the accuracy obtained by the optimal classifier is higher than both a simple MLP and a vanilla GCN [Kipf and Welling. 2017]. We plot the test accuracy of Architecture I against the SNR in the node features, 7 = || /o in Fig. la, and against the graph SNR I = |a bl/(a b) in Fig. 1b. We fix r = 0.42 and 7 = for the two plots, respectively. We chose these specific values because they generate relatively clearer plots where the accuracy metrics for the three architectures are easily visible and distinguished from each other. The results are similar for other values for I and y, i.c., the Bayes optimal architecture is superior to both MLP and GCN.
8

---

16
Accuracy
Accuracy
Bayes Optimal
Bayes Optimal
MLP
MLP
GCN
GCN
GMM signal Y
Graph signal r
(a) Varying y with fixed r 0.42.
(b) Varying I with fixed y =
Figure 1: Comparison of Architecture against an MLP and a vanilla GCN [Kipf and Welling, 2017].
Furthermore, Fig. shows that as claimed Theorem when graph signal is at the extremes, i.e., r = 0 and | = 1, Architecture 1 behaves like simple MLP and performs typical convolution (averaging) over all nodes the Ł-neighbourhood, respectively. In the regime of poor graph SNR, ie., I = 0, GCN is worse than simple MLP, as inferred from part three of Theorem 3.
Accuracy
Bayes Optimal
Accuracy
00-
MLP
Bayes Optimal
GCN
MLP
GCN
GMM signal Y
GMM signal Y
(a) Fixed graph signal r
(b) Fixed graph signal I =
Figure 2: Demonstration of Theorem for extreme graph signals. In the case where T 0, the architecture reduces MLP (Fig. 2a), while if = behaves the same GCN (Fig. 2b).
Finally, we observe that for the binary setting when the parameters of the architecture are initialized uniformly at random, gradient descent converges and the neural network learns the right parameters such that Architecture 1 realizes the optimal classifier in Corollary 1.1. This convergence, along with a comparison our architecture the Approximate dessage-passingg Belief Propagation (AMP-BP) algorithm from Deshpande et al. [2018] is presented in Appendix B.
3.5 Non-asymptotic Setting
We now turn the non-asymptotic regime and argue that for fixed n, the classifier in Corollary 1.1 is still in a formal sense, Bayes optimal for an overwhelming fraction of nodes. We begin by exploiting the fact that for up to logarithmic depth neighbourhoods, a sparse CSBM graph is tree-like.
= b) for constants Proposition 3.1 (Tree neighbourhoods). Let G (V, ~ CSBM(n, d, P, a
b> 1. Then for any &. c. log such that c (o)(((++))/2) < 1/4, with probability 1 O(1 log n), the number of nodes E V whose L-neighbourhood is cycle-free is n(1 o(log' (n)/vm))
In particular, Proposition 3.1 states that for c clog n for suitable constant c, the ý-neighbourhood of overwhelming fraction of nodes is tree. This implies that the classifier h3 is Bayes optimal for roughly of the nodes. Moreover, since the diameter of sparse graph (as in our setting) is O n) almost surely [Chung and Lu, 2001, Theorem 6]. any learning mechanism can only look as far as (log n) -hops away from a node to gather new information. This shows that for such graphs, GNNs that not very deep and look only up logarithmic distance in the neighbourhood sufficient.
Let us now turn to the misclassification error in the non-asymptotic setting. Recall that for classifier h Cz, denote by (h) and Ehh) the misclassification error of h on the data model with nodes,

---

and on the limiting data model with n - oo, respectively. Furthermore, recall from Corollary 1.1 that minnec, E(h) (h;).. Our next result shows that the optimal misclassification error the non- asymptotic setting across all ê-local classifiers, i.e., minnec, &n (h), is close to the misclassification error obtained in the non-asymptotic setting by hg. Moreover, minkec, &n (h) is also close to & (lhi)
which is explicitly computed in Theorem 2.
Theorem 4 (Misclassification error for fixed n). For any I L Σ clog n such that the positive constant e satisfies e log( 2 < 1/4, we have that
min En (h) En (h:) 0 kECe
min En(hh {hb) O NECE
log"
log²
Recall that Corollary 1.1 implies that h performs optimally on the limiting data model (asymptotic setting) among the class of é-local classifiers Cr. but may not be optimal for the non-asymptotic data model where we have finite feature-decorater graph with n nodes. However, Theorem 4 helps us conclude that even the non-asymptotic setting, hū performs almost as well as the actual optimal classifier among Cę in this case, long compare with classifiers that can only look at moderate logarithmic depths in the local neighbourhood, i.c., E S c log n for a suitable c.
4 Conclusion and Future Work
In this work, we present a comprehensive theoretical characterization of the Bayes optimal node classification architecture for sparse feature-decorated graphs and show that can be realized using the trassage-passingg framework. Utilizing well-establisher and well-studied statistical model, we interpret its performance in terms of the SNR in the data and validate our findings through empirical analysis of synthetic data. Additionally, we identify the following limitations as prospects for future work: (1) We consider neighbourhoods up to distance = clog n for a small enough c. Extending é to the graph's diameter (known to be (log n) with high probability) by removing the restriction on e poses challenges due to the presence of cycles. (2) More insights can be provided through experiments on real data to benchmark the architecture in cases where we have significant gap between the theoretical assumptions (sparse and locally tree-like graph) and the real-world data.
Acknowledgments and Disclosure of Funding
A.J. acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Canada Research Chairs programme. Cette recherche été enterprise grâce, en partie, au soutien financier du Conseil de Recherches en Sciences Naturelles et en Génie du Canada (CRSNG), IRGPIN-2020-0455) du Canada.
2020000-2200009991 et du Programme des chaires de recherche
K. Fountoulakis would like to acknowledge 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 en génie du Canada (CRSNG), IRGPIN-2019-04067, DGECR-2019-001-44
References
A. B. Adcock, B. D. Sullivan, and M. W. Mahoney. Tree-like structure in large social and information networks. In 2013 IEEE 13th International Conference on Data Mining, pages 1-10, 2013. doi: 10.1109/CDM22211..77.
L. Backstrom and J. Leskovee. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference Web search and data mining, pages 635-644, 2011.
M. Balcilar, G. Renton, P. Héroux, B. Gaüzère, S. Adam, and P. Honeine. Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. In International Conference on Learning Representations, 2021.
V. Bapst, T. Keck, A. Krabska-Barwiissee C. Donner, E. D. Cubuk, S. S. Schoenholz, A. Obika, A. W. Nelson, T. Back, D. Hassabis, et al. Unveiling the predictive power of static structure in glassy systems. Nature Physics, 16(4):448-454 2020.
10

---

A. Baranwal, K. Fountoulakis, and A. Jagannath. Graph Convolution for Semi- Semi-Supevvieed Classifica- tion: Improved Linear Separability and Out-of-Distribution Generalization. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proc. of Mach. Learn, Res., pages 684-693. PMIR, 18-24 Jul 2021.
A. Baranwal, K. Fountoulakis, and A. Jagannath. Effects of Graph Convolutions in Multi-layer Networks. In The Eleventh International Conference on Learning Representations, 2023.
A. D. Barbour and L. H. Y. Chen. An introduction to Stein's 's method, volume 4. World Scientific, 2005.
P. Battaglia, R. Pascanu, M. Lai, J. Rezende, and K. Kavukcuoglu. Interaction Networks for Learning about Objects, Relations and Physies. Advances Neural Information Processing Systems (NeurIPS), 2016.
C. Bordenave. Lecture notes random graphs and probabilistic combinatorial optimization, 2016.
L. H. Y. Chen. Poisson Approximation for Dependent Trials. The Annals of Probability, 3(3):534 545, 1975.
M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li. Simple and Deep Graph Convolutional Networks. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 13-18 Jul 2020.
PMLR,
Z. Chen, S. Villar, L. Chen, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buse E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
E. Chien, W.-C. Chang, C.-J. Hsieh, H.-F. Yu, J. Zhang, O. Milenkovic, and I. S. Dhillon. Node Feature Extraction by Supervsuee Multi-scale Neighborhood Prediction. In International Conference on Learning Representations, 2022.
Chung and L. Lu. The diameter of sparse random graphs. Advances in Applied Mathematics, 26 (4):257-279, 2001.
Y. Deshpande, S. Sen, A. Montanari, and E. Mossel. Contextual Stochastic Block Models. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
J. Dreier, P. Kuinke, B. Le Xuan, et al. Local Structure Theorems for Rédos-Rényí Graphs and Their Algorithmic Applications. SOFSEM 2018: Theory and Practice of Computer Science LNCS 10706, page 125, 2018.
J. Feng, Y. Chen, F. Li, A. Sarkar, and M. Zhang. How powerful are k-hop message passing graph neural networks. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances Neural Information Processing Systems, 2022.
M. Fey and J. E. Lenssen. Fast Graph Representation Learning with Py PoTch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
K. Fountoulakis, D. He, S. Lattanzi, B. Perozzi, A. Tsitsulin, and Yang. On classification thresholds for graph attention with edge features. arXiv preprint (00::2210.101111 2022a.
K. Fountoulakis, A. Levi, S. Yang. A. Baranwal, and A. Jagannath. Graph Attention Retrospective. arXiv preprint arXiv:2202. /3060, 2022b.
J. Gilmer, 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 on Machine Learning. 2017.
L. Gosch, D. Sturm, S. Geisler, and S. Günnemann. Revisiting robustness in graph machine learning. In The Eleventh International Conference on Learning Representations, 2023. URL https: /ttpe:://pppeeereeeeeee httt:/orrmmiiddho//lla.e.

---

J. Hao. T. Zhao, Li, X. L. Dong, C. Faloutsos, Y. Sun, and W. Wang. P-companion: A principled framework for diversified complementary product recommendation. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 2517-2524, 2020.
W. Holland, K. B. Laskey, and Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-1377 137, 1983.
W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems, 2020.
A. Javaloy, S. Martin, A. Levi, and I. Valera. Learnable graph convolutional attention networks. In Has Trained Yet? NeurIPS 2022 Workshop, 2022.
N. Keriven. Not too little, not too much: theoretical analysis of graph (over)smoothing. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
N. Keriven, A. Bietti, and S. Vaiter. On the universality of graph neural networks large random graphs. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 1960-6971. Curran Associates, Inc., 2021.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations (ICLR), 2017.
Q. Li, Z. Han, and X.-M. Wu. Deeper insights into graph convolutional networks for sumi-supervised learning. In Thirty-Seen Second AAAI conference on artificial intelligence, 2018.
Liu, S. Jing, T. Zhao, Z. Huang, and D. Wu. Enhancing Multi-hop Connectivity for Graph Convolutional Networks. In First Workshop Pre-training: Perspectives, Pitfalls, and Paths Forward ICML 2022, 2022.
C. Lu and S. Sen. Contextual Stochastic Block Model: Sharp Thresholds and Contiguity. ArXiv, 2020. arXiv:2011.096
Z. Lu, H. Pu, F. Wang, Z. Hu, and L. Wang. The expressive power of neural networks: A view from the width. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, Fergus, Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019.
S. Maskey, R. Levie, Y. Lee, and G. Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
L. Massoulié. Community Detection Thresholds and the Weak Ramanujan Property. In Proceddings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, page 694-703, 2014.
A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, A. Nazi, et al. A graph placement methodology for fast chip design. Nature, 594(7862):
207-212, 2021.
F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein. Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), July 2017.
E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162:431-461, 2015.
E. Mossel, Neeman, and A. Sly. proof of the block model threshold conjecture. Combinatorica, 38(3):665-700 2018
12

---

R. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro. Relational pooling for graph representations. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4663-4675 PMLR, 09-15 Jun 2019.
G. Nikolentzos, G. Dasoulas, and M. Vazirgiannis. k-hop graph neural networks. Neural Networks, 130: 1951995-5- 2020.
K. Oono and Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In International Conference on Learning Representations, 2020.
K. Ramanan. CRM-PIMS Summer School 2021: Background Material For Mini Course on Asymp- totics of Interacting Stochastic Processes Sparse Graphs, 2021.
Y. Rong, W. Huang, T. Xu, and J. Huang. DropEdge: Towards Deep Graph Convolutional Networks on Node Classification. In International Conference on Learning Representations, 2020.
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.
C. Stein. A bound for the error the normal approximation the distribution of sum of dependent random variables. In Proc. Sixth Berkeley Symp. Math. Stat. Prob., pages 583-602, 1972.
U. Stelzl, U. Worm, M. Lalowski, C. Haenig, F. H. Brembeck, H. Goehler, M. Stroedicke, M. Zenkner, A. Schoenhem, S. Koeppen, et al. A human protein-proteid interaction network: a resource for annotating the proteome. Cell, 122(6):957-99) 968, 2005.
Veličković. Message passing all the way up. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Bengio. Graph Attention Networks. In International Conference Learning Representations, 2018.
P. Veličković. Message passing all the way up, 2022.
R. Vershynin. Hligh-Dimensinnn Probability: An Introduction with Applications Data Science, volume 47. Cambridge University Press, 2018
M. Weber, G. Domeniconi, J. Chen, D. K. I. Weidele, C. Bellei, T. Robinson, and C. E. Leiserson. Anti-money laundering bitcoin: Experimenting with graph convolutional networks for financial forensics. arXiv preprint arXiv: 02591, 2019.
R. Wei, H. Yin, J. Jia, A. R. Benson, and P. Li. Understanding Non-linearity in Graph Neural Perspective. In A. H. Oh, A. Agarwal, D. Belgrave, and
Networks from the K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation Learning on Graphs with Jumping Knowledge Networks. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 3453-5462, PMLR, 10-15 Jul 2018.
K. Xu, M. Zhang, J. Li, S. Du, K.-I. Kawarabayashi, and S. Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. In International Conference Learning Representations, 2021.
R. Ying, He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovee. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974-983, 2018.
S. Zhang, D. Zhou, M. Y. Yildirim, S. Alcom, J. He, H. Davulcu, and H. Tong. Hidden: hierarchical dense subgraph detection with application to financial fraud detection. In Proceedings of the 2017 SIAM International Conference on Data Mining, pages 570-578. SIAM, 2017.
X.-M. Zhang, L. Liang, Liu, and M.-J. Tang. Graph neural networks and their current applications in bioinformatics. Frontiers in genetics, 12:690049, 2021.
13

---

A Supplementary Discussion and Proofs
A.1 Local Weak Convergence
We briefly recall here the notion of local weak convergence of random rooted graphs. The notion of local weak convergence of random, feature-decorated, rooted graphs is defined analogously.
Let us begin first with the case of rooted graphs. A rooted graph (G, u) = ((E, V). is graph G with distinguished vertex called the root. We say that two rooted graphs (G "1) ((E,, Vi), ut).
(G2, u2) = =(E2, V2), u2) are isomorphic there a bijection ø VV + 1/2 such that d(u) = v and such that if (ar 3) E Ei then (Ø(z), (())) E Ez. In this case we write w1) = (G2, U2). For rooted graph (G, u), we denote its isomorphism class as [(G, u)].
Let G. denote the set of isomorphism classes of (locally finite) rooted graphs. For vertex E G we let (v) denote the collection of neighbours of v of distance at most & in the canonical edge distance metric, and G (v)] denote the subgraph induced on this collection of vertices. We then have the notion of local convergence in G..
Definition A.1 (Local convergence on G.). We say that a sequence [G,, un)] E G. converges locally to [G, u)] G. if for each O, we have that G'me (un)] G(T% (u) eventually.
can be shown [Bordenave, 2016, Lemma 3.4] that G. equipped with the topology of local conver- gence is Polish space. We are then in the position to define local weak convergence on G. In brief, the topology of local weak convergence random graphs is the topology of weak convergence of measures the space of probability measures on Gu, namely M1(G.).
Definition A.2 (local weak convergence of rooted graphs), A sequence [[G,, un]} of random rooted graphs with corresponding laws {un} C (G.) is said to locally weakly converge to random rooted graph [G, u| with law μ E (G.) if pn > l weakly.
We note here that it is common also to talk about the notion of local weak convergence of a sequence of (finite) random graphs G,, In this case G, + G locally weakly if [[G,, u,)] - [(G, u)] locally weakly where u. ~ (G..).
A.2 Preliminary Results
In this section, we state two important preliminary results and fact that are used to establish our results in the paper.
Lemma A.1. (Dreier al., 2018, Lemma 3]. Let G ~ CSBM(n, d, PPP 2 b) and r be fixed constant. Then the probability that there exists an r-neighbourhood in G with m more edges than the number of vertices is bounded as follows:
ni
Pr(3 G, C.G.I.S.. s.t. |E(G,)) 2 (V S (2(((m+1)) +1)) + b)) 20)mm+mm))
nh
Lemma A.2. [Massoulié, 2014, Lemma 4.2). Assume clog(n) with clog A < 1/4, where A = b)/2. Then with high probability, node has more than one cycle in its t-neighbourhood. Moreover, for any m > with probability at least 1 - (11m²²) the number of nodes whose E-neighbourhood contains at least one cycle is bounded by (m log (n)
Fact A.3. For any non-negative u, v, x, such that x. 3) S 1,
(xu + yu)² < - (1 x) (1 y)² S zu ye.
zu + yv
A.3 Bayes Optimal Classifier
In this section, we compute the asymptotically é-locally Bayes optimal classifier for the general CSBM described in Section 3.2 and establish Theorem 1, followed by proof of Corollary 1.1. Next, we compute the generalization error for the two-class case with arbitrary node features.
A.3.1 Computing the Classifier
For the proofs, we introduce the notation (u) for given graph to mean the set of vertices that at distance of exactly & from node in the graph. Thus, Th (u) {w) Uا_ (u).
14

---

Theorem (Restatement of Theorem 1), For any 8 2 1, the asymptotically f-locally Bayes optimal classifier of the root for the sequence (G,, Up) CSBM(n, d, Q)
(u, (Xoleem())) = arginax { log (X..) + iE|O]
Σ
Mi
where (pilietoy are the densities associated with the distributions P, E and
Mx = max {log Pj(()) + log Q
jEIC
Furthermore, there exists choice of parameters for Architecture / such that it realizes h.
Proof. We begin by writing the MAP estimation for this problem. Note that the features X, Rd for every node v E [n]] follow the law P, if yu = E [C]. In addition, recall that we have the edge-probability matrix Q {ag hijeje with Pr((u, v) is edge 1/u i, y/ = =) Piz where Qsj big/r for absolute constants bij. Then can write the likelihood of the f-neighbourhood of node u as the joint function:
f'u, ((X,,, Uo) (e) (((l))))PPt)aee))e -ttyolocngts Puo (X.) II kE[ vEN((u)
II
Pv. (X., (
In the above, Q denotes the j. entry of the matrix Q' and quantifies the probability that node in class j is at distance & from a node in class i; while P (v. leenytu) denotes the prior distribution of the node labels, which by our assumption is uniform. Let us now compute the MAP estimator.
h2(u, (Xo = argmax max f(u, {(Xu: Bo) (w)
VE[C]
[b,[C]]}
(Enz(u)
argmax P: (X...
II
II
Pj (X,)
<E[c]
kE|d (EN)(u) %E|C
argmax log Ps (x)) <E(C]
+ Σ
Σ
max (log(p; + log (%1)) jE(G)
kEll
(w)
argmaax log P (X.) VE[CI
Σ KE[B (EN
Σ
max Ma (X.),
JE(C)
where (X.) = log(p,(X.))) + loooog(( (Qt)). Furthermore, note that an instance of Architecture I with L = 1, = {pi hiecc,. and Q for the adge-probabilities realizes the function hū for given root node и and its E-neighbourhood me (e)).. in the sense that ÿ.. = 12 (u, [X.)
Next, we obtain simpler version the classifier for the two-class symmetric CSBM with an arbitrary distribution of node features. Recall that &b is the log of the likelihood ratio.
Corollary (Restatement of Corollary 1.1). For any e 2 1, the asymptotically f-locally Bayes optimal for rootfor the sequence (G,,, u,)) ~ CSBM(n, d, P. a n
classifier of the root
#) is
(ū, (Xohven((u)) sgn (xx) +
Σ
Ma(u.r) (X,)),
vEn((a)
where Mx(x) = sgn(a - b) (p(((x),, with cg = log
1+12 I-TX
and v0(x) = loog (x) p- (x))
Proof. The proof follows directly from Theorem 1, by taking C = 2. In this two-class case, the features X, E Rd for every node follow the law Py,. where the class labels E {F1) are Unif([-1,+1]) In addition, we have
Pr((u, v) is edge)
pp
Vu Vv
q
yn + Vh
15

---

where p a/n and b/n for absolute constants a > 1,6 2 0. Define the quantities pkd Q as follows for k E [e]:
1//21
k2/2
k
h
Pk Σ
9k - Σ
p 2j 2
2j
2j
Then we can simplify the likelihood of the (-neighbourhood of node u from (4) as follows:
Fl((Kx,, = Pvu. (X.) kE(4] vENN(a)
II
II
(pu. (o.x
1 1-
9k
Then maximizing the likelihood over possible class labels, we have
(u, (Xx E (v+E(#)) vEni(u)
argmax max ((((Ke:Vo)Devvi)
= argmax max 1= ((LI) (EN((M)
log [( (o))m(w))
argmax M=E(21}
log Pyu (Xu)
max
Σ
log (pv. (Xn)Pz
Hixaan 1 you
4x
(++E(#))
vEne(a)
kETe vENN(())
log P+ (X.)
Ma(X.))
Σ
sgn
p_ (X,)
kE[A] vEN+(u)
where Mx(x)= log (og(mmx(())) (papa (x), "xp (x))) log (anmm(xxppp--aa (x), qxp+ (x)))- Next, we observe that for any w, v. y, = E IR,
log( (maxaxwyg xz), log wow.(maxx (max(wx,xz)) = sgn(w-st x) min max [log z²'
w log -
W
log
Hence, M₁ (X+) is simply sgn(a b) :pllog P+ (_(x.) between -Ck and
Ck), i.e., the signed likelihood ratio clipped
A.3.2 Generalization Error
Let us now compute the generalization error of hjs Formally, given data instance (v, (X, (v)m(()) along with the neighbourhood me (u), hü outputs a label f.. {=1}, and the generalization error defined as the probability Pr(yağu < 1). For a simple calculation, let us assume that the latent labels y/ are uniformly distributed, i.e., Pr(y: = -1) Pr(y, = 1) 1 It is straightforward to generalize to unbalanced settings. Recall that the features classes +f follow the law P., and denote by the log likelihood ratio by (xx) = log(p+ (x)/p-xx)))))))) Then we have that for fixed
P+ (X() P (X..)
E(hī)= = Pr
Yu log
Σ
Σ
Ma(X.)) <0
KE[T vEN
1 <0) ]
Pr 4b (1)) +
0
+ Pr
(( +
2
kE
KE
where (70) = Eje(au) M&
ky + Ma kg) and z,00 = Σ Ejelau] MA (Y
RJ
Σjela MY k.)) are independent random variables with Y k.j P and Y (2) P++
The above expression is not particularly insightful. For this reason, we now specialize to the case of Gaussian features and interpret the error terms of the natural SNRs associated with the Gaussian mixture and the graph, i.c., the quantities y and l.
16

---

A.4
Specialization to Gaussian Features
In this section, we look at the specialized setting where the node features are sampled from symmetric binary Gaussian mixture model. Let us begin with the generalization error in this case.
A.4.1
Generalization Error
Theorem (Restatement of Theorem 2). For any i 1, the generalization error of the asymptotically l-locally Bayes optimal classifier of the root for the sequence (Gns Un) ~ CSBM d, P. Q) with Gaussian features given by
E(h)) Pr
g
Σ
(b) ku
>9
27
kE[(]
(E(ag]
[E(
where okk; are as (2), Z 2-2² 27gu is Ck), 2 mutually independent standard Gaussian random variables.
cp(22)2
2ygk. Cx), and g. {g
Proof. For the Gaussian mixture, the log of the likelihood ratio for node a is given by 2 (X,,, le) 2 2y 2gg, where g ~N 1). Replacing every {Xi)eem) as X; EX; + ogi 1 + ogi we obtain the expression in Theorem 2.
A.4.2 Extreme Graph SNRs
Let us now turn the result, where analyze the generalization error in the where the graph SNR I' takes extreme values.
Theorem 3). Let h& be the classifier from Corollary 1.1, hū(u) sgu((X,. : pi) be the Bayes optimal classifier given only the feature information of the root node and ggen be the one-layer vanilla GCN classifier. Then we have that for any fixed E:
Theorem (Restatement
1. IfT = then E(hī) E(ht) $b-7), where to is the standard Gaussian CDF.
2. IfT then & 2 a.s. and E(h)) + Pr(g TEe), where g NO,,
3. E(hgen) Pr (g 751).
Proof. Note that when r = 0, i.e. when a = b, then = by for all & [e], hence, log(as /bb) = 0. This implies that information from the k-hop neighbours is truncated to 0 for all l E [d]. Thus, the classifier reduces to h; = hf(u, [X (Xchrem((w) = sgn (+((w))
sgn (g 7 = hō,u, (X,)). Thus, the probability that hi < 0
Pr(h.y, < 0) = Pr(yy + 0) = (--)),
where (--) the standard Gaussian CDF.
For the other case where > 1, we have two sub-cases: Either a + 0 with b + 0, or a + 0 with
b 0. In this case, Cg oc for all k, so the classifier takes the form
(H, (Xv)vem(()) sgn + Bay + Σ
Σ
(Øk.o + (-7)
kE
vE
Hence, the probability of making a mistake is
yo < <0) = Pr
Yag + Σ Σ (yugR.v + bulle) <
kE[d] vENe(u)
mm (a) (b)
1/
Pr
9 > 7
(a)
(b)
11 + 1/
17

---

where (a) .i (b) denote the total number of nodes in the Ł-neighbourhood (ee()) that are in the same class as u and different class as u, respectively. The last equation is obtained by using the fact that (g. (gk,o)) are i..d. standard Gaussians. Note that in this case since either b - 0 or 0 (but not both), we have n/t + or n/ (0) - O using (2) for any fixed Thus, Eı(a, b) > a.s. Following a similar analysis, can find that (lhgen) Pr(g > r b))
is interesting to note that we may not have & (a, b) > 1 in general, meaning that a GCN is better than methods that do not a graph only in the case where (a,
A.5 Non-asymptotic Analysis
First, consider the case where f, the total depth of the neighbourhood is constant independent of the number of nodes.
Putting m = in Lemma A.I, we see that the probability is bounded by (8L2 + +))+ (i))4+1/n = O(1/n). Hence, we conclude that in the limit n 30, there are no cycles in any constant-depth neighbourhoods in the graph. In particular, we obtain that the local weak limit (G, u) is tree.
We now turn to the case where the depth of the neighbourhood is logarithmic in n.
Proposition (Restatement of Proposition 3.1). Lei = (V, E) ~ CSBM(nn d, P, n h). Then for any = c log n such that c clog( (++ < 1/4, with probability - O(1/ log" n), the number of nodes E V whose E-neighbourhood is cycle-free is 1 ol log log*(n)) (n) )) v
Tlog 1 log n. Thus, putting = log n, we find that with probability at least 011 log" n). the number of nodes whose é-neighbourhood contains at least one cycle is bounded by O(log (glog((n) An) o(log (n))n). Hence, the fraction of nodes whose f-neighbourhood cycle-free is o( VB
Proof. In Lemma A.2, observe that since clog A 1/4, have 8 < log
For fixed node E [n]]. let us denote the number of nodes at distance & (respectively < k) from with class label yy, by U (u) (respectively, U (2)). Also let n denote the number of nodes with class label +, so that n n4 + n. Note that Uzt (u) 1, Uo (u) = O, and conditionally on the sigma-field F σ (U, (). $ k 1). we have
U+ (1) ~ Bin n - U 1 - (1 - U -1-n
(6)
Ug (u) Bin n1 - U 1- (1-a/n) U b/n)
(7)
Define Sy(w) = U (u) + U (u) be the number of nodes at distance exactly à from u, and denote a+b = 2 to be the expected degree of a node. Correspondingly. recall from (2) that we have
ag 30 0,
0 Poi [00 + b.3k-1 )), Bk Poi
[aBx-1 box- for A [Q]
(8)
Let us now state a useful bigh-probabillity bound on Su(u) Ut (u) + (u).
Lemma A.4. [Massoulié, 2014, Theorem 2.3]. For any c log n with clog A < 1/4, there exist constants C, such that with probability at least O(n "), Sa(u) < C& log (n) for all E [n] and all k E [[].
We now obtain a total variation bound between the sequences (U 1220 and {ax, Bx Bal220
Lemma A.S. Let E [n] be fixed with label the E {+1). Let = clog n with clog A < 1/4. Then the total variation distance between the collections of variables {Uz (u), UØ (u) hese and (u), 3y (u))sse keee is bounded by Ollog" 1/1)
18

---

Proof. Define the following events for C' as in Lemma A.4:
24 = (SA - CA log [.gn),1s6 lskse.
Conditionally on the sigma-fiele F (w 1) and the event 9g-11 we compute the total variation distance between the variables (UZ U (u)) and (ax(u), (x(xx))) Since u is fixed, we omit it from the notation for brevity. Define the following random variables:
W Poi
[aUR k- + +bU k-1
W Poi
a aaU
k-
+ bU
2
We now apply the Stein-Chen method to bound drv (U , W. For more details on this technique,
we refer to Stein [1972], Chen [1975]. Barbour and Chen [2005]. In particular, we use the fact that for
X1 (nn A/n). X2 ~ Poi(A) and X3 Poi(X'), dTv(X1, X2) S A/n and drv (X2, Xs) s A llK Let us focus on drv(UF, ) as the other case for (UK W is similar. Construct an intermediate random variable based on the distributions of U as in Eqs. (6) and (7),
V& ~ Poi (11+ USA- - (1
a/n)a// (1 (1-
Denote T, = 11 -) U² (1 -1)
b) UJ for brevity. Note that using triangle inequality,
aU, k
+
bU
dTv(Vk, W;) <
(n+ -
2
11)
aU k-
-b--1 T
n+ U Sk-1 2)
Tx-1 +
T
2
= n+ U U-AA-1
- Tx-1
12
+ 2
aU k- + bU k-1
Tx-1
n+
U ビK- 2 Tx-1
(aU bU b0
where in the last inequality we used Fact A.3. Then we obtain the variation distance:
drv(Ut, W S dTv Vv) + drv (Vr. Wit)
s Th- + n4+ - - - 17)
Th-1 + 4n
(aU + bb
Tk-1 (1 1+ n+ U クn
+
1
(al - + bUūT))
4n
Consider now choice of e such that clog A < 1/4. We have & = c clogn < 1 log n, implying that A < 1/4 Recalling (9) corresponding to Lemma A.4, we have that under the event Ω4-1 for k < E, the number of nodes at distance h - is
5-11 U + + < CA log CA Coologn C/4/4 4o41log n.
(10)
Observe now that from Fact A.3, T-- S aU aU,_, +bU Recalling that yu have uniform prior, by the Chernoff bound [Vershynin, 2018 Theorem 2.3.1] on n+, we have |n+ a
2 (Vnnlognn
with probability at least - (n). Thus, we obtain that under this event,
1 SUSA-ll
logn Vn
dTv(Ut, WT) 50
(aUt + bUū +
4n (aU + bUEi))
n
log n vn
max(a, b)²
loog n n2/4
S 0
max(a, 6) +
52_ -
4n
where in the last step we used the bound from (10). Now recall that the variables {U=t ak,, 3x 3x are defined as in Eqs. (6) to (8) for all & < f. For a fixed
[ro], we have the base cases Ujt ao =
19

---

and Uo- = Bo = 0. Then following an induction argument with a union bound over all & E .7. we have that the variation distance between the sequences { U% hage and {ax, Sx Jase is upper bounded by O
log V n/
We now obtain a relationship between the misclassification error on the data model with finite n, i.e. En and the error on the limit of the model with n + 0o, i.e., E.
Theorem (Restatement of Theorem 4). For any S t S clog n such that the positive constant c satisfies e log( b+ 1/4, we have that
min &, (h) E, (ni) =0 log" (log"n)
(1ogg )
1
min (1) - E(h)) =0 IECz
loog* m )
NECz
Proof. Consider a random feature-decorated graph G ~ CSBM(n, d. {P+),, a/n, b/n), where + correspond to the distributions h E Cz, the class of all é-local classifiers, define E,, (h) to be the probability of misclassification for a uniform at random node u E [n1] i..., (h) = Pr(y h(u, [Xo hreett)))) ne < 0). Since known that all classifiers in C₃ operate on и given the information in its E-neighbourhood ne(u), we will omit (u) from the notation and say h(u) instead of h(u, (X, (eneen)())), (e(u)) when it is understood. Let P be the joint measure of the variables {U= Jese from Eqs. (6) and (7), and P be the joint measure of the variables {ox, 3x. jage from Eq. (8). Then Lemma A.5 gives us that
for the node features given by (X. [m]] For classifier
drv (P, P') < 00(
Ing 12474
= (1).
Recall E())) computed in Theorem 2 for the limiting data model (G, u).
E(h)) Pr
g
+
1
O,k
(b)
>
y
27
kE[!]
i=1
Pr
9
1
2
(b)
>7
{ax, BaJase dp'.
2-
kE
Similarly, we have
U Σ
UN
E, (12) Pr
9
+
1
(a)
(8)
27
kE[A]
UE
/ Pr
9
Σ
Zz.
(b)
7
Uttee dP.
27
kE(1]
Thus, we obtain that
log"
(h7) - E(h)) S (P,(PP 0
= on (1),
(II)
1/4
Let us now focus on the case with finite n. Let A denote the event from Proposition 3.1 where the number of nodes with cycle-free é-neighbourhoods is 1 - o( ollog""). For node Gn, let E, denote the event that the subgraph induced by the E-neighbourhood of u, ne(u) is a tree. Then observe that for uniform random node Gn.
vin
min &,, (h) Pr(mu (1) <)) kEC,
Pr(E., ((..)).(yylll Pr(yuli, (w) < 0 E.) + PPEPPPEEPPPPP Pr(v.i..) <0 ES)
-(1 on (1)))) (u) < 0) + (1)
= -b,( + (1).
20

---

In the above, we used from Proposition 3.1 that Pr(Eu) Pr(E, n A) + Pr(E, n A9) 1 O log' and that e,, (h;) minnec. Pr(y.h(u) E.). This establishes the first part:
min (h) &n (bt))= = kgdz
log n
Combining the above display with (11), we obtain the second part, i.e.,
min en (h) min (h)
=
min (n) E(12)
NEC,
NEC,
kEC;
min En(h) (n())) + En(1)) - ((()))()()))))))))))))))()))) kEC;
min en (h) En() MEC;
+ (n)) - E(h2)
log" 0
0
0
log n
n1/4
log
B Additional Empirical Observations
B.1 Convergence of Parameters
We observe empirically that gradient descent (SGD and Adam implementations in the pytorch library) converges in the binary setting. In this case, the neural network learns the right parameters corresponding to the parameters of the CSBM, i.e., and Q, such that Architecture 1 realizes the optimal classifier in Corollary 1.1. In Fig. 3, the x-axis denotes the number of epochs elapsed since
3.5
01.00
0.4
3.0
3.0
0.2
100
200
300
Figure 3: Convergence of parameters of Architecture 1.
the beginning of the training process. For the first plot, the y-axis denotes the cosine similarity between the parameters 0 E Rd learned by the MLP (4) in Architecture and the ansatz that realizes the optimal classifier; while in the second plot, the y-axis denotes the absolute difference
between the clip parameter 0g IR and the ansatz value log( [+r) These experiments are performed in the same setting as Fig. 1b with fixed r = 0.2. We see that the parameters converge as the number of training iterations increases. The reported metrics are averaged over 10 trials, and the standard deviation is shown at each iteration using the translucent blue region.
21

---

B.2
Comparison with AMP-BP
We now perform a comparison of our architecture with 5 against the AMP-BP algorithm from [Deshpande et al.. 2018] in two different settings. We set n. = 1000 and work with two values of E {5, 500). The case 5 simulates the low-dimensional case where asymptotically d/n + while d = 500 represents the high-dimensional case where d/n.
for a constant For the AMP-BP algorithm, we choose two values for the number of iterations, E (5, 20).
Tables 1 and show the results for = with varying values of T E {0.3, 0.4, 0.5, 0.6}. We observe that the classifier obtained after training Architecture almost always outperforms AMP-BP for both low-dimensional and high-dimensional cases.
Table 1: Accuracy metrics for Architecture 1 and AMP-BP for y and d 5.
Graph signal
5-local Bayes Optimal
AMP, 1
AMP, / 20
0.3
0.870
0.753
0.858
0.4
0.954
0.816
0)890
0.5
0.988
0.819
0.916
0.6
0.996
0.892
0.952
Table Accuracy metrics for Architecture and AMP-BP for y = and 500.
Graph signal
5-local Bayes Optimal
AMP, |
AMP, / 20
0.3
0.916
0,554
0.848
0.4
0.995
0.558
0.877
0.5
0.998
0.626
0.920
0.6
0.998
0.657
0.940
Tables and show the results for y = 0.2, i.e., for weaker feature signal in the data. Here, we observe that although Architecture outperforms AMP-BP in the low-dimensions regime, it exhibits worse performance than AMP-BP in the sigh-dimensional regime.
Table 3:
Accuracy metrics for Architecture and AMPPBP for 7 = 0.2 and 5.
Graph signal 5-local Bayes Optimal
AMP,
AMP, t 20
0.3
0.554
0.520
0.579
0.4
0.587
0.528
0.584
0.5
0.823
0.604
0.756
0.6
0.997
0.637
0.880
Table 4: Accuracy metrics for Architecture and AMP-BP for 7 0.2 and d 500.
Graph signal
5-local Bayes Optimal
AMP, t
AMP, t 20
0.3
0.584
0.502
0.543
0.4
0.706
0.525
0.694
0.5
0.762
0.568
0.804
0.6
0.788
0.604
0.878
is important note, however, that this is an aoples-to--oangess comparison because AMP-BP is not a local algorithm, i.e., the whole graph is visible to the algorithm and all nodes contribute to the classification of every other node. This is not true for Architecture 1, where only the nodes in the ê-hop neighbourhood contribute to this decision. Our notion of optimality is among the class of local algorithms. Furthermore, we observe that AMP-BP with 5 iterations does not converge and obtains much lower accuracy compared to 20 iterations.
22


Reviews:
[{"review_id": "OwqZgr209f", "reviewer": "Reviewer_LT99", "summary": "The focus of this research paper was the investigation of node classification problem on sparsely populated graphs that exhibit local tree-like structures. Thy introduced asymptotic local Bayes optimality to define the ideal performance standard for node classification tasks. By utilizing this criterion, the paper derived the optimal classifier for a wide range of statistical data models with diverse distributions of node features and edge connectivity. The research paper further assessed the generalization error of this classifier and conducted a theoretical comparison of its performance with existing learning methods. This evaluation was carried out on a model that inherently possesses identifiable signal-to-noise ratios (SNRs) in the data.\n\n", "questions": "* Analysis of the cost associated with the preprocessing step and discussion on scalability of the proposed approach\n\n* What is impact of log(Q^k) vs Q^k on the performance?\n\nPlease look at the weakness for more detailed question.", "limitations": "The paper discussed the limitation of the proposed approach.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Existing works explored conventional message-passing graph neural network architectures. However, their analyses heavily depend on two key assumptions: firstly, the graph is not excessively sparse, and secondly, the node features are represented as a Gaussian mixture. In contrast, this study investigates the realm of highly sparse graphs, where the expected degree of a node is on the order of O(1). Moreover, it considers nodes that extend beyond the immediate neighbors, encompassing nodes at fixed distances.\n\n* Their result holds for a general multi-class statistical model with arbitrary continuous or discrete feature distributions and arbitrary edge-connectivity probabilities between all pairs of classes.\n\n* They showed that in scenarios where the graph signal-to-noise ratio (SNR) is extremely low, the architecture simplifies to a basic MLP that disregards the underlying graph structure. Conversely, when the SNR is significantly high, their architecture transforms into a standard convolutional network that aggregates information from all nodes within the local neighborhood. However, in the intermediate SNR regime, it exhibits interpolation behavior and outperforms both the simple MLP and the typical graph convolutional network (GCN).\n\n\n", "weaknesses": "* The analysis in the paper seems interesting but more experimental results are required to support the claims. For example, comaprison with the baselines on existing benchmarks in GCN literature as well as more synthetic types of graphs (e.g scale-free, random etc) with controllable degree distribution to enforce different level of sparsity.\n\n\n* The proposed method relies on the pre-processing step to calculator A^\\~(k) that models a non-backtracking walk of length k that considers new nodes in the distance-k neighborhood that were not discovered. Specifically A\\~(k)uv=1 If and only if v is present in the distance k neighborhood of u but not within the distance (k-1) neighborhood. Such a calculation seems to be expensive and might not be scalable. Would you please elaborate on that? \n\n\n* Q^k models the probability of observing a distance k path between a pair of nodes in two classes. I am wondering why the log (Q^k) is considered in calculation of M. What is the intuition? What would happen if the Q^k has been used? Having abolition study would help in understanding.\n\n* How is the performance of proposed approach in compare to the traditional GCN baselines in real datasets? The papers just considered synthetic graphs with controllable degree but more experimental results are needed on exiting benchmarks. Also for the synthetic graph what type of graph is it and what is the underlying distribution?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments and questions. We address the comments below.\n\n> The analysis in the paper seems interesting but more experimental results are required to support the claims. For example, comaprison with the baselines on existing benchmarks in GCN literature as well as more synthetic types of graphs (e.g scale-free, random etc) with controllable degree distribution to enforce different level of sparsity.\n\nWe sincerely request the reviewer to consider that our claims are stated as theorems and are rigorously proved in the paper. We agree that more experimental results will help demonstrate our results more, but in our opinion, they do not provide more insight unless we change the setting of the experiments substantially (one example would be what the reviewer suggested: scale-free or power-law degree-distributed graphs). We note that the primary focus of our work is to show that the optimal GNN architecture for the CSBM with arbitrary feature distributions is a message-passing architecture. We believe that this is a very important result in itself, and decided to leave similar results on many other random graph models (other than the stochastic block model) as future work. Since our theorems specifically rely on the graphs being sparse enough so that $\\ell=c\\log n$ depth neighbourhoods for a substantially large number of nodes are tree-like, we do not consider dense graphs for experiments. \n\n> The proposed method relies on the pre-processing step to calculator A^(k) that models a non-backtracking walk of length k that considers new nodes in the distance-k neighborhood that were not discovered. Specifically A^(k)_{uv}=1 If and only if v is present in the distance k neighborhood of u but not within the distance (k-1) neighborhood. Such a calculation seems to be expensive and might not be scalable. Would you please elaborate on that?\n\nWe completely agree with the reviewer that the pre-processing step is expensive and may not be scalable for extremely large graphs with more than tens of millions of nodes. However, there exist neighbour-sampling techniques that can be explored as a potential future direction of work to make the architecture practically more useful. The primary scope of our paper is to introduce a message-passing architecture that is provably optimal for a very general statistical data model, and thus, we decided to leave the study of computational pre-processing costs as potential future work. We sincerely believe that further research will be able to construct more efficient pre-processing techniques for implementing this architecture for large-scale graphs.\n\n> Q^k models the probability of observing a distance k path between a pair of nodes in two classes. I am wondering why the log (Q^k) is considered in calculation of M. What is the intuition? What would happen if the Q^k has been used? Having abolition study would help in understanding.\n\nThe $\\log Q^k$ shows up in the architecture because of the maximization of log-likelihood. Our goal was to show that the optimal architecture in the regime we study is a message-passing architecture. Message-passing architectures aggregate messages from all the nodes in the neighbourhood to classify a node of interest. The distribution of the neighbourhood can be expressed as a product of probabilities, and taking a $\\log$ helps consider the distribution in terms of a sum of log probabilities. We could have used $Q^k$ instead of $\\log Q^k$ in the architecture, but then the message-passing mechanism will need to consider products instead of sums of messages from the nodes.\n\n> How is the performance of proposed approach in compare to the traditional GCN baselines in real datasets? The papers just considered synthetic graphs with controllable degree but more experimental results are needed on exiting benchmarks. Also for the synthetic graph what type of graph is it and what is the underlying distribution?\n\nThank you for this important question! The main objective of our paper is to establish the theoretical foundation and principles behind the optimal message-passing architecture. We humbly emphasize that our goal is to provide insights about message-passing that could be applied across various domains, and conducting experiments on real datasets is an interesting future endeavour that could follow our theoretical work. We define the synthetic data model that we experiment with, in detail in Sections 3.2 (general case) and 3.4 (binary case and Gaussian case), where we describe the underlying distributions of both the graph and the node features."}, {"review_id": "aUY2BnY2Zu", "reviewer": "Reviewer_mQCx", "summary": "The authors propose a local analysis of the CSBM. They define and derive a local Bayes-optimal classifier and show it can be achieved by a message-passing architecture. They give an interpretation of it in the limiting cases when the graph caries no or all information and support it with numerical experiments.\n", "questions": "Some more general questions:\n\n1 As to the training: can the performances of the trained model be compared to theorem 2? do the learned Q and rho match the ones of the binary CSBM?\n\n2 Does this neural network generalize well to other datasets?\n\n3 Would the authors have an idea how to generalize their results to non-local large l estimators?\n\nTypos :\n\nl. 150 \"for a class of estimators this general,\" ?\n\nref. l. 409 Andrea Montanari is missing.", "limitations": "See above.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The topic of this article is of great interest. CSBM has been widely used as an artificial dataset and deriving an optimal GNN for it would be good. For this reason I think this article should be published.", "weaknesses": "1 In the CSBM usually one considers the high-dimensional limit where the dimension d of the features proportional to n, to model what happens in ML. Here the authors consider d=O(1), which seems limited. I do not see if this is just for convenience or if it is a stronger limitation to this work. For the high-dimensional Gaussian mixture Bayes-optimal classifiers are known and the MLP the authors use works. Could the authors better explain this point?\n\n2 A weakness of this article is a lack of clarity:\n\n– the analysis the authors give is local, the graph is tree-like. For l ~ O(log n) it will not hold. I was a bit confused; maybe the authors should emphasize that l is fixed compared to n, that there are no loops and many things are independent;\n\n– in the definition of architecture 1, the authors should precise that the l and L of the first line (for H^(l)) have nothing to do with the calligraphic l of the second line (the size of the neighborhood). L. 121 \"as a simple MLP\" –> \"as the output of a simple L-layer MLP\";\n\n– maybe introducing the model before theorem 1 is counter-intuitive. The authors could explain that the model is a way to realize theorem 1, that the NN just learns rho and Q. This would ease the introduction of tilde A;\n\n– the experiments of fig. 1 and 2 are not clear. What are the training procedure, l, L, training nodes, number of runs, ...\n\n3 It is a pity that the numerical experiments deal with the interpolation and not the major point of the article: the optimality. The authors could compare against other GNNs. Also one has access to the conjecturally-optimal performances on CSBM (in Deshpande '18 for instance); how far is this l-neighborhood model? does the limit large l converge to these or is there a gap (due to the cycles)?\n\n4 How does this model deal with train labels? In architecture 1 the authors assume there is no train node in the l-neighborhood of u, no? otherwise the Bayes-optimal classification would take the labels in account, M_{u,i} = (H_{u,j=label of u} + log Q_{i,j=label of u}). The prior distribution of node labels is not iid uniform in the semi-supervised setting.\n\nI would be pleased to give a higher rating to this article if the authors improve or comment on these points. If the authors develop them in their revised manuscript maybe they could summarize part 3.5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging review and insightful comments that helped us improve the clarity and credibility of our work. We address these below.\n\n> In the CSBM usually one considers the high-dimensional limit. the authors consider d=O(1) which seems limited.\n\nWe agree that the high-dimensional limit is usually considered where $d$ is proportional to $n$ in the CSBM literature. However, in popular benchmark datasets for node classification, the number of features ($d$) is relatively very small compared to $n$; see for example, OGB datasets: products (n=2.4m, d=100), proteins (n=130k, d=8), papers100m (n=100m, d=128). Therefore, it is not very clear that the high-dimensional scaling is the relevant one. The existing literature on CSBM is focused on $d$ being proportional to $n$, while we consider the setting with fixed $d$. We added a discussion about this in the revision.\n\n> the analysis is for locally tree-like graphs. For $\\ell = O(\\log n)$ it will not hold...\n\nAlthough the locally tree-like property will not hold for $\\ell= O(\\log n)$ in general, in Proposition 3.1 we show that if $\\ell<c\\log n$ for a bounded $c$, then with high probability the graph is still locally tree-like. We also show in Theorem 4 that for this setting of $\\ell$, even in the non-asymptotic case the performance of the classifier $h^{*}$ is close to that of the optimal classifier ${\\rm argmin}\\_{h\\in\\mathcal{C_\\ell}}\\\\,\\mathcal{E}_n(h)$. Thus, although we do not consider the entire regime where $\\ell= O(\\log n)$, we do consider the case beyond fixed $\\ell$.\n\n> Definition of arch 1: l and L of the first line have nothing to do with the calligraphic l.\n\nThank you! We incorporated this in the revision.\n\n> The authors could explain that the model is a way to realize theorem 1...\n\nWe understand that it may seem reasonable to introduce the model after Theorem 1 from a theoretical perspective, but we also wanted to show the message-passing architecture before a theoretical analysis, and then motivate the architecture using Theorem 1. We discuss right after Theorem 1 about Architecture 1 being a way to realize the classifier in Theorem 1. \n\n> What are the training procedure, l, L, training nodes, number of runs...\n\nThe plots are for $\\ell=2$ (two-hop neighbourhoods) and $L=1$ (single-layer MLP). Our experiments with $\\ell,L\\in\\{1,2,3\\}$ yield the same result in terms of the plots. The networks are trained on a dataset with 10k nodes, and tested on another dataset with 10k nodes, plotting the average test accuracy across 50 trials. We added this in the revision.\n\n> the numerical experiments deal with interpolation and not optimality. The authors could compare against other GNNs and the conjecturally-optimal performances on CSBM\n\nWe aimed to show optimality to some extent through the interpolation. We find that with strong graph signal, the optimal classifier mimics a GCN, while with weak graph signal, it mimics an MLP disregarding the noisy graph. This interpolation showcases model optimality across signal strengths, ranging from MLP to GCN extremes and surpassing both throughout. The conjecturally optimal performance on CSBM is for the case where $d$ is proportional to $n$, and our regime of study does not consider this setting. As suggested by the reviewer in an earlier comment, we have added a discussion about this in the revision.\n\n>  how far is the l-neighborhood?...\n\nWe take $\\ell$ to be as far as $c\\log n$ for a suitably bounded constant $c$, as mentioned in Proposition 3.1 and Theorem 4. Beyond this limit, we are not able to guarantee that the $\\ell$-neighbourhoods of a substantial fraction of nodes in the graph are cycle-free with high probability, hence we do not consider larger values of $\\ell$.\n\n> In architecture 1 the authors assume there is no train node in the l-neighborhood of u, no? otherwise the Bayes-optimal classification would take the labels in account. The prior distribution of node labels is not iid uniform in the semi-supervised setting.\n\nWe agree that the architecture doesn't assume labels for the $\\ell$-neighbourhood of $u$. The problem's objective is: Given a node's features and its $\\ell$-neighbourhood, predict its label. The learning process computes gradients using only node $u$'s training label, despite the output considering features of all $\\ell$-neighbourhood nodes. Although the prior label distribution might not be iid uniform in the semi-supervised setup, introducing this complexity alters the Bayes classifier, complicating analysis. Nonetheless, generalizing to this scenario isn't challenging, and the model would adapt to learn the appropriate node label distribution in that case.\n\n\n> Can the performances of the trained model be compared to theorem 2? do the learned Q and rho match the ones of the binary CSBM?\n\nYes! Our plots in fig 1,2 are where randomly initialized models were trained. The learned $Q$ and $\\rho$ match the optimal value for the binary CSBM. We have added this information in the supplementary document now with plots showing convergence of model parameters to the right $Q$ and $\\rho$ against the training iterations. **These plots can be found in our rebuttal one-page pdf response**.\n\n> Does it generalize to other datasets?\n\nWe evaluate the model on a completely different dataset (but with the same distribution) than the one it is trained on. Figures 1 and 2 are plots of the performance on these unseen datasets.\n\n> Can results generalize to non-local large l estimators?\n\nThanks for this important question! We are currently limited in this regard because to increase $\\ell$ beyond $c\\log n$, we need mathematical tools that can deal with the large amount of correlations in the data due to the presence of a large number of cycles in the neighbourhoods of a non-diminishing fraction of nodes. We leave this as a very interesting direction for future work.\n\nThank you for pointing out the typos. We have fixed them in the revision.\n"}, {"review_id": "2Rt0oYt73S", "reviewer": "Reviewer_K3Xe", "summary": "The paper considers the inference problem of node classification in feature-decorated locally tree-like sparse graphs. The authors introduce and motivate a notion of asymptotic local Bayes optimality for local estimators. The first main result, Theorem 1, concerns the characterisation of the Bayes optimal (in the former sense) classifier in the setting considered. This theorem implies that this estimator is implementable in a message passing graph neural network architecture. The authors then consider the case in which the features are Gaussian. In this context, Theorem 2 establishes the asymptotic local Bayes optimal error while Theorem 3 compares this optimal classifier with other standard classifiers in some extreme signal-to-noise settings. These results are contrasted with numerical experiments. Finally, Theorem 4 gives a finite size bound for the difference between the misclassification error of the estimator proposed and the minimum misclassification error of local classifiers.\n", "questions": "General comments:\n- The analytical tools used require the graphs to be locally tree-like and extending the analysis to non locally tree-like graphs is clearly beyond the scope of the work. But it is my opinion that it would make the case for the paper much stronger if the authors could add some numerical simulations comparing the classifier proposed and other estimators in some non locally tree-like settings. This would address to some extent the comment on the Weaknesses' section above.\n- The analysis presented focuses mainly in the case of two classes. This is understandable as it renders the presentation more clear. However, it would be good if the authors could add a brief discussion on how the complexity of the estimator depends with respect to c. Is it feasible to compute it for reasonable graph sizes and a moderately large number of classes?\n\nSome particular comments:\n- In line 270 after the dot the next word should be capitalised.\n- In Figure 1(a), is the value of $\\Gamma$ used above the transition? I guess it is but it would be good if this is explicitly stated.\n- The convergence rate of Theorem 4 is rather slow. It would thus be specially interesting to have some estimation of the constant for this bound. Do the authors think that this would be possible by some adaptations of the proof?", "limitations": "Although the limitations of the work are not explicitly stated, the context and reach of the results are clear in the presentation.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The questions addressed in the paper are relevant, interesting, and are part of an active research field.\n- The results are interesting, rigorous, and thorough and the proofs are clear.\n- The inclusion of finite size bounds for the difference between the performance of the classifier proposed and the optimal performance is of particular interest and renders the analysis presented very complete.", "weaknesses": "- Maybe the most relevant weakness of the work is, in my opinion, that it solely focuses in locally tree-like graphs. Although this kind of models are very extended in the literature, the topologies present in many of the applications mentioned are not expected to be of this kind. Indeed, in many social settings, for example, the kind of networks that are observed have diverse clustering coefficient values. Though the paper undoubtedly has theoretical value, this will probably limit the impact it could have in more applied research communities. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and encouraging comments about our work! We address the questions below.\n\n> Maybe the most relevant weakness of the work is, in my opinion, that it solely focuses in locally tree-like graphs. Although this kind of models are very extended in the literature, the topologies present in many of the applications mentioned are not expected to be of this kind. Indeed, in many social settings, for example, the kind of networks that are observed have diverse clustering coefficient values. Though the paper undoubtedly has theoretical value, this will probably limit the impact it could have in more applied research communities.\n\nThank you for raising this important concern. We agree that the analysis in our paper is limited to locally tree-like graphs, since we look at the regime of constant degree. Although the architecture we obtained can be evaluated on denser graphs as well, it may not necessarily be optimal in that regime. We believe that our work will inspire further research in this direction, where the quest for optimal architectures is pursued for other topologies suited to many other applications. We will add a discussion about this in the conclusion section of the paper.\n\n> The analytical tools used require the graphs to be locally tree-like and extending the analysis to non locally tree-like graphs is clearly beyond the scope of the work. But it is my opinion that it would make the case for the paper much stronger if the authors could add some numerical simulations comparing the classifier proposed and other estimators in some non locally tree-like settings. This would address to some extent the comment on the Weaknesses' section above.\n\nWe agree with the reviewer that extending the analysis to locally tree-like graphs is beyond the scope of the current work, and is a very interesting potential future direction of research. We believe that a comparative study of this architecture against other baselines on graphs that are not locally tree-like would be very interesting and would make the architecture more appealing, and we thank the reviewer for this suggestion. We omitted this in the current work as our primary focus (and the main result, Theorem 1) is for the regime where the average degree is constant and $\\ell<c\\log n$ for a suitably bounded constant $c$.\n\n> The analysis presented focuses mainly in the case of two classes. This is understandable as it renders the presentation more clear. However, it would be good if the authors could add a brief discussion on how the complexity of the estimator depends with respect to c. Is it feasible to compute it for reasonable graph sizes and a moderately large number of classes?\n\nOur implementation and comparison with MLP and GCN is done for the binary case, however, our main result (Theorem 1) and the architecture we describe (Architecture 1) are for the general case of multiple classes. The estimator has a nice closed form and the architecture makes the estimator realizable. The preprocessing step is a bit computationally expensive for very large graphs for the case of multiple classes due to the calculation of non-backtracking walk matrices. However, we believe that further research in this direction will improve on our preprocessing and help us realize this estimator more efficiently for large graphs.\n\n> In Figure 1(a), is the value of $\\Gamma$ used above the transition? I guess it is but it would be good if this is explicitly stated.\n\nThe plots in Figure 1 show the accuracy of three different neural networks (MLP, GCN, and Architecture 1) trained on the CSBM. The value of $\\Gamma$ is fixed for fig 1 (a), and we plot the accuracy is plotted for a test set on the same distribution but previously unseen features and graph.\n\n> The convergence rate of Theorem 4 is rather slow. It would thus be specially interesting to have some estimation of the constant for this bound. Do the authors think that this would be possible by some adaptations of the proof?\n\nWe agree that the convergence rate $O(1/\\log^2 n)$ is very slow. For an estimation of the constant, we refer to L. Massoulié. Community Detection Thresholds and the Weak Ramanujan Property. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, page 694–703, 2014. Unpacking Lemma 4.2 in the reference, we see that the constant depends on many other constants that are used throughout its proof, and one can choose suitable values for these constants to arrive at a constant $<2$. \n"}, {"review_id": "LncQuP8ou2", "reviewer": "Reviewer_S322", "summary": "This paper studies a specific graph convolutional architecture (and the resultant estimators from an architecture with appropriate learned values) \nbased in the setting of a contextual stochastic block model: one where a graph with latent clustering also has node features available that \nare informative for discovering the clustering. The paper studies this in the \"constant average degree and constant feature dimension\" regime\nand makes the following contributions:\n\n1. Identifies the Bayes-optimal classifier for node clustering restricted to a constant size neighborhood in the graph (using local\nweak convergence theory) and shows this matches the GCN architecture proposed.\n2. Specializes the classifier to Gaussian features and 2 latent clusters, proving a formula for the bayes optimal classifier\n3. Shows that the local classifier is nearly optimal even for GCN architectures of $c \\log n$ (for a small enough constant c)\nusing the locally-tree-like nature of the graph.", "questions": "Some questions, roughly in order of the paper reading:\n1. Why is the notion of SNR $\\frac{(a-b)}{a+b}$ when in prior notions of SBM in the constant degree regime it is usually $\\frac{(a-b)^2}{2(a+b)}$ which makes sense in terms of the difference of mean / sd of poisson degrees (which is correct in the limit)? If not, how does this reconcile with prior work when features are not meaningful?\n2. What happens to Corollary 1.1. when $\\Gamma > 1$ (particularly the formula for c_k should be modified somewhat). Naively (using the same formula but with $\\Gamma^k -1$), this means that c_k converges to a constant as $k$ diverges. Intuitively, it should be the case that the features should matter less and less as the neighborhood diverges in this regime, irrespective of the snr, which is the behavior for $\\Gamma <1$. This suggests that the formula needs more than a naive change for $\\Gamma >1$.\n3. Same question as 1 on formula (3) and Theorem 3 (the specialization to the Gaussian case)\n4. Theorem 3: the statement $\\xi_\\ell \\ge 1$ looks like it needs to be probabilistic statement (almost surely?, with high probability?) or perhaps needs vanishing slack? E.g. take $a$ large, $\\ell = 1$ and $b=1$, then there's a constant (but small as a diverges) probability that $\\alpha_1$ is 0 and $\\beta_1 \\leq 2$ is not large so that $\\xi_1 <1$. \n5. Does the Bayes optimal classifier know the probabilities $Q$ and the densiites? Presumably this is necessary. \n6. What about the GCN in Fig 1? Does it learn it from scratch, or initialized at true values, etc?\n7. In figure 1, presumably the (roughly) 0.75 accuracy is basically $\\Phi(-1)$ at $\\Gamma = 0$?", "limitations": "The most important weakness is highlighted in the weaknesses.\n\nSecond, it is also not obvious how one would change this for dense graphs. Analogous results (though with *very* different proof techniques) might be expected\nto hold when graphs have degrees of order $n$ but with within/out cluster probabilities differing by order $1/\\sqrt{n}$. How would one identify GCN architectures that might work there?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strengths are:\n\n1. Identifies a setting in which specific GCN architectures are provably optimal\n2. Uses local weak convergence theory to show some simple but illustrative examples of how (local) Bayes-optimal classifiers\naggregate information across features/graph structure.", "weaknesses": "It is hard to get excited about this paper. The main weakness to me is that the Bayes optimal classifier for the tree model is essentially obvious, given Bayes rule. It is far from clear that GCN architectures uninformatively initialized would converge to this, and the paper's experiments do not show this (or in fact consider it from what I could tell). They instead rely on the fact that the architecture they propose can approximate (with some setting of weights) the Bayes optimal classifier. At this point, it is well-known that the success of NN architectures cannot be explained by such existence/approximation theorems.\n\nIf the experiments carried out show that naive initializations of the architectures converge to the optimal ones, then that is a priori surprising, and should be discussed more. I might even pivot the paper to start with that as an experimental finding, since the theoretical results are relatively unsurprising.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their concise and thought-provoking questions! They really help us develop a better perspective of our contributions and improve our presentation. We address the comments below.\n\n> It is far from clear that GCN architectures uninformatively initialized would converge to this, and the paper's experiments do not show this. They instead rely on the fact that the architecture they propose can approximate (with some setting of weights) the Bayes optimal classifier.\n\nWe would like to clarify that our experiments indeed show that in the binary case, Architecture 1 uninformatively initialized converges to the ansatz, i.e., it is able to learn the right values of $Q$ and $\\rho$. Both Figures 1 and 2 depict the test accuracy of trained models that were initialized uninformatively (uniformly at random). We have added this information in the supplementary material, and also **attached a pdf of the plots showing the convergence in the general rebuttal response** above.\n\n> If the experiments carried out show that naive initializations of the architectures converge to the optimal ones, then that is a priori surprising. I might even pivot the paper to start with that as an experimental finding, since the theoretical results are relatively unsurprising.\n\nWe do indeed observe that naive initializations of the architecture converge to the optimal one in the binary Gaussian case (see the attached figures). We agree that this is a priori surprising, and we will add a discussion about this in the revision. However, we humbly request the reviewer to consider that pivoting the paper to start with this experimental finding will change the primary focus of our work, which is to show that the optimal estimator in the regime we study is realizable by a message-passing GNN architecture.\n\n> Why is the notion of SNR $\\frac{|a-b|}{a+b}$ when in prior notions of SBM in the constant degree regime it is usually $\\frac{(a-b)^2}{2(a+b)}$ which makes sense in terms of the difference of mean / sd of poisson degrees? How does this reconcile with prior work when features are not meaningful?\n\nWhen computing the optimal classifier, $\\Gamma=\\frac{|a-b|}{a+b}$ is what naturally shows up in the estimator's expression. We agree that in previous works where features are not present, the SNR is defined as $\\frac{(a-b)^2}{2(a+b)}$. We believe that this is because of the nature of the previous work on detectability thresholds for SBMs. It is known (Mossel et al, Massoulie et al) that weak recovery is possible if and only if this SNR > 1, however, we do not study detectability thresholds. Instead, we compute the optimal architecture in terms of the parameters of the data model, and the quantities that naturally pop up in the expression of the estimator are what we interpret as signals in the data.\n\n> What happens to Corollary 1.1 when $\\Gamma>1$. Naively (using the same formula but with $\\Gamma^k - 1$), this means that c_k converges to a constant as $k$ diverges. Intuitively, it should be the case that the features should matter less and less as the neighborhood diverges in this regime, irrespective of the snr, which is the behavior for \n$\\Gamma < 1$. This suggests that the formula needs more than a naive change for $\\Gamma>1$.\n\nWe would like to note that $\\Gamma=\\frac{|a-b|}{a+b}$ is always $\\le1$ for $a,b\\ge 0$. Hence, we are not concerned with the case $\\Gamma>1$. However, the reviewer's intuition overall is exactly what we intended to communicate.\n\n> Theorem 3: the statement $\\xi_\\ell\\ge 1$ looks like it needs to be probabilistic statement (almost surely?, with high probability?) or perhaps needs vanishing slack?\n\nThank your for pointing this out. The statement should say $\\xi_\\ell>1$ a.s. We will fix this in the revision.\n\n> Does the Bayes optimal classifier know the probabilities $Q$ and the densiites? Presumably this is necessary.\n\nWe believe that this relates to the first comment about the architecture's parameters converging to the optimal parameters with gradient descent. As we mentioned above, the architecture when trained on CSBM data indeed learns the right values of $Q$ and $\\rho$. It does not know the right values in advance for the experiments we show in the paper.\n\n> What about the GCN in Fig 1? Does it learn it from scratch, or initialized at true values, etc?\n\nAll the architectures in fig 1 (MLP, GCN, Architecture 1) are trained from scratch with uniform random initializations. We have added this information in the revision. Thank you for pointing this out, it helps us clarify that our results are indeed as strong as one would ideally expect.\n\n> In figure 1, presumably the (roughly) 0.75 accuracy is basically $\\Phi(-1)$ at $\\Gamma=0$?\n\nWe believe the reviewer wanted to say that the accuracy is roughly $0.85$, which is basically $\\1 - \\Phi(-1) = \\Phi(1)$ at $\\Gamma=0$. Yes, this is the correct interpretation.\n\n> it is also not obvious how one would change this for dense graphs. Analogous results (though with very different proof techniques) might be expected to hold when graphs have degrees of order $n$, but with within/out cluster probabilities differing by order $1/\\sqrt{n}$. How would one identify GCN architectures that might work there?\n\nThis is a very interesting question, and it is true that our current technique is limited to sparse graphs. We rely on the fact that for the sparse regime that we study, a substantial fraction of nodes in the graph have locally tree-like neighbourhoods up to depth $c\\log n$ for a suitably bounded $c$. This fails for dense graphs and make it difficult to compute an informative expression for the optimal architecture. By 'informative', we mean an expression that is well-defined in terms of recognizable signals in the data. We leave the question of extending our results to dense graphs as an interesting open problem and a challenging direction for future work."}]

Author rebuttal:
In this comment, we respond to the general comments and questions of the reviewers about the convergence of the architecture's parameters, referred to as $(\theta_1, \theta_2)$ in the attached pdf, to the optimal values associated with $\rho$ and $Q$. We emphasize that figures 1 and 2 in the paper are indeed for a network that is initialized uniformly at random, and then trained using a CSBM dataset. In the attached pdf of this rebuttal, we show two plots showing the convergence of the parameters of the architecture to the optimal values associated with $\rho$ and $Q$, i.e., $\mu$ and $\log(\frac{1+\Gamma}{1-\Gamma})$. In the first plot, we show that the normalized inner product between $\theta_1$ and $\mu$ converges to $1$ as the number of iterations increase. Similarly in the second plot we show that $\theta_2$ converges to $\log(\frac{1+\Gamma}{1-\Gamma})$ as the number of iterations increase (here we show that the absolute difference between the values goes to 0). The settings of these plots are the same as that in Fig 1b with $\Gamma=0.2$.

We address all other comments and questions individually for each reviewer.

Meta-review: This paper was considered to bring an interesting technical contribution. The discussion clarified many of the referees' questions, and the authors should carry those answers into the manuscript. In particular, it should be made very clear under what conditions the claims of optimality hold and present explicit examples of cases (via numerical experiments) where the proposed architecture is not optimal (e.g. high-dimensional features). Without this, the paper may mislead the reader that the results are stronger than what they are. The results are considered interesting, and the limitations should be put forward already in the introduction rather than being hidden in mathematical formulations of the limiting assumptions in the later technical pages.
Decision: Accept (poster)