Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a method that is based on graph kernels to perform graph convolution, which add to the interpretability of GNNs.
A framework for learning graph kernels is introduced and studied on multiple datasets. The results show improvement in some datasets.
main_review: The paper is well motivated and easy to follow. The authors provide a detailed description of the problem and related works and background.


Regarding contribution #1 "Unlike existing approaches that require embedding the input graph
into a larger, relaxed space with a higher likelihood of ending up in a local minimum, our model
is fully structural". -- Why is this true? Usually, we would like to have a high dimensional feature space, to capture more abstract features of the input. I am not convinced that remaining in a smaller dimension is more beneficial. Perhaps the authors can elaborate on this point ?

Regarding the second paragraph in the related works section, where diffusion in GNNs is discussed - while the statement is correct, it was also recently shown in "PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations" (https://arxiv.org/abs/2108.01938) that not all kind of applications and datasets indeed benefit from diffusion, and at times propagation is favored. I believe that discussion that in the paper will contribute to its content.

All the experiments consider graph classification, which is indeed an important task. However, it would be interesting to know how the proposed method would work, for instance, for node classification (e.g., Cora, Citeseer). Also, it would be interesting to know if the method can be used for geometric datasets, where a more learned masks may be easier to explain.

In all experiments, a rather shallow network is considered to my understanding. Either 1,2,3 kernel layers are used, following a classifier. Since oversmoothing is a known phenomenon in typical GCNs, it would be interesting to know if the proposed method can prevent this problem. It may be, that learning the correct masks can aid in feature preservation and distinguishability (this is also related to the diffusion/propagation discussion above and the works cited by the authors).

Overall, the results presented in Table 1 show that in some cases the proposed method outperforms other by quite a small margin, but in most cases it is not better methods.

The authors state that graph kernels are limited by implementation. While this may be fine, I think that the authors can strengthen their claims by adding some information regarding the run times of their work compared to others.






summary_of_the_review: The paper is clearly written and motivated but lacks on the experimental side, both in results of current experiments, and also the scope of the experiments is rather limited.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel architecture for graph processing that uses graph kernels with learnable structural masks.
The core feature of this novel architecture is the graph kernel convolution (GKC) layer. 
The GKC layer consists of computing for each node $v$ a subgraph centred in $v$ of radius $r$, then the subgraph is compared with a series of structural masks through a graph kernel. The resulting kernel responses are collected into a vector, which is then quantized using k-means clustering, and the cluster label is used as the new node label. 
Multiple layers can be stacked, although they require adding skip connections because of the quantization operation.
The authors propose also 
main_review: Strengths:
- The paper presents a novel and interesting class of learning algorithms for processing graph-based data. This is is a particularly relevant area in machine learning which contributes to raising the significance of this work.
- The model is somewhat more interpretable than competitors and seems to be well apt to settings where the topological structure of the graphs plays a major role 
- The paper is generally well written and easy to follow, although some parts of the presentation could be improved as in the detailed comment 1. 

Weaknesses:
- The model has some limitations. First, it seems limited to graph classification/regression problems. Could it be used also for node-level tasks? Furthermore, it is suitable to settings in which nodes have either no or only a discrete set of labels (with low cardinality). The authors should be more clear about these limitations from the introduction.
- The optimization problem involves optimizing over discrete structures. I believe the part regarding the learning technique could be clearer, more formal and with more details. Please see detailed comments. For this reason, I have some doubts about how much of the performance is driven by learning and how much by engineering. 
- The experimental section is improbable, see detailed comments 4.

Detailed comments:
1. Clarity: 
a) in *To keep the labelling consistent among different batches, the k-means algorithm centroids at step $\ell + 1$ are initialized using the centroids
computed at the previous step* (pag 4) does batch mean layer? Or is it about batched (stochastic?) processing of the nodes or of graphs in a mini-batch of graphs?
b) On page 3, it is not entirely clear to me what $g$ is and what $\theta$ and $\Theta$ refer to (specifically, do they represent the same sets of parameters?). Does (1) implements $g_{\theta}$?I think this passage could be written much more clearly. 
b2) This confusion is carried forward also to eq (4). What is $\theta$ there precisely? Only the parameters of the last classification layer?
c)  The $h$ in (4) seems to be quite different from the $h$ in (1), probably it would be better to change notation there to avoid confusion.
d) The proofs are only sketched, with little details and not particularly easy to follow. Just to give an example, in *the presence of a triangle in the graph induces the existence of at least three sub-graphs of radius 1 with *cross-neighbor* connections.* what does cross-neighbor specifically mean?

2. I never heard of the discrete randomized descent method and the authors seem not to make any reference. Can the authors comment on this? If this is a (well-known) approach, please add a reference, otherwise, I think there should be more explanation about the method. For instance, in P(6) there is an equality sign which seems misplaced (also the authors talk about "estimation"). On the same line, I think also the concept of discrete sub-gradient is non-standard and needs to be defined or linked to some relevant literature. For instance, it seems that it differs from the concept in [1].

3. The authors argue that in order to backpropagate the error in a multi-layer version of the architecture they need to add skip connections since they do not propagate the gradient through the vector quantization operation. However "discrete gradients" are used to learn both the mask structures and the edit distributions. Can't they (or similar strategies) be used also to propagate the gradients throw the quantization operations?

 4. Regarding experimental validation: a) I would like to see a training curve. How much does the model improve with iterative optimization? How many iterations are needed and how many passes through the training data? b) I wonder what's the effect of the initialization. I would ideally like to see a set of experiments to ascertain how much the (random) initialization impacts the performances and convergence/training time. c) I believe that grid search makes it really difficult to understand what is it the tuning effort of the proposed model (learning algorithm)  with respect to the other competitors. This is because the total allocated computational budget can vary extensively. In my opinion, random search would have been a better and equally simple alternative, as it allows to have an "anytime solution" which makes it easier to compare methods (i.e. at each timestep, one could compare the best model found so far. 

Minor points:

5. The authors make the point that GKN can leverage the presence of many graph kernels that have been proposed in the literature. However, most of the experiments have been done with the WL kernel. Would it be possible to have a GKN that uses multiple graph kernels? If so, how would it fare on the benchmark datasets?

6. A discussion of the computational complexity is entirely missing, as well as reports of runtime measurements.

7. I would call section 4.1*Sensitivity study* rather than *Ablation study*. Ablation usually refers to the practice of removing components of the learning algorithm that is being proposed. Instead, section 4.1 is about seeing what is the relative effect of each of the model hyperparameters.

8. Missing sensitivity analysis of the number of clusters to use during the quantization step.

[1] Bagirov, Adil M., Bülent Karasözen, and Meral Sezer. "Discrete gradient method: derivative-free method for nonsmooth optimization." Journal of Optimization Theory and Applications 137.2 (2008): 317-334.

summary_of_the_review: This paper is a potentially significant contribution to the area of graph ML.
At the moment, however, I have some concerns regarding the training mechanism proposed, specifically regarding the utilization of "discrete gradients". Moreover, the experimental section could be improved.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose a model that uses graph kernels to extend the convolution operator to the graph domain. Given a graph, the model extracts a subgraph centered around each node of the graph and generates a representation for that node by comparing its subgraph against a number of structural masks using graph kernels. Since graph kernels are not in general differentiable functions, the authors use a discrete randomized descent strategy to optimize the structural masks. The authors also add a Jensen-Shannon divergence loss term to force the masks provide dissimilar responses from each other. The proposed model was evaluated on standard graph classification datasets where it was found to be competitive with the baselines.
main_review: - In summary, the approach proposed in this paper is interesting and deals with a topic that has not been thoroughly studied yet. The paper generalizes the model presented in [1] and allows the use of any graph kernel as a component of graph neural networks. However, the paper in its current form does not appear ready for publication and there are several concerns that the authors need to address (see comments below). Furthermore, the empirical results are okay, it seems that the model is competitive with the baselines, but they are not impressive.

- One of the main limitations of the proposed model is its computational complexity, but the authors do not discuss it in the paper. Since the authors extract subgraphs of radius r centered at each node, I would expect the complexity of the model to be high especially when r is set to large values (e.g., 3, 4, etc). I also guess that the high complexity of the model is the reason why the authors do not evaluate it on any of the REDDIT datasets or on COLLAB since these datasets contain very large graphs. I would suggest the authors also report the running time of the proposed model on the different datasets such that one can compare them against those of other baselines. The authors mention in the conclusion that there are no widely available GPU implementations of graph kernels, thus it is likely that the running time of the proposed model would be prohibitive for real-world applications. This is a key weakness of the paper, but still reporting those running times would strengthen the paper.

