Simplified Graph Convolution with Heterophily
Authors: Sudhanshu Chanpuriya
Cameron N Musco
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph
network
convolution
homophily
heterophily
disassortative
classification

Abstract: Recent work has shown that a simple, fast method called Simple Graph Convolution (SGC) (Wu et al., 2019), which eschews deep learning, is competitive with deep methods like graph convolutional networks (GCNs) (Kipf & Welling, 2017) in common graph machine learning benchmarks. The use of graph data in SGC implicitly assumes the common but not universal graph characteristic of homophily, wherein nodes link to nodes which are similar. Here we confirm that SGC is indeed ineffective for heterophilous (i.e., non-homophilous) graphs via experiments on synthetic and real-world datasets. We propose Adaptive Simple Graph Convolution (ASGC), which we show can adapt to both homophilous and heterophilous graph structure. Like SGC, ASGC is not a deep model, and hence is fast, scalable, and interpretable; further, we can prove performance guarantees on natural synthetic data models. Empirically, ASGC is often competitive with recent deep models at node classification on a benchmark of real-world datasets. The SGC paper questioned whether the complexity of graph neural networks is warranted for common graph problems involving homophilous networks; our results similarly suggest that, while deep learning often achieves the highest performance, heterophilous structure alone does not necessitate these more involved methods.

Simplified Graph Convolution with Heterophily
Sudhanshu Chanpuriya University of Massachusetts Amherst schanpuriya@cs. umass.
Cameron Musco
University of Massachusetts Amherst cmuscoêcs. umass edu
Abstract
Recent work has shown that a simple, fast method called Simple Graph Convolu- tion (SGC) (Wu et al., 2019), which eschews deep learning, is competitive with deep methods like graph convolutional networks (GCNs) (Kipf & Welling, 2017) in common graph machine learning benchmarks. The use of graph data in SGC implicitly assumes the common but not universal graph characteristic of homophily, wherein nodes link to nodes which are similar. Here we confirm that SGC is indeed ineffective for heterophilous (i.e., non con-homophilous) graphs via experiments on synthetic and real-world datasets. We propose Adaptive Simple Graph Convolution (ASGC), which we show can adapt to both homophilous and heterophilous graph structure. Like SGC, ASGC is not deep model, and hence is fast, scalable, and interpretable; further, we can prove performance guarantees on natural synthetic data models. Empirically, ASGC is often competitive with recent deep models node classification on a benchmark of real-world datasets. The SGC paper ques- tioned whether the complexity of graph neural networks is warranted for common graph problems involving homophilous networks; our results similarly suggest that, while deep learning often achieves the highest performance, heterophilous structure alone does not necessitate these more involved methods.
Introduction
Data involving relationships between entities arises in biology, sociology, and many other fields, and such data is often best expressed as a graph. Therefore, models of graph data that yield algorithms for common graph machine learning tasks, like node classification, have wide-reaching impact. Deep learning (LeCun et al., 2015) has enjoyed great success in modeling image and text data, and graph convolutional networks (GCNs) (Kipf & Welling, 2017) attempt extend this success to graph data. Various deep models branch off from GCNs, offering additional speed, accuracy, or other features. However, like other deep models. these algorithms involve repeated nonlinear transformations of inputs and are therefore time and memory intensive to train.
Recent work has shown that much simpler model, simple graph convolution (SGC) (Wu al., 2019), is competitive with GCNs in common graph machine learning benchmarks. SGC is much faster than GCNs, partly because the role of the graph in SGC restricted to feature extraction step in which node features are smoothed across the graph; by contrast, GCNs include graph convolution steps part of an end-to-end model, resulting in expensive backpropagation calculations. However, the feature smoothing operation in SGC implicity assumes the common but not universal graph characteristic of homophily, wherein nodes mostly link similar nodes; indeed, recent work (NT & Maehara, 2019) suggests that many GCNs may assume such structure. We ask whether feature extraction approach, that, like SGC, free of deep learning, can tackle heterophilous (i.e.. non-homophilous) graph structure. We see this work as extending the following broader research question introduced by the SGC paper to wider range of graphs:
Are nonlinearities, end-to-end backpropagation, and other characteristics of deep learning essential to effective learning on graphs?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Contributions We confirm that SGC, which uses a fixed smoothing filter, can indeed be ineffective for heterophilous features via experiments on synthetic and real-world datasets. We propose adaptive simple graph convolution (ASGC), which fits a different filter for each feature. These filters can be smoothing or non-smoothing, and thus can adapt to both homophilous and heterophilous structures. Like SGC, ASGC is not a deep model, instead being based on linear least squares, and hence is fast, scalable, and interpretable. We propose a natural synthetic model for networks with a node feature, Featured Stochastic Block Models (FSBMs), and prove that ASGC denoises the network feature regardless of whether the model is set to produce homophilous or heterophilous networks, in contrast to SGC, which we show is inappropriate for the heterophilous setting. Finally, we show that the performance of ASGC is superior to that of SGC at node classification on real-world heterophilous networks, and generally competitive with recent deep methods on a benchmark of both heterophilous and homophilous networks. The SGC paper suggested that deep learning is not necessarily required for good performance on common graph learning tasks and benchmarks involving homophilous networks; our results suggest that simple methods can also be competitive for heterophilous networks.
2 Background
Preliminaries We first establish common notation for working with graphs. An undirected, possibly weighted graph on n nodes can be represented by its symmetric adjacency matrix A E R850" Letting 1 denote an all-ones column vector, d = A1 is the vector of degrees of the nodes; the degree matrix D the diagonal matrix with d along the diagonal. The normalized adjacency matrix is given by S = 1-2 AD-1/2 while the symmetric normalized graph Laplacian is L I S, where I is an identity matrix. Note that the eigenvectors of L are exactly the eigenvectors of S. It is a well known fact that the eigenvalues of S are contained within [- +1]. It follows that the eigenvalues of L are within [0, 2). so L is positive semidefinite.
Consider feature x E R" the graph, that is, real-valued vector where each entry is associated with a node. The quadratic form over known to have the following equivalency:
x Lx
LLx 1/ E Eu.nemn Aij (va, x;
1 vd,"
Up a reweighting based on the nodes' degrees, this expression is the sum of squared differences of the feature's 's values between adjacent nodes, Hence, the quadratic form has a low value, near 0, if the feature æ is 'smooth' across the graph, that is, if adjacent nodes have generally similar values of the feature. Similarly, the quadratic has a high value if the feature is 'rough' across the graph, if adjacent nodes have generally differing values of the feature. When 2 an eigenvector of L, these 'smooth' and 'rough' cases correspond to the eigenvalue being low or high, respectively. (In terms of eigenvalues of S. the opposite true, with positive eigenvalues being smooth and negative eigenvalues being rough.) More generally, decomposition of an arbitrary feature vector æ as linear combination of the eigenvectors of L separates æ into components ranging from 'smooth' to 'rough' across the graph. In the graph signal processing literature (Ortega et al., 2018; Huang et al., 2016; Stanković et al., 2019), these smooth and rough components are also called low and high frequency 'modes," respectively, based on the eigenvalues of L.
Simple graph convolution Our work is primarily inspired by the simple graph convolution (SGC) algorithm (Wu et al., 2019). SGC comprises logistic regression after the following feature extraction step, which can be interpreted as smoothing the nodes' features across the graph's 's edges:
5* ac.
ØSGC
This equation shows how single raw feature x is filtered to produce the smoothed feature Zsse- Here S E R.xx the normalized adjacency matrix after addition of self-loop each node (that is, addition of the identity matrix to the adjacency matrix), and K E Z is hyperparameter; K determines the radius of the filter, that is, the maximum number of hops between two nodes whose features can directly influence others' features in the filtering process. Wu et al. (2019) show that the addition of the self-loop increases the minimum eigenvalue of S: intuitively, the self-loop limits the extent to which feature can be 'rough' across the graph. This results in the highest magnitude eigenvalues of the normalized adjacency S tending to be positive (smooth). Because the eigenvalues of S all have magnitude at most 1, powering up S results in a filter which generally attenuates the

---

feature but does so least along these high magnitude, smooth eigenvectors. Hence the SGC filter smooths out the feature locally along the edges. Since it attenuates the high-frequency modes more than the low-frequency ones, SGC is described as a 'low-pass' filter.
Heterophily If node features are used for node classification or regression, smoothing the features of nodes along edges encourages similar predictions along locally connected nodes. This seems sensible when locally connected nodes should be generally similar terms of features and labels; the variance in features and labels between connected nodes is generally attributable to noise, then this smoothing procedure acts as useful denoising step. Graphs in which connected nodes tend to be similar are called homophilous papers on various topics: papers concerning the same topic tend to cite each other. Much of the existing work graph models has an underlying assumption of network homophily, and there has been significant recent interest (discussed further in Section 6) on the limitations of graph models at addressing network heterophillyddiassootaaa nodes. An example would be a network based on adjacencies of words in text, where the labels are based on the part of speech: adjacent words tend be of different parts of speech. For disassortative networks, smoothing a feature across connections as in SGC may not be sensible, since encouraging predictions of connected nodes be similar is contrary to disassortativity.
assortative. An example would be citation network of
wherein connections tend to be between dissimilar
3 Methodology
Adaptive SGC In our method, we replace the fixed feature propagation step of SGC (Equation 1) with an adaptive one, which may or may not be smoothing based on the feature and graph. We produce a filtered version #'sGC of the raw feature x by multiplying æ with a learned polynomial of the normalized adjacency matrix S; this polynomial is set so that FASGC w::
BASGC EE
k=o Sk
where K is hyperparameter which, as in SGC, controls the radius of feature propagation, and the coefficients /3 gx+ +1 are learned by minimizing the approximation error in a least squares sense. Note that, unlike SGC, we do not add self-loops to S. This approximation error would be trivially minimized with Bu = 1 and all other coefficients set to zero, resulting in ÆASGC S x I, so we regularize the magnitude of Sg.
More concretely, let T E [1)((++) denote the Krylov matrix generated by multiplying a feature vector E R by the normalized adjacency matrix S up some K E E times:
T = (50x;: S' x; Sa::..... 55k))
(3)
Here the leftmost column of T is just the raw feature æ, and each column represents the feature generated by propagating the feature vector its left across the graph, i.e., by multiplying once by S. We produce filtered version BAsGe of the raw feature x by linear combination of the columns of T. That is, ASGG T3, and we the combination coefficients 3 E k++ by minimizing loss function as follows:
min (IT (12+(R()))) 3
The term on the right is Le regularization applied to the zeroth combination coefficient 3o (which multiplies the raw feature S x)) and R. e R>0 a hyperparameter which controls the strength of this regularization. Equation 4 is solved for the optimal coefficents / using linear least squares.
Intuition As noted above, we set the regularization R O. or more generally in the limit as R + 0, the approximation eтror in Equation 4 is trivially minimized and results in AAsGC z; that is, the learned filter just ignores the graph structure and maps the input feature through unchanged. Nonzero regularization forces the least squares reconstruction to use the graph structure as it approxi- mates the raw, unpropagated feature. Ideally, this results denoising effect that able to extend beyond SGC's fixed smoothing along edges. For example, when graph S is homophilous with
3

---

Algorithm Adaptive Simple Graph Convolution (ASGC) Filter
Input: undirected graph E {0, 1,ax=, node feature æ R", number of hops K E Z regularization strength It E Rg
Output: ASGC-filtered feature #AsGC
D < diag (A1) (degree matrix)
S D-1/2 AD AD-1/2 1122 (normalized adjacency matrix)
T E (*+( + 0 [k-step propagated features)
To f x
for k = 1 to K do
T& 4- k-
end for
R E RK+1 t (R,0,0,....
3 +- least squares solution of 3=)== Return: TB
respect to a node feature æ; in that neighbors tend to have similar feature values, the raw feature is correlated positively with the propagated version Sæ of the feature. By contrast, when graph is heterophilous with respect to a feature, the correlation is negative. The least squares in ASGC is able adapt to both cases and exploit this correlation, as well as correlations that occur when repeatedly propagating features (i.e., correlations of æ with S x for ls > 1).
Further remarks In theory, K is raised to higher values, T will provide sufficiently high-rank basis that FASGC will be arbitrarily close to æ, even if R is very high. Then ASGC would have essentially the same performance using the raw feature. While this issue could be resolved by introducing a smaller regularization term for the remaining coefficients, we find that this is generally not problem over reasonable values of K on real-world graphs; hence, for simplicity, we do not introduce this further regularization.
Pseudocode filter single feature is given in Algorithm 1. This algorithm is applied independently to all features; note that this is trivially parallelizable across features. After this, as in SGC, the logistic regression classifier for node classification. The core computations in Algorithm are 1) creation of the matrix T by multiplying æ by S up to K times, for which the time complexity is ((mK), where m is the number of edges; and linear least squares with a matrix of dimensionality (n + 1) x (K + 1), for which the complexity is )²)
filtered features are passed as input
Spectral Interpretation of ASGC ASGC admits interesting alternate interpretation based a spectral view of Equation 4. Let S = Q diag (A)Q be an eigendecomposition of S, and let Y Q -2x that is, y is the graph Fourier transform of the feature æ. The central objective in ASGC is the norm of the residual of the least squares in Equation 4. As in Parseval's Theorem, due to the orthogonality of Q, this norm invariant under the graph Fourier transform:
|AAGC =0|2 = [TB 00|² QQT
(T3 m)|
Q (TB m)|
Recall that each column of T is of the form S'x for some nonnegative power i. Then
-' Q-1 (Q diag(A)* (Qy) diag(A)'y
and the minimization objective can be written as
AASGC x=|² = ||Q TT x= 212 |diag(>) V33 7 - = - |[dig((>>) (V13 1)]1
where, letting superscript of denote the entrywise ,th power of vector,
V/2 (A :
X
the Vandermonde matrix of powers to of the eigenvalues of S. Note that multiplying VA by the vector 3 yields the values of the polynomial with coefficients f, evaluated at the eigenvalues X. Hence ASGC can interpreted as fitting a K K-degree polynomial over the graph's eigenvalues, with the target being all-ones. The value the polynomial takes over each eigenvalue represents how the

---

learned filter scales the component of the feature a which is along the direction of the corresponding eigenvector of S: the all-ones target corresponds a do-nothing filter. The least squares loss weighed proportionately to the magnitude of this component at each eigenvalue. That K is small, and the use of regularization on the zeroth coefficient, precludes the learned filter actually being the do-nothing filter, and instead results in simple polynomial which adapts to the feature.
4 Motivating Example
We now use a synthetic network to demonstrate the capability of ASGC, and the potential deficiencies of SGC, at denoising a single heterophilous feature. We propose Featured SBMs, which augment stochastic block models (SBMs) (Holland et al., 1983) with single feature; we note that our FSBMs can be seen as a simplified variant of recently studied Contextual SBMs (Deshpande et al., 2018).
Definition (Featured SBM). An SBM graph G has nodes partitioned into r communities with intra- and inter- community edge probabilitties p and Let C1. C2..... E {0, 13th be indicator vectors for membership in each community, i.e. the jth entry of C₁ 1 if the j node is in C₁ and O otherwise. A Featured SBM (FSBM) is such graph model G. plus feuture is zero-centered, isotropic Gaussian noise and f f= Σ; 11,C4 for some P1, M2: ................................ Pr E R, which are the expected feature values of each community.
C1, C2....,Cr C,.,.
vector x. f + 1 E R", where n ~ (O, a²
We consider FSBMs with n = 1000, 2 equally-sized communities C+ and C_, feature means ,4, +1, and μ = 1, and noise variance 1. Thus, there are 500 nodes in each community; calling these communities 'plus' and 'minus,' the feature mean is +1 for nodes in the former and -1 for the latter, to which standard normal noise is added. We generate different graphs by setting the expected degree of all nodes to 10 (that is, & {p + q) n = 10). then varying the intra- and inter-community edge probabilities p and q from p > q (highly homophilous, in that 'plus' nodes are much more likely to connect to other 'plus' nodes than to 'minus' nodes) to > p (highly heterophilous, in that 'plus' nodes tend to connect to 'minus' nodes). See Figure for illustration.
Heterophilous
Neither
Hamophilous
500
1000
500
1000
500
1000
Feature
500
-2
1000
1000
1000
500
1000
Node
Figure 1: Synthetic dataset visualization. Left: 3 sample adjacency matrices, from the highly heterophilous (g < p) to the highly homophilous (p >> 9); for visual clarity, these graphs are 10 times denser the description in Section 4. Right: Feature values by node; note the feature means.
We seek to denoise the feature by exploiting the graph, which should result in the feature values moving towards the means of the respective communities. We employ SGC and our ASGC, both with number of hops K 2. Figure (left) shows the deviation from the feature means after denoising. It also shows the proportion of nodes whose filtered feature differs from the community mean in sign, that is, the error when classifying nodes into C+ and C_. By both metries, ASGC outperforms SGC on heterophilous graphs, while SGC outperforms ASGC on homophilous graphs. Both methods can lose accuracy relative just using the raw feature when the graph is neither homophilous nor heterophilous, that is, when the graph is not informative about the communities. However, the performance of ASGC increases similarly as the graph becomes either more heterophilous or homophilous, whereas SGC's performance improves significantly less in the heterophilous direction. Finally, the performance gap between the two is smaller on homophilous graphs, particularly on sign We
accuracy. suggesting that ASGC can better adapt to varying degrees of tomoopily//eterophii examine the highly heterophilous case more detail Figure 2 (right), which shows the distributions of the feature before and after filtering. The fixed propagation of SGC tends towards merging the two communities" feature distributions; by contrast, ASGC able to keep them separated, preserves the feature means, and pulls the feature distributions towards the respective community means.
5

---

Raw
Mcan Abs. Efror
0.8
150
100
0.8
50
0.4
SGC
150
SGC
100
0.3
ASSC
50
Sign Error
0.2
0.1
150
100
0.0
-1.0
-0.5
+1.0 (Homaphilaus)
(Heteraphilous)
P-q
-3
DTT
Figure 2: Left: Denoising results on the synthetic graphs using SGC and ASGC with number of hops K = 2. 'Raw' shows the error when no filtering method is applied. ASGC and SGC are more effective denoising on heterophilous and homophilous networks, respectively, and ASGC more effective overall. Right: Distribution of the feature values before and after applying each of the filterig methods on a very heterophilous synthetic graph ( (P-7 = 9/10),, separated by ground-truth communities. SGC tends to merge the two communities, while ASGC is able to keep them separated.
5 Theoretical Guarantees
To support our empirical investigation in Section 4, we now theoretically verify the limitations and capabilities of SGC and ASGC at denoising FSBM networks. For simplicity, we analyze SGC without the addition of loof (that is, using S in Equation rather than S); the distinction between the two in the analysis vanishes as the number of intra-community edges grows, i..., if n p is high. Further, assume that the regularization hyperparameter R for ASGC is high, in which case the coefficient 30 is fixed to zero, or equivalently, the column S is removed from the Krylov matrix T in Equations and 4. Finally, though we conjecture that via concentration bounds one could extend the following results to the sampled setting (Spielman, 2012). Here, we analyze FSBMs with 2 equally-sized communities. In Appendix 9.1, we prove that these results extend to an arbitrary number of communities. Unless otherwise specified, we use the same notation as Definition 1.
analyze using expected adjacency matrices from the model,
Theorem 1 (Effect of SGC on FSBM Networks). Consider FSBMs having 2 equally-sized communi- ties with indicator vectors Cu and Co, expected adjacency matrix A, and feature vector = f + n, Let &SGC be the feature vector returned by applying SGC, with number of hops K, to A and æ. Fur- ther, let J 1 (Muu + He) be the average of the feature means. Then, Essc = f Cu + C, where f' = X f + X55 (Tt), and On and 02 are both distributed according to / (0, 1/4 + X²K)o²)
Proof. In expectation, an entry Aij of the adjacency matrix of the graph is p if both i, C. or both i.j E C.,. and it is q otherwise. The eigendecomposition Q dtag(A)QQ
of the associated normalized adjacency matrix has two nonzero eigenvalues: À = 1, with eigenvector Qi = (t/va)1 = (c/va)(cu- + Cv), and X2 p-g with Q2 (l/VF) - c.). In the following analysis, we use the fact that zero-cen,ered, isotropic Gaussian distributions are invariant to rotation, meaning Q nj ~ ~N0, I² for any orthonormal matrix Q.
p+g'
ØsGC 5 x
Q diag(A)* Q (MuCuu + Co + 17)
qi (JunCu + MaCo + 17) + >1 9292 (aa + HoCCo + n)
qi (L (pm + uv) + vi + >/ g2
2 (Um - -mn) + 1k2)
= (B(ua + pw) + ) (Cu + c.) + K [1( - Hv) + ) (co - co)
= N (prcCu + m,..)) + (1 - (1 1 [ + pr + cv)
In (vi + 2 1/6) eu # ( 2 m/) Cv
= xx + -1 ( + 0 + 0 0_co, Cv.

---

where 01 = vn (1/ = n1)n),,
1/2,, which has the specified distribution.
Note that A2 = = E [-], with negative values indicating heterophily (p < q) and positive values indicating homophily (p > q). SGC only preserves the feature means in certain limiting cases. In particular, this occurs as X2 - +1, or as X2 + 1 K is even; then A + 1, so the expected filtered feature vector f - f. On the other hand, if 22 - O, then X + 0 and f + p1, that is, the feature value means are averaged between the communities. Finally, if A2 + -1 and K is odd, then X - -1 and f = fil + (μ1l f) MryCu + MaCp: the feature value means are entirely exchanged across the communities. By contrast, ASGC preserves the means, while similarly reducing noise by (()) factor, with much looser restrictions X₂ and K:
Theorem 2 (Effect of ASGC on FSBM Networks). Consider FSBMs with p # having 2 equally- sized communities with community indicator vectors Cu and Cw, expected adjacency matrix A, and feature vector x = f + 17. Let TASGC be the feature vector returned by applying ASGC, with number of hops K 2, to A and æ. Then TASGC = f f.,cc. Cu + 6' Cv. where 0¹, and 8'_ are both distributed
according to N (o, 3.
Proof. The least squares in ASGC is equivalent to projecting the feature onto the column span of the Krylov matrix T = ( x; s'=: the column span of S. Further, S is rank-2 (by the assumption that p # q), with probability 1 over the distribution of 17. as long as 2 2, the column span of T equals that of S. Thus ASGC projects onto the column span of S, i... the span of q1: 92, the eigenvectors of S. The following analysis proceeds exactly like the one for SGC, just without the terms for the eigenvalue X2, so we use the same notation and abbreviate the steps:
: S
x)). Observe that the column span of T contained in
FASOC QQTx x
= qptb (HuCu + u. + 7) + 9292 (PoCu + MoCo + 17)
= f + 0f Cu + 0' co:
where 84 = vn 3 + n1)., which has the specified distribution.
Observe that in the sampled setting, standard matrix concentration results be used show that, while will be full rank with high probability, it will have two outlying eigenvalues, corresponding to eigenvectors close to qı and q2 (Spielman, 2012). It well known that the span of the Krylov matrix T will align well with these outlying eigendirections (Saad, 2011). Thus, we expect the projection QQ x = QQ f + QQ ') to still approximately preserve f. At the same time, QQ' n is the projection of a random Gaussian vector r onto a fixed K --dimensional subspace. Thus, we will have [QQ n
2 K || so ASGC will still perform significant denoising when K is small. 2
6 Related Work
Deep graph models As discussed previously, the SGC algorithm is drastic simplification of the graph convolutional network (GCN) model (Kipf & Welling, 2017). GCNs learn a sequence of node representations that evolve via repeated propagation through the graph and nonlinear transformations. The starting node representations H (0) are set to the input feature matrix X E gnxf, where f is the number of features. The 1hth -thp representations are H (R) = a (SH (k- 1) (+)). where (M) is the learned linear transformation matrix for the th layer and a is a nonlinearity like ReLU.. After K such steps, the representations are used classify the nodes via a softmax layer, and the whole model is trained end-to-end via gradient descent. Wu et al. (2019) observe that if the nonlincarities are ignored, all of the linear transformations collapse into single one, while the repeated multiplications by S collapse into single one by S this yields their algorithm of the SGC filter (Equation 1) followed by logistic regression. GCNs have spawned streamlined versions like FastGCN (Chen et al., 2018), as well as more complicated variants like graph isomorphism networks (GINs) (Xu et al., 2019) and graph attention networks (GAT') (Veličković et al., 2018); despite being much simpler and faster than these competitors, SGC manages similar performance on common benchmarks, though, based on the analysis of NT & Maehara (2019), this may be due part to the simplicity of the benchmark datasets in that they mainly exhibit homophily/asoottaiiiit.
7

---

Table 1: Statistics of datasets used in our experiments, separated by homophilous vs heterophilous.
Dataset
CORA
CITE.
PUBM.
СОмP.
PHOtO
CHAM.
SQUI.
ACTOR
TEXAS
CORN.
Nodes
2708
3327
19717
13752
7650
2277
5201
7600
183
183
Edges
5278
4552
44324
245861
119081
31421
198493
26752
295
280
Features
1433
3703
500
767
745
2325
2089
932
1703
1703
Classes
7
6
3
10
8
5
5
5
5
(9)
0.825
0.718
0.792
0.802
0.849
0.247
0.217
0.215
0,057
0.301
Addressing heterophily Like our work, some other recent methods attempt to address node heterophily. Gatterbauer (2014) and Zhu et al. (2020a) augment classical feature propagation and GCNs, respectively, to accommodate heterophily by modifying feature propagation based on node classes. Zhu et al. (2020b) and Yan al. (2021) analyze common structures heterophilous graphs and the failure points of GCNs, then propose GCN variants based on their analyses. The Geom-GCN paper of Pei et al. (2020) introduces several of the real-world heterophilous networks which are commonly used in related papers, including this one. Their method allows for long-range feature propagation based on similarity of pre-trained node embeddings. The preceding is just a sample of recent works in this area, which has seen a surge of activity (Liu et al., 2020; Luan et al., 2021; Suresh et al., 2021). We note that, like the GNNs of Kipf & Welling (2017) but unlike SGC and our ASGC, almost all of these methods are based on deep learning and are trained via backpropagation through repeated feature propagation and linear transformation steps, and hence incur an associated speed and memory requirement. Understanding and implementing these methods is also more complicated relative to our method, which just constitutes a learned feature filter and logistic regression. We mainly compare our results with the deep method which is most similar ours, Generalized PageRank GNN (GPR-GNN) (Chien et al., 2021). Like ASGC, EPR-GNN produces node representations by linear combination of propagated versions of node features; unlike ASGC, the raw features first transformed by neural network, and parameters for this network, as well as the linear combination coefficients, are learned by backpropagation using the known node labels. To our knowledge, our work is the first to show that heterophily can be handled using just feature pre-processing.
7 Empirical Performance
We test the performance of ASGC for the node classification task on a benchmark of real-world datasets given in Table 1, and compare with SGC and several deep methods.
Real-world datasets We experiment on 10 commonly-used datasets, the same collection of datasets as Chien et al. (2021). CORA, CITESEER, and PUBMED are citation networks which are common benchmarks for node classification (Sen et al., 2008; Namata et al., 2012); these have been used the GCN (Kipf & Welling, 2017) and GAT (Veličković et al., 2018) papers. in
for evaluation addition to SGC itself. The features are hag-of-words representations of papers, and the node labels give the topies of the paper. COMPUTERS and PHOTO are segments of the Amazon co- purchase graph (McAuley et al., 2015; Shchur et al., 2018); features are derived from product reviews, and labels are product categories. These first 5 datasets are considered assortativ/hhooopiloous:: the remaining 5 datasets, which are dissasorrativv/neccophiioooo per (Pei et al., 2020), which also introduces the following measure of of a network's 's homophily: #e's neighbors with the same label 8 neighhors of v
come from the Geom-GCN pa-
é [o, 1]. We include this statistic in Table 1. The latter 5 datasets have much lower values of H9).. CHAMELEON and SQUIRREL are hyperlink networks of pages in Wikipedia which concern the two topics (Rozemberezki al., 2021). Features derive from text in the pages, and labels correspond to the amount of web traffic to the page, split into categories. ACTOR is the actor-only induced subgraph of the fim-director-actorn werterr network of Tang & Liu (2009). Nodes and edges represent actors and co-occurrence on a Wikipedia page. Features are based on keywords on the webpage, and labels derive from the number of words on the page, split into 5 categories. Finally, TEXAS and CORNELL are hyperlink networks from university websites (Craven et al., 2000); features derive from webpage text, and the labels represent the type of page: student, project, course, staff, or faculty.
HG)) = M Evev
Implementation
The SGC and ASGC algorithms are implemented in Python using NumPy (Harris et al., 2020) for least squares regression and other linear algebraic computations. We use scikit-
8

---

Cora
Citeseer
PubMed
Computers
Photo
70
60
00
50
20
20
SGC AGC GCN GEO GMR
SGC AGC GCN GEO GMA
SGC AGC GCN GEO GM
SGC
AGC GCN
GMH
S6C AGC GCN GPR
Chameleon
Squirrel
Actor
Cornell
75
90
70
55
35
80
80
63
50
70
45
40
60
60
59
35
50
50
30
20
40
40
SGC AGC GEN
GEO GPR
Figure 3: Test classification accuracy on the benchmark of datasets from Table for selected methods: 2 non-deep. SGC and ASGC: and 3 deep. GCN, Geom-GCN, and GPR-GNN. Error bars show the 95% confidence intervals. SGC is generally competitive with the deep methods on the homophilous datasets (top row), but not so on the heterophilous ones, whereas ASGC is competitive throughout.
learn (Pedregosa et al., 2011) for logistic regression with 1,000 maximum iterations and otherwise default settings. For our implementations of SGC and ASGC, we treat each network as undi- rected, in that edge ji appears, we also include edge (j. i). Like Chien al. (2021), we use random 60%/20% 20%% splits as saadiingvalidationn/eess data for the 5 heterophilous datasets, as in Pei et al. (2020), and use random 2.5%/2.5 /.5/////9/%% splits for the homophilous datasets, which is closer to the original setting from Kipf & Welling (2017) and Shchur et al. (2018). We re- lease code in the form of a Jupyter notebook (Pérez & Granger, 2007) demo which available at github. github.com/schee wwooo//aaaiaa/aaaeeeoo www.ptiieeiimpll-ooooeeeeo
Hyperparameter settings We tune the number of hops over K E (1,2,4,8) roughly covering the range analyzed in Wu et al. (2019), and the regularization strength = Vn- R' over log (R') e (-4,-3, -2 -1. This dependency on the number of nodes n allows the regularization loss to scale with the least squares loss, which generally grows linearly with n. In Appendix 9.2, we report results for some additional experiments investigating the effect of fixing these hyperparameters.
Classification results We apply our implementations of SGC and ASGC to these datasets and report the mean test accuracy across 10 random splits of the data. As baseline, we also report the accuracy of logistic regression on the 'raw,' unfiltered features, ignoring the graph. We compare to results from Chien et al. (2021) for 9 deep methods applied to these datasets. These methods are 1) a multi-layer perceptron which ignores the graph: 2) GCN; 3) GAT; 4) SAGE (Hamilton et al., 2017); 5) JKNet (Xu et al., 2018): 3); 6) GCN-Cheby (Defferrard et al., 2016); 7) Geom- 8) APPNP (Klicpera et al., 2019); and 9) GPR-GNN Full results are given in Table Appendix 9.3.
We plot accuracies for selected methods in Figure 3. In addition to SGC and ASGC, we include 3 deep methods: 'vanilla' GCN; Geom-GCN, which originated the heterophilous datasets; and GPR-GNN, recent method claiming state-of-the-art performance. We find that SGC is generally competitive with the deep methods on the homophilous datasets, but not on the heterophilous ones, whereas ASGC is generally competitive throughout. Interestingly, the datasets on which GPRGNN significantly outperforms ASGC (PUBMED, ACTOR, TEXAS, CORNELL) are exactly those on which a multi-layer perceptron significantly outperforms logistic regression; note that the latter two methods both ignore the graph. This suggests that the some nonlinear processing of the node features may be key to performance on these networks, separate from how the graph is exploited. To compactly compare all 12 of the methods across these 10 datasets, we aggregate the performance across the datasets as follows. For each dataset, we calculate the accuracy of each method as proportion of the accuracy of the best method. We plot the mean and the minimum across the 10 datasets of each method's proportional accuracies. See Figure 4, GPRGNN and ASGC achieve the highest mean

