Simple Spectral Graph Convolution from an Optimization Perspective
Authors: Hao Zhu
Piotr Koniusz
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Convolution
Graph Fourier Transformation
Unsupervised Learning

Abstract: Recent studies on SGC, PageRank and S\textsuperscript{2}GC have demonstrated that several graph diffusion techniques are straightforward, quick, and effective for tasks in the graph domain like node classification. Even though these techniques do not even need labels, they can nevertheless produce more discriminating features than raw attributes for downstream tasks with different classifiers. These methods are data-independent and thus primarily rely on some empirical parameters on polynomial bases (e.g., Monomial and Chebyshev), which ignore the homophily of graphs and the attribute distribution. They are more insensitive to heterophilous graphs due to the low-pass filtering. Although there are many approaches focusing on GNNs based on heterophilous graphs, these approaches are dependent on label information to learn model parameters. In this paper, we study the question: are labels a necessity for GNNs with heterophilous graphs? Based on this question, we propose a framework of self-representation on graphs related to the Least Squares problem. Specifically, we use Generalized Minimum RESidual (GMRES) method, which finds the least squares solution over Krylov subspaces. In theoretical analysis, without label information, we enjoy better features with graph convolution. 
The proposed method, like previous data-independent methods, is not a deep model and is, therefore, quick, scalable, and simple. We  also show performance guarantees for models on real and synthetic data. On a benchmark of real-world datasets, empirically, our method is competitive with existing deep models for node classification.

Under review as a conference paper at ICLR 2023
SIMPLE SPECTRAL GRAPH CONVOLUTION FROM AN OPTIMIZATION PERSPECTIVE
Anonymous authors
Paper under double-blind review
ABSTRACT
Recent studies SGC, PageRank and SCGC have demonstrated that several graph diffusion techniques are straightforward, quick, and effective for tasks the graph domain like node classification. Even though these techniques do not even need labels, they can nevertheless produce more discriminating features than attributes for downstream tasks with different classifiers. These methods are date-independent and thus primarily rely some empirical parameters poly- nomial bases (c.g.. Monomial and Chebyshev), which ignore the homophily of graphs and the attribute distribution. They are more insensitive to heterophilous graphs due to the low-pass filtering. Although there are many approaches focus- ing GNNs based on heterophilous graphs, these approaches are dependent on label information to learn model parameters. this paper, we study the ques- tion: are labels necessity for GNNs with heterophilous graphs? Based this question, we propose a framework of self-represnnttttion on graphs related to the Least Squares problem. Specifically, (GMRES) method, which finds the least squares solution over Krylov subspaces. In theoretical analysis, without label information, graph convolution. The proposed method, like previous data-independent meth- ods, not deep model and is, therefore, quick, scalable, and simple. We also show performance guarantees for models on real and synthetic data. On bench- mark of real- world datasets, empirically, our method is competitive with existing deep models for node classification.
use Generalized Minimum RESidual
enjoy better features with
INTRODUCTION
With the development of deep learning, CNNs have been widely used in different applications. A convolutional neural network (CNN) exploits the shift-invariance, local connectivity, and compo- sitionality of image data. As result, CNNs extract meaningful local features for various image- related problems. Although CNNs effectively capture hidden patterns on the Euclidean grid, there is an increasing number of applications where data is represented in the form of oonFuucideean grid, e.g. in the graph domain.
GNNs redefine the convolution the graph in two different ways: spatial and spectral. Spatial- based methods decompose the convolution operation into an aggregation function and a transforma- tion function. The aggregation function is used aggregate neighbourhood node information by the mean function, which is somewhat similar to the box filter in traditional image processing. Some representative methods in this category are Message Passing Neural Networks (MPNN (Gilmer et al., 2017)), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2017). etc. Spectral methods are based on Graph Fourier Transformation (GFT). They try to learn a filtering function on the eigenvalues (or graph kernel, heat kernel, etc.) These methods usually use approximations in order to simplify the amount of computation, e.g. Chebyshev polynomials and Monomial polyno- mials are used by ChebNet (Defferrard et al., 2016)), GDC (Klicpera et al., 2019), SGC (Wu et al., 2019), SºGC (Zhu & Koniusz, 2021). Although spatial and spectral methods effectively extend the convolution operator the graph domain, they usually suffer from oversmoothing on heterophily graph because they follow the homophily assumption, thus severely affect the node classification task as shown in Figure 1.

---

