Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective
Authors: Rongzhe Wei
Haoteng Yin
Junteng Jia
Austin R. Benson
Pan Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Network
Bayesian Method
Theory

Abstract: Graph neural networks (GNNs) have shown superiority in many prediction tasks over graphs due to their impressive capability of capturing nonlinear relations in graph-structured data. However, for node classification tasks, often, only marginal improvement of GNNs has been observed in practice over their linear counterparts. Previous works provide very few understandings of this phenomenon. In this work, we resort to Bayesian learning to give an in-depth investigation of the functions of non-linearity in GNNs for node classification tasks. Given a graph generated from the statistical model CSBM, we observe that the max-a-posterior estimation of a node label given its own and neighbors' attributes consists of two types of non-linearity, the transformation of node attributes and a ReLU-activated feature aggregation from neighbors. The latter surprisingly matches the type of non-linearity used in many GNN models. By further imposing Gaussian assumption on node attributes, we prove that the superiority of those ReLU activations is only significant when the node attributes are far more informative than the graph structure, which nicely explains previous empirical observations. A similar argument is derived when there is a distribution shift of node attributes between the training and testing datasets. Finally, we verify our theory on both synthetic and real-world networks. Our code is available at <https://github.com/Graph-COM/Bayesian_inference_based_GNN.git>.