---

Mean
1.0
1.0
0.9
0.7
0.6
0.
Cheby GON MP
GNN
Cheey GCN NP GNN
Figure 4: Test accuracy proportion of the best method's accuracy; mean and minimum perfor- mance over the 10 networks. The 3 non-deep (logistic regression) methods are on the left. ASGC achieves the highest minimum performance, and is competitive with GPRGNN the mean.
performance. Further, ASGC achieves the highest minimum performance: at worst, it achieves over 90% the best method's test accuracy on each the datasets.
8 Conclusion, Limitations, and Broader Impact
Building SGC, we propose feature filtering technique, ASGC, based on feature propagation and least-squares regression. We propose a natural class of synthetic featured networks, FSBMs, and show both empirically and with theoretical guarantees that ASGC can denoise both homophilous and heterophilous FSBMs, whereas SGC is inappropriate for the latter. Further, we find that ASGC is generally competitive with recent deep learning-based methods benchmark of real-world datasets, covering both homophilous and heterophilous networks. Our results suggest that deep learning is not strictly necessary for handling heterophily, and that even simple feature pre-processing method can be competitive. We hope that, like SGC, ASGC can serve as good first method to try, especially for node classification on heterophilous networks, and a baseline for future works.
We note certain limitations of our work. First, our theoretical guarantees are in the fairly idealized setting of FSBM networks; we provide general guarantee of performance. Second, empirical evaluations on real-world datasets do not include any truly large-scale datasets (n ~ 10 or higher), though collection of 10 datasets is fairly broad selection amongst those which used in related papers about heterophily. Finally, as we note in Section 6, there are many more recent works and methods for handling heterophily which we could compare our results. We limit ourselves to subset due to the amount of activity in this area; further, we are not asserting absolute sate-offtheeart results in this area, merely that simple method like ours can be competitive.
commonly
We do not anticipate direct negative societal impacts of our work, but improved methods for network analysis, including those for node classification, have social consequences. For example. improved graph-based recommendations may be associated with negative impacts to well- well-being due to increased social media (Verduyn et al., 2017; Kelly al., 2018). They might also contribute concerns of filter bubbles and polarization (Nguyen et al., 2014; Lee et al., 2014; Musco et al., 2018)
Acknowledgments and Disclosure of Funding
This project was partially supported by an Adobe Research grant, a Google Research Scholar Award, and NSF Grants 2046235 and 1763618. We also thank Raj Kumar Maity and Konstantinos Sotiropoulos for helpful conversations.
References
Chen, J., Ma, T., and Xiao, C. Fastgen: fast learning with graph convolutional networks via importance sampling. International Conference on Learning Representations, 2018.
Chien, E.,, Peng. J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
10

---

Craven, M., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T., Nigam, K., and Slattery, S. Learning to construct knowledge bases from the world wide web. Artificial intelligence, 118(1-2): 69-113, 2000.
Defferrard, M., Bresson, X., and Vandergheynst, Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 3837-3845, 2016.
Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. Contextual stochastic block models. In Advances in Neural Information Processing Systems, 2018.
Gatterbauer, W. Semi-supervised learning with heterophily. arXiv preprini arXiv: 2014.
Hamilton, W. L., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach. CA, USA, pp. 1024-1034 2017.
Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtamen, P., Coumapeau, D., Wieser, B., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Breut M., Haldane, A., del Río, J. F,, Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. Array programming with NumPy. Nature, 585(7825):357-366 September 2020. doi: 10.1038/$4158-0000 020-0009-222222
Holland, P. W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Huang, W., Goldsberry, L., Wymbs, N. F., Grafton, S. T., Bassett, D. S., and Ribeiro, A. Graph frequency analysis of brain signals. IEEE Journal of Selected Topics in Signal Processing, 10(7): 1189-1203, 2016.
Kelly, Y., Zilanawala, A., Booker, C., and Sacker, A. Social media use and adolescent mental health: Findings from the uk millennium cohort study. EClinicalMedicine, 6:59-68, 2018.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Klicpera, J., Bojchevski, A., and Günnemann, S. 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, 2019.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature, 521(7553):436 444, 2015.
Lee, K., Choi, J., Kim, C., and Kim, Y. Social media, network heterogeneity, and opinion polarization. Journal of Communication, 64(4):702-722, 2014.
Liu, M., Wang, Z., and Ji, Non-local graph neural networks. arXiv preprint arXiv:2005.14612 2020.
Luan, S., Hua, C., Lu, Q. Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D. het- erophily real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.088 109.05641, 2021.
McAuley, J., Targett, C., Shi, Q. and Van Den Hengel, A. Image-based recommendations on styles and substitutes. Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information retrieval, pp. 43-52, 2015.
Musco, C.,, Musco, C., and Tsourakakis. C. E. Minimizing polarization and disagreement in social networks. In 20/8, pp. 369-378, 2018.
Namata, G., London, B., Getoor, L.,, Huang, B., and EDU, U. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, pp. 1, 2012.
11

