Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the graph neural network structure is integrated into the GP framework to construct a kernel function with graph structure, and the low-rank approximation method is used to deduce the efficient training and inference method of GP, aiming to improve the performance and efficiency of graph structure data classification and regression.
strength_and_weaknesses: Strength:

1. The idea is interesting and somewhat novel.
2. The manuscript is clear and easy to read.
3. The experiments validate the effectiveness of the proposed method.

Weaknesses:

1. Why does integrating graph neural network structure into GP framework improve the performance compared with GNN? In my opinion, one of the main advantages of GP is the use of kernel functions like RBF, which can approximate the nodes of infinite element network, and the kernel functions used here are still based on the inner product of mapping functions.

2. The authors emphasize that the proposed method is suitable for semi-supervised scenarios, but does not give the reason and the specific algorithm of semi-supervised learning. If it is supervised learning, whether the proposed method still has the same advantage?

3. Can the authors explain the trend of the curves in Figure 3?


clarity,_quality,_novelty_and_reproducibility: The paper is mostly well-organized. The techniques are solid and correct.
summary_of_the_review: A novel idea and implementation of combing GP and graph neural network.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The goal of this study is to attack the semi-supervised learning problem for graph-structured data. The paper focus on bridging the gap between GNNs and the limiting GPs by deriving the covariance kernel that incorporates the graph inductive bias as GNNs do.  More specifically, the paper has shown that the GP can be derived as a limit of the GCN when the layer widths tend to infinity and demonstrated the kernel universality and the limiting behavior in depth. In addition, the paper also develops an efficient computational algorithm for posterior inference on large-scale data.
strength_and_weaknesses: Overall, the paper is well motivated. The use of a real data set is a huge strength of the paper. In particular, I would also like to commend the authors on the crystal clear exposition and writing throughout the paper. The proposed method and theory are clearly presented and easy to follow. 

My main concern is the originality of establishing connection between GCNs and GPs. I have seen a number of previous studies which reached a similar conclusion. For example:
- https://arxiv.org/pdf/1711.00165.pdf
- https://arxiv.org/pdf/2002.12168.pdf
- https://proceedings.neurips.cc/paper/2019/hash/5e69fda38cda2060819766569fd93aa5-Abstract.html

It would be better for the authors to clarify the differences and highlight their main theoretical & methodological contributions compared to the existing studies. Also, the low rank approximation for scalable computation hinges on the Nystrom approximation of matrix K, which is widely-used in the GP literature. Therefore, in my opinion, the algorithmic contributions are incremental (or limited).

Given that I believe the authors would need to effectively address the above questions and the totality and generality of the contributions to be not significant enough to warrant publication at this stage.
I hope the authors may find these high-level comments helpful in thinking about the next steps for their paper. 
clarity,_quality,_novelty_and_reproducibility: The paper is cleary written and well presented. 
summary_of_the_review: See above
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper defines GCN-inspired kernels by deriving GP as the limit of GCN. The authors present some theoretical results such as universality and develop a scalable posterior inference method based on low-rank approximation of covariance matrix. The effectiveness of the proposed method is demonstrated using multiple bench mark datasets.
strength_and_weaknesses: S1. The authors derive GCN-inspired kernels by defining GP as the limit of GCN.

S2. The theoretical guarantees such as universality are thoroughly discussed.

S3. A practical inference algorithm is also presented, whose effectiveness is verified on real-world datasets.

W1. There is no discussion of important related studies, graph Gaussian processes [R1]. Can you please explain in detail the relationship with the proposed method? Please add to the baseline method if necessary.

[R1] Yin Cheng Ng et. al., Bayesian Semi-supervised Learning with Graph Gaussian Processes, NeurIPS, 2018.
clarity,_quality,_novelty_and_reproducibility: - The manuscript is readable.
- Technically sound.
- The proposed formulation seems novel, but some related works are missing.
summary_of_the_review: Connection of GP and GCN is interesting. The proposed formulation is reasonable and the approximation method is beneficial. But discussion about related works (graph Gaussian processes) are missing. Then, my opinion is "weak accept" for now.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper derives a GP model as a GCN with layer widths increased to infinity. To make the prediction more scalable, a low-rank approximation approach is proposed. Experiments are conducted to compare with other baseline models and show the GP model’s running time and scalability advantages.
strength_and_weaknesses: Strength:

1. The designed GP covariance kernel is able to capture the geometry information of the graph.
2. The runtime of the designed GP is much faster than standard GCN, especially using the low-rank version. Also, its performance on all datasets is better than GCN.
3. For most of the operations in GNNs, operational counterparts for the GP exist. Therefore, the proposed GP model can be extended to many other GNNs.

Weaknesses:

1. It is interesting to see that GP versions of many SOTA GNNs achieve comparable performance with respect to their original models. However, this is only done in one dataset. It would be great if the authors can also have this comparison on other datasets in Table 4.


Questions:
1. How is $d_0$ defined in $C^{(0)}$? 
2. For usual GPs, their hyperparameters (typically in the prior mean function and the covariance function) can be obtained by optimizing the log-marginal likelihood. In the proposed GP, how can these hyperparameters be optimized?
3. Can the proposed GP model be extended to the GAT family?

clarity,_quality,_novelty_and_reproducibility: 1. The paper is written clearly.
2. The code of the proposed model is not uploaded. Given the designed efficient implementation and the proposed GP model's potential influence in GNNs, it is encouraged to have the code public so that others can study or reproduce it.

summary_of_the_review: The idea of deriving a GP model for infinitely wide GCN is novel. Also, the GP model can be extended to a wide range of GNNs, which shows its generality.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper bridges the gap between GNNs and GPs by deriving the covariance kernel that incorporates the graph inductive bias as GNNs do. More specifically, the paper has shown that the GP can be derived as a limit of the GCN when the layer widths tend to infinity and demonstrated the kernel universality and the limiting behavior in depth. Despite an earlier paper which has made the same connection between GNN and GP, this paper provides some interesting theoretical analyses and a scalable inference method which is critical for GPs with large-scale kernels. The proposed GP model can be extended to many other GNNs. 

We think this paper has made a good contribution to the GP community. We all agree that the authors need to do a bit more thorough investigation into the related works, which we hope can be addressed in the final version.





justification_for_why_not_higher_score: The main concern is still that the proposed connection between GNNs and GPs has been studied in the previous work. The authors didn't mention this previous work at all in their initial submission. This harms the originality of the paper.

justification_for_why_not_lower_score: Apart from the originality issue, the paper is well-written, addresses several interesting and critical issues in GNN-inspired kernels, and makes it scalable and generalizable to several interesting members of the GNN family. These are significant contribution to the GP community.
Decision: Accept: poster