Understanding Non-linearity in Graph Neural Networks from the Perspective of Bayesian Inference
Rongzhe Wei', Haoteng Yin Junteng Jia², Austin R. Benson', Pan Li'
Department of Computer Science, Purdue University
Department of Computer Science, Cornell University
{wei397, yinht, panli edu, jj885@coreel edu, arbenson@gmail com
Abstract
Graph neural networks (GNNs) have shown superiority in many prediction tasks over graphs due to their impressive capability of capturing nonlinear relations graph-structure data. However, for node classification tasks, often, only marginal improvement of GNNs over their linear counterparts has been observed. Previous works provide very few understandings of this phenomenon. In this work, we resort Bayesian learning to deeply investigate the functions non-linearity GNNs for node classification tasks. Given a graph generated from the statistical model CSBM, we observe that the max-a-posterior estimation of a node label given its own and neighbors' attributes consists of two types of non-linearity, a possibly non-linear transformation of node attributes and a ReLU-activated feature aggregation from neighbors. The latter surprisingly matches the type of non- lincarity used many GNN models. By further imposing a Gaussian assumption node attributes, only significant when the node attributes are far more informative than the graph structure, which nicely matches many previous empirical observations. A similar argument can be achieved when there is a distribution shift of node attributes between the training and testing datasets. Finally, verify our theory both synthetic and real-world networks. Our code is available at https:/ battps://gttht com/ Htmm/GrrapaCOM/BBeessii http:/Byyysiaanniffeeeeeeeee based_ GNN.tttN..
prove that the superiority of those ReLU activations is
Introduction
Learning on graphs (LoG) has been widely used in the applications with graph-structured data Node classification, a graph, which has been used in many applications such as community detection (3-6 anomaly biological pathway analysis 9 10 and on.
of the most crucial tasks in LoG, asks to predict the labels of nodes in
detection
Recently, graph neural networks (GNNs) have become the de-facto standard used many LoG tasks due to their super empirical performance [1] Researchers often attribute such success to linearity in GNNs which associates them with great expressive power [3] 14). GNNs can approximate wide range of functions defined over graphs [15 and thus excel predicting, e.g., the free energies molecules [88.. which are by nature non-linear solutions of some quantum-mechanical equations. However, for node classification tasks, many studies have shown that non-linearity to control the exchange of features among neighbors seems not that crucial. For example, many works linear propagation of node attributes over graphs [1920), and others recommend adding non- linearity while only to the transformation of initial node attributes [21H23). Both cases achieve comparable even better performance than other models with complex nonlinear propagation, such as using neighbor-attention mechanism [24). Recently, even in the complicated heterophilic setting where nodes with same labels are not directly connected, linear propagation still achieves competitive
performance 25 26 compared with the models with nonlinear and deep architectures [27 28
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Mud
CiteSour
Nunitzear Model
Netihaar Modal Liner Mtsdel No Proparat
Netiibarr Nedal UJeasr Stdds No propopatios
Liwar Medel
69
Propagatio
Appuracy
Accuracy
505 035 2.20 0.30
030 0:37
0. 3300 015 0:35 Attributed Information U -M1a?
Attriouted Information (lpp [1pp-Mj 21
Attributed Information (ij (10--Mij.) Mila)
Figure I: Averaged one-vs-all Classification Accuracy on Citation Networks of Nonlinear Models v.s. Linear Models. Node attributes in or out of the one class are generated from Gaussian distributions Ni,, (nd and NV,, ) U. E R respectively. The detailed settings are introduced in Sec. 5.3
Although empirical studies GNNs extensive till and many practical observations as above have been made, there have been very few works attempting to characterize GNNs in theory, especially to understand the effect of non-linearity by comparing with the linear counterparts for node classification tasks. The only work on this topic to the best of our knowledge still focuses on comparing the expressive power of the two methods distinguish nodes with different local structures 229.. However, the achieved statement that non-linear propagation improves expressiveness may not necessarily reveal the above phenomenon that non-linear and linear methods have close empirical performance while with subtle difference. Moreover, more expressiveness is often at the cost of model generalization and thus may not necessarily yield more accurate prediction 30.31 31
In this work, we expect to give a more precise characterization of the values non-linearity in GNNs from a statistical perspective, based on Bayesian inference specifically. We resort contextual We make a significant observation that given a graph
stochastic block models (CSBM) 32 33 generated by CSBM, the maax-a-postrne (MAP) estimation of node label given its own and neighbors' features surprisingly corresponds to graph convolution layer with ReLU as the activation combined with an initial node-attribute transformation. Such a transformation of node attributes is generally nonlinear unless they are generated from the natural exponential family (34). Since the MAP estimator known to be Bayesian optimal (35]. the above observation means that ReLU-based propagation has the potential to outperform linear propagation. To precisely characterize such benefit, we further assume that the node attributes are generated from a label-conditioned Gaussian model, and analyze and compare the node mis-classificatin errors of linear and nonlinear models. We have achieved the following conclusions (note that we only provide informal statements here and the formal statements are left in the theorems).
When the node attributes are less informative compared to the structural information, non-linear propagation and linear propagation have almost the same mis-classffication error (case in Thm. 2
When the node attributes are more informative, non-linear propagation shows advantages. The mis-classification егror of non-linear propagation can be significantly smaller than that of linear propagation with sufficiently informative node attributes (case II in Thm. 2
When there is distribution shift of the node attributes between the training and testing datasets, non-linearity provides better transferability in the regime of informative node attributes (Thmm B
Given that practical node attributes are often not that informative, the advantages of non- non-linear propagation over linear propagation for node classification is limited albeit observable. Our analysis and conclusion apply to both homophilic and heterophilic settings, i.e., when nodes with same labels
tend to be connected (homophily) or disconnected (heterophily), respectively 25
28 36.3).
Extensive evaluation on both synthetic and real datasets demonstrates our theory. Specifically, the node mis-classification errors of three citation networks with different levels of attributed information (Gaussian attributes) are shown in Fig. [ which precisely matches the above conclusions.
1.1 More Related Works
GNNs have achieved great empirical success while theoretical understanding of GNNs, their non- linearity in particular, is still limited. There are many works studying the expressive power of GNNs (16 38)48), while they often assume arbitrarily complex non-linearity with limited quantitative results. Only few works provide characterizations on the needed width or depth of GNN layers [45]
48
More quantitative arguments GNN analysis often depend on linear or Lipschitz continuous

---

and over- squashing |
assumptions to enable graph spectral analysis, such as feature oversmoothing 44 50
52] the failure to process heterophilic graphs [25 and the limited spectral
representation [5 55 Some works also study the generalization bounds (56588) and the stability of GNNs (29622) However, the obtained results may not reveal direct comparison between non- linearity and linearity of the model, and their analytic techniques avoid tackling the specific forms of non-linear activations by using a Lipschitz continuous bound which is too loose in our case.
62
Stochastic block models (SBM) and its contextual counterparts have been widely used to study the node classification problems 32 63 67]. while these studies focus on the fundamental limits.
Recently, (C)SBM and its large- graph limitation also have been used to study the transferrability and expressive power of GNN models [68 70 and GNNs on line graphs (5), while these works did
not compare non-linear and linear propagation. CSBM has also been used to show the advantage of
linear convolution over no convolution for node classification (7]. very recent result shows that attention-based propagation
24 may he much worse than linear propagation given low-quality node
attributes under CSBM (22. Our results imply that ReL.U is the de facto optimal non-linearity instead
of attention and may most marginally outperform the linear model when with low-quality node attributes. Some previous works also use Bayesian inference to inspire GNN architectures (73 while these works focus on empirical evaluation instead of theoretical analysis.
2 Preliminaries
In this section, we introduce preliminaries and notations for our later discussion.
Maximum-a-posterioor (MAP) estimation. Suppose there are set of finite classes C. A class label Y E C is generated with probability Ty, where Eyee Ty = =1. Given Y. the corresponding feature X in the space X' is generated from the distribution X Py. A classifier is decision f X C and x(x where and later 1s indicates if S is true and otherwise. The MAP estimation of Y given X is
the Bayesian mis- miisclassificattinn error can be characterized as E(f) = Evec T J 1
the classifier (X) _ arg maxyee Ty (X) that can minimize {(ʃ) 335 Later, we denote the minimal Bayesian mis-classification error E(f) as 5 = E("")
Signal-to-Noiee Ratio (SNR). Detection of a signal from the background essentially corresponds to a binary classification problem. SNR is widely used to measure the potential detection performance before specifying the classifier (81). In particular, if we have two equiprobable classes C = {-1, 1}
and the features follows 1-d Gaussian distributions Py = N(Jy, o²), Y E C. The SNR p defined as follows precisely characterizes the minimal Bayesian mis clsscsassiiicatton error.
mean difference?
(#1 2-1) g²
SNR: P
(1)
variance
In this case, the MAP estimation (xX) = 2 + x 1 and the minimal Bayesian mis-classification error is ((-vp/2 where & denotes the cumulative standard Gaussian distribution function. For more general cases where the two classes are associated with aab-Guassian distribu- tions Iy,, s.t. (r > 1) E [el exp(-c2(²), C1 exp(-C2(2)) for some non-negative constants C1, C22 C1, C2, a similar connection between g* and p can be shown by leveraging sharp sub-Gaussian lower bounds [82). We will specify the connection to SNR in our case in Sec. f and the SNR p will be used as the main bridge to compare the mis-classification errors of non-linear v.s. linear models.
Contextual Stochastic Block Model (CSBM). Random graph models have been widely used to For node classification problems, CSBM is often used (68] 770. as it well combines the models of network structure and node attributes.
study the performance of algorithms graphs 83 84
We study the case that nodes are in two ggui-probable classes C = {-1, 1), where 'Ty = 1, Y E C. Our analysis can be generalized. An attributed network 9 = (V, E, is sampled from CSBM with parameters (n,, P, q, P1, P-1) as follows. Suppose there are nodes, V = [m]. For each node the label Y, E C is sampled from Rademacher distribution. Given Y,,, the node attribute X, is sampled from Py.. For two nodes u, v, if Y, Y., there is edge Cue E E connecting them with probability p. If Y,, * Y,, there is an edge ene E E connecting them with probability q. All node attributes X and edges & are independent given the node labels Y (Y./v= E V).
Note that p > q indicates the nodes with the same labels tend to be directly connected, which corresponds to the homophilic case, while p < q corresponds to the heterophilic case.
3

---

The gap p gl. representing probabilities difference of a node connects to nodes from the same class or the different class, reflects structural information and the gap between P,. P-1 reflects attributed information, e.g., Jensen-Shannon distance JS(PI, PP) that is well connected to Bayesian mis-classification error [85]. Graph learning allows combining these two types of information. In Sec. D we give more specific definitions of these two types of information and their regime for our analysis.
3 Bayesian Inference and Nonlinearity in Graph Neural Networks
In the previous section, we discuss that given conditioned feature distributions X ~ Py, Y E C, the MAP estimation (X) can minimize mis-classification error. For node classification in an attributed network, the estimation of a node label should depend on not only one's own attributes but also its neighbors'. For example, in homophilic network, nodes with same labels tend be directly connected. Intuitively, using the averaged neighbor attributes may provide better estimation of the label, which gives us graph convolution. In heterophilic network, nodes with different labels tend to be directed connected. So, intuitively, checking the difference between one's 's attributes and the neighbors' may provide better estimation. However, what could be the optimal form combine one's 's own attribute with the neighbors' attributes? We resort to the MAP estimation. That is, given and its neighbors No, we consider the MAP estimation as follows.
the attributes of a node
(X
argmax max Y.EC Y.E..VEN,
TYu,IYuhEN,, I (Xu: (XuIueN, (Y (Yu)ueN.),
where "Y..(YuJueen denotes their prior distributions node labels. Note that here we simplify the problem and consider only I-hop neighbors by following the setting (7T). In practice, most GNN models can only work on local networks due to the scalability constraints [1186887] Even with the above simplification, the above MAP estimation is generally intractable.
Therefore, we consider the CSBM with parameters (n. p. q. P1, P-1). In this case, the prior distribu- tion follows TY...Y.)aeN. 2 .Mll11, which is constant given Ng. The rest term follows
P (X.,, (Xu)nEN, (Yu]ueN,) = (X,, { (Xa)
XuJuEN, IY,, PP (Ya)
II
Py, (X,) II g2 (2)
uEN.U(u)
WEN.
Therefore, the MAP estimation f"(X,,, (Xu)aeN,) is solve
(",,,, (Xu)aeA.) argmax Py, (X,)
max Py, II
(3)
Y.EC
Y.EC
MEN,
This can be solved via the max-product algorithm 88]. To establish the connection to GNNs, we in the logarithmic form and use the fact that C (-1,1). And, achieve
rewrite the RHS of Eq. 3
P. (Xx)
(" (XulueN.) sgn
log
Σ M(X
where
P-1 (Xw)
NEN.
P1 (X,) P-1 (X.)
+ log P 7)
P1 (X₂) - ReLU log P-1 (X.)
! p
! p
M(Xx, = ReLU log
+ log
+ log
We leave the derivation in Appendix B Amazingly, activation ReLUs in the message M well connect
the activations commonly-us optimality of the MAP estimation, we summarize this observation in Proposition |
GNN models, e.g., graph convolution networks 12 Given the
Proposition (Optimal Nonlinear Propagation). Consider a network G ~ P, To classify node the optimal nonlinear propagation (derived by the MAP estimation) given the attributes of o and its neighbors follows:
P. = (X
Σ WENs
( (X.: PP)::PP.
(4)
where v (a; P-1) log P((a) F_](a]
and (aa log 2) = ReLU(a + log ?) ReLU lloga--ooog- log ?) - -log P.

---

The optimal nonlinear propagation in Eq. may contain two types of non-linear functions: (1) & to measure the likelihood ratio between two classes given the node attributes; (2) Φ is to propagate the likelihood ratios of the neighhors. ReL.Us in & avoid the overuse of the likelihood ratios from neighbors, as & essentially provides a bounded function (See Fig. D. One observation of the direct benefit of this non-linear propagation is as follows.
Homephili:
A+p
Hetereghiiee
Figure 2: Function Φ(x; log g)
Remark 1. When there is no structural information, i.e., P = 6(x; = 0, Va E R, the propagation is deactivated, which avoids potential contamination, from the attributes of the neighbors.
In the equiprobable case, the MAP estimation also gives the maximum likelihood estimation (MLE) of Y if we view the labels as the fixed parameters. When the classes are unbalanced Ty o 3. similar results can be obtained while additional terms log カー1 analysis focuses on the equiprobable case while empirical results in Sec. show more general cases.
_h_ may appear bias in Eq. 4 Later, our
Moreover, if one is to infer the posterior distribution of Y, one may replace the max-product algorithm solve Eq. B with the sum-product algorithm (89]. Then, the obtained non-linearity in ő will turn into Tanh functions. As ReLUs are more used in practical GNNs, we focus on the case with ReLUs.
Discussion the Non-linearity. Next, we discuss more insights into the non-linearity of sb and Φ
The function & essentially corresponds to a node-attribute transformation. which depends on the distributions P11. As these distributions are unknown in practice, NN model to learn & is suggested, such as the one in the model APPNP (1 and GPR-GNN (25). Due to the expressivity of NNs 90 91]. a wide range of sa can be modeled. One insighfful example is that when P11 are Laplace distributions. &b is a bounded function (same as Φ)) to control the heavy-tailed attributes generated by Laplace distributions.
Example 1 (Laplace Assumption). When node attributes follow m-dimensional independent Laplace distribution, i.e., Py, (26)m exp(- x /bb for μ E IR"", and Y, E 1-1,1}. According to Eq. 4 the function (- 11,PP can be specified as
1a (X,: F1, 1-1) 1d o(xo(Xx;2)) 2p/b), where & as defined in Eq. works in an entry-wise manner.
As node-attribute distributions may vary lot, y is better to be modeled via general NN in practice. More interesting findings may come from ø in Eq. as it has a fixed form and well matches the most commonly-used GNN architecture. Specifically, besides the extreme case stated in Remark D we are to investigate how non-linearity induced by the ReLUU in á may benefit the model. We expect the findings provide the explanations some previous empirical experiences using GNNs.
To simplify our discussion, when analyzing é, we focus on the case with a linear node-attribute transformation vi t'Gau in Eq. 1 by assuming label-dependen Gaussian node attributes. This follows the assumptions in previous studies [7 [2]. In fact, there are a class of distributions named natural exponential family (NEF) 34 which if the node attributes satisfy, the induced ø is linear. We conjecture that our later results in Sec. are applied to the general NEF since the only difference is the bias term by comparing Eq. and Eq. (6)
Example 2 (Natural Exponential Family Assumption). When node features follow m-dimensional natural exponential family distributions Py, (x)= h(X.)) exp(0), X, (fy.)) for fy, E R" and Yu E 111,1} where M (0y,) is a parameter function. The function s/; 1P, is specified as:
Vnn( 01, 01) In particular, when P. No,, 1/ h/mm. P-1 = =N(,, for 10r,, RM
-0-1)² x. (M,))) ((-))))
(5)
Vaa u, (X, m 11 x,, - (11A112 - 1121
(6)
More generally, our optimal nonlinear propagation Eq. 4 can be well generalized to other settings as long as the model satisfies edge-independent assumption, where edges random variables are mutually independent conditioned on the labels of nodes. When this assumption is satisfied, the MAP estimation will result in graph convolution with ReI.U activation.
We summarize our main theoretical findings regarding the nonlinearity of & in the next section.
5

---

(71,, we also 4 Main Results on ReLU-based Nonlinear Propagation
In this section, we summarize our analytical results on @ in the optimal nonlinear propagation (Eq. Our study assumes an attributed network generated from CSBM(n, P, q, N,,N,, N/,, I/m)) where μ4, v E IR. We use CSBM-G(n, P. q; H1 v) later to denote this model for simplicity. We are interested in the asymptotic behavior when - co. Note that all parameters je, v,P, q, may implicitly depend on n. We are to compare the non-linear propagation model P. suggested by Eq. where v Gan with the following linear counterpart P.
Baseline linear model: (w) d' (Xui v) + w
Σ M.N.
D.eau (Xu: for all E V. (7)
where E R is extra parameter to be tuned. Note that this linear model can be claimed as an optimal linear model up-to a choice of w because the distributions of both the center node attribute X, and the linear aggregation from the neighbors Enex, X2, are Gaussian and symmetric w.r.t. the hyperplane {Z E [ =) = (11m1 [|,] for the two classes. We are to compare their classification errors e" = =(sgn(P.)) and <'(w) E(sgn( (w))). By following
discuss separability of all nodes in the network, i.e., P(ve E V.P. Y, > 0) in Theorem 1.
To begin with, introduce several quantities for the convenience of further statements. The SNRs
Ar (E|P, 1| EYP, -1)) var(P.|V, 1)
.p((w) (E(P)(W))Y, = 1]
-1))
var(P.(w)) 1)
are important quantities to later characterize different types of propagation. Also, we characterize structural information by S(p, q) = (p - //2 q) and attributed information by vmilı / 1112.
Assumption (Moderate Structural Information). S(p. q) = wnn( (log and S(p.9) lp-gi +
n
Assumption 2 (Bounded Attributed Information). /m pl u|12 on (logn).
Assumption states that structural information should be neither too weak nor too strong. S(p. q) =
wo.( (] excludes the extremely weak case discussed in Remark Moreover, the graph structure should not be too sparse, so the aggregated information from neighbors dominates the propagation. S(p.9)
1 means neither p (g) nor q wn (p), which avoids extremely strong structural
In-gl
information. This assumption is more general than some concurrent works on CSBM-based GNN analysis 71 72 as include the cases with less structural information Ip 9l o, (p + q) and with heterophily p < q. Assumption 2 is to avoid too strong attributed information: when Vmillu 2112- S2, (log rz), all nodes in CSBM can be accurately classified in the asymptotic sense without structural information, i.c. IP(vo E V, Viaa μt, 1/) Y, >> 0) = 1 1- (1). Now, we present our first lemma which links the mis-classification errors & gl to with the SNRs pr. Pr:
Lemma 1. Suppose (p.q) satisfies Assumption 1 for any CS p,
e" E [C1 exp(-Cap,/2), exp(- pr))),, ('(w) + exp(-p on (1))/2)
(8)
where C2 is asymptotically a constant, and the notation a(n) + b(n) denotes a(n) /b()))/))) 1. Lemma claimms that the classification errors under both nonlinear and linear model can be controlled by their SNRs. By leveraging Lemma I we can further illustrate the separability of all nodes in the network, which is presented in the following theorem.
Theorem 1 (Separability). Suppose that (p, q) satisfies Assumption 7 for G ~ (SBM-GG(n.......) if mm || - 2112- = wnl ValVlog Vlogg/////// Snp/Spp.))) n)), then
PPVV E V. P. Y. 0) = O₂ (n = 1- (1),
(9)
P(VU E V. P! (l (w) Y, > 10 (n
= - on (1).
(10)
Here, assume |w| > e for some positive constant and anddaan(ww) sgn(w) sgn(p q) in the linear model.
Theorem I applies to both homophilic (p > 9) and heterophilic (p < 9) scenarios. Even for just the linear case, compared to (71) which needs v/mlI wI12 w. (log (S(p q)m) to achieve separability, we have Vlog improvement due to tight analysis.

---

As shown in Lemma I and Theorem the errors are mainly determined by SNRs. Large SNR implies a fast decay rate of the errors single node and the entire graph, which motivates to further explore SNRs to illustrate a comparison between non-linear and linear models. We consider comparing with the optimal linear model, i.e., pi = pr(w") ") where wr = arg min (ww).
Theorem 2. Suppose that (p,9) 9) satisfies Assumption 7 for 9 ~ CSBM-G(n, P. p.q, p. v), under the separable condition in Theorem Vmllu= 2/12 = wn (v log n/ggn/(pp, q)m), we further have
I. Limited Attributed Information: When Vmill - 1/12 (I),
Pr p- (pi))
(11)
Further, if Vmllp- v1|2 or, ((og(p///))) pr/pi 1;
II. Sufficient Attributed Information: When /mill 2112 win (1) and satisfies Assumption 2
Pr -w,, (min (min(((eex(((m]]) =112/3,, (S(p.))m - =1122) pi) (ni
(12)
Theorem 2 also works both homophilic (p > 9) and heterophilic (p < q) scenarios. Theorem implies that when attributed information is limited, nonlinear propagation behaves similar to the linear model as their SNRs in the same order. Particularly, when attributed information is very limited, V 2//2 on (1 fo)(p/g)l), the SNRs of two models are asymptotically the same. In the regime of sufficient attributed information, nonlinear propagation brings order-level superiority compared with the linear model. The intuition is that in this regime, when the attributes are very informative, the bounds of in Eq. help with avoiding overconfidence given by the node attributes. The coefficient before of in Eq. (12 shows the trade-off between structural information and attributed information on controlling the superiority of nonlinear propagation.
Next, we analyze whether nonlinearity makes model more transferable or not when there often exists distribution shift between the training and testing datasets, which is also practically useful.
We consider the following setting. We assume using large enough network generated by CSBM- G(n.P, P. 9. 16,1,. v) for training so that the optimal parameters as in P. and (ww") for this CSBM-G have been learnt. We consider their mis-classificattin errors over another CSBM-G with parameters (n. p', q'' μ², v²). We keep the amounts of attributed information and structural information unchanged
by setting p = p'. q = g', μ² = (μ + v) /2+ + R(p - v)/2, v' = μ + v/2 + R(v - p2/2 for a rotation matrix R close I. Let Aç" and AE' (w*) denote the increase of miisclaasification errors of models P. and (w("", respectively, due such distribution shift. We may achieve the following results.
Theorem 3 (Transferabilityy. Suppose that (p,4) satisfies Assumption 7 for G' -CSBM- G(n, p', d' 1l,, v'), under the linear separable condition /milpp v/112 wi (Voo n/S(p' ..fd)mm)) mn). Suppose Pe and (((w") have learnt parameters from ~ CSBM-G(n, q. n4 v) where the parame- ters of two CSBM-Gs follow the relation described above. Then, we have
I. Limited Attributed Information: When /m 2112 on log(p/g))) DE DET (A
II. Sufficient Attributed Information: When /milp w112 (1) and and satisfies Assump- tion DET AET/AE((W") O.
Similar to Theorem 2, when attributed information is very limited, nonlinearity will not bring any benefit, while in the regime with informative attributes, nonlincarity increases model transfcrability. We leave the intermediate regime /mlly l ul12 E [S2, ((og(p//))) ( for future study.
5 Experiments
In this section, we verify our theoretical results based on synthetic and real datasets. In all experiments, we fix w in the linear model (Eq. 7 as = for the homophilic case (p > q) and w 1 for the heterophilic case (p < 9). Experiments on other w's can be found in Appendix H.1.1 which does not change the achieved conclusion. This is because when the node number is large, for constant w, the neighbor information will dominate the results. Later, we use p! (!(w) for simplicity.
5.1 Asymptotic Experiments - Model Accuracy & Transferability Study
Our first experiments focus on evaluating the asymptotic (n - oc) classification performance of nonlinear and linear models. Given CSBM-G, we generate 5 graphs and compute the average
7

---

Komophil Limited Atributed Information.
Heg-oomppiille Sefficient Altributed Informaline
Heswophhy 1 Fioed Attributed Information
Optimal Nostineer Propogedie
Optimal Nothoaar Propogation
Optiall Nostibeer Propogetion
lissu Apurasuiiss
0.00
Lanner Agurepataon
0.50
0.70
Apcurec:
0.66
VT
10
0.80
0.70
0.60
12
2
0.3 Log
0.60
1
2
<10g
1x
2 0.5
0.70
137
0.60
0.50 13
Graph Nodas
Graph Nodaa
Figure 3: Classification Performance Nonlinear Models v.s. Linear Models (Po v.s. P(). LEFT: Homophily + Limited Attr. Info.; MIDDLE: Homophily + Suff. Attr. Info.; RIGHT: Heterophily + Fixed Attr. Info.. 10 and other parameters are listed in the figures.
Perturbation Error Ratlo
3.2
Limbed Allntbatad Insermation
X 10
Porturbation Etror Rato
1.2
Limitd Altrthated Infermaticn
1 10
1.2
Limied Altritated Intermation
X
Actriooted Infommttion
Sullituat Aitthoeed Infinnution
Bullissaat Alcibate Iafamndion
1.0
1.0
0.9
6.
6.8
0.10
0.35
3.20
0.25
0,30
0.10
0.35 Perlorbation Intensily
9.20
1.225
0.30
0.0
0.10
0.35
0.20
0.25
0.30
Pertarbation Toletsily
Perturbation Inlessity
Figure 4: Perturbation Intensity (1 (ul 1 /\/llm =113) v.s. Perturbation Error Ratio
(Aç*/ /Ag)) with Different Node Numbers. Other parameters are: p = 2//nnn, vn/n; Limited
Attr. Info. || 2/12 0.3 log" n/ nn; Suff. Attr. Info. || 2112 0. 0l1vlogn.
accuracy results (#correctly classified nodes #total nodes). We compare the nonlinear v.s. linear models under three different CSBM-G settings. Fig. 3 shows the results.
All three cases satisfy the separability condition in Theorem [ so, increases, the accuracy progressively increases to 1. Our results also match well with the implications provided by Theorem In the regime with limited attribute information (Fig. D LEFT) where Pr (p) proved. the nonlinear model and the linear model behave almost the same (performance gap < 0.15% for [
10º). In the regime with sufficient attribute information (Fig. MIDDLE) where p, w,, (pf) as proved, we may observe that the nonlinear model can significantly outperform the linear model (p q). If we switch the values
Fig. RIGHT is to show the heterophilic graph of p. (and also change the models correspondingly), we obtain the exactly same figure up to some experimental randomness (see Appendix H.I.2).. Also, Fig. RIGHT considers boundary case of sufficient attributed information, i.e., V U112 = (I))). We observe that Theorem still well describes the asymptotic performance when + co.
We further study the transferability for the non-linear model and the linear model. We follow the setting in Theorem B by rotating / μL, 1,'2" v'. Fig. g shows the result and well matches Theorem In the regime of limited attributed information, the two models have the almost same transferability. i.e, the perturbation error ratio is close 1. In contrast, with sufficient attributed information, the non-linear model more transferrable than the linear counterpart as the ratio is smaller than 1.
5.2 Transition Curve
Our second experiment studies the tradeoff between attributed information and structural information. We fix the graph size n = 2 x 10a and get the averaged classification accuracy based on generated graphs. For the homophilic case, we test different levels of attributed information (I) =ll from 10-4 to 10 with m 10) and structural information (fixing q = 5 x 10-3 -3 and increasing p from p g to 1). The intermediate testing points sampled in log scales. Fig. LEFT shows the results. When structural information is limited and attributed information is sufficient, the non-linear model shows significant advantage
the linear model while for most other parameter settings, these two models share similar performance. Fig. RIGHT shows the heterophilic case, where we observe a similar pattern. In the heterophilic case, fixing p 5 x 10 and increasing from q p to 1.

---

Norlinear
Linea
Performance Gap
Nont hew"
Uneer
Astributee information
Attrbited Aitrhuddd Informatoon
Structural Information
Structurll Information (hanarophiic)
Figure 5: Transition Curves Attributed Information (ymll v112) Structural Information () [log(p/)) ( for CSBM-G with Homophilic (LEFT) Heterophilic (RIGHT) Graph Structures. The values in Performance Gap are obtained by the nonlinear case subtracting the linear case.
PubMed Laplecian
Laplecion
Laplacion
Accuracy
0.8
Accuracy
Accuracy
Propagetion
Propagation
Propagatinn
Model
Unvar Mrdd
Unwee Macel
Only the Nat-Irwer Tropagiican
Only Nan-Iraer Tropepation
Drtx The Nin-iraae Tropapation
Ouly PSi Almibuis Translonnatinn
0.5:
Only Altribute Trunslemation No Propayation
0.5
Out Pai Aunber funniomation
No Propagation
-4-
-4- No Propagation
0.4
0.4
0s Attributed Information ((uule))
0.1
0 as
Altributed
((uila))
Attributed
((ulla)
Figure 6: Averaged one-vs-all Classification Accuracies on Citation Networks of Different Nonlinear Models v.s. Linear Models. Node attributes in or out of the one class are generated from Laplace distributions with different means =u and = (Example [ The optimal non-linear model has advantage over the models with only nonlinear attribute transformation (thap), with only nonlinear information propagation (ø), the linear model.
5.3 Real-world Network Experiments
This experiments compare non-linear models and linear models under Gaussian and Laplacian attributes on three benchmark citation networks PubMed, Cora, and CiteSeer (92). In these three networks, nodes denote papers and edges denote the citation relationships between the papers. The statisties (# nodes, # edges, # classes) of these three networks are: PubMed (19,717, 44,338, 3); Cora (2,708, 5,428, 7); CiteSeer (3,327, 4,732, 6).
Experimental Settings. We carry out o.s-v.s.-all and seeeeera classification tasks. After nodes are put into two classes, we generate two graphs independently with attributes according to Gaussian (or Laplace) distributions. One graph is used for training and the other one for testing. For the Gaussian case, we use a nonlinear model by following Eq. 4 with vi = t/Gm while the parameters such log(p/ ()) μl- and other biases need to be learned. For the Laplacian case, consider three nonlinear models by following the form of (a) full Eq. 4 with 3 = Vaaap: (b) only nonlinear attribute (c) only nonlinear propagation & with linear attribute transformation. Later, we call them nonlinear models (a), (b), (c), respectively. Similar to the Gaussian case, all the parameters in these functions obtained by training. The model is trained with Adam optimizer (learning rate- = le - 2, weight decay= = 5e - 4). We give other details to Appendix H.2.
transformation z t'tap'
Result Analysis. We report the averaged results over trials in Fig. [ Gaussian) and Fig. 6 (Lapla- cian). Due to the space limit, we leave the results for the several-v.s.-Se -severa case Appendix H.2. The Gaussian case well matches our theory. Only when the node features are very informative, the gaps between the nonlincar model and the linear model become significant. This is true for all three networks.
The Laplacian case is more complicated. Non-linear model (a) outperforms the non-linear models (b) and (c). The two non-linear models both outperform the linear model. More specifically, when attributed information is not very informative, i.e., small ||||| attribute nonlinear transformation function chaa is more crucial, because in this regime, non-linear model (a) significantly outperforms non-linear model (c) and non-linear model (b) significantly outperforms the linear model, while two nin-lr models (a) and (b) perform similarly, and non-linear model (c) and the linear model perform similarly. With more informative attributed information, nonlinear propagation function becomes more significant, because the gaps between two non-linear models (a) and (b) (also,

---

non-linear model (c) and the linear model) are obvious, which again matches our Theorem 2 although here we have Laplacian node attributes instead of Gaussian node attributes.
Conclusion
This work uses Bayesian methods to investigate the function of non-linearity in GNNs. Given graph generated from CSBM, we observe the optimal non-linearity to estimate a node label given its own and neighbors' attributes in twofold: attribute non-linear transformation and non-linear propagation. We further investigate the non- non-linear propagation by imposing Gaussian assumptions on node attributes. We prove that non- non-linear propagation shares similar performance (with without distribution shift) with linear propagation in most cases except when node attributes become very informative. These findings explain many previous empirical observations in this domain and would help researchers and practitioners to understand their GNNs' behaviors in practice.
7 Acknowledgement
We greatly thank all the reviewers for valuable feedback and actionable suggestions. R. Wei, H. Yin and P. Li are partially supported by 2021 JPMorgan Faculty Award and NSF award OAC-2117997.
References
[1] X. Zhu, Semi-supervised learning with graphs. Carnegie Mellon University, 2005.
[2] W. L. Hamilton, "Graph representation learning," Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 14, no. 3, pp. 1-159.
[3] S. Fortunato, "Community detection in graphs," Physics reports, vol. 486, no. 3-5, pp. 75-174, 2010.
[4] A. Lancichinetti and S. Fortunato, "Community detection algorithms: comparative analysis." Physical review E, vol. 80, no. 5. p. 0561 17, 2009.
[5] Z. Chen, I., Li, and J. Bruna, "'Supevviedd community detection with line graph neural networks," in International Conference on Learning Representations, 2020.
[6] Liu, S. Xue, Wu, C. Zhou, W. Hu, C. Paris, S. Nepal, J. Yang, and P. S. Yu, "Deep learning for community detection: progress, challenges and opportunities," in Proceedings of the Twenty- Ninth International Joint Conferences on Artificial Intelligence, 2021, pp. 4981-4987.
[7] X. Ma, J. Wu, S. Xue, J. Yang, C. Zhou, Q. Z. Sheng, H. Xiong, and L.. Akoglu, "A comprehen- sive survey on graph anomaly detection with deep learning," IEEE Transactions on Knowledge and Data Engineering, 2021.
[8] A. Z. Wang, R. Ying, P. Li, N. Rao, K. Subbian, and J. Leskovec. "Bipartite dynamic representa- tions for abuse detection," " in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 3638 -6488
[9] T. Aittokallio and B. Schwikowski, "Graph-based methods for analysing networks in cell biology." " Briefings bioinformatics, vol. 7, no. 3, pp. 243-255, 2006.
[10] J. Scott, T. Ideker, R. M. Karp, and R. Sharan, "Efficient algorithms for detecting signaling
pathways in protein interaction networks," Journal of Computational Biology, vol. 13, no. 2, pp. 133-144, 2006.
[11) W. Hamilton, 7. Ying, and J. Leskovec, "Inductive representation learning on large graphs," in Advances in Neural Information Processing Systems, vol. 30, 2017.
[12] T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," in International Conference on Learning Representations, 2017.
[13] K. Xu, W. Hu, Leskovec, and S. Jegelka, "How powerful are graph neural networks?" in International Conference on Learning Representations, 2019.
[14] C. Morris, M. Ritzert, M. Fey, W. I.. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, "Weisfeiler and leman go neural: Higher-order graph neural networks." in Proceedings of the AAAI conference on artificial intelligence, vol. 33, 2019, pp. 4602-4609.
[15] N. Keriven and Peyré, "Universal invariant and equivariant graph neural networks." Advances in Neural Information Processing Systems, vol. 32, 2019.
10

---

[16] Z. Chen, S. Villar, L. Chen, and J. Bruna, "On the equivalence between graph isomorphism testing and function approximation with gnns," " Advances in Neural Information Processing Systems, vol. 32, 2019.
[17] W. Azizian et al., "Expressive power of invariant and equivariant graph neural networks," in International Conference on Learning Representations, 2021.
[18] Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. Dahl, "Neural message passing for quantum chemistry," in International Conference on Machine Learning. PMLR, 2017, pp. 1263-1272.
[19] Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger, "Simplifying graph convolutional networks," in International Conference on Machine Learning. PMLR, 2019, pp.
[20] X. He, K. Deng, X. Wang. Y. Li, Y. Zhang, and M. Wang. "Lightgen: Simplifying and powering graph convolution network for recommendation." in Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, 2020, pp.
[21] J. Klicpera, A. Bojchevski, and S. Günnemann, "Predict then propagate: Graph neural networks meet personalized pagerank," in International Conference on Learning Representations, 2018.
[22] Klicpera, S. Weißenberger, and S. Günnemann, "Diffusion improves graph learning," in Advances in Neural Information Processing Systems, vol. 32, 2019.
[23] Q Huang, H. He, A. Singh, S.-N. Lim, and A. Benson, "Combining label propagation and simple models out-performs graph neural networks," in International Conference on Learning Representations, 2020.
[24] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph attention networks," in International Conference on Learning Representations, 2018.
[25] E. Chien, Peng, P. Li, and O. Milenkovic, "Adaptive universal generalized pagerank graph neural network," " in International Conference on Learning Representations, 2021.
[26] X. Wang and M. Zhang, "How powerful are spectral graph neural networks," in International Conference Machine Learning. PMLR, 2022.
[27] J. Zhu, Y. Yan, I.. Zhao, M. Heimann, L.. Akoglu, and D. Koutra, "Beyond homophily in graph neural networks: Current limitations and effective designs," Advances in Neural Information Processing Systems, vol. 33, 2020.
[28] J. Zhu, R. A. Rossi, A. B. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra, "Graph neural networks with heterophily," in Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[29] L. Chen, Z. Chen, and J. Bruna, "On graph neural networks versus graph-augmented mips," in International Conference on Learning Representations, 2021.
[30] W. Cong, M. Ramezani, and M. Mahdavi, "On provable benefits of depth in training graph convolutional networks," Advances in Neural Information Processing Systems, vol. 34, 2021.
[31] P. Li and J. Leskovec, "The expressive power of graph neural networks," in Graph Neural Networks: Foundations, Frontiers, and Applications. Springer, 2022, pp. 63-98.
[32] N. Binkiewicz, J. T. Vogelstein, and K. Rohe, "Covariate-assissted spectral clustering," Biometrika, vol. 104, no. 2. pp. 361-377, 2017.
[33] Y. Deshpande, S. Sen, A. Montanari, and E. Mossel, "Contextual stochastic block models," Advances in Neural Information Processing Systems, vol. 31, 2018.
[34] C. N. Morris, "Natural exponential families with quadratic variance functions," " The Annals of Statistics, pp. 65-80, 1982
[35] S. Theodoridis, Machine learning; a Bayesian and optimization perspective. Academic press, 2015.
[36] S. Suresh, V. Budde, J. Neville, P. Li, and J. Ma, "Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns," in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021, pp. 1541-1551.
[37] Y. Ma, X. Liu, N. Shah, and Tang, "Is homophily a necessity for graph neural networks?" arXiv preprint arXiv:2106.0611 2021.
11

---

[38] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman, "Provably powerful graph networks," Advances neural information processing systems, vol. 32. 2019.
[39] M. Balcilar, P. Héroux, B. Gauzere, P. Vasseur, S. Adam, and P. Honeine, "Breaking the limits of message passing graph neural networks," in International Conference on Machine Learning. PMLR, 2021, pp. 599-608.
[40] W. Azizian et al., "Expressive power of invariant and equivariant graph neural networks," in International Conference on Learning Representations, 2021.
[41] R. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro, "Relational pooling for graph representations," in International Conference Machine Learning. PMLR, 2019, pp. 4663-4673.
[42] R. Sato, M. Yamada, and H. Kashima, "Random features strengthen graph neural networks," in Proceedings of the 2021 SIAM International Conference on Data Mining (SDM). SIAM, 2021, pp. 333-341.
[43] R. Abboud, I. I. Ceylan, M. Grohe, and T. Lukasiewicz. "The surprising power of graph neural networks with random node initialization,"" " in Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021, pp. 2112-2118.
[44] C. Bodnar, F. Frasca, N. Otter, Y. Wang, P. Lio, G. F. Montufar, and M. Bronstein, "Weisfeiler and lehman go cellular: Cw networks," Advances in Neural Information Processing Systems, vol. 34, 2021.
[45] P. Li, Y. Wang. H. Wang, and J. Leskovee, "Distance encoding: Design provably more powerful neural networks for graph representation learning," Advances in Neural Information Processing Systems, vol. 33, pp.
2020.
[46] A. Loukas, "What graph neural networks cannot learn: depth vs width," in International Conference Learning Representations, 2020.
[47] C. Vignac, A. Loukas, and P. Frossard, "Building powerful and equivariant graph neural networks with structural gressageppassingg Advances in Neural Information Processing Systems, vol. 33, 2020.
[48] M. Zhang and P. Li, "Nested graph neural networks," Advances in Neural Information Processing Systems, vol. 34, 2021.
[49] K. Oono and T. Suzuki, "Graph neural networks exponentially lose expressive power for node classification," in International Conference on Learning Representations. 2019.
[50] Q. Li, Z. Han, and X.-M. Wu, "Deeper insights into graph convolutional networks for semi- supervised learning." in Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[51] U. Alon and E. Yahav, "On the bottleneck of graph neural networks and its practical implications," in International Conference on Learning Representations, 2021.
[52] J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, and M. M. Bronstein, "Understanding over-squashing and bottlenecks on graphs via curvature," arXiv preprint arXiv:2111.14522 2021.
[53] Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra, "Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks," arXiv preprins arXiv:2102.06462, 2021.
[54] M. Balcilar, G. Renton, P. Héroux, B. Gaüizèee S. Adam, and P. Honeine, "Analyzing the expressive power of graph neural networks a spectral perspective," " in International Conference on Learning Representations, 2020.
[55] F. M. Bianchi, D. Grattarola, L. Livi, and C. Alippi, "Graph neural networks with convolutional arma filters." " IEEE Transactions on Pattern Analysis and Machine Intelligecee 2021.
[56] S. Du, K. Hou, R. R. Salakhutdinov, B. Poczos, R. Wang, and K. Xu, "Graph neural tangent kernel: Fusing graph neural networks with graph kernels." Advances in neural information processing systems, vol. 32, 2019.
[57] V. Garg, S. Jegelka, and T. Jaakkola, "Generalization and representational limits of graph neural networks," in International Conference on Machine Learning. PMLR, 2020, pp. 3419-3430.
[58] R. Liao, R. Urtasun, and R. Zemel, "A pac-bayesian approach to generalization bounds for graph neural networks," in International Conference on Learning Representations, 2020.
12

---

[59] F. Gama, J. Bruna, and A. Ribeiro, "Diffusion scattering transforms on graphs." in International Conference on Learning Representations, 2019.
[60] F. Gama, A. Ribeiro, and J. Bruna, "Stability of graph scattering transforms," Advances in Neural Information Processing Systems, vol. 32, 2019.
[61] R. Levie, W. Huang. L. Bucci, M. Bronstein, and G. Kutyniok, "Transferability of spectral graph convolutional neural networks." Journal of Machine Leurning Research, vol. 22, no. 272, pp. 1-59, 2021.
[62] Gama, J. Bruna, and A. Ribeiro, "Stability properties of graph neural networks," IEEE Transactions on Signal Processing, vol. 68, pp. 5680-5695, 2020.
[63] E. Abbe, "Community detection and stochastic block models: recent developments," The Journal of Machine Learning Research, vol. 18, no. 1, pp. 6446-6531, 2017.
[64] E. Abbe and C. Sandon, "Proof of the achievability conjectures for the general stochastic block model," Communications on Pure and Applied Mathematics, vol. 71, no. 7, pp. 1334-1406, 2018.
[65] L. Massoulié, "Community detection thresholds and the weak ramanujan property," in Proceed- ings of the forty-sixth annual ACM symposium on Theory of compuring, 2014, pp. 694-703.
[66] C. Bordenave, M. Lelarge, and L. Massoulié, "Nonbacktracking spectrum of random graphs: Community detection and nonregular ramanujan graphs," Annals of Probability, vol. 46, no. 1, pp. 1-71, 2018.
[67] A. Montanari and S. Sen, "Semidefinite programs on sparse random graphs and their application to community detection," Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 814-827.
[68] N. Keriven, A. Bietti, and S. Vaiter, "Convergence and stability of graph convolutional networks on large random graphs," Advances in Neural Information Processing Systems, vol. 33, 2020.
[69] Keriven, A. Bietti, and S. Vaiter, "On the universality of graph neural networks on large random graphs," Advances in Neural Information Processing Systems, vol. 34, 2021.
[70] L. Ruiz, L. Chamon, and A. Ribeiro, "Graphon neural networks and the transferability of graph neural networks," Advances in Neural Information Processing Systems, vol. 33, 2020.
[71] A. Baranwal, K. Fountoulakis, and A. Jagamnath, "Graph convolution for semiisupervised clas- sification: Improved linear separability and out-of-distribution generalization," in International Conference on Machine Learning. PMLR, 2021, pp. 684-693.
[72] K. Fountoulakis, A. Levi, S. Yang, A. Baranwal, and A. Jagannath, "Graph attention retrospec- tive," arXiv preprint arXiv:2202. 13060, 2022.
[73] D. Jin, Z. Liu, W. Li, D. He, and W. Zhang, "Graph convolutional networks meet markov random fields: Sumi-super community detection in attribute networks," in Proceedings of the AAAI conference on artificial intelligence, vol. 33, no. 01, 2019, pp. 152-159.
[74] M. Qu, Y. Bengio, and J. Tang, "Gmnn: Graph markov neural networks," in International conference machine learning. PMLR, 2019, pp. 5241-5250.
[75] J. Kuck, S. Chakraborty, H. Tang, R. Luo, J. Song, A. Sabharwal, and S. Ermon, "Belief propagation neural networks," Advances in Neural Information Processing Systems, vol. 33, 2020.
[76] J. Jia and A. R. Benson, "A unifying generative model for graph learning algorithms: Label propagation, graph convolutions, and combinations." SIAM Journal on Mathematics of Data Science, vol. 4, no. 1, pp. 100-125, 2022.
[77] V. G. Satorras and M. Welling, "Neural enhanced belief propagation on factor graphs," in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 685-693.
[78] J. Jia, C. Baykal, V. K. Potluru, and A. R. Benson, "Graph belief propagation networks." arXiv preprint arXiv:2 /06 106.0303. 03033, 2021.
[79] M. Qu, H. Cai, and J. Tang, "Neural structured prediction for inductive node classification," in International Conference on Learning Representations, 2021.
[80] N. Mehta, L. C. Duke, and Rai, "Stochastic blockmodels meet graph neural networks," in International Conference on Machine Learning. PMLR, 2019, pp. 4466-4474.
13

---

[81] H. V. Poor, An introduction to signal detection and estimation. Springer Science & Business
Media, 2013.
[82] A. R. Zhang and Y. Zhou, "On the non-asymptotic and sharp lower tail bounds of random variables," " Stat, vol. 9, no. 1, p. e314, 2020.
[83] Ding. Z. Ma, Y. Wu, and J. Xu, "Efficient random graph matching via degree profiles"" Probability Theory and Related Fields, vol. 179, pp. 29-115, 2021.
[84] P. Li, I. Chien, and O. Milenkovic, "Optimizing generalized pagerank methods for seed- expansion community detection," " Advances in Neural Information Processing Systems, vol. 32, 2019.
[85] J. Lin, "Divergence measures based on the shannon entropy," IEEE Transactions on Information Theory, vol. 37, pp. 145-151, 1991.
[86] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna, "Graphsaint: Graph sampling based inductive learning method," in International Conference on Learning Representations, 2019.
[87] H. Yin, M. Zhang. Y. Wang, J. Wang, and P. Li, "Algorithm and system co-design for efficient subgraph-based graph representation learning," arXiv preprint arXiv:2202. 13538, 2022.
[88] Y. Weiss and W. T. Freeman, "On the optimality of solutions of the max-product belief- propagation algorithm in arbitrary graphs." IEEE Transactions on Information Theory, vol. 47,
no. pp. 736-744, 2001.
[89] J. Pearl, "Reverend bayes inference engines: distributed hicrarchical approach." in Pro- ceedings of the AAAI conference on artificial intelligence, 1982, pp. 133-136.
[90] G. Cybenko, "Approximation by superpositions of sigmoidal function," Mathematics of Control, Signals and Systems, vol. 2, no. 4, pp. 303-314, 1989.
[91] K. Hornik, M. Stinchcombe, and H. White, "Multilayer feedforward networks are universal approximators." Neural Networks, vol. 2, no. 5, pp. 359-366, 1989.
[92] Sen, G. Namata, M. Bilgic, L.. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective classifica- tion network data," Al Magazine, vol. 29, no. 3, pp. 93-93, 2008
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We accurately claim our contributions. See section I, paragraph 4.
(b) Did you describe the limitations of your work? [Yes] See section 1, paragraph 4.
(c) Did you discuss any potential negative societal impacts your work? [N/A] Our work focuses theoretical contributions to better understanding of graph neural networks, which are not directly related to negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Our paper conforms to the ethics review guidelines.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tion M 2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Appendix G
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Figure
(d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [Yes] Refer to Appendix G
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See subsection 5.3
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Not applicable.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] Not applicable.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] Not applicable.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] Not applicable.
15


Reviews:
[{"review_id": "yURR0rPQ74q", "reviewer": "Reviewer_6wNk", "summary": "This paper characterizes the effect of non-linearity in GNNs from a Bayesian inference perspective. It shows whether non-linearity is beneficial is related to whether node attributes are more informative than structural information. Experiments are conducted to verify the theoretical results.", "questions": "See above.", "limitations": "I don’t think this paper has any negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies a very interesting research question concerning the role of non-linearity in GNNs. It poses valuable theoretical results answering when and why non-linear propagations have the potential to outperform linear counterparts, which is of benefit to the GNN community. The idea of using MAP to study the optimal propagation scheme may be of interest beyond the scope of this paper. The results also seem solid though I didn’t verity proofs in the supplementary material. Extensive experiments are conducted, and the results appear to align with the theoretical findings.\n\nI also think the paper is clearly written and easy-to-follow. I appreciate that the authors tried to give high-level explanations of theories throughout the paper. Yet, there seems to be some typos, e.g., Eq.(3) in line 199 and 203 should be Eq.(4)? I suggest the authors double checking equation references. \n\nHowever, I have a lingering concern regarding the discrepancy between the models used for analysis (i.e., Eq.(3) and Eq.(7)) and the common ones used in practice (e.g.,  non-linear [1-3], linear [4,5]). Though the models considered in the paper are valid GNN instantiations, the corresponding functions $\\phi$ and $\\psi_{Gau}$ are different with their counterparts in mainstream GNN models (i.e., $\\phi$ is ReLU and $\\psi$ is linear map), and usually we also apply activation function to $\\psi(X_{v})$ in Eq.(3). It is also strange that baseline linear model in Eq.(7) still uses $\\psi$ since it corresponds to using feature transformation in conventional linear GNNs. Whether the theoretical results generalize to other GNN settings is questionable (both theoretically and empirically). Maybe the authors can shed more lights on this? \n\n[1] Semi-supervised classiﬁcation with graph convolutional networks. \n[2] Inductive representation learning on large graphs.\n[3] Graph attention networks.\n[4] Simplifying graph convolutional networks.\n[5] LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VN9iQOzWSgA", "reviewer": "Reviewer_o4Ni", "summary": "This paper studies when non-linearity is useful for accuracy in graph neural nets. Authors show that under assumptions, the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure. \n----\nAuthors say that I gave \"accept score\" initially. This is wrong.\nSomehow this year \"5\" means borderline accept, but usually it meant \"weak reject\". So I intended to reject. I took another look of the paper and I feel the paper is not ready for publication so changed score to reject. ", "questions": "1. The main conclusion is vague and not so clear. The main point of the paper is trying to claim that \"the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure.\" However, it's not clear what you mean by node attributes are more informative than graph strucutre. A very clear definition and intuition, examples need to be give. \n2. It's not clear what practical implication we can gain? Why not just always add non-linearity, since they will outperform in some cases?\n\nAuthors need to clearly resolve my concerns to raise rating.", "limitations": "1. The main conclusion is vague and not so clear. The main point of the paper is trying to claim that \"the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure.\" However, it's not clear what you mean by node attributes are more informative than graph strucutre. A very clear definition and intuition, examples need to be give. \n2. It's not clear what practical implication we can gain? Why not just always add non-linearity, since they will outperform in some cases?\n\nAuthors need to clearly resolve my concerns to raise rating.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The problem of non-linearity is interesting and useful in practice.\n2. The result shows some interesting implications, e.g., when structure vs feature is more important. Though the main message is too vague to be useful.\n\nWeakness:\n1. The main conclusion is vague and not so clear. The main point of the paper is trying to claim that \"the superiority of ReLU activations is only significant when the node attributes are far more informative than the graph structure.\" However, it's not clear what you mean by node attributes are more informative than graph strucutre. A very clear definition and intuition, examples need to be give. \n2. It's not clear what practical implication we can gain? Why not just always add non-linearity, since they will outperform in some cases?\n\nAuthors need to clearly resolve my concerns to raise rating.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6g4ClnRfUM", "reviewer": "Reviewer_48Dg", "summary": "The paper theoretically and empirically studies non-linearity and linearity in Graph Neural Networks (GNN) from the Bayesian-Inference Perspective and tries to explain the phenomenon that in practice for node classification tasks, the non-linearity of GNNs only has marginal improvement over their linear counterparts. The paper considers CSBM graph and one-hop neighbor settings with proper density and bounded attribution assumptions. The authors claim that the max-a-posterior estimation consists of two types of non-linearity, a non-linear transformation of node attributes and a ReLU-activated feature aggregation from neighbors. The paper also verifies their theorem on synthetic and real-world datasets.  ", "questions": "1. Due to the CSBM setting, the paper can directly get the closed form solution equation (4) and give an analysis. I wonder is there any way to generalize the result, e.g., each node has its private connecting probability. \n2. Assumption 1 (Moderate Structural Information) means that the paper only considers a dense regime. Nowadays, community cluster detection works on sparse regime, e.g., S(p,q) = O(1/n) in [1]. Is the analysis still guaranteed in this regime? \n3. The non-linearity of a real dataset is hard to measure. Is there any way to metic the non-linearity in the dataset? Figure 4 seems related but still weak. \n\n[1] Li, Xiaodong, Yudong Chen, and Jiaming Xu. \"Convex relaxation methods for community detection.\" Statistical Science 36.1 (2021): 2-15.\n", "limitations": "The paper only considers a 1-hop neighbor. It would be better to consider a 2-hop neighbor. I believe that for a 2-hop neighbor the gap between linearity and non-linearity will be much larger. For the experiments, the scale problem can be solved by sub-sampling. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strongness: \n\n1. Contribution: As far as I know, this is the first paper systematically study non-linear properties in GNN. The paper provides a clear take-home message that the non-linearity only makes a contribution when the Attributed Information is sufficient (Theorem 2). The theorem is strong enough to support the authors’ claim and seems consistent with our intuition. The observation about the ReLU non-linearity part is insightful. It is closely connected to the empirical GNN. Remark 1 is insightful. The paper also verifies their theorem on synthetic and real-world datasets. They are consistent with the theorem.\n2. Writing: The paper has a clear motivation and good structure in Sections 3 and 4. The paper has all the necessary components, e.g., theorem and experiments. \n\nWeakness:\n\n1. The gap in Figure 1 right is not large enough. It would be better to plot with a larger x. \n2. The discussion about the non-linearity of node-attribute transformation is limited. It would be better to give one more example for the NN case, e.g., a two-layer network. \n\nClaim: I only checked a limited part of the proof. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept