Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: Paper presents a novel graph-structure aware kernel for graph data that leverages local sub-graph structure for node label and link prediction. It leverages spectral representation of kernels and RFFs along with ideas from graph learning to present a variational EM algorithm for graph learning. Strong empirical results show efficacy of proposed method over non-GP based GNN learning approaches.
main_review: A key contribution of the paper is the idea of using local sub-graph structure around each node in order to define a structure-ware Bayesian graph kernel. It combines several ideas of spectral kernel representation, RFFs and GP's to proposes an interesting idea that leverages local neighborhood of a node for graph learning.  

Paper is well written and technically strong and addresses several aspects of proposed framework including choice of distributions, convergence, label distribution impact, sample size, effect thresholding and so on. It also provides a Bayesian and computationally efficient algorithm to estimate model parameters. 

Another aspect of Graph learning that is not considered in this work is most real-world graphs (random graphs with large N) are sparse with fewer edges and how does this impact EM modeling, convergence and results. 
limitations_and_societal_impact: Paper addresses some limitations of the graph learning framework in the conclusion but without any empirical results. Appendix E.1 addresses effect of label data imbalance. No direct societal impact of concern.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
This paper develops a structure-aware random feature kernel for Gaussian process-based learning over graphs. Experiments were carried out on real-world datasets for classification and link prediction.

main_review: The reviewer finds the novelty of the proposed framework not enough. It is a direct combination of Gaussian process +Fourier Random Feature +GNN (GP+RF+GNN). However, GP+RF has already been studied in previous work, and the incorporation of graph structure is just by input the graph with the existing GNN framework to obtain a representation.

Moreover, in the experiments, it is shown that a threshold needs to be introduced for the proposed algorithm to obtain better results than GAT. However, the choice of \tau was not discussed. Moreover, the choice of some critical parameters such as L (hops of neighbors), F (number of RFs) is not discussed for the experiments either.

The reviewer finds the organization of the paper can be improved. Some important information is missing. For example, it is claimed that the output of g() is a subgraph representation obtained using GNN in (2) and (3), but (2) (3) only provides node-level representation. It is not clear how the subgraph representation is obtained.

The writing of the paper could be improved by clearly defining operators, discussing or clarifying the procedure of parameter selection, as well as clarifying the novelty compared with existing works.



limitations_and_societal_impact: The reviewer finds this aspect inadequate, while the authors discussed the limitation: require off-line training and not robust to attacks from adversary and claim that as negative societal impact, but it seems to the reviewer believe these are just algorithmic limitation instead of societal impact. The reviewer believes societal impact could be discussed regarding the potential privacy concern, as a lot of social network datasets are used which naturally leads to privacy concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposed a novel SRF kernel defined with spectral distribution based on the Fourier duality given by Bochner's theorem on the vector embedding of subgraphs using GCNN.  Based on the SRF kernel, the paper  proposes a GP model, GPSRF,  for graph learning tasks. Paper developed a variational EM algorithm to solve kernel parameters. It also studies the run time complexity of the proposed method. Model has been evaluated for semi-supervised object classification and link prediction. Experimental results show that GPSRF yields best performance compared with state-of-the-art baselines.
main_review: Use of GCNN to define a graph based kernel is new to me. 
Combining subgraph embedding with Fourier kennel is interesting and might be very useful for many graph based tasks. 
Advantage of this method is that it can capture features and graph structure in one kernel and the run time complexity is very less O(N). 
Paper is well written and has clarity and is technically sound.
Experiment section is well planned and has been compared with many possible state of the art methods. 
Paper has also discussed the possible negative social impact.

This model is applicable when an object is in a graph. Does it also applicable for tasks when the data object is a graph like protein classification etc?

Following related work is missing.
Nikolentzos, G., Meladianos, P., Tixier, A.J.P., Skianis, K. and Vazirgiannis, M., 2018, October. Kernel graph convolutional neural networks. In International conference on artificial neural networks (pp. 22-32). Springer, Cham.

limitations_and_societal_impact: Author has already discussed it in paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The idea of this paper is to build a kernel on the features of the graph that takes into account the underlying structure of the graph. Once found, this kernel is used to define a GP on the graph. This is useful for learning tasks on graphs such as node classification/link prediction. In order to build this kernel, the authors propose to use a base translation invariant kernel that admits, by Bochner, a feature expansion, i.e. an embedding $\phi(x,w)$ (like RFF). More precisely, they propose to learn the law on the drawing of the frequencies $w$ of these features under the constraint that the features must incorporate the structure of the graph. These features are built in two steps: 1) the law on the drawing of frequencies $w$ is defined by a "hierarchical" law parameterized by a neural network that can be "arbitrarily complex" (in the manner of a GAN generator) 2) the features take the embedding of a subgraph centered at this node as input $x$. This embedding is defined by a GNN.
main_review: - Pros:
	- The article is well written, quite clear.
	- The method proposed is interesting, and, to the best of my knowledge quite new.