---

Nguyen, T. T., Hui, P.-M., Harper, F. M., Terveen, L., and Konstan, J. A. Exploring the filter bubble: the effect of using recommender systems on content diversity. In Proceedings of the 23rd International Conference World Wide Web, pp. 677-686, 2014.
NT, H. and Machara, T. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:I905.095550 2019.
Ortega, A., Frossard, P. Kovačević, J., Moura, J. M., and Vandergheynst, P. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808 828, 2018.
Pedregosa, F.. Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O.. Blondel, M.. Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
Pei, H., Wei, B., Chang, K. C.,, Lei, Y., and Yang, B. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Pérez, and Granger, B. IPython: a system for interactive scientific computing. Computing in Science and Engineering, 9(3):21-29, May 2007. ISSN 1521-9615, doi: 10. 10110CSCEE22207.335 URL https: /ttpypyttoooorr..
Rozemberezki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding. Complex Networks, 9(),, 2021.
Saad, Y. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
Sen, P., Namata, G., Bilgic, M., Getoor, L., Gallagher, B., and Eliassi-Rad, T. Collective classification in network data. Al Mag., 29(3)993-106, 2008.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, Pitfalls of graph neural network 2018
evaluation. arXiv preprint
Spielman, D. Spectral graph theory. Combinatorial Scientific Computing, 18, 2012.
Stanković, L., Daković, M., and Sejdié, E. Introduction to graph signal processing. In Vertex- Frequency Analysis of Graph Signals, pp. 3-108. Springer, 2019.
Suresh, S., Budde, V., Neville, J., Li, P., and Ma, J. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pp. 1541-1551. ACM, 2021.
Tang, L. and Liu, H. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 817-826. ACM, 2009.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. International Conference on Learning Representations, 2018.
Verduyn, P., Ybarra, O., Résibois, M., Jonides, J., and Kross, E. Do social network sites enhance or undermine subjective well-being? A critical review. Social Issues and Policy Review, 11((): 274-302, 2017.
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Weinberger, K. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference Machine Learning, pp. 6861- 6871. PMLR, 2019.
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pp. 5453-5462. PMLR, 2018
Xu, K., Hu, W., Leskovec, J., and Jegelka, How powerful are graph neural networks? International Conference Learning Representations, 2019.
12

---

Yan, Y., Hashemi, M.. Swersky, K., Yang, Y., and Koutra, D. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint SXKv:22022006662. 2021.
Zhu, J., Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, K., and Koutra, Graph neural networks with heterophily. AAAI Conference on Artificial Intelligence, 2020a.
Zhu, J., Yan, Y., Zhao, L.., Heimann, M., Akoglu, L.., and Koutra, Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Section 8 describes limitations.
(C) Did you discuss any potential negative societal impacts of your work? [Yes] Section discusses potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Section defines the FSBM networks and Section describes any further assumptions for theoretical results.
(b) Did you include complete proofs of all theoretical results? [Yes] Section 5 includes proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes] The code is straightforward Jupyter demo, and is included in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters how they were chosen)? [Yes] The implementation subsection of Section 7 specifies the data splits and hyperparameters and where they came from.
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] Both the main results plot and the full table of results include confidence intervals.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No] As should be clear from the time complexity discussion in Section and the dataset statistics Table 1, our method is lightweight enough to the benchmarks within a few hours laptop without GPU, so compute is not significant concern.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We only use standard node classification benchmarks and credit the original papers.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] We do not produce new assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
13

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "wDtqaSeoAI", "reviewer": "Reviewer_86p6", "summary": "The paper introduces Adaptive SGC as an improvement of SGC to better handle heterophilous graphs. The major idea is to learn a polynomial of normalized adjacency matrix by solving a least square problem. The proposed idea is simple and scalable. Theoretical analyses under very ideal assumptions are provided. The empirical performance is competitive with recent baselines. ", "questions": "Please respond to the comments mentioned in the weakness.\n\nIn addition to that, could you please compare the advantages and disadvantages of the proposed filter learning and existing filter learning such as ChebNet and GPR-GNN in terms of accuracy regardless of efficiency？", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper introduces a simple and scalable approach for graph learning in both homophilous and heterophilous settings. \n\n2. The paper is clearly written and easy to follow. \n\n3. Motivation examples and theoretical analyses are provided to justify the proposed idea. \n\n4. Empirical evidence supports the effectiveness of the proposed algorithm.\n\nWeakness:\n\n1. Despite the motivation example and theoretical analyses, the intuition and motivation of the proposed filter learning via lease square approximation are still unclear. There is a lack of discussion about the insight of projecting the feature onto the column space of the Krylov matrix.\n\n2. The motivation example and theoretical analyses are provided under ideal assumptions. For instance, the adjacent matrix is the expected adjacent matrix that precisely reflects the membership information of each node. It is unclear how the sampled setting impacts the current theoretical results.\n\n3. The theoretical analysis removes the raw feature in the least square approximation. But the impact of raw feature and coefficient regularization are never studied in the experiments. \n\n4. It is unclear why ASGC would achieve similar performance as using the raw feature. A shallow discussion is provided in Section 3 but it is not sufficient. A further discussion about when and why the proposed method fails will also be helpful to understand its limitation.\n\n5. The performance improvements over recent baselines are not stable and are sometimes worse.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "b3Na0RJuwUI", "reviewer": "Reviewer_NDRL", "summary": "This paper study the extension of SGC for heterophily settings. More specifically, it is known that SGC work for the homophilous setting where nodes that have similar labels are connected by an edge, however, SGC performs poorly on heterophily graph where nodes with different labels are connected by an edge.\nThe authors consider an multi-hop SGC as $\\mathbf{H} = \\sum_{i=0}^K \\beta_i \\mathbf{S}^i \\mathbf{X},~\\mathbf{S}=\\mathbf{D}^{-1/2} \\mathbf{A} \\mathbf{D}^{-1/2}$.\nTo overcome the performance degradation issue for applying SGC on heterophily graphs, the authors propose an adaptive SGC method that learns the combination coefficient $\\beta_i$ (as shown in Eq. 4).", "questions": "**Won't Eq. 4 with regularization lead to a degenerated solution?**\n\nFor example, I can write the Eq. 4 as\n$$\n\\min_{\\boldsymbol{\\beta}} f(\\boldsymbol{\\beta}) = \\sum_{i=1}^K \\\\| \\beta_i (\\mathbf{S}^i \\mathbf{x} - \\mathbf{x})\\\\|_2^2 + \\mathbf{I}\\\\{i=0\\\\} R^2 \\beta_0^2,\n$$ \nwhere $S^0 = \\mathbf{I}_N$ by using the authors' notation. \nTaking gradient to each $\\beta_i, i\\in \\{ 0,\\ldots, K\\}$ and set to zero, we have\n$$\n\\frac{\\partial f(\\boldsymbol{\\beta})}{\\partial \\beta_i} = 2\\beta_i (\\mathbf{S}^i \\mathbf{x} - \\mathbf{x}) (\\mathbf{S}^i \\mathbf{x} - \\mathbf{x}) + \\mathbf{I}\\\\{i=0\\\\} 2R^2 \\beta_0 = 0\n$$\n\nThen, the closed form solution still has $\\beta_0 \\neq 0$ but $\\beta_i = 0, i=1,\\ldots,K$, which is the degenerated solution ...\nin other words, the optimal $\\boldsymbol{\\beta}$ gives us linear NN.", "limitations": "No", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**\n\nBoth the method and the analysis in this paper sound novel and interesting to me.\n\n**Quality + Significance**\n\nI have doubts about the correctness of the adaptive SGC method in Eq. 4. Please refer to the Question section.\n\nIf I misunderstood the method in Eq. 4 and the author could correct me, then the contribution is significant. Otherwise, the authors might need to double-check their experiment results because according to my understanding, Eq. 4 should lead to a degenerated solution ...\n\n \n**Clarity**  \n\nThe paper is easy to follow and the intuition is quite clear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_R2UjCc2CMh", "reviewer": "Reviewer_MRH6", "summary": "This paper presents an adaptive simple graph convolution method (ASGC) for learning over heterophilous graphs. ASGC is proposed as an extension of the previously proposed simple graph convolution (SGC) to better handle graph heterophily. The authors provide a theoretical analysis of synthetic datasets to demonstrate the ineffectiveness of SGC on heterophilous graphs. Empirical comparisons with several state-of-the-art methods show some promising results of ASGC as compared with deep learning models. ", "questions": "1. What is the key difference between the proposed ASGC method and Generalized PageRank GNN (GPR-GNN), except for the loss function? Why ASGC works better than GPR-GNN on some datasets, but worse on some other datasets?\n\n2. The authors claim that they are the first to handle graph heterophily using feature pre-processing. What is the significance of pre-processing features to handle heterophily without considering any particular learning tasks? Please give more explanations.\n\n3 Please give more explanations for the theoretical analysis provided. For example, what is the connection between the learned coefficients \\beta and homophily ratio of graphs?\n\n", "limitations": "I think the authors have adequately addressed the limitations of their proposed method.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper is well written and easy to follow. \n2. The theoretical analysis based on stochastic block models show the limitations of SGC and the improvements of ASGC over SGC.\n\nWeakness:\n1. Technical contributions of this paper are somehow limited. In essence, I think the proposed method uses a similar \"adaptive\" idea as  Generalized PageRank GNN (GPR-GNN) -- which achieves adaptive smoothing over edges via learnable coefficients, thus better generalising to heterophilous graphs. It is unclear to me what advantages ASGC offers over GPR-GNN, apart from being a non deep learning model. Empirical results also show that ASGC is less effective than GPR-GNN on 3 out of 5 heterophilous graphs. \n\n2. The authors claim that \"our work is the first to show that heterophily can be handled using just feature pre-processing\". I think this is overclaimed because the authors are mainly concerned about node classification on graphs. In a general sense, how to effectively handle heterophily is indeed dependent on the learning task to be addressed. \n\n3. The experimental evaluation is weak. First, heterophilous graphs used in the experiments are quite small. Adding more and larger datasets would make the evaluation stronger. Second, empirically, ASGC is claimed to be competitive with recent deep learning models on heterophilous graphs. However, its performance is found to be inferior to GPR-GNN on more than half of heterophilous graphs. Third, the authors have not provided comparisons with several recent works for handling graph heterophily.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WTSUi1bK862", "reviewer": "Reviewer_X7Nw", "summary": "This paper proposes Adaptive Simple Graph Convolution (ASGC), which can adapt to both homophilous and heterophilous graph structures. ASGC represents an extension of SGC to graph with heterophily, which is a novel and timely contribution.", "questions": "Suggestions:\n- Typos on Figure 3. Should be ASGC, not AGC. \n\nQuestions:\n- Could ASGC extend to graph classification tasks?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The contribution is novel. Most existing methods for simplifying Graph Neural Networks make the homophily assumption. This paper extends the use case of this line of work to heterophilous graphs, which have wide applications in cases like networks based on adjacencies of words in text\n- The paper provides nice theoretical guarantees on the capability of proposed ASGC at denoising FSBM networks.\n\nWeakness:\n- More explorations regarding the potential of ASGC are needed. Based on the experimental results in Figure 3, ASGC actually performs worse than the standard SGC in a few datasets. I hope the authors can provide more justifications and analyses on why this is the case.\n- I hope the paper can somehow unify the idea of ASGC and SGC, such that a model can automatically decide and apply the best feature propagation scheme based on the task of interest. I.e., the model tends to be more ASGC alike when the input graph is more heterophilous, and the model is more SGC alike when the input graph is more homophilous. This improvement to the model should make it much easier to use, as a user no longer has to decide between ASGC and SGC.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept