Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes a walk-based kernels for graphs with nodes being labeled with WL labeling scheme. It is supposed to improve expressiveness of random walk kernels and can be as good as WL subtree kernels. 

--------------------
After looking at responses, other reviews and the paper again, I do find the paper does offer a new way to compute kernels, even though not strictly solving the expressiveness problem of previous work, may offer a new view and future development. I think I can raise my evaluation a bit.
strengths_and_weaknesses: The paper's originality is in its combination of walk-based kernels with WL labeling scheme. This is proved to be an improvement on random walk kernels, but not on WL-based kernels.

The paper show many properties of the proposed methods, which I could not check in details, can be interesting. The paper's writing is clear. 

However, all of these do not seem to solve any problem of graph kernels. The approach is shown that can be as good as WL kernels with more computation. I cannot see the benefit of the paper in practice.  

questions: What is the benefit of the proposed kernels? What does controlling the strictness of neighborhood comparison help classifying graphs in practice? What's the benefit of node/edge similarities?

limitations: The paper is clear about its limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper presents a novel framework to describe random walk kernels. First, a unified view is provided to integrate and relate random walk kernels with the popular Weisfeler-Lehman (WL) framework. The paper also introduces a modification of the classical random walk kernel, which allows to improve the expressivity to match the performance of the WL kernel. Experimental analysis is showed to compare the proposed framework with existing graph kernels. 
strengths_and_weaknesses: Strengths: 

- The paper is well written and properly structured, with good notation and clarity of presentation
- Both the experimental evaluation and theoretical framework are solid and robust

Weaknesses:

- The originality is limited. While the integration of these kernel approaches in a unified view is innovative, the methodological changes in the kernel are incremental
- The experimental results are also limited. The actual benefit of the modified RW kernel is not reflected in the results. 
questions: Have the authors compared to the GraphHopper kernel? The kernel formulation seem quite similar, in terms of adding a label-based similarity. I guess one can see the current kernel as an extension of the RW kernel, as the GraphHopper kernel is an extension of the classical shortest path. 

I believe that a stronger experimental section might help to show the actual benefit of the approach. The impact of the paper in the current status is moderated. In particular, I would suggest:

- Extensive runtime evaluation: this is especially important given that he RW kernels are computationally expensive
- Application on attributed graphs: given that the performance superiority to WL is limited, this additional use case would be beneficial  to improve the experimental comparison and show the benefit of the approach. 
- Potentially, find simulated or real case graphs where the kernel can capture information missed by WL
limitations: No negative societal impact.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: 

The paper formally relates finite length node centered random walks to the Weisfeiler Lehman method.  
The Weisfeiler Lehman vertex relabeling algorithm produces a hierarchy of vertex labels, which is shown to be related to a vertex label hierarchy that can be obtained from multisets of vertex centered walks, which correspond to root-leaf paths in the unfolding trees of various depths.
The paper subsequently develops variants of a vertex kernel that is based on multisets of labeled walks, relates them to the random walk, as well as the weisfeiler lehman subtree kernel, and empirically shows that it performs well in practice.
strengths_and_weaknesses: The paper is very well written and technically very precise. It was a pleasure to read and easy to follow. 
Every step is very clearly presented and seems to follow naturally. However, in the almost twenty (resp. fifteen) years since the introduction of random walk (resp. WL subtree) kernels, nobody (as of my knowledge) has yet drawn this connection this rigorously. This insight deserves to be published at a very good conference. 

A generalized $\ell$-walk node kernel is proposed as a result of the insights on the connection between WL and RW refinement hierarchies.
It can be seen as a soft (a little bit weaker) version of the discrete WL vertex kernel. It is hence related to recent approaches which try to weaken the strict dirac-delta comparison of node labels/unfolding trees of the WL subtree kernel. The resulting node centric $\ell$-walk graph kernel is then shown to generalize the random walk kernel, as well as the Weisfeiler Lehman subtree kernel in the limit $\alpha \to \infty$. 
As a result of the comprehensive view that the authors have, it can be readily computed using the machinery that was developed over the last decades.
Empirical evaluation suggests that the theoretical results on expressiveness translate to comparable predictive performance and expressiveness in practice. 

The only 'weakness' that I want to briefly mention is that now that this connection is made, there is an open field of practical questions that could be addressed, regarding the application of 'Weisfeiler-Lehman-like' kernels to attributed graphs, which can now potentially be addressed by choice of suitable base kernels. 
While certainly out of scope of this article, I am eager to see more. 
questions: Proposition 3.9 is correct if the base kernel used for vertex comparison within the walks is $k_V$ as defined in Line 202. However, it seems that using a different base kernel, such as $k(u,v) = 0 \ \forall u,v \in V(G)$ should yield $\hat{k}^+_\ell(u,v,a) = 1 \  \forall u,v \in V(G) \ \forall \alpha\geq 0$. Therefore, for this (obviously useless) base kernel, Proposition 3.9 would not hold. It hence seems that Line 202 'w.l.o.g' might be misleading. Furthermore, it should be stressed that Prop. 3.9 is somewhat specific to the base kernel $k_V$ (as it is also used in the proof). 
In fact, any kernel that identifies two or more vertex labels will result similar issues.
Is my assessment correct?


In the experimental section, I am a bit lost. I am assuming that NCW is the kernel as of Definition 4.1 with $\hat{k}^+_i$ and $k_i$ computed by Algorithm 1 _without the blue Line 9_, while NCWWL is _the same, with Line 9_? 
It might reduce (at least my) potential confusion if you could clearify this a bit more.

In the experimental evaluation of the expressivity, it seems that $\alpha = 1000$ is a rather large parameter for the rbf part of Def 4.1. It seems to be the largest parameter that you consider in the experiments. Why do you choose $\alpha=1000$ and $\beta=0$ here? How does the expressiveness change if the parameters are changed? Also, how does NCWWL behave? 


The paper is very nicely and cleanly written. It has been a real pleasure reading it! Minor typos and issues that I have found are listed below:

- l58: Our Contribution -> Our contribution
- l143/Fig.1: It seems that Fig(1a) shows the unfolding trees of nodes $f$ and $e$, not $f$ and $g$, as mentioned in line 143. The text is correct for $f$ and $g$. I was confused for a while. 
- l223: a techniques
- l228: line -> Line
- l300: TuDatsets (also in appendix somewhere)
- Fig2: the Label kernel is not described in the experimental section. Is it VL, EL, or a combination of the two?

limitations: 
The authors don't report runtimes of the kernel computation and mention runtime improvements as future work. Another mentioned limitation is the current restriction to node label information and to discretely labeled graphs. It seems that these limitations are not inherent to the node centric $\ell$-walk graph kernel, but merely due to implementation and/or scope of the experiments.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper gives a unified view on random walk kernels and Weisfeiler-Leman subtree kernel and relate walk-based label refinement to the Weisfeiler-Leman method. They derive a node-centric walk kernel on graphs which generalizes the classical random walk kernel and allows grouping of walks by their start node. They verify the theoretical results on real-world graphs and show that their method has higher accuracies, surpassing the Weisfeiler-Leman subtree kernel in some cases.
strengths_and_weaknesses: Originality and Significance: This work is the first that relate random walks in labeled graphs and the Weisfeiler-Leman method formally and show that classical random walk kernels with only minor modifications regarding definition and computation are as expressive as the widely-used Weisfeiler-Leman subtree kernel but support non-strict neighborhood comparison. The contributions play well into previous work as a helpful summary as well as extension and also bring inspiration to future research.
Quality: The paper is well done with sufficiently proved theoretical results and the detailed experiments which verified the key problems the paper concerned(Q1-Q3).
Clarity: Clear writing and structure. 

**Weaknesses:** Some notations are recommended to be mentioned like $  \Delta $ in line 109.
questions: We do not have questions. 
limitations: They address it adequately.
review_title: null

Meta-review: metareview:  The paper yields new understanding of random walk kernels and W-L graph isomorphism test based kernels. This is a very interesting contribution towards understanding kernels between graphs. This should be of interest to Neurips community.
confidence: Certain
Decision: Accept