Under review as a conference paper at ICLR 2023
0.75
Sign Errr
Raw
0.2
SGC
S5GC
PR
0.0
+0.5
11.0
-0.5
10.5
(Heterophilous)
(Hamophilous)
(Heterophilous)
(Homophilous)
p
(a) K = 2
1.0
Sign Emor
0.4
Raw
0.5
0.2
SSGC
Moan
PR
-1.0 (Heterophilous)
-0.5
+0.5
+1.0 (Homophilous]
-1.0 (Heterophilous)
-0.5
+0.5
+1.0 (Homophilous)
(b) K =
Figure 1: Results on the contextual SBM using SGC, S and PR (PageRank) with number of hops K 2, 8. 'Raw' shows the error when filtering method is applied. All methods only work well in homophilous networks.
However, graphs are not always homophilic: they show the opposite property in some connected node groups. This makes it harder for existing homophilic GNNs to learn from general graph- structured data, which leads to significant drop in performance heterophilous graphs. There many GNNs for a graph with heterophily. Their motivation mainly focuses on improving feature propagation and features transformation. Non-local neighbor extension usually is used for incor- porating high-order neighbor information (Abu-El-Haija et al., 2019; Zhu et al., 2020; Jin et al., 2021) discovering potential neighbours (Liu et al., 2021; Yang et al., 2021; Zheng et al., 2022). Adaptive message aggregation is a good way to reduce the heterophilous edges (Veličković et al., 2017; Suresh al., 2021). Inter-layer combination provide more flexible way to learn graph volution (Xu et al., 2018; Zhu et al., 2020: Chien et al., 2021). However, all of these approaches are designed for semi- supervupe node classification, which is usually transductive (labels for training).
In this paper, first we review the connection between GNNs and the Label Propagation (LP) with Laplacian regularization (Zhou et al., 2003). The closed-form solution only depends on a parame- ter balancing smoothing and fitting error. This results in low-pass filter methods for homophilious graphs such as PageRank and S²GC, which cannot work well on heterophilous graphs. Based on the Taylor expansion of the closed form solution, we reformulate label propagation with Laplacian Krylov subspace. We further generalize the residual minimization in the Krylov subspace into more generalized Polynomial Approximation. Then we discuss other possible bases such as Chebshev polynomials. In theoretical analysis, we try to explore whether high-order (second-order in this paper) multi-scale graph convolutions able to improve the performance given raw attributes without labels. In experiments with synthetic data, show performance in line with our theoretical expectations. On the real-world benchmarks, our method is competitive with other graph convolution techniques in homophilous graphs and outper- forms them (even some GNNs methods with transductive learning) on heterophilous graphs.
regularization to Residual Minimization
Our contributions are: 1.) We reveal the labels are not necessary for graph neural networks on heterophilous graphs. The linear graph convolution is powerful on heterophilous graphs and ho- mophilous graph, and outperforms GNNs for heterophilous graphs on semi comi-supervised node classi- fication. 2.) We propose framework of Feature (or Label) Propagation by parameterizing spectral graph convolution residual minimization in Krylov subspace. We further reformulate residual minimization problem into Polymonimial Approximation, which can yield Chebshev and Berstein bases to overcome the Runge phenomenon. 3.) In theory, we prove second-order graph convolu- tion is better than first-order graph convolution on heterophilous graphs and multi-scale (single and second-order) provide better results with some combinations of parameters. 4.) Compared with other methods of label-dependent GNNs under heterophily, our method is competitive in real-world benchmarks. The proposed method outperforms other low-pass graph convolution without learning.
2

---