- Cons:
	- The method supposes to have already a good embedding of the graph, which is rather limiting. 
	- Some points in the experiments are not very clear.
	- The advantages and limitations of the approach could be better underlined.

Overall I find this article interesting, it combines many ideas and domains (kernels/GNN/GP) to define an interesting method for learning on structured data. I also find it well written, pedagogical, and I thank the authors for this effort. The proposed method seems to me quite relevant. There are however some points that are not very clear to me. Here are my detailed comments.

- About the method:

I find the method well detailed and clear. I think, the use of GNN embedding is the central point of the method. In this context, a point that seems unclear to me is that, as far as I understand, this embedding is not learned in conjunction with the kernel and is considered as fixed. Overall this implies to have already a good embedding of the graph, which can cause some problems in practice. Indeed, for the method to work, one needs to: 1) either have a good pre-trained GNN 2) or re-train a GNN on the data. Moreover, as shown in experiment 8.5 it seems that it is quite crucial to have a good embedding $g$. I find that this limitation is not discussed enough in the paper, especially in terms of learning complexity (section 7). It would have been good to point out that this complexity also depends on having a good GNN. On the other hand the method is flexible enough to consider more hand-crafted and unsupervised embeddings based on graph kernels for example. Did the authors test with other embeddings that are less dependent on a GNN? Moreover I think that ref [1] can be interesting in this context. The Variational EM part is quite "classical" for this kind of problems and seems relevant to me.

- About the experiments:

	- Semi supervised classification task. I am a bit skeptical about the message brought by this experiment. I find that the conclusion that "GPSRF > all GP models" is a bit misleading. As much as it is clear for most of the GPs, it is a bit less clear for the GPP method [2] (ref [17] of the article) which is the most similar to the method proposed in this article. The major difference between the two methods is that the base kernel of the graph-based GP of [2] is based on the Laplacian of the graph. So it is really interesting to compare with GPP. However, the performances between the two methods are very close, because of the variance, on all datasets (except maybe Computers). Especially since the performances are only calculated on one train/validation/test split. For me it is difficult to see that the difference between the two is statistically significant. 
	- Link prediction. The results of this experiment seem convincing and show the advantage of the method on this type of task. 
	- Regression task. It is not really clear to me the relevance of this experiment. More precisely I don't understand the interest of an experiment that considers only the base kernel (without the graph part). Is it to illustrate that the hierarchical Bayesian approach to learn the RF law is interesting? In this case, I think it would have been interesting to discuss a little bit why this idea is new (because I think that some works approach the same idea of learning the law of frequencies according to the data [3,4,5]).

One point that I thought was worth highlighting is the fact that the method in question can take into account/model uncertainty in the prediction. I think that this property is interesting and should be emphasized, because, to the best of my knowledge, it is rarely taken into account in the context of graphs. 

- Minors:

I think it should be mitigated that methods relying on traditional kernels and Laplacian are wether "inefficient for them to capture the structural smoothness in graph data" (row 31) and "they ignore the rich features of objects and may not be capable to model complicated functions over large-scale graphs" (row 36). It is precisely what they are attempting to do, based on the prior that "close" nodes (in the topology of the graph) should share similar features, and, as always, the fact that these methods sometimes struggle with the learning task depends on the dataset.


[1] Daniele Zambon, Cesare Alippi, Lorenzo Livi. Graph Random Neural Features for Distance-Preserving Graph Representations

[2] Yin Cheng Ng, Nicolo Colombo, Ricardo Silva. Bayesian Semi-supervised Learning with Graph Gaussian Processes

[3] Zichao Yang, Alexander J. Smola, Le Song, Andrew Gordon Wilson. A la Carte - Learning Fast Kernels

[4] Aman Sinha, John C. Duchi. Learning Kernels with Random Features

[5] Junier Oliva, Avinava Dubey, Andrew G. Wilson, Barnabas Poczos, Jeff Schneider, Eric P. Xing. Bayesian Nonparametric Kernel-Learning


---- AFTER REBUTTAL ----

The authors addressed most of my concerns (see my comment below). I am changing my score to 7.

limitations_and_societal_impact: Authors did not provide any potential negative societal impact of their work however, it is difficult for me to foresee these impacts as the work is mostly a methodological paper. There are some other limitations that I think should be more discussed. Especially concerning the fact that one needs to have a good GNN at first (see my review above).
review_title: null

Meta-review: The paper received positive reviews and the rebuttal phase clarified some potential 
issues. Overall, this is a solid contribution, which should be accepted. The final submission 
should, however, incorporate suggestions made during the rebuttal phase.
Decision: Accept (Poster)