Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
main_review: Strengths:
1) It is natural to utilize the piece-wise polynomial to learn a graph filter on different subsets of the spectrum.
2) 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.
3) 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.

Weaknesses:
1) 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.
2) 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.
3) 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.
4) 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.
5) 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.
[1] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. TPAMI, 2021.
[2] Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Graph neural networks with adaptive frequency response filter. In CIKM, 2021.
[3] Mingguo He, Zhewei Wei ,  Zengfeng, Hunang, and Hongteng, Xu. BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. In NeurIPS 2021.

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of designing polynomial graph filters for use in graph neural networks.
The 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.
Here, the authors consider the design of spline polynomials for spectral-domain filtering, as opposed to the typical ``global'' polynomials used in graph filter design.
That 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.

Of course, doing this requires a full eigendecomposition of the graph matrix, which has high complexity.
To ameliorate this issue, the authors propose an efficient variant of their spline spectral filter.
This approach only uses a coarse partition of the spectrum, rather than using the full eigendecomposition.
main_review: I found this paper enjoyable to read, and appreciated the authors' approach to the filter design problem.
Although 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.
In 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.
However, I have significant concerns regarding the efficiency of the filtering approach, as well as the actual value of the theoretical analysis.

Although I can vaguely see how the efficient variant of your filtering program works, I am not fully convinced of its actual efficiency.
In particular, evaluating the filter on the low-pass and high-pass components is still only defined in the spectral domain.
Typically, 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.
Of 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!
In that case though, filtering can only be done in the spectral domain.
What I would like to see, then, is how these filters are actually implemented, in a way similar to Equation (1).
Although you remark on how this can be done using Lanczos iteration, I would like to see a more precise specification of the filtering operation.

I appreciated the statements of the analysis section, as it helped explain that piecewise polynomials are strictly more expressive than global polynomials in some sense.
However, I do not think that your claims of superiority over regular graph filters are necessarily fair.
I 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."
While this is true, this downplays the complexity of implementing these filters.
The 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).
This means that for low-order graph filters, it is easy to implement them on any given graph.
This is the reason why we like graph filters of low degree: because they are localized!
However, in the proposed approach, you claim to also be using low degree polynomials, while achieving significantly higher expressivity.
While it looks like this is the case on the surface, I am not convinced that this actually translates into anything useful.
A 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.
In 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.
This ties back to my concerns about the implementation of these filters: what does this look like in the spatial domain?
What are the localization properties?
The current explanation obscures these properties.
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.
Although 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.
This 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.
Based on these concerns, I do not recommend the acceptance of this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: 
Strength
- The proposed architecture is well-motivated.
- The ablation study is extensive.

Weakness
- 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].)
- 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?
- 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.

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

In 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.

However, 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.

In 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

[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.

[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.

Given 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.

An FIR graph filter is a mapping H(S) between graph signals given by

H(S) = \sum_{k=0}^{K} h_k S^k

where 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.

At 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.

It'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).

Now, 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.

At 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.

My 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.

When 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

H(X;S) = \sum_{k=0}^{K} S^k X H_k

where 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:

[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.

Once we have the FIR graph description for node features

H(X;S) = \sum_{k=0}^{K} S^k X H_k

It is immediate to see many of the other architectures as imposing different constraints on this general definition, i.e.

GCN: K = 1, S = normalization(I+A), H_0 = 0, H_1 = learnable

SGC: K chosen, S = normalization(I+A), H_k = 0 for k < K, H_K = learnable

GPR-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)

As 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.

Thus, 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

H(X;S) = \sum_{k=0}^{K} S^k X H_k

ChebNets 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.

The 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.

While this is true, the reasons to propose the spectrum partition are not entirely justified.

On the one hand, it has been noted that even K=1 is enough to learn a high-pass filter.

On the other hand, higher values of K allow for sharper frequency transitions, which may or may not be useful.

The 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.

However, it is known that the use of ARMA graph filters lead to sharper transition with a fewer number of exchanges

[R4] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein, "CayleyNets:
Graph convolutional neural networks with complex rational spectral filters," IEEE Trans. Signal Process., vol. 67, no. 1, pp. 97–109, Jan. 2019.

[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

This 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.

The 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?

To 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?

The 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

[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

In 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.

For 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

[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.

In particular, graph wavelets have been used in the context of GNNs to create graph scattering transforms

[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.

[R9] F. Gao, G. Wolf, and M. Hirn, "Geometric scattering for graph
data analysis," in 36th Int. Conf. Mach. Learning, Long Beach, CA, 15-9 June 2019, pp. 1–10.

[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.

I 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).

The 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.

My 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.

My 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.

Summary of concerns:

The 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.

A) 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.

B) 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.

C) 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?

D) 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.

E) I would appreciate it if the authors clarify my concern on Theorem 1.

F) I believe the title could be improved to better reflect the paper's contributions.

Minor comments:

(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).

Page 3, where it reads "nod features computed via A^j X becomes indistinguishable" should read "node features computed via A^j X become indistinguishable"

The i subindex in \gamma in eq. (3) is boldfaced and I believe it shouldn't be.

The 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.

In theorem 4.2, where it says 'learn-able' it should say 'learnable'.

Please, 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_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.

I 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.

The summary of the changes I expect is given in what follows:

A) 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.

B) 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.

C) 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?

D) 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.

E) I would appreciate it if the authors clarify my concern on Theorem 1.

F) I believe the title could be improved to better reflect the paper's contributions.

--- 0 ---

Update after the first round of reviews:

I consider D, B, and F to be appropriately addressed.

I have minor concerns on E.

I still have major concerns about A and C, mainly with respect to the omission of graph convolutional filters upon the objection of overfitting.

Thank you very much to the authors for their time and effort in addressing my concerns. I will increase my score to 5.
review_title: null

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