Under review as a conference paper at ICLR 2023
2 RELATED WORKS
Data-independent Spectral Graph Convolution Hammond et al. (2011) introduced Chebyshev polynomial to estimate wavelets in graph signal processing. Based on this polynomial approxima- tion, ChebNet was proposed for combining neural network and the graph convolution operator. Un- like ChebNet using Chebyshev polynomial, Diffusion Convolutional Neural Network (DCNN (At- wood & Towsley, 2016)) use the normalized adjacent matrix polynomial bases to approximate any graph filters. Simplifying Graph Convolution (SGC (Wu et al., 2019)) are a special case of DCNN: only k-th power of normalized adjacent matrix is selected. Graph Diffusion Convolution (GDC (Klicpera et al., 2019)) shown two other special cases based on normalized adjacent matrix: heat kernel and PageRank kernel. It should be noted that GDC re-normalizes the given kernel like a normalized adjacent matrix. Thus, in this paper, we use PageRank kernel such as APPNP (Klicpera al., 2018). Simple Spectral Graph Convolution GS (Zhu & Koniusz, 2021)) is based on a modified Markov diffusion kernel (Fouss et al., 2012). Although these methods are effective on node classification, fixed parameters ignore the graph property homophilyyheeterpphily and node attributes in different dimensions. These drawbacks limit such methods on heterophilous graphs.
Learnable graph convolutions Chebyshev polynomials are used by ChebNet (Defferrard et al., 2016) to approximate the graph convolutions. In theory, one can learn any kind of filter (Balcilar et al., 2021). With Cayley polynomials, CayleyNet (Levie et al., 2018) learns the graph convo- lutions and produces a variety of graph filters. Low-pass or high-pass filters can be derived from graph convolutions. GPR- GNN (Chien et al., 2021) employs the Monomial basis to approximate these filters. Through the family of Auto-Regressive Moving Average filters (Narang et al., 2013), ARMA (Bianchi al., 2021) learns the rational graph convolutions. The graph convolutions approximated in BernNet (He et al., 2021). which also learns graph filter using the Bernstein basis. Although these methods achieve good performance on different datasets, the learnable parameters of the graph convolution kernel depend only on the label information, which leads to overfitting due to too few or unbalanced labels.
Graph Neural Networks for Heretophily Graphs are not always homophilic. The opposite is true on connected node groups. This makes it harder for existing homophilic GNNs to learn from general graph-structured data, which leads to a significant drop in performance on heterophilous graphs. Increasing Homophilic Edges (HoE) and decreasing Heterophilic Edges (HeE) are two mainly ways to improve feature propagation. HoE refers to edges connecting two nodes of the same class while HcH means edges connecting two nodes of different classes. The strategies of increasing increasing HoE include using two-hop (or higher) neighbours and discovering new neighbours with feature similarity. Decreasing Heterophilic Edges (HeF) assigns the weights on edges to reduce the impact from potential heterophilous edges. At each message passing step, H2GCN (Zhu et al., 2020) aggregates data from higher-order neighbors. In order to offer theoretical guarantee, H2GCN con- firms that when one-hop neighbors' labels are conditionally independent, two-hop neighbors tend to include more nodes belonging the same class. The generalised PageRank used with graph convolutions in GPR-GNN (Chien et al., 2) to jointly maximise the extraction of node features and topological information for both homophilous and heterophilous graphs. These methods are based on transductive learning. Without label information they cannot learn a useful model. Graph convolution based methods such as SGC, SCGC and PageRank do not need labels at all.
METHODS
In this section, we review the classical Label Propagation with Laplacian Regularization (Zhou et al., 2003) and show the relationship between his iterative solution and the existing GNNs. Then, by analyzing the closed form of LP, we formulate the label propagation to residual minimizing in Krylov subspace to learn parameters for graph convolution. To overcome the Runge phenomenon, we reformulate residual minimizing problem in Krylov subspace to a more general polymonimial approximation problem, which helps introduce other kinds of bases such as Chebyshev and Berstein polynomials.
3.1 PRELIMINARIES
Let G = (V, be a simple and connected undirected graph with n nodes and m edges. We use {1, .1.... ,n] to denote the node index of G, whereas d, denotes the degree of node j in G. Let
3

---

Under review as a conference paper at ICLR 2023
A be the adjacency matrix and D be the diagonal degree matrix. Let A A In denote the adjacency matrix with added self-loops and the corresponding diagonal degree matrix D, where In E _2 is an identity matrix. Finally, let X E RR" denote the node feature matrix, where each node is associated with a d-dimensional feature vector Zv. To facilitate the definition of dimension-ine -nndeeddnnnde objective functions, we use E R to denote 1D node features.
Label Propagation with Laplacian Regularization. A classical regularization framework for label (or feature) propagation (Zhou et al., 2003) includes two components: fitting term with least square and a smoothing term with Laplacian regularization. The fitting term controls the target so is not far away to the original point. The smoothing term encourages the connected elements have similar scale. The loss function associated with f IR defined as:
E(f)
Asj
VD# fi
1 VDj
f
Σ
1I: -5ll
(1)
2
1=1
where μ > is the regularization parameter. Differentiating {ff with respect to f. we have
aQ
f=f- =f -f + y) 0.
0f
Although there exist a closed-form based on Eq. 2, for large graphs the inverse of I a is not practically-fessible to compute, and instead iterative approximations are preferable. To this end, we may set (0) and then proceed to iteratively descend in the direction of the negative gradient:
f ff + (1 -1--0 af)
(3)
where T+, If we define y f(X; 0) and replace A with Á. Eq. 3 equates to principled GNN layers, such as those used by GCN (Kipf& & Welling, 2016), APPNP (Kliepera et al., 2018).
3.2 LABEL PROPAGATION WITH RESIDUAL MINIMIZING OVER KRYLOV SUBSPACE
In this section, we reformulate the closed-form solution label propagation with Laplacian reg- ularization (Zhou et al., 2003) to more generalized model based on Residual Minimizing over Krylov Subspace to solve for the parameters for graph convolution.
Let remind the closed-fomm solution Eq. 1: f solution into the fitting term of Eq. 1, we have:
aI aA)-'y y. If put the closed-form
min y fl12 min y (1-a) aA) min lla A Σ A yull f
<=0
where w; (1 a)a'. We could rescale by (1 a) to eliminate the parameter 8. Please note r rank(A) (A). Then we obtain a more compact form:
min 1/
A Σ
A'yll = min (A.6)
||
Aa
weRt-
1=0
where the set of vectors KC, (A. y) {y,Ay, Ay, A A } is called the order-r Krylov ma- trix, and the subspace spanned by these vectors is called the order-r Krylov subspace. Based on this obtain denoised signal as A...
Relation to GPR-GNN (Chien et al., 2021), GPR-GNN first extracts hidden state features with a MLP for each node and then uses Generalized PageRank (GPR) propagate them. The GPR-GNN process can be mathematically described as:
softmax 2) Z
H HIH = (K-1-1 H = (X;
(6)
2,
where softmax Z...) Σラ= 3.5
Although Generalized PageRank looks similar to the purpose
of our approach, we notice three key differences: (1) The GPR learns generalized graph convolution on logits rather than features (or attributes). (2) The parameters in GPR only depend on labels rather than internal information of the graph and the corresponding attributes. (3) There no global optimal solution for GPR-GNN because of the feature extraction with ML.P
4

---

Under review as a conference paper at ICLR 2023
3.3 POLYNOMIAL APPROXIMATION WITH CONSTRAINTS
The Eq. 5 also solves an approximation problem. The only difference being that the space of poly- nomials is now P. { polynomials p of degree r with pr( 1}. Expressed in terms of polynomial coefficients, we have a constraint of we = 1. Here is how Eq. 5 can be reduced to the polynomial approximation in P.. The iterate z can be written as a 9r (A),. where q. is a poly- nomial of degree r 1; its coefficients are the entries of the vector w of Eq. 5. The corresponding
residual r y A. is = Aq, (A)) y. we define pr(2) = 2qr (2), which is the polynomial, we have pr for some polynomial Pr Pr. Thus, we can reformulate Eq. 5 as:
min (A,b)
1 A =
min (|p)(A)yll)
P. P.EP..D.(0)
where P. is the set of all polynomials pr of degree at most such that p+(0) =.
Chebyshev polynomials are frequently employed in digital signal processing and graph signal fil- tering to approximate variety of functions. The analytical functions may be approximated by minimax polynomial using the truncated Chebyshev expansions. Consequently, a truncated expan- sion expressed in terms of Chebyshev polynomials can minimize the Ioss function as follows:
min R
w.TT(L)
(8)
where É 222 Amax I denotes the scaled Laplacian matrix. Amma is the largest eigenvalue of L and Wy denote the Chebyshev coefficients. The Chebyshev polynomials can be recursively defined as Ty (z) (x)) - 2x)) with To(x) = 1 and (x) = I. Although Chebyshev poly-
nomials have many great properties such as relieving the Runge phenomenon, they underperform in GNNs. How to solve this problem is beyond the scope of this paper.
3.4 THEORETICAL ANALYSIS
We study our method in the contextual stochastic block model (cSBM) (Deshpande et al., 2018), which is a generative model for random graphs For the purposes of theoretical analysis, we take into account CSBM model with classes, co and c1. The generated graphs in this instance have nodes made up of two distinct sets, Co and C₁, which represent the two classes, respectively. An intra-class probability p and an inter-class probability q are used produce edges. In particular, an edge is constructed to connect any two nodes in the graph with probability p if they belong to the same class, and q otherwise. For each node i, its initial associated features 2; E RR are sampled from Gaussian distribution Hence, we denote graph generated from such an cSBM model as G ~ cSBM (M), 42, P. p).). and the features for node obtained after first-order graph convolution as h! and h with second-order graph convolution.
N N(,, o1) where μ Me E I for i E CR with & E {0, 1}.
Ma et al. (2022) propose very interesting problem 'Is homophily necessity for graph neural networks?' very useful property has been proven that first-order graph convolution can provide better features if the deg(i) > (p+tg)² is met, which demonstrates that the node degree deg(i) (p-q)"
and the distinguishability (measured by the Euclidean distance) of the neighborhood distributions both affect graph convolution performance. This condition often happens in practice. Thus, we are interested whether or not the higher-order graph convolution still enjoy such a property. As the proposed method could be regarded as multi-scale graph convolution, it is important to know whether there are existing parameters that make the multi-scale graph convolution better than single graph convolution.
To better evaluate the effectiveness of our method, we study the linear classifiers with the largest margin based fæ,, i V). {h! E V} and {hद V} compare their performance. Here define relation among wc, h! and h² follows:
h
Σ
xy and h deg(i) jEN(()
Σ h).
deg(i)
JEN())
where (i) denotes the neighbors of node i.
5

---

Under review as a conference paper at ICLR 2023
For graph G ~ cSBM M42 p. q). we approximately regard that for each node i, its neigh- bor's 's labels are independently sampled from a neighborhood distribution Dz., where yi denotes the label of node i. Specifically, the neighborhood distributions corresponding to co and
2 and Da - p+g ptol respectively. Based on the neighborhood distributions, Deo = و 1- p+gl
the features obtained from Graph Convolution follow the Gaussian distributions:
PPo + q/4
h2 ~ N (deg(0)( 1² M40
1.1) for i Co, 2pqun + + +
h N
p+ q
deg(t) I
P+9
914 + PP1
h N (dcg(i)) P + 2pqp4 + gbmu) I) for i C1. /de((i)
h N
P q
p+ q
(10)
Proposition 1. (Ma et al., 2022) (Beco [2r.] [ Reg (mn]]) and (Beo [ha], Bei [h,]) share the same middle point. Ece [æ;]- - Ee, [xi] and Eeo [h,] - Ec, [he] share the same direction. Specifi- cally, the middle point m and the shared direction w as follows: = (nn + p1) /2, and w = (po μ1) || -21122-
This proposition follows from direct calculations. Given that the feature distributions of these two classes are systematic to each other (for both æ; and h, ). the hyperplane that is orthogonal to ur and goes through m and defines the decision boundary of the optimal linear classifier for both types of features. We denote this decision boundary as P { w x w (no + 11) /2]. Next, to evaluate how higher-order graph convolution affects the classification performance, we compare the probability that this linear classifier misclassifies a certain node based on the features after first-order graph convolution and after the second-ores graph convolution. We summarize the results in the following theorem.
Theorem 3.1. Consider graph G ~ cSBM (nr, MI q). For any node in this graph, the linear classifier defined by the decision boundary P has a lower or equivalent probability to misclassify h3 than h! when deg(i) > (p - /pp ?
Proof. We only prove this for nodes from classes co since the case for nodes from classes e1 is symmetric and then the proof follows. For node E Co. we have the follows
I (h) is mis-classified)
P (w T h + b < 0) for i E Co, and IP (h) is mis-classified = (w h + S 0) for E Co.
(11)
where w and b = - T (n0 + 11) /2 is the parameters of the decision boundary P. We have w T h + b - 0) = P (w TuTVen deg(())); + dde((i) S 0) and
(12)
w h2 + b < 0) = P w Vdeg(i) + /deg(i)b o)
We denote the scaled version of h and h h / deg(1) hi) and h" / deg(i)h? respectively. Then, h/ and h² follow
h1 /deg(i)h) N Vdee(i) (apd que)) .1), for i Co, and
p+q
(13)
= deg(i)) ~ (eg(()) p² No 2pqpu + (Hu) (111), ),11). for i Co-
1):
p+g
Now, since h and h" share the same variance, to compare the misclassification probabilities, we only need to compare the distance from their expected value to their corresponding decision bound- ary. Specifically, the two distances are:
disM: / deggi)(p - 4) ||m0 - -111l1 and dis deg(i)(p g)²
|| M1lle
(14)
(p 9)
2
(p + g)2
2
The larger the distance is the smaller the misclassification probability is. Hence, when disn; disny, hy has lower probability to be misclassified than h and æ; Comparing the two distances, we conclude that when deg(i) > (p + q)2/(p q)². h" has a lower probability to be misclassified
than h/:

---

