Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper shows that the geometric random walk kernel is differentiable using implicit differentiation and can hence be used in a graph neural network to match an input graph to a set of learned graphs. The experimental results show that this method is competitive with a variety of other methods.
main_review: This is a well-written and well-executed paper with encouraging and thorough experimental results.

The only real question in my mind is whether it meets the bar for novelty and significance: It falls under the large number of papers that take an iterative process and use implicit differentiation to efficiently include it in a neural network for training. With this formula in mind, the derivations are relatively straightforward. Moreover, the experimental results are not particularly surprising and don't show very significant improvements over other methods. With that in mind, perhaps this paper is more appropriate for a workshop? Or perhaps there is a way that this work could be extended?

The authors refer repeatedly to Bai et al. (2019) for the implicit differentiation. Although this might be the correct reference for the recent rediscovery of implicit differentiation in deep learning, I believe that "Automatic Differentiation and Iterative Processes" (Gilbert, 1992) should probably be cited as one of the papers that originally introduced the idea.


summary_of_the_review: A well-written and decent paper that struggles to meet the bar for novelty and significance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper deals with learning with graphs, specifically graph-level classification. Given a graph G, the main idea of the paper is to compare the graph G to a set of N graphs using the (infinite-length) random walk kernel (Vishwanathan et al. 2010), resulting in a vector with N components. The resulting vector is fed into an MLP performing the classification tasks. Crucially, the N graphs are learned using end-to-end learning.

Further, the authors show how to compute the RW kernel efficiently, building on previous work  (Vishwanathan et al. 2010), and how to do differentiate through the architecture efficiently, building on (Bai et al. 2016). The paper can be seen as an extension of the RWNN model (Nikolentzos et al. 2020), which uses a finite-length random kernel. 

The methodology is complemented with an experimental study showing promising performance on standard benchmarks datasets. 





main_review: **Strengths**
1. Simple architecture that give good empirical results 
2. Well-written and easy to follow

**Weaknesses**
1. Incremental work, building on known work 
2. No clear performance gain over fixed-length RW models, see Table 1 
3. Comparision to fixed-length RW models only done on small-scale datasets, compare Table 1 and Figure 1(a)


**Questions**
1. You state that "Such local patterns may fail to capture the overall large-scale shape of the graphs, while several interesting
properties of graphs depend on the graph’s global structure."

Can you quantify exactly for which kind of graph structures this is the case? 
E.g., by quantifiying the graph structures captured by the infinite-length RW models but not by finite-length RW models.

2. Why did you not evaluate the fixed-length RW models on the OBG datasets?

3. Does your architecture offer any insights on how to design deep GNNs?

**Suggestions**
To show a clear performance gain, especially over the fixed-length RW models, one should compare the model on more large-scale datasets, e.g., from OGB and graphlearning.io. The small-scale datasets from Table 1 exhibit large standard deviations which make comparisons in terms of accuracy often not meaningful. 

**Minor comments**
1. You seem to use \citet{} when citep{} would be more appropriate
2. First page, second paragraph:  "graphs, So far, ..." -> "graphs. So far, ...

summary_of_the_review: The paper is well-written and easy to follow. However, the idea is incremental, building largely on previous work. Moreover, the gain in expressiveness is not quantified, e.g., by showing that the infinite-length RW models can expressive more permutation-invariant functions compared to the fixed-length RW models. Morever, the emperical results are not convincing, i.e., they do not clearly win over  the fixed-length RW models.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper discusses random walk graph kernels for graph neural network feature generation in other works. They work by generating features for graphs by comparing random walks present in each graph compared to a set of trainable hidden graphs. It is stated in this paper that an advantage of random walk kernels is that they are end to end differentiable, but current implementations have the weakness of only being efficient for walks of very short length. They introduce a way to efficiently extend walks to ‘infinite length’, theoretically making features generated by the kernel more informative. They compare their results with top GNNs and with other graph kernel approaches such as the mentioned random walk kernels on graph classification datasets. Out of 10 datasets they achieve best performance on 2 (1 of the 2 is tied for best), second best on 3, and third best on 1, It should be noted that many placements are well within the margin of error. 
main_review: strengths: 

