Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 
#### **Post Rebuttal**
I'm afraid the authors failed to answer my main question regarding the results and the applicability of their proposed approximation.

Therefore, I decide to keep my score.

---
#### **Contribution Claims** 
The paper vouches for the use of GNTK as a strong method for graph learning combining good properties of kernels and GNNs. However, it raises the issue of time complexity for calculating the kernel scaling with $O(N^4)$, and addresses it by suggesting two techniques to gain speed up. The proposed techniques are based on matrix decoupling, which simply improves complexity, and matrix sketching which approximates the correct kernel (in probability).
The authors further present a theoretical result that similar generalization guarantees, as attributed to the exact GNTK, are achieved with their approximation.

**Strengths** 
- The paper gains a major speed up in GNTK calculation with no harm to performance (*up to a clarification regarding the reported results. See first item in weaknesses section) 
- The method generalization properties are analyzed and shown to be preserved.
- Although the paper is packed with lots of details, the flow of the paper allows the reader to pick upon the general ideas presented in the paper.

**Weaknesses** 
- *Results* - I have concerns regarding the reported performance in Table 2. I find it quite uncanny that the numbers are *exactly* the same as achieved by exact GNTK, although the proposed method is an approximation which also utilizes a stochastic component. In case I misunderstood, I would kindly ask the authors to clarify this point. 
- *Discussion compared to GNTK* - A discussion on how the exact GNTK generalization bound compares to the approximate one is missing.
- *Related work* - The paper does not explain and mention previous and relevant uses of matrix sketching (either in deep learning or kernel methods in general) which makes it hard for someone who is not familiar with the term to understand solely from the paper what it means. It is also unclear how innovative the use of it is. 
- *Experimental setting* - Regarding the evaluation on social datasets, it is mentioned that a degree feature was added as an input. Is it true for the other baselines as well? 
- *Missing convincing use-cases* - As the paper claims to gain speed up making GNTK scalable to larger datasets, I would have liked to see the performance both in time and accuracy of the proposed method. 

#### **Decision Recommendation**
For now, I suggest to reject the paper.  
I think that it is interesting and valuable but feels that it needs to be solidified. 
Upon clarification of the questionable results I would consider changing my decision. 

#### **Other Comments**
- Typos - the paper contains many typos. e.g, Theorem 4.1 "...n graphs n graphs..." repeating twice.  








review_title: Interesting but misses convincing evaluation and has questionable results. 

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper, the authors propose two techniques to speed up the training of the graph neural tangent kernel, by matrix decoupling and sketching. Experiments are convincing.

We find the title of the paper inappropriate, because the paper only consider the  graph neural tangent kernel.

In general, the paper is difficult to read because many important parts are only available in the appendices.

There are some spelling and grammatical errors that can be easily identified and corrected, such as "The descriptions in this section is".

----------------
Following the authors' response,  we have updated our rating accordingly considering the following facts: the authors didn't make any change to the paper within the rebuttal, while they had the possibility in response to several questions. They didn't address even our simplest concerns, about the title being inappropriate. They still want to keep the title too general, while the paper considers only graph neural tangent kernel. Even if the latter is equivalent to infinitely wide multi-layer GNN, it is still a very special case. Moreover, many of the major issues raised by the other reviews were not addressed.
review_title: A good paper on accelerating graph neural tangent kernel

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes to apply Neural Tangent Kernel to GNN to improve training. This is a good initiative to apply state of the art methods to GNN training which would interest researchers and practitioners in the community. However, the novelty introduced in the paper low since the authors directly apply NTK to GNN.

Pros:
a.) A good point of the paper is the compressive experiments and theoretical guarantees which make the paper complete and useful to the community. The paper is also well written.

b.) Good performances have been achieved from experiments with many benchmark datasets


Cons:
a.) My main issue with the paper is its lack of novelty. It is a good idea but the authors do not provide any new ideas for either NTK and GNN. The paper shows significant performance improvement with the proposed method, however, it is somewhat understandable. 

b.) More details about the experiments would be helpful. Can the authors give details about varying dimensions of the sketch matrices and its effect on speed and accuracy?

c.) This paper focuses on using sketch matrices based on Alon et al.. It would be more informative if the authors compare using other sketching methods such as Gaussian matrices and sampling methods.
review_title: Good idea but lacks novelty

Meta-review: While the author response clarified some concerns, it could not convince the reviewers that the current version of the paper should be accepted for publication at ICLR. 

Decision: Reject