Under review as a conference paper at ICLR 2023
Raw
Raw
100
SGC
100
GC2
SSGC
100
Sum Graph Convolutions
PageRank
100
Difference Graph Convolutions
Ours
100
100
-3
-2
(a) Graph Convolution (GC)
(b) Graph Convolution based Methods.
Figure 2: Distribution of the feature values on highly heterophilous synthetic graph before and after using different graph convolution based methods.
Mean Abs. Error
0.8
022
0.6
GC2R7
0.5
-0.5
(Heterophilous)
(Homophilous)
(Heterophilous)
(Homophilous)
Figure 3: Results on the contextual SBM using graph convolutions with first-order (GC), second- order (GC2), third-order (GC3) and fouth-order (GC4). Two different combination of graph convo- lutions have been considered: the difference between first two-order (GCdiffl) and the difference between even orders and odd orders (GCdiff2).
7

---

Under review as a conference paper at ICLR 2023
Theorem 3.2. When p q (heterophilous graphs) the presence of the parameters w1 0 and W2 > 0 allows wy h w to have lower probability to be misclassified than h2 when (1-wa)² dog(i(p-a)= Please refer the appendix for proof. (ptg)
wf
4 EXPERIMENTS
4.1 RESULT ON CSBM SYNTHETIC
Synthetic data In order test the ability of graph convolution based methods with arbitrary levels of homophily and heterophily, we use cSBMs (Deshpande et al., 2018) to generate synthetic graphs We consider the case with two equal-size classes and take into account cSBM with n 1000, two communities Co and Ci, feature means /40 and μ = -1, and noise variance = 1. Then there are 500 nodes each community, which we will refer to as "positive" and "negative," respectively. Standard normal noise is applied to the feature means of the nodes in the "positive" community, which is 1, and the "negative" community, which -1. With the expected degree of all nodes set 10), create various graphs by varying the intra- and inter-community
to 10 (i.c., 2(p + g)n edge probabilities p and y from p > q (highly homophilous, in that "positive" nodes are much more likely to connect to other "positive" nodes than to "negative" nodes) to q p (highly heterophilous, in that "negative" nodes. We compare our methods with three baseline models: Raw, SGC (Wu al., 2019), S²GC (Veličković al., 2017), PageRank (Page al., 1999; Klicpera et al., 2018). At the sametime, we also evaluate first-order graph convolution (GC), second-order graph convolution (GC2), the sum of graph convolutions and the difference of graph convolutions.
As shown in Figure la, we found that some low-pass filters (SGC and APPNP) can have a positive effect on some heterophilous graphs .pt. -1) with a low number of convolutions (second-order), However this phenomenon rapidly disappears as the number of convolutions increases as shown in Figure 1b, and when K = 8 it can be seen that all low-pass filters perform much worse than the original features on synthetic heterophilous graphs. In theoretical analysis, we prove the second- order graph convolution can provide more discriminant features than first-order graph convolution and raw features. As shown in Figure 2a, the distribution of the feature values can qualitatively state this view. We found that in heterophilous graphs, first-order graph convolution may change the sign of the features. Thus for methods that use non-negative weights, such as PageRank, S'GC, this leads to the class centre of the features moving closer the features' centre (global centre) as shown in Figure 2b. And the proposed method is able to keep the distance between two class centers and reduce the intra-class variance. As shown in Figure 3, we found the second-order graph convolution is better than the first-order graph convolution in graphs with different heterophilous score, The difference between recond-order and first-order graph convolutions can provide better graph convolution in heterophilous graphs while p-g < 00.6. p+g
4.2 REAL WORLD BENCHMARK
We use homophilous benchmark datasets available from the Pytorch Geometric library, including the citation graphs Cora, CiteSeer, PubMed (Sen et al., 2008; Yang et al., 2016) and the Amazon co-purchase graphs Computers and Photo (McAuley et al., 2015; Shchur et al., 20. We also use 5 heterophilous benchmark datasets tested in (Pei et al., 2020), including Wikipedia graphs Chameleon and Squirrel, the Actor co-occurrence graph, and webpage graphs Texas and Cornell from WebKB. We summarize the dataset statistics and results in Table and 2.
Results on real-world datasets. We use accuracy (the micro-F1 score) as the evaluation met- ric along with a 95% confidence interval. The relevant results are summarized in Table 2 For homophilous datasets, we provide results for sparse splitting 2.5%/2.5%/95% splits as train- ing/validation/test data) as same the definition in Chien et al. (2021) 1), which is different with the original setting used in (Kipf & Welling, 2016); (Shchur et al., 2018). For the heterophilous datasets, adopt dense splitting ( 600%/20%/20% splits
data) which is used in (Pei et al., 2020). We apply our SGC, SCGC and PageRank implementations to these datasets and present the mean test accuracy over 10 randomly split data sets. We also provide baseline on
aaaniing/alidattinn/ee
8

---

