Effective Polynomial Filter Adaptation for Graph Neural Networks
Authors: Vijay Lingam
Chanakya Ajit Ekbote
Manan Sharma
Rahul Ragesh
Arun Iyer
SUNDARARAJAN SELLAMANICKAM
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Neural Networks
Graph Filters

Abstract: Graph Neural Networks (GNNs) exploit signals from node features and the input graph topology to improve node classification task performance. However, these models tend to perform poorly on heterophilic graphs, where connected nodes have different labels. Recently proposed GNNs work across graphs having varying levels of homophily. Among these, models relying on polynomial graph filters have shown promise. We observe that solutions to these polynomial graph filter models are also solutions to an overdetermined system of equations. It suggests that in some instances, the model needs to learn a reasonably high order polynomial. On investigation, we find the proposed models ineffective at learning such polynomials due to their designs. To mitigate this issue, we perform an eigendecomposition of the graph and propose to learn multiple adaptive polynomial filters acting on different subsets of the spectrum. We theoretically and empirically show that our proposed model learns a better filter, thereby improving classification accuracy. We study various aspects of our proposed model including, dependency on the number of eigencomponents utilized, latent polynomial filters learned, and performance of the individual polynomials on the node classification task. We further show that our model is scalable by evaluating over large graphs. Our model achieves performance gains of up to 10% over the state-of-the-art models and outperforms existing polynomial filter-based approaches in general.

Under review as a conference paper at ICLR 2022
A PIECE-WISE POLYNOMIAL FILTERING APPROACH FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) exploit signals from node features and the input graph topology to improve node classification task performance. However, these models tend to perform poorly on heterophilic graphs, where connected nodes have different labels. Recently proposed GNNs work across graphs having vary- ing levels of homophily. Among these, models relying on polynomial graph filters have shown promise. We observe that solutions to these polynomial graph filter models are also solutions to an overdetermined system of equations. It suggests that in some instances, the model needs to learn a reasonably high order polyno- mial. On investigation, we find the proposed models ineffective at learning such polynomials due to their designs. To mitigate this issue, we perform eigende- composition of the graph and propose to learn multiple adaptive polynomial filters acting on different subsets of the spectrum. We theoretically and empirically show that our proposed model learns better filter, thereby improving classification ac- curacy. We study various aspects of our proposed model including, dependency on the number of eigencomponents utilized, latent polynomial filters learned, and performance of the individual polynomials on the node classification task. We fur- ther show that our model is scalable by evaluating over large graphs. Our model achieves performance gains of up to 10% over the state-of-the- models and out- performs existing polynomial filter-based approaches in general. Our anonymized code is available at https: : /tinuuri com/ PPGNN.
INTRODUCTION
In this work, we are interested in the problem of classifying nodes in graph. In this problem, graph and features for all the nodes the graph are made available. We are also given labels for subset of the nodes in the graph. The learning model utilizes this information to predict labels for the remaining nodes. Graph Neural Networks (GNNs) perform well on such problems (Kipf & Welling, 2017). GNNs predict node's 's label by aggregating information from its neighbours. Thus, the performance of GNN is dependent on how well the given graph correlates with the node labels. Characterizing the correlation between the graph and node labels is an active area of research. Several metrics have been proposed including edge homophily (Abu-EI-Haija et al., 2019a; Zhu al., 2020), node homophily (Pei et al., 2020), class homophily (Lim et al., 2021). All these metrics show that GNNs perform well when the graphs and node labels are positively correlated. For example, in the simplest case, GNNs work well when the node and its neighbours share similar labels. However, the performance can be poor if this criterion is not satisfied.
Several proposed GNN models attempt to be robust the underlying correlation between graphs and labels. Some approaches modify the aggregation mechanism (Pei et al., 2020; Zhu et al., 2020; Kim & Oh, 2021), while other approaches propose to estimate and leverage the label-label compatibility matrix as a prior (Zhu et al., 2021). More recent approaches have tackled this problem from filter learning perspective (Bo et al., 2021; Chien et al., 2021). These methods learn filter function that operates on the eigenvalues of the graph. With eigenvalues having frequency interpretations (Shu- man et al., 2013), the filter function selectively accentuates and suppresses various frequencies as required by the task. This process enables the model to learn better embeddings. which translates to improved performance. Our interest lies in the area of modelling GNNs that can learn an effective filter.

---

Under review as a conference paper at ICLR 2022
Chien et al. (2021) proposed to learn a polynomial filter. This model achieves good performance gains on several datasets with varying correlations between graphs and labels. However, we observe that learning polynomial of degree lower than the number of nodes can be seen solving an over-determined system of equations. Our observation suggests needing a higher-order polynomial to model richer more complex frequency responses for certain datasets. The design of the model proposed in Chien et al. (2021) makes it ineffective in learning a higher-order polynomial. It happens because the model attempts overeome over-smoothing by giving smaller coefficient values to larger powers. In this paper, we address this issue and make the following contributions:
Inspired by Chien et al. (2021), we propose to learn a polynomial filter; however, we do by learning sum of polynomials over different subsets of eigenvalues. Such modelling enables learning higher-order polynomials with several low order polynomials acting over the different subsets.
Such modelling, however, requires an eigendecomposition of the graph, which can be ex- pensive. We leverage the model in Chien et al. (2021) and the fact that there exist efficient algorithms for computing top and bottom eigen components to propose a practically effi- cient model.
We present theoretical analysis that suggests that our sum of polynomials approach can approximate a latent optimal filter better than a single polynomial. We also show that the space of learnable filters and graphs using our approach is larger than what possible with Chien et al. (2021).
Our experimental results show that model performs better than state-of-the thee---- art methods on several datasets, giving up to 10% gains. These gains indicate that modelling the filter as sum of polynomials is needed to approximate the latent filter better. We also answer other research questions through ablative studies, including the importance of the top and bottom eigenvalues, the number of top and bottom eigenvalues needed, the number of polynomials needed, and the trade-off's involved.
The rest of the paper is organized as follows: We present related work in Section 2, problem setup and motivation for the approach in Section 3, details of the proposed approach with complexity and theoretical analysis in Section 4 and finally experimental results and empirical analysis in Section 5.
2 RELATED WORKS
In the recent times, Graph Neural Networks (GNNs) have become an increasingly popular method for semi-supervised classification with graphs. Bruna et al. (2014) set the stage for early GNN models, which was then followed by various modifications (Defferrard et al., 2016; Kipf & Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018). Incorporating random walk information (Abu- El-Haija al., 2019b;a; Li et al., 2018) gave further improvements in these models, but they still suffer from over smoothing. Several proposed models attempt to overcome this problem (Klicpera al., 2019; Lukovnikov & Fischer, 2021; Chamberlain et al., 2021; Yang al., 2021).
Another line of research explored the question of which graphs worked well with GNNs. The critical understanding was that the performance of GNN was dependent on the correlation of the graphs with the node labels. Several approaches (Abu-El-Haija et al., 2019a; Zhu et al., 2020; Wang & Derr, 2021) considered edge homophily and proposed a robust GNN model by aggregating information from several higher-order hops. Kim & Oh (2021) also considered edge homophily and mitigated the issue by learning robust attention models. Pei al. (2020) talks about node homophily and proposes to aggregate information from neighbours in the graph and neighbours inferred from the latent space. Zhu et al. (2021) proposes to estimate label-lahel compatibility matrix and uses it as prior to update posterior belief on the labels. However, these approaches still rely the given graphs for information like the hop neighbours etc., which might be poor approximations of the desired neighbours with similar labels.
Some of the recent approaches focused on learning filter functions that operate on the eigenvalues of the graph. Learning these filter functions can be viewed as directly adapting the graph for the desired task. Bo et al. (2021) models the filter function as an attention mechanism on the edges, which learns the difference in the proportion of low-pass and high-pass frequency signals. Chien et al.
2

---

Under review as a conference paper at ICLR 2022
(2021) proposes a polynomial filter the eigenvalues that directly adapts the graph for the desired task. Zheng et al. (2021) decompose the graph into low-pass and high-pass frequencies, and define framelet based convolutional model. Our work is closely related to these lines of exploration. In this work, we propose to learn a filter function as a sum of polynomials over different subsets of the eigenvalues, enabling design of effective filters to model task-specific complex frequency responses with compute tradc-offs.
3 PROBLEM SETUP AND MOTIVATION
We focus the problem of semi-supervised node classification on simple graph G (V, E), where V is the set of vertices and & is the set edges. Let A E {0, 1jax= be the adjacency matrix associated with G, where = = is the number of nodes. Let 3 be the set of all possible class labels. Let X E Rexd be the d-dimensional feature matrix for all the nodes in the graph. Given a training set of nodes D C V whose labels known, along with A and X, our goal is to predict the labels of the remaining nodes. Let A = + I where I is the identity matrix. Let DA, be the 1/2 ADD 1/2 Let À UAU be the eigendecomposition of A. Ar
degree matrix of A and A DA
Then, the spectral convolution of X on the graph A can be defined via the reference operator À and a filter function h operating on the eigenvalues, in the Fourier domain (Tremblay et al., 2017; Chien et al., 2021)aan as,
Z UHAAUU" (ddiag(Va))"
Σ aj A
where (A) diag(h(A)). In this process, the filter function is essentially adapting the graph for the desired task at hand. The second equality follows from using a polynomial filter, (()) = Σ a; where a; 's are coefficients of the polynomial, & is the order of the polynomial and À is any eigenvalue from A. Note that ((A) A = diag(Vax where V E TR* is a Vandermonde matrix constructed using eigenvalues from A and a R is the vector consisting of az 's. The last equality follows from the eigendecomposition properties, enabling avoidance of eigendecompo- sition. It is well-known that polynomial filters can approximate any graph filter (Shuman al., 2013; Tremblay et al., 2017). However, several practical challenges arise in learning good polynomial filter. We briefly discuss them below.
Let h- be the optimal filter for some given task. Learning a polynomial filter involves the approx- imation: h² Ra Vo. Notice that this system is over-determined since the number of unknowns (k: the size of a:) is less than the number of equations (n,, the number of nodes). To obtain consis- tent solution, we may have to work with higher-order polynomials. Working with higher powers poses several practical challenges, and the following observations are in order. First, node features computed via A X becomes indistinguishable (see Figure 1a and A.2.1). Since the node features are indistinguishable, the importance of the coefficient associated with A for the task at hand reduces significantly. These observations are in line with Theorem 4.2 in Chien et al. (2021), where states that as over-smoothing happens, the corresponding coefficients of the polynomial go to zero. We observe that with insignificant contributions from higher-order terms, the performance (aka test accuracy) does not improve with the increase in the order of the polynomial (See Figure 1b, Ic and A.2.2). Next, one can think of addressing this issue with A by directly working with full eigendecomposition. However, this approach is prohibitively expensive for large graphs. Even if we were to do this, As's are in the range of [-1, 1] and thus X will diminish with higher powers. Therefore, it will continue to be less effective in learning coefficients of a higher power. Motivated by the above observations, we propose a novel piece-wise polynomial filter learning approach.
4 PROPOSED APPROACH
The central goal of our approach is to get improved task-specific performance by learning effective task-specific graph filters. We propose leam the polynomial filter as sum of polynomials operat- ing on different eigenvalue intervals, taking task-specific requirements and practical considerations into account. We show that our proposed filter design can approximate the latent optimal graph
3

---

Under review as a conference paper at ICLR 2022
16
103
154.
25
122
86
04
(a)
(b)
(C)
Figure 1: In (a), we plot the average of pairwise distances between node features for the Cora dataset, after computing A X for increasing, values. X-axis represents the various powers and the Y-axis represents the average of pairwise distances between node features. In (b) and (c), plot the test accuracies of the model in Chien et al. (2021) for increasing order of polynomials for Cora and Chameleon dataset respectively. X-axis represents the order of the polynomial and Y-axis represents the test accuracy achieved for that order.
filter better than single polynomial, and the resultant class of learnable filters/graphs is richer. We briefly discuss the training and computational complexity of the proposed model.
4.1 PIECE-WISE POLYNOMIAL/SPLINE GRAPH FILTER FUNCTION
We model the filtering function h(X) piece-wise polynomial spline function where each polynomial is of lower degree (e.g.. a cubic polynomial). We partition the eigen spectrum in [-1, (or [0, 2] as needed) into contiguous intervals and approximate the desired frequency response by fitting a low degree polynomial in each interval. This process helps us to learn a more complex shaped frequency response as needed for the task. Let S {or ......, Fm denote partition set with m contiguous intervals and hs, (): denote kę-degree polynomial filter function of the interval a; with polynomial coefficients %/. We define PP-GNN filter function as:
h(A) Σ o.ES
h4.4, h4, (A;%))
and learn a smooth filter function by imposing additional constraints to maintain continuity between polynomials of contiguous intervals at different endpoints (aka knots). This class of filter functions is rich, and its complexity is controlled by choosing intervals (i.e., endpoints and number of partitions) and polynomial degrees. Given the filter function, compute the node embedding matrix as:
Z Z,
(3)
where U; is matrix with eigenvectors corresponding eigenvalues that lie in d. H,(*) is the diagonal matrix with diagonals containing the h2 evaluated at the eigenvalues and Zo θ) is an MLP network with parameters θ.
4.2 PRACTICAL AND IMPLEMENTATION CONSIDERATIONS
The filter function (3) requires computing eigendecomposition of A and is expensive, therefore, scalable for very large graphs. Thus, having finer control to learn complex frequency responses comes with high computational cost. We address this problem by devising graph filter function that enables a trade-off between computational cost and frequency response control. First, we make the following observations:
1. Top-k and bottom-k eigenvalues represent i low and high frequencies. There are efficient algorithms and off-the-shelf library packages available to get top-k and bottom-k eigenval- ues and eigenvectors of sparse matrices.
4

---

Under review as a conference paper at ICLR 2022
2. GPR-GNN method also lears graph filter but operates the entire eigen spectrum by sharing the filter coefficients across the spectrum. Therefore, it is a special case of our proposed model (3). Since GPR-GNN learns a global polynomial by having shared coefficients across the spectrum (like learning a global polynomial to fit a function), is not flexible enough to learn complex frequency responses, as needed in several practical applications. Note that increasing the degree of the global polynomial does not help beyond some high degree specific tasks. We demonstrate this through extensive experiments on benchmark datasets in the experiment and appendix sections. One important advantage of GPR-GNNN that it does not require computation of eigendecomposition: therefore, efficient.
3. Many recent works, including GPR-GNN, investigated the problem of designing robust graph neural networks that work well across homophilic and heterophilic graphs. They found that graph filters that amplify or attenuate low and high-frequency components of signals (i.e., low-pass and high-pass filters) are critical to improving performance on several benchmark datasets.
Efficient Variant. Using the above observations, we propose an efficient variant of (2) as:
h(A)= = 1 Σ h (2:7,)) + mh Σ
th (A:7;
(h)) + Tggpr t (2;7)
(4)
OLES!
where St consists of partitions over low frequency components, Shh consists of partitions over high frequency components, the first and second terms fit piece-wise polynomials' in low and high frequency regions, indicated through superscripts. However, ful information from other frequencies in the central region, yet maintain efficiency. We achieve this by adding the GPR-GNN filter function, hape ();r), which is computationally efficient. Since hop (>; is special case of (2) and the terms in (4) are additive, it is easy to see that (4) is same as (2) with modified set of polynomial coefficients. In practice, the required low and egg-frrquency components are computed based on affordable computational cost. Furthermore, we can also con- trol the contributions from each term by setting or optimizing over hyperparameters, T7,, ?h and 'lppr- Thus, the proposed model offers richer capability and flexibility to learn complex frequency response and balance computation costs over GPR-GNN.
do not want lose any use-
Model Training. Like GPR-GNN, we apply SOFTMAX activation function on (3) and use the stan- dard cross-entropy loss function to learn the sets of polynomial coefficients (7) and classifier model parameters (θ) using labeled data. To ensure smoothness of the Iearned filter functions, regularization term that penalizes squared differences between the function values of polynomials of contiguous intervals at each other's interval end end-points. More details can be found in the appendix (A.4. 1).
add
Computational Cost. There is some pre-training cost of computing the cigendecomposition for top and bottom k eigenvalues. Most algorithms for this task utilize Lanczos' iteration, convergence bounds of which depends on the input matrix' spectrum (Saad, 1980; LI, 2010), which although have superlinear convergence, but are observed to be efficient in practice. We compute node embeddings afresh whenever the model parameters are updated. This computation involves matrix multiplication with cigenmatrices incurring an additional cost (over GPR-GNN) of (nk where ks and L denote the number of selected low/high eigenvalues and classes, respectively.
4.3 ANALYSIS
We first give simple theoretical justification for using multiple polynomials. We upper-bound the approximation error achieved by using multiple polynomials by the error that the single polynomial parameterization achieves. We relegate the proofs of all the theorems of this section to the appendix.
Theorem 4.1. For any frequency response h², and integer K N, let h h + h with hy having a continuous support over a subset of the spectrum, σy. Assume that h and hy are parameterized by independent K and -'-order polynomials, p and py. respectively, with K' S K. Then there exists h, such that min - h 1=2 S min | h 11 where the minimum is taken over the polynomial parameterizations. Moreover, for multiple polynomial adaptive filters h f2 .... h
For brevity, dropped the polynomial degree dependency.
5

---

Under review as a conference paper at ICLR 2022
parameterized by independent K' -degree polynomials with K' x K but having disjoint, contiguous supports, the same inequality holds for h h Ei=1 hy.
For detailed proof please refer to A.4.3. We constructed waveforms of arbitrary complexity, ap- proximated by first fitting a single globally-defined polynomial and then adding locally defined polynomials on top of it. We assess the performance by varying the degrees of the local polyno- mials. The corresponding plots (See Figure 8) indicate that use of lower-order filters achieves fit comparable to one by a relatively higher-degree polynomial. Since actual waveform is not observed in practice and instead, we estimate by optimizing over the observed labels via learning graph filter, we theoretically show that the family of filters that we learn is strict superset of the polynomial filter family. The same result holds for the families of the resulting adapted graphs.
Theorem 4.2. Define H : (h(.) possible K-degree polynomial parameterizations of h} to be the set of all K-degree polynomial filters, whose arguments are n x n diagonal matrices, such that a filter response over some A is given by ((A) for h(-) E H.. Similarly H' {h(.) possible polynomial parameterizations of h is set of all filters learn-able via PP-GNN, with h = h + h1,, + h where h is parameterized by a K-degree polynomial supported over en- tire spectrum, f and h adaptive filters parameterized by independent K'- Ke-degree polynomials which only act on top and bottom & diagonal elements respectively, with t < n/2 and K' < K; then dim(H') K+2K'+3
H and H' form a vector space, with H H'. Also, dim(EI]
K+1
Corollary 4.2.1. The corresponding adapted graph families
{U (U) Vh(+) H. and G/ (U" vh(+) E H'' for any unitary matrix form vector space, with G c G' and
dam
K K+2K'43
dim(
K+1
This implies that our model is learning from a more diverse space of filters and the corresponding adapted graphs. Moreover, the dimension of the space increases significantly by using just two adaptive filters. Note that learning from such diverse region feasible. This observation is possible from the proofs of Theorem 4.2 (A.4.4) and Corollary 4.2.1 (A.4.5). Using the adaptive filters without any filter with the entire spectrum as support results in learning set of adapted graphs, G. This set disjoint from G, with G' = G @ G. We conduct various ablative studies where we demonstrate the effectiveness learning from G and G'.
5 EXPERIMENTS
We conduct comprehensive experiments to demonstrate the effectiveness and competitiveness the proposed PP-GNN model over state-of-the-ar (SOTA) models/methods and answer the following research questions.
1. [RQ1] Does the PP-GNN model outperform SOTA models/methods over a broad range of datasets (homophilcchhterrppllio)
2. [RQ2] Does the proposed model learn better and complex frequency responses that im- prove performance [Frequency response plots]?
3. [RQ3] With the PP-GNN model comprising of multiple filters, how does each filter con- tribute to achieving improved performance?
4. [RQ4 and RQ5] Does the model learn better embedding, and do we need large number of eigenvalues/vectors and polynomials to get improved performance?
5. [RQ6] How does the training time of the PP-GNN and GPR-GNN models compare?
Datasets and Setup. We evaluate our model on several real-world heterophilic and homophilic datasets including a few large graphs for the node classification task. Detailed statistics of the benchmark datasets are provided in the appendix (A.5.1). The heterophilic datasets include Texas?. Cornell,, Wisconsin", Chameleon, Squirrel, (Rozemberezki et al., 2021) and Flickr. We use the 10 random splits (48% nodes for train/validation/tes set) from Pei et al. (2020). For Flickr, Ogbn-Arxiv, and Wiki-CS, use the data splits from Kim & Oh (2021). We also
1/www/wwkh

---

Under review as a conference paper at ICLR 2022
evaluate 8 homophilic datasets: Cora-Full, Ogbn-Arxiv, Wiki-CS, Citeseer, Pubmed, Cora, Computer, and Photos borrowed from Kim & Oh (2021). For the remaining homophilic datasets, create 10 random splits for each dataset following Kim & Oh (2021). We use PCA node features (Kim & Oh (2021)) for the Chameleon and Cora-Full datasets. We report mean and standard deviation of test accuracy over splits compare model performance.
Baselines. We compare our model against (a) filtering based approaches, GPR-GNN, FAGCN, APPNP, and LGC, (b) other state-of-the-art models include SUPERGAT, TDGNN, H₂GCN, and GEOM-GCN, and (c) standard baselines, namely, LR (Logistic Regression), MLP (Multi Layer Perceptron). GCN, and SGCN. Detailed descriptions for all the baselines, hardware and software specifications are in the appendix (A.5.2 and A.5.5)
Hyperparameter Tuning. For the PP-GNN model, we separately partition the low-end and high- end eigenvalues into several contiguous partitions and use shared filter parameters for frequencies of each partition. The number of partitions, which can be interpreted as the number of filters, is swept in the range [2.3,4.5, 10.20J. The polynomial filter order is swept in the range [1,10] in steps of size 1. The number of eigenvalues/vectors are swept the range [32, 64, 128, 256, 512, 1024]. M/-
In our experiments, we set Y = `/ and we vary them in range (0, 1) and set 'lgpr
We did hyperparameter tuning for other models as suggested in respective references and public repositories. More details are in the appendix (A.5.5).
Test Acc
Texas
Wisconsin
Squirrel
Chameleon
Cornell
Flickr
LR
81.35 (6.33)
84.12 (4.25)
34.73 (1.39)
45.68 (2.52)
83.24 (5.64)
46.51
MLP
81.24 (6.35)
84.43 (5.36)
35.38 (1.38)
51.64 (1.89)
83.78 (5.80)
46.93
SGCN
62.43 (4,43)
55.69 (3.53)
45.72 (1.55)
60.77 (2.11)
62.43 (4.90)
50.75
GCN
61.62 (6.14)
58.82 (4.89)
47.78 (2.13)
62.83 (1,52)
62.97 (5.41)
53.4
SuperGAT
61.08 (4.97)
56.47 (3.90)
31.84 (1.26)
43.22 (1.71)
57.30 (8.53)
53.47
Geom-GCN
67.57%
64.12*
38.14*
60.90*
60.81
NA
H2GCN
84.86 (6.77)*
86.67 (4.69)*
37.90 (2.02)*
58.40 (2.77)
82.16 (4.80)*
OOM
FAGCN
82.43 (6.89)
82.94 (7.95)
42.59 (0.79)
55.22 (3.19)
79.19 (9.79)
OOM
APPNP
81.89 (5.85)
85.49 (4.45)
39.15 (1.88
47.79 (2.35)
81.89 (6.25)
50.33
LGC
80.20 (4.28)
81.89 (5.98)
44.26 (1.49)
61.14 (2.07)
74.59 (3.42)
51.67
GPR-GNN
81.35 (5.32)
82.55 (6.23)
46.31 (2.46)
62.59 (2.04)
78.11 (6.55)
52.74
TDGNN
83.00 (4.50)*
85.57 (3.78)*
43.84 (2.16)
55.20 (2.30)
82.92 (6.61)*
0OM
PP-GNN
89.73 (4.90)
88.24 (3.33)
56.86 (1.20)
67.74 (2.31)
82.43 (4.27)
55.17
Table 1: Results Heterophilic Datasets. We underline the results for the best performing baseline model. ** indicates that the results were borrowed from the corresponding papers.
Test Ace
Cora-Full
OGBN-ArXiv
Wiki-CS
Citeseer
Pubmed
Cora
Computer
Photos
LR
39.10 (0.43)
52.53
72.28 (0.59)
72.22 (1.54)
87.00 (0.40)
73.94 (2.47)
64.92 (2.59)
77.57 (2.29)
MLP
43.03 (0.82)
54.96
73.74 (0.71)
73.83 (1.73)
87.77 (0.27)
77.06 (2.16)
64.96 (3.57)
76.96 (2.46)
SGCN
61.31 (0.78)
68.51
78.30 (0:75
76.77 (1.52)
88,48 (0.45)
86.96 (0.78)
80.65 (2.78)
89.99 (0.69)
GCN
59.63 (0.86)
69.37
77.64 (0.49)
76.47 (1.33)
88.41 (0.46)
87.36 (0.91)
82.50 (1.23)
90.67 (0.68)
SuperGAT
57.75 (0.97)
55.1*
(0.82)
(1.59)
87.19 (0.50)
86.75 (1.24)
83.04 (1.02)
90.31 (1.22)
Geom-GCN
NA
77.99*
90.05*
85.27*
H2GCN
57.83 (1.47)
OOM
0OM
77.07 (1. (1.64y*
89.59 (0.33)*
87.81 (1.35)*
0OM
91.17 (0.89)
FAGUN
60.07 (1.43)
0OM
79.23 (0.66)
76.80 (1.63)
89.04 (0.50)
88.21 (1.37)
82,16 (1.48)
90.91 (1.11)
APPNP
60.83 (0.55)
69.2
79.13 (0.50)
76.86 (1.51)
89.57 (0.53)
88, (3))
82.03 (2.04)
91. 68 (0.62)
LGC
61.84 (0.90)
69.64
79.82 (0.49)
76.96 (1.73)
88.78 (0.51)
88.02
(1.77)
91.56 (0.74)
GPR-GNN
61.37 (0.96)
68.44
79.68 (0.50)
76.84 (1.69)
89.08 (0.39)
87.77 (1.31)
82.38 (1.60)
91.43 (0.89)
0OM
(0.51)
76.64 (1.54y*
89.22 (0.41)*
88.26 (1.32y>
(0.92)
92.54 (0.28)
PP-GNN
61.42 (0.79)
69.28
80.04
78.25 (1.76)
89.71 (0.32)
89.52 (0.85)
(1.36)
92.89 (0.37)
Table 2: Results on Homophilic Datasets.
7

---

Under review as a conference paper at ICLR 2022
5.1 RQI: PP-GNN VERSUS SOTA MODELS
We present several important observations from Tables I and 2. We observe that the PP-GNN model consistently outperforms all models, including recent filtering approach based models on all datasets (both heterophilic and homophilie) except Pubmed and Cornell, where it achieves simi- lar performance. This result demonstrates the effectiveness and robustness of our model across a wide variety of datasets. Furthermore, compared with the GPR-GNN model, learning piece-wise polynomial filters improves performance significantly over learning a single polynomial filter. In particular, PP-GNN achieves performance improvements of around 10% and 5% on the Chameleon and Squirrel datasets.
5.2 RQ2: ADAPTABLE FREQUENCY RESPONSES
We computed the frequency responses (i.e., h())) of learned polynomials of the PP-GNN and GPR- GNN models on several datasets, including Squirrel and Citeseer datasets shown in Figure 2. We observe from Figure 2a, though the GPR-GNN model can learn some variations at low/high fre- quencies, it is insufficient to achieve higher classification aceuracy. On the other hand, the PP- GNN model can capture complex shapes at the low and high ends of the spectrum, enabling it to achieve significantly improved test accuracy. We observed a similar phenomenon for the chameleon dataset well. To illustrate another behaviour, we present the frequency responses for the Citeseer dataset Figure 2b, and the responses are similar except for some variations at the low-end of the spectrum. Note that the GPR-GNT model does well on several homophilic datasets. These obser- vations suggest that the PP-GNN model adapts very well in learning desired frequency responses, as dictated by the task at hand. We can observe such behaviour for two other datasets in the appendix (A.5.6).
(P CINK (FIP) STANO
CRUN (OPR
P2-GNN
PT-GWN
steeggt
elgen
elgen
(a) Squirrel
(b) Citeseer
Figure 2: Visualization of adapted eigenspectrum by our proposed model and GPR-GNN
5.3 RQ3: PERFORMANCE COMPARISON OF DIFFERENT FILTERS
Recall that the PP-GNN model is sum of polynomials model comprising of polynomial filters operating at different parts of the spectrum. Here, we study the importance and effect of using a combination of filters operating on different regions. For reference, we also compare the perfor- mance of GPR-GN GNN model that operates on the entire spectrum using single filter. Several inter- esting observations are in order. From Table 3, we see that the best performance is achievable using high-frequency signals alone for the heterophilic datasets (Squirrel and Chameleon), suggesting that significant discriminatory information is available at high frequencies compared to low-frequency signals. In contrast, homophilic datasets (Cora and Citeseer) exhibit reverse trend. On comparing the first (second) and third (fourth) row results, we see that having the GPR-GNT filter as part of the PP-GNN filter helps to get improved performance over individual filters (PP-GNN(LOW) or PP-GNN (High)). Finally, the PP-GNN model can adapt well, capture contrasting information bands across datasets, and outperform the GPR-GNN model.
8

---

Under review as a conference paper at ICLR 2022
880
Test Accuracy
20
80
50
120
512
EVD Components Adigted
(hanleen
Chanaer
(a) Varying No. of EVs
(b) PP-GNN on Squirrel
(c) GPR-GNN Squirrel
Figure 3: Analyzing varying number of eigenvalues and the learned embeddings
Test Acc
Squirrel
Chameleon
Citeseer
Cora
PP-GNN (Low)
45.75 (1.69)
56.73 (4.03)
76.23 (1.54)
88.03 (0.79)
PP-GNN (High)
58.70 (1.60)
69.19 (1.88)
55.50 (6.38)
73.76 (2.03)
PP-GNN (GPR-GNN+Low)
50.96 (1.26)
63.71 (2.69)
78.07 (1.71)
89.56 (0.93)
PP-GNN (GPR-GNN + High)
60.39 (0.91)
67.83 (2.30)
78.30 (1.60)
89.42 (0.97)
GPR-GNN
42.06 (1.55)
56.29 (1.58)
76.74 (1.33)
87.93 (1.52)
PP-GNN
56.21 (1.79) 68.93 (1.95) 78.25 (1.76)
89.52 (0.85)
Table 3: Performance of different filters
5.4 RQ4- RQ6: VARYING No. OF EVS, LEARNED EMBEDDING AND TIMING COMPARISON
We conducted ablative studies to the effect of varying different hyperparameters of the PP-GNN model. From Figure 3a, we see that as small as 32 eigen components are sufficient to achieve near- best performance on the homophilic datasets (Cora, Citeseer). On the other hand, peak performance achieved for some intermediate (z:200-500) number of eigen components for the Squirrel and Chameleon datasets. Also, we note that models on large datasets (Flickr and OGBN-Arxiv) using only 1024 components (See Tables I and 2). This study suggests that the PP-GNN model is scalable least for medium sized graphs ( 1100K nodes). More evaluation and investigation are needed to study performance versus computation cost trade-off for very large graphs (millions of nodes).
achieve comparable performance to state of the art
To assess the quality of learned embedding, we also created t-SNE plots and made a visual inspec- tion. From Figure 3b and 3c, we see that the clusters belonging different classes of the Squirrel dataset are better separated for the PP-GNN model compared to the GPR-GNN model. We also measured the time taken by the GPR-GNN and PP-GNN models. We observed that the GPR- GNN model is only (1.2 2)x faster than the PP-GNN model (using 1024 eigencomponents) on many datasets. Thus, the extra training cost incurred by the PP-GNN model is not significantly different for practical purposes. More details are in the appendix (A.6).
CONCLUSION
Several proposed models attempt to be robust to the correlations between graph and node labels. We build on the flter-based approach of GPR-GNN (Chien et al., 2021). This work proposed an effective polynomial filter design. We combine GPR-GNN with additional polynomials that adapt specifically to low and high-frequency components. Our experiments demonstrate that such an approach can learn filter functions that improve performance the node classification task. Our plots of these filter functions suggest that they are of high order on several datasets. It would be common characteristies. These will enable
interesting to amalyze these filter plots and identify us to a] characterize the correlation of graphs and labels, b] further improve the performance and c] build robust graph privacy models. We plan do this future work.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
We have taken several steps to ensure the reproducibility of our work. First, we provide a detailed description of our model Section 4. Section provides a brief description of the datasets utilized in our experiments. A detailed description of the datasets, including their sources, statistics are given the appendix (A.5.1). We also provide details on the number of splits and the method used to generate them. We also list out all the baselines utilized in the experiments in Section 5. A detailed description of these baselines and the parameter sweep ranges are given in the appendix (A.5.2). We also provide implementation detail of our model in the appendix (A.5.5). Additionally, we share an anonymized URL the code for our model, and the data splits in the appendix (A.I).
8 ETHICS STATEMENT
Social network graphs form the most exciting application for GNNs. GNNs can be used to reveal user information that the user otherwise would have preferred to keep private. Privacy-preserving methods might rely obfuscating the graph by adding spurious edges, and these edges will, in turn, reduce the graph's 's correlation with the node labels. Earlier GNNs would likely not have predicted the target label with reasonable accuracy under this setting. Thereby, such obfuscation methods would give some level of privacy for the users. However, our model exhibits good performance even in the presence of lower correlation. Such methods make simple obfuscation based privacy approaches obsolete while still revealing important information about the users. On the other hand, our model can also give insights into what makes graphs reveal certain information and develop more robust privacy model for graphs
REFERENCES
Sami Abu-El-Haij Hl-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan. Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tion architectures via sparsified neighborhood mixing. In International Conference Machine Learning (ICML), 2019a.
Sami Abu-FllHaija, Bryan Perozzi, Amol Kapoor, and Joonseok Lee. N-gen: Multi-scale graph convolutionfor semi-supervised node classification. In Conference on Uncertainty in Artificial Intelligence (UAI). 2019b.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. ArXiv, abs/1997..10900 2019.
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, pp. 1-1, 2021. ISSN 1939-3539. doi: 10.1 1099///m..2221..000.. 33054830. URL http: : dx doi.
org/10. /10. 11011199/10 1ww1111091AAAA ATAM 2021 3054830.
Deyu Bo, X. Wang, Chuan Shi, and Hua-Wei Shen. Beyond low-frequency information in graph convolutional networks. In Association for the Advancement of Artificial Intelligence (AAAI), 2021.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In International Conference on Learning Representations (ICLR), 2014.
Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pp. 1407-1418. PMLR, 18-24 Jul 2021. URL https: //proceed i ngs ml .press / / v1 39/ wwwwberlaaaaacccccmm ai html.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations (ICIR), 2021.
10

---

Under review as a conference paper at ICLR 2022
Tat-Seng Chua, Jinhui Tang. Richang Hong. Haojie Li, Zhiping Luo, and Yan-Tao Zheng. Nus- wide: A real-world web image database from national university of singapore. In Proc. ACM Conf. on Image and Video Retrieval (CIVR 09), Santorini, Greece., July 8-10, 2009.
Jane K. Cullum and Ralph A. Willoughby. Lanczos Algorithms for Large Symmetric Eigen- value Computations. Society for Industrial and Applied Mathematics, 2002. doi: 10. 97379199780987199999 URL ntttps:/eett //ebbbs/pbbb.///// simm. aam.orr///eeeeeooo /abs/ 10 1137/1. 9780898719192.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Neural Information Processing Systems (NeurIPS), 2016.
Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Graph neural networks with adaptive frequency response filter, 2021.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Neural Information Processing Systems (NeurlPS), 2017.
Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation, 2021.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint wwXiv:2005.0066%" 2020.
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with superviieev In International Conference on Learning Representations (ICLR), 2021.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations (ICLR), 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Association for the Advancement of Artificial Intelligence (AAAI), 2018.
CEN-CANG L.I. Sharpness rates of convergence for the symmetric lanezos method. Mathematics of Computation, 79(26)):41 2010. ISSN 00255718, 10886842. URL. http: /www. setor.org/sttbbe//005523
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs. The WebConf Workshop on Graph Learning Benchmarks (GL.B-WWW) 2021.
Denis Lukovnikov and Asja Fischer. Improving breadth- wise backpropagation in graph neural net- works helps learning long-range dependencies. In Marina Meila and Tong Zhang (eds.), Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pp. 7180-7191. PMLR, 18-24 Jul 2021. URL https: / h/proceedings.oo
www.nnssmmmm.. mlr, wttppnn..w...........eaee.eeseee wwwpppessvvii. Setees//v19/lukoo/eee www.wukkwwwwi.....o..o. html.
Nicolò Navarin, Wolfgang Erb, Luca Pasa, and Alessandro Sperduti. Linear graph convo- lutional networks. In 28th European Symposium on Artificial Neural Newworks, Compu- tational Intelligence and Machine Learning, ESANN 2020, Bruges, Belgium, October 2-4, 2020, pp. 151-156, 2020. URL https:/ /ttps://wwww /www. www.esaane esann. org/ wtteg//sieea//eeeeeeeeeeeee /attt//////eaa//iieeeesseessseee proceedi ngs 2020//E222002020 96. f.dff

---

Under review as a conference paper at ICLR 2022
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. URL http: /paperspppppseeeeeeea nwwrips. cttpsscc/ppare cc/paper/ 9015-pytorch-al pdf.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations (ICLR), 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
Y. Saad. On the rates of convergence of the lanezos and the block-lanczos methods. SIAM Journal on Numerical Analysis, 17(5):687-706, 1980. doi: 10.1137/071 URL https://dol.
3xg/10.1137/07111
David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013. doi: 10. 10.10999...222.222255559
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2009.
Nicolas Tremblay, Paulo Gonçalves, and Pierre Borgnat. Design of graph filters and filterbanks, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations (ICLR), 2018.
Yu Wang and Tyler Derr. Tree decomposed graph neural network. In Conference on Information and Knowledge Management, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In International Conference on Machine Learning (ICML), 2019.
Yongyi Yang, Tang Liu, Yangkun Wang. Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative al- gorithms. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11773-11783, PMLR, 18-24 Jul 2021. URL https: htttp://prroee /ttppppeeeeegs...////////// mlr p v139 h/39/yang22g... html.
Xuebin Zheng, Bingxin Zhou, Junbin Gao, Yuguang Wang, Pietro Lió, Ming Li, and Guido Mont- ufar. How framelets enhance graph neural networks. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pp. 12761-12771 PMLR, 18 14 Jul 2021. URL https:/ https:/ http://pooeeeeiig...eo/ mll. wwa.inngs.mr..preese..m vv1/9/ http9//hhgn2cchhhccc html.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. In Neural Information Processing Systems (NeurIPS), 2020.
Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph Neural Networks with Heterophily. In Association for the Advancement of Artifi- cial Intelligence (AAAI), 2021.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
The appendix is structured as follows. In Section A.I, we provide a URL with our code and data, along with some information about the contents in the URL. In Section A.2, present additional evidence of the limitations of GPR-GNN. that motivates Section 4. In Section A.4, provide proofs for theorems and corollaries defined in Section 4.3. In Section A.5, we provide more details regarding the baselines, datasets and their respective splits. We also provide implementation details and rank PP-GNN against current SoTA. In Section A.6, we perform a timing analysis where we compare PP-GNN to GPR-GNN.
Section A.3, we show a representative experiment
A.1 CODE AND DATASET
Our code, along with the datasets and their respective splits, is available ht /tttps://tinurll com/PPGNN. A README file is available explaining how the code can be executed on various datasets. The requirements txt file lists all the necessary python packages required to execute the code. The sre folder also contains bash scripts to run the code on various datasets.
A.2 MOTIVATION
A.2.1 NODE FEATURE INDISTINGUISHAABLY PLOTS
In the main paper (Figure la), we plot the average of pairwise distances between node features for the Cora dataset, after computing A X for increasing values, and showed that the mean pairwise node feature distance decreases as j increases. We observe that this is consistent across three more datasets: Citeseer, Chameleon and Squirre.. This is observed in Figure 4.
07
05
24
Mean Pursits
a2
1.
0.1
21
10
20
16
3
of
Nambe Saa (1)
Nambe
Sa 11)
(a) Chamelcon
(b) Squirrel
(c) Citeseer
Figure 4: Average pairwise distances between node features, after computing A X, for increasing
j values
We also observed the mean of the variance of each dimension of node features, after computing A for increasing j values. We observe that this mean does indeed reduce as the number of hops increase. We also observe that the variance of each dimension of node features reduces for Cora, Squirrel and Chameleon as the number of hops increase; however, we don't observe such an explicit phenomenon for Citeseer. See Figure 5.
A.2.2 EFFECT OF VARYING THE ORDER OF THE GPR-GNN POLYNOMIAL.
In the main paper (Figure la), we plot the test accuracies of the GPR-GNN model while increasing the order of the polynomials for the Cora and Chameleon dataset, respectively. We observe that on increasing the polynomial order, the accuracies do not increase any further. We can show similar phenomenon on two other datasets, Squirrel and Citeseer, Figure 6.
In Section 3 of the main paper, claim that due to the over-smoothing effect, even increasing the order of the polynomial, there is no improvement in the test accuracy. Moreover, in Figure that model can learn complicated filter polynomial while GPR-GNN cannot. This section shows that even on increasing the order of the GPR-GN GNNpolynomial, neither does the test accuracy increase nor does the waveform become complicated PP-GNN, See Figure 7.
13

---

Under review as a conference paper at ICLR 2022
0.007
0.006
0.006
Veciana
0.005
0.004
0.004
0.003
0.002
0.000:
10
15
25
30
40
10
15
25
30
hops ())
hops
(a) Cora
(h) Citeseer
0.0035
0.0020
0.0000
Pesture Vartanss
0.0015
Varkuce
0.0025
0.0020
0.0015
0.0010
0.0003
0,0000
0.0000
0 0.0000
10
15
20
25
30
20
25
35
Number of hoge (J)
Numier of heps (J)
Squirrel
(d) Chameleon
Figure 5: Variance of each dimension of node features
16
323
358-
83
215
(a) Citeseer
(b) Squirrel
Figure 6: Accuracy of the GPR-GNN model on inceasing the order the polynomial
A.3 FICTITIOUS POLYNOMIAL
In Section claim that having multiple disjoint low order polynomials approximate plicated waveform better than a higher-order polynomial. We create representative experiment that shows this is indeed true by creating fictitious complicated polynomial and trying fit it using both a single polynomial and the disjoint multi polynomial. We observe in Figure that the lower order disjoint polynomial fits the complicated waveform better than higher-order single polynomial.
A.4 PROPOSED APPROACH
A.4.1 DETAILS REGARDING BOUNDARY REGULARIZATION
To induce smoothness in the learned filters, add regularization term that penalizes squared differences between function values of polynomials at knots (endpoints of contiguous bins). Our regularization term looks as follows:
14

---

Under review as a conference paper at ICLR 2022
Order buly
Order Pay
Grdaa- Iuty
Onder-t tuyy
Ordec Paly
Order PVV
Ce
Grder-18 Poly
-0.75
-0.00
-0225
8.25
0.50
0.25
1.00
5.44
11.5
0.0
1.2
Eigarvaltoss
Experaatio
(a) Chameleon
(b) Citeseer
Ordee4
Orean-6 Iuty
Orderd Pulr
Orden-16 16 Pods
Order-13 15 Nyy
Orcie 52 Paly
Grdersi2 Ivlly
2.0
Eigorsltoos
Eigasslions
(c) Cora
(d) Squirrel
Figure 7: Varying Polynomial Order in CNR-GNN
alo
(a) Fitting single 10-degree polynomial
(b) Fitting with 5-order adaptive filters
Figure 8: To demonstrate the adaptability of adaptive polynomial filter, we try to approximate complex waveform (blue dashed line) via (a) single 10 degree polynomial, and (b) 10-degree polynomial with 10 adaptive filters order 5. The waveform learnt via the filter is shown in solid dashed line. The corresponding RMSE are: (a) 3.9011, 1, (b) 0.2800
exp (o mur mmin
(hi(omar)) (ominn
(5)
In equation 5, Th and min refer to the maximum and minimum eigenvalues in a; (Refer to Section 4). This regularization term is added to the Cross-Entropy loss. We perform experiments with this model and report the performance in Table 4. We observe that we are able to reach similar performance even without the presence of this regularization term. Therefore, majority of the results reported in our Main paper are without this regularization term.
A.4.2 NOTATION USED
Vectors are denoted by lower case bold Roman letters such as x, and all vectors are assumed to be column vectors. In the paper, h with any sub/super-script refers to frequency response, which is
15

---

Under review as a conference paper at ICLR 2022
Test Acc
Computer
Chameleon
Citeseer
Cora
Squirrel
PPGNN (With Reg)
83.53 (1.67)
67.92 (2.05)
76.85 (2)
88.19 (1.19)
55,42 (2.1)
PPGNN
85.23 (1.36)
67.74 (2.31)
76.74 (1.33)
89.52 (0.85)
56.86 (1.20)
Table 4: Results with and without boundary regularization
also considered be a vector. A superscript I denotes the transpose of matrix vector, Matrices are denoted by bold Roman upper case letters, such as M. A field is represented by K; sets of real and complex numbers are denoted by IR and C respectively. K[ In.] denotes multivariate polynomial ring over the field K, in indeterminates T1..... ....... Set of x square matrices with entries from some S are denoted by (S). Moore-Penrost pseudoinverse of a matrix A is denoted by AT. Figenvalues of matrix are denoted by A, with Å1, A2.... denoting a decreasing order when the eigenvalues are real. A matrix A denotes diagonal matrix of eigenvalues. Set of all eigenvalues, i.e., spectrum, of matrix is denoted by од simply when the context is clear. Lp norms are denoted by || l1. Frobenius norm over matrices is denoted by I|F.. Norms without subscript default to L2 norms for vector arguments and Frobenius norm for matrices. @ denotes a direct sum. For maps fü defined from the vector spaces V1, ....... Vm. with a map of the form f: V W, with V Vi @ . . Vn, the the phrase "f V + W by mapping f(v;) to fi(((v)))" means that f maps a vector v = V1 +
Vm with v; E V; to (g(((v)) + +...+ + fm (g(( (V()))
A.4.3 PROOF OF THEOREM 4.1
Theorem. For any desired frequency response h", and an integer K N. let h := h + h with h having a continuous support over a subset of the spectrum, oy. Assuming and h, to be pa- rameterized by independent K and K'-order polynomials p and py respectively, with K' S K, then there exists h, such that min I| - 1* S min || 12112, where the minimum is taken over the polynomial parameterizations.. Moreover, for multiple polynomial adaptive filters h hf: h parameterized by independent K' -degre polynomials with K' < but having disjoint, contiguous supports, the same inequality holds for h > h4.
Proof. We make the following simplifying assumptions:
1. |oy, > K, Vi E [m], i.e., that is all support sizes are lower bounded by K (and hence K')
2. All eigenvalues of the reference matrix are distinct
For methods that use single polynomial filter, the polynomial graph filter, lx(A) diag (Vn) where y is a vector of coefficients (i.e, y parameterizes ho, with eigenvalues sorted descending order in components, and V is Vandermonde matrix:
1
x
X
X2
X
A
V
An
X
And to approximate frequency response h², we have the following objective:
min |1/2 1/2 == min |diag(h") diagl Vz) min ||4 Vrll2 min (
Where || and ||I| system of equations h² Vvy is well-defined and has unique minimizer, x* vth"" and thus
the Frobenius and L2 norms respectively. Due to the assumptions, the
16

---

Under review as a conference paper at ICLR 2022
[|pp(>")]| min, 1lep (1)(l))l Next we break this enror vector
cp(7²) h Vy*
(Mg Vir*) + (h2 -V
cp. + cp..
Where e; == (h-- -vn") with similar definition for epr hg is vector whose value at components corresponding to the set o (ft,,) is same as that of h- and rest are zero. Similarly, V; is matrix whose rows corresponding to the set ohh,) are same as that of V with other rows being zero Also, Vr = V Σ i= V; and 1y h' 2 m
Li-o h Note that as result of this construction, [ep;] U ep; is a linearly independent set since the supports [o (or,,) )] form disjoint set (note theorem statement). We split the proof in two cases:
Case 1: K" K. We now analyze the case where we have m polynomial adaptive filters added, all having an order of K, where the objective is min | ht||,, which can be written as:
m
min diag(h") diog 7.lr
Vy
Vina
min 7./rl
h''
Vy
Vm
min |1,g(1, (x))
Before characterizing the above system, we break a general error vector as:
m
eg(7, == h²
(hg
Vilr + n)) (hl VLn)
Σ cg. Og.
Where eg. (h: Vi(y +x)) with similar definition for egr. Clearly, the systems of equations, Cy. = -0, Vi and Cg.. = 0 are well-defined due to the assumptions and 2. Since all the systems of equations have independent argument, unlike in the polynomial filter case where the optimization is constrained over a single variable; one can now resort to individual minimization of squared norms of eg, which results in minimum squared norm of eg. Thus,
Vi 7
7 Vin vhhi v. Vie [m]
to minimize squared norms of egy and egg- Note that [e Ueg is linearly independent set since the supports (orh,,) ) form disjoint set and by the above construction, this is also an orthogonal
set, and hence have |le, 2 -m | 2 + lle 12 and hence the above assignment implies:
(xDI = min | (7px [x))]| min ll h 11
7./rr
Hence, it follows that, min, |1 V 12 || 11 < |00 1| ||M| Vrr"l II2 and min 1|
VL 12 ||og ||
|ep,1
||h
V 1|2 Hence,
Σ m
m
1e, ||
|e ||? + | 1|
0z.
min
h h S min - -
Case 2: K' < K. We demonstrate the inequality showing the existence of an h that achieves a better approximation error. By definition, the minimum error too will be bounded above by this
17

---

Under review as a conference paper at ICLR 2022
error. For this, we fix y, the parameterization of as 7 Vih² =% (say). Note that Op*
arg min, ||ep(>)||- Now our objective function becomes
m1
og( (ril) == h- 7
Σ (h: - Ving + V(x) + (h7, V
Σ c/ + + 10
Where hi: Vi, V. have same definitions that in case 1 and V is matrix containing first K' + columns of V; as its columns (and hence has full column rank), and, 76 E RK'+1 +1, By this construction, we have
= min [[pp(()) = [1<p();])1
Our optimization objective becomes min (7p: hxDII, which is easy since the problem is well- posed by assumption 1 and 2. The unique minimizer of this is obtained by setting
% V (h. V.n;) 2 (say) Vi [m²]
Now,
( baIII = min () 1 bxliI S ( 0)ll min [|ep(>)]] = min ||h
h"ll
[x]
By the definition of minima, min |le, [xxiil s min [7e, [xD]], and by the definition, min | hell ((x) [1e [xlll], we have:
min l l' S min 114-4"11 A'll
A.4.4 PROOF OF THEOREM 4.2
Theorem. Define HI == (n(.) | A possible K-degree polynomial parameterizations of h} to be the set of all K-degree polynomial filters, whose arguments are n diagonal matrices, such that a filter response over some A is given by h(A) for h(-) E H. Similarly H' == (Ā(.) A possible polynomial parameterizations of h is set of all filters learn-able via PP-GNN, with h h + h1, h/2, where h is parameterized by K-degree polynomial supported over tire spectrum, h,, and hy, are adaptive filters parameterized by independent K' -degre polynomials which only act top and bottom diagonal elements respectively, with t n/2 and K' < K; then dim(H') K+2K'+3 HI and H' form a vector space, with HH C H. Also, dim(H]
K+1
Proof. We start by constructing the abstract spaces on top of the polynomial vector space. Consider the set of all the univariate polynomials having degree at most K in the vector space over the ring K, := K[ In] where IK is the field of real numbers. Partition this set into subsets, say Vi...., Vn, such that for E [n]] V; contains all polynomials of degree up to K in Z;
easy to see that Vi,..., Vn are subspaces of K[ .I,, Define V V $ V/2 θ .... + V, where @ denotes a direct sum. Define the matrix Djíc] whose (1. 1)th entry is c and all the other entries are zero. For i E [n]. define linear maps Φb V, + M, (Kg) by f(x;) + D [ Im(()) forms vector space of all diagonal matrices, whose (i, entry is the an element of V. Generate a linear map Φ V - Mi, (KÇ) by mapping (xx)) to (f.)) for all i [n] as the components of the direct sum present in its argument. Note that @; for i E [n] are injective maps, making 6 an injective map. This implies that C. Im()) is subspace with basis B, == {ő(2) + +... =²)), d(I; + making dim(HH) = K+1. Similarly we have, H' C Im((),, subspace +2
.n),..., ( +... xK
with basis B2 = B, U {6(x)
0(1 +..
((( +
+ + 0)) (0(0 +... + 2 +... =.)), p(0 + + 0 2n +... Ia), ....... (0 +.....++0
K'
and additive identities of K +1 + .... .... x }} where x. and are the corresponding multiplicative
implying H c H' and dim("H K + 2K"
18

---

Under review as a conference paper at ICLR 2022
A.4.5 PROOF OF COROLLARY 4.2.1
Corollary. The corresponding adapted graph families G := (U")()"" Vh(+) E HD and O' =
{UTh(-)UT | Vh(.) E H for any unitary matrix U form a vector space, with G c G' and dim (G)
K+2K'+3
K+1
Proof. Consider the injective linear maps f1. (,, + (,,) as (i(A) = U A and
(A) = AU. Define fa H - M., (KK) and fa : H + M,, (K{)) as fa(A) = (fi o f2) for
A E H and (A) = (f1 o (A) for A E H'. Since U is given to be unitary matrix, f3 and fa
are monomorphisms. Using this with the result from Theorem 4.2, H C HI', we have C C C'. 0
A.5 EXPERIMENTS
A.5.1 DATASETS
We evaluate on multiple benchmark datasets to show the effectiveness of our approach. Detailed statistics of the datasets used are provided in Table 5. We borrowed Texas, Cornell, Wisconsin from WebKB where nodes represent web pages and edges denote hyperlinks between them. Actor is co-occurrence network borrowed from Tang al. (2009), where nodes correspond to tor, and and edge represents the co-occurrence on the same Wikipedia page. Chameleon, Squirrel borrowed from Rozemberczki et al. (2021). Nodes correspond to web pages and edges cap- ture mutual links between pages. For all benchmark datasets, we use feature vectors, class labels from Kim & Oh (2021). For datasets in (Texas, Wisconsin, Cornell, Chameleon, Squirrel, Actor), we use 10 random splits (48%/32%//20) of nodes for train/ vaann/alidation/test set) from Pei et al. (2020). We borrowed Cora, Citeseer. and Pubmed datasets and the corresponding train/val/test set splits from Pei et al. (2020). The remaining datasets were borrowed from Kim & Oh (2021). We follow the same dataset setup mentioned in Kim & Oh (2021) to create 10 random splits for each of these datasets. We also experiment with two slightly larger datasets Flickr Chua et al. (July 8-10, 2009) and OGBN-arXiv Hu et al. (2020). We use the publicly available splits for these datasets.
Properties
Tinaas
Wicrenois
Actur
Squirre
Charelean
Comell
Flickr
Cara-fall
OGBN-arXiv
WIL--C
Cliower
Prihrre
Cara
Computer
Plutox
Hanophily Leve
0.11
0.31
0.23
0.22
0.23
0.30
0.32
0.59
0.63
0:58
0..4
0.90
0.51
0.91
0.85
iNedo
5101
19793
19717
13752
#Edges
492
750
213134
83214
1385586
302220
108365
13264
259613
126731
#Feateces
1703
1703
952
2000
500
1705
500
500
125
350
5703
550
1435
767
745
IChssess
5
70
40
10
3
10
ITraia
120
3648
2406
446625
1395
550
9463
1392
200
2432
1864
2000
1799
6310
196
300
Flot
37
51
1530
1041
456
37
22313
16340
40603
5487
566
2044
407
19252
7250
Table 5: Dataset Statistics.
A.5.2 BASELINES
We provide the methods in comparison along with the hyper-parameters ranges for each model. For all the models, we sweep the common syper-parametedd in the same ranges. Learning rate is swept over [0.001. 0.003, 0.005, 0.008. 0.01], dropout over [o.2, 0.3, 0.4, 0.5. 0.6, 0.7, 0.8]. weight decay over [e 4, 5e - 4. le - 3, 5e - 3, le 2, 5e - 2, le - 1]. and hidden dimensions over [16, 32, 64). For model-specific
aaper-parametery, we tune over author prescribed ranges. We use undirected graphs with symmetric normalization for all graph networks in comparison. For all models, we report test accuracy for the configuration that achieves the highest validation accuracy. We report standard deviation wherever applicable.
LR and MLP: We trained Logistic Regression classifier and Multi Layer Perceptron on the given node features. For MLP, we limit the number of hidden layers to one.
GCN: We use the GCN implementation provided by the authors of Chien et al. (2021). Note: We observe discrepancies in performance with various implementations of GCN. We make note of this in Section A.7.
http://wwww.......ccc.occcccc/tt hwwp:////cccccoooooo/o////////bb 1/www/wwkh
19

---

Under review as a conference paper at ICLR 2022
SGCN (Wu et al., 2019) is a spectral method that models a low pass filter and uses linear classifier. The number of layers in SGCN is treated as a
SGCN:
and swept over [1,
SUPERGAT (Kim & Oh, 2021) is an improved graph attention model designed to also work with noisy graphs. SUPERGAT employs a link-prediction based self-supervised task to learn attention edges. As suggested by the authors, datasets with homophily levels lower than 0.2 we use SUPERGAT For other datasets, we use MXx-- We rely on authors code" for our experiments.
SUPERGAT:
GEOM-GCN; GEOM-GCN (Pei et al., 2020) proposes a geometric aggregation scheme that can capture structural information of nodes in neighborhoods and also capture long range dependen- cies. We quote author reported numbers for Geom-GCN. We could not run Geom- GCN on other benchmark datasets because of the unavailability of a pre-processing function that not publicly available.
HCGCN: H,GCN (Zhu et al., 2020) proposes an architecture, specially for heterophilic settings, that incorporates three design choices: i) ego and neighbor-ens weighbor-embedding separation, higher-orde order neighborhoods, and combining intermediate representations. We quote author reported numbers where available, and sweep over author prescribed hyper-parameters for reporting results on the rest datasets. We rely on author's code² for our experiments.
FAGCN (Bo et al., 2021) adaptively aggregates different low-frequency and high- frequency signals from neighbors belonging to same and different classes to learn better node rep- resentations, We rely on author's ' code for our experiments.
FAGCN:
APPNP: APPNP (Klicpera et al., 2019) is an improved message propagation scheme derived from personalized PageRank. APPNP's addition of probability of teleporting back to root node permits it to use more propagation steps without oversmoothing. We use GPR-GNN's implementation of APPNP for our experiments.
LIGHTGCN; LIGHTGCN (Navarin et al., 2020) is spectrally grounded GCN that adapts the entire eigen spectrum of the graph obtain better node feature representations.
(Chien et al., 2021) adaptively learns weights to jointly optimize node representations and the level of information to be extracted from graph topology. We rely on author's code' for our experiments.
GPR-GNN:
TDGNN:
TDGNN (Wang & Derr, 2021) is tree decomposition method which mitigates feature smoothening and disentangles neighbourhoods in different layers. We rely on author's 's code for our experiments.
ARMA: ARMA (Bianchi et al., 2021) is a spectral method that uses K stacks of ARM A filters in order to create an ARM Aς filter (an ARMA filter of order K). Since (Bianchi al., 2021) do not specify a hyperparameter range in their work, following are the ranges we have followed: GCS stacks (S): 2,, 4, 5, 5, 7, 8, 9, 10), stacks' depth(Z'): [1 2, 4. 5, 6, 7, 8, 9, 10). However we only select configurations such that the number of learnable parameters are less than or equal those in PP-GNN. The input to the ARMAConv layer are the node features and the output the number of classes. This output is then passed through a softmax layer. We use the implementation from the official PyTorch Geometric Library
BernNet: BernNet (He et al., 2021) is a method that approximates any filter over the normalised Laplacian spectrum of a graph, by a kth Order Bernstein Polynomial Approximation. We use the model specific hyper-parameters prescribed by the authors of the paper. We vary the Propagation Layer Learning Rate as follows: [0.001, 0.002, 0.01, 0.05). We also vary the Propagation Layer
*nttps: htttta/s//dtaabbb.cm/m/anrrrrrrr
/torch_
geometric/n//con//// #ARMACoNV
20

---

Under review as a conference paper at ICLR 2022
Dropout follows: [0.2, 0.3, 0.4, 0.6, 0.7, 0.7, We rely the authors code for experi- ments.
AdaGNN: AdaGNN (Dong al., 2021) is method that captures the different importance's 's for varying frequency components for node representation learning. We use the model specific hyper- parameters prescribed by the authors of the paper. The No. of Layers hyper-parameter is varied as follows: 42,4,8, 8, 32, 128). We rely on the authors code for our experiments.
A.5.3 COMPARISON AGAINST ADDITIONAL. BASELINES
We performed experiments over the same datasets using three new baselines: ARMA (Bianchi et al. (2021)), BernNet (He et al. (2021)) and AdaGNN (Dong al. (2021)). 1).. Details about these baselines are given in Section A.5.2. The results are reported in Tables 6 and 7. The results are obtained after thorough optimization over the respective hyperparameters, the details of which are listed in A.5.2:
Test Ace
Texas
Wisconsin
Squirrel
Chameleon
Cornell
Flickr
BemNET
83,24 (6.47)
84.90 (4.53)
52.56 (1.69)
62.02 (2.28)
80.27 (5.41)
52.35
ARMA
79.46 (3.65)
82.75 (3.56)
47.37 (1.63)
60.24 (2.19)
80.27 (7.76)
53.79
AdaGNN
71.08 (8.55)
77.70 (4.91)
53.50 (0.96)
65,45 (1.17)
71.08 (8.36)
52.30
GPR-GNN
81.35 (5.32)
82.55 (6.23)
46.31 (2.46)
62.59 (2.04)
78.11 (6.55)
52.74
PP-GNN
89.73 (4.90)
88.24 (3.33)
56.86 (1.20)
67.74 (2.31)
82.43 (4.27)
54.44
Table Results on Heterophilic Datasets.
Test Ace
Cora-Full Full (PCA)
OGBN-ArXiv
Wiki-CS
Citeseer
Puhmed
Cora
Computer
Pbotos
BemNET
60.77 (0,92)
(1.43)
89.03 (0.55)
(1.41)
(1.99)
91.61 (0.51)
ARMA
60.23 (1.21)
69.49
78.94 (0.32)
78.15 (0.74)
88.73 (0.52)
87.37 (1.14)
(2.62)
90.26 (0.48)
AdaGNN
59.57 (1.18)
69.44
77.87 (4.95)
74.94 (0.91)
89.33 (0.55)
86.72 (1.29)
81.27 (2.10)
89.93 (1.22)
GPR-GNN
61.37 (0.96)
68.44
79.68 (0.50)
76.84 (1.69)
89.08 (0.39)
87.77 (1.31)
82,38 (1.60)
91.43 (0.89)
PP-GNN
61.42 (0.79)
69.28
80.04 (0.43)
78.25 (1.76)
89.71 (0.32)
89.52 (0.85)
85.23
92.89 (0.37)
Table 7: Results on Homophilic Datasets.
For AdaGNN and BernNet, we use the authors code and tune over the hyperparameters as provided in the paper. For ARMA, we use the official PyTorch Geometric implementation (see A.5.2). As sanity check, we also tested ARMA on the node classification datasets described in the paper and were able to reproduce similar numbers.
A.5.4 COMPARISON AGAINST GENERAL FIR FILTERS
Instead of using polynomial filter, we general FIR filter (GFIR) which is described by the following equation:
K
7
S
XH
where S is the graph shift operator (which in our case is A), X is the node feature matrix and H 's are learnable filter matrices. One can see GCN, SGCN, GPR-GNN special cases of this GFIR filter, which constrain the H₃ in different ways.
We first demonstrate that constraint on the GFIR filter is necessary for getting improvement in performance, particularly on heterophilic datasets. Towards this, we build two versions of GFIR: one with regularization (constrained), and the other without regularization (unconstrained), We ensure that that the number of trainable parameters in these models are comparable to those used in PP-GNN. We provide further details of the versions of the GFIR models below and report the results in Table 8 below:
"htpps: ://gi wht...com//vmmmee//eeeeneet "https: :/ thub. cot.b..comyuiiii htt..//co/ysssunogg///oeo AdaGNN
21

---

Under review as a conference paper at ICLR 2022
Unconstrained Setting: In this setting, we do not impose any regularization constraints such as dropout and L2 regularization.
Constrained Setting: In this setting, we impose dropouts well as 1.2 regularization on the GFIR model. Both dropouts and 1.2 regularization were applied on the H (the learnable filter matrices from the above equation).
We also compare PP-GNN (the proposed model) as well as GPR-GNN to the General FIR filter model (GFIR).
Train Acc /Test Ace
Computers
Chameleon
Citeseer
Cora
Squirrel
Texas
Wisconsin
GFIR (Unconstruined)
78.39 (1.09)
51.71 (3.11)
75.83 (1,94)
87.93 (0.90)
36.50
73.24 (6.91)
77.84 (3.21)
GFIR (Constrained)
79.57 (2.12)
61.27 (2.42)
76.24 (1.43)
87.46 (1.26)
41.12
74.59 (4.45)
79.41 (3.10)
GPR-GNN
82.38 (1.60)
62.59 (2.04)
76.84 (1.69)
87.77 (1.31)
46.31 (2.46)
81.35 (5.32)
82.55 (6.23)
PP-GNN
85.23 (1.36)
67.74 (2.31)
78.25 (1.76)
89.52 (0.85)
56.86 (1.20)
89.73 (4,90)
88.24 (3.33)
Table 8: Comparing PP-GNN and GPR-GNN against the GFIR filter models.
We can make the following observation from the results reported in Table 8:
Firstly, constrained GFIR performs better than the unconstrained version, with performance lifts of up to 10%% This suggests that regularization important for GFIR models.
GPR-GNN outperforms the constrained GFIR version. It is to be noted that GPR-GNN further restricts the space graphs explored as compared to GFIR. This suggests that regularization beyond simple L2/dropout kind of regularization (polynomial filter) is bene- ficial.
PP-GNN performs better than GPR-GNN Our model slightly expands the space of graphs explored (as compared to GPR-GNN, but lesser than GFIR), while retaining good perfor- mance. This suggests that there is still room for improvement on how regularization is done.
PP-GNN has shown one possible way to constrain the space of graphs while improving performance on several datasets, however, it remains to seen whether there are alternative methods that can do even better. We hope to study and analyze this aspect in the future.
A.5.5 IMPLEMENTATION DETAILS
In this subsection, we present several important points that are useful for practical implementation of our proposed method and other experiments related details. Our approach is based on adaptation
of eigen graphs constructed using eigen components. Following Kipf & Welling (2017), we use symmetric normalized version (A) of adjacency matrix A with self-loops: À = D (A + I)D We work with eigen matrix and eigen
where D.; = 1 DRs Dü Ej Aij and Dij 0, + values of Å.
To reduce the learnable hyper-parameters, we separately partition the low-end and high-end eigen values into several contiguous bins and use shared filter parameters for each of these bins. The number of bins, which can be interpreted as number of filters, is swept in the range 2,, 4, 4,5, 5, 10, 20). The orders of the polynomial filters are swept in the range [1, 10) in steps of 1. The number of EVD components are swept in the range [32, 64, 128, 256, 512, 1024]. In our experiments, we set rj = *] and we vary the 7)I parameter in range (0, 1) and Mgprr 1 m
For optimization, we use the Adam optimizer (Kingma & Ba, 2015). We set early stopping to 200 and the maximum number of epochs to 1000. We utilize learning rate with decay, with decay factor set to 0.99 and decay frequency set to 50. All our experiments were performed on a machine with Intel Xeon 2. 2.60GHz processor, 1 12GB Ram, Nvidia Tesla P-100 GPU with 16GB of memory, Python 3.6, and PyTorch 1.9.0 (Paszke et al., 2019). We used Optuna (Akiba et al., 2019) to optimize the hyperparameter search.
22

---

Under review as a conference paper at ICLR 2022
A.5.6 ADAPTABLE FREQUENCY RESPONSES
In Figure 2 of the main paper, we observe that PP-GNN learns a complicated frequency response for a heterophilic dataset (Squirrel) and a simpler frequency response for homophilic dataset (Cite- seer). We observe that this trend follows for two other datasets Chameleon (heterophilic) and Com- puter (homophilic). See Figure 9.
CAN (GM--NNI)
PANGNN (GFT-CNN)
10.00
eigen values
eigen values
(a) Chameleon
(b) Computer
Figure 9: Learnt Frequency Responses
A.5.7 DOES THE POLYNOMIAL INITIALIZATION MATTER FOR GIVING GOOD PERFORMANCE?
In our experiments, we have varied the polynomial initialization schemes namely: [PPR, NPPR and Random], as described in GPRGNN paper Chien al. (2021). To understand whether this polynomial initialization is important, we perform an ablative study to compare the various initialization schemes. We observe that our model (PP-GNN) retains similar performance across all initialization schemes. For brevity, we report results on six datasets (Cora, Citeseer, Squirrel, Chameleon, Texas and Wisconsin). The results can be found Table 9, Our experiment results suggest that tuning polynomial initialization for each partition can indeed be avoided without compromising on the performance.
Test Acc
Chumeleon
Citeseer
Cora
Squirrel
Texas
Wisconsin
PP-GNN (NPPR)
66.73 (1.86)
78.41 (1.54)
89.52 (0.85)
$7.93 (1.46)
88.38 (3.61)
87.25 (2.96)
PP-GNN (Random)
68.71 (2.47)
78.28 (1.70)
89.42 (0.98)
$7.59 (1.56)
88.38 (3.48)
88.63 (2.58)
PP-GNN (PPR)
67.74 (2.31)
78.25 (1.76)
89.52 (0.85)
56.86 (1.20)
89.73 (4.90)
88.24 (3.33)
65.45 (1.17)
78.15 (0.74)
88.26 (1.32)*
53.50 (0.96)
84.86 (6.77)*
86.67 (4.69)*
Best Performing Baselines
AdaGNN
ARMA
TDGNN
AdaCNNN
H2GCN
H2GCN
Table 9: Results for PP-GNN using different polynomial (gamma) initializations versus the best performing baseline models. The names of the best performing baseline models are given right below the test accuracy, in the 'Best Performing Baselines' row.
A.5.8 DOES THE MLP EVEN MATTER?
In PP-GNN there is a two layered MLP (that transforms the input node features) followed by a single graph filtering layer similar to GPR-GNN.
To understand MLP's significance, we ran an additional experiment, where we have used a single linear layer, instead of the two layered MLP. We continue observe competitive (with respect to our original PP-GNN model) performance, across most datasets. The results can be found in Table 10. Also, the two layer MLP is not the significant contributor towards performance. This can also be seen by comparing GPR-GNN performance with that of LGC's. LGC can be interpreted as a linear version of GPR-GNN and achieves comparable performance GPR-GNN.
Note that PP-GNN (Linear) was not thoroughly trained as the PP-GNN (Original) due to time con- straints. The hyperparameter ranges explained right below the next paragraph.
23

---

Under review as a conference paper at ICLR 2022
Computers
Chameleon
Citeseer
Cora
Squirrel
Texas
Wisconsin
GPR-GNN
82.38 (1.60)
62.59 (2.04)
76.8 (1.69)
87.77 (1.31)
46.31 (2.46)
81.35 (5.32)
82.55 (6.23)
LGC
83.44 (1.77)
61.14 (2.07)
76.96 (1.73)
88.02 (1.44)
44.26 (1.49)
80.20 (4.28)
81.89 (5.98)
PP-GNN (Original)
85.23 (1.36)
67.74 (2.31)
78.25 (1.76)
89.52 (0.85)
56.86 (1.20)
89.73 (4.90)
88.24 (3.33)
PP-GNN (Linear)
84.27 (1.19)
67.88 (1.62)
77.86 (1.74)
88.43 (0.69)
55.11 (1.72)
85.58 (4.70)
86.24 (3,23)
Table 10: Comparision of Linear GPR-GNN and Linear PP-GNN with respect to other pertinent baselines.
Table 10 above seems to suggest that PP-GNN (Linear) is competitive to PP-GNN (Original). We believe the difference in performance is an artifact of inadequate tuning. We can infer that adding MLP ma give marginal improvements over the linear version. This phenomenon is also observed in GPR-GNN, To illustrate this, we can compare GPR-GNT with LGC (linear version of GPR-GNN). We can observe in the above table that GPR-GNN and LGC are comparable in performance.
For this additional set of experiments (Linear PP-GNN), due to time constraints, we have reduced the ranges for several Trials to 50. These reduced ranges are as follows:
of our model, while also reducing the number of Optuna
Learning Rate: [0.003, 0.005]
Weight Decay: [0.0001, 0.001]
Dropout: [0.3, 0.5]
Hidden Dims: [32, 64]
Order of the Polynomial: [2, 4]
No. of Partitions (Buckets): [2, 4]
Number of Eigen Value: [256, 1024]
t.: Sampled uniformly between [0, 1] using Optuna
Despite this smaller hyper-parameten search space, we are only shy by few percentage points on the Texas dataset. We believe this difference can be recovered with thorough tuning.
A.6 TRAINING TIME ANALYSIS
In the following subsections, we provide comprehensive timing analysis.
Computational Complexity: Listed below is the computational complexity for each piece in our model for single forward pass. Notation n: number of nodes, |E]: the number of edges, A: symmetric normalized adjacency matrix, F: features dimensions, d: hidden layer dimension, C: number of classes, ex denotes the cost of EVD, K: polynomial order/hop order, 1: number of cigenvalues/vectors in a single partition of spectrum (for implementation, we keep I same for all such intervals), number of partitions of a spectrum.
MLP: OnFFd + ndC)
GPR-term: O(K) (KEE + OnKCC) The first term the cost for computing A f() for sparse A. The second term is the cost of summation En A fXX).
Excess terms for PP-GNN: O(mnIC). This is obtained by the optimal matrix multiplica- tion present in Equation of the main paper (U, is n x I, (7)) is x I, Zo() is n x C). The additional factor m is because have different contiguous intervals/different poly- nomials. Note that typically n is much larger than I.
EVD-term: e", the complexity for obtaining the eigenvalues/vectors the adjacency matrix, which is usually very sparse for the observed graphs. Most publicly available solvers for this task utilize Lanczos' algorithm (which is a specific case of a more general Amoldi iteration). However, the convergence bound of this iterative procedure depends upon the starting vectors and the underlying spectrum (particularly the ratio of the absolute difference of two largest eigenvalues to the diameter of the spectrum) [Saad (1980), LI
24

---

Under review as a conference paper at ICLR 2022
(2010), Cullum & Willoughby (2002)]. Lanezos' algorithm is shown to be a practically efficient way for obtaining extreme eigenpairs for a similar and even very large systems. We use ARPACK's built-in implementation to precompute the eigenvalues/vectors for all datasets before training, thus amortizing this cost across training with different hyper-parameters configuration.
Per Component Timing Breakup: In Table 11, we provide a breakdown of cost incurred in seconds for different components of our model. Since the eigenpairs' computation is a one time cost, we amortize this cost over the total hyper-parameters configurations and report the effective training time in the last column on of Table 11.
Average Training Time: In Table 12, we report the training time averaged over 100 hyper- parameter configurations for several models. To understand the relative performance of our model with respect to GCN, we compute the relative time taken and report it in Table 13. We can observe in Table 13 that PP-GNN is 4x slower than GCN, 2X slower than GPR-GNN and BemNET, and ~ 2X faster than AdaGNN. However, it is important to note that in our average training time, the time taken compute K top and bottom eigenvalues/vectors is amortized across the number of trials
Can we cut down the total training cost for PP-GNN? syper-parameters for our 100 configurations experiments and prescribe below the new ranges for hyperparameters. Reduced hyperparameters space:
To study this, we analyzed the chosen
Learning Rate: [0.003, 0.005]
Weight Decay: [0.0001, 0.001]
Dropout: [0.3, 0.5]
Hidden Dims: [32, 64]
Order of the Polynomial: [2, 4]
No. of Partitions (Buckets): [2, 4]
Number of Eigen Value: [256, 1024]
t.: Sampled uniformly between [0, 1] using Optuna
We further restrict the total number of Optuna trials to 20. Note that as shown in Section A.5.7, our model is insensitive to the polynomial initialization scheme. Hence we use 'random' initialization, thereby reducing the number of hyperparameters even further. The total time taken by PP-GNN (in- cluding the one-time cost for obtaining eigenpairs) for training (and performing hyperparameter op- timization) over 20 haper-parrmeter configurations reported in Table 14. For comparison, we also show the total training time for the 100 configurations experiments in Table 15 which too includes the time taken to obtain min(n, 1024) eigenpairs. From Tables [14,15] we can observe that the total training time has reduced by 5z. In Table 16. hyper-paramese range, our model performs competitively or better.
observe that even with the reduced
A.7 DISCREPANCIES IN PERFORMANCE BETWEEN DIFFERENT GCN IMPLEMENTATIONS
We tested three different implementations of GCN(s) (Kipf & Welling, 2017) provided by 1) Thomas Kipf and Max Welling 12 (In TensorFlow), 2) The implementation' 13 of the authors the GPR-GNN paper (Chien et al., 2021) (in PyTorch), 3) The code base 14 publicly available at the OGBN-ArXiv leader-board (in PyTocc)), on the OGBN-ArXi dataset.
hottpp:///ithhbe htt..tcccc//aaaaac020011111 /
nodeproppred/arxix
25

---

Under review as a conference paper at ICLR 2022
PP-GNN
Training Time
EVD Cost
Number of EV's obtained
Effective Training Time
Texas
11.89
0.00747
183 (All BVs)
11.89
Cornell
11.63
0.03271
183 (All EVs)
11.63
Wisconsin
12.08
0.01225
251 (All EVs)
12.08
Chameleon
21.44
3.71883
2048
21.48
Squirrel
31.38
15.8152
2048
31.54
Cora
22,46
54.3684
2048
23.01
Citeseer
20.51
56.9744
2048
21.08
Cora-Full
63.98
155.304
2048
65.53
Pubmed
52.54
256.71
2048
55.11
Computers
28.63
76.2738
2048
29.39
Photo
19.3
48.3683
2048
19.78
Flickr 161.16
304.114
2048
164.20
ArXiv 189.94
412.504
1024
194.06
WikiCS
27.92
65.4376
2048
28.57
Table 11: PP-GNN's per component timing cost. Training Time refers to the end to end training time (without eigen decomposition) averaged across 100 trials. EVD cost refers to the time taken to obtain x top and bottom eigenvalues. This can be found in the 'Number of EV's obtained' column. Since EVD is one time cost, we average this cost over the total number of trials and add the training time. We refer to this cost as the Effective Training Time.
Dataset
GPR-GNN
PP-GNN
MLP
GCN
BernNet
ARMA
AdaGNN
Texas
9.27
11.89
1.08
3,46
5.59
6
13.97
Cornell
9.41
11.63
1.06
3.69
5.37
5.51
12.56
Wisconsin
9.67
12.08
1.07
3.42
5.69
5.36
13.57
Chameleon
14.69
21.48
2.6
6.42
12.46
7.84
28.77
Squirrel
18.94
31.54
5.04
7.52
17.82
28.87
90.36
Cora
12.9
23.01
1.95
5.94
12.25
10.67
22.15
Citeseer
10.62
21.08
3.72
4.56
9.52
19.5
35.34
Cora-Full
24.98
65.53
7.77
8.01
31.26
40.21
175.58
Pubmed
14
55.11
6.21
11.73
12.64
27.76
162.01
Computers
7.67
29.39
2.24
6.68
7.48
27.76
118.43
Photo
8.58
19.78
1.68
5.1
7.95
14.34
45,46
Flickr
42.64
164.20
21
30.4
62.11
119.3
178.7371
ArXiv
118.35
194.06
78.9
102.88
693.92
771.59
307.84
WikiCS
14.37
28.57
3.34
10.8
11.43
30.79
73.63
Table 12: Training Time (in seconds) across Models
Note that the authors of the leader-board code report test accuracy of 71.74% on the OGBN-ArXiV dataset. Extensive tuning was done on the Kipf and Welling implementation in order match the results of the leaderboard code. However, accuracy increased to only 65.53%, which is still much lesser.
after extensive lyper-parameter tuning, the test
Two other implementations that we tested were: a) The GCN implementation from the authors of the GPR-GNN paper (Chien et al., 2021) (in PyTorch) b) The leader-board implementation (in PyTorch). The results for all the three implementations the OGBN-ArXiv Dataset can be found Table 17.
26

---

believe that Under review as a conference paper at ICLR 2022
Dataset
GPR-GNN
PP-GNN
MLP
GCN
BernNet
ARMA
AdaGNN
Texas
2.68
3.44
0.31
1.00
1.62
1.73
4.04
Cornell
2.55
3.15
0.29
1.00
1.46
1.49
3,40
Wisconsin
2.83
3.53
0.31
1.00
1.66
1.57
3.97
Chameleon
2.29
3,35
0,40
1.00
1.94
1.22
4.48
Squirrel
2.52
4.19
0.67
1.00
2.37
3.84
12.02
Cora
2.17
3.87
0.33
1.00
2.06
1.80
3.73
Citeseer
2.33
4.62
0.82
1.00
2.09
4.28
7.75
Cora-Full
3.12
8.18
0.97
1.00
3.90
5.02
21.92
Pubmed
1.19
4.70
0.53
1.00
1.08
2.37
13.81
Computers
1.15
4.40
0.34
1.00
1.12
4.16
17.73
Photo
1.68
3.88
0.33
1.00
1.56
2.81
8.91
Flickr
1.40
5,40
0.69
1.00
2.04
3.92
5.88
ArXiv
1.15
1.89
0.77
1.00
6.74
7.50
2.99
WikiCS
1.33
2.65
0.31
1.00
1.06
2.85
6.82
Average
2.03
4.09
0.50
1.00
2.19
3.18
8.39
Table 13: Training Time of models relative to the training time GCN
Datasel
Chameleon
Citeseer
Computers
Cora
Cora-Full
Photo
Pubmed
Squirrel
Texas
Wisconsin
OGBN-ArXiv
Time
00:03:16
00:10:17
00:34:37
00:05:21
00:59:29
00:10:31
00:57:40
00:10:38
00:02:27
00:02:33
01:03:20
Table 14: End to end training time (HH:MM:SS) for optimizing over 20 hyperparameter configura- tions
Besides different implementations of GCN(s), we find that batch normalization is done in the implementation used in the GCN leader-board code. We see that (in Table 17) the performance numbers vary depending on the implementation. Also, batch normalization helps to get nearly 2% improvement for this dataset. Since we did not perform batch normalization in all our experiments we find a performance gap 2% for this dataset in results reported in our paper (against the leader-board code).
We have also compared the GCN implementation from Kipf and Welling as well as the GCN imple- mentation from the authors the GPR-GNN across various datasets in Table 18.
We can see that both the TensorFlow and the PyTorch implementations lead to a similar performance for most of the datasets. However, there are some differences performance for some datasets (Wisconsin, Cora-Full (PCA), OGBN-ArXiv, Computer and Photos). We have ensured that hyper- parameters, preprocessing steps etc., are same across both these implementations. these differences can be attributed the different internal workings of TensorFlow and Py PoTch..
further study is required to understand where these gaps are coming from.
Note: In the main paper (in Tables [l) report the results obtained on the GCN implementation by the authors of the GPR-GNN paper.
27

---

Under review as a conference paper at ICLR 2022
Conguters
Squirel
Time
01-3934
01:31:36
01-51:11
01-30MM
04:00-15
(0:46:00
03:19-97
01:59-30
006460)
(0:44:56
(41-8:16
050061
Table 15: End to end training time (HH: for optimizing over 100 hyperparameter configu- rations
Texas
Squirnd
Chamclesa
Cuss-Full (PCA)
OGBN-AcKi
Ciesser
Puhmel
Cora
Plotes (Amasun)
PP-GAN
(2.30)
(1.0 (1.15
(0.33
(7.97
89.43 (0.4)
(0
(0.58
Performing Buselins
54 8h (6
$1.5010 96)
(1.551
(0:90)
3710 (1.64)
89.59 10-33
$8.26 (1 10)
92 (21
Table 16: Comparison of PP-GNN trained on reduced hyper-parameter space against the best performing baseline models. Note that the best performing baseline models are trained the full (original pprameer set) and also for 100 Optuna Trials. The names of the best performing baseline models given below the value of the test accuracy, in the 'Best Performing Baseline row.
OGBN-ArXiv
Framework
Batch Norm
Test Accuracy
GCN (Kipf and Welling)
TensorFlow
True
65.84
GCN (Kipf and Welling)
TensorFlow
False
65.53
GCN (Leaderboard Code)
PyTorch
True
71.88
GCN (Leaderboard Code)
PyTorch
False
70.23
GCN (GPR-GNN)
PyTorch
True
71.05
GCN (GPR-GNN)
PyTorch
False
69.37
Table 17: GCN results with different implementations.
Table 18: Comparing different GCN implementations. (GPR-GNN implementation Kipf and
Welling Implementation)
28


Reviews:
[{"review_id": "umYf9elP20T", "reviewer": "Reviewer_SUfF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrength\n- The proposed architecture is well-motivated.\n- The ablation study is extensive.\n\nWeakness\n- There are a lot of hyper-parameters to tune. ( The number of partitions, which can be interpreted as the number of filters, is swept in the range [2,3,4,5,10,20]. The polynomial filter order is swept in the range [1,10] in steps of size 1. The number of eigenvalues/vectors are swept in the range [32, 64, 128, 256, 512, 1024].)\n- Computational time is unclear. I suggest the authors clearly write the training time for each dataset. Please clarify the eventual computational complexity of the model that's used in the experiments. How many times is your model more expensive than GCN or the polynomial filter?\n- It is not clear why the reported performance of ogbn-arxiv is much worse than that in the leaderboard. For instance, the GCN performance reported in Table 2 is 63.48, while the official leaderboard reports (https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-arxiv) the test accuracy of 0.7174 ± 0.0029.\n", "summary_of_the_paper": "In this paper, the authors aim to develop GNN that can better adapt to the given prediction task (both homophily and heterophiliy). Specifically, the authors extend the existing polynomial filter and propose to learn a filter function as a sum of polynomials over different subsets of the eigenvalues. The effectiveness of the proposed GNN architecture is demonstrated on diverse node classification tasks. The ablation studies were carried out to understand the proposed GNN architecture.", "summary_of_the_review": "I suggest the weak reject to this paper in its current form. I can consider raising my score if all my concerns (raised in the weakness section) are addressed properly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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": "t4xw6cDzlvQ", "reviewer": "Reviewer_eu6Q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "This paper focuses on the task of node classification (semi-supervised learning) in heterophilic graphs. The authors identify that low-pass filter-based GNNs perform poorly on heterophilic graphs, precisely because they tend to smooth out differences in neighboring node features. Thus, they propose to look into filters capable of learning high-frequency content that can thus learn labels even if neighboring nodes do not share a label.\n\nIn particular, the authors propose to learn different low-order polynomials for different parts of the spectrum. I find this idea very interesting, and worth investigating.\n\nHowever, I find the premises of the paper not to be entirely adequate. In particular, there is quite a few references missing that should be more relevant for the discussion at hand. This leads the experimental results, albeit certainly very extensive, quite uninformative.\n\nIn what follows, I will introduce some well-known definitions to ground the discussion and to illustrate my point. Most of the basic graph signal processing (GSP) definitions can be found in\n\n[R1] A. Sandryhaila and J. M. F. Moura, \"Discrete signal processing on graphs,\" IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644-1656, 1 Apr. 2013.\n\n[R2] A. Sandyhaila and J. M. F. Moura, \"Discrete signal processing on graphs: Frequency analysis,\" IEEE Trans. Signal Process., vol. 62, no. 12, pp. 3042-3054, Jun. 2014.\n\nGiven a graph G = (V,E), a graph signal is defined as a mapping between the node set and the real numbers, x: V \\to R. This can be conveniently collected in a vector x \\in R^n, where n is the number of nodes of the graph.\n\nAn FIR graph filter is a mapping H(S) between graph signals given by\n\nH(S) = \\sum_{k=0}^{K} h_k S^k\n\nwhere S is the so-called graph shift operator (i.e. a n x n matrix description of the graph, for example, the adjacency matrix, the Laplacian matrix, the Markov matrix, or any of their normalized counterparts) and where h_k are the filter taps. The output y = H(S)x is another graph signal.\n\nAt this point, the authors correctly identify the shortcomings of GCN (Kipf and Welling 2017) --and many derived works-- in terms of the frequency response of the learned filters: GCN forces K = 1, h_0 = 0 and only learns h_1. By choosing S = normalization(I+A), then it is evident that the frequency response of the learned filters is going to be h_1*\\lambda, and since S is derived from the adjacency matrix, higher eigenvalues denote lower frequencies [R2]. Thus, the only filters learned are low-pass filters, leading to good classification in homophily graphs (where neighbors share a label). This is, of course, also true of SGCs (Wu et al, 2019) where the h_k = 0 for all k < K and only h_K is learned, thus the frequency response is h_K * \\lambda^k, which is also a low pass filter when choosing S = I+A.\n\nIt's worth noting, that even if K = 1, it is possible to create a high-pass filter if only h_0 can be learned as well. As a matter of fact, by setting h_0 = 2 and h_1 = -1, the resulting frequency response is 2 - \\lambda, which is a high-pass filter (high-frequency response for small lambda, lower frequency response for higher lambda).\n\nNow, that one needs to learn all filter taps, and that the value of K is a design choice akin to the kernel size in CNNs, is duly noted in Defferrard et al, 2021. Albeit, ChebNets restrict themselves to normalized Laplacians and filter taps computed by means of a Chebyshev polynomial.\n\nAt this point, the author's assessment is correct, in that, in order to learn classification in heterophilic graphs, high-pass filters are necessary (to compute differences with neighborhoods), and thus GCNs (and their variants like SGC) are always going to fall short.\n\nMy concerns arise when handling node features, which are typically d-dimensional vectors. In this case, the concept of graph signal is extended to encompass node features: x is now a mapping from the node set to R^d. This is now conveniently collected in a matrix X in R^{n \\times d}, as the authors correctly observe.\n\nWhen handling node features, the dimension of the node features at the output, say e, may be different from the dimension of the node features at the input, say d. Thus, the FIR graph filter is extended to be a bank of D x E graph filters, which can be compactly written as\n\nH(X;S) = \\sum_{k=0}^{K} S^k X H_k\n\nwhere now the filter taps H_k are D x E matrices. This was duly noted in Defferrard et al 2016, albeit with a very particular value of S, and with a Chebyshev recursion on the H_k. This was properly extended to arbitrary filters with arbitrary values of S back in 2018:\n\n[R3] F. Gama, A. G. Marques, G. Leus, and A. Ribeiro, \"Convolutional neural network architectures for signals supported on graphs,\" IEEE Trans. Signal Process., vol. 67, no. 4, pp. 1034–1049, 17 Dec. 2018.\n\nOnce we have the FIR graph description for node features\n\nH(X;S) = \\sum_{k=0}^{K} S^k X H_k\n\nIt is immediate to see many of the other architectures as imposing different constraints on this general definition, i.e.\n\nGCN: K = 1, S = normalization(I+A), H_0 = 0, H_1 = learnable\n\nSGC: K chosen, S = normalization(I+A), H_k = 0 for k < K, H_K = learnable\n\nGPR-GNN: K chosen, S = normalization(I+A), H_k = \\gamma_k I for k > 0 (In the GPR-GNN, H_0 is learned by means of the same MLP applied to the features of each node, if such MLP has length L, this can be written as X_l = sigma(X_{l-1} H_l), so it can be seen as adding L layers with K=0 at the beginning of the GNN)\n\nAs we can see, all these architectures, even if they can learn high-pass filters (as is the case of GPR-GNN), unnecessarily restrict the space of allowable filters, for no apparent reason. This will, undeniably, affect their performance.\n\nThus, we reach my first concern: I genuinely appreciate the exhaustiveness of the numerical experiments, but I believe them to be misguided. Comparisons with GCNs and SGCs are pointless in the context of heterophilly, and comparison with GPR-GNN is misleading due to the unnecessary constraints. I would expect, at the very least, a comparison with a GNN built with arbitrary FIR graph filters with no constraints, i.e., where the linear part of the layer is given by the following equation\n\nH(X;S) = \\sum_{k=0}^{K} S^k X H_k\n\nChebNets are a good implementation for this, albeit, for a fair comparison, the value of S should be the same, and thus, Chebyshev Polynomials may not be an option, so that the architecture in [R3] may make more sense.\n\nThe next argument that the authors make is the choice of K. The authors correctly identify that for K = N-1 all possible filters can be learned (in theory, albeit probably not in practice due to optimization problems in a space that grows with the size of the data) from the FIR graph filter due to the Cayley-Hamilton theorem (as long as the eigenvalues are distinct). The authors correctly argue that high values of K are impractical, because higher values of K involve a higher number of exchanges with neighbors, incurring a communication delay.\n\nWhile this is true, the reasons to propose the spectrum partition are not entirely justified.\n\nOn the one hand, it has been noted that even K=1 is enough to learn a high-pass filter.\n\nOn the other hand, higher values of K allow for sharper frequency transitions, which may or may not be useful.\n\nThe authors thus propose to partition the frequency space (at the expense of an eigendecomposition) and use low-order polynomials over different parts of the spectrum.\n\nHowever, it is known that the use of ARMA graph filters lead to sharper transition with a fewer number of exchanges\n\n[R4] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein, \"CayleyNets:\nGraph convolutional neural networks with complex rational spectral filters,\" IEEE Trans. Signal Process., vol. 67, no. 1, pp. 97–109, Jan. 2019.\n\n[R5] F. M. Bianchi, D. Grattarola, L. Livi, and C. Alippi, \"Graph Neural Networks with Convolutional ARMA Filters\", IEEE Trans. Pattern Anal. Mach. Intell., 26 Jan. 2021, early access. [Online]. Available: https://doi.org/10.1109/TPAMI.2021.3054830\n\nThis gives rise to my second concern: I believe that comparisons with GNNs using ARMA graph filters is absolutely necessary to see if the sharper transitions obtained by smaller frequency bands are worth their use over other techniques to design sharp transitions with small K.\n\nThe third concern comes from the fact that, when partitioning the spectrum, the authors are learning a collection of filters, one for each part of the spectrum. However, the expression for processing node features already includes a bank of graph filters. How does the choice of node features in the hidden layers (i.e. number of hidden units) interplay with the number of filters learned in the spectrum transition?\n\nTo be more precise on my third concern, let's assume that we partition the spectrum on three different frequency bands, and we learn a different low-order polynomial for each of them. Due to superposition, these three bands can be thought of as three different filters. How do I know that this is not equivalent to learning those three different filters in the filter bank used to map d-dimensional node features into e-dimensional node features? What's the relationship between the number of features in the filter bank and the partitioning of the spectrum?\n\nThe fourth concern starts from the use of GNNs such as SuperGAT which involve non-convolutional graph filters. The frequency responses of these filters are ill-defined, thus comparing with non-convolutional GNNs, while great to show SotA is an unfair comparison in general, but in particular in an architecture that proposes a frequency interpretation of the results. A general framework to understand the differences between convolutional and non-convolutional GNNs can be found in\n\n[R6] E. Isufi, F. Gama, and A. Ribeiro, \"EdgeNets: Edge varying graph neural networks,\" IEEE Trans. Pattern Anal. Mach. Intell., 13 Sep. 2021, early access. [Online]. Available: https://doi.org/10.1109/TPAMI.2021.3111054\n\nIn this respect, I would like to note that ARMA graph filters are convolutional, as well as FIR filters (and IIR filters). Thus, a comparison with ARMA filters is fair in the context of graph convolutional neural networks.\n\nFor the fifth concern, I would like to note that the notion of partitioning the frequency spectrum is evocative of wavelet filter banks. A very nice tutorial on graph wavelets can be found in\n\n[R7] D. I. Shuman, \"Localized spectral graph filter frames: A unifying framework, survey of design considerations, and numerical comparison\", IEEE Signal Process. Mag., vol. 37, no. 6, pp. 43-63, Nov. 2020.\n\nIn particular, graph wavelets have been used in the context of GNNs to create graph scattering transforms\n\n[R8] D. Zou and G. Lerman, \"Graph convolutional neural networks via scattering,\" Appl. Comput. Harmonic Anal., vol. 49, no. 3, pp. 1046-1074, Nov. 2020.\n\n[R9] F. Gao, G. Wolf, and M. Hirn, \"Geometric scattering for graph\ndata analysis,\" in 36th Int. Conf. Mach. Learning, Long Beach, CA, 15-9 June 2019, pp. 1–10.\n\n[R10] F. Gama, J. Bruna, and A. Ribeiro, \"Stability of graph scattering transforms,\" in 33rd Conf. Neural Inform. Process. Syst. Vancouver, BC: Neural Inform. Process. Syst. Foundation, 8-14 Dec. 2019, pp. 8038–8048.\n\nI believe that the relationships with graph scattering transforms should be discussed, if not also included in the numerical simulations (in this respect, I would recommend the works by Wolf, who has studied the subject extensively, even proposing learnable variants of graph scattering transforms).\n\nThe sixth concern that I have is about computational complexity. It is stated that computing the k-lowest and k-highest eigenvalues are relatively inexpensive, reporting a cost of O(nkL) in addition to the GPR-GNN. I would suggest including the total cost of each of the main architectures to compare, and if possible, runtimes. As the authors are probably aware, the shift from conceptually interesting but impractical GNNs (Bruna et al, 2014) to computable ones (Defferrard et al, 2016) and the consequent boom of GNNs, is due to the avoidance of eigendecompositions. Going back to them, while interesting from a conceptual standpoint (and I do appreciate it), requires a much lengthier justification.\n\nMy seventh concern is that, unfortunately, I don't understand Theorem 1, and I would highly appreciate it if the authors can clarify it. My observation is that \\hat{h} is a superset of h, (i.e. if we set h_f = 0, we end up with h). It should then be evident that the error achieved by \\hat{h} should be lower or equal to the error achieved by h (i.e. h_f can only help... if it's useless, just set it to be equal to 0 yielding h). A clarification on what the authors tried to achieve with this theorem would be highly appreciated.\n\nMy eighth and last concern is the title. The inclusion of a polynomial filter is slightly misleading. There's nothing novel about it. However, the most interesting novelty, the spectrum partition, is completely omitted.\n\nSummary of concerns:\n\nThe paper is certainly interesting in the idea of partitioning the spectrum and learning different filters for different bands. I think this idea is worth publishing in ICLR, albeit not in its current form.\n\nA) The numerical experiments are extensive, but unfortunately, the choice of baselines is misguided. Comparisons with general FIR filters as well as ARMA filters are absolutely necessary. Comparisons with non-convolutional GNNs are optional, but I understand it from a SOTA perspective.\n\nB) A discussion on the relationship between the proposed method and scattering transforms is necessary, due to the nature of the spectrum partitioning and wavelets. While including numerical simulations comparing with scattering transforms would be very much welcome, it is indeed not necessary and maybe only left for future work.\n\nC) The interplay between the bank of FIR graph filters (i.e. the d x e bank of filters) and the partitioning of the spectrum should be explored: how do we know that these partitions cannot be learned in the bank of filters? choosing the intervals acts as a regularizer?\n\nD) The increase in computational complexity due to the computation of eigenvalues should be thoroughly explained and total computational costs should be reported for all architectures.\n\nE) I would appreciate it if the authors clarify my concern on Theorem 1.\n\nF) I believe the title could be improved to better reflect the paper's contributions.\n\nMinor comments:\n\n(1) is incomplete. The term for j=0 is missing, and as it has been discussed extensively above, the ability to learn the filter tap for the term j=0 is key for obtaining high-pass filters (even if k is small).\n\nPage 3, where it reads \"nod features computed via A^j X becomes indistinguishable\" should read \"node features computed via A^j X become indistinguishable\"\n\nThe i subindex in \\gamma in eq. (3) is boldfaced and I believe it shouldn't be.\n\nThe acronym GPR-GNN is mentioned for the first time in point 2 on page 5, but it has never mentioned what it is. Please, explicitly say that this refers to the Generalized Page Rank architecture of Chien et al.\n\nIn theorem 4.2, where it says 'learn-able' it should say 'learnable'.\n\nPlease, in the paragraph titled 'baselines' of the simulation section, add the corresponding references (I know these are in the supplementary material, but at least the references should also be included here)", "summary_of_the_paper": "This paper focuses on the task of node classification (semi-supervised learning) in heterophilic graphs. The authors identify that low-pass filter-based GNNs perform poorly on heterophilic graphs, precisely because they tend to smooth out differences in neighboring node features. Thus, they propose to look into filters capable of learning high-frequency content that can thus learn labels even if neighboring nodes do not share a label. In particular, the authors propose to learn different low-order polynomials for different parts of the spectrum.", "summary_of_the_review": "I find the idea of partitioning the spectrum to be very interesting. However, the idea is not fully explored and a lot of space is devoted to uninformative comparisons.\n\nI am currently assigning a score of 4, but I really see promise in this paper. So I'm willing to raise my score to 7 if my concerns are either addressed, or an explanation on why I have misinterpreted the paper is given.\n\nThe summary of the changes I expect is given in what follows:\n\nA) The numerical experiments are extensive, but unfortunately, the choice of baselines is misguided. Comparisons with general FIR filters as well as ARMA filters are absolutely necessary. Comparisons with non-convolutional GNNs are optional, but I understand it from a SOTA perspective.\n\nB) A discussion on the relationship between the proposed method and scattering transforms is necessary, due to the nature of the spectrum partitioning and wavelets. While including numerical simulations comparing with scattering transforms would be very much welcome, it is indeed not necessary and maybe only left for future work.\n\nC) The interplay between the bank of FIR graph filters (i.e. the d x e bank of filters) and the partitioning of the spectrum should be explored: how do we know that these partitions cannot be learned in the bank of filters? choosing the intervals acts as a regularizer?\n\nD) The increase in computational complexity due to the computation of eigenvalues should be thoroughly explained and total computational costs should be reported for all architectures.\n\nE) I would appreciate it if the authors clarify my concern on Theorem 1.\n\nF) I believe the title could be improved to better reflect the paper's contributions.\n\n--- 0 ---\n\nUpdate after the first round of reviews:\n\nI consider D, B, and F to be appropriately addressed.\n\nI have minor concerns on E.\n\nI still have major concerns about A and C, mainly with respect to the omission of graph convolutional filters upon the objection of overfitting.\n\nThank you very much to the authors for their time and effort in addressing my concerns. I will increase my score to 5.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": "a_xJtE6BvEW", "reviewer": "Reviewer_kGGE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found this paper enjoyable to read, and appreciated the authors' approach to the filter design problem.\nAlthough the goal of the paper is to develop methods for node classification with graph neural networks, its core ideas are rooted in graph signal processing.\nIn that regard, this work's contributions go beyond those of interest to the graph machine learning community, also finding interest for those in the graph signal processing community.\nHowever, I have significant concerns regarding the efficiency of the filtering approach, as well as the actual value of the theoretical analysis.\n\nAlthough I can vaguely see how the efficient variant of your filtering program works, I am not fully convinced of its actual efficiency.\nIn particular, evaluating the filter on the low-pass and high-pass components is still only defined in the spectral domain.\nTypically, although filters are easily defined in the spectral domain, it is more convenient to apply them in a spatial sense, via some low-order matrix polynomial.\nOf course, the polynomial splines used here do not yield filter functions that are represented as low-order matrix polynomials: this is the whole point of the paper, that piecewise polynomials of low-order can do better than global polynomials of high-order in many cases!\nIn that case though, filtering can only be done in the spectral domain.\nWhat I would like to see, then, is how these filters are actually implemented, in a way similar to Equation (1).\nAlthough you remark on how this can be done using Lanczos iteration, I would like to see a more precise specification of the filtering operation.\n\nI appreciated the statements of the analysis section, as it helped explain that piecewise polynomials are strictly more expressive than global polynomials in some sense.\nHowever, I do not think that your claims of superiority over regular graph filters are necessarily fair.\nI would like to draw attention to the claim following Corollary 4.2.1: \"the dimension of the space [of filters] increases significantly by using just two adaptive filters.\"\nWhile this is true, this downplays the complexity of implementing these filters.\nThe most notable property of normal graph filters of degree $k$ is that they are strictly dependent on the $k$-hop neighborhoods of each node (or $k+1$, depending on what shift operator is used).\nThis means that for low-order graph filters, it is easy to implement them on any given graph.\nThis is the reason why we like graph filters of low degree: because they are localized!\nHowever, in the proposed approach, you claim to also be using low degree polynomials, while achieving significantly higher expressivity.\nWhile it looks like this is the case on the surface, I am not convinced that this actually translates into anything useful.\nA graph filter of degree $k$ applied to the low and high-pass partitions of the spectrum must only operate in the spectral domain: its spatial implementation will almost certainly not be localized to $k$-hop neighborhoods.\nIn this sense, it is almost obvious that your filters will be more expressive, since they are indirectly using much larger neighborhoods of the nodes, merely having the restriction of being implementable as low-degree polynomials in a particular subset of the spectrum.\nThis ties back to my concerns about the implementation of these filters: what does this look like in the spatial domain?\nWhat are the localization properties?\nThe current explanation obscures these properties.", "summary_of_the_paper": "This paper considers the problem of designing polynomial graph filters for use in graph neural networks.\nThe motivation for doing so stems from the notions of homophily and heterophily in labeling the nodes of a graph: the former requiring the use of low-pass filters, and the latter requiring the use of high-pass filters.\nHere, the authors consider the design of spline polynomials for spectral-domain filtering, as opposed to the typical ``global'' polynomials used in graph filter design.\nThat is, they first partition the spectrum of the graph matrix into low-pass, band-pass, and high-pass components, learn polynomials over each partition, and then combine these polynomials, enforcing continuity at the boundary of each interval via a penalty function.\n\nOf course, doing this requires a full eigendecomposition of the graph matrix, which has high complexity.\nTo ameliorate this issue, the authors propose an efficient variant of their spline spectral filter.\nThis approach only uses a coarse partition of the spectrum, rather than using the full eigendecomposition.", "summary_of_the_review": "To summarize: I am currently under the impression that the apparent complexity-expressivity tradeoff is not as significant as the authors claim.\nAlthough it is apparent that that filtering operations are implemented as low-order polynomials over a partition of the spectrum, their piecewise nature completely destroys the locality inherent to low-degree graph filters, which is why such filters are useful in the first place.\nThis is mere speculation on my part, but I suspect that this method would, for instance, fail to generalize well to graphs other than the one it is trained on, even if the structure is somewhat similar.\nBased on these concerns, I do not recommend the acceptance of this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8y9NkXMOq0y", "reviewer": "Reviewer_fpGz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1) It is natural to utilize the piece-wise polynomial to learn a graph filter on different subsets of the spectrum.\n2) The authors demonstrate that the sum of the polynomials approach is more accurate than a single polynomial at approximating a latent optimum filter and that the set of learnable filters is wider than that of GPR-GNN.\n3) The experiments demonstrate that PP-GNN is capable of learning more complicated filters, such as capturing complex shapes on Squirrel and Chameleon, outperforming other advanced GNN models.\n\nWeaknesses:\n1) As the author discussed in the paper, PP-GNN cannot be scaled to big graphs due to the complexity of the eigendecomposition, and therefore must make a trade-off between performance and efficiency.\n2) Once we know the eigen components at the top and bottom of the spectrum, we can alter the eigenvalues in a variety of ways. Additional research is needed to determine whether a polynomial base is the best choice for filter learning.\n3) PP-GNN has a large number of hyperparameters (the number of partitions, the order of the polynomial filter, the number of eigenvalues, and so on), and the code demonstrates that the polynomial initialization for each partition has a separate set of hyperparameters as well. I'm concerned that a large number of hyperparameters will degrade the model's generalizability and result in considerable tuning work.\n4) The implementation performs SVD on the node feature matrix, which is not discussed in the paper. In particular, the time cost for this operation should be discussed.\n5) There are several related works that are missing, including ARMA[1], AdaGNN[2], and BernNet[3], all of which are capable of learning graph spectrum filters.\n[1] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. TPAMI, 2021.\n[2] Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Graph neural networks with adaptive frequency response filter. In CIKM, 2021.\n[3] Mingguo He, Zhewei Wei ,  Zengfeng, Hunang, and Hongteng, Xu. BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. In NeurIPS 2021.\n", "summary_of_the_paper": " This paper proposes PP-GNN, a novel graph neural network that learns multiple adaptive polynomial filters acting on different subsets of the eigenvalues. The authors combine GPR-GNN with existing efficient algorithms for generating top and bottom eigen components to reduce the expensive complexity of eigendecomposition. They show that the piece-wise polynomial method can approximate a latent optimal filter better than a single polynomial in theory. ", "summary_of_the_review": "The paper contains some interesting ideas, as evidenced by the experimental results. However, the theoretical depth and novelty may not be enough to meet ICLR's standards.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to apply a piece-wise polynomial filter on the spectral corresponding to the graph convolution to enhance the model expressivity of graph neural networks. The effectiveness of the proposed model is investigated through numerical experiments and it was shown that the method achieves fairly nice performances.  

This paper gives a natural extension to the usual adaptive Generalized PageRank approaches to more expressive piece-wise polynomial filters. However, the reviewers are not enthusiastic on this paper. This is mainly because of the following concerns: (1) Since it requires diagonalization of the aggregation operator, it requires much more computational burden than the usual polynomial filters, which prevents the method from being applied to data with much more large size. (2) The choice of the filter could be more investigated, in particular, the complexity-expressivity trade-off (in other words, bias-variance trade-off) could be discussed more, for example, by theoretical work.  

In summary, the paper seems not to be well matured for being published in ICLR conference.
Decision: Reject