Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes BernNet, a novel graph neural network with theoretical support that provides a simple but effective scheme for designing and learning arbitrary graph spectral filters. The key property of BernNet is that 1) any valid polynomial filers that maps [0,2] to [0,1] can always be expressed by a BernNet, and 2) the filters learned by our BernNet are always non-negative. The experiments demonstrate that BernNet can learn complex spectral filters, such as band-rejection and comb filters, and it achieves superior performance in real-world graph modeling tasks. Overall, the motivation is clear and the idea is interesting. Technical contributions are clearly shown with both theoretical and empirical evidence. 
main_review: This work is mostly well-written with informative content and new ideas that are worth publishing.  

Strengths:

1. The use of the Bernstein basis to approximate an arbitrary graph filter is an exciting idea. 

2. The Bernstein basis has higher interpretability and controllability than the Chebyshev basis since its coefficients directly match the filter values. 

3. The authors demonstrate that any non-negative polynomial filter can be expressed using a non-negative linear combination of the Bernstein basis, distinguishing Bernstein from other learnable GNNs (e.g. ChebNet, GPR). 

4. The experiments reveal some intriguing findings. BernNet, for example, learns an MLP from the Actor dataset, which seems to outperform other advanced GNN models.

Weakness:

1. The technical section of the paper is relatively dense, which may be difficult for non-experts in GNN to understand. 

2. From the standpoint of graph optimization, the authors justify the non-negative feature of polynomial filters. While this motivation makes perfect sense, it appears that a valid filter has to be non-negative by definition.

limitations_and_societal_impact: Yes, the authors addressed all these aspects.

Describe the limitations of your work? [Yes] BernNet is quadratic dependent on K.

Any potential negative societal impacts of this work? [Yes] see Section 7 [Broader Impact]
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new graph neural network (GNN) architecture whose convolutional layer is capable of learning spectral graph filters of arbitrary characteristics via Bernstein approximation. Under the constraint of positive filter response, the authors show that the polynomial which approximates the solution to a generalised graph-based optimisation necessarily has the form of a non-negative linear combination of Bernstein basis, which justifies the proposed GNN convolutional layer. Experimental results demonstrate that the proposed scheme can learn complex filters and achieve competitive results on a number of benchmark datasets.
main_review: This paper proposes a new GNN architecture following the so-called spectral designs. Compared to spatial designs (e.g. message-pass neural networks), spectral designs have been arguably less extensively studied, and in this sense the paper adds value to the GNN literature. The proposed graph convolutional layer involves a filter based on Bernstein polynomial approximation and has several advantages: 1) it guarantees a non-negative filter response; 2) it can adapt to complex filter characteristics; 3) it is theoretically justified via a graph-based optimisation problem. Despite the rich literature, these are interesting aspects that enrich the design of GNN architectures.

The paper is generally technically sound and ideas are presented in a clear and coherent manner. The illustrations of the filter response of various types are helpful for understanding the advantage of the proposed approach.

My main concern is that the advantages of the proposed approach over existing methods that can learn flexible spectral filters (e.g. ChebNet) should be better justified. Theoretically, the authors should explain in more depth why the Bernstein polynomial approximation is potentially better than the one by Chebyshev polynomials. Empirically, in addition to performance metrics, it would be good to compare the learned filters from BertNet and ChebNet (among others) so that their differences can be made more clear.

Another major issue is that, to increase the expressivity of the proposed filter we need to increase the order of the polynomial K, which increases the computational complexity quadratically. This can in certain scenarios be a significant shortcoming compared to approaches such as ChebNet whose complexity is linear with respect to K.

Overall, I am slightly inclined to recommend acceptance due to the positive aspects of the paper mentioned above, but I would recommend the authors address some of the issues raised in the review during rebuttal.

Below are additional comments that may help further improve the quality of the paper:

The statement “none of the existing work supports designing arbitrary spectral filters” is not precise as architectures such as ChebNet can do that in theory.

I am not sure it is the negative spectral response that leads to the over-smoothing of GNNs as claimed by the authors. To me these seem to be separate issues (unless a definitive link can be made which would be welcome).

The claim that some existing GNNs may not satisfy Constraint 3.1 is in my view not precise as it depends on the range of spectrum. For example, the GCN filter would guarantee non-negative filter response if the eigenvalues are upper bounded by 1, which is the case for scaled or shifted normalised graph Laplacian (which are commonly used in the literature, e.g. in ChebNet). This corresponds to one of the main novelties of the paper and needs to be explained in more depth. Related to a comment above, it would be good to compare the learned filters using BernNet and baselines to demonstrate this point.

The statement “these methods mainly focus on designing low- or high-pass filters…” is not entirely precise. In theory, as long as the architecture can adapt to data characteristics (e.g. non-smoothness) they can learn flexible filters beyond low- or high-pass ones.

In 5.1, the formulation of the problem as a regression problem should be explained more clearly (e.g. what do the authors means by using “a mask to cover the edge nodes”?).

Some recent work on learning filters of various spectral characteristics should be discussed in Related Work, for example:
- https://arxiv.org/abs/2011.10988
- https://arxiv.org/abs/2104.12840

------post-rebuttal------

I thank the authors for their response and clarifications. I would suggest that the authors further improve their paper based on these discussions. One thing I am not sure about is the authors' claim that it would not be easy to check the filter response from ChebNet. In my view this should be possible to do (see for example a recent work https://arxiv.org/abs/2003.11702) and can further strengthen the paper.

limitations_and_societal_impact: Limitations are mainly discussed from the perspective of computational complexity for which running time results have been reported and discussed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose BernNet, which uses Bernstein polynomial basis to learn graph filters. From extensive experiments and theoretical reasoning, the authors demonstrate that BernNet is favored over baselines with a similar idea such as GPR-GNN and ChebyNet.
main_review: Strengths:

(+) The theoretical motivation of using the Bernstein basis is neat and inspiring.

(+) The synthetic experiments on the ability of BernNet to learn arbitrary graph filters well support its validity.

(+) The paper is well written.

(+) The higher computational complexity of BernNet over simpler models such as GPR-GNN is clearly stated. So, the performance-complexity trade-off is clear to the readers.

Minor Weakness:

(-) Do not compare with the other popular polynomial basis such as Chebyshev (different from ChebyNet), Legendre. I understand that they might not have the same good properties as Bernstein, but some synthetic experiments would be appreciated.

Detail comments:

Overall, I like the main idea of this paper. The motivation of why we should use Bernstein basis is clear and neat. The synthetic experiments on learning filters for images are interesting and convincing. Although the model itself just changes monomial basis in GPR-GNN to Bernstein basis, the idea and theoretical reasoning behind it is profound.

Still, I think some minor things can further improve the current manuscript. The authors clearly show that it is reasonable to consider the non-negative constraint and thus Bernstein basis becomes a great choice. However, when it comes to polynomial approximation the other popular polynomial basis should also be considered, such as Chebyshev and Legendre. Note that using Chebyshev basis in GPR-GNN is not the same as ChebyNet. I think the current manuscript can be even more solid if such an experiment can be done.

Originality: Great. Although the model itself does not differ a lot, the idea and motivation behind it are inspiring.

Quality: Both theoretical reasoning and experiments are convincing.

Clarity: The paper is well written. Maybe the importance of the non-negative graph filters section can be further emphasized.

Significance: This work has moderate significance.

limitations_and_societal_impact: Limitations on computational complexity are addressed.
review_title: null

Meta-review: The paper proposes a new algorithmic approach for GNNs, and is backed up with both theory and empirical validation. The reviewers are all generally positive and in agreement of its important contributions.
Decision: Accept (Poster)