Under review as a conference paper at ICLR 2023
Table 1: Statistics and results on homophilous datasets: Mean accuracy (%) - 95% confidence interval. As expected due to design, on homophilous datasets, our method is only comparable to other graph convolution based methods because the low- low-pass filtering is all we need in this situation.
CORA
CITESEER
PUBMED
COMPUTER
PHOTO
Nodes
2708
3527
19717
13752
7650
Edges
Features
1433
3703
500
767
745
Classes
6
(())
0.825
0.718
0.792
0.802
0.849
Raw
55.09 = 1.81
60.30
+ 1.55
77.79 +: 0.95
76.07 + 0.57
82.97 = U
73.90
1:
92.03
SºGC
78.57 1.64
70.34 1: 1.04
82.89
0.46
86.94 1 0.51
92.89
0.58
PageRank
77.65 = 1.70
70.51 +: 1.05
75.05 +: 1.38
87. + 0.46
92.95
0.37
74.94
0.97 78.72
86.72 0.50
91.74
MLP
50.34 0.48
52.88
+ 0.51
80.57 0.12
70.48 : 0.28
78.69
0.30
GCN
75.21 1 0.38
67.30
1. 0.35
84.27 1: 0.01
82.52 1. 0.32
90.54
0.21
GAT
76.70 + 0.42
67.20
0.46
83.25 0.12
81.95 + 0.38
90.09
0.27
SAGE
70.89 = 0.54
0.44 61.52
81.30 0.100
83.11 0.23
90.51
0.25
73.22
82.91 0.11
0.97
87.70
GCN-Cheby
71.39 = 0.51
05.67 0.38
83.83 0.12
82.41 = 0.28
90.09 0.28
GeomGCN
20.37 1.13
20.30
+ 0.90
58.20 + 1.23
NA
APPNP
79.41 0.38
68.59
1: 0.30
85.02 0.09
81.99 + 0.26
91.11 0.26
GPRGNN
79.51 0.36
67.63
1: 0.38
85.07
0.09
82.90 1: 0.37
91.93 0.26
Table 2: Statistics and results on heterophilous benchmark datasets: Mean accuracy (%) + 95% confidence interval. As expected due to design, our methods all meet or exceed the performance of raw features and are not affected by the heterophilous property like other graph convolution methods.
CHAMELEON
SQUIRREL.
ACTOR
TEXAS
CORNELL
Nodes
5201
7600
183
Edges
31421
198493
26752
295
280
Features
2089
1703
Classes
5
H())
0.247
0.217
0,215
0.057
0.301
49.56 0.88
36.28
SGC
57.70 1: 1.62
44.98
1: 1.28
30.07
1: 0.76
55.68 1: 5.71
54.32 1: 6.41
SOGC
50.35
1.51
37.77
+ 0.78
33.99 1: 0.84
71.08
+ 4.74
62. + 6.91
PageRank
58.68 2.14
0.68
33.27
7.03
63. 03.24
6.26
Ours
72.28 + 0.90
58.98
+ 1.01
36.45 1:66::00 0.79
86.76 + 3.58
86 09
- 3.08
MLP
46.72 0.46
31.28
1: 0.27
38.58
0.25
92.26 1 0.71
91.36 1 0.70
GCN
60.96 0.78
45.66
1: 0.39
30.59
0.23
75.16 0.96
66.72
1.37
GAT
63.90 0.46
0.46
42.72 0.33
0.23 35.98
78.87 + 0.86
76.00
+ 1.01
SAGE
62.15
41.26
0.26
36.37
1.24
JKNet
62.92 0.49
44.72 1: 0.48
0.25 33.41
75.53 + 1.16
66.73 : 1.73
Cheby
59.96 0.51
1.04
GeomGCN
61.06 0.49
38.28
+ 0.27
31.81
0.24
58.56 - 1.77
55.59
- 1.59
APPNP
51.91 0.56
34.77
1: 0.34
38.86
0.24
91.18 1 0.70
91.80
0.63
GPRGNN
67.48 0.40
49.93 4 0.53
39.30
0.27
92.92
0.61
91.36
0.70
the precision of logistic regression using the attributes without taking into account the graph convolution.
Table shows that, in general, Our method cannot beat other convolution methods based on low- pass filtering designs such as SGC, S²GC and PageRank on homophilous datasets. However, our approach still outperforms some classical GNNs like SAGE, JKNet, GCN-Cheby and GeomGCN. GPR-GNN achieves the state-of-the-art performance. On heterophilous datasets, our method sig- nificantly outperforms all the other graph convolution models. On Chameleon and Squirrel, we outperform other methods. It is worthy to note our approach outperform the GPR-GNN, which use the same monimial basis as our method. This is good case to prove that the label is not necessary for heterophilous graphs. In actor, most methods cannot outperform the corresponding baseline. Except ours, all graph convolution based methods cannot outperform raw attributes with logistic regression. Similarly, only APPNP and GPRGNN can outperform raw attributes with MLP. On the Texas dataset, all methods behave similarly to those on Actor. The only difference is APPNP cannot outperform the baseline while ours and GPRGNN outperform the baseline method. Conrnell is the most challenge dataset for all methods, no one can outperform the baseline (Logistic Regression and ML.) although ours and GPRGNN can have the same performance.

---

Under review as a conference paper at ICLR 2023
5 CONCLUSION
From an optimalization perspective we propose an novel framework for label (or feature) propaga- tion that is not based on Laplacian regularization. This framework extends label propagation from the least squares problem to polynomial approximation, and sheds light on graph convolution with heretophilous graphs. We show we can learn (unsupervised setting) a graph convolution that obtains better features than raw attributes. In synthetic data experiments, we show that our method has bet- ter properties on heterophilous graphs compared to existing fixed parameter graph convolutions. In real-world benchmarks, our method even outperforms some methods that use label information.
REFERENCES
Sami Abu-El-Haija, 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, PMLR, 2019.
James Atwood and Don Towsley. Diffussion-convolutionaall neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In Proceedings of the International Conference on Learning Representations (ICLR). 2021.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL
https: httpss///ppeeeeeeeee wwt/forumm Eorum?id=n6j177Exxz
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, 29, 2016.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.
François Fouss, Kevin Francoisse, Luh Yen, Alain Pirotte, and Marco Saerens. An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classifi- cation. Neural networks, 31:53-72, 2012.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pp- 2263-1272. PMLR, 2017.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-1500 2011.
Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34:14239-144 14251, 2021.
Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal graph convolutional networks. Advances in Neural Information Processing Systems, 34:10654- 10664, 2021.
10

