We thank the reviewer for their reply. However, we would like to point out that this post was made very close to the deadline and during the authors' nighttime. A proper reply to the reviewer takes several hours. We provide a reply to the best of our ability given the limited time.
We want to re-iterate the fact that the corrected convolution is not ours. We mention this in our first reply above and we point this out in lines 348 to 350. This idea is already implemented in widely cited practical papers [ref line 512 (ICLR 2020)]. We provide a rigorous analysis.
> In the referenced work [ref line 443, Keriven: Not Too Little, Not Too Much], ... task.
The result that the reviewer claims seems to be Theorem 2. We would like to clarify what is proved in the main theorem of this paper. The authors don't provide a non-asymptotic analysis as we do in our paper. They only provide an existential result. They prove that 1 convolution can be better, under specific assumptions, than 0 convolutions. They also prove that 1 convolution is better than infinite convolutions. This implies that there might exist a $k^* \ge 1$ which is optimal. However, they never rigorously analyze the performance of convolution for $k>1$ and $k<\infty$. In fact, the authors mention in their paper that "In the next section, we also derive an intuitive expression for $R(k)$ (although without rigorous proof), which we observe to match the numerics quite well."
We would like to point out that it is technically extremely challenging, and requires a whole different set of methodology, to achieve non-asymptotic analysis as we do in our paper, and we hope the review appreciates it.
> Can this study be extended ... in the limit becomes worse?
We will reply to this question by focusing on other tasks within node-classification, since node-classification is the focus of our paper. By dominating eigenvector we assume that the reviewer implies the second or higher eigenvectors. The dominant (first) eigenvector does not hold meaningful classification information, therefore removing it helps. We prove this in our Theorems 4.1 and 4.2. Also, Fig 3 shows that removing the top eigenvector allows the model to have better performance as the number of convolutions increases.
We interpret the reviewer's comment as a question about why the performance decreases for $k$ larger than 1 or 2. The reason is not because we remove the dominant (first) eigenvector. As we point out this is beneficial, since the first eigenvector holds no information about the classes. The reason is that in the particular real data which we used there are eigenvectors with small eigenvalues which might contain meaningful information. Asymptotically, the corrected convolution, which we repeat is not our idea, see comments above, might miss the information from such eigenvectors. Intuitively, this could be the case in a graph where there are small communities within larger communities in the given graph structure. The top eigenvectors are likely to be correlated with the larger communities. To capture the information from small eigenvalues, a different convolution is needed which filters eigenvectors in an appropriate way. However, we would like to point out again, that the first eigenvector will be filtered out in this case too since it's not meaningful.
To analyze such a scenario, we would have to change our random data model. That's because in the current data model the first few top eigenvectors (excluding the first one) are the most meaningful ones, and eigenvectors for small eigenvalues are just noise. Technically, a non-asymptotic spectral analysis could also work in this hypothetical new data model. The corrected convolution in our paper is likely to lose performance as $k$ increases. A different convolution would be needed to better capture the information of eigenvectors of small eigenvalues. This study is indeed interesting, however, we would like to mention that it is far from the goal of our present paper.
We would be happy to mention the above in our paper.
> Convolution: ... in this work clearer.
We will make sure to clarify this in our paper. We come from a graph neural network background where this definition is ubiquitous and we didn't explicitly specify it as a definition.
> Corrected convolution: ... can be more "correct".
We chose the word corrected since in the literature of statistical community detection (no node features), the word is often used for modified versions of the original SBM, for example: B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E 83 (2011). In this case, the fact that one does degree "correction" does not necessarily mean that it is a universal correction for any possible problem. It's a name which makes sense within a specific context. We can offer to change the title to "Analysis of Eigen-Corrected Graph Convolutions" if the reviewer believes that this is more specific.