The main contribution, which I believe is their solution to allowing an ‘infinite step’ geometric random walk to be efficiently differentiated and thus the hidden graphs trained, is thoroughly detailed in section 4. Also, they thoroughly justify and demonstrate settings for their main hyper-parameter lambda. Assuming correctness of the implementation itself, which I am not very confident in my ability to critique, I believe this is an idea worth exploring regardless of the outcome. 

Although the results aren’t clearly superior, it seems that none of the competitors listed are in a significant lead, and instead each has strengths and weaknesses in the diverse pool of graph datasets. I would say this method proved itself to be a good choice for some kinds of graph classification problems. 


weaknesses: 

A major problem of this work is numbers reported the experimental study. In table 1, many results are far lower than that in their original papers. For example, GIN achieves 75.1 and 52.3 on IMDB-B and IMDB-M but was reported 71.2 and 48.5 (https://arxiv.org/pdf/1810.00826.pdf). The state-of-the-art performances on these datasets have been greatly improved and far better than the performances achieved by GRWNN. The authors need to address this issue. Otherwise, I would have concern that the reported numbers are misleading the audiences and reviewers.

The conclusion seems rushed and doesn’t analyze the results very well, such as the fact that allowing longer random walks is, in some cases but not others, an advantage over the 1-step random walks on all datasets. I’m naive to the true implications in this case, but I assume there is knowledge to be gleaned from the results even if they aren’t a large improvement over competitors. 
summary_of_the_review: Although the authors make great contribution to the technical part, the experimental results have big flaw, which needs to be addressed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors proposed an interesting geometric random walk neural network for graph representation. The proposed method can be viewed as an improvement of the random walk neural network in [Nikolentzos & Vazirgiannis, 2020], which learns graph representations by modeling the geometric series of the “product” between observed graphs and some hidden and learnable graphs. 
As a result, the graph representations are learned by finding fixed points of linear systems. 
main_review: Pros:
1. The idea of this work is interesting and has sufficient novelty. An efficient computational method is designed to simplify the computation associated with the “graph product”.

2. The experiments are sufficient and representative graph datasets and baselines are considered.

3. The paper is well-written and thus easy to follow. 


Cons:
1. Although the authors make efforts to reduce the complexity of the proposed method. Compared with message passing neural networks (MPNN), the proposed method involves inevitable dense matrix multiplication — in Eq.(6) and Proposition 1, A_i is a dense learnable matrix. As a result, when there are many large hidden graph A_i’s, the proposed method will be much worse than MPNN.

2. The experimental results in Table 1 and Figure 1 do not show the superiority of the proposed method. Considering the potential high complexity of the method, what is the main advantage of the proposed GRWNN method?

3. Besides RWNN, the factorization-based methods in [a, b] also leverage several learnable hidden graphs to learn graph representations, and they are applicable in unsupervised learning cases. The authors should consider these works and the corresponding learning strategy in the related work and discuss them in-depth.

[a] Xu, Hongteng. "Gromov-Wasserstein factorization models for graph clustering." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.
[b] Vincent-Cuaz, Cédric, et al. "Online Graph Dictionary Learning." arXiv preprint arXiv:2102.06555 (2021).

Minors:
1. Although the authors provide an empirical method to determine “\lambda”, I wonder if it is possible to learn lambda automatically. 

summary_of_the_review: The idea proposed in this paper is interesting indeed, which provides a new way to learn graph representations. However, the superiority of the proposed method to existing work is verified neither on classification accuracy nor runtime. Additionally, some related graph representation strategies are not considered or discussed.
review_title: null

Meta-review: This paper shows how to back-propagate through a kernel between graphs that counts common random walks of infinite length between the graphs. Reviewers tend to agree that the paper is well-written and the technical contributions are sound. However, there are concerns about the significance and novelty of the method relative to related work, alongside mixed experimental results. Overall that puts it as a very borderline paper. In the rebuttals, the authors argued for the significance of the contribution, but reviewers were generally unconvinced.
Decision: Reject