Summary
Kernel methods are important in many ML applications, but they suffer from scalability issues. In the Euclidean setting, random features methods (Rahimi & Recht NeurIPS 2017) can be used to "sketch" the kernel matrices and speed up computations. In the graph setting, however, no such random feature seems to have been available until a 2023 preprint by Choromanski.
The present paper present an improvement over Choromanski's method. To explain it, note that the basic idea in the 2023 preprint is to consider random features for the regularized graph Laplacian, and to obtain an approximation of an operator of the form $(I-U)^{-d}$ via importance-weighted random walks. These random walks have geometrically distributed lengths.
The main theoretical contribution of the present paper can now be explained: a simple modification of Choromanski's method, where the the geometrics of pairs of random walks become correlated, has the same zero bias and a smaller variance than the above method.
This requires an elementary, but long proof with a long case analysis.
Experimentally, the gains observed were:
* visible, but not too big for approximation of the kernel;
* impressive for graph diffusions (which is natural because this requires exponentiating the Laplacian);
* fairly significant for clustering and node attribute prediction methods.
Strengths
The paper is clear and seemingly original. In general it is fairly well-written. Moreover, the "anthitetic" coupling is a simple little idea that could be applicable more broadly.
Weaknesses
The present paper has been submitted before Choromanski's preprint appeared. As a result, applications of graph kernel random sketches are quite incipient still. It is hard to say whether the present paper will have a significant direct impact. _[Edit on 08/11: this was partly addressed in the rebuttal.]_
The proof of variance reduction is very long and difficult to check. (Though I believe it.) (An "actionable version" of this point is that it would pay off to make this paper a bit less dependent on Chorumovski's preprint by eg. adding more experiments or theory.)
_Less important comments_
The notation $t_{1,2}$ is a bit weird as it represents a pair of RVs. Moreover, if I understand correctly, these r.v.s are resampled at each step of the walk.
In terms of exposition, it seems that all the authors need to do is to correlate the coin flips for the two walks at each step. Could you write their joint distribution purely in terms of the probabilities of 00, 01, 10 and 11?
Questions
Can you point to more specific and realistic applications where this methodology would be useful? (A somewhat speculative discussion would be nice.)
--
Edit (08/11) -- addressed in rebuttal.
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.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
These are properly discussed.