Adaptive Universal Generalized PageRank Graph Neural Network
Authors: Eli Chien
Jianhao Peng
Pan Li
Olgica Milenkovic
Venue: ICLR 2021 Poster (2021)
Keywords: Graph Neural Networks
Generalized PageRank
Heterophily
Homophily
Over-smoothing

Abstract: In many important graph data processing applications the acquired information includes both node features and observations of the graph topology. Graph neural networks (GNNs) are designed to exploit both sources of evidence but they do not optimally trade-off their utility and integrate them in a manner that is also universal. Here, universality refers to independence on homophily or heterophily graph assumptions. We address these issues by introducing a new Generalized PageRank (GPR) GNN architecture that adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction, regardless of the extent to which the node labels are homophilic or heterophilic. Learned GPR weights automatically adjust to the node label pattern, irrelevant on the type of initialization, and thereby guarantee excellent learning performance for label patterns that are usually hard to handle. Furthermore, they allow one to avoid feature over-smoothing, a process which renders feature information nondiscriminative, without requiring the network to be shallow. Our accompanying theoretical analysis of the GPR-GNN method is facilitated by novel synthetic benchmark datasets generated by the so-called contextual stochastic block model. We also compare the performance of our GNN architecture with that of several state-of-the-art GNNs on the problem of node-classification, using well-known benchmark homophilic and heterophilic datasets. The results demonstrate that GPR-GNN offers significant performance improvement compared to existing techniques on both synthetic and benchmark data.

Published as a conference paper at ICLR 2021
ADAPTIVE UNIVERSAL GENERALIZED PAGERANK GRAPH NEURAL NETWORK
Eli Chien & Jianhao Peng"
Department of Electrical and Computer Engineering University of Illinois Urbana-Chane Chaaaaa-aa USA (ichien3, jianhao2 e ilinois.ediu
Pan Li
Olgica Milenkovic
Department of Computer Science Purdue University, USA panli i @epurdueeed
Department Electrical and Computer Engineering University of Illinois Urbana-Champaign, USA mi wwwkkoo@@llinoia.. edu
ABSTRACT
In many important graph data processing applications the acquired information includes both node features and observations of the graph topology. Graph neu- ral networks (GNNs) are designed to exploit both sources of evidence but they do not optimally trade-off their utility and integrate them in a manner that is also universal. Here, universality refers to independence graph assumptions. We address these issues by introducing a new Generalized PageRank (GPR) GNN architecture that adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction, regardless of the extent to which the node labels are homophilic or heterophilic. Learned GPR weights automatically adjust to the node label pattern, irrelevant on the type of initialization, and thereby guarantee excellent learning performance for label patterns that are usually hard to handle. Furthermore, they allow one to avoid feature over-smoothing, process which renders feature information nondiserim- inative, without requiring the network to be shallow. Our accompanying thcoreti- cal analysis of the GPR-GNN method is facilitated by novel synthetic benchmark datasets generated by the so-called contextual stochastic block model. We also compare the performance of our GNN architecture with that of several state-of- the-art GNNs on the problem of node-elassification, using well-known benchmark homophilic and heterophilic datasets. The results demonstrate that GPR-GNN offers significant performance improvement compared existing techniques on both synthetic and benchmark data. Our implementation is available online
homophily or heterophily
INTRODUCTION
Graph-centered machine learning has received significant interest in recent years due to the ubiquity of graph-structured data and its importance in solving numerous real-world problems such as semi-
supervised node classification and graph classification (Zhul 2005 Shervashidze et al. 2011 Lü & Zhou 2011). Usually, the data at hand contains two sources of information: Node features and graph topology. As an example, in social networks, nodes represent users that have different combinations of interests and properties captured by their corresponding feature vectors; edges the other hand document observable friendship and collaboration relations that may or may not depend on the node features. Hence, learning methods that are able simultaneously and adaptively exploit node features and the graph topology are highly desirable as they make use of their latent connections and thereby improve learning on graphs
Graph neural networks (GNN) leverage their representational power to provide oftt--of-theaat per- formance when addressing the above described application domains. Many GNNs use message
"quul contribution hutp://ghhhh..ommmaaaaoDDcCCCn

---

Published as a conference paper at ICLR 2021
passing (iimmr et al. 2017: Battaglia et al. 2018) to manipulate node features and graph topol- ogy. They are constructed by stacking (graph) neural network layers which essentially propagate and transform node features over the given graph topology. Different types of layers have been pro- posed and used in practice, including graph convolutional layers (GCN) (Bruna et al. 2014] Kipf &
Welling, 2017), graph attention layers (GAT) (Velickovic et al. 2018) and many others (Hamilton
ct al. 2017 7 Wijesinghe & Wang 2019; Zeng et al. 2020; Abu- El-Haija et al. 2019))
However, most of the existing GNN architectures have two fundamental weaknesses which restrict their learning ability on general graph-structured data. First, most of them seem to be tailor-made to work on homophilic (associative) graphs. The homophily principle (McPherson et al. 2001) in the context of node classification asserts that nodes from the same class tend to form edges. Homophily
also a common assumption in graph clustering (Von Luxburg.
2007
Tsourakakis 2015 Dau
& Milenkovic, 2017) and in many GNNs design (Klicpera et al. 2018). Methods developed for
homophilic graphs are nonuniversal in so far that they fail to properly solve learning problems on heterophilic (disassortative) graphs (Pei et al. 2019 Bojchevski et al. [2119] 2020). In heterophilic graphs, nodes with distinct labels are more likely to link together (For example, many people tend to preferentially connect with people of the opposite sex in dating graphs, different classes of amino acids are more likely to connect within many protein structures (Zhu et al. (2020) etc). GNNs model the homophily principle by aggregating node features within graph neighborhoods. For this purpose, they use different mechanisms such as averaging in each network layer. Neighborhood aggregation problematic and significantly more difficult for heterophilic graphs (Jia & Benson, 2020).
Second, most of the existing GNNs fail to be "deep enough". Although in principle an arbitrary num- ber of layers may be stacked, practical models are usually shallow (including 2-4 layers) as these architectures are known to achieve better empirical performance than deep networks. A widely ac- cepted explanation for the performance degradation of GNNs with increasing depth is feature- smoothing, which may be intuitively explained as follows. The process of GNN feature propagating represents a form of random walks on "feature graphs," " and under proper conditions, such random walks converge with exponential rate to their stationary points. This essentially levels the expressive power of the features and renders them nondiscriminative. This intuitive reasoning was first de- scribed for linear settings in Li et al. (2018) and has been recently studied in Oono & Suzuki (2020) for a setting involving nonlinear rectifiers.
We address these two described weaknesses by combining GNNs with Generalized PageRank tech- niques (GPR) within a new model termed GPR-GNN. The GPR- architecture is designed to first learn the hidden features and then propagate them via GPR techniques. The focal compo- nent of the network is the GPR procedure that associates each step of feature propagation with a learnable weight. The weights depend on the contributions of different steps during the information propagation procedure, and they can be both positive and negative. This departures from common nonnegativity assumptions (Kliepera et al., 2018) allows for the signs of the weights to adapt the homophily/heeerophiiyy structure of the underlying graphs. The amplitudes of the weights trade-off the degree of smoothing of node features and the aggregation power of topological features. These traits do not change with the choice of the initialization procedure and elucidate the process used to combine node features and the graph structure so as to achieve (near)-optimal predictions. In sum- mary, the GPR-GNN method can simultaneously learn the node label patterns of disparate classes of graphs and prevent feature over-smoothing
The excellent performance of GPR-GNN is demonstrated empirically, on real world datasets, and further supported through a number of theoretical findings. In the latter setting, we show that the GPR procedure relates to general polynomial graph filtering, which can naturally deal with both high and low frequency parts of the graph signals. In contrast, recent GNN models that utilize Personalized PageRanks (PPR) with fixed weights (Wu et al. 2019 Klicpera et al.) [0188] 2019) inevitably act as low-pass filters. Thus, they fail to learn the labels of heterophilic graphs. We also establish that GPR-GNN can provably mitigate the wwwuue--vve--mmoohhie issue in an adaptive manner even after large-step propagation (i.c., after large number of propagation steps). Hence, the method is able to make use of informative large-step propagation.
To test the performance of GPR-GNN on homophilic and heterophilic node label patterns and deter- mine the trade-off between node and topological feature exploration, we first describe the recently proposed contextual stochastic block model (cSBM) (Deshpande et al.) 2018). The cSBM allows for smoothly controlling the "informativeness ratio" between node features and graph topology,
2

---

Published as a conference paper at ICLR 2021
Generalized PageRank
Hidden state feature estraction
Z Σ H
HD
Neural Net: fa
H. )
X,
H
pm
H
Il
(a) Illustration of our proposed GPR-GNN model.
(b) Cora, H(G) = 0.656 (c) Texas, H(G) = 0.016
Figure (a) Hidden state feature extraction performed by neural networks using individual node features propagated via GPR. Note that both the GPR weights */k and parameter set {0} of the neural network are learned simultaneously in an end-to-end fashion (as indicated in red). (b)-(c) The learnt GPR weights of the GPR-GNN on real world datasets. Cora is homophilic while Texas is heterophilic (Here, H stands for the level of homophily defined below). An interesting trend may be observed: For the heterophilic case the weights altemate from positive to negative with dampening amplitudes (more examples are provided in Section 5). The shaded region corresponds to a 95% confidence interval.
where the graph can vary from being highly homophilic to highly heterophilic. We show that GPR- GNN outperforms all other baseline methods for the task of supervuper node classification the cSBM consistently from strong homophily to strong heterophily. We then proceed to show that GPR-GNN offers state-of-the-art performance on node-classification benchmark real-world datasets which contain both homophilic and heterophilic graphs. Due to the space limit, we put all proofs, formal theorem statements, and the conclusion section in the Supplement.
2 PRELIMINARIES
Let G = (V. be undirected graph with nodes V and edges E. Let denote the number of nodes, assumed to belong to one of C 2 2 classes. The nodes are associated with the node feature matrix X E R=xf, where f denotes the number of features per node. Throughout the paper, use X,, to indicate the Nhh row and X., to indicate the j"h column of the matrix X, respectively. The symbol di is reserved for the Kronecker delta function. The graph G is described by the adjacency matrix A, while Á stands for the adjacency matrix for a graph with added self-loops. We let D be the diagonal degree matrix of Á and A.ym D-122 AD-1 denote the symmetric normalized adjacency matrix with self-loops.
GPR-GNNS: MOTIVATION AND CONTRIBUTIONS
Generalized PageRanks. Generalized PageRank (GPR) methods were first used in the context of unsupervised graph clustering where they showed significant performance improvements
Per- sonalized PageRank (Kloumann et al. 2017 Li et al. 2019). The operational principles of GPRs can be succinctly described as follows. Given seed node V in some cluster of the graph, one-dimensional feature vector (0) E R is initialized according to H = 6.s. The GPR score defined as Σ "Yk A sym
& O)) = Σ k= 7/k (()), where the parameters */k E R, k = 0, 1......,
referred to the GPR weights. Clustering of the graph performed locally by thresholding the GPR score. Certain PangRank methods, such as Personalized PageRank or heat-kernel PageR- ank (Chung) 2007), are associated with specific choices of GPR weights (Li et al.) 2019). For an excellent in-depth discussion of PageRank methods, the interested reader is referred to (Gleich) 2013). The work in Li al. (2019) recently introduced and theoretically analyzed special form of GPR termed Inverse PR (IPR) and showed that long random walk paths are more beneficial for clustering then previously assumed, provided that the GPR weights are properly selected (Note that IPR was developed for homophilic graphs and optimal GPR weights for heterophilic graphs not currently known).
Equivalence of the GPR method and polynomial graph filtering. If we truncate the infinite sum in the definition of GPR at natural number K, Ek=D 7% A.k. sym corresponds to polynomial
3

---

Published as a conference paper at ICLR 2021
graph filter of order K. Thus, learning the optimal GPR weights is equivalent to learning the optimal polynomial graph filter. Note that one can approximate any graph filter using a polynomial graph filter (Shuman et al. 2013) and hence the GPR method is able to deal with large range of different node label patterns. Also, increasing K allows one to better approximate the underlying optimal graph filter. This once again shows that large-step propagation is beneficial.
Universality with respect to node label patterns: Homophily versus heterophily. In their re- cent work, Pei et al. (2019) proposed an index to measure the level of homophily of nodes in Number of neighbors of v V that have the same label Number of neighbons of
graph H(G)) = P Evev
Note that H(G)) + cor-
responds to strong homophily while H(G) - O indicates strong heterophily. Figures | (b) and (c) plot the GPR weights learnt by our GPR-GNN method on homophilic (Cora) and heterophilic (Texas) dataset. The learnt GPR weights from Cora match the behavior of IPR (Li et al. 2019). which verifies that large-step propagation is indeed of great importance for homophilic graphs. The GPR weights learnt from Texas behave significantly differently from all known PR variants, tak- ing a number of negative values. These differences in weight patterns are observed under random initialization, demonstrating that the weights are actually learned by the network and not forced by specific initialization. Furthermore, the large difference in the GPR weights for these two graph models illustrates the learning power of GPR-GNN and their universal adaptability.
The overssmoothing problem. One of the key components in most GNN models the graph convolutional layer, described by
) PGCN = softmax A Ayn H GON
H GCN
ReLU
A (Ay GON
(K
where H GON X and (()) represents the trainable weight matrix for the htth layer. The key issue that limits stacking multiple layers is the smoothhg phenomenon: If one were to remove ReLU in the above expression, lim A sym H = H where each row of ((() only depends on the degree of the corresponding node, provided that the graph is irreducible and aperiodic. This shows that the model looses discriminative information provided by the node features as the number of layers increases.
Mitigating graph heterophily and over-smoothing issues with the GPR-GNN model. GPR- GNN first extracts hidden state features for each node and then uses GPR to propagate them. The GPR-GNN process can be mathematically described as:
K
p softmax (Z), Z
Yh (K),
(K)
H
Asy H = (X.)),
where fo(.) represents neural network with parameter set { that generates the hidden state fea- tures ())) The GPR weights 7% are trained together with {0} in an end-to-end fashion. The GPR- GNN model is easy to interpret: As already pointed out, GPR-GNN has the ability to adaptively control the contribution of each propagation step and adjust it to the node label pattern. Examining the learnt GPR weights also helps with elucidating the properties of the topological information of graph (i.e., determining the optimal polynomial graph filter), as illustrated in Figure (b) and (c).
Placing GPR-GNNs in the context of related prior work. Among the methods that differ from repeated stacking of GCN layers, APPNP (Klicpera al. 2018) represents one of the state-of-the. art GNNs that is related to our GPR-GNN approach. It can be easily seen that APPNP as well as SGC (Wu et al. 2019)) are special cases of our model since APPNP fixes 7 = a(1-a)* 7K = (1- a)* while SGC removes all nonlinearities with 7 = dzK, respectively. These two weight choices correspond Personalized PageRank (PPR) (Jhh & Widom 2003). which is known be suboptimal compared to the IPR framework when applied to homophilic node classification (Li et al. 2019). Fixing the GPR weights makes the model unable to adaptively learn the optimal propagation rules which is of crucial importance: As we will show in Section 4 the fixed PPR weights corresponds to low-pass graph filters which makes them inadequate for learning on heterophilic graphs. The recent work (Klicpera et al., 2018) showed that fixed PPR weights (APPNP) can also provably resolve the ovor-smog problem. However, the way APPNP prevents over-smoothing is independent on the node label information. In contrast, the escape of GPN-GNN from over-smoohhing is guided by the node label information (Theorem 4.2). A detailed discussion of this phenomena along with illustrative examples is delegated to the Supplement.
4

---

Theorem (.2orem/4422shooee 4.2 that as long over-smoothing happens. ITx. will approach 0 for all k 2 k when we use an optimizer such as stochastic gradient descent (SGD) which has a suitable learning rate decay. This reduces the contribution of the corresponding steps (k)) in the final output Z. When Published as a conference paper at ICLR 2021
Among the GCN-like models, JK-Net (Xu also aggregates the outputs of different GCN
al.
2018) exhibits some similarities with GPR-GNN
layers to arrive at the final output. On the other
2016 Kipf & Welling 2017) is related to polyno- mial graph filtering, where each convolutional layer propagates multiple steps and the graph filter is related to Chebyshev polynomials. In both cases, the depth of the models is limited in prac- tice (Kliepera et al.] 2018) and they are not easy to interpret as our GPR-GNN method. Some prior work also emphasizes adaptively learning the importance of different steps (Abu-EI-Haija et al. 2018: Berberidis et al., 2018). Nevertheless, none of the above works is applicable for semi- supervised learning with GNNs and considers heterophilic graphs.
hand, the GCN-Cheby method (Defferrard et al.
4 THEORETICAL PROPERTIES OF GPR-GNNS
the GPR component of the network may be viewed as a polynomial graph filter. Let Asm UAUT be the eigenvalue de- composition of Asym- Then, the corresponding polynomial graph filter equals Σx=D A Ugy. (A)U", where (A, is applied element-wise and 9y,k(A) = Ek=o 7AA We estab- lished the following result.
Graph filtering aspects of GPR-GNNs. As mentioned Section 3
Theorem 4.1 (Informal). Assume that the graph G connected. If Th 2 0 AK {0. K}, Σk 7k = 1 and 3k' > O such that "' > O, then gx,K(-) is a low-pass graph filter. Also, if Yh = (-a)* a (0,1) and K is large enough, then gx,x(() is a high-pass graph gitee.
By Theorem 4.1 and from our discussion in Section 3 we know that both APPNP and SGC will in- variably suppress the high frequency components. Thus, they are inadequate for use on heterophilic graphs. In contrast, if one allows "/k to be negative and learned adaptively the graph filter will pass relevant high frequencies. This is what allows GPR-GNN to perform exceptionally well on heterophilic graphs (see Figure 2(c)).
GPR-GNN can escape from over-smoothing, As already emphasized, one crucial innovation of the GPR-GNN method is to make the GPR weights adaptively learnalle, which allows GPR-GNN to avoid over-smoothing and trade node and topology feature informativeness. Intuitively, when large- step propagation is not beneficial, it increases the training loss. Hence, the corresponding GPR weights should decay in magnitdee. This observation is captured by the following result, whose more formal statement and proof are delegated to the Supplement due to space limitations.
Theorem 4.2 (Informal), Assume the graph G is connected and the training set contains nodes from each of the classes, Also assume that k' is large enough so that the over-smoothing effect occurs for ((k) Vk > K' which dominate the contribution to the final output Z. Then, the gradients of " and Tk are identical in sign for all le 2 V.
the weights lnsl are small enough so that (&) no longer dominates the value of the final output Z, the over-smoothing effect is eliminated.
RESULTS FOR NEW CSBM SYNTHETIC AND REAL-WORLD DATASETS
Synthetic data. In order to test the ability of label learning of GNNs on graphs with arbitrary levels of homophily and heterophily, we propose to use cSBMs (Deshpande et al.) 2018) to generate synthetic graphs. We consider the case with two equal-size classes. In eSBMs, the node features are Gaussian random vectors, where the mean of the Gaussian depends on the community assignment. The difference of the means is controlled by a parameter μ4, while the difference of the edge densities in the communities and between the communities is controlled by parameter X. Hence μ and À capture the "relative informativeness" of node features and the graph topology, respectively. More- over, positive X's correspond to homophilic graphs while negative X's correspond to heterophilic graphs. The exfommation-theoret limits of reconstruction for the cSBM are characterized in Desh-
pande al. (2018). The results show that asymptotically, one needs X² + /22 / > 1 to ensure
5

---

Published as a conference paper at ICLR 2021
vanishing ratio of the misclassified nodes and the total number of nodes, where & n/f and f as before denotes the dimension of the node feature vector.
Note that given tolerance value e > 0, X² + 1²/5 +++ is an of an ellipsoid for which 2 0 and μ 2 0. To fairly and continuously control the extent of information carried by the node features and graph topology, we introduce a parameter & = arctan( ركا x -.2 The setting 0 indicates that only node features are informative, while |ő] = indicates that only the graph topology is informative. Moreover, á = 1 corresponds to strongly homophilic graphs while = -1 corresponds to strongly heterophilic graphs. Note that the values o and -Ø convey the same amount of information regarding graph topology. This is due to the fact that X - (- Ideally, GNNs that are able to optimally learn on both homophilic and heterophilic graph should have similar performances for é and - Due to space limitation we refer the interested reader to (Deshpande et al. 2018) for a review of all formal theoretical results and only outline the cSBM properties needed for our analysis. Additional information is also available in the Supplement.
Our experimental setup examines the semi-supervised node classification task in the transductive setting. We consider two different choices for the random split into rraining/validation/e samples, which we call sparse splitting (2.%% 2.5%/2.5% /95%) and dense splitting (60% 2/0///00%///2 20%), respec- tively. The sparse splittnig is more similar to the original semi remi-supervised setting considered in Kipf & Welling (201)) while the dense setting is considered in Pei et al.] (2019) for studying heterophilic graphs. We run each experiment 100 times with multiple random splits and different initializations.
Methods used for comparisons. We compare GPR-GNI with 6 baseline models: MLP, GCN (Kipf & Welling, 2017), GAT (Velickovic et al. 2018), JK-Net (Xu et al.) 2018), GCN-Cheby (Defferrard iet 2016)) APPNP (Klicpera et al. 2018). SGC (Wu et al. 2011), SAGE (Hamilton et al. 2017) and Deom-GCN (Pei et al.] 2019). For all architectures, we use the corresponding Pytorch Geo- metric library implementations (Fey & Lenssen (219)). For Geom-GCN, we directly use the code provided by the a We could not test Geom-GCN on cSBM and other datasets not originally tested in the paper due to preprocessing subroutine that is not publicly available (Pei et al. 2019).
The GPR-GNN model setup and hyperparameter tuning. We choose random walk path lengths with K 10 and use 2-layer (MLP) with 64 hidden units for the NN component. For the GPR weights, we use different initializations including PPR with a E {0.1, 0.2, 0.5, 0.9). 7A = dox or 0K and the default random initialization in pytorch. Similarly, for APPNP we search the optimal a within {0.1. 0.2, 0.5. 0.9}. For other hyperparameter tuning, we optimize the learning rate over {0.002, 0.01, 0.05) and weight decay {0.0, 0.0005) for all models. For Geom-GCN, we use the best variants in the original paper for each dataset. Finally, we use GPR-GNN(rand) to describe the results obtained with random initialization of the GPR weights. Further experimental settings discussed in the Supplement.
Results. We examine the robustness of all baseline methods and GPR-GNN using cSBM-generated data with & E -0.75, -0.5,... 1}. which includes graphs across the heterophilyhomophhin spectrum. The results are summarized in Figure 2 For both the sparse and dense setting, GPR- GNN significantly outperforms all other bascline models whenever ó < 0 (heterophilic graphs). On the other hand, all baseline GNNs can be worse then simple MLP when the graph information is weak (Ø- = O. -0.25). This shows that existing GNNs cannot apply to arbitrary graphs, while GPR-GNN is clearly more robust. APPNP methods have the worst performance on strongly het- erophilic graphs. This is in agreement with the result of Theorem 4.1 which asserts that APPNP intrinsically acts a low-pass filter and is thus inadequate for strong heterophily settings. JKNet, GCN-Cheby and SAGE are the only three baseline models that are able to learn strongly het- erophilic graphs under dense splitting. This is also to be expected since JKNet is the only base- line model that combines results from different steps at the last layer, which is similar to what is done in GPR-GNN. GCN-Cheby uses multiple steps in each layers which allows it to par- tially adapt heterophilic settings each layer is related to a polynomial graph filter of higher order compared to that of GCN. SAGE treats ego-embeddings and embeddings from neighbor- ing nodes differently and does not simply average them out. This allows SAGE to adapt to the heterophilic case since the ego-embeddings prevent nodes from being overwhelmed by informa- tion from their neighbors. Nevertheless, JKNet, GCN-Cheby and SAGE are not deep in practice.