- It is not clear to me why the input graph is not directly compared against the structural masks as in [1], but instead the authors extract a subraph centered around each node and compare those subgraphs against the masks. I guess that this can lead to higher expressive power (the model is more expressive than 1-WL), however, as discussed above, it also increases the computational complexity of the model.

- In the literature of graph kernels, there exist some kernels that can handle graphs whose nodes are annotated with feature vectors such as the GraphHopper kernel [2] or the multiscale laplacian kernel [3]. I wonder why the authors do not employ those kernels and instead resort to vector quantization techniques which lead to loss of information. Perhaps this is due to the computational complexity of those kernels. I would like the authors to comment on that and it would also be nice if the authors could present some experimental results of the proposed model using one of the above kernels on some dataset that contains small graphs.

- The k-means algorithm is run multiple time at each epoch (once per batch). I am not thus sure whether the clustering result of the k-means algorithm is consistent across different batches. The authors initialize the centroids of the algorithm using the centroids of the previous batch. I would suggest the authors perform an experiment and measure the average distance of each centroid from one batch to the next. If those distances are large, this might indicate that the model is unstable.

- The learning process employed in this paper is different from a traditional learning setting since the model samples an edit operation, and it does not directly learn which operation is the best. I feel that such an approach can easily get stuck in local optima. In such a scenario, the masks could be of no practical interest. I would suggest the authors investigate how much the structure of the masks changes during training. The authors could also borrow ideas from the field of discrete optimization, and design some more sophisticated approach for updating the masks.

- The authors perform their ablation study on the MUTAG dataset. This dataset is very small (188 graph in total) and in general, obtained results are very sensitive to fold assignments and potentially to weight initialization. I am not thus sure whether the results of the ablation study are significant and whether they would also apply to other datasets. The authors should consider to use another dataset that contains a larger number of graphs such that the obtained results are more valid.

- Please specify how the representation of the entire graph is produced. Do the authors use a sum aggregator?

- Typos:
	- p.2: "includes methods where" -> "include methods where"
	- p.3: "are assumes" -> "are assumed"
	- p.6: "G_1 = (V_2, E_2)" -> "G_2 = (V_2, E_2)"

[1] Nikolentzos G. and Vazirgiannis M., "Random Walk Graph Neural Networks". Advances in Neural Information Processing Systems, pp. 16211-16222, 2020.\
[2] Feragen A., Kasenburg N., Petersen J., de Bruijne M. and Borgwardt K.M., "Scalable kernels for graphs with continuous attributes". Advances in Neural Information Processing Systems, pp. 216-224, 2013.\
[3] Kondor R. and Pan H., "The multiscale laplacian graph kernel". Advances in Neural Information Processing Systems, pp. 2990-2998, 2016.
summary_of_the_review: Overall, this is an interesting paper which studies a topic that has not been fully explored yet.  Even though the originality of the paper is not stellar, the paper introduces some new ideas. However, there are several issues that the authors need to address (e.g., running time, investigate whether clustering is consistent, ablation study on some other dataset, etc). Furthermore, the empirical results are not bad, but they are also not impressive. Thus, the paper does not seem ready for publication in its current state.
review_title: null

Meta-review: The paper uses graph kernels to perform local convolutions and achieve better expressiveness than classical GNNs. The paper received three borderline reviews. The area chair found the feedback to be consistent and constructive and agrees with most statements made by the reviewers. Overall, the idea has some interest (even though there are other works who also propose hybrid approaches between graph kernels and GNNs, as noted in the paper). Nevertheless, there is a lot of room for improvement regarding the experimental validation and the results are not very convincing (yet?). The datasets used in the paper have been traditionally used for evaluating GNNs but they have strong limitations due to their small size and it is often hard to draw conclusions from them. If the method does not suffer from scalablity issues, it is likely that more interesting results could be obtained by using ZINC or MOLHIV datasets, which are larger and often provide statistically significant results.

Overall, these issues may require a major revision and unfortunately, the area chair believes that the paper is not ready for publication.
Decision: Reject