Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################
Summary:

The paper proposes a parametric form for a matrix representation of a graph to be used as a building block within graph neural networks (GNNs). In essence, people use different normalized versions of the adjacency and Laplacian matrices within GNNs. The authors, in turn, propose a generic parametrized version that encompasses those normalizations and that can be learned from data.

##########################################################################
Reasons for score: 
 
My overall evaluation is slightly positive. Although the methodological contribution is minor, my positive recommendation is based on the wide applicability of the simple idea proposed. The parametric graph shift operator can be readily used in existing applications of GNNs possibly boosting performance.
 
##########################################################################

Pros: 

1. Simple contribution explained in a straightforward manner. This can help adoption by practitioners.

2. Numerical experiments rightly illustrate the value of the contribution.
 

##########################################################################

Cons: 

1. There is no clear justification for the specific parametric form in (1), other than it can recover existing choices of the GSO. This, of course, can be obtained with other conceivable parametrizations. The authors try to justify this by saying that (1) is the "most general affine form of the adjacency matrix", but this does not seem to be a rigorous statement. Most general in what sense? What is the space of all affine forms of matrices?

2. The value of the theoretical analysis is unclear. The paragraph after Theorem 1 is supposed to highlight the value of having real eigenvalues. The authors mention "without having to worry about complex values", worrying in what sense? Why would it be difficult to implement the examples at the end of page 4 if the eigenvalues would be complex? The authors then mention the difficulty of doing spectral clustering with complex eigenvalues, but the connection with the ongoing discussion is quite loose.

3. Similarly, the value of Theorem 2 is unclear to me. Why are these bounds useful? The discussion after Theorem 2 again tries to enlighten in that direction, but it falls short.
  

#########################################################################

Some typos: 
(1) In Remark 1, "absence of an edge" should be "existence of an edge".

#########################################################################

Edit after author response: We thank the authors for their response to my concerns and those of other reviewers. I have updated my score from 6 to 7 based on their changes.
review_title: A simple but useful idea

final_score: rating: 7: Good paper, accept
review_content: The authors consider the problem of learning a parametrized graph shift operator (or message passing operator) in the context of graph neural networks. They consider a family of GSO (that they name PGSO) based on seven scalar parameters, and show that it includes most commonly used operators such as the adjacency matrix or the laplacian. The spectral properties of the PGSO are analyzed. Finally, some empirical results are provided demonstrating the PGSO as a drop-in replacement for standard GSO in GNN architectures.

Graph neural networks have gathered a large amount of interest in the past years, and found widespread use in adapted problems. However, recent analyses have shown that typical architectures may have limited expressiveness (e.g. bounded by the WL test). The paper is overall well-written, and proposes a method which could be of interest to practitioners. On the other hand, the paper has some minor weaknesses, in that the proposed parametrization is redundant with some existing techniques (e.g. $m_3$ corresponds to residual connections, which are widely used), and, given the simplicity of the proposed method, a more comprehensive empirical evaluation could be beneficial. Additionally, the proposed operator is still restricted to 1-neighborhoods, and hence cannot by itself solve the expressiveness problems encountered by graph neural networks. This lack of expressiveness, in conjunction with the mixed empirical results (which show overall good performance improvement but with overlapping error bars), potentially lower the impact of this contribution.

Given the potential interest this method could hold for practitioners, I believe that the paper could be substantially improved by making the empirical evaluation more comprehensive. In particular, a more comprehensive analysis of the training dynamics (as in figure 1) as well as the effect of initialization would give a clearer picture of the effect of the PGSO in practice. Specifically, one might wonder about the importance of initialization for the $m_2$ parameter, given that it controls the influence of the edge information, and for example whether it is possible for it to change sign during training. Perhaps an informative experiment could be to initialize the PGSO at different commonly used GSO parameters (e.g. adjacency, Laplacian, normalized Laplacian), and observe how such initialization affects performance.

==============================

Edit after author response: we thank the authors for their response and providing some more empirical information. Overall I feel that this paper presents a neat idea that could be of interest to some people in the community, and I have modified my score from 6 to 7. It would be great for the authors to discuss the importance of initialization, as in particular, it seems to me that the sign of $m_2$ can never change  (from its initial value), indicating perhaps that practitioners should try initialization at either and select the better performing model.

review_title: An interesting idea with some promising empirical results which should be made more comprehensive

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper describes a parameterized family of "graph shift operators", defined for any graph on n vertices as an n x n matrix where the i,j-th entry is 0 whenever edge (i,j) does not appear in the graph. The paper studies some spectral properties of the parameterized family, and experiments with using them as components of graph neural networks.

This paper appears to me to be a hammer in search of a nail. It was not clear what problem is meant to be solved here. Nor does it seem that the topic is fundamental, scientific investigation. 

The paper is generally poorly written and was difficult to follow. I suspect much of that relates to the lack of clarity in the problem. However, the writing is also unfocused at the paragraph level.

In short: this paper needs substantial work before it's ready for publication. 
review_title: Not ready for publication

final_score: rating: 7: Good paper, accept
review_content: The paper proposes a parameterized graph shift operator (PGSO) as a replacement of fixed, hand-picked GSOs for application to GNN architectures and the experiments illustrate that PGSOs automatically adapt to the regularized GSOs for different settings. The contribution is of interest to the ML community as existing studies show significant improvements in performance of GNNs by using certain GSOs in specific contexts and therefore, a data driven characterization of GSO helps introduce adaptivity to the network representation in GNNs.

Pros: The paper is well written and easy to follow. The theoretical and empirical spectral analysis of PGSO reveals its applicability to many existing GNN architectures. The experiments are sufficient to illustrate the utility of using PGSO over a constant GSO for different settings. 

Cons: 
1. Remark 1 seems to contradict Definition 1. Do the authors mean 'presence' and not 'absence' of an edge in Remark 1?

2. An explicit discussion on how PGSO parameters are learned or updated in every epoch is missing. 

3. The authors compare the final accuracy results of GNNS with PGSOs and those with constants GSOs. The evolution of accuracy with the number of epochs for some of these results will help evaluate the cost of learning the parameters of PGSOs. 
review_title: Parametrized GSOs in GNNs

Meta-review: Summary:
The authors observe that a range of Laplacian-type operators used in
graph neural networks can be embedded in a parametric family, so that
the precise form of the Laplacian used can be determined by the
learning process. Empirical evaluation and some (limited) theoretical
analysis are provided. 

Discussion:
The authors have provided detailed replies and also additional
experiments. That has addressed major concerns, and most reviewers now
agree the paper is good. One reviewer is more skeptical, mostly
regarding presentation. I agree with some of the points raised in this
regard, but see them as less of an issue - I would consider the
presentation improvable, but acceptable.

One weakness I should mention is that the two theorems provided are
frankly trivial. I appreciate this is 'only' a conference
submission,
but I would nonetheless call the fact that symmetric matrices have real
eigenvalues (theorem 1) an observation, not a result. 
That similarly holds for any direct consequence
of Gershgorin's theorem (theorem 2). The entire page used to state this could perhaps be put to
better use for additional empirical results.


Recommendation:
The program committee (the AC and program chairs) were hesitating about this paper but decided to recommend acceptance. The idea is neat and simple, presentation and empirical evaluation are fine, if improvable (we strongly recommend the authors to invest time). What is phrased as theory is trivial, but also admittedly not the main focus of the paper. 



Decision: Accept (Poster)