---

Published as a conference paper at ICLR 2021
0.41
4 =0.55 Iherandom
CSM d 75,crsn Inferandom
6580
-0.2 deneee berandom
1.00
15RN
T5 cerse Inf
0.50
0.7
0.23
0.5
0.2
8.30
0.
0.2
8.-
-0.5
0.00
023
010
005
01
-0.
80
[steo]
<(eept
(a) 0 = 0.25,
(b)
0.75,
(c)
-0.25,
(d)
-0.75,
(H(G) 0.189)
(H(G) = 0.688)
(H(G) 0.029)
(H{G) = 0.002)
Figure 3: Figure (d)-(d) shows the learnt GPR weights by GPR-GNN with random initialization on cSBM, dense split. The shaded region indicates 95% confidence interval.
Moreover, JKNet fails to learn under the sparse splitting model while GCN-Cheby and SAGE fail to learn well when the graph information is strong (lé) 2 0.5), again under the sparse splitting model.
cSBM sparse split
100
50
accuracy 1%5
80
Also, we observe that random initialization of our GPR weights only results in slight performance drops under dense splitting. The drop is more evident for sparse splitting setting but our method still outperforms baseline models by a large margin for strongly heterophilic graphs. This also to be expected as we have less label infor- mation in the sparse splitting setting where the implicit bias provided by good GPR initialization is helpful. The implicit bias becomes irrelevant for the dense splitting set- ting, since the label information is sufficiently rich.
60
50
40
.05
cSBM split
100
70-
Besides the strong performance of GPR-GNN, the other benefit is its interpretability.. In Figure 3 we demonstrate the learnt GPR weights by our GPR-GNN random initialization. When the graph is weak homophilic (á 0.25), the learnt GPR weights are decreasing. This is similar to the PPR weights used in APPNP, despite that the decaying speed is different. When the graph strong ho-
60
cSBM with
50
40
-05
Figure 2: Accuracy of tested models on cSBM. Error bars indicate 95% confi- dence interval.
mophilic (Φ = 0.75). the learnt GPR weights are increas- ing which is significantly different from the PPR weights. This result matches the recent finding in Li et al. (2019)
and behave similar to IPR proposed by the authors. On the other hand, the learnt GPR weights have
zig-zag shape when the graph is heterophilic. This again validates 4.. GPR weights with alternating signs correspond to a high-past filter. Interestingly, when Φ = -0.25 the magnitude of learnt GPR weight is decreasing. This is because the graph information is weak and the node feature information is more important in this case. It makes sense that the learnt GPR weight focus on the first few steps. Hence, we have validated the interpretablity of GPR-GNN. In practice, can use the learnt GPR weights to better understand the graph structured data at hand. We showcase this benefit in the results of real world benchmark datasets.
Real world benchmark datasets. We use homophilic benchmark datasets available from the Pytorch Geometric library, including the citation graphs Cora, CiteSeer, PubMed (Sen et 2008
Yang et aL. (016)) and the Amazon co-purchase graphs Computers and Photo (McAuley et al. 2015
Shchur et al. 2018). We also use 5 heterophilic benchmark datasets tested in Pei et al. (2019).
including Wikipedia graphs Chameleon and Squirrel, the Actor co-occurrence graph, and webpage graphs Texas and Cornell from F
We summarize the dataset statistics in Table
Results on real-world datasets. We use accuracy (the micro-Fl score) as the evaluation metric along with a 95% confidence interval. The relevant results are summarized in Table 2 For homophilic datasets, we provide results for sparse splitting which is more aligned with the original setting used in Kipf & Welling (2017); Shchur et al. (2018). For the heterophilic datasets, we adopt dense splitting which used in Pei et al. (2019).
http://wwwww...mm...ttttsscccucp http:///thhhhoollll////////////t 1/www/wwkh
7

---

Published as a conference paper at ICLR 2021
Table I: Benchmark dataset properties and statisties.
Dataset
Cora
Citeseer
PubMed
Computers
Photo
Chameleon
Squirrel
Actor
Texas
Cornell
Classes
7
6
5
10
8
5
5
5
5
Features
1433
3703
500
767
745
2325
2089
932
1703
1703
Nodes
2708
3327
19717
13752
7650
2277
5201
7600
183
183
Edges
5278
4552
44324
245861
119081
31371
198353
26659
279
277
H(G)
0.656
0.578
0.644
0.272
0.459
0,024
0.055
0.008
0.016
0.137
Table 2: Results on real world benchmark datasets: Mean accuracy (%) + 95% confidence interval. Boldface letters are used to mark the best results while underlined boldface letters indicate results within the given confidence interval of the best result.
Cora
Citeseer
PubMed
Computers
Photo
Chumeleon
Actor
Squiree
Texas
Cornell
GPRGNN
79.51
67.63+4-.38
85.07=0.09
82.90-0-337
91.93-2-26
67.48=0.40
39.30=00.27
49,93-1-.55
92.92-0061
91.36+0.70
APPNP
79.41=0035
68.5910.00
85.02:20.00
81.99:0.26
91.11
51.91=0:66
34.77:1034
91.18
MLP
50.341048
52.8810511
80.5720.12
70.4810028
78, 78.69:0330
46,7 46,72=20.6
38.5810.25
31.28:1027
92.26=1071
91.36:1070
SGC
70.81
58.9820047
82.09-20.11
76.27:00.6
83.802046
63.02=00.43
29.39:0..0
43.144022
55.18
47.80=1.50
GCN
75:21
67.30.1035
84.27:0001
82.52:10.30
90,5410211
60.96:0.78
30.591:.23
45.66:10.99
16.162099
66.7221.37
GAT
76.70:1.42 67,20:10.16
83.28:10122
81.95
90.09:1027
63.910..6
35.98110.23
42.72:1:.33
78.87:0..6
76.0011.1
SAGE
70.89+0.54
61.5240.4
81.30++010
90.51+0225
62.15=0.42
36.37++0.21
41.26-+-266
79.03+1.20
7141++124
JKNet
73.22+0064 60.85+0766
82.91
77.80=0.97
87.70
62.92=0.49
33.41
44.72+00.8
75.53=1.16
66.73=1.73
GCN-Cheby
71.39=0.51 65.6740.38
83.8320.12
82.41:0028
90.09:10:88
59.96=0.511
38.02:00:33
40.67:0311
86.0820.66
85.33=104
GeomGCN
20.37
20.30:1000
18.20
NA
NA
61.06:0.49
3:.11:0.44
38,2810227
58,56:11.7
55.59
Table shows that, in general, GPR-GNN outperforms all tested methods. On homophilic datasets, GPR-GNN achieves the state-of-the-art performance. On heterophilic datasets, GPR-GNN signif- icantly outperforms all the other baseline models. It is important to point out that there are two different patterns to be observed among the heterophilic datasets. On Chamelcon and Squirrel, MLP and APPNP perform worse then other baseline methods such as GCN and JKNet. In contrast, MLP and APPNP outperform the other baseline methods Actor, Texas and Cornell. We conjecture that this is due to the fact that the graph topology information is strong and weak, respectively. Note that these two patterns match the results of the cSBM experiments for á close 1 and 0, respectively (Figure 2). Furthermore, the homophily measure HH(G) proposed by Pei et al. (2019) cannot char- acterize such differences in heterophilic datasets. We relegate the more detailed discussion of this topic along with illustrative examples to the Supplement.For fairness, we also repeated the experi- ment involving GeomGCN on homophilic datasets using a dense split - the observed performance pattern tends to be similar which can be found in Supplement.
We also examined the learned GPR weights on real datasets in Figure 4 Due space limitations, more comprehensive GPR weight analysis for other datasets is deferred to the Supplement. We can see that learned GPR weights are all positive for homophilic datasets (PubMed and Photo). In contrast, some GPR weights learned from heterophilic datasets (Actor and Squirrel) are negative. These results agree with the patterns observed on cSBMs. Interestingly, the learned weight % has the largest magnitude for the Actor dataset. This indicates that most of the information is contained in node features. From Table 2 we can also see that MIPs indeed outperforms most baseline GNNs (this is similar the case of cSBM(
0.225). On the other hand, GPR weights learned from Squirrel have zig-zag pattern. This implies that graph topology is more informative for Squirrel compared to Actor From Table 2 we also see that baseline GNNs also outperform MLPs on Squirrel.
Escaping from over-smoothing and dynamics of learning GPR weights. To demonstrate the ability of GGR--NNN escape from over- wer-shotth,ig, we choose the initial GPR weights be 7% = бдк- This ensures that wer-smoothing effects are present with high probability at the very beginning of the learning process. On cSBM = -1) with dense splitting, we find that for 96 out of 100 runs, GPR-GNN predicts the same labels for all nodes at epoch O, which implies that svor-sngg indeed occurs immediately. The final prediction is 98.79% accurate which much larger than the initial accuracy of 50.07% at epoch O. Similar results can be observed for other datasets and this verifies our theoretical findings. We plot the dynamics of the learned GPR weights in Figure e)- (h), which shows that the peak at last step is indeed reduced while the GPR weights for other steps are significantly increased in magnitude. More results on the dynamics of learning GPR weights may be found in the Supplement.
8

---

Published as a conference paper at ICLR 2021
Pubitted batted,dense Initorando
peor.deree.nt--randee
Squireldense rnE-oendom
0.-
0.4
0.2
0.6
02
0.0
10
(step)
(a) PubMed
(b) Photo
(c) Actor
(d) Squirrel
<555 - mi spicho
15883 e LinilmD
1588 4 L.nit 100
1.0
1.2
0.0
0.8
0.5
0.5
MW
044
MW
0.4
322
02
0.4
0.0
02
-0.
9.2
-0.4
-04
(step)
(ctep)
kittpp))
K k15tep)
(c) Epoch= 0
(f) Epoch= 50
(g) Epoch= 100
(h) Epoch= 150
Figure 4: Figures (a)-(d) show the learned GPR weights of our GPR-GNN method with random initialization on various datasets, for dense splitting. Figures (e)-(f) show the learned weights of
our GPR-GNI method with initialization  on cSBM( = 1), for dense splitting. The shaded region indicates a 95% confidence interval.
Table 3: Efficiency on selected real world benchmark datasets: Average running time per epoch(ms))average total running time(s). Note that Geom-GCN requires a preprocessing proce- dure so we do not include it in the table. Complete efficiency table for all benchmark datasets is in Supplementary due space limit.
Cora
Pubmed
Computers
Chameleon
Actor
Squirrel
Texas
GPRONN
17.62ms 3.74s
30.19ms / 5.533
39.93ms / 11:40s
16.74ms / 3.40s
19.31ms /4,49s
25.28ms 5.12s
17.56ms 3.55
APPNP
17.16mns 4,00s
18.47mms / 6.29%
39.59mm / 20.00s
17.01ms 3.44s
16.32ms /4.04s
22.93mm 4.63s
15.96mn / 3.244
MI.
4. 4.14ms/ / 0.992
5.43ms 2.866s
5.33ms / 2.77s
3.41ms 0.699
4.84ms 0.98%
5. 5.19ms 1.05s
3.81 1.044s
SGC
3.31ms/ / 1331ss
3.81ms/3.88
4.36ms / 4.36s
3.13ms / 3.13s
3.98mss/ / 1.00s
4.79mms / 4.79,
2.86ms / 2.099
GCN
9.25ms
4.177
32.45ms 16.29%
13.83ms 2.79%
12.39ms 2.50s
27.11ms 5.56x
10.22ms/ 2.06s.
GAT
14.78ms
3.42s
21.52ms / 6.70s
61. 61.45ms/ / 24.28s
16.63ms / 3.63s
18.91ms / 86s
47.46ms / 10.05s
15 5.50mm// / 3.15
SAGE
12.06ms 2.44s
28.82ms / 6.32s
171.36ms/ 71.94s
171.
64.43ms 13.02s
27.95ms
5 6.65s
343.47ms
69.38s
6.08ms 1.288
JKNet
18.97ms 4444s
24.48ms / 6.61s
35.02ms 14,96s
20.03ms / 5.15%
23.52ms /4.55s
29.89ms 6.67s
19.67mms 4.01s
GCeyy
22.96ms /.75%
45.76ms 12.02s
218 118.82ms/ 196.8ss
89.41ms 18.06s
43.94ms 8.88s
440.55mms
88.99
12.34m 3.08
Efficiency analysis. We also examine the computational complexity of GNR- compared to other baseline models. We report the empirical training time in Table Compared to APPNP, we only need to learn K+1 additional GPR weights for GPR-GNN, and usually K < 20 (i.e. we choose K = 10 in our experiments). This additional computations are dominated by the computations performed by the neural network module fe. We can observe from Table 3 that indeed GPR-GNN has a running time similar to that of APPNP. It is nevertheless worth pointing out that the authors of Bojchevski et al.) (2020) successfully scaled APPNP to operate on large graphs. Whether the same techniques may be used to scale GPR-GNNs is an interesting open question.
6 CONCLUSIONS
We addressed two fundamental weaknesses of existing GNNs: Failing to act as universal learners by not generalizing to heterophilic graphs and making use of large number of propagation steps. We developed a novel GPR-GNN architecture which combines adaptive generalized PageRank (GPR) scheme with GNNs. We theoretically showed that our method does not only mitigates feature over- smoothing but also works on highly diverse node label patterns. We also tested GPR-GNNs on both homophilic and heterophilic node label patterns, and proposed novel synthetic benchmark datasets generated by the contextual stochastic block model. Our experiments on real-world benchmark datasets showed clear performance gains of GPR-GNN over the state-of-the th-the-art methods. Moreover, we showed that GPR-GNN has desirable interpretability properties which is of independent interest.
ACKNOWLEDGMENTTS
The work was supported in part by the NSF Emerging Frontiers of Science of Information Grant 0939370 and the NSF CIF 1618366 Grant.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, (11)):444666311 2017.
Sami Abu-El-Haija, Bryan Perozzi, Rami AI-Rfou, and Alexander A Alemi. Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems, pp. 9180-9190, 2018.
Sami Abu- Bou-EE-HHane Eljaa, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learn- ing, pp. 21-29, 2019.
Peter Battaglia, Jessica B Hamrick. Victor Bapst, Alvaro Gonzale, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 1806.0026..... 2018.
Dimitris Berberidis, Athanasios Nikolakopoulos, and Georgios B Giamnakis. Adaptive diffusions for scalable learning over graphs. In Mining and Learning with Graphs Workshop @ ACM KDD 2018, pp. 2018.
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Martin Blais, Amol Kapoor, Michal Lukasik, and Stephan Günnemann. Is pagerank all you need for scalable graph neural networks? In ACM KDD, MLG Workshop, 2019.
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464-2443 2020.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and lo- cally connected networks on graphs. In International Conference on Learning Representations (ICLR2014), CBLS, April 2014, pp. http-openreview, 2014.
Fan Chung. The heat kernel as the pagerank of a graph. Proceedings of the National Academy of Sciences, 104(50):19335-199)) 19740, 2007.
Hoang Dau and Olgica Milenkovic. Latent network features and overlapping community discovery via boolean intersection representations. IEEE/ACM Transactions on Networking, 25(5):3219- 3234, 2017.
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, pp. 3844-3852, 2016.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In Advances in Neural Information Processing Systems, pp. 8581-8592 2018.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.022
2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Vone Volume 70, pp. 1263-1272. JMLR. org, 2017.
David F Gleich. Pagerank beyond the web. Siam Review, 57(3):321 33)33331336,, 2015.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs.
In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th inter- national conference World Wide Web, pp. 271 271-279, 2003.
10

---

Published as a conference paper at ICLR 2021
Junteng Jia and Austin Benson. Outcome correlation in graph neural network regression. arXiv preprint arXiv:2002.08274, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.668 (eeii14126600 6980, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems, pp. 13333-13344 2019.
Isabel M Kloumann, Johan Ugander, and Jon Kleinberg, Block models and personalized pagerank. Proceedings of the National Academy of Sciences, (4(1))33-38, 2017.
Pan Li, Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed- expansion community detection. In Advances Neural Information Processing Systems, pp- 11705-11716) 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical 150-11700, 2011.
mechanics and its applications,
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based rec- ommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference Research and Development Information Retrieval, pp. 43-52, 2015.
Miller McPherson, Lynn Smith-Lovin, and James Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):415-444, 2001.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi Rad.. Collective classification in network data. Al magazine, 29(3):93-92 2008
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 108868, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehmar graph kernels. Journal of Machine Learning Research, 12(77):2539- 2561, 2011.
D. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending digh-diimnsional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013.
Charalampos Tsourakakis. Provably fast inference of latent features from networks: With applica- tions to learning social circles and multilabel classification. In Proceedings of the 24th Interna- tional Conference on World Wide Web, pp. 1111-1121, 2015.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova. Adriana Romero, Pietro Lia, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL hiRl:hhttts::/peereee net. fttt://frmmmmmmmmmmmmm wttp://wwwwe.eeooommeeeereooooe