---

Under review as a conference paper at ICLR 2023
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.0500 2018.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. arXiv preprint arXiv:1911.05485 2019.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1))97-109 2018.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 2021.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? International Conference on Learning Representations, 2022.
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 on research and development in information retrieval, pp. 43 53,52, 2015.
Sunil K Narang, Akshay Gadde, and Antonio Ortega. Signal processing techniques for interpolation in graph structured data. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing. pp. 5445 5449. IEEE, 2013.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.052: 202222002..2.,.... 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):33-93, 2008.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1.05668, 2018.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns, arXiv preprint arXiv:2106.00 06586, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17/0. 10903, 2017.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference machine learning, pp- 6861-6871. PMLR, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462. PMLR, 2018.
Liang Yang, Mengzhe Li, Liyang Liu, Chuan Wang, Xiaochun Cao, Yuanfang Guo, al. Diverse message passing for attribute with heterophily. Advances in Neural Information Processing Sys- tems, 14:4751-4773. 2021.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning. pp. 40-48. PMLR, 2016.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.070082 2022.

---

Under review as a conference paper at ICLR 2023
Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793- -804, 2020.
A APPENDIX
A. PROOF OF THEOREM 3.2
Proof. We could add w1 and W2 into Eq. 14 and have:
W1 deg(i( ②) ll Milla
w2 deg(i)(p q)²
|| - 11ll2
discomb
(p+
2
(p + q)
(15)
u11 / deg( (p ②) w2 deg(t)(p 2)
Mo H1llz
(p 9)
(p 9)²
We hope the discomb is larger than disny then we need the following inequation:
W1 v de 4) + w2 deg(i)(p q)²
dp q)²
(p +
(p+ 122
(p + 4)2
(16)
/ deg(i)(p - 9)
(1 -22) deg( 9)²
(p+
(p 0+99 9)2
(deg(e)(-o)) (x+4)
We can assume
> 1 and then we have:
w
deg( (e) (p - 9)²
(17)
(1 W2)
(p + q)²
12


Reviews:
[{"review_id": "yDqJGfWyrb", "reviewer": "Reviewer_EaVm", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper proposes a novel approach for shallow graph representation through combining the idea behind label propagation with Krylov subspace methods. Label propagation is applied to the node features, and then the closed form solution is substituted into a least squares fitting term, which is then reparametrized using the Krylov subspace of order-r. Interpretation is provided as a polynomial approximation problem, and extension using Chebyshev polynomials is proposed. Theoretical analysis is provided in the context of the contextual stochastic block model in support of the approach. Experiments are carried out on synthetic data, and real-world node classification datasets.", "summary_of_the_review": "The paper combines label propagation with optimization over Krylov subspaces. The core idea seems interesting, but the point seems lost in the convoluted exposition, technical inconsistencies in the derivation. The presentation could be improved to help better convey the idea. Experimental results only show strong performance on 2 out of 5 heterophilous datasets, while on the other 3 it performs the same as raw logistic regression, hence the feature propagation effectively having no effect. On homophilous datasets mostly weaker performance compared to baselines.", "strength_and_weaknesses": "## Strengths:\n- The formulation in terms of the Krylov subspace is interesting and novel.\n- Improvement on some heterophilous datasets (CHAMELEON and SQUIRREL)\n- Theoretical analysis supports hints at some benefits of the approach on heterophilous datasets\n\n## Weaknesses:\n- The exposition is very convoluted.\n- The motivation behind the core idea seems lost.\n- Minor problems in the algorithm formulation.\n- On most other datasets the approach underperforms.  \n\n### The exposition is very convoluted.\nThe related work section mentions several approaches, but the discussion provided for each of them is confusing. Although the authors have tried to connect it to the current work, these points are hard to follow. Similarly, the \"Relation to GPR-GNN\" section is also hard to follow, where there is new notation used but not defined.\n\n### The motivation behind the core idea seems lost.\nIt seems to me that the main idea behind the approach is to substitute the closed form solution of LP into the least squares \"fitting term\". Why this is a good idea is not discussed at the moment. The formulation of the algorithm here seems unmotivated, and there are also minor errors, which further blurs the intuition.\n\nI was also confused about the role of the \"Polynomial Approximation with Constraints\" section. The contribution of the first paragraph is tautological. Parametrizing the least squares solution in terms of the Krylov subspace is obviously equivalent to minimizing the residual with respect to all polynomials of order-r over $\\mathbf{A}$. The second paragraph, on the other hand, suggests to use Chebyshev polynomials instead, but then at the end the authors say Chebyshev polynomials underperform in GNNs. No results are reported for this setting either. This makes me wonder why the authors chose to include this paragraph.\n\n### Minor problems in the algorithm formulation.\nI have found several inconsistencies in the mathematical derivation of LP and the Krylov subspace formulation. First, equation 3) seems incorrect since LP does not use the adjacency matrix $\\mathbf{A}$ in the update rule, but its normalized counterpart $\\mathbf{D}^{-1/2} \\mathbf{A} \\mathbf{D}^{-1/2}$. This follows from the Dirichlet energy term containing the division by $D_{ii}^{-1/2}$ in equation 1).\n\nFurther, in equation 4) the second equality is not true. In general, minimizing the quantity on the rightmost hand side with respect to $\\mathbf{w}$ is not equivalent to minimizing the one on the middle with respect to $\\alpha$. In particular, the minimum will be lower. Afterwards, the authors state that $w_i = (1 - \\alpha)\\alpha^i$. This contradicts the previous line, where optimization over $\\mathbf{w} \\in \\mathbb{R}^n$ was denoted to be unconstrained. Overall, there are some inconsistencies here, which make me unsure about the actual algorithm the authors use.\n\n### On most other datasets the approach underperforms\nOn the homophilous datasets, it seems like the approach is outperformed by both shallow and deep baselines. On the heterophilous datasets, it outperforms all baselines on 2 datasets, while for the other 3, it performs on par with raw logistic regression  (i.e. without connectivity information) and outperformed by deep baselines. Overall, these results are not convincing enough for me. It is not investigated where the improvements come from on the 2/5 datasets. Training time comparison against shallow/deep baselines is not reported.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lIyLyORyqA", "reviewer": "Reviewer_MznN", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper addresses the problem of graph learning and label propagation from an optimization perspective. A theoretical framework is presented which exploit least squares to obtain a graph representation. The authors claim multiple contributions. First, it is investigated whether node labels are necessary to learn an informative representation, in the scenario of heterophilous graphs. Then, both a theoretical and experimental analysis is conducted to assess the validity of the proposed approach. ", "summary_of_the_review": "I believe the paper is valid but misses a strong contribution on the theoretical or experimental side. ", "strength_and_weaknesses": "The paper presents the problem from an innovative perspective and proposes a link with label propagation and laplacian regularization. I believe the contribution of the paper is limited. I don't see a strong theoretical neither experimental contribution. The methodological development could benefit from more detailed explanations. For example, the claim that labels are not needed could be better empahsized. \n\nThe empirical analysis could be more comprehensive, besides the results are not fully supporting on the effectiveness of the method. In particular, one could explore more on the synthetic data side. For example, study the effect of varying parameters like the number of graphs or degree. Furthermore, especially given that it is a non deep learning based methods, it would be useful to investigate the runtime and scalability aspect. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PX1-2wO23m6", "reviewer": "Reviewer_VWj7", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors proposed a method to propagate node features without labels and still achieve competitive performance in both heterophilous and homophiles graphs. They reformulated the spectral convolution into a residual minimization problem and provide extensive experiments with different orders of convolution and different GNN based models. ", "summary_of_the_review": "The authors provided a different perspective on graph convolution using residual minimization and Chebyshev polynomials for approximation. However the theorems only shows the benefits of second order information, the potential complexity for higher order information in the closed form approximation is still unclear. The empirical form also ends up very similar to GPR-GNN. Without further elaboration on the necessity and complexity analysis, I am not leaning towards recommending the paper. ", "strength_and_weaknesses": "Pros: \n- Training does not depends on label information hence more robust to noise and biases in training data labels. \n- Solving the spectral convolution directly which can potentially avoid over-smoothing and leverage long-range interactions. \n- No traditional BP process is needed. \n- Extensive comparison to different GNN models and tested on various synthetic and real-world datasets. \n\nCons: \n- Typo above equation (5), \\beta is not defined.\n- I think last step in eq(4) is still an approximation and not a strict equal, i.e. not an exact closed form. If it is a approximation, how do we choose r? \n- The theoretical guarantee only consider up to 2nd order information, gap between 2nd order and the close-form solution is missing and only marginally support the necessity of higher order information. \n- I am interested in the computational complexity needed in solving eq(5) and (8). How does the method compare to GNN based methods? \n- Although the authors claims propagation on heterphily graphs should not depends on labels, the definition of H(\\mathcal{G}) and cSBM is still label-dependent. Are there examples where we can see some cases it doesn’t depend on node labels? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4MzJlRnjkSF", "reviewer": "Reviewer_Zwbq", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper proposes a generalisation of the family of linear networks (SGC, SSGC, APPNP, etc.) to heterophilous graphs. In contrast to existing methods which work well with homophilous networks, this work studies an objective which can work well with heterophilous graphs. Authors demonstrate the least squares based solver based on Krylov subspaces which attempts to find a set of weights which produce a network which preserves node attributes.", "summary_of_the_review": "Main comments:\n\n1. In Eq. 4 and Eq. 5, do authors use class labels or attribute channels? The reviewer guesses it is attribute channels to ensure the model is an unsupervised model. This detail could be made clearer. Additionally, does Eq. 5 result in one set of weights or d set of weights assuming attributes have d channels? Could authors compare both cases?\n\n2. Do authors ablate the impact of hyper-parameter r? Is there a sweet spot for r, or is it the best to select the largest r in each experiment?\n\n3. Section 3.3 shows an extension of the proposed idea to optimisation over Chybyshev polynomials. Does this mean the authors could apply a simple network with weighted polynomials of degrees 1...r? If so, it would be interesting to see some result for such a problem.\n\n4. Can authors comment on the complexity of the approach? Are Krylov subspaces used because they can find weights for consecutive diffusions $A, A^2, A^3,...$ of the linear network design or they are somehow more central to heterophily?\n\n5. Section 3.4 provides a theoretical analysis. Are $\\mu$ representing attribute centers? If p and q are inter- and intra-class probabilities of edge connectivity, does this mean p represents heterophily and q represents homophily?\n\n6. Is there any simple strategy that could combine homophilous and heterophilious graph classification strategies?\n\n\nMinor comments:\n\n1. Dimensions of w appear to differ in Eq. 4 and Eq. 5. Do authors mean r-1 or r for the dimension of w? The same goes for Eq. 8.\n\n2. Page 7 appears to have issues with floats (big gap between two figures).", "strength_and_weaknesses": "\\+ the problem of learning graph representations without class labels is interesting and timely\n\n\\+ the results on heterophilous graph benchmarks is SOTA\n\n\\- results on homophilous benchmarks could be higher \n\n\\- writing can be improved in some parts of the paper", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject