$p$-Laplacian Based Graph Neural Networks
Authors: Guoji Fu
Peilin Zhao
Yatao Bian
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph neural networks
$p$-Laplacian
semi-supervised learning
node prediction

Abstract: Graph neural networks (GNNs) have demonstrated superior performance for semi-supervised node classification on graphs, as a result of their ability to exploit node features and topological information simultaneously. However, most GNNs implicitly assume that the labels of nodes and their neighbors in a graph are the same or consistent, which does not hold in heterophilic graphs, where the labels of linked nodes are likely to differ. Hence, when the topology is non-informative for label prediction, ordinary GNNs may work significantly worse than simply applying multi-layer perceptrons (MLPs) on each node. To tackle the above problem, we propose a new $p$-Laplacian based GNN model, termed as $^p$GNN, whose message passing mechanism is derived from a discrete regularization framework and could be theoretically explained as an approximation of a polynomial graph filter defined on the spectral domain of $p$-Laplacians. The spectral analysis shows that the new message passing mechanism works simultaneously as low-pass and high-pass filters, thus making $^p$GNNs effective on both homophilic and heterophilic graphs. Empirical studies on real-world and synthetic datasets validate our findings and demonstrate that $^p$GNNs significantly outperform several state-of-the-art GNN architectures on heterophilic benchmarks while achieving competitive performance on homophilic benchmarks. Moreover, $^p$GNNs can adaptively learn aggregation weights and are robust to noisy edges.

Under review as a conference paper at ICLR 2022
P-LAPLACIAN BASED GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) have demonstrated superior performance for semi- supervised node classification graphs, result of their ability to exploit node features and topological information simultaneously. However, most GNNs im- plicitly assume that the labels of nodes and their neighbors in graph are the same or consistent, which does not hold in heterophilic graphs, where the labels of linked nodes are likely to differ. Moreover, when the topology is non-informative for label prediction, ordinary GNNs may work significantly worse than simply applying multi-layer perceptrons (MLPs) on each node. To tackle the above prob- lem, we propose a new p-Laplacian based GNN model, termed as PGNN, whose message passing mechanism is derived from discrete regularization framework and could be theoretically explained as an approximation of a polynomial graph filter defined on the spectral domain of p-Laplacians. The spectral analysis shows that the new message passing mechanism works simultaneously as low-pass and high-pass filters, thus making "GNNs are effeetive on both homophilic and het- erophilic graphs. Empirical studies real-world and synthetic datasets validate our findings and demonstrate that PGNNs significantly outperform several state- of-the-art GNN architectures on heterophilic benchmarks while achieving compet- itive performance on homophilic benchmarks. Moreover, "GNNs can adaptively learn aggregation weights and robust to noisy edges.
INTRODUCTION
In this paper. we explore the usage of graph neural networks (GNNs) for semi-supervised node classification on graphs, especially when the graphs admit strong heterophily or noisy edges. Semi- supervised learning problems on graphs are ubiquitous in a lot of real-world scenarios, such as user classification in social media (Kipf & Welling, 2017), protein classification in biology (Velickovic al., 2018), molecular property prediction in chemistry (Duvenaud al., 2015), and many oth- ers (Marcheggiani & Titov, 2017; Satorras & Estrach, 2018). Recently, GNNs are becoming the de facto choice for processing graph structured data. They can exploit the node features and the graph topology by propagating and transforming the features over the topology in each layer and thereby learn refined node representations. A series of GNN architectures have been proposed, including graph convolutional networks (Bruna et al., 2014; Henaff et al., 2015; Defferrard et al., 2016; Kipf & Welling, 2017; Wu et al., 2019), graph attention networks (Velickovic et al., 2018; Thekumpara- mpil et al., 2018), and other representatives (Hamilton et al., 2017; Xu al., 2018; Pei al., 2020).
Most of the existing GNN architectures work under the homophily assumption, i.e. the labels of nodes and their neighbors in graph are the same or consistent, which is also commonly used in graph clustering (Bach & Jordan, 2004; von Luxburg, 2007; Liu & Han, 2013) and semi-supervised learning on graphs (Belkin et al., 2004; Hein, 2006: Nadler et al., 2009). However, recent stud- ies (Zhu et al., 2020: 2021; Chien et al., 2021) show that in contrast to their success on homophilic graphs, most GNNs fail to work well on heterophilic graphs, in which linked nodes are more likely to have distinct labels. Moreover, GNNs could even fail on graphs where their topology is not help- ful for label prediction. In these cases, propagating and transforming node features over the graph topology could lead to worse performance than simply applying multi-layer perceptrons (MLPs) on each of the nodes independently. Several recent works were proposed to deal with the heterophily is- sues of GNNs. Zhu et al. (2020) finds that heuristically combining ego-, neighbor, and higher-order embeddings improves GNN performance on heterophilic graphs. Zhu et al. (2021) uses a compat- ibility matrix to model the graph homophily or heterphily level. Chien al. (2021) incorporates

---

Under review as a conference paper at ICLR 2022
the generalized PageRank algorithm with graph convolutions to jointly optimize node feature and topological information extraction for both homophilic and heterophilic graphs. However, the problem of GNNs on graphs with non-informative topologies (or noisy edges) remains open.
Unlike previous works, we tackle the above issues of GNNs by proposing the discrete p-Laplacian based message passing scheme, termed p-Laplacian message passing. It is derived from a discrete regularization framework and is theoretically verified as an approximation of a polynomial graph filter defined the spectral domain of the p-Laplacian. Spectral analysis of p-Laplacian message passing shows that it works simultaneously as low-pass and high-pass filters' and thus is applicable to both homophilic and heterophilic graphs. Moreover, when p , 2. our theoretical results indicate that it can udaptively learn aggregation weights in terms of the variation of node embeddings on edges (measured by the graph gradient (Amghibech, 2003; Zhou & Schölkopf, 2005; Luo et al., 2010)), and work as low-pass or both low-pass and high-pass filters on node according to the local variation of node embeddings around the node (measured by the norm of graph gradients).
Based on p-Laplacian message passing, we propose new GNN architecture, called "GNN, to en- able GNNs to work with heterophilic graphs and graphs with non-informative topologies. Several existing GNN architectures, including SGC (Wu et al., 2019), APPNP (Klicpera et al., 2019) and GPRGNN (Chien et al., 2021). can be shown to be analogical to "GNN with p = 2. Our empin- cal studies real-world benchmark datasets (homophilic and heterophilic datasets) and synthetic datasets (cSBM (Deshpande et al., 2018)) demonstrate that "GNNS obtain the best performance on heterophilic graphs and competitive performance homophilic graphs against state-of-the-ae GNNs. Moreover, experimental results on graphs with different levels of noisy edges show that PGNNs work much more robustly than GNN baselines and even as well MLPs on graphs with completely random edges. Additional experiments (reported in Appendix E.5) illustrate that inter- grating "GNNs with existing GNN architectures (i.e. GCN (Kipf & Welling. 2017), JKNet (Xu et al., 2018)) can significantly improve their performance on heterophilic graphs. In conclusion, our contributions can be summarized as below:
(1) New methodologies. We propose p-Laplacian message passing and "GNN to adapt GNNs to heterophilic graphs and graphs where the topology is non-informative for label prediction. (2) Supe- rior performance. We empirically demonstrate that "GNNs is superior on heterophilic graphs and competitive on homophilic graphs against state-of-the-art GNNs. Moreover, PGNNs work robustly on graphs with noisy edges or non-informative topologies. (3) Theoretical justification. We theo- retically demonstrate that p-Laplacian message passing works as both low-pass and high-pass filters and the message passing iteration is guarantee to converge with proper settings. (4) New paradigm of designing GNN architectures. We bridge the gap between discrete regularization framework and GNNs, which could further inspire researchers develop new graph convolutions or message pass- ing schemes using other regularization techniques with explicit assumptions on graphs. Due to space limit, we defer the discussions on related work and future work and all proofs the Appendix.
2 PRELIMINARIES AND BACKGROUND
Notation. Let G = EV,E, W) be an undirected graph, where V = 21. NN. is the set of nodes, E C V/2 x V is the set of edges, W IR-NNN is the adjacency matrix and Wa, W j. W., 0 for [r,]] E E, Wa, = O, otherwise. Nr = {jhr.Jee denotes the set of neighbors of node i, DE NxN_ diag( 11, 1,,,,..... DN,N) denotes the diagonal degree matrix with D.,, = Σラ Wis. for I. f: + R and g E + IR functions defined on the vertices and edges of G. respectively, Fv denotes the Hilbert space of functions endowed with the inner product (f, f) Eiev (i). Similarly define Fg. We also denote by [K] = 21,2,... K), VK E N and we use Vx E d to denote the Frobenius norm of vector. |xx| = ||x||2 (2 1 x7)3/2
Problem Formulation. Given a graph g = (V, W), each node E V has a feature vector X which is the i-th row of X and a subset of nodes in G have labels from label set L = (1,.... L). The goal of sumi-super node classification on 9 is to learn a mapping M V + L and predict the labels of unlabeled nodes.
Note that if the low frequencies and high frequencies dominate the middle frequencies (the frequencies that around the cutoff frequency), we say that the filter works both low-pass and high-pass filters.
2

---

Under review as a conference paper at ICLR 2022
Homophily and Heterophily. The homophily heterophily of a graph is used to describe the relation of labels between linked nodes in the graphs. The level of homophily of a graph can be measured by H(()) Eiev [[i'))eN....v /[Mi]] (Pei et al., 2020; Chien et al., 2021), where Ki) denotes the number of neighbors of i E V that share the same label i and H(G) + corresponds strong homophily while H(G)
indicates strong heterophily. We say that a graph is a homophilic (heterophilic) graph if it has strong homophily (heterophily).
i. E V is defined to be a measurement of the variation of function f V - IR on the edge [i.
Graph Gradient. The graph gradient of an edge [t, ",,
Definition 1 (Graph Gradient). Given a graph G = EV,8) and function I V - R, the gruph gradient is an operator : Fv - Fe defined by
Wi (V.)(i)))) V Da.""
Wis f(1,, for all Da,,
f6)
(1)
For [i,j] & E, (V.) == O. The graph gradient of a function f at vertex i is defined to be fi( = ((Vf)(( I)), ..... (Vi), N))) and its Frobenius norm is given by | fii)ll
E (E ((t) '2, which measures the variation of f around node i. We measure the variation of f over the whole graph 9 by Sp(f) where it is defined to be
N N
N
N
WoJ DjJ (6) 16)
Wa, Dr. , for p 2 1, (2)
sp(f) = 2
ΣΣ
f(i)
==1
8= j=1
Note that the definition of S, here is different with the p-Dirichlet form in Zhou & Schölkopf (2005).
Graph Divergence. The graph divergence is defined to be the adjoint of the graph gradient: Definition (Graph Divergence). Given a graph G (V, E), and functions f V - IR g g R, the graph divergence is an operator div : Fe - Fv which satisfies (Vf.g) (f. divg).
(3)
The graph divergence can be computed by
Woj (o((E.5)) i().)))) Di.i
(divg)
Σ
(4)
J=1
Fig. 4 in Appendix E.1 gives a tiny example of illustration of graph gradient and graph divergence.
Graph p-Laplacian Operator. By the definitions of graph gradient and graph divergence, we reach the definition of graph p-Laplacian operator as below.
Definition (Graph p-Laplacian'), Given a graph G (V,E) and a function f + E. the graph p-Laplacian is an operator 4p Fv + Fv defined by
div([IV f[ll-V f), for 2 1. where |||11-2 is element-wise, i.e. [V(0)) (II 11) p-2 (E
Apf
(5)
P-2))
Substituting Eq. (1) and Eq. (4) into Eq. (5), we obtain
Wis (VDD))))))
Wir Di.
Win r(i)
(a,)
D..:
(v
f(i) V Das
(6)
The graph p-Laplacian is semi-definite: (f.A,f) = Ss,()) 2 0 and we have
(S) (()))))().
(7)
0f
When p 2, A2 is refered as the ordinary Laplacian operator and AS I D D-D-1/WD-12
and when p- = 1, A refered as the Curvature operator and A == 1 (IV Note that Laplacian 2 is a linear operator, while in general for p * 2, p-Lalaacian is nonlinear since Ap(af) # (f) for a E R.
2f can be a vector function: V.V IR for some e E N and here we use f V + R for better illustration. Note that the definition adopted is slightly different with the one used in Zhou & Schölkopf (2005) where Ip-2 is not element-wise and the used in some literature such as Amghibech (2003); Bühler & Hein W., (2009), where (i) E/ Di, ( SG) (f(i) f()) for p and p 1 is not allowed.
3

---

Under review as a conference paper at ICLR 2022
3 P-LAPLACIAN BASED GRAPH NEURAL NETWORKS
In this section, we derive the p-Laplacian message passing scheme from p-Laapaccian regularization framework and present "GNN, a new GNN architecture developed upon the new message passing scheme. We theoretically characterize how p-Laplacian message passing adaptively learns aggre- gation weights and profits "GNN for being effective on both homophilic and heterophilic graphs.
3.1 P-LAPLACIAN REGULARIZATION FRAMEWORK
Given undirected graph G (V. and signal function with c (c E N) channels f - R. X = (X] X E R with X,, E R R [N] denoting the node features of g and F
Rx be a matrix whose 7th row vector F,; E gixe, i [AV] represents the function value of f the i-th vertex in G. We present p-Laplacian regularization problem whose cost function is defined to be
N
F
arg min C(F) == arg F
arg min Sp(F) + Σ F L.:
X
F
where μ E (0, o)) The first term of the right-hand side in Eq. (8) is measurement of variation of the signal over the graph based on p-Laaacci... As we will discuss later, different choices of p result in different smoothness constraint the signals. The second term is the constraint that the optimal signals F should not change too much from the input signal X, and μ provides a trade-off between these two constraints.
Regularization with = 2. When p = 2, the solution of Eq. (8) satisfies A2F' + 1( - X) = and we can obtain the closed form (Zhou et al., 2003; Zhou & Schölkopf, 2005)
F
μu( ( + p
Then, we could use the following iteration algorithm to get an approximation of Eq. (9):
((++1) - 1122p(k) + 3X,
(10)
where l represents the iteration index, I+ and , - =1 a. The iteration converges to closed-form solution k goes to infinity (Zhou et al., 2003; Zhou & Schölkopf, 2005). We could relate the the result here with the personalized PageRank (PPR) (Page et al., 1999; Klicpera et al.,
2019) algorithm (proof defered to Appendix D.1):
Theorem 1 (Relation to personalized PageRank (Klicpera et al., 2019)). n(A2 + =IN) in the closed form solution of Eq. (9) is equivalent to the personalized PageRank matrix.
Regularization with p > 1. For porp3 By Eq. (6) we have that, for all E [N].
> 1, the solution of Eq. (8) satisfics p + +2u(F= - X)= = O.
Σ
Was II IKVF")
1
Fi
Fj
+
2p p
(F x.,)
1=1 DD.
Vii,
VDJs
Based on which we can construct a similar iterative algorithm to obtain a solution (Zhou & Schölkopf, 2005):
M
F (++1)
a,
(K)
Σ
(b) +
(()) X
for all i [N],
(11)
1=1
with (RR) E NNN (k) diag(a (K)
N. (xx)
(K)
diag( 111..........................(.. ....... ( updated by
$ = Wis
V
Wi.
Di.3
F
W3 Das
(())
j:
for all i E [N],
(12)
N
M(A)
(k)
0, = 1/
+
241
((k) =
2μ 0g
for all i E [N],
(13)
Disi
Note that in Eq. (12), when
Wis (k) Dr.
W
(k)
= 0. we set M(K) = It is easy to see
1,
D).
j
that Eq. (10) is the special cases of Eq. (14) with p 2.
4

---

Under review as a conference paper at ICLR 2022
1). For porp=1 =p= when f is real-valued function (c = 1), A1f is step function, which could make the stationary condition of the objective function Eq. (8) become problematic. Additionally.A1 f is not continuous at [IV (). allowed when f is a real value function. On the other hand, note that there is a Frobenius norm in Apf. When f is a vector-valued function (c > 1), the step function in A only exists on the axes. The stationary condition will be fine if the node embeddings F are not a matrix of vectors that has only one non-zero element, which is true for many graphs. p I may work for these graphs. Overall, we suggest to use p > 1 in practice but 1 may work for graphs with multiple channel signals as well. We conduct experiments for p > (e.g., p = 1.5, 2, 2.5) and p 1 in Sec. 5.
Remark (Discussion on p
0. Therefore, p 1 is not
3.2 P-LAPLACIAN MESSAGE PASSING AND GGNN ARCHITECTURE
p-Laplacian Message Passing. Rewrite Eq. (11) in matrix form we obtain
p(++1) = (k) D 1/2 M ( D - 1/2p(() + +,300x
(14)
Eq. (14) provides a new message passing mechanism, named p-Laplacian message passing.
Remark 2. aD aD-1/2MD 1/2 in Eq. (14) can be regarded as the learned aggregation weights at each step for message passing. suggests that p-Laplacian message passing could adaptively tune the aggregation weights during the course of learning, which will be demonstrated theoretically and empirically in the sequel of this paper. 3X in Eq. (14) can be regarded as a residual unit, which helps the model escape from the oversmoothing issue (Chien et al., 2021).
We present the following theorem to show the shrinking property of p-Laplacian message passing.
Theorem (Shrinking Property of p-Laplacian Message Passing). Given a graph 9 = (V,E, W)
with node features X, ((8), F((), M (k) are updated accordingly to Equations (11) to (13) for k 0, 1,..,,, K and P(O) = X. Then there exist some positive real value p. 0 which depends on X, G.p and p > 1 such that
C,(p(t+1) S (F(()))
Proof see Appendix D.2. Thm. 2 shows that with some proper positive real value y and p > 1, the loss of the objective function Eq. (8) is guaranteed to decline after taking one step p-Laplacian message passing. Thm. 2 also demonstrates that the iteration Equations (11) to (13) is guaranteed to converge for > 1 with some proper y which is chosen depends on the input graph and p.
PGNN Architecture. We design the architecture of PGNNs using p-Laplacian message passing. Given node features X E R-Nxe, the number of node labels L, the number of hidden units h, the maximum number of iterations K, and M, a, and B updated by Equations (12) and (13) respec- tively, we give the "GNN architecture as following:
F 00) ReLU(XO(')
(15)
F (k+1) a D 1/2 ( 10/pp(())) + (()) ==0,1,... K-
(16)
Z = softmax (F (())))
(17)
where Z E RNL is the output propbability matrix with Zı,j is the estimated probability that the label at node i E [N] is E [I.] given the features X and the graph G. ())) E Reex and ( e
L are the first- and the second-layer parameters of the neural network, respectively.
Remark (Connection to existing GNN variants). The message passing scheme of "GNNS is dif- ferent from that of several GNN variants (say, GCN, GAT, and GraphSage), which repeatedly stack message passing layers. In contrast, it is similar with SGC (Wu et al., 2019), APPNP (Klicpera et al., 2019), and GPRGNN (Chien et al., 2021). SGC is approximation to the closed-form in Eq. (9) (Fu et al., 2020). By Thm. I, it is easy to see that APPNP. which uses PPR to propagate the node embeddings, is analogical to "GNN with p 2. termed as 2.0 2.O.NN APPNP and 2.O work analogically and effectively on homophilic graphs. 2.0 can also work effectively on heterophilic graphs by letting (2) be negative. However, APPNP fails on heterophilic graphs as its PPR weights
5

---

Under review as a conference paper at ICLR 2022
are fixed (Chien et al., 2021). Unlike APPNP, GPRGNN, which adaptively learn the generalized PageRank (GPR) weights, works similarly to 2.0 GNN on both homophilic and heterophilic graphs. However, GPRGNN needs more supervised information in order to learn optimal GPR weights. On the contrary, PGNNs need less supervised information to obtain similar results because ((2) acts like hyperplane for classification. "GNNs could work better under weak supervised information. Our analysis is also verified by the experimental results in Sec. 5.
We also provide an upper- bounding risk of PGNNs by Thm. in Appendix C.1 to study the effect of the hyperparameter jr on the performance of "GNNs. Thm. 4 shows that the risk of PGNNs is upper- bounded by the sum of three terms: the risk of label prediction using only the original node features X, the norm of p-Laplacian diffusion on X, and the magnitude of the noise in X. μ controls the
trade-off between these three terms. The smaller μu, the more weights on the p p-Laplacian diffusion term and the noise term and the less weights on the the other term and vice versa.
4 SPECTRAL VIEWS OF P-LAPLACIAN MESSAGE PASSING
In this section, we theoretically demonstrate that p-Laplacian message passing is an approximation of a polynomial graph filter defined on the spectral domain of p-Laplacian. We show by spectral analysis that p-Laplacian message passing works simultaneously as low-pass and high-pass filters.
p- p-Eigenvalues and p-Eigenvectors of the Graph p-Laplacian. We first introduce the defini- tions of p-eigenvalues and p-eigenvectors of p-Laplacian. Let dp R + R defined as Φp(u) ||u||- uu for u E R, u * O. Note that Φ2(u) = u. For notational simplicity, we denote by for (U.))........
(u) U NNN and U., E RN the 7th column vector of U.
(p(UN)) for u E RN and (U)
Definition 4 (p-Eigenvector and p-Eigenvalue). vector u E R. is a p-eigenvector of Ap if satisfies the equation
(A,u), - (w,), for all i E [N],
where X E IR is real value referred p-eigenvalue of Ap associated with the p-eigenvector u. Definition 5 (p-Orthogonal (Luo, Huang, Ding, and Nie, 2010)). Given two vectors RVV with V # we call that u and v is p-orthogonal if (u) dp(v) EN (p(u:)o)()))
Luo et al. (2010) demonstrated that the preggenvectors of Ap are p-orthogonal to each other (see Thm. 5 in Appendix C.2 for details). Therefore, the space spanned by the multiple p-eigenvectors of Ap is p-orthogonal. Additionally, we demonstrate that the p-cigen-decomposition of Ap is given by: A, (U)AA, (U)) (see Thm. 6 in Appendix C.3 for details), where U is matrix of p-eigenvectors of A, and A is a diagonal matrix in which the diagonal is the p-eigenvalues of Ap.
Graph Convolutions based on p-Laplacian. Based on Thm. 5, the graph Fourier Transform f of any function f on the vertices of G can be defined as the expansion of f in terms of + (UU) where U is the matrix of peigennvectors of Ap: f = & (U) f. Similarly, the inverse graph Fourier transform is then given by: f = p (U)f. Therefore, signal X E NNx being filtered by spectral filter ge can be expressed formally as: ge * X = 4 (U))a (U) X, where A denotes diagonal matrix in which the diagonal corresponds to the p-eigenvalues {Ar)
TX
of Ap and go(A) ()) denotes a diagonal matrix in which the diagonal corresponds to spectral filter coefficients. Let go be polynomial filter defined as go Ek=0 fa-Y,, where the parameter θ = [d...... 0x-1] R k is a vector of polynomial coefficients. By the p-eigen-decompen
of LLaplaciin,, we have
K-1
K-1
go * X
Σ
(
(U) x
Σ 0
(18)
K=
Theorem 3. The K K-step p- L-aplaccian message passing is a K-order polynomial approximation to the graph filter given by Eq. (18).
Proof see Appendix D.3. Thm. 3 indicates that Lapplaciinn message passing mechanism is implicitly polynomial spectral filter defined on the spectral domain of p-Laplacian.

---

Under review as a conference paper at ICLR 2022
Spectral Analysis of p-Laplacian Message Passing. Here, we analyze the spectral propecties of p- p-Laplacian message passing. We can approximately view p-Laplacian message pasing as a filter of
a linear combination of K spectral filters g( ,()))))(A)))))) (())))))) ,.... g( ())(K-) with each spectral filter
W - V W F F defined to be g(A)(k) == (a 1001///-///2)) where Mr,, = Wi Dr.
for j E [N] and F is the matrix of node embeddings. We can study the properties of p-L.aplacian message passing by studying the spectral properties of -DD-1/2MD-1 -1/2 as given below.
Proposition 1. Given a connected graph 9 - (V,E,W) with node embeddings F and the p- Laplacian Ap with its p-eigenvectors { J==0,1...NN-1 and the p-eigenvalues (N.. DJJ/? Let 9p (p(Ai-1) == aziii Ej D 1/2 Ma. DJJ 1/2 for E [NT] be the filters defined on the spectral domain
of Ap. where Mi = Wa FV JD1 (V.)( is the graph gradient of the edge between node and j and f(iill is the norm of graph gradient at i. N, denotes the number of edges connected to Nuii min (Na and k- arg max,((1y) // (EMNANNNNM then
1. When p- = 2, 9p (Ai-1) works as both low-pass and high-pass filters.
2. When p > if ((+) S 2(e--1)(e-2), 9p (Ai-1) works as both low-pass and high-pass
filters on node and 9p (A<-1) works as low-pass filters on i when [[V 2 20e-1)/(p2))
3. When 1 S p < 2, 1 0 <
|V(II I (o--2) (0(2s-1) works as low-pass filters on node i and gp (x-))) works as both low-pass and high-pass filters on i when
|VS(II 2 (2VNA)
2(p-2) Specifically, when p = 1, N2 can be replaced by Nman-
Proof see Appendix D.7. Proposition 1 shows that when p * 2, p-Laplacian message passing adaptively works as low-pass or both low-pass and high-pass filters on node i in terms of the degree of local node embedding variation around i, i.e. the norm of the graph gradient [[V]( at node i. When p = 2. p-Laplacian message passing works as both low-pass and high-pas filters on node i regardless of the value of [i)]. When p > 2. p-Laplacian message passing works as low- pass filters on node i for large [[V)( and works as both low-pass pass and high-pass filters for small [V)(( Therefore, PGNNS with p > can work very effectively on graphs with strong homophily. When 1 S < 2, p-Laplacian message passing works as low-pass filters for small [V]()] and works as both low-pass and high-pass filters for large | Thus, PGNNs with 1 S p < 2 can work effectively on graphs with low homophily, i.e. heterophilic graphs. The results here confirms our analysis of the aggregation weights of p-Laplacian message passing presented in Thm. 2.
EMPIRICAL STUDIES
In this section, we empirically study the effectiveness of FGNNs for semi-supervised node classifica- tion using and real-world benchmark and synthetic datasets with heterophily and strong homophily. The experimental results are also used to validate our theoretical findings presented previously.
Datasets and Experimental Setup. We use seven homophilic benchmark datasets: citation graphs Cora, CiteSeer, PubMed (Sen et al., 2008), Amazon co-purchase graphs Computers, Photo, coauthor graphs CS, Physics (Shchur et al., 2018), 8), and six heterophilic benchmark datasets: Wikipedia graphs Chameleon, Squirrel (Rozemberezki et al., 2021), the Actor co-occurrence graph, webpage graphs Wisconsin, Texas, Cornell (Pei et al., 2020). The node classification tasks are conducted in the transductive setting. Following Chien et al. (2021), we use the sparse splitting (2.5% /2.6% 5%/95%) and the dense splitting (60% 22666/0%/222 into training/ validation inliddationteesting testing sets, respectively. Dataset statistics and their levels of homophily are presented in Appendix E.
to randomly split the homophilic and heterophilic graphs
Baselines. We compare "GNN with seven models, including MLP, GCN (Kipf & Welling, 2017), SGC (Wu et al., 2019). GAT (Velickovic et al., 2018), JKNet (Xu et al., 2018), APPNP (Klicpera et al., 2019), GPRGNN (Chien et al., 2021). We use the Pytorch Geometric library (Fey & Lenssen, 2019) to implement all baselines except GPRGNN. For GPRGNN, we use the code released by the a The details of hyperparameter settings are deferred to Appendix E.3.
httpps://gi thub. com www..oo//jaaaaac jiahhao201 6/ /PRGNNN
7

---

Under review as a conference paper at ICLR 2022
Table I: Heterophilious results. Averaged accuracy (%) for 100 runs, Best results outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold.
Method
Chameleon
Squirrel
Actor
Wisconsin
Texas
Cornell
MLP
48.02
33.80
39.68
93.56
79.50
80.30
GCN
34.54+2.78 25.28
31.28+2.04
61.93+3.00
56.54_17.02
51.36+2..9
SGC
34.7624.55 25.4921.63
30.9823.60
66.9442.58
59.9919.95
44.39
GAT
45.1622.10 31.4120.98
34.11+1.25
65.6446.29
56.41=13.01
43.9447..3
JKNet
33.28+3.59 25.82+1.68
29.77+-2.61
61.08+33.71
59.65=12.62
55.344+4.48
APPNP
36.18
26.8541.48
31.26422.2
64.59
82.90+o.us
66.47+9.34
GPRGNN
43.67
31.27
36.63
88.54444.9
80.74
78.95
GNG
48.86
33.75 + 1.50
40.62
2.
95.37 #2.06
84.0647.41
82.16+8.62
1. GNN
48.74
33.33+1.45
40.35
95.24
84.4647.77
78.477+6.87
1.002
1.35
GNN
48.77 11.87
33.60
40.07
91.15+2.76
87.9626.22
72.04
2.6 GNN
48. 48.80 21.77 33.79
+1.45
39.80g1.31
87.08
83.01
70.31
Superior Performance on Keal-World Heterophilic Datasets. The results on homophilic bench- mark datasets are deferred to Appendix F.I, which show that "GNNs obtains competitive perfor- mance against of-te-of-the-rr GNNs on homophilic datasets. Table 1 summarizes the results on heterophilic benchmark datasets. Table I shows that PGNNs significantly dominate the baselines all heterophilic graphs except the Texas dataset. For Texas, 2.0 GNN is the best. We also observe that MLP works very well and significantly outperforms most GNN baselines, which indicates that the graph topology is not informative for label predic- tion on these heterophilic graphs. Therefore, propagating and transforming node features over the graph topology could lead worse performance than MIP. Unlike ordinary GNNs, PGNNS can adaptively learn aggregation weights and ignore edges that are not informative for label prediction and thus could work better. It confirms our theoretical findings presented in previous sections. Note that GAT can also learn aggregation weights, i.c the attention weights. However, the aggregation weights learned by GAT are significantly distinet from that of "GNNs, as we will show following.
and GNN obtains the best performance
Computers LRO Asc 35.2%)
unfform
LOCMN AAc 85.24%)
FIGNN (Ace 85.00%)
GXT 12,7780
Wisconsin
013137
enbray
Figure 1: Aggregation weight entropy distribution of graphs. Low entropy means high degree of concentration, vice versa. An entropy of zero means all aggregation weights are on one source node.
Interpretability of the Learned Aggregation Weights of PGNNs. We showcase the interpretabil- Mr, 1/2 of PGNNs by studying its entropy
ity of the learned aggregation weights Dr, 1/2 distribution, along with the attention weights of GAT on real-world datasets. Denote {Ar, IseN, as the aggregation weights of node and its neighbors. For GAT, (ALj)jeN, are referred as the attention weights (in the first layer) and for PGNNs are az, 11/2/ "., 1/22 For any node i, (Ai, forms a discrete probability distribution over all its neighbors with the entropy given by H ((AA))EN = - -EEN. As,j lA,,).,)). Low entropy means high degree of concentration and vice versa. An entropy of zero means all aggregation weights or attentions are on one source node. The uniform distribution has the highest entropy of log(D..). Fig. reports the results on Com- puters, Wisconsin and we defer more results on other datasets to Appendix F.2 due to space limit. Fig. 1 shows that the aggregation weight entropy distributions of GAT and PGNNs on Computers (homophily) are both similar to the uniform case. It indicates the original graph topology of Com- puters is very helpful for label prediction and therefore GNNs could work very well on Computers. However, for Wisconsin (heterophily), the entropy distribution of PGNNs is significantly different from that of GAT and the uniform case. Most entropy of "GNNs is around zero, which means that most aggregation weights are on one source node. It states that the original graph topology of Wisconsin is not helpful for label prediction, which explains why ML. works well Wisconsin.
8

---

Under review as a conference paper at ICLR 2022
Computers
Wisconsin
100
MLP
100
GCN
SGC
Accuracy (8)
GAT
Alquuree
70
APPNP
APPMP
GPRGNN
GPRGNN
10-GNN
15-
20-GNN
40
20-6NN
0.25
0.5
25-GNN
25-GNN
Figure Averaged accuracy (%) on graphs with noisy edges for 20 runs. Best view in colors.
On the contrary, the entropy distribution of GAT is similar to the uniform case and therefore GAT works similarly to GCN and is significantly worse than " "GNNs on Wisconsin. Similar results can be observed on the experiments on more datasets in Appendix F.2.
Results on cSBM Datasets. We exam the performance of FGNNs on heterophilic graphs whose topology is informative for label pre- diction using synthetic graphs generated by
cSBM sparse
MLP
100
50
56C
cSBM (Deshpande et al., 2018) with E (-1,-0.75..... 1,. We use the same settings of cSBM used in Chien et al. (2021). Due to the space limit, we refer the readers to Chien et al. (2021) for more details of cSBM dataset. Fig. 2 reports the results on cSBM using sparse splitting (for results on cSBM with dense split- ting see Appendix F.3). Fig. 2 shows that when ó < -0.5 (heterophilic graphs), 2.ºNNN obtains the best performance and "GNNs and GPRGNN significantly dominate the others. It validates the effectiveness of PGNNs on het- erophilic graphs Moreover, 2.GNNN works better than GPRGNN and it again confirms that GNO is more superior under weak supervision (2.5% training rate), as stated in Remark 3. Note that GNN and 1.5 GNN are not better than 2." the reason could be the iteration al- gorithms Eq. (11) with p 1, 1.5 are not as stable as the one with p = 2. When the graph topology is almost non-informative for label prediction (ø- - -0.25, 0), The performance of PGNNs is close to MIP and they outperform the other baselines. Again, it validates that "GNNs can erase non- informative edges and work as well as MLP and confirms the statements in Thm. 4. When the graph is homophilic (ø 2 0.25), GNN is the best on weak homophilic graphs (ø 0.25, 0.5) and PGNNs work competitively with all GNN baselines strong homophilic graphs (ø 0.75).
GAT
Accuracy
JKNet
70
APPNP
GPRGNN
60
1.0GN
50
1560M
20GMN
-.5
0.25
Figure 2:
Averaged accuracy (%) on cSBM (sparse split) for 20 runs. Best view in colors.
Results on Datasets with Noisy Edges. We conduct experiments to evaluate the performance of PGNNs graphs with noisy edges by randomly adding edges to the graphs and randomly remove the same number of original edges. We define the random edge rate iments are conducted on homophilic datasets (Computers, Photo, CS, Physics) and 2 heterophilic datasets (Wisconsin, Texas) with r = 0.25, 0.5, 1. Fig. 3 reports the results on Computers, Wiscon- sin and we defer more results to Appendix F.4. Fig. 3 shows that "GNNs significantly outperform all baselines. Specifically. 1.5 GNN obtains the best performance on Computers, and L.5GNN and 2.OGNN even work as well as MLP on Computers with completely random edges (r 1). For Wisconsin, 1.ºGNN is the best, and L."GNN and 1.1GNN significantly dominate the others. We also observed that APPNP and GPRGNN, whose architectures are analogical to 2.NGNN, also work bet- ter than other GNNs. Nevertheless, they are significantly outperformed by "GNNs overall. Similar results can be observed in the experiments conducted on more datasets as presented in Appendix F.4.
#random edges The exper- #all edges
CONCLUSION. We have addressed the problem of generalizing GNNs to heterophilic graphs and graphs with noisy edges. To this end, we derived a novel p-Laplacian message passing scheme from discrete regularization framework and proposed new 'GNN architecture. We theoretically demonstrate our method works as low-pass and high-pass filters and thereby applicable to both homophilic and heterophilic graphs. We empirically validate our theoretical results and show the advantages of our methods on heterophilic graphs and graphs with non-informative topologies.
9

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
In order to ensure reproducibility, we have made the efforts in the following respects: (1) Provide sampled code the supplementary material; (2) Provide self-contained proofs of the main claims in Appendices C and D; (3) Provide more details on experimental configurations in Appendix E and experimental results in Appendix All the datasets are publicly available as described in the main text. We will fully release our training and evaluation code, as well as our train/validation//es splits.
REFERENCES
Sami Abu-El-Haijj Bryan Perozzi, Rami Al-Rfou, and Alexander A. Alemi. Watch your step: Learning node embeddings via graph attention. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neu- ral Information Processing Systems 31, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9198-9208, 2018.
Sami Abu- El- Ea-Haija, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-GCN: multi-scale graph convolution for semi-supervised node classification. In Amir Globerson and Ricardo Silva (eds.), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, Tel Aviv, Israel, July 22-25, 2019, volume 115 of Proceedings of Machine Learning Research, pp- 841-851. AUAI Press, 2019.
S. Amghibech. Eigenvalues of the discrete p-laplacian for graphs. Ars Combinatoria, 67:283-302, 2003.
James Atwood and Don Towsley, Diffusion-convoluttinaa neural networks. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29, NeurIPS 2016, December 5-10, 2016, Barcelona, Spain, pp. 1993-2001, 2016.
Francis Bach and Michael Jordan. Learning spectral clustering, Advances in Neural Information Processing Systems, NIPS 2004, 16(2):305-312, 2004.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst. Alvaro Sanchez-Gonzale Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1 806.01261, 2018.
Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for laplacian- based manifold methods. Journal of Computer and System Sciences, (188):1299-1388 2008
Mikhail Belkin, Irina Matveeva, and Partha Niyogi. Regularization and sumi-supervised learning on large graphs. In The 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004, volume 3120, pp. 624-638, 2004.
Misha Belkin, Partha Niyogi, and Vikas Sindhwani. On manifold regularization. In Robert G. Cow- ell and Zoubin Ghahramani (eds.), Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, AISTATS 2005, Bridgetown, Barbados, January 6-8, 2005. Society for Artificial Intelligence and Statistics, 2005.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally con- nected networks on graphs. In The 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, 2014.
Thomas Bühler and Matthias Hein. Spectral clustering based the graph p-laplacian. In An- drea Pohoreckyj Danyluk, Léon Bottou, and Michael L. Littman (eds.). Proceedings of the 26th Annual International Conference Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pp. 81-88. ACM, 2009.
10

---

Under review as a conference paper at ICLR 2022
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018. Conference Track Proceedings, 2018.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems 29, NeurIPS 2016, December 5-10, 2016, Barcelona, Spain, pp- 3837-3845, 2016.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8590- 8602, 2018.
David Duvenaud, Dougal Maclaurin, Jorge Iparaarr-,,r Rafael othy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances in Neural Informatioon Processing Systems 28, NeurIPS 2015 December 7-12, 2015, Montreal, Quebec, Canada, pp. 2224-2231 2015.
Tim-
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. CoRR, abs/1903.02422 2019.
Guoji Fu, Yifan Hou, Jian Zhang, Kaili Ma, Barakeel Fanseu Kamhoua, and James Cheng. Under- standing graph neural networks from graph signal denoising perspectives. CoRR, abs/2006.04386, 2020.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks IEEE Transactions Signal Processing, 68:5680-5695, 2020.
Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational lim- its of graph neural networks. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3419 3430. PMLR, 2020.
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. In Ad- vances in Neural Information Processing Systems 17, NIPS 2004, December 13-18, 2004, Van- couver, British Columbia, Canada], pp. 529-536, 2004.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems 30, NeurlPS 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1024-1034, 2017.
Matthias Hein. Uniform convergence of adaptive graph-base regularization. In The 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006, volume 4005, pp. 50-64, 2006.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. CoRR, abs/1506.05 161,,, 2015.
Weihua Hu, Mauhiis Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson. Combining label propagation and simple models out-performs graph neural networks. In 9th International Confer- ence on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenRe- view.net, 2021.
11

---

Under review as a conference paper at ICLR 2022
Thomas N. Kipf and Max Welling. Semi Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Guohao Li, Matthias Mülerr, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 November 2, 2019, pp. 9266-9275, IEEE, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In T'irty-Second AAAI Conference on Artificial Intelligence, AAAI 2018, New Orleans, Louisiana, USA, February 2-7, 2018, pp. 3538-333 3345, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OeenReview.net. 2019.
Fei Liu, Sounak Chakraborty, Fan Li, Yan Liu, and Aurelic C Lozano. Bayesian regularization via graph laplacian. Bayesian Analysis, 9(2):449 474, 2014.
Jialu Liu and Jiawei Han. Spectral clustering. In Charu C. Aggarwal and Chandan K. Reddy (eds.), Data Clustering: Algorithms and Applications, pp. 177-200. CRC Press, 2013.
Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Inter- national Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp.
PMLR, 2021.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Dijun Luo, Heng Huang, Chris H. Q. Ding, and Feiping Nie. On the eigenvectors of p-laplacian. Machine Learning, 81(1):37-51, 2010.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In Martha Palmer, Rebecca Hwa, and Sebastian Riedel (eds.). Proceedings of the 2017 Conference Empirical Methods in Natural Language Processing, EMNLP 2017, Copenhagen, Denmark, September 9-11, 2017, pp. 1506-1515. Association for Computational Linguistics, 2017.
Boaz Nadler, Nathan Srebro, and Xueyuan Zhou. Semi-supervised learning with the graph laplacian: The limit of infinite unlabelled data. Advances in Neural Information Processing Systems, NIPS 2009, 1230033-3338 2009.
Partha Niyogi Manifold regularization and sumi-supervised learning: some theoretical analyses. Journal of Machine Learning Research, 14(1): 2013.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters.
CoRR, abs/1 905.09550, 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Lawrence Page. Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representattinss ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. 2020.
12

---

Under review as a conference paper at ICLR 2022
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scak attributed node embedding. Journal of Complex Networks, 9(2), 2021.
Victor Garcia Satorras and Joan Bruna Estrach. Few-shot learning with graph neural networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Truck Proceedings. OpenReview.net, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-106 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, abs/181 10.s/181.00586.. 2018.
Vikas Sindhwani, Partha Niyogi. Mikhail Belkin, and Sathiya Keerthi. Linear manifold regulariza- tion for large scale semi-supervised learning. In Proceedings of the 22nd ICML Workshop on Learning with Partially Classified Training Data, volume 28, 2005.
Dejan Slepcev and Matthew Thorpe. Analysis of p-laplacian regularization in semi-supervised learn- ing. CoRR, abs/1707 ..2.166222222 2017.
Alexander Smola and Risi Kondor. Kernels and regularization on graphs. In Bernhard Schölkopf and Manfred K. Warmuth (eds.), Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Computer Science, pp. 144-158. Springer, 2003.
Kiran Koshy Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. CoRR, abs/1880.03743 2018.
Laurens der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(86) 26099,2265,222 2008.
Jesper E. van Engelen and Holger H. Hoos. A survey on semi-supervised learning. Machine Learn- ing, 109(2):373-440) 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, 2018
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. In The 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1539-1548, 2019.
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395 416, 2007.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propa- gation. CoRR, abs/2002.06755, 2020.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 6861- 1871,2019
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning System, 32(1): ):4 24, 2021.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA. May 6-9, 2019. OpenReview.net, 2019.
13

---

Under review as a conference paper at ICLR 2022
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stock- holm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp- 1449-5455 PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural net- works? In 7th International Conference on Learning Representations, ICLR 2017 New Orleans, LA, USA, May 6-9, 2019, Conference Track Proceedings, 2019.
Zhitao Ying. Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 4815-4815, 2018.
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Process- ing Systems 32, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 9240-9251, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRe- view.net, 2020.
Dengyong Zhou and Bernhard Schölkopf. Regularization on discrete spaces. In The 27th DAGM Symposium, Vienna, Austria, August 31 September 2, 2005, volume 3663, pp. 361-368 2005.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Sebastian Thrun, Lawrence K. Saul, and Bernhard Schölkopf (eds.), Advances in Neural Information Processing Systems 16, NIPS 2003, December 8-13, 2003, Vancouver and Whistler, British Columbia, Canada], pp. 321-328. MIT Press, 2003.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changeheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020.
Xueyuan Zhou and Mikhail Belkin. Semi-supervised learning by higher order regularization. In Geoffrey J. Gordon, David B. Dunson, and Miroslav Dudík (eds.), Proceedings of the Fourteenth International Conference on Arlificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11-13, 2011, volume 15 of JMLR Proceedings, pp. 892-900. JMLR.org. 2011.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems 33, NeurlPS 2020, December 6-12 12, 2020, virtual, 2020.
Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph neural networks with heterophily. In 35th AAAI Conference on Artificial Intelli- gence, AAAI 2021, Virtual Event, February 2-9, 2021, pp. 11168 11168-11176. AAAI Press, 2021.
Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaus- sian fields and harmonic functions. In Tom Fawcett and Nina Mishra (eds.), Machine Learning, Proceedings of the Twentieth International Conference, ICML 2003, August 21-24, 2003, Wash- ington, DC, USA, pp. 912-919. AAAI Press, 2003.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinform., 33(14):1190-i198 2017.
14

---

Under review as a conference paper at ICLR 2022
Appendix
CONTENTS
Related Work
16
B Discussions and Future Work
17
Additional Theorems
18
C.1 Theorem 4
Risk of "GNN)
18
C,2 Theorem 5 (p-Orthogonal Theorem (Luo et al., 2010))
C.3 Theorem 6 Er-Eigen-Decompond of 4p)
18
C,4 Theorem (Bounds of p-Eigenvalues)
19
Proof of Theorems
19
D.I Proof of Theorem
19
D.2 Proof of Theorem 2
20
D.3 Proof of Theorem
22
D.4 Proof of Theorem 4
24
D.5 Proof of Theorem
25
D.6 Proof of Theorem 7
25
D.7 Proof of Proposition
27
Dataset Statistics and Hyperparameters
29
E.1
Illustration of Graph Gradient and Graph Divergence
29
E,2 Dataset Statistics
................................
29
E,3
Hyperparameter Settings
Additional Experiments
F.1
Experimental Results on Homophilic Benchmark Datasets
31
F2
Experimental Results of Aggregation Weight Entropy Distribution
31
F3
Experimental Results on cSBM
34
F.4
Experimental Results Graphs with Noisy Edges
34
E5
Experimental Results Intergrating PGNNs with GCN and JKN
36
F66
Experimental Results of PGNNs PPI Dataset for Inductive Learning
37
F7
Experimental Results PGNNs on OGBN arXiv Dataset
37
F88
Running Time of PGNNs Experimental Results on Benchmark Datasets for 64 Hidden Units
38
F.9
38
F110
Training Curves for Visualization Results of Node Embeddings
39
F11
40
15

---

Under review as a conference paper at ICLR 2022
A RELATED WORK
Graph Neural Networks. Graph neural networks (GNNs) are a variant of neural networks for graph-structured data, which can propagate and transform the node features over the graph topol- ogy and exploit the information in the graphs. Graph convolutional networks (GCNs) are one type of GNNs whose graph convolution mechanisms or the message passing schemes were mainly in- spired by the field of graph signal processing. Bruna et al. (2014) defined a nonparametric graph filter using the Fourier coefficients. Defferrard et al. (2016) introduced Chebyshev polynomial to avoid computational expensive eigen-decomposstion of Laplacian and obtain localized spectral fil- ters. GCN (Kipf & Welling, 2017) used the first-order approximation and reparameterized trick to simplify the spectral filters and obtain the layer-wise graph convolution. SGC (Wu et al., 2019) further simplify GCN by removing non-linear transition functions between each layer. Chen et al. (2018) propose importance sampling design an efficient variant of GCN. Xu et al. (2018) 1) explored a jumping knowledge architecture that flexibly leverages different neighborhood ranges for each node to enable better structure-aware representation. Atwood & Towsley (2016); Liao et al. (2019); Abu-EI-Haija et al. (2019) exploited multi-scale information by diffusing multi-hop neighbor in- formation over the graph topology. Wang & Leskovec (2020) used label propagation GCNs. Klicpera et al. (2019) incorporated personalized PageRank with GCNs. Liu et al. (2021) introduced a 4 norm-based graph smoothing term to enhance the local smoothnesss adaptivity of GNNs. Hamilton et al. (2017); Zeng et al. (2020) proposed sampling and aggregation frameworks to extent GCNs to inductive learning settings. Another variant of GNNs is graph attention net- works (Velickovic et al., 2018; Thekumparampil et al., 2018; Abu-El-Haija al., 2018), which use attention mechanisms to adaptively learn aggregation weights based on the nodes features. There many other works GNNs (Pei et al., 2020) (Ying al., 2018; Xinyi & Chen, 2019; Velick- ovic et al., 2019; Zeng et al., 2020), we refer to Zhou et al. (2020); Battaglia et al. (2018); Wu et al. (2021) for comprehensive review. Most GNN models implicitly assume that the labels of nodes and their neighbors should be the same or consistent, while does not hold for heterophilic graphs. Zhu al. (2020) investigated the issues of GNNs heterophilic graphs and proposed to separately learn the embeddings of ego-node and its neighborhood. Zhu et al. (2021) proposed framework to model the heterophily or homophily levels of graphs. Chien et al. (2021) incorporated generalized PageRank with graph convolution to adapt GNNs to heterophilic graphs.
improve
There are also some works on the interpretability of GNNs proposed recently. Li et al. (2018); Ying et al. (2019); Fu et al. (2020) showed that spectral graph convolutions work as conducting Laplacian smoothing on the graph signals and Wu et al. (2019); NT & Maehara (2019) demonstrated that GCN, SGC work as low-pass filters. Gama et al. (2020) studied the stability properties of GNNs. Xu al. (2019); Oono & Suzuki (2020); Loukas (2020) studied the expressiveness of GNNs. Verma & Zhang (2019); Garg al. (2020) work on the generalization and representation power of GNNs.
Graph based Semi-supervised Learning. Graph-based semi-supervised learning works under the assumption that the labels of a node and its neighbors shall be the same consistent. Many meth- ods have been proposed in the last decade, such as Smola & Kondor (2003); Zhou et al. (2003); Belkin et al. (2004) use Laplacian regularization techniques to force the labels of linked nodes to be the same or consistent. Zhou & Schölkopf (2005) introduce discrete regularization techniques to impose different regularizations on the node features based on p-Laplacian. Lable propagation (Zhu et al., 2003) recursively propagates the labels of labeled nodes over the graph topology and use the convergence results to make predictions. To mention but a few, we refer to Zhou & Schölkopf (2005); van Engelen & Hoos (2020) for a more comprehensive review.
16

---

Under review as a conference paper at ICLR 2022
B DISCUSSIONS AND FUTURE WORK
In this section, we discuss the future work of PGNNs. Our theoretical results and experimental results could lead to several potential extensions of PGNNs
New Paradigm of Designing GNN Architectures. We bridge the gap between discrete regulariza- tion framework, graph-based semi-supervised learning, and GNNs, which provides new paradigm of designing new GNN architectures. Following the new paradigm, researchers could introduce more regularization techniques, c.g.. Laplacian regularization (Smola & Kondor, 2003; Belkin al., 2004), manifold regularization (Sindhwani et al., 2005; Belkin et al., 2005; Niyogi, 2013), high- order regularization (Zhou& Belkin, 2011), Bayesian regularization (Liu et al., 2014), entropy reg- ularization (Grandvalet & Bengio, 2004), and consider more explicit assumptions the homophily assumption, the low-density region assumption (i.e. the decision boundary is likely to lie in low data density region), manifold assumption (i.e. the high dimensional data lies on a ciw-dimensional manifold), to develop new graph convolutions or message passing schemes for graphs with specific properties and generalize GNNs much broader range of graphs. Moreover, the paradigm also enables us to explicitly study the behaviors of the designed graph convolutions or message passing schemes from the theory of regularization (Belkin & Niyogi, 2008; Niyogi, 2013; Slepcev & Thorpe, 2017).
graphs, e.g.
Applications of "GNNs to learn on graphs with noisy topologies. The empirical results (as shown in Fig. and Tables and 7) on graphs with noisy edges show that PGNNs are very robust to noisy edges, which suggests the applications of p-Laplacian message passing and PGNNs the graph learning scenarios where the graph topology could potentially be seriously intervened.
Integrating with existing GNN architectures. As shown in Table 9, the experimental results on heterophilic benchmark datasets illustrate that integrating GCN, JKNet with PGNNs can signifi- cantly improve their performance on heterophilic graphs. It shows that "GNN could be used as plug-and- sas--ndd-layy -layppyy component to be integrated into existing GNN architectures and improve their perfor- mance on real-world applications.
Inductive learning for PGNNs. PGNNs are shown to be very effective for inductive learning on PPI datasets as reported Table PGNNs even outperforms GAT on PPI, while using much fewer parameters than GAT. It suggests the promising extensions of 2 GNNNs to inductive learning graphs.
17

---

Under review as a conference paper at ICLR 2022
C ADDITIONAL THEOREMS
C.I THROREM (UPPER- HOPPRRBOUNNDIN RISK OF PGNN)
Theorem 4 (Upper-bounding risks of PGNNs). Given graph G (V,E, W) with N nodes, let X E IRNxe be the node features and y E R be the node labels and ((k) a 3 Fk are updated accordingly by Equations (12) to (14) for k = 0, 0.1..... K and F = X, K E N. Assume that is d-regular and the ground-truth node features X X represents the noise in the node features and there exists a L-Lipschitz function a RNNx + RN
where E RNx
such that a (X*) ) y. let y (k+1) = ( (K 1/2 (F(k(((()) + 3(%) (F(D)), we have
N
N
y
VAl
1K-1)
11 (XH,)))
N
1=1
K-2 K-
MD
ai
(K-1)
A(K 11-1)
pl
+
II
Σ d
A
( X1,
k=
I=
Σ (1 1--k/k--) ||e,.
Proof see Appendix D.4. Thm. 4 shows that the risk of "GNNs is upper-bounded by the sum of three The first term of the r.h.s in the above inequation represents the risk of label prediction using only the original node features X, the second term is the norm of p-Laplacian diffusion on the node features X, and the third term is the magnitude of the noise in the node features. o,2 and 9r, control the trade-off between these three terms and they are related to the hyperparameter l in Eq. (10). The smaller μ., the smaller 8 and larger Osg, thus the more important of the p-Laplacian diffusion term but also the more effect from the noise, Therefore, for graphs whose topological information is not helpful for label prediction, we could impose more weights on the first term by using large μ so that PGNNs work more like MLPs which simply learn on node features. While for graphs whose topological information is helpful for label prediction, we could impose more weights on the second term by using small y so that PGNNs can benefit from p-Laplacian smoothing node features.
terms:
In practice, to choose a proper value of μi one may first simply apply MLPs on the node features to have a glance at the helpfulness of the node features. If MLPs work very well, there is not much space for the graph's topological information to further improve the prediction performance and we may choose a large μ.. Otherwise, there could be large chance for the graph's 's topological information to further improve the performance and we should choose a small J..
C.2 THEOREM (P-ORTHOGONAL. THEOREM (LUO ET AL., 2010))
Theorem 5 (p-Orthogonal Theorem (Luo al., 2010)). If ( and ut are two eigenvectors of p- Laplacian Ap associated with two different non-zero eigenvalues x and X,, W is symmetric and p 2 1, then (9) and (rr) are p-orthogonal up to the second order Taylor expansion.
Thm. 5 implies that (p) op (u(") = O, for all 1, O...., space spanned by the multiple eigenvectors of the graph p-Laplacian y-orthogonal.
N - 1 and X # X,. Therefore, the
C.3 THBOREM (p-EIGEN-DECOMPOSII
A,)
Theorem 6 wwreiien-Decomposiiee of Ap). Given the p-eigenvalues {hr E R RRI and the eiigenvvectors {u()) e R 1= of L-Lpllacian Dp and | (2) [|p = (EN ( p/)
1. let U be a matrix of p-eigenvectors with = ()) (1) ()...... (N-))) and A be a diagonal matrix with A- diag(>o, >I,..., 11- then the preigen-decomppsiiionn of p-Laplacian Dp is given by
A, = (U)
When 2, it reduces to the standard eigen-decomposition of the Laplacian matrix.
Proof Appendix D.5.
18

---

Under review as a conference paper at ICLR 2022
C.4 THEOREM 7 (BOUNDS OF P-EIGENVALUES)
Theorem 7 (Bounds of p-Eigenvalues), Given a graph 9 = E,, W), if is connected and p-eigenvalue associated with the p-eigenvector u of Ap. let N; denotes the number of edges connected node N Nmnn (iin(Ni):1112 N, and arg max([]u]/ - (...)= then
1. for p 2 2, < 2F-1;
2. for < < 2, < A 201 V
3. for 1, 0 < A / Nmmnn
Proof see Appendix D.6.
D PROOF OF THEOREMS
D.1 PROOF OF THEOREM 1
Proof. Let i be the one-hot indicator vector whose i-th element is one and the other elements are zero. Then, we can obtain the personalized PageRank on node i, denoted as TP), by using the recurrent equation (Klicpera et al., 2019):
(k-1)
(i) aD 1D 1/2
(k) π TPp (8) + Sé,
TPPR
where k is the iteration step, < < 1 and B = (1 a) represents the restart probability, Without
loss of generality, suppose TPPR (i) Then we have.
(0)
π PPR (2) = aD 1/2 WD 1/2 π (A-
(i) + Bi
PPR
=aD 1/2 - 1/2
oD 1/2 DD" 1/2 (k-2) PPR
(i) + Bi) + Bi
(aD 1/2 WD 1/2
2 (t-2)
(1) + 30 1/2 WD 1/2 + Bi
TPPR
k-1
(aD (aD-1/2WWI) WD 1/2)
TPPR
ii + +B
aD 1/2 1122
WD WD 1/2)²
1=0
(aD 1/2 WD 1/2) K
i 3 Σ
aD DDD 1/W WD 1/2)
t=0
Since a and the eigenvalues D 1/2 1/2 in [-1, 1]. we have
1/2 WD 1/2) 0, lim n
and we also have
aD aD aDD11/2 WD 1/2) INN - -112 1/2) -1
lim 100
Therefore,
Tppp (2)
lim
TPpR
(i) = 8 INN - aD -1/2WD - 112
10000
= 3 (a + (1 - aI)
= plA2 + *IIN) i.
where we let Ifp and 3 Ifp / 0. Then the fully personalized PageRank matrix can be obtained by substituting i with In:
IPPR = (1 + -1
19

---

Under review as a conference paper at ICLR 2022
D.2 PROOF OF THEOREM 2
Proof. By the definition of (p( in Eq. (8), we have for some positive real value 14, 14 >
0
(F
2
1
Σ
Wii Fi:
Di.
V
Wid Diu
Fji
+ p
F 8,
x
i=1
and by Eq. (12),
p-2
Wis p( |V
WaS V
M
F
Da.t
Djs
3=:
Then, we have
0cp (F())
(K))
N
Wij
W (())
W (kk
(V
Wis p())
Wis (b)
+ 2u(F (A) - -x..)
(F(k) (4)
Di,
|V
Da.
V
D3s
Di,
V
Djs 3:
N
M
N Σ
M
Σ
F
F((A)
2p((F(()) x..))
p
Di.
4,2
Dr,
Diái
:::
j=1
p
M
F
(K)
M
+
21 X..
))
Di.i
P
Dr. Dis ز.j
P
M 1.
(R)
X1:; ))
p
F
(k)
0,,
(K)
F (k)
(k)
(R)
Di.s Djs
j=1
p
F
(1++1)
1)
(R)
which indicates that
(k)
acp (F())
(b)
F
(1+
(k)
p
For all i,j E [N], v E Ixc, denote by
OC, (F(K))
OC,
OF(A) (k)
p-2
M
We
Wii
E (R) v) V
W
F (K) d
V
D
Dju
N
M
((K)
1.j
2/
D4,5
p
j=1
(((k) = ai,
2p ((K)
N
M (kk
((+11) = ai.
((k)
((() + X..
D Di.Diis j.j
j=1
20

---

Under review as a conference paper at ICLR 2022
Then
p (K)
+v) - +v)- (F (
F
+ F((et!i)
((6)
(k)
p
|
p
F
F(()))
p
F
(()
((k)
(k)
1,2
1,3
p
M
+
P
P
F(R)
p
F((+1)
+
p (k+11)
(k)
(K)
(k)
(R)
4,:
(k)
i,
M
+P
N
M
((R)
N
M.
(k)
N
M (k)
2p
X
+
N
M
(k)
F
+
214
X
(()
D
Di,s
Di. Djs
p
Di,
P
j=1
j=1
N
M ((R)
N
M
N
(R)
N
M
(k)
|
+p
P
F(K)
+
F(())
(K)
Di.
Dia
Dr, 3.5
3
DD, P3
J.'
j=1
j=1
N
(K)
N
M
(K)
(K)
M M
(k)
M
(k)
N Σ
M (k)
M (A)
p
+ 2p
|| +
|
+p
p(a)
Di.
Di.i
D
VDa:Dos
j=1
1=1
j=1
N
(k)
24 p
+ o v, xx
|Iv||
p
Di
Therefore, there exists some real positive value μ E o v, x) > O such that
(F +v) (F!
S pl
N
M
+
2p
[|||
|v|l
(19)
Di.i
p
(R)
1=1
Let y = TT) E RN and n E Nxc, By Taylor's theorem, we have:
(,(F((1) + mm)))
= (,((!! + { (F +exma)) m.
(,((!! + (T (F (F!!)) (F (k)
+ewm.)) - (C,,(F(.)), )e
s (.,(((())) + T4 (
(T. )) 78 | +erma))) ac, (T.(.) ||| ni /de s (F(( + ( (F!
+
1llm...11
20
(8)
21

---

Under review as a conference paper at ICLR 2022
Let Lp (F())) and choose some positive real value μ which depends on X, 9. and p 1, Le. μ E 0 (p, X. 9). By Eq. (19), we have for all E [N],
[F (8) - -&C, (F ( (n:
P
11110p (F)))
75
20
(R)
2 1,3
(F( (k))
2
||0c (F 1
(k)
%
20
p
(k)
(R)
(F
p
ai
aii
|F
Y/6
2a
(k)
p²
P
1,
Then for all E [M], when S 7/ 5
20
we have (p(F 0F0S s (p(F
and
p
% minimizes Sp (F(( - -, (1))) Therefore,
(K)
(p(((ttt))= (F(()(
1
_ VLp((((())) s (P(()))
p
D.3 PROOF OF THEOREMS 3
Proof. Without loss of generality, suppose F(()_ X. Denote M D D-1/ D D-122 by
Eq. (14), we have for K 2 2,
F(K) = a 1/2 M (K - -12pp((( + 3(K-11xx
-K-1I) M - pp(k-1) B(K-1)x
-a(K-t (a (K2)) M K -2p(k-2 2) + (((K-2) + x(K--1)x
-((-1)) (K-2) M MM 2p 2) + (K- (1) 11 -(K + -3(K-1188
(K-1
K-1 (
K-1
K-1
a (k)
(b)
O
Σ
II ) B(K-1- + (((
k=
k=
1=1
N=K-k
K
K-1
K-1
K-1
II
(R)
(k)
II
(
X +
II a
3(K-1- + (((K1)xx
O=
k=
k=1
N=K-k
(20)
Recall Equations (12) and (13), we have
P-2
Wis p(()
W., p(N)
for all i,j 1.2....... N,
Dja
IV
D1,s
D3s
and
for all = 1,2,..., N.
2p
j==
Dr
Note that the eigenvalues of M are not infinity and 0 ai, < 1 for all 1, 1.... N. Then we have
lim
II
(k)
0,
K K0000
k=0
and
K-1
K-1
lim K-+00
II (A)
I (K) k=0
=
k=
22

---

Under review as a conference paper at ICLR 2022
Therefore,
K-
K-1
lim F(K)
lim K0000
Σ
II a MMO 3(K-1-8) x + 3(K-
(21)
K-000
I= K
By Equations (6) and (12), we have
N
Wi
W
Apf(1) = Σ
Σ j=1
Di.
Dis
j=1
N
Ms.5
N Σ
Mi
= Σ
f(i)
f()).
(22)
Di.
Dii
j=1
j=1
By Eq. (13), we have
N
M(h)
(k)
2p
(23)
Di.i
(k)
p
==1
Equations (22) and (23) show that
p
((a11)
241 IN
(A),
(24)
which indicates
24 (4) a (*)
a (h) M (k)
IN
(25)
Eq. (25) shows that (x) is linear w.r. Ap and therefore can be expressed by linear combi-
nation in terms of Ap:
a ( M
g^(h) Ap.
(26)
where 0' = diag(0% (6/ "l,...,,',, 11 are the parameters. Therefore, we have
K-1
lim F(K)_
lim Koy00
II
(M)
BiK-
3(K-1)x
K 100
V=K-k
K-1
lim
0 Ap
g(k-1- + B((--)x
K-000
I=K-k
K-1 Bik-1-1
K-1
lim K00
II
0r()) A + -((K
V=K-
lim
Σ (()) A
K
where (*())_ diag(0)(()) ,0((k) (x(k)) defined as (0()) = -B((k-1) and
K
(M(h)) = 3 (1-
(10)) for 1,2,..., K 1.
t=
Let = (0o, 0,...,, 0 defined as 02 = ΣN iill
0M(()) for all k ==00 -0, 1,... K - 1, then
K-1
lim p(K)= = lim K-0
Σ
0,4xx +0ox
K4000
K-1
lim
Ax
K-000
Therefore complete the proof.
23

---

Under review as a conference paper at ICLR 2022
D.4 PROOF OF THEOREM 4
Proof. The first-order Taylor expansion with Peano's form of remainder for at X is given by:
O (Xi.) +
da (X).))
(F) ( xi.)
T + 10(1I -X;,111
0x
Note that in general the output non-linear layer (-) is simple. Here we assume that it can be well approximated by the first-order Taylor expansion and we can ignore the Peano's 's form of remainder.
For all I,..., N. Di, = Dass d, we have ai Σn Di, 1/2 (K (1) DJs Pi. Then
MLS
(K--1) 1.
[k)
91 - y/
N
M 1)
(K-1) 1)
σ (F - - 3(KK-1) 1) o (Xi:)
91 - i
Dr, Oز
N
M 1i(K-1)
do (Xi:)
91 1
(K 1)
a (X,:) - ai,
(K-1)
Di, Djs 5ز
1 (xx;,)
+
OX
(F(K-1)
J::
-xi,)
==1
M(K-1)
M(K-1)
F//K11 (xo()
91
(K-1)
1/1
(XX..)
- -2ii
(K-1)
Σ
F
/D.;D
DiiiDDjs
0x
/=1
N
M
(K)) (x))))
(K-1) 1) (y: o(x,.)) - (K-1)
a,i
Σ
}3 -X,: -cA:)
Dis
Ox
N
M
(Xi.)
[F(K-1) - Xi:) T
Oo (x
< (K)- 1/41 oX(,,)) + a
1)
+(1 Big 1((-111
DDr OX
0X
M(K-1)
S 50(K (K-1)
|//1 -X(x.)) + oz5t
(1-1)
do (
Σ
(F (n(Kk-1) - X1.))
+ (1 -
(1- =
1o (x
0X
v DisiDis
ax
N
M
< (11) 1//- - o(x,,)) + Uz
L
inj
(p(k-1) -x::) -x:s)
+ (1 - -/// -1(- ( ||a:!ll
d
1=1
N
MM
(K-1)
= ((1-1) 1y: - xX.). + 2z
Σ
(p(K-1) -F(K-)
+ F(K-1)
Xix))
d
6,:
1=1
+ +(1
N
M 1K-
N (2))
= (11-1) 1/: - (X.:)) + a
A
(K-1)
(F(K-2) Xi:)
1.:
j=1 d
d
j=1
+ (1
1) ) |G
K-2K-2
= [[(--1) 1y: - o(x,:)) + a
(K-1)
L
1)
K-1)
Σ
II
Σ
A X,
+(1 3(K 1) L |E,.1l
p
d
K=
1=
K-2K-2 II
0
(
= -((K-1) 1y: o(Xi:)l + 0
(K (K-1)
L
A 1K-11 FF!
K
Σ
4 X.
X.
+11 3/ 3 |EL,1
24

---

Under review as a conference paper at ICLR 2022
Therefore,
Vsl
-
1
1))
yy: a (xx,,))
N
1,
(K-1)
A
F
(K-1)
Σ
II
4, (6)
X
N
Pis
((K-1))
||a..|
D.5 PROOF OF THEOREM 6
Proof. Note that
(u) Σ up(u))u
| |l 2
|/ |
Σ
1
||
1,
1=1
1=1
then have
A U -,,0,,,
Therefore, 4, = (U)A4, T
When = 2, by (2((U) = U, we get A₂ = (2 (U) UAU
D.6 PROOF OF THEBRRE 7
Proof. By the definition of graph p-Laplacian, we have for all = 1, 1,2,...,A
N
Wi
Wis D
Wij Dys
p-2
(1
Wis Di,s
Wi, Djss
(Auu), Σ
uj
uj
(xp(
D
Then, for all 1.,,..., N.
p-2
W
Wes u4 D
W Uj Djs
Wa.t us Di.
Wes Dj.
Uj
6n
(u:)
Di.i
1=1
1
N
Waj Di.
We, u4 D
WiS Dj.s
(v
Wa.s us Dis
Wis uj Djnt
|1i11 10ll1-22u
V
us
V
j=1
N
Wes
We un De.
Wi11 Ds.s
n-
Wes Diss
We, uj Dist us
Di,5
| P--
Was De,
Wee Mj Dy.s
Wad
Wa,
"
Di,s
DD.,D ui
||us||
W., V
Wini ti
Wis
Wis uj
u4 D.,;
v
Ds.s
Di,s
/ DD,, Di.j ui
U1
1--
Wid
W4. U
Wa. Di,5
W., uj V DJ.s ui
Di,i
Vi,,DiJ W4
25

---

Under review as a conference paper at ICLR 2022
Let 1 arg max
|4
141....1. the above equation holds for all = then
1P-2
Wi,i
Wii
Wi
Wia
Wi,5 Uj Djs m
A
Dia
VD ii
V
Dr
N
Wi.1
Wi,
4i
IV
Wi.
Wi.i Wj Dau
10-2
Di.
V Do
24
Dr.
V
Wi.
Wis
Wis
Wiss Uj Djs Wi
Di.t
Di
Du.
0.
When p p=l. L,
A Σ
Wij
Wij
Mjj
W3.3 Dis
Wa. Wj Dau 24
Dia
v Di,:Dj. ui
V
N
Wi.
N
Wis
K
<
N₂
/N..
D1,t
D&s
1=1
1=1
where the last inequality holds by using the Cauchy-Schwarz inequality. The above inequality holds for all i = 1,2, ... N, therefore,
Wes S
Nmin
Di,
j=1
When > 1, we have for i = 1,2,...,N.. N.
N
Wi,i
WaS
W,,
W Uj Dj.t us
p-2
D
Di,Dis us
Dr.
Wi.i Di.
Wis Uj Djs uq
D
V
Wes Di,
W D
Wi, Dj.s
Uj
V
Σ Ø=1
Wi. D
1
D
Uj
V
D
14
Without loss of generality, let k = arg max /lu/// holds for = 1, 1,2.... N. then we have
D N). Because the above inequality
p-1
Wk. DR.K
Di. k Din
Ug uig
A
1
V
WR.5 DE.K
< 2P-11
For p 2 2,
Whos Da.2
WKJ
A < 2D Σ
< 2D
Σ
20-1
V
Dr.
j=1
26

---

Under review as a conference paper at ICLR 2022
For < <2
Wkd Da.E
N
Wki
A $ 2
Σ
2
S 22-1
-
VNk.
Di.e
Du.
j=1
j=1
D.7 PROOF OF PROPOSITION
Proof. We proof Proposition based on the bounds of p-eigenvalues as demonstrated in Thm.
By Eq. (6) and Eq. (12), we have
N
Wid
W1S ((
Apf(1) = Σ
Σ
Di.i
Dis
3=1
==1
N
M,
N
Mi f())
= Σ
f(i)
Σ
(27)
Di.i
VD
1=1
j=1
By Eq. (13), we have
M(A)
2p
(28)
Did
(K)
p
Equations (27) and (28) show that
4 = ((a(t))
-1
2 IN - -D (6) 1/2
(29)
which indicates
2p (b) (1() (1)).
a (A) (122 D D-1/2 IN
(30)
p
For io = 1,2,..., N, let ā (āI....,áx). a. = 1/ Σ N
Mi. then D.
MIS
24 p
04,5
(1 (4,)) - i
VDiaDis
Σ 1= D.,
Mid
1
Σ 1=1 Di.
N Mi.1
24
Me
j=
De.s
(1 azd:),
(31)
+ 2pá
Recall the Eq. (12) that
p-2
W
Wij
Mcj = Wss
// Di.i
F,,
V
Dj.
Fj
1. When = 2. for all I,...,NN, a; = and 0 S A,11 S 2, (2(A11)) works as both low-pass and high-pass filters.
2. When p > 2, by Thm. we have for all = 1..... N, A,-1 2 If0 â; 2
then 0 1 ā.d; < 1, which indicates that (p((--1) works low-pass filter; If
27

---

Under review as a conference paper at ICLR 2022
0e > -r, then 9p(2; 9p(2i-1) works as both low-pass and high- pash-passsss filters. Since
Mis
D&
Di,
N
Wij
2 N
Σ
(KV
D
N
((
1 11 |V
which indicates that ã; 2 |V/()) 0 ā S 2'- directly implies that 0 <
[V < -P ie. [v( 2 2 1)(o-) and when [|]](i]] 2 2 ie.
[V)( s 111-1)/(---- 2), a. 2 2PP always holds. Therefore, if [ - 2(p 1)/(p-)), 2),
Op (X works as both low-pass and high-pass filters node i; If 9p (p(-;11) works low-pass filter, || 2 2(e-1)/(p-2)
3. When 5 < 2, by Thm. we have for all i = L, 5 2 0 S 0; 22 0 S a,A; S 1, which indicates that 9p (Xi-)) work as low-pass filters; If à; 2 2 - /Nk, (p(1)-1 work as both low- low-pass and high-pass filters. By
Σ
Wij
1
DLs I(
W.S 1i=1 DE
IV
N
W
1
N WiS
[(V
D
[VV
Di,
N
Wis
1
2
11 [[
D
j=1
1,
we have
64
WiS D.
(
i=1
DEs
N
Wis
DES
((E
3=1
Wis (I
Σ D
< |
6; > 2/-p/VNN directly implies that [/) 2 2'-r/VNe, ie. [Vf(0)
AI VIVV V
1/(0-2) and when 0 < | < 22-P/VN2, i.c. 0 < [V((]
2(2 No 1/(0-2), 0 < ã; < 2 22-P/VNN always holds. Therefore, if 0 < |VS( 2(2 NNx 1/6-2), 9p(A work as low-pass filters; If 9p(A--1) work as both low-pass
and high-pass filters, | (()) > 2 (2 1/(0-2)
Specifically, when p 1, by Thm. we have for all 1,..., N, < X
2- /N min- Following the same derivation above we attain if 0 < |])(I)) < ((2/Nmin) 1/(6))), gp (A:1)) work as low filters; If (p(-1))) work as both low-pass
and high-pass filters, // f()Il 2 2 (2 (2/)) 1/(p-2)
28

---

Under review as a conference paper at ICLR 2022
E DATASET STATISTICS AND HYPERPARAMETERS
E.1
ILLUSTRATION OF GRAPH GRADIENT AND GRAPH DIVERGENCE
00002D
Wi
Wi. BL
Wizt
UC2.11
(
Miz (00.20 31 19)+
DC3
(b) Graph divergence.
(a) Graph gradient.
Figure A tiny example of illustration of graph gradient and graph divergence. Best view in colors.
E.2 DATASET STATISTICS
Table 2 summarizes the dataset statisties and the levels of homophily H(G) of all benchmark datasets. Note that the homophily scores here different with the scores reported by Chien et al. (2021). There is bug in their code when computing the homophily scores (doing division with torch integers) which caused their homophily scores to be smaller.
Table 2: Statistics of datasets.
Dataset
#Class #Feature
#Node
#Edge
Training Validation Testing H(g)
Cora
7
1433
2708
5278
2.5%
2.5%
95%
0.825
CiteSeer
3703
3327
4552
2.5%
2.5%
95%
0.717
PubMed
500
19717
44324
2.5%
2.5%
95%
0.792
Computers
13381
245778
2.5%
2.5%
95%
0.802
Photo
8
745
7487
119043
2.5%
2.5%
95%
0.849
CS
15
6805
18333
81894
2.5%
2.5%
95%
0.832
Physics
5
8415
34493
247962
2.5%
2.5%
95%
0.915
Chameleon
5
2325
2277
31371
60%
20%
20%
0.247
Squirrel
2089
5201
198353
60%
20%
20%
0.216
Actor
7600
26659
60%
20%
20%
0.221
Wisconsin
251
499
1703
60%
20%
20%
0.150
Texas
5
1703
183
279
60%
20%
20%
0.097
Coreell
1703
183
277
60%
20%
20%
0.386
E.3 HYPERPARAMETER SETTINGS
We set the number of layers as 2, the maximum number of epochs as 1000, the number for early stopping 200, the weight decay 0.0005 for all models. The other hyperparameters for each model are listed as below:
1."GN,, 155N, 2OGNN, 2:5GNN:
Number of hidden units:
Learning rate: {0.001, 0.01, 0.05)
Dropout rate: {0, 0.5}
μ.: {0.01, 0.1, 0.2, 1, 10
K: 6,
29

---

Under review as a conference paper at ICLR 2022
MLP:
Number of hidden units: 16
Learning rate: {0.001, 0.01}
Dropout rate: {0, 0.5)
GCN:
Number of hidden units: 16
Learning rate: {0.001, 0.01)
Dropout rate: {0, 0.5}
SGC:
Number of hidden units: 16 Learning rate: {0.2, 0.01)
Dropout rate: {0, 0.53
2
GAT:
Number of hidden units: 8
Number of attention heads:
Learning rate: {0.001, 0.005]
Dropout rate: {0, 0.6)
JKNet:
Number of hidden units: 16
Learning rate: {0.001, 0.01)
Dropout rate: {0, 0.5}
K: 10
a: (0.1, 0.5, 0.7,
The number of GCN based layers:
The layer aggregation: LSTM with 16 channels and layers
APPNP:
Number of hidden units: 16
Learning rate: {0.001, 0.013
Dropout rate: {0, 0.5}
K: 10
a: (0.1, 0.5, 0.7,
GPRGNN:
Number of hidden units: 16
Learning rate: (0.001, 0.01,0.05)
Dropout rate: (0, 0.5)
KK: 10
a: (0, 0.1, 0.2, 0.5, 0.9, 1}
dprate: (0, 0.,0.5.00 0.7.
30

---

Under review as a conference paper at ICLR 2022
F ADDITIONAL EXPERIMENTS
F.1 EXPERIMENTAL RESULTS ON HOMOPIЛLIC BENCHMARK DATASETS
Competitive Performance on Real- World Homophilic Datasets. Table 3 summarizes the aver- aged accuracy (the micro-F1 score) and standard deviation of semi-supervised node classification on homophilic benchmark datasets. Table 3 shows that the performance of "GNN is very close to APPNP, JKNet, GCN on Cora, CiteSeer, PubMed datasets and slightly outperforms all baselines on Computers, Photo, CS, Physics datasets. Moreover, we observe that "GNNs outperform GPRGNN on all homophilic datasets, which confirms that "GNNs work better under weak supervised infor- mation (2.5% training rate) discussed in Remark 3. We also see that all GNN models work significantly better than MLP on all homophilic datasets. It illustrates that the graph topological in- formation is helpful for the label prediction tasks. Notably, 1.0 GNN is slightly worse than the other "GNNs with larger p. which suggests to use p = 2 for homophilic graphs. Overall, the results of Table indicates that #GNNs obtain competitive performance against all baselines on homophilic datasets.
Table 3: Results on homophilic benchmark datasets. Averaged accuracy (%) for 100 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold. OOM denotes out of memory.
Method
Cora
CiteSeer
PubMed
Computers
Photo
CS
Physics
MLP
43.47
46.15
78.95
66.11
76.44
86.24
92.58
GCN
76.23 62.43
83.72.0.27
84.17
90.4610.4s
90.33
94.46
SGC
77.19=1.47 64.10+1.3
79.2640..9
84.32
89.81
91.06
00M
GAT
75.62=1.01 61.28+1.00
83.60.0.22
82.72+1.29
90.4820.sr
89.9620.27
93.96+0.21
JKNet
77.19=0.08 63.3220.95
82.54
79.94+2.47
88.29 1.64
89.6920.64
93.92=00.22
APPNP
79.58_00.0
63.02+1.10
84.80
83.3221.11
90.422..63
91.5420.22 24
94.93
GPRGNN
16.10
61.60+1.69
83.1640.84
82.78+1.87
89.81
90.59
94.72 10.16
1.ºGNN
77.5920.69
63.19
83.21
84.4620.89
90.69 40.66
91.4620.50
94.7240.37
1.5GNN
78.86
63.80 70.79
83.65
90.91 85.03
92.12 #0.40
94.90 10.16
2.0 GNN
=8.93
63.65
1100
84.1940.22
8..39
90.40
92.
40.47
94.93 00.14
GNN
78.87 00.77
63.28
84.45
83.85
89.82 20.64
20.94
94.87
F.2 EXPERIMENTAL RESULTS OF AGGREGATION WEIGHT ENTROPY DISTRIBUTION
Here we present the visualization results of the learned aggregation weight entropy distribution of PGNNs and GAT on all benchmark datasets. Fig. 5 and Fig. 6 show the results obtained on homophilic and heterophilic benchmark datasets, respectively.
We observe from Fig. 5 that the aggregation weight entropy distributions learned by PGNNs and GAT on homophilic benchmark datasets are similar to the uniform cases, which indicates that ag- gregating and transforming node features over the original graph topology is very helpful for label prediction. It explains why "GNNs and GNN baselines obtained similar performance on homophilic benchmark datasets and all GNN models significantly outperform MLP.
Contradict to the results on homophilic graphs shown in Fig. 5, Fig. 6 shows that the aggregation weight entropy distributions of PGNNs on heterophilic benchmark datasets are very different from that of GAT and the uniform cases. We observe from Fig. 6 that the entropy of most of the aggrega- tion weights learned by PGNNs are around zero, which means that most aggregation weights are on one source node. It indicates that the graph topological information in these heterophilic benchmark graphs is not helpful for label prediction. Therefore, propagating and transforming node features over the graph topology could lead to worse performance than MLPs, which validates the results in Table 3 that the performance of MLP is significantly better most GNN baselines on all heterophilic graphs and closed P PGNNs.
31

---

Under review as a conference paper at ICLR 2022
uniform
FGNN (Ace: 78.43%)
35N (Acc: 78.98%)
1FGNN (Aoc: 78.39%)
GAT (Ace: 73.06%)
entrapy
entropy
criropy
entropy
entropy
Citeseer
un unfform
19GN N (Acc 62.95%)
1GNN IAce: 64.87%)
AGNN (Acc: 63.32%)
CAT (Acc: 61.59%)
2.10
1214
enAropy
entropy
orEtopy
entropy
eniropy
Pubmed
uniform
1-GNN (Ace: 83.2%)
15CAN (Aee: 83.73%)
*GNN (Ace: 84.35%)
GAT (Ace: 83.85%)
entrody
encregy
en2rayy
entapy
entrapy
Computers
uniform
1/CAN (Ace: 65,24%)
1NGNN (Acc: 85, 3181
2NGNN (Ace: 83.68%)
GAT (Acc: 82.73%)
600
entrpy
entryy
entrODy
entropy
entrpy
Photo
uniform
RRNN (Ace: 91.33%)
(Ace: 9128%)
*GNNN (Ace: 9025%)
GAT (Aoc: 90.2956)
3103
2000
modee
#ntropy
entmpy
enirroy
entrooy
entropy
CS
uniform
01.178)
(Acc:
GAT (Ace: 89.0%)
ontropy
entropy
entmpy
entroy
entropy
Physics
(Acc: 94.94%)
(AcE:
antmppy
estrogy
antmmy
entmpy
Figure 5: Aggregation weight entropy distribution of homophilic benchmark graphs. Low entropy means high degree of concentration, vice versa. An entropy zero means all aggregation weights are on one source node.
32

---

Under review as a conference paper at ICLR 2022
Chameleon
un inrfoom
FGNN (Acc: 48.8%)
GGNN (Ace: 48.916)
*GNNN (Acc: 49.23%]
GAT (Acc: 44.64%)
1213
200
entryy
entropy
enempy
entropy
entrayy
Squirrel
uniform
LGNN (Ace: 32 0.08%)
SGNN (Ace: 28.15%)
25GNN (Ace: 33.39%)
GAT (Acc 28.7256)
3500
entropy
entropp
erR-opy
entropy
entroyy
Actor
uniform
3:GNN (Ace: 41 41.219)
15GNN IAce: 40.63%)
3.5NN (Ace: 39.46%)
GAT (Aett 31.12%
300
entroyy
entropy
entmpy
entropy
entryy
Wisconsin
uniform
3FGNN IAce: 98.15%)
1GNN (Ace; 96.3%)
25GNN (Ace: 84.26%
GAT (Ace: 62.96%6
370
wntropy
entropy
ankopy
entropy
entropy
Texas
uniform
(Ac:: (6.25%)
GNN (Ace: 03.75%
2RGNN (Ace: 86, 25%
GAT (Ace: 48, (5%6)
00305
entropy
entropy
estopy
entropy
Cornell
(Acc: 75.0%
(Ace: 42.5%)
of
ontropy
ontropy
entloyy
crempy
Figure 6: Aggregation weight entropy distribution of heterophilic benchmark graphs. Low entropy means high degree of concentration and vice versa. An entropy of zero means all aggregation weights are on one source node.
33

---

Under review as a conference paper at ICLR 2022
F.3 EXPERIMENTAL RESULTS ON CSBM
In this section we present the experimental results on cSBM using sparse splitting and dense split- ting, respectively. We used the same settings in Chien al. (2021) in which the number of nodes n = 5000, the number of features / = 2000, = 3.25 for all experiments. Table 4 reports the results on cSBM with sparse splitting setting, which also are presented in Fig. 2 and discussed in Sec. 5. Table 5 reports the results on cSBM with dense splitting settings.
Table 4: Results on cSBM with sparse splitting setting. Average accuracy (%) for 20 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold.
Mathod
d= 0.75
0.5
== -.25
@ = 0.25
0 = 0.5
0 0.75
4= 1
49. 39
51.42+1.88
83
59.21
11001
+0.38
61.70
+ 30
59.9221.88
07.20
54.48
50.09
GCN
57 57.24
56.
19.141144
37
54.45 51.97
64.70
82.45
01.31
76.07
SGC
55.9811.48
08.3611
10.54
01.34g0.92
32.6912.30
64.14:1.05
19.88
90.3710000
70.9420.92
29.72+2.23
60.20
4..9
50.15
43.05
64.00+2.03
81.04
1.
78.24=1.95
JKNel
49. 39.70
49.75.0.79
19.65.0.522
48.93_0.48
$2.3812.00
62.76
87.1011.52
97.43 10:30
97.69
APINP
48. 45.1.8....
49.6520-46
53.3110.99
56.3820.58
60.1010.88
65.0212.25
82.95:11.58
95.4910-43
89.85-20.0
GPRONN
97.2610.66 66
94.81g0.91
82.14.0.47
61.15g2.55
60.20
22.90
83.61
96.96g0.41
98.01
1N
05.75+1.22
03.06+1.13
77.39+4.21
61.38
40.30
61.80+ 0.20
65.73
85.85+4..24
06.80+0.a7
97.-40+1.10
GNN
46.90++3.01
44.10+4.57
73.08 42.50
+0.30
0.33
06.0141..5
90.67+0.71
97.38+0.4
97.70+0 +0.80 86
GNNN
96.32 98.37
84.98
61.1320.61
61.79
+0 34
63.5611.73
88.6541..0
97.56.0.16
97.9440 30
GNN
07. 07.74+0.30
96.78+0044
83.21+2.12
61.30
61.74
62.88+2.81
79.6442.11
97.25 05.71+0.34
Table 5: Results on cSBM with dense splitting setting. Average accuracy (%) for 20 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold.
Mechod
== 00.75
0.5
== -0.25
0 0
0.25
0.5
0.75
MLP
50. 50.37
06.22
76.8240..8
81.18.0.a5
79.97 70.86-00.00
76.08
67.53 es
51.9640..0
GCN
83.1440.49
02.59-0.48
77.1740.50
58.58+0.41
61.18+1.00
02.59
92. 92.20+0.27
07.21+0.2
97. 97.10+0.12
78.35+0.36
82.13+0.00
77-76+0.12
58.14+0.67
60.31+0.60
81.96+0.84
91.68
96-56+0.00
96.87=0.06
GAT
92.9940.56
90.80-0..0
87.02.40.80
08.40-11.0
61.98+1.18
82.92
92.05.20.73
97.28-00.25
98.04-0048
JKNet
68 9549.06
79.2147.07
67.97+5.22
56, 12444.10
58.3341.70
15.1560.80
91. 91.2140.50
98.32 07.62-0.25
97.
APPNP
49.
49.86.20.39 39
20.47.2..8
73.98.0..4 20.28
70.3720.88
86.0020.75
02.45:0.39
97.17
97.65-2044
GPRGNN
99.06 0.22
97.1440.51
94.69+0.32
88.8440..0
78.8141.30
85.85+1.01
92.0840.55
97.49
40.22
98.40
1NNNNN
98. 98.19
94.3820.44
86. 16.40:1.00
60.3720.45
80.21
42
92.42 87.3220.44
e2
97.52
98.37 20.33
1.
98.88
05.6220.a1
16
80.7010.7
80.28
10 31
86.29
92.40
97.58
20.25
98.24
2NNN
99.21 09
10.11
20.
60.83
80.04
go 49
64.96 60
97.41 91. 18.
20.14
98.45 10
GNN
99.2110.14
20.16
93.2810.37
80.93.0.44
80.28:0 38
63.8330.70
86. 86.10.0.59
96. 98.2820.44
97.7620.18
Table 5 shows that PGNNs obtain the best performance weak homophilic graphs (ò 0, 0.25)
while competitive performance against GPRGNN on strong hetcrophilic graphs (ø = -0.75, 1) and competitive performance with sfate-of-the--ar GNNs on strong homophilic graphs (ò- 0.75, 1). We also observe that GPRGNN is slightly better than "GNNs on weak heterophilic graphs (ø- -0.25, -0.5), which suggests that GPRGNN could work very well using strong supervised infor- mation (60% training rate and 20% validation rate). However, as shown in Table 4, #GNNs work better than GPRGNN under weak supervised information (2.5% training rate and 2.5%) on all het- erophilic graphs The result is reasonable, as discussed in Remark 3 in Sec. 3.2, GPRGNN can adaptively learn the generalized PageRank (GPR) weights and it works similarly 2.O on both homophilic and heterophilic graphs. However, it needs more supervised information in order to learn optimal GPR weights. On the contrary, "GNNs need less supervised information to obtain similar results because (2)) acts like hyperplane for classification. Therefore, PGNNs can work better under weak supervised information.
F.4 EXPERIMENTAL RESULTS ON GRAPHS WITH NOISY EDGES
Here we present more experimental results on graph with noisy edges. Table 6 reports the results on homophilic graphs (Computers, Photo. CS, Physics) and Table 7 reports the results on heterophilic graphs (Wisconsin Texas). We observe from Tables 6 and 7 that "GNNs dominate all baselines. Moreover, P PGNNs even slightly better than MLP when the graph topologies are completely random, ie. the noisy edge rate r = 1. We also observe that the performance of GCN, SGC, JKNet on homophilic graphs dramatically degrades as the noisy edge rate increases while they do not change
34

---

Under review as a conference paper at ICLR 2022
lot for the cases heterophilic graphs. It is reasonable since the original graph topological information is very helpful for label prediction on these homophilic graphs. Adding noisy edges and remove the same number of original edges could significantly degrade the performance of ordinary GNNs. On the other hand, since we find that the original graph topological information in Wisconsin and Texas is not helpful for label prediction. Therefore, adding noisy edges and removing original edges on these heterophilic graphs would not affect too much their performance.
Table Results on homophilic graphs with random edges. Average accuracy (%) for 20 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold. OOM denotes out of memory.
Computers
Photo
Method
0.25
r= 0.5
1
r' 0.25
r= 0.5
r
MLP
66.11 22.70
66.11
76.4142.83 16.11
76.44+2.s.
76.4442.83
GCN
74.70+1.72
62.16_2.76
8.95
81.43+0.76
75.52+3.69
12.78+6.20
SGC
75.15 66.96_1.0s
15.7947.47
82.22+0.36
77.80+0.49
13.57
GAT
76.44:1.81 68.34_2.61
11.5817.70
82.70+1.31
17.2012.10
77.20
13.7415.14
JKNet
56.7426.48
46.11_8.43
12.5016.56
73.4618.74
15.6616.10 64.18
APPNP
78.23
74.57=2.22
66.67
1..63
8..22
75.55+1.72
GPRGNN
77.30=2.24
77.11=1.80
66.85+1.65
85.95
85.6441.22
77.46+1.44
1Nº
75. 75.19
63.26
11.60
87.97
94.4713..0
41.17:11.15
1.5 GNN
81.79.1.33
78.12
66.04
88.09
1118
16.20
68.7816..7
2. GNN
80.34
76.90_1.93
67.17:1163
87.65
87.06
77.07 +1.83
GNN
79.14
75.19_1.25
61..5522.7
87.38
86.1111.10
76.65
CS
Physics
Method
r 0.25
r 0.5
r= 1
r = 0.25
r= 0.5
r r=
MLP
86.24
86.24_1.43
86.24 1.43
92.58 63
92.58
92.5810.83
GCN
81.05
68.37
7.72+2.39
89.02.20. 18
80.45
19.78:3394
SGC
83.41 71.98
8.00
00M
OOM
00M
GAT
80.11
68.66_1.42
8.49442.9
82.05 88.7240..1
22.3946.04
JKNet
81.35+0077 71.30
11.43:
87 87.9840.97
81.90
26.38
APPNP
87.56_0.61 88.63.0.68
76.90
93, 98.4640.12
92.81
90.4940.33
GPRGNN
85.77
72.7942.24
92, 18.0.22
90.96.0.48
91.7710.41
GNN
90.27 20.86
89, 59.56
86.60.1.22
94.35-20.99
94.23
92.97
GNN
91.27 00.4
90.50
84. 1.84
94.34
93.7710.29
92.51
2.0 GNN
90.97 20.49
89, 89.98_0.00
80.8441.4
94.14
93.30+0.a1
91.72+0.44
40.18
2. GNN
89.90
89. 89.00=a..9
76.82+2.11
93.61
92.77+0.26
91.16+0.47
Table Results on heterophilic graphs with random edges. Average accuracy (%) for 20 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold.
Wisconsin
Texas
Method
== 0.25
0.5
r
0.25
= 0.5
MLP
93.5645.14
93.5623.14
93.5643.14
79.50 10.62
79.50+10.62
79.50+10.62
GCN
62.31 59.4445.78
64.21144.0
41.5645.89
44.69423.05
40.31+18.26
SGC
64.6847.34 62.3612.64
51.8142.63
42.50
40.91418.34
23.81
GAT
65.37+9.04 60.05
60.05+7.46
39.50+9.29
34.88+21.69
29.38+11.6a
JKNet
64.91413.07 51.39911.36
57.4 57.41
47.75+7.30
46.6242a.23
40.69413.67
APPNP
70.19+9.04
60.32++470
72. 72.6444.73
66, 66.69413.46
63.25
69. 69.81
GPRGNN
90.97 13.83
87.50
87.551.2.97
74.25
76.75114.05
80.65 80.69
1.0 GNN
94.91 +2.73
95.97 22.00
81.50+9.24 95.97
81.81 (1.815..6
1.5 GNN
94.58 11225
95.1942.18
94.95
12.50
78,50 78.12
2.0 GNN
90.4642.77
90.97
91.4442.27
66.06+5.17
69.38
63.50
2.5 GNN
82, 82.4519.93
88.24+2.79
84.40+1.9a
80.00=10.sa
56.62410.01
52.31 100.58
35

---

Under review as a conference paper at ICLR 2022
F.5 EXPERIMENTAL RESULTS OF INTERGRATING "GNNS WITH GCN AND JKNET
Here we further conduct experiments to study whether "GNNs can be intergrated into existing GNN architectures and improve their performance on heterophilic graphs. We use two popular GNN architectures: GCN (Kipf Welling, 2017) and JKNet (Xu et al., 2018).
To incorporate "GNNs with GCN, we use the "GNN layers as the first layer of the combined models, termed as "GNN + GCN, and GCN layer as the second layer. Specifically, we use the aggregation weights oD MD 1/2 learned by the PGNN in the first layer as the input edge weights of GCN layer in the second layer. To combine "GNN with JKNet, we use the 'GNN layer as the GNN layers in the JKNe framework, termed as "GNN + JKNet. Tables 8 and report the experimental results on homophilic and heterophilic benchmark datasets, respectively.
Table 8: The results of "GNNs + GCN and PGNNs JKNet on homophilic benchmark dataset. Averaged accuracy (%) for 20 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold.
Method
Cora
CiteSeer
PubMed
Computers
Photo
CS
Physics
GCN
62.43 76.23
83.72
84.1740.50
90.462..4s
90.33
94.46.0.0s
1.0 GNN GCN
32.37
60.56.1559
82.1410.91
83.75.1.05
90.24 1.12
94.5920. 89.6010.46
GNN GCN 72.72+1.39
60.23
83.89 80.21
40.74
90. 90.00
89.48
94. #0.18
GNG GCN 4..3
60.19
82.24
83.92 1.09
90.17
40.88
94.51 94.51+0.39 89.60
2. 2NNGNN GCN
72.85+1.19
59.68
82.23
83.69
90.02
89.53
94.58.
JKNet
77.19 10,98
63.32 10.95
82.54
L0.43
12.47
$8.29
89.69
93.92....2
LeG
75.67
60.38
81.68
83.1911.36
89.71
90.26
94.27 20.69
LeeGNNJJKNet
76.40+1.59
60.67
82.42
82.78.2.09 12.09
90.25
1.00
90.76.0.75
94.82210.3
2.0 GNN+JNNNeet GNN+JKNNet
76.75.1.26
61.05 61.05+1148
82.50
2o.53
82.36
89.31
1..39
94.70 90.3310.63 33
76.48+1.28
60.97
82.56
81.45
89.21
94.29 89.66
Table 9: The results of PGNNs + GCN and PGNNs + JKNet on heterophilic benchmark dataset. Averaged accuracy (%) for 20 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold.
Method
Chameleon
Squirrel
Actor
Wisconsin
Texas
Cornell
GCN
34.5442.78
25.28
31.28+2.04
61.93
56.54.17.02
51.36
1.0 GNN + GCN
34.78 48.52
32.37 13.12
68.5213.75
67.94
12.60
67.81 177.8117.66 17.61
1.5 1.NGNN GCN
48.8542.13
34.61
32.37
66.25
64.88.9..18 65.62
2.0 GNN + GCN
48.71 35.0611.18
32.72.2.02
66.34
65.9417.63
68.62.16.55
2.5 GNN GCN
49.53
34.40+1.00
32.40+3.23
67. 67.1843.50
68.31
66.0649.56
NKt
33.2843.59
25.82
29.7722.61
61.08
59.65212.62
55.34444.45
1.OGNN JKNet 49.00
+2.00
35.5641.34
40.74_0.98
95.23
80.25 .87
78.38
1.5 1.5GNN + JKNet 48.77+2.22
35.9810.08
40.2221.27
94.8642.00
80.38
72.25
2NNNN JKNet 48.8841.43
35.7741773
40.16
88.8442.78
86.1245.50
74.75-47.81
&GNN + JKNet 49.04
35.78
40.00+1.12
85.4243.86
79.0647.60
76.81 4.666
We observe from Table that intergrating "GNNs with GCN and JKNet does not improve their performance on homophilic graphs. The performance of GCN slightly degrade after incorporating PGNNs. The performance of JKNet also slightly degrade on Cora, CiteSeer, and PubMed but improved on Computers, Photo, CS, Physics. It is reasonable since GCN and JKNet can predict well on these homophilic benchmark datasets based on their original graph topology.
However, for heterophilic benchmark datasets, Table 9 shows that there are significant improvements over GCN, and JKNet after intergrating with "GNNs. Moreover, "GNNs JKNet obtain advanced performance all heterophilic benchmark datasets and even better than PGNNs on Squirrel. The results of Table demonstrate that intergrating PGNNs with GCN and JKNet can sigificantly im- prove their performance on heterophilic graphs.
36

---

Under review as a conference paper at ICLR 2022
F.6 EXPERIMENTAL RESULTS OF "GNNS ON PPI DATASET FOR INDUCTIVE LEARNING
Additionally, we conduct comparison experiments of PGNNs against GAT on PPI dataset (Zitnik & Leskovec, 2017) using the inductive learning settings as in Velickovic et al. (2018) (20 graphs for training. 2 graphs for validation, graphs for testing). We use three layers of GAT architecture with 256 hidden units, use 1 attention head for GAT (1 head) and 4 attention heads for GAT (4 heads). We use three PGNN layers and MLP layer the first layer for PGNNs, set 0.01, K 1, and use 256 hidden units for "GNN-256 and 512 hidden units for PGNN-512. The experimental results reported in Table 10.
Table 10: Results on PPI datasets. Averaged micro-F1 scores for 10 runs. Best results are outlined in bold.
Method
PPI
GAT head) GAT (4 heads)
0.917 + 0.041 0.972 0.002
1.0 GNN- -26
0.961 0.003
1-GNN-256
0.967 + 0.008
2-GNNN2566
0.968 0.006
2-GGNN-566
0.973 1: 0.002
LOGNN-512
0.978 + 0.005
1.5 GNNN-5522
0.977 + 0.008
GNN-551
0.981 + 0.006
2.5 GNN-512
0.978 + 0.005
From Appendix F.6 we observe that the results of 2. on PPI slightly better than GAT with attention heads and other "GNNs very close to it. Moreover, all results of "GNNs significantly outperform GAT with one attention head. The results of "GNNs on PPI is impressive. PGNNs have much less parameters than GAT with 4 attention heads while obtain very completitive performance on PPI. When we use more hidden units, 512 hidden units, PGNNs-512 significantly outperform GAT, while "GNNs-512 still have less parameters. It illustrates the superior potential of applying PGNNs to inducting learning on graphs.
F.7 EXPERIMENTAL RESULTS OF PGNNS ON OGBN ARXIV DATASET
Table 11: Results on OGBN arXiv dataset. Average accuracy (%) for 10 runs. Best results are outlined in bold.
Method
OGBN arXiv
MLP
55.50 1 0.23
GCN
71.74 0.29
JKNet (CCN-based)
72.19 0.21
DeepGCN
71.92 0.16
GCN residual (6 layers)
72.86 0.16
GCN residual (8 layers) C&S
72.97 1 0.22
GCN residual (8 layers) C&S v2
73.13 1 0.17
GNN
72.40 1 0.19
GGNN
72.45 1 0.20
"GNN
72.58 1 0.23
GNNN + residual (6 layers) + C&S
72.96 - 0.22
GGNN + residual (6 layers) + C&S
73.13 + 0.20
GNNN + residual (6 layers) + C&S
73.23 1 0.16
Here we present the experimental of "GNNs on OGBN arXiv dataset (Hu et al., 2020). We use the official data split setting of OGBN arXiv. We three layers "GNN architecture and 256 hidden units with μ = 0.5, K = 2. We also combine "GNNs with correct and smooth model (C&S) (Huang al., 2021) and introduce residual units. The results of MIP, GCN, JKNet, DeepGCN (Li et al.,
37

---

Under review as a conference paper at ICLR 2022
2019). GCN with residual units, C&S model are extracted from the leaderboard for OGBN arXiv. dataset?. Table 11 summaries the results of "GNNs against the baselines.
We observe from Table 11 that PGNNs outperform MLP, GCN, JKNet, and DeepGCN. The perfor- mance of PGNNs can be further improved by combining with C&S model and residual units and 3GNN residual (6 layers) C&S obtains the best performance against the baselines.
F.8 RUNNING TIME OF PGNNS
Tables 12 and 13 report the averaged running time of PGNNs and baselines on homophilic and heterophilic benchmark datasets, respectively.
Table 12: Efficiency on homophilic benchmark datasests. Averaged running time per epoch (ms) / averaged total running time (s). OOM denotes out of memory.
Method
Corn
CieSeer
PubMedd
Computers
Photo
CS
Physics
MLP
7.7 ms / 5.274
8.1 us / 5.37%
7.8 6.522
8.8 m..8///// 6.46+
8. is 5.344
10.5 ms 8. 8.184
14.6 ms 12.784
84.2 6.11
/ 6.333
2oss/7. 7.07s
ms/
8G ms/ 9.68ls
90 13.84
89-5 ms /4.96.
74.7 mi
80.6 5.2254
100
85.9 4.96.
213.6 8800
O0M
GAT
534.8 ms/ 13.06s
813 G mi/ 13.354
914.6 as 13.97ss
441.3 mtsmm/22 /2s.224..2 6:2
309.8 ms 15.
454 ms 21 875
436 9 ms 40.9s
JKNet
95.4 ms / 20.UTs
101.1 ms 19.08s
103.4 ms/ 20.
106.1 ms / 722
97.9 ms 21.188
102.7 ms 24. 9446
119. 2 ms 4U.83s
APPNP
86.7
11
86.3
11.98x
85-5
92.1 ms/15.764
86 12.1
90.5 /17.36
99.6
GPRGNN
86.0 ms 122.42x
195.8
12.66
88.6 ms /12500
93.3 ms/ 15.984
80.7 us /12.654
92 ms 1.7.84
217.1 ms 335
GNN
96 mx/ 20. 12s
98.1 ms 19.8
100.2 ms mwk./2 72..74
151.4 ms/ 64.00
121.3 m /4.07%
109.7 mx 25.00s
122. /49.
1.6 1.6
98.2
20.19k
97 a 20,2002222 26s
100.2 ma
140.3 64.08s
120 ms /3.224
112.3 ma 225.1
127. ms 64x
GNN
98.1 mx/ mw.00.1 1s
96.3 ms 99%
99.3 ms 17x
141
m4.66.0044 64.04s
129.3 ms /4.34.14 34.1
104.7
mk 24.92s
124.6 ms 44.335-
2.5 GNN
96.6 6 ms/ 20.1
92. 9 ms. 20.16s
103 ms 22.17s
141.8 ms /6.001s
128.1 ms / 34.22s
110.8
ms ms/05.007
124 msx 49.39s
Table 13: Efficiency on heterophilic benchmark datasests. Averaged running time per epoch (ms) / averaged total running time (s).
Mathed
Chumelooe
Squirel
Actor
Wisconsin
Texas
Comeel
ms 29s
ms/ 5.44s
8.6 ms
7.7 ms 5.1ds
7.9 ms 2:2
7.6 5.
GCN
83.4 ms 1s
83. 2 uss / 2s
90.7 ms G.00s
83.5 as/ 5.94s
50.7 ms 6.9kis
87.1 / 92s
SGL
78.1 ms/ 4.933
110.9 ms / 21s
77.1 ms /4. 44771s
73.2 m2222.//4422 4.52s
74.2 ms 7.7
71.3 ms 44.85
374.9 ma/
324.2 117.15.
420 / 13.822
317.5
357.9 /12.38..
383.3
12.45+
JKNet
102.4 ass
101 /22.84s
97.22 ms 21, 21.244
98.5 ms /21.07s
103.6 ms 22-924
102.2 ms /20.795
APENP
87.1 ms/ 12:12s
98.88 ms 122 41s
87.2 ms 11 885
84.2 ms 11.883
86 ms 11.99
83.1 ms/ 11.94s
GPRGNN
93 mss/ 12,98s
86.1 ms/ 13.01s
94.2 ms 133.038
84.3 ms 12.666
92 mi /12.64s
89.1 / 12.6x
1.OGNN
107.3 /ss 4.8
116.3 ms /80.22s
117.5 ms
94.5 18..77
92 18.
92.7 ms 18.977
GNN
97.2 ms /22.642..444 54x
115 ms 31.04s
119.2 ms 23.475
93.3 ms 18.64s
90.8 mis 199.08
94.9 mi 188884
2.0 GNN
98.7 7..7ms/22 /22.37
114.8 ms 31..14s
100.8 ms 733
92.2 ms 19.09.
92. 5 ms 18. 72s
98 ms 18.644
GNN
97.9 ms 22.388
115.9 ms/ 31.004
97.3 ms/ 23.774
92.8 ms 19.034
91 ma/ 188.84
90.7 ms 188834
F.9 EXPERIMENTAL RESULTS ON BENCHMARK DATASETS FOR 64 HIDDEN UNITS
Table 14: Results on heterophilic benchmark datasets for 64 hidden units. Averaged accuracy (%) for 20 runs. Best results outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold.
Method
Chamelcon
Squirrel
Actor
Wisconsin
Texas
Cornell
MLP
16.55 33.83
38.40_o.re
93.91 22.47
87.51
86.75 4 22
8.53
GCN
34.71+2.2 25.68
30.86_1.51
65.93
58.56113.20
16.81
SGC
34.57+4.1 24.39
35.50 .0
62.87
88 92
50.6225.60
29.41414.83
GAT
43.33
30.07
33.44_2.45
66.57 4..00
50.69+12.89
42.62
JKNet
32.69
27. 27.18
25. 25.72_2.75
66.57
43. 43.88417.110
47. 49.2299322
APPNP
35.0913.18
28, 15.993
32.28
1.75
66.30
69.00
54.88 88
GPRGNN
34.65
28.5641.35
34.58 1.45
93.70aa.112
86.50 0.04
84.75.4..30
LºGNN
49.51 1.32
32.67+1.00
40.70 05.23+1.00 20.8
84. 64.12+7.0 39
82.56
1.5 LNNNN
49.52=1.15
33. 33.144
39.82_1.c. 1.54
94.03 -0 28
86,94 86.94
86.89
2. GGNNN
33.78 49.19
10.88
+0.87
39.75
1.28
94.49 1.81
87.62
6
85.5647.25
2. 2.5 GGNN
33.31+1.27 40.9
39.47
92.13
87.25
5.57
80.5645.28
mode-propttoghn-arkiy
38

---

Under review as a conference paper at ICLR 2022
Table 15: Results on homophilic benchmark datasets for 64 hidden units, Averaged accuracy (%) for 20 runs. Best results are outlined in bold and the results within 95% confidence interval of the best results are outlined in underlined bold. OOM denotes out of memory.
Method
Cora
CiteSeer
PubMed
Computers
Photo
CS
Physics
MLP
29.05=0.82
50.67
00.32
70.58+0.82
09.44
29.48
92.84+0.62
GCN
27.65
60.72
84.13
84.56
90. 10..88
=1.14
94.75.10.4
SGC
70.32=1.87 65.77
76.27
83.2440.81
89. 89.4341.0s
91.11
OOM
GAT
76.97=1118 61.28
83
83.84+1.93
90.54 10.56
89.68+0.42
93.91+9.20
JKNet
70.77=0.79
64.62220.50
12.82
82.22
88.43
90.4820.13
93.75+0.32
APPNP
79.95.40.72 63.56
1..64
6..64
84.00+0.22
83.83+0.78
90.50 10.59
91.90#0.12
94.8410.00
GPRGNN
78. 78.17
61.26
84.5440.24
83.7721.06
89.8640.65
91.3420.25
94.6340.22
1.NNNN
77.1 20.11
63.17
83.1420.46
82.6440.s8
89.60
92.53
94.86
#0.24
1.5 GNN
78. 20.49
63.1420.93
83.97
84.64 1.44
90.6710.07
92.93 14
94.93 40.12
GNN
79.06
63.92
84.57 84.24
1.096
90.17 80.88
92.74
10.28
95.05
2N5
79. 0.
63.1611.25
84.88 10.09
83.8440.71
89.05
92.31 10.19
94.921..110
F.10 TRAINING CURVES FOR p =
1
cora
240
cit sper
pubmed
LEAA
Epoch
Esoch
Epoch
computers
Trar nq
Tactin Assii)
18,20
Tasiig Ausuicy
Lakking Taatig ALDUNO)
Less
3
Artuwcy
8
Loss
Esech
Epech
physics
Chameleon
Squirrel
1.00
T150 P01 Tertig Aour
Trining Taring Ailu
Taain cal
LO04
2
Accurry
3
Losa
actor
110
wisconsin
L203
8
20
Spach
Epoch comell
Epoch
AcCUrDES
Eooch
Figure 7: The curves of training loss and testing accuracy for = 1.
39

---

Under review as a conference paper at ICLR 2022
F.11 VISUALIZATION RESULTS OF NODE EMBEDDINGS
(a) L.G
(b) L.N
2.GNNN
(d) 2.5 GNN.
(e) GCN.
Figure 8: Visualization of node embeddings for Cora dataset using t-SNE (van der Maaten & Hinton, 2008)
computers
computers
computers
(a) L.N.
(b) L.5.
(c) 2.0
computers
(d) 2.5 GNN.
(c) GCN.
Figure 9: Visualization of node embeddings for Computers dataset using t-SNE,
40

---

Under review as a conference paper at ICLR 2022
chamellon
chamelson
Cham elcon
(a) GN..
GNN.
2.0 GNN.
chamelson
(d) GNN.
(c) GCN.
Figure 10: Visualization of node embeddings for Chameleon dataset using t-SNE.
Wiscorsin
wiscorsin
wisconsin
(a) LNN.
(b) 1.5 LN5
(c) 2.0 2.0
wisconsin
(d) GNN.
(c) GCN.
Figure 11: Visualization node embeddings for Wisconsin Dataset using t-SNE.
41


Reviews:
[{"review_id": "euXj3JsaiIa", "reviewer": "Reviewer_rMNu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-- Strengths:\n\n1. The paper is very well-written and easy to follow. It was a pleasure to read the novel theoretical material presented in this paper. \n\n2. The paper proposes a novel architecture of p-GNN that introduces p-Laplacian message passing by leveraging and infusing existing architectures like SGC, APPNP and GPRGCN. \n\n3. The theoretical connection drawn between the “p-Laplacian message passing scheme” and “the polynomial graph filter defined on the spectral domain of the p-Laplacian” is particularly interesting. \n\n-- Weaknesses:\n\n1. It would have been interesting to see a theoretical justification as to why p-GNN always outperforms say GCNs, GATs, etc. (models that stack their message passing layers) on heterophilic graphs. Can the authors please elaborate on this point in their rebuttal? I feel this would give more insights into the behavior of p-GNN and why it is outperforming standard GNN models. \n\n2. Much of the material in Sections 2 and 3 is obtained from Zhou and Scholkopf 2005. Less space could have been used for this explanation.\n\n3. The function signature for the graph gradient operator in Definition 1 does not look right. The domain of this operator has to be a space of functions, it cannot be the set of vertices. Can you please relook into this?\n\n4. In regards to the experiments conducted on noisy edges, it would be interesting to see how p-GNN performs on some stochastic block models based on edge dropping and some other random graph percolations. The random edge drop model seems a bit simplistic and it's not easy to see how this sort of noise is affecting the graph inputs and why p-GNN should do better than other robust GNNs?\n\n5. In regards to the following statement in the paper on Pg 6. \t\t\t\t\n\n“Therefore, for graphs whose topological information is not helpful for label prediction, we could impose more weights on the first term in Eq. (18) by using a large μ so that P-GNNs work more like MLPs which simply learn on node features. While for graphs whose topological information is helpful for label prediction, we could impose more weights on the second term by using a small μ so that P-GNNs can benefit from p-Laplacian smoothing on node features.” \n\nHow does one determine when the graph’s topological information is helpful for\nlabel prediction, as opposed to when it’s not?\n", "summary_of_the_paper": "This paper proposes a p-Laplacian based GNN to handle heterophilic graphs and graphs with non-informative topologies. Both the above cases are assumed in most existing GNN architectures and hence this work breaks away from the norm. This work proposes a discrete p-Laplacian message passing scheme which is derived from a discrete regularization framework. The authors do a spectral analysis of their novel p-Laplacian message passing scheme and show that it works as both a low-pass and high-pass filter, which is then applicable to both homophilic and heterophilic graphs. More specifically, they show that p-GNN with p>2, works well for graphs which exhibit strong homophily, while for p \\in [1,2) p-GNN works effectively on heterophilic graphs. The empirical results support the theoretical justifications and outperform the baselines quite significantly especially on heterophilic and non-informative topology bearing graphs.", "summary_of_the_review": "The paper is well written and presents a novel p-GNN architecture on top of other PageRank based GNN architectures. I found the theoretical justifications and connections drawn between the message passing scheme and the polynomial graph filter particularly interesting. Also, they had an interesting bound on the risk (Theorem 3). I am overall quite positive about this paper's acceptance, as it makes novel contributions to handle a difficult scenario like heterophilly in graphs and also the fact that they challenge the implicit assumption made by previous works that the \"shape of node neighborhoods\" helps distinguish nodes.. of course this can be extended to graph shapes too.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cgYHYECo-9I", "reviewer": "Reviewer_4UH6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Pros:\n\n(+) The idea of designing new message-passing based on p-Laplacian is interesting.\n\n(+) The empirical evaluation of cSBM is great.\n\n(+) The high-level idea on the effect of different choices of p is inspiring.\n\n## Cons:\n\n(-) Most theorems derived in this paper are either well-known (Theorem 1) or not meaningful (Theorem 3).\n\n(-) The overall clarity of the paper can be improved, especially in section 4.\n\n(-) Some concerns regarding the choice of hyperparameters (see detail below).\n\n## Detail comments:\n\n-\tTheorem 1 is well-known in the graph learning community, (see [4], equation (3) for example). I think there should be a proper reference for it.\n-\tTheorem 3 is not very meaningful, as the derived risk bound is greater than discarding the graph part ($\\beta = 1,\\; \\alpha = 0$). This is because the analysis does not take the correlation of graphs into account. See [3] on how the authors show the graph convolution is helpful under cSBM assumption. I feel like the analysis and result here can be further improved for meaningful bound.\n-\tThe clarity of section 4 and explanation of Theorem 2 should be improved. Regarding the explanation of Theorem 2, I cannot understand why the “weight effect” of p-Laplacian based message passing can help for heterophilic graphs. What does the “boundary of the lined nodes” refer to in the explanation? On the other hand, while I like the explanation of Proposition 1, I feel like the authors treat the matrix M as fixed in this section. However, according to their definition, it should depend on the input feature matrix. Please elaborate more on this point and improve the clarity of the text.\n-\tI find it weird for the choice of hyperparameter for all baseline methods. More precisely, the authors choose the hidden unit = 16 while the default and common choice is 64. I wonder why the authors detour from the standard choice.\n\n### Typo:\n\n1.\tPage 2, the reference of the cSBM is incorrect. Should be [1].\n\n2.\tPage 5, in Remark 2: “In contrast, it is is similar with SGC…”, redundant “is” here.\n\n### Additional questions:\n\n1.\tThe matrix M in Theorem 2 depends on the node embedding F right? I assume it follows the specific aggregation rule of equation (12).\n\n2.\tDoes the iteration (11)-(13) guarantee to converge?\n\n## Reference:\n\n[1] Contextual stochastic block models. Deshpande et al. NeurIPS 2018. \n\n[2] Optimizing generalized pagerank methods for seed-expansion community detection, Li et al. NeurIPS 2019.\n\n[3] Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization, Baranwal et al. ICML 2021.\n\n[4] PREDICT THEN PROPAGATE: GRAPH NEURAL NETWORKS MEET PERSONALIZED PAGERANK, Klicpera et al. ICLR 2019. \n", "summary_of_the_paper": "The authors propose a new message-passing design based on p-Laplacian. They demonstrate that their method works better in heterophilic graphs.", "summary_of_the_review": "I have mixed feelings about this paper. On one hand, I like the newly designed message passing scheme and their implicit bias demonstrated in Proposition 1. Also, conducting experiments on cSBM is great for studying problems of heterophilic graphs. On the other hand, the drawbacks of the paper prevent me from supporting acceptance of it. I think the paper has great potential but requires a major revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CT7OVmNS2EG", "reviewer": "Reviewer_Pzid", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes general p-GNNs architecture under the p-Laplacian regularization framework\nwith comprehensive experimental results. The paper is well written and the theoretical part is well\norganized, though not significant. However, we still have some concerns. \n\nStrength:\n(1) The author proposes a new general GNN architecture based on p-Laplacian message passing,\nwhich claims to work on both heterophily and homophily settings.\n(2) Relations of p-Laplacian message passing with low-pass and high-pass filters have been\nexplained.\n(3)Experiments are comprehensive and inclusive.\n\nWeakness:\n(1) More insights on how to choose parameter p should be given. From the upper bound risk theorem, we only know that for K=1, the risk can be controlled by \\mu which further depends on whether the topological information of graphs is useful or not. However, for K >=2, we do not see the relations. More insights are welcomed.\n\n(2) The stationary point for the objective function in equation 8 is problematic when $p < 2$ and $\\nabla f =0$. In particular, when $p=1$  and $\\nabla f =0$, the Laplacian diffusion should have a step function that is not continuous at $\\nabla f =0$. The authors seem not to have given a good discussion on this aspect. \n\n(3) Moreover, when $p<2$, the graph diffusion operator is not Lip-continuous, which violates the assumption made by the upper-bounding risks theorem. So I do not see how that theorem can be applied here. \n\n(4) For p=1, the diffusion becomes a step function (piecewise constant), how can the model be trained? Can the authors also provide the training curve for the p=1 case?\n\n(5) P-GNN can only get comparable performances on homophilic benchmark datasets (both\naccuracy and entropy experiments).\n\n(6) The authors claim that p-lap can handle the heterophilic case. And the explanation is that the p-lap allows big change on the class boundary which can be viewed as a high-pass filter. I do not think this argument is very convincing. Can the authors have TSNE of the node embeddings for the heterophilic case so that we can get some visualization of the results?\n\n\nSome typos:\n(1)Page 2, last paragraph: Heterphily -> Heterophily\n(2)Section 3.1, R^N should be changed into N", "summary_of_the_paper": "The paper derives the p-Laplacian message passing formula under the p-Laplacian based regularization framework and further proposes p-GNN architecture. Authors further justify the relations of p-Laplacian message passing with low and high-pass filters and the upper bound of\none layer risk of p-GNNs. Experiments show the superiority of p-GNNs on both heterophilic and homophilic settings. However, we still have some concerns for the paper before further evaluation.", "summary_of_the_review": "See the main review. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies a variant of a message-passing scheme,  aiming to improve the efficiency of GNNs to heterophilic graphs, as well as improving its stability to noise. The authors provide a new architecture, called $p$-Laplacian message passing, as well as some theoretical analysis and empirical evaluation. 
Reviewers highlighted several positive aspects on this work, such as the general idea of considering p-Laplacians, as well as the extensive empirical evaluation. However, during the review discussions, several important issues arose, namely important concerns regarding the theoretical contributions, as well as concerns in calibrating the baselines in some empirical evaluations. Overall, the AC is of the opinion that this paper requires a further iteration before it can be considered for publication, and encourages the authors to take the time to address the comments raised by the reviewers.
Decision: Reject