---

Published as a conference paper at ICLR 2021
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395 416, 2007.
WOK Asiri Suranga Wijesinghe and Qing Wang. Dinets: Spectral cnns for graphs with feedback- looped filters. In Advances in Neural Information Processing Systems, pp. 6007-6018, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, Pp- 6861-6871, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462, 2018.
Zhilin Yang. William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volnme 48, pp. 40-48, 2016.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. International Conference on Learn- ing Representations, 2020.
net forum Pid wew.oruummd--JJe-eeeeee
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. General- izing graph neural networks beyond homophily. arXiv preprint arXiv:2006. / 1468, 2020.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey, Technical report, University of Wisconsin- Madisson Department of Computer Sciences, 2005.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 DETAILED DISCUSSION ON PREVENTING WVER-SMOOTHING.
As mentioned Section another method APPNP can also provably prevents over- smoothing Klicpera al. 2018 The authors of this study the fact that the PPR propagation will converge to p H where ppr a(I, (1 a) Aym) is independent on the node label information provided the training data. Each row of II ppr still depends on H))) and thus APPNP will not suffer from the over-smoothing effect. However, since ppr is independent of the
label information, it can cause undesired consequences that discuss what follows.
(a) A graph
(b) One example of label assignment.
(c) Another example of label
assignment.
Figure 5: A simple example demonstrating how GPR-GNN escapes over-smoothing.
Let us consider simple example shown in Figure 5 involving a connected and undirected graph (V, E) (Figure 5 (a)). Consider two different node label assignments shown in Figure (b)
and Figure (c). Obviously, the graph topologies depicted in Figure 5 (b) and (c) are identical and the only difference the class label assignment. In Figure (b), the graph is homophilic and hence the optimal graph filter should emphasize the low-frequeney part of the graph signal. In contrast, Figure (c), the graph is heterophilic as the graph is bipartite with respect to the labels. Hence, the optimal graph filter should emphasize the high-frequency part of the graph signal. This example illustrates that the optimal graph filter should depend on both the graph topology and the node label information. Recall that the equivalent graph filter that APPNP uses in the asymptotic regime is Pp which is independent on the node label information. Also, Theorem 4.1 established that APPNP intrinsically utilizes low-pass filter. In contrast, GPR-GNN learns the GPR weights guided by the node label information which allows it to account for both cases (homophilic and heterophilic) shown.
A.2 DISCUSSION ON THE INSUFFICIENCY OF HOMOPHILY MEASURE H(G)
(a) Case 1.
Casc
Figure 6: A simple example for explaining the insufficiency of homophily measure H(G). As mentioned in Section the homophily measure H(G) inadequate for characterizing whether heterophilic graph topology is informative not. Consider simple examples depicted in Fig-
13

---

Published as a conference paper at ICLR 2021
ure 6 where the color of the nodes indicates their label. In case 1, blue and green nodes link to all orange and purple nodes. In case 2, blue nodes only link to orange nodes and green nodes only link to purple nodes. From the definition of H(G) one can see that both cases have H(G) 0, since in both cases nodes do not link to other nodes of the same label. However, it is obvious that the graph topology carries more node label information in case 2 compared case 1. In fact, for case I it is impossible to distinguish blue and green nodes merely from the graph topology (and the same is true of orange and purple nodes). One possible alternative for the homophily measure is the Chernoff-Hellinger divergence Abbbe| (2177) of the empirical edge probability matrix B; here Biy the empirical probability of an edge with one end node labeled and the other labeled j. divergence charac-
The intuition behind our suggestion lies in the fact that the terizes the fundamental limit of SBMs. However, as many practical graph generative processes may significantly differ from SBMs, investigating alternative homophilyhheterophily measures is another interesting open problem.
A.3 PROOF OF THEOREM
We first state the formal version of Theorem 4.1
Theorem A.1 (Formal version of Theorem 4.1p. Assume the graph G is connected. Let A1 2 X2 2
2 An be the eigenvalues of A Asym- 7 2 0 Ak E {0, 1,.., K), Ek= T = and Ek' > 0 such
that "we > O, then 19y,K (>e)/ (A1)l < A An Vi 2 2. Also, ik = (-a))* . E (0, 1) and
K- + oG, then lim K ( limg- 9 K (At)l > |A./1I Vi 2 2.
Note that (A.))(()) (An) < [A/Aai Vi 2 2 implies that after applying the graph filter Ky.K. the lowest frequency component (correspond to X1) further dominates. Hence 9-.K acts like a low pass filter in this case. In contrast, |limx Ir.K (A:)/ limx 9r.k (A1)) > /Ar/Ail Vi 2 2 implies that after applying the graph filter, the lowest frequency component (correspond X1) no longer dominates. This correspond to the high pass filter case.
Proof. We start with the low pass filter result. From basic spectral analysis (Von Luxburg 2007) we know that a 1 and |Ai < 1, Vi 2 2. One can also find the analysis in the proof of our Lemma A.2 in the Supplement. Then by assumption we know that
K
9-.k (A1) =
Σ 7 = 1.
R=
Hence, proving Theorem A.1 is equivalent to show
107, (As)) < |A Vi 2
This is obvious since x (A) EK ThA 2 is polynomial of order K with nonnegative coeffi- cients. It easy to check that Vk 2 DAI* < |/A 1. Combine with the fact that all ' 's are nonnegative we have
9 (A,k
S
Σ
Σ k=
R
Σ k=
7h 7A = IaI.
k=
Finally, note that the only possibility that the inequality (a) holds is " = 50,K since Vk 2 1, |\| <
[*], AIAA < 1. However, by assumption Ex= 7 = 1 and 3K' > 0 such that y >> 0 we know that this is impossible. Hence (a) is a strict inequality <. Together we complete the proof for low pass filtering part.
For the high pass filter result, it is not hard to see that
K
K Σ
lim 0r.K (A) = lim
x
lim
(a))*
K
K
K
1 Itad
k=
k=
where the last step is due the fact that (0, 1) and thus lim
=0 - 1. Thus
we have
lim Hn (At)
1 1 a
(6) (c)
>
$12
|. 22
lim oo In.K (A1)
aA;
14

---

Published as a conference paper at ICLR 2021
Both strict inequalities (b) and (c) are from the fact that |A,| < 1, 2 2. Notably, supxe(1.-1) 1+a happens at the boundary À -1, which corresponds the the bipartite graph. It further shows that the graph filter with respect to the choice * = (-a)* emphasizes high frequency components and thus it is indeed acting high pass filter.
A.4 PROOF OF THEOREM
We start by introducing some additional notation, lemmas and definition before we proceed to the formal statement of Theorem 4.2 The label matrix denoted by Y R where each row is one-hot vector. We use 1 E -. to denote the argmax of the vector B E æ²; we have [ and only if 33 = max(33 (ties are broken evenly), and 1[3]; softmax(-) with softmax,,.), where we let softmax,(33;
otherwise. Let us replace the e /2,, eni3) stand for the softmax with smooth parameter 17 > 0. Note that for 1 = 1 we recover the standard softmax. With slight abuse of notation, for the vector we write exp(3) to denote element wise exponentiation. We use ( > to denote the standard Euclidean inner product. Also we use I. for the cross entropy loss where
L - logg( (ee(PPr..) Y:))
&EV
Lemma A.2. Assume that the nodes in an undirected and connected graph G have one of C labels. Then, for k large enough, we have
VD V EvEE D
H (b) .j oz( Vj E (C], where n.
and B² 7 (o)
(2)
For any (0) and large enough k S K, if the label prediction is dominated by (a),, all nodes will have a representation proportional to 3.B. Hence, we will arrive at the same label for all nodes. This is what refer to the over-smoot phenomenon.
Definition A.3 (The over-smoothing phenomenon). First, recall that Z E. Yh H If over- smoothing occurs in the GPR-GNN for K sufficiently large, we have Z,j = C Vj E [C] some Co > 0 if Y
and Z,j- = ,, VjE [C] some co > 0 if
Lemma A.4. Let I, = EiET I, Ever-log(( (P (P...))))
Yz:)) be the cross entropy loss and let T be
the training Under the same assumption given in Lemma A.2 the gradient of "Bs for k large OL = EVET (P:.- Yv. (P:-Yu.P3 (1).
enough is T%
Lemma A.5. For any real vector B B.C and n large enough, have softmax,,() 1 + (1).
Now we are ready to state the formal version of Theorem 4.2
Theorem A.6 (Formal version Theorem 4.2). Under the same assumptions as those listed in Lemma A.2 if the training set contains nodes from euch class, then the GPR-GNN method can always avoid over-smoothing. More specifically, for ki 1J large enough we have
ØL
Σ n,; RET
max 3, - -BI + +1x when 7hk > 0. .E(C]
(3)
OYk
aL
Σ m|;;;
min 3, -BIpY.) jE[C]
+ +1) when 7 < 0.
o
(4)
0Tk
TET
Note that when 76 > 0, 3 O when ignoring the o(1) term. The equality is achieved if and only if maxje[c] 33 B1 This means that over-smoothing results in prediction that perfectly aligns with the ground truth label in the training set. However, if our training set contains at least one node from each class then the equality can never be attained. Thus, the gradient of 7 will always be positive when Y 0. Similarly when 7 < 0, (4) when ignoring the o(1) term. The equality achieved if and only if minjeicy B3 = Biyy: By the same reason we know that under the assumption training set the equality can never attained. Thus, the gradient of 7 will always
15

---

Published as a conference paper at ICLR 2021
be negative when > < O. Finally, it is not hard check that the gradient is bounded in magnitude. Together we have shown that the gradient of "/k and 7/8 are of the same sign. This directly implies that 17 will approach to 0 until we escape from over-smoothing when rate for the optimizer (i.e. SGD).
decreasing learning
Proof. First, let assume the over-smoothing takes place and the Y > for the dominate term. By Definition A.3 we know that Z:j = Co vj E [C] for some > 0 and K sufficiently large. By Lemma we have
aL 0yk
Σ nπt
Y2,
+ +xx(1)
(5)
Σ jElcy en
iET
e
Σ ET
1
Σ Ejelo e
Y
+ +ox(1),
(6)
where the last step follows from Definition softmax, by the true argmax for
Next, by Lemma
A.5
we may approximate the
0 large enough according to
Σ
mmm (1 Y B) + +1( (1)
RET
Σ y7l (1[3) Y.:. 33 + ox() +
(8)
iET
Σ
max
3, Bi(y..) + o (1).
[JE[C]
iE
The first equality is due to the fact that co > 0 and π. > 0. Recall that by Lemma A.2 n
VD., Since we have self- loop for each node, D 0 and thus π, 0. For the case
V V.err D..
Tk < 0, the same analysis still valid until 77 Hence have
Σ
cu Y., +1x(1) + (1)
(10)
NE
Σ
1771; (1|-3) Y.: + ox + (1)
(11)
iET
Σ
min 33 - 31(x.1) + (1) (1)
(12)
JE[C]
NE
Together we complete the proof.
A.5 CSBM DETAILS
The cSBM adds Gaussian random vectors as node features on top of the classical SBM. For simplic- ity, we assume C equally sized communities with node labels v; (+1, Each node associate with a f dimensional Gaussian vector b, /. 2, v/ where n the number of nodes,
N(0, I/f) and Z; R! has independent standard normal entries. The (undirected) graph in cSBM is described by the adjacency matrix A defined as
d Ava
if 0:0; > 0 otherwise
P (A. =) =
Avdd
Similar to the classical SBM, given the node labels the edges independent. The symbol d stands for the average degree of the graph. Also, recall that and control the information strength carried by the node features and the graph structure respectively.
One reason for using the cSBM to generate synthetic data is that the information -heorreti limit of the model is already characterized in Deshpande et al. (018). This result is summarized below.
16

---

Published as a conference paper at ICLR 2021
Theorem A.7 (Informal main result in Deshpande et al. (2018)), Assume that n. - 00, 3 -
-000,
and d cc. Then there exists an estimator ē such that lim inf inf,- 200 and only if x2 + n² 1.
Ra,ell is bounded away from
In our experiment, set 5000, f 2000 and thus have ç 2.5. We vary μ and À along the are X + /²/5 = 1 + e for some e > 0 to ensure that we are in the achievable parameter regime. We also choose 3.25 for all our experiment.
A.6 PROOF OF LEMMA A.2
Note that the proof of Lemma A.2 reduces to a standard analysis of random walks graph. We include it for completeness and refer the interested readers to the tutorial Von Luxburg (2007).
We start by showing that the symmetric graph Laplacian
L Laym 1 1 D-
1/2 A- 1/2 = I- Asym
(13)
positive semi-definite. Let u be any real vector of unit norm and f f D-1122 then we have
n
u Lyym't = x - u 1/2 AD
1/2
Σ
U
Σ
fij
(14)
i=1
1J=1
D Duf Σ
fuffA.j = 1
Duf -2 Σ
fify Au + Σ
D
(15)
1=1
$,=1
1=1
41=1
j=1
A 11)
(16)
where the last step follows from the definition of the degree.
Next we show that is indeed an eigenvalue of Lyy associated with the unit eigenvector æ where VD.
VE. Dos
Let be the all one vector. Then, a direct calculation reveals that
L Lym π - -D-1/2 1/2
D 1/2
AD
1/2D1/11
1/2
x
(17)
Ex
D R0
1-1/2Ā1 Ā1 x
1/1
D1
1
(18)
Σ D m
V Σ, D
DV
1
0.
(19)
Σ D D2
Combining this result with the positive semi- property of the Laplacian shows that 0 indeed
the smallest eigenvalue of Lyym associated with the cigenvector л. Moreover, from (16) and the assumption that the graph connected, it is not hard see that the multiplicity of the eigenvalue is exactly 1 (See Proposition 2 and 4 in Von Luxburg (2007) for more detail). Finally, from (13) it is obvious that the the largest eigenvalue of Asym is 1, which correspond to the eigenvector π. Hence all other eigenvalues of Agym > X 2 ... Xn-
17

---

Published as a conference paper at ICLR 2021
Next, we prove that Pa,l < 1. This can also be shown directly from T6p. Note that
T
Lyym
L
U
Σ
Aús(i 15) 13)
(20)
1,=1
0f + ff) = Σ
Aust = Σ
A
(21)
Da
1==1
+/=1
2
Σ j=1
Ag = Σ 1=1
D 11 2 Σ
2 2.
(22)
1=1
x=1
The inequality follows from application of the Cauchy-Schwand inequality. Consequently, the largest eigenvalue of Lsym is bounded by 2 which means that Ah, I 1. Note that equality holds and only the underlying graph is bipartite. However, this is impossible in our setting since we have added self loop to each node. Hence Aa1 1. This means
lim A sym ππ
(23)
k
Hence, for any O have
lim
A sym
H
क: T ( TT.T.
(24)
k-+00
Note that this can also be written with the (1) term as
k sym
H
-T 0z)
(25)
This completes the proof.
A.7 PROOF OF LEMMA
Recall that our loss function equals
log( (Zu... vo)
L
(26)
Dr en7tmm
iET
EET
Then by taking the partial derivative of the loss function with respect to the we have
E
(log( Σ
Eeizim) (iiim ) (1i Y.)).
(27)
Oyk
Next, recall that for GPR-GNN also have Z previous formula and applying the chain rule we obtain
Ei=o Th ((), Plugging this expression into the
Zim On Byy
Em=l
(log(
(n
Y(t)
(1 (k')
Va))
(28)
One
===1 cz
iET
m=1
ET
H (K')
(
(K))
Y::)
(29)
2m
7m
1ET
Settin K6 = for large enough k, it follows from Lemma A.2 that
aT.
Σ m
- e (A))
(H!*), (k) x.:))
(30)
O7k
Dim eni
iET
D Dm=1 e (T.B +ox(1)
(T, + (1),,, Y.))
(31)
iET
Z m=
Bm
Σ mimp
(32)
m==1 Cn
iET
Σ
T
P im LmmBm - Y,)) (1) = Σ 177; (p +o(().
+
(33)
iT
m=1
GET
18

---

Published as a conference paper at ICLR 2021
Note that in (2) and (33
we used the definition of the soft prediction P softmax, (Z). This
completes the proof.
A.8 PROOF OF LEMMA
Let 3 max(3). Then by the definition of softmax, for v > 0 we have
e/
e e-1(3-8)
softmax,,(3)
(34)
2 mmml en
C
mmm1 e e-n(ß-8...
Note that 3 - B... > O when 3m # B and B 3. 0 when 3m B. Without loss of generality we assume that there are p maxima in 3. where S p S C, and let P denote the set indices of those maxima. Then, taking the limit 77 + oo have
c-n(8-3,)
0,
if Bf 3 otherwise.
lim softmax,, (3), 9-+00
lim 7-+00
(35)
Empp e 11330(1-80 Bm) +p
p
This implies that for 1) > large enough one has
softmax,, (B) = 1[3] o,)
(36)
The above result completes the proof.
A.9
ADDITIONAL EXPERIMENTAL DETAILS
Table 4: The values of the homophily measure for cSBM datasets.
-0.75
-0.5
-0.25
0
0.25
0.5
0.75
H(G)
0.001
0.002
0.009
0.029
0.077
0.189
0.419
0.688
0.809
All experiments are performed on Linux Machine with 48 cores, 376GB of RAM, and NVIDIA Tesla P100 GPU with 12GB of GPU memory. For the training set, we ensure that number of nodes from each class is approximately the same an keep the total number of training nodes close to 2.5%/60% For the validation set, we randomly sample 2.5% 222%% of the nodes and place the remaining ones into the test set.
For all baseline models, we directly use the implementation available in the Pytorch Geometric library Fey & Lenssen (2019). We use early stopping 200 and maximum number of epochs equal to 1000 for both real benchmark dataset and our cSBM synthetic datasets. All models use the Adam optimizer Kingma & Ba (011)). Note that the early stopping criteria is exactly the same as in Pytorch Geometric when the epoch is greater than half of the maximum epoch, we check if the current validation loss is lower than the average over the past 200 epochs. it is not lower, we stop the training process.
For GCN, we use GCN layers with 64 hidden units. For GAT, we use 2 GAT convolutional layers, where the first layer has 8 attention heads and each head has 8 hidden units; the second layer has attention head and 64 hidden units. For GCN-Cheby, we use steps propagation for each layer with 32 hidden units. Note that the number of equivalent hidden units for each layer is64 for this case. For JK-Net, we use the GCN-based model with 2 layers and 16 hidden units in each layer. As for the layer aggregation part, we use LSTM with 16 channels and layers. For the MLP, we choose a 2-layer fully connected network with 64 hidden units. For APPNP we use the same 2-layer MLP with 10 steps of propagation. Besides the GPR-GNN, we fix the dropout rate for the NN part to be 0.5 as APPNP and optimize the dropout rate for the GPR part among {0, 0.5, 0.7 For Geom-GCN, we choose the datasets already tested the paper were the method was first described (Pei et al., 2019). For SGC, we use the default K 2 layers after test among {2, For SAGE, use SAGE convolutional layers with 64 hidden units.
The heterophilic datasets used in (Pei et al. 2019). The graphs Chameleon, Actor, Squirrel, Texas and Cornell in their original form are directed graphs (see the github repository of (Pei et al.) 2019). ). Since the usual setting for remi-supervised node classifications involves undirected graph, trans- formed the graphs into undirected to test them on all previously described benchmark methods. We keep the input graph directed for Geom-GCN as the method uses fixed preprocessing scheme that
19

---

Published as a conference paper at ICLR 2021
was unfortunately not made public by the authors. Our homophily measure values H(G) in Table are all based on undirected graphs and hence the numbers are different from those reported in (Pei et al. 2019).
A.10 ADDITIONAL EXPERIMENTAL RESULTS
Table Results for cSBM, sparse splitting. Bold values indicate the best obtained result and while bold, underlined values indicate results within a 95% confidence interval with respect to the best result.
0.75
0.5
0.25
0
0.25
01.5
0.75
GPRGNN
97.19
05.54_0.15
81,54.1073
60.6510.31
62.16-0.23
68.83
89.31
96.9810008
10.
GPRGNNGandom)
88 331331
88.5413.01
66.9112993
56.35
08.09
64.01 1.39
81.93:1:668
94.59.1.29
93.69111.8
APPNP
49.57=0.11
52.45-0227
56.32440.40
59.55-40.44
94.37=+0.09
90.02
MLP
49.88=00100
53.40=0.34
$7.14+041
60.55+00.11
62.15-0.33
61.26-00.21
$7.91
53.36=00.32
49.92+t0.11
54.4120337
59.74=0029
55.57:1033
51.84+0.25
65.65=0.27
85.51
93.99
GCN
55 05.24:10.35
61.04
56,40:1:039
52.23-1:0.44
54,43:00.32
67.23:10:29
84.56:1:020
90.19:10144
78.67:10.0
GAT
53.97
57.18
53.39:1:34
$1.23-1.0199
53,26:00277
64.45
81.94:10.44
88.45:10.26
78.061:0.30
SAGE
62.30=00.0
75.10=0.50
72.8440044
63.88-00377
58.62-0030
63.55+0047
73.50++0.00
75.26+00.2
62.61 +:0.4
JKNet
51.70:10.39
55.83:10.75
52.67:10.51
50.27:10.15
52.02:10335
63.67
86.35.10.19
95.13:10.00
90.32210.17
GCN-Cheby
61.44=00.51
59.70=0034
73.56-+0.65
Table 6: Results for cSBM, dense splitting. Bold values indicate the best results found while bold, underlined values indicate results within a 95% confidence interval with respect to the best result.
0.75
0.5
-0.25
0.25
0.5
0.75
GPRGNN
98083:10006
98.19=00008
94.23-10.14
86.06:10.20
82.22-00.20
8..48
94.34:10.13
98.46110.08
98.84110.66
GPRGNNcandom)
08.75:00005
98.08 0.08
94,22 00.14
86.06.10.20
81.57 0.23
86.36 0.20
94.09:10.14
98.38 10.08
98.77
APPNP
73.30-4026
94.20-20.14
ML.P
49.79=0.29
6.269=0027
05.36-
50.30=00.4
82. 02.19:0.22
80.88
76.07=00224
66.61
49.65-20.22
78.95=00.23
81.79=0024
15.05::225
59.40:10.28
63.75=00226
1:.22
93.04:0015
98.05-20:88
80:00.00000
GCN
78.50=00.28
83.68=0.22
75.98-4025
59.98-20.25
64.09=0.26
81.88 01.19900119
93.9110.12
97.78=20.08
96. 06.29:1:011
GAT
82.39::041
80.37=20.22
71.01:1026
57.68:10.2
62. 22.95_20.28
80:61 0.004
93.26.0 14
97.99
98.40::0:0
SAGE
91.33:10:23
95.72:10112
93.23:10.17
84.52:10.20
78.99-0.24
84.87.10.20
92.90.10.15
95.75.10.1
91.19100244
JKNNt
96.11
95.33-0025
87.98
59.61:40.89
63.28
80.23-6-00
93.28 8.115
98.33-+0007
98.22 08.22--0000
GCN Cheby
90.94-00116
94.82-20155
91.83:40.17
15.18400.11
80.80=00255
92.70:10.16
95.06.20.13
90.34+00118
Table 7: Results on homophilic real-world benchmark datasets tested (Pei et al. 2019), dense splitting: Mean accuracy (%) + 95% confidence interval. Boldface values indicate the best results found while boldface, underlined values indicates results within the confidence interval with respect to the best result.
Cora
Citeseer
PubMed
GPRGNN
$8.65-0.28
80.01 =:
09.1
88.11:033
00.5
0.
MLP
76.44:1.30
76.25:10:28
0.
SGC
86.58-+0.26
76.23-4-0.99
83.52-+0.10
GCN
86.87:40.25
79.28-t-22
0..97
GAT
87.52:10.34
80.56:10.31
86.64-20111
SAGE
86.58.10.26
78.24:10.00
86.85.10.11
JKNet
86.97-00277
37.69-1:35
87. 07.38:20.13
GCN-Cheby
86.46110.26
78.66:1:0.26
08.2990.09
GeomGCN
85.4-1-.26
76.42.10.77
88.51
20

---

Published as a conference paper at ICLR 2021
<SSK in A.deoseeerrddde
CSEMA 2i.dera.iitrrdddnn
CSMM
644
035
61-
(Rcp)
(Stop)
(a)
cSBM = 0.0, (H( 0.077)
(b)
cBM, 0.25,
(c)
cSBM Φ = 0.5.
(H 0.189)
(H(G) = 0.419)
12-
61
(d)
cSBM, 0 0.75. (H(G) 0.688)
(c)
cSBM, Φ 1.0.
cSBM, -0255.
(H{()) 0.809)
(Hl()) 0.029)
CS -iddeenneeoneeeeeeenn
<54Mg Jddessitttrrnde
1.0
0.5
MW
MWV
025
50
-825
-.50
47
-175
-18
cste))
(depp)
Esteg)
(g)
cSBM, Φ -0.5. (H(G) 0.009)
(h)
cSBM, 6 -0.75. (H(()) 0.002)
(i)
cSBM Φ = ----100 -1.0.
(H(G) = 0.001)
Figure 7: Figures (i)-(i) show the learned GPR weights by GPR-GN GNN with random initialization on cSBM, dense splitting. The shaded region indicates 95% confidence interval.
Table 8: Additional experiments illustrating that GPR-GNN escapes over-smoothing. We initialize the GPR weights "A ỘεK as described in Section We report the mean accuracy at Epoch 0 and after training (Final epoch). The over-smoothing ratio indicates how many time out of the 100 runs that
started with lead to the same label for all nodes. For an illustration of how GPR weights change over different epochs, please check Figure 9
Accuracy at epoch 0(%)
Accuracy at the final epoch(%6 %))
Over-smoothing ratio %%)
Cora
12.75
88.25
84
Computers
9.41
85,93
Squirrel Texas
19.87
52.06
97
21.05
90.05
100
21

---

Published as a conference paper at ICLR 2021
denee neght
Chose: cenas weght
Poblled wrimmandemeeenn nuight
678
60
646
10-
066
694
65
(Step)
(stept
(a) Cora,
(H(G) = 0.656)
(b) Citeseer,
(Hi(G) = 0.578)
(c) PubMed,
(H[ - 0.644)
Compptessseecciitterrreeeeeeemee weiet
meatoueenseittereerrrtne ore waght
30
15-
10-
50-
-55
(step)
(step)
(d) Computers.
(e) Photo,
(H(()) 0.459)
(f) Chameleon.
(H(G) 0.272)
(H(G) = 0.024)
mrassdenseejttooedddaee weight
-00
(xtep)
Extepp
Extep)
g
Actor,
(H(G) 0.008)
(h) Squirrel,
(H(G) 0.055)
Texas,
(H(G) = 0.016)
Cornell dence inturnnndon leame (PRt weight
k (stpp)
(i) Cornell,
(HL(G = 0.137)
Figure 8: Figures (a)-() show the learned GPR weights by GPR-GNN with random initialization on various benchmark datasets, dense splitting. The shaded region indicates a 95% confidence interval. Note that the leamned GPR weights are all positive for every homophilic dataset. There is at least one negative learned GPR weight for every heterophilic dataset.
22

---

Published as a conference paper at ICLR 2021
(a) Cora, epoch 0
(b) Cora, epoch 50 (c) Cora, epoch 100 (d) Cora, epoch 150 (c) Cora, epoch 200
(f) Computers, epoch 0
g
Computers, epoch 50
(h) Computers, epoch 100
(i) Computers, epoch 150
Computers, epoch 200
VW
MW
(k) Squirrel, epoch 0
(I) Squirel,, epoch 50
(m) Squirrel, epoch 100
(n) Squirel, epoch 150
(o) Squirel, epoch 200
(p) Texas, epoch 0 (q) Texas, epoch 50 (r) Texas, epoch 100 (s) Texas, epoch 150 (t) Texas, epech 200
Figure 9: Learned GPR weights by GPR-GNN with initialization 7/ δд (last step) various benchmark datasets, dense splitting. The shaded region indicates 95% confidence interval. Also, please check Table 8 Note that the GPR weights {r are identical to {-7k HK in terms of graph filtering.
Table 9: Efficiency on homophilic real world benchmark datasets: Average running time per epoch(ms)\average total running time(s).
Cora
Citeseer
Pubmed
Computers
Photo
GPRGNN
17.62ms 3.74s
19.28ms / /3899s
20.19ms 5.553
39.93ms 11.40s
21.61 / 6.18s
APPNP
17.16ms 4.00s
15.97ms 3.266
18.47ms 6.29s
39.59ms / 20.00s
20. 10ms / 10.93s
MLP
4.14ms / 0,92s
5.30ms / 1.13s
5.43ms / 2,86s
5.33ms / 2.77s
4.63ms / 2.72s
SGC
3.31ms 3.31s
11.45ms 2.31s
3.8 / 3.81s
4.36ms / 44366
19ms 8.75s
GCN
9.25ms 1.97s
17.46ms 3.533
14.1 4..
32.45ms 16.29s
32.56ms 11.33s
GAT
14.78ms 3,42s
19.94ms 4.47s
21.52ms 6.70s
61.45ms 24.28s
24.57ms 11,61s
SAGE
12.06ms 2,44s
41 41.40m// 8,36s
28, 18.82ms/ 6,32s
171.36ms / 71.94s
108. 88ms / 42,
JKNet
18.97ms /4.41s
3.99ms / 3,99s
24.48ms 6.61s
35.02ms 14.96s
3.66ms / 3.66s
GCN-cheby
22.96ms /.755s
23.16ms / 4.688
45.76ms 12.02s
218.82ms 96.58s
82.38ms 30.48s
23

---

Published as a conference paper at ICLR 2021
MM
(a) Cora, epoch
(b) Cora, epoch 50 (c) Cora, epoch 100 (d) Cora, epoch 150 (c) Cora, epoch 200
(f) Computers, epoch 0
(g) Computers, epoch 50
(h) Computers. epoch 100
(i) Computers, epoch 150
Computers, epoch 200
W
(k) Squirel, epoch 0
(I) Squirell, epoch 50
(m) Squirrel, epoch 100
Squirell epech 150
Squirrl epoch 200
(p) Texas, epoch 0 (q) Texas, epach 50 (r) Texas, epoch 100 (s) Texas, epoch 150 (t) Texas, epoch 200
The dynamics of learning GPR weights with random initialization on various benchmark datasets, dense splitting. The shaded region indicates 95% confidence interval.
Figure 10:
Table 10: Efficiency on heterophilic real world benchmark datasets: Average running time per epoch(ms)/averagee total running time(s).
Chameleon
Squirrel
Actor
Texas
Cornell
GPRGNN
16.74ms / 3.400s
25.28ms /5.12
19.31ms / 44.49s
17.56ms 3.555
18.42ms / 3.72s
APPNP
17.01ms 3.44s
22.93ms / 4.63s
16.32ms / /4.04s
15.96ms 3.24s
14.66ms / 33099
MLP
3.41ms 0.69s
5.19ms 1.05s
4.84ms 0.98s
3.81ms/ 1.04s
3.46ms / 0.89s
SGC
13.83ms 2.79s
27.1 5.56s
12.39ms 2.50s
10.22ms 2.06s
10.38ms 2.10s
GCN
16.63ms 3.63s
47.46ms 10.05s
18.91ms 3.86s
15.50ms
3.13s
13.67ms 2.76s
GAT
20.03ms / 5.15s
29,
19,89ms// 6.67s
23.52ms / /4.55s
19.67ms /.00ls
19.35ms /,91s
SAGE
89.41ms 18.06s
440.55ms 88.99s
43.94ms 8.88s
12.34ms 3.08s
12.15ms 2.69s
JKNet
3.13ms 3.13s
4.79ms 4.79s
3,98ms 1.00s
2.86ms/ 2.09s
2.81ms 1.18s
GCN-cheby
64.43ms 13.02s
343.47ms 69.38s
27.95ms 5.65s
6.08ms 1.28s
6.05ms 1.44s
24


Reviews:
[{"review_id": "TdgQqcQmTq5", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed a generalized pagerank version of a graph neural network (GNN). The authors learn a weighted combination of higher powers of the graph adjacency matrix, with the weights themselves being learnable. This allows their method to generalize existing GNN methods that work well when there's graph homophily, but not in the case of heterophily. The proposed method reduces to existing cases under certain weight settings, but in other cases, the learned weights allow for the GNN to act as a \"high pass filter\", which existing methods do not do. By learning these weights, the authors can also go deeper in the graph, and aggregate information from several hops away. Experiments on several standard datasets show that the proposed method outperforms multiple baselines. \n\nThe paper is clearly written. My main concern is the overall novelty of the paper, with respect to ICLR. Unless I'm missing something, the main point the authors are making is to learn the weights of the decomposition, and show that by making those weights learnable, good things happen when compared to the methods in Klicpera et al, and Wu et al.  Just that to me is not grounds for strong acceptance. \n\nminor comments:\npage 2: you keep using the term \"large step propagation\" several times, without actually defining what that means. \n\nThm 4.1: is there a formal version of this theorem with a proof? if not it's probably not fair to call it a theorem. \n\nplease make the text in figures 3 and 4 larger. It's hard to read. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EWmYzixbw2g", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new GNN architecture based on Generalized PageRank to handle two weakness in some existing GNNs: the difficulty of neighborhood aggregation on heterophilic graphs, and the oversmoothing problem when stacking GNN layers. The proposed GPR-GNN can be viewed as an extension of the Personalized PageRank-based GNNs, such as APPNP and SGC, which also aimed to handle oversmoothing problem. Pros:  The paper highlights and clearly explains why optimizing the proposed layerwise GPR weights in GNN could tackle the two challenges. Although the final GPR-GNN architecture is simple, the ideas behind are significant. The paper is technically sound. The paper clearly analyzes the differences and relationships between related prior works and the proposed approach. In experiment, datasets are sufficient, including both homophilic and heterophilic graphs (both synthetic datasets and 10 real benchmarks are sufficient) which proves that GPR-GNN can achieve state-of-the-art performances especially on heterophilic graphs.\nCons:\n* Baselines: The paper compares GPR-GNN with the state-of-the-art APPNP, a Personalized PageRank-based GNN. However, it also mentions SGC as another most related work based on PPR, but does not use it as a baseline. \n* Since the GPR-GNN only have one set of NN parameter \\theta in the first layer, and other layers do not have such feature transformation parameters, maybe add more efficiency analysis would be better, since APPNP also has efficiency analysis.\n* There are five heterophilic benchmarks. The performances of GPR-GNN on Chameleon and Squirrel are impressive, but GPR-GNN actually does not \"significantly outperform\" APPNP on Actor, Texas and Cornell datasets, which contradicts the claims. More discussions about this would be better. If it is due to other statistic differences between heterophilic benchmarks, it is necessary to mention them in Table 1.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5wSUoP8Ado-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper proposes a new neural net architecture based partially on the previously proposed Generalized\nPageRank (GPR). The model adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction. The main advantage of  this approach is that -- unlike previously proposed GCNs -- this approach works well for both homophilic and heterophilic graphs (due to the use of GPR). This allows for e.g. node classification without a priori knowledge about the type of graph at hand. Additionally, this approach avoids feature over-smoothing, a known problem in GCNs. \n\n############\n\nI recommend this paper for acceptance due to its novelty and its algorithmic contribution. I really enjoyed reading it. \n\n############\n\nPros\n+ A very interesting approach with useful practical implications for a node classification of both both homophilic and heterophilic graphs. \n+ Very clearly written and well articulated. \n+ Great literature review of related topics in the area of GCNs. \n\n############\n\nCons/Suggestions \n- I found the explanation of GPR in the beginning of Sec 3 a bit confusing. Please rewrite to add a bit more detail (e.g. what is gamma?), I had to consult the original  paper to understand the notation here. \n \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-CvoT27A0E-", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper Summary:\n\nPaper summary:\nThis paper attempts to incorporate generalized page rank (GPR) in Graph Neural Networks (GNNs), aiming to address two problems plaguing GNNs: i) Existing message-passing based GNNs are best suited to handle graph-structured data with the homophily property and may not be able to handle those with the heterophily property. ii) Existing GNNs suffer over-smoothing which force them to be \"shallow.\" The key idea of GPR is to introduce a weight factor $\\gamma_k$ in the kth iteration of computing the page rank score. The authors conduct extensive evaluation using bencmark datasets, and show improvements over some existing GNN methods.\n\nPros:\n  + Attempt in addressing the potential limitations of message-exchange based GNNs that may not be suited to deal with graph datasets with heterophily relations.\n  + Evaluation using both synthetic data based on  contextual stochastic block models (cSBM) and real-world \"heterophily\" datasets.\n\nConcerns:\n\n  - The paper starts by talking about the \"trade-offs\" between node features and graph topology. However, the bulk of the paper is focused on using GPR as a more \"general\" graph filter as in the \"standard\" GNNs. The latter in recent years, unfortunately, since the work of Kipf & Welling, have primarily used variants of a simple graph of the form I+A.  Based on the GPR-GNN model shown in Fig.1, the node features {X_i} are only used to initialize H^{(0)}. In other words, the node features do not factor into the choice (or learning) of \\gamma_k's in the latter stage.\n\n - One would assume that where a graph or network is \"homophily\" or \"heterophily\" would be in some matter encoded in the node features, apart from the network topology. In other words, the same network topology may appear in both homophily and heterophily datasets. [This might not be true in practice: one might imagine that heterophily datasets might likely contain bi-partite or multi-partite structures than homophily datasets.]\n\n - From a theoretical point of view, GPR as used in the paper does not really provide a trade-off between node features and graph topology. As a \"polynomial graph filter\", the parameters {\\gamma_k} simply \"modulate\" the eigenvalues. In particular, if  {\\gamma_k} (as an infinite sequence) is convergent,  the series \\sum_k \\gamma_k --> \\gamma, then \\sum_k \\gamma_k A^k --> (\\gamma)(I-A)^{-1}  (assuming A is normalized, the dominant eigenvalue is less 1), A^kH^{(k)} would converge to the eigenvector  (a normalized node degree vector) associated with the dominant eigenvalue, thus independent of the initial vector H^{(0)} that derives from the node features {X_i}.\n\n - Of course, the paper uses a fixed K power iteration (instead of letting K goes infinity). The issue of oversmoothing comes from when K is large, the \"dominant\" eigenvector takes over the \"graph structure\". I am not convinced that GPR helps either address the heterophily or the oversmoothing issues of GNNs. The use of GPR is motivated by the reference [Li et al 2019] \"Optimizing Generalized PageRnak Methods for Seed-Expanision Community Detection\". However,in [Li et al] GPR is used for community detection, where \"homophily\" is actually assumed. Note that stochastic block models (SBMs)  are fundamentally graphs with \"homopily\"  where nodes are likely to connected with nodes within the same community. \n\n - All in all, GPR is yet another way to compute some \"centrality\" or ranking among the nodes. It does not fundamentally capture the structural (local or global) properties of graphs. There are other (perhaps \"better\" metrics, see, e.g., the paper \"Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs\" (NeurISP 2017), which is used to develop a Graph Capsule GNN. Unfortunately, some of these metrics are more computationally expensive to compute for large graphs.\n\nOther comments:\n - As an aside, one can in fact absorb the parameter \\gamma_k as part of the weight vector $W^{(k)}$ to be learned during the  kth-layer of the GNN. I believe that this might be the advantage gained by GPR-GNN, where in many existing GNNs the weight vector $W{(k)}$ is re-used (i.e., the same weight vector is often used in different layers). In GPR-GNN, the learned weight vector is rescaled by \\gamma_k. \n\n- The theoretical results in Section 4 in terms of \"graph filters\"  are largely well known, see, the survey paper by Michael M. Bronstein et al, \"Geometric deep learning: going beyond Euclidean data.\" IEEE Signal Processing Magazine, 2017.\n\n- I am curious about the specific GNNs that you used to compare with your method, besides Geom-GNNs. There are many other GNNs, e.g., GIN, SAGE that are not chosen for comparison. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a new GNN architecture based on Generalized PageRank to handle two weaknesses in some existing GNNs. The novelty of this approach is that it works well for both homophilic and heterophilic graphs (due to the use of GPR).

Overall the paper is interesting and well written. Moreover,  the authors addressed the concerns of reviewers during the rebuttal period. Thus, I vote for acceptance.
Decision: Accept (Poster)