Pith. sign in

REVIEW 5 major objections 4 minor 43 references

Stitching several short random walks yields an unbiased, faster estimator of long-range graph kernels.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-08-04 10:56 UTC pith:D7LFAJJB

load-bearing objection The walk-stitching estimator is a genuine and correct contribution; the accuracy-at-no-extra-cost claim is not proven as written, so the paper needs careful revision before the performance headline can be trusted. the 5 major comments →

arxiv 2510.07716 v2 pith:D7LFAJJB submitted 2025-10-09 cs.LG

Computationally-efficient Graph Modeling with Refined Graph Random Features

Krzysztof Choromanski , Avinava Dubey , Arijit Sehanobish , Isaac Reid This is my paper
classification cs.LG
keywords graph random featureswalk-stitchinggraph kernelsrandom walksunbiased estimationkernel approximationdiffusion kernelgraph node kernels
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that graph node kernels of the form K(W) = Σ α_k W^k can be approximated more accurately and more cheaply by stitching together several short random walks instead of sampling one long walk. Its central claim is that the product of several independent random-feature factorizations remains an unbiased estimator of K whenever the modulation function is obtained by a 2l-fold deconvolution of the kernel coefficients. A second claim is that the termination rule used by earlier random-feature methods can be replaced by any walk-length distribution, with a simple reweighting by the survival probability, without breaking unbiasedness and with better accuracy at fixed average length. If these claims hold, long-walk sampling can be traded for parallel short walks plus matrix multiplications, making kernel approximation of large, high-diameter graphs practical on parallel hardware. The paper's monotone-improvement theorem over stitching degree rests on an appendix inequality asserted without derivation.

Core claim

The paper's central discovery is that the product of several independently estimated low-rank GRF factors is an unbiased estimator of the original graph kernel, as long as the modulation function satisfies a 2l-fold convolution identity. This means a long random walk can be replaced by l pairs of shorter walks that meet at intermediate proxy nodes, and the concatenation is mathematically equivalent in expectation. The same identity survives when walk lengths are drawn from any efficiently samplable distribution via reweighting by the inverse survival probability. The paper further claims that stitching more walks monotonically decreases mean squared error for degrees that are powers of two,

What carries the argument

The central object is the walk-stitching factorization K_α(W) = E[∏_{i=1}^l K_1^{(i)}(K_2^{(i)})^T]. The identity that carries the argument is the 2l-fold discrete convolution condition α_k = Σ_{p1+...+p2l=k} f(p1)...f(p2l); equivalently, the modulation function f is the coefficient sequence of the 2l-th root of the kernel's generating function g(x) = Σ α_k x^k. For the diffusion kernel g(x) = exp(λx), this gives f(p) = 1/((2l)^p p!). Coupled with Algorithm 2's reweighting by τ(k) = P(X ≥ k), this decouples the walk-length distribution from the kernel coefficients and makes the product an unbiased estimator.

Load-bearing premise

The improvement claim collapses if more stitching does not lower error at the same sampling budget; the proof of that monotonicity is the weakest link because the appendix's key inequality (Eq. 18) is asserted without derivation, Eqs. (16)-(17) contain undefined indices, and the informal claim that degree-ceiling(r/2) stitching emulates length-r walks with probability independent of the next-step probability is unproved.

What would settle it

Run the paper's diffusion-kernel experiment on a fixed graph with a fixed number of random walks and halting rule, then over many independent runs measure Frobenius error for stitching degrees 1, 2, 4, and 8. If degree 2 is not below degree 1, or degree 4 below degree 2, at identical total budget, the monotone-improvement theorem is false. A second check is to expand both sides of Eq. (18) on a small graph and verify the claimed inequality numerically.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Any graph kernel of the form Σ α_k W^k can be unbiasedly approximated with a product of l stitched GRF factors, provided the modulation function is obtained by 2l-fold deconvolution; for diffusion kernels that function takes a simple closed form.
  • Stitched short walks preserve unbiasedness while replacing sequential long-walk sampling with parallel short-walk sampling and matrix multiplications, which is better suited to modern accelerators.
  • The walk-length distribution need not be the fixed-halting-probability rule; any distribution P works if loads are reweighted by 1/P(X ≥ k), potentially giving more accurate kernels at matched average length.
  • The paper's experiments report lower Frobenius approximation error, better estimates on distant node pairs, and gains in node clustering, graph classification, and mesh normal prediction when stitching is used.
  • Because the stitched factors can reuse the same set of random walks in practice, the technique can deliver accuracy improvements even without sampling additional walks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the monotonicity theorem holds, walk-stitching is a general variance-reduction scheme: any matrix function with a convenient root could be factorized into short-path products, suggesting extensions beyond graph kernels to other matrix functions such as regularized inverses or cosines.
  • The general termination distribution opens a possible route to learning walk-length distributions per graph or task, since the paper's reweighting identity does not depend on the distribution being fixed in advance.
  • The empirical observation that reusing the same walk set still helps suggests that in iterative or streaming settings, walks could be sampled once and recombined at multiple stitching degrees, lowering total sampling cost.
  • A natural testable extension is to apply the deconvolution recipe to kernels whose generating function is not a simple exponential, checking whether the closed-form modulation functions remain easy to compute and whether the accuracy gains persist.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

5 major / 4 minor

Summary. The paper proposes GRFs++ (refined graph random features), a method for unbiased low-rank approximation of graph node kernels of the form Kα(W)=Σ_k α_k W^k. The main ingredients are (i) a walk-stitching procedure that replaces one long random walk by a product of l independent short-walk feature matrices, and (ii) a generalization of the Bernoulli walk-termination scheme to arbitrary walk-length distributions P. The central unbiasedness condition is Eq. (4): the modulation function f must be a 2l-fold self-convolution root of the kernel coefficient sequence α. The paper claims that stitching more walks monotonically reduces MSE (Theorem 3.3), that degree-2 MSE has a closed form (Lemma 3.2), and that the method is more accurate and faster than regular GRFs, with experiments on kernel approximation, graph classification, clustering, and mesh normal prediction.

Significance. If fully established, the walk-stitching idea is a valuable contribution: it replaces sequential sampling of long random walks with parallel short walks and matrix products, and the general termination scheme (Algorithm 2) is a clean extension of the GRF framework. The unbiasedness computation behind Lemma 3.1 is straightforward and appears correct: the 2l-fold convolution condition in Eq. (4) is exactly what is needed for the product of l independent K1^(i)(K2^(i))^T factors to estimate Σ α_k W^k in expectation. The paper is also commendable for deriving f from the kernel's generating function rather than fitting it to data. However, the theoretical support for the headline 'more accurate without extra computational cost' is not currently established: the proof of the monotone-MSE theorem is not checkable as written, and the degree-2 MSE lemma relies on a false symmetry assumption. The empirical evidence is suggestive but incomplete (only the diffusion kernel, no error bars, and a biased walk-reuse ablation).

major comments (5)
  1. [Appendix A.2, Eq. (14), item 5] The proof of Lemma 3.2 is invalid. It uses the symmetry of X1 and X2 to write E[tr(X1^T X1 X2 X2^T)] = tr(E[X1^2 X2^2]). But X_i = K1^(i)(K2^(i))^T is not symmetric: its (a,b) entry is the dot product of the random feature vector at a in K1^(i) with the random feature vector at b in K2^(i), and these two vectors are independent and have different row distributions. Thus X_i(a,b) ≠ X_i(b,a) in general. The MSE formula in Eq. (8)/(13) is therefore not established. This is a load-bearing error because Lemma 3.2 is the only quantitative variance result for degree 2.
  2. [Appendix A.3, Theorem 3.3] The proof of the monotone-MSE claim is not verifiable as written. The key inequality in Eq. (18) is asserted to 'follow from the convolutional properties of the modulation function f' without any derivation. Moreover, Eqs. (16)–(17) contain undefined and inconsistent notation: l is used both as the stitching degree and as a length variable, v_{2l} appears without definition, and the index ranges for p_i, v_i, and u_i are unclear. Because Theorem 3.3 is the theoretical basis for the central claim that higher stitching degree improves accuracy at no extra cost, the proof must be supplied in full or the claim must be substantially weakened.
  3. [Section 2.2.1, diffusion kernel formula] For the diffusion kernel Kα(W)=exp(λW), the paper states that the modulation function is f(p)=1/((2l)^p p!). The correct Taylor coefficient of exp(λx/(2l)) is λ^p/((2l)^p p!). As written, the formula omits λ^p, so Eq. (4) is not satisfied for λ≠1 and the estimator is not unbiased. Since the experiments perform a sweep over kernel widths (e.g., Appendix B.2), this is not a purely cosmetic issue.
  4. [Section 2.2.3, 'Walk-stitching with general termination strategies'] The informal claim that stitching degree ⌈r/2⌉ emulates a length-r walk with probability lower-bounded independently of p_next is stated without proof and appears too strong when stitched segments have length at least 2. A precise statement, a proof, or a clear hedge is needed; as written this motivational claim cannot be checked.
  5. [Section 4, Fig. 4 and Table 5] The ablation labeled 're-using the same set of random walks' (GRF++r) is not an unbiased estimator of the kernel, as the paper itself notes. Reporting it as evidence that walk-stitching 'pinpoints the effectiveness' or 'provides additional computational gains' is misleading unless it is explicitly presented as a heuristic diagnostic. Additionally, Figs. 2–4 report no error bars despite stating s=10 repetitions, so the statistical significance of the empirical improvements cannot be assessed.
minor comments (4)
  1. [Section 3 / Conclusion] The text promises 'concentration results' (Sec. 3 introduction and Conclusion) but no concentration theorem or proof appears in the main text or the Appendix. Either provide such results or remove the claim.
  2. [Theorem 3.3 statement] The theorem is stated only for degrees that are powers of two, yet the abstract and introduction suggest a general monotonicity in l. The scope should be stated explicitly in the main text.
  3. [Eq. (5)–(6)] The definition of X,Y in Option I is correct but terse; a small example for l=2 and l=3 would improve readability.
  4. [Algorithm 2] The notation (P(X ≥ k)) is used for the survival function τ(k), but the text later writes 1/τ(k) without defining the convention at τ(k)=0. For distributions with finite support, the reweighting needs a precise convention.

Circularity Check

0 steps flagged

No significant circularity: GRFs++ construction is parameter-free, and the kernel target is not reused as an input.

full rationale

The central derivation is a constructive design, not a fitted equivalence. The modulation function f is computed from the kernel coefficients α_k (closed form for diffusion kernels, Taylor-root method for general kernels), and unbiasedness then follows from the 2l-fold convolution identity (Eq. 4 applied through Eq. 12). This is a mathematical construction rather than a case where the target quantity is defined in terms of the estimator or where a fitted parameter is relabeled as a prediction; hyperparameters l, P, and m are user-set, and no parameter is fit to the kernel values being approximated. The only load-bearing external result is the base GRF unbiasedness theorem from Reid et al. 2024b, which is a peer-reviewed, code-backed prior result by overlapping authors; moreover, the appendix re-derives the generalized version for Algorithm 2 (App. A.1, Eqs. 10-12), so the reliance is independent support rather than an unverified self-citation chain. The proof gaps flagged by the skeptic—the asserted inequality Eq. 18 in Theorem 3.3 and the invalid symmetry step in Lemma 3.2—are correctness risks and prevent the theoretical claims from being fully verified as written, but they are not examples of circular reasoning: they do not reduce the theorem to its inputs by definition, nor do they involve fitting the estimator to the target. Empirical plots compare against exact kernel matrices, providing external validation. Accordingly, no circular step is identified.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

The unbiasedness of GRFs++ is self-contained given the regular-GRF unbiasedness theorem from the authors' prior work (Reid et al. 2024b), which is a parameter-free derivation with stated assumptions. The paper introduces no fitted constants into its derivations; l, P, m, p_halt are user-set hyperparameters. The main unstated load-bearing input is the assertion (Sec. 3.1) that the 2l-th convolution root of the kernel's coefficient sequence can always be computed efficiently/stably; this is shown in closed form only for the diffusion kernel, and all experiments use that kernel.

free parameters (3)
  • stitching degree l = 2 in most experiments; swept over {1,...,6}
    User-selected hyperparameter of the mechanism (Sec. 2.2.3). The theoretical unbiasedness holds for any l, but reported gains and estimator complexity scale with l; downstream tasks fix l=2 (App. B.2-B.4).
  • walk-length distribution P = Poisson with mean matched to the Bernoulli baseline (Fig. 3)
    The general termination scheme is unbiased for any P, but the empirical accuracy gains are demonstrated only for a Poisson choice matched to the Bernoulli budget (Sec. 4.1).
  • halting probability p_halt / number of walks m = p_halt = 0.1, m ∈ {4,8,16,256} depending on experiment
    Inherited from regular GRFs; chosen per experiment (App. B). Large-diameter experiments use p_halt = 0.1; speed experiments scale p_halt by degree to equalize expected walk length (Fig. 5).
axioms (4)
  • domain assumption Unbiasedness of regular GRFs with Bernoulli termination (Theorem 2.1 of Reid et al., 2024b)
    The proof of Lemma 3.1 (App. A.1) says 'using similar analysis, as in the proof of Theorem 2.1 from (Reid et al., 2024b)'; the base case of the estimator is taken as established from the authors' prior work.
  • standard math Convergence of K_α(W) = Σ_k α_k W^k for ∥W∥ small enough
    Invoked in Sec. 2.1 to define the kernel; standard analytic functional calculus for weighted adjacency matrices.
  • ad hoc to paper The 2l-th convolution root f of α (Eq. 4) exists and its Taylor coefficients are computable for the kernels of interest
    Sec. 3.1 asserts a 'general mechanism' (compute g^{1/(2l)} and its Taylor series) but gives a closed form only for diffusion kernels; all experiments use diffusion kernels, so generality outside that family is asserted, not demonstrated.
  • domain assumption Independence of walks: walks from different nodes, and the l factor matrices K^(i), are mutually independent
    Used in App. A.1 (Eq. 11, factoring expectations across i) and App. A.2 (independence of X_1 and X_2); this is the standard sampling model for GRFs. The walk-reuse ablation (Fig. 4) explicitly violates it, re-introducing bias.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Computationally-efficient Graph Modeling with Refined Graph Random Features." pith.science (2026). https://pith.science/paper/D7LFAJJB

@misc{pith2026251007716,
  author       = {Pith},
  title        = {Pith review of: Computationally-efficient Graph Modeling with Refined Graph Random Features},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D7LFAJJB}},
  note         = {Machine review of arXiv:2510.07716}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more distant nodes. They reduce dependence on sampling long graph random walks via a novel walk-stitching technique, concatenating several shorter walks without breaking unbiasedness. By applying these techniques, GRFs++ inherit the approximation quality provided by longer walks but with greater efficiency, trading sequential, inefficient sampling of a long walk for parallel computation of short walks and matrix-matrix multiplication. Furthermore, GRFs++ extend the simplistic GRFs walk termination mechanism (Bernoulli schemes with fixed halting probabilities) to a broader class of strategies, applying general distributions on the walks' lengths. This improves the approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase all our claims and complement our results with theoretical analysis.

Figures

Figures reproduced from arXiv: 2510.07716 by Arijit Sehanobish, Avinava Dubey, Isaac Reid, Krzysztof Choromanski.

Figure 1
Figure 1. Figure 1: Pictorial description of the walk-stitching technique. Each rectangular block corresponds to a random walk and red nodes depict vertices where walks meet. The blue nodes are the communi￾cating ones. The thickness of the arrow, depicting a transition from step t to step t+1, indicates the probability that such a transition will occur (a walk can terminate earlier). Top: In regular GRFs, two graph vertices c… view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of different GRF methods for the diffusion kernel estimation. The approxi￾mation error (y-axis) improves with the number of walks m (x-axis) and GRF++ provides a sharper estimate than the previous GRF mechanism. The experiment is repeated s = 10 times. 4 Experiments In this section, we showcase the ability of GRFs++ to efficiently approximate graph node kernels (see Sec. 4.1), including with lar… view at source ↗
Figure 3
Figure 3. Figure 3: Our novel halting policy based on Poisson distribution provides additional gains over the GRF mechanisms. We run the experiment s = 10 times on different graphs of varying sizes. New Termination Strategy: Next, we investigate the benefits a more general (non￾Bernoulli) termination strategy, as described in Sec. 2.2.2. Specifically, we employ a halting probability governed by a Poisson distribution P. For a… view at source ↗
Figure 4
Figure 4. Figure 4: Using the exact same walk as the baseline GRF, re￾peated multiple times, pinpoints the effectiveness of the walk￾stitching algorithm, showing additional computational gains. Re-using the same set of random walks: Fi￾nally, we conduct an abla￾tion study (see [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Speed comparison for various GRF-methods: reg [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Graph classification using the approximate dif￾fusion kernel from GRF++. Our method performs at par with the baseline diffusion kernel and always beats GRFs. Graph Classification : Graph kernels have been widely used for graph classification tasks (Kriege et al., 2020; Nikolentzos et al., 2021). We compare the graph classification results obtained us￾ing the approximate kernel from GRF++ with those from th… view at source ↗
Figure 7
Figure 7. Figure 7: Estimation of the kernel values for distant nodes for the diffusion kernel. GRF++ provides a more accurate estimation in various graphs of large diameters. B.1 Accurate estimation of Graph Kernels We follow the exact setup as (Reid et al., 2024b). For computational comparison we used a randomly generated connected graph with 500 nodes. To have fair comparison we derived the relevant phalt = pbase ∗ degree … view at source ↗
Figure 8
Figure 8. Figure 8: As in [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 6 canonical work pages · 2 internal anchors

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Graph spectra as a systematic tool in computational biology

    Anirban Banerjee and J \" u rgen Jost. Graph spectra as a systematic tool in computational biology. Discret. Appl. Math., 157 0 (10): 0 2425--2431, 2009. doi:10.1016/J.DAM.2008.06.033. URL https://doi.org/10.1016/j.dam.2008.06.033

    work page doi:10.1016/j.dam.2008.06.033 2009

  3. [4]

    Graph-based user behavior modeling: From prediction to fraud detection

    Alex Beutel, Leman Akoglu, and Christos Faloutsos. Graph-based user behavior modeling: From prediction to fraud detection. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams (eds.), Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, A...

    arXiv 2015

  4. [5]

    Boosting graph anomaly detection with adaptive message passing

    Jingyan Chen, Guanghui Zhu, Chunfeng Yuan, and Yihua Huang. Boosting graph anomaly detection with adaptive message passing. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024 . OpenReview.net, 2024. URL https://openreview.net/forum?id=CanomFZssu

    2024

  5. [6]

    Taming graph kernels with random features

    Krzysztof Marcin Choromanski. Taming graph kernels with random features. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA , volume 202 of Proceedings of Machine Learning Research, pp.\ 5964--5977....

    2023

  6. [7]

    Fast tree-field integrators: From low displacement rank to topological transformers

    Krzysztof Marcin Choromanski, Arijit Sehanobish, Somnath Basu Roy Chowdhury, Han Lin, Kumar Avinava Dubey, Tamas Sarlos, and Snigdha Chaturvedi. Fast tree-field integrators: From low displacement rank to topological transformers. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=Eok6HbcSRI

    2024

  7. [8]

    Optimal time complexity algorithms for computing general random walk graph kernels on sparse graphs

    Krzysztof Marcin Choromanski, Isaac Reid, Arijit Sehanobish, and Kumar Avinava Dubey. Optimal time complexity algorithms for computing general random walk graph kernels on sparse graphs. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Mohammad Emtiyaz Khan (eds.), International Conference on Artificial Intelligence and Statistics, AISTATS 2025, Mai Kha...

    2025

  8. [9]

    A simple baseline algorithm for graph classification, 2018

    Nathan de Lara and Edouard Pineau. A simple baseline algorithm for graph classification, 2018

    2018

  9. [10]

    Graph convolution network based recommender systems: Learning guarantee and item mixture powered strategy

    Leyan Deng, Defu Lian, Chenwang Wu, and Enhong Chen. Graph convolution network based recommender systems: Learning guarantee and item mixture powered strategy. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing System...

    2022

  10. [11]

    Spacegnn: Multi-space graph neural network for node anomaly detection with extremely limited labels

    Xiangyu Dong, Xingyi Zhang, Lei Chen, Mingxuan Yuan, and Sibo Wang. Spacegnn: Multi-space graph neural network for node anomaly detection with extremely limited labels. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025 . OpenReview.net, 2025. URL https://openreview.net/forum?id=Syt4fWwVm1

    2025

  11. [12]

    Benchmarking graph neural networks

    Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020

    Pith/arXiv arXiv 2003

  12. [13]

    Long range graph benchmark

    Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. URL https://openreview.net/forum?id=in7XC5RcjEn

    2022

  13. [14]

    A fair comparison of graph neural networks for graph classification

    Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In Proceedings of the 8th International Conference on Learning Representations ( ICLR ) , 2020

    2020

  14. [15]

    An introduction to johnson-lindenstrauss transforms

    Casper Benjamin Freksen. An introduction to johnson-lindenstrauss transforms. CoRR, abs/2103.00564, 2021. URL https://arxiv.org/abs/2103.00564

    Pith/arXiv arXiv 2021

  15. [16]

    A survey of graph neural networks for recommender systems: Challenges, methods, and directions

    Chen Gao, Yu Zheng, Nian Li, Yinfeng Li, Yingrong Qin, Jinghua Piao, Yuhan Quan, Jianxin Chang, Depeng Jin, Xiangnan He, and Yong Li. A survey of graph neural networks for recommender systems: Challenges, methods, and directions. Trans. Recomm. Syst., 1 0 (1): 0 1--51, 2023. doi:10.1145/3568022. URL https://doi.org/10.1145/3568022

    doi:10.1145/3568022 2023

  16. [17]

    Do logarithmic proximity measures outperform plain ones in graph clustering? In International Conference on Network Analysis, pp.\ 87--105

    Vladimir Ivashkin and Pavel Chebotarev. Do logarithmic proximity measures outperform plain ones in graph clustering? In International Conference on Network Analysis, pp.\ 87--105. Springer, 2016

    2016

  17. [18]

    Graph anomaly detection with graph neural networks: Current status and challenges

    Hwan Kim, Byung Suk Lee, Won - Yong Shin, and Sungsu Lim. Graph anomaly detection with graph neural networks: Current status and challenges. IEEE Access , 10: 0 111820--111829, 2022. doi:10.1109/ACCESS.2022.3211306. URL https://doi.org/10.1109/ACCESS.2022.3211306

    arXiv 2022

  18. [19]

    Label-based graph augmentation with metapath for graph anomaly detection

    Hwan Kim, Junghoon Kim, Byung Suk Lee, and Sungsu Lim. Label-based graph augmentation with metapath for graph anomaly detection. Expert Syst. Appl., 296: 0 129087, 2026. doi:10.1016/J.ESWA.2025.129087. URL https://doi.org/10.1016/j.eswa.2025.129087

    arXiv 2026

  19. [20]

    Lafferty

    Risi Kondor and John D. Lafferty. Diffusion kernels on graphs and other discrete input spaces. In Claude Sammut and Achim G. Hoffmann (eds.), Machine Learning, Proceedings of the Nineteenth International Conference (ICML 2002), University of New South Wales, Sydney, Australia, July 8-12, 2002 , pp.\ 315--322. Morgan Kaufmann, 2002

    2002

  20. [21]

    Kriege, Fredrik D

    Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5 0 (1), January 2020. ISSN 2364-8228. doi:10.1007/s41109-019-0195-3. URL http://dx.doi.org/10.1007/s41109-019-0195-3

    work page doi:10.1007/s41109-019-0195-3 2020

  21. [22]

    Diffgad: A diffusion-based unsupervised graph anomaly detector

    Jinghan Li, Yuan Gao, Jinda Lu, Junfeng Fang, Congcong Wen, Hui Lin, and Xiang Wang. Diffgad: A diffusion-based unsupervised graph anomaly detector. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025 . OpenReview.net, 2025. URL https://openreview.net/forum?id=AhcYq4CnfF

    2025

  22. [23]

    Towards self-interpretable graph-level anomaly detection

    Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. Towards self-interpretable graph-level anomaly detection. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS...

    2023

  23. [24]

    Molecule Graph Networks with Many-body Equivariant Interactions

    Zetian Mao, Jiawen Li, Chen Liang, Diptesh Das, Masato Sumita, and Koji Tsuda. Molecule graph networks with many-body equivariant interactions. CoRR, abs/2406.13265, 2024. doi:10.48550/ARXIV.2406.13265. URL https://doi.org/10.48550/arXiv.2406.13265

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2406.13265 2024

  24. [25]

    Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann

    Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www.graphlearning.io

    2020

  25. [26]

    Graph kernels: A survey

    Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. Journal of Artificial Intelligence Research, 72: 0 943–1027, November 2021. ISSN 1076-9757. doi:10.1613/jair.1.13225. URL http://dx.doi.org/10.1613/jair.1.13225

    work page doi:10.1613/jair.1.13225 2021

  26. [27]

    Noble and Diane J

    Caleb C. Noble and Diane J. Cook. Graph-based anomaly detection. In Lise Getoor, Ted E. Senator, Pedro M. Domingos, and Christos Faloutsos (eds.), Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 - 27, 2003 , pp.\ 631--636. ACM , 2003. doi:10.1145/956750.956831. URL https:/...

    arXiv 2003

  27. [28]

    Quasi-monte carlo graph random features

    Isaac Reid, Adrian Weller, and Krzysztof Marcin Choromanski. Quasi-monte carlo graph random features. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, D...

    2023

  28. [29]

    Repelling random walks

    Isaac Reid, Eli Berger, Krzysztof Marcin Choromanski, and Adrian Weller. Repelling random walks. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024 . OpenReview.net, 2024 a . URL https://openreview.net/forum?id=31IOmrnoP4

    2024

  29. [30]

    General graph random features

    Isaac Reid, Krzysztof Marcin Choromanski, Eli Berger, and Adrian Weller. General graph random features. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024 . OpenReview.net, 2024 b . URL https://openreview.net/forum?id=viftsX50Rt

    2024

  30. [31]

    Whitney, Amr Ahmed, Joshua Ainslie, Alex Bewley, Mithun George Jacob, Aranyak Mehta, David Rendleman, Connor Schenck, Richard E

    Isaac Reid, Kumar Avinava Dubey, Deepali Jain, William F. Whitney, Amr Ahmed, Joshua Ainslie, Alex Bewley, Mithun George Jacob, Aranyak Mehta, David Rendleman, Connor Schenck, Richard E. Turner, Ren \' e Wagner, Adrian Weller, and Krzysztof Marcin Choromanski. Linear transformer topological masking with graph random features. In The Thirteenth Internation...

    2025

  31. [32]

    Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. Efficient graphlet kernels for large graph comparison. In David A. Van Dyk and Max Welling (eds.), Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, AISTATS 2009, Clearwater Beach, Florida, USA, April 16-18, 2009 , ...

    2009

  32. [33]

    Smola and Risi Kondor

    Alexander J. Smola and Risi Kondor. Kernels and regularization on graphs. In Bernhard Sch \" o lkopf and Manfred K. Warmuth (eds.), Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lectur...

    work page doi:10.1007/978-3-540-45167-9 2003

  33. [34]

    S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. J. Mach. Learn. Res., 11: 0 1201--1242, 2010. doi:10.5555/1756006.1859891. URL https://dl.acm.org/doi/10.5555/1756006.1859891

    arXiv 2010

  34. [35]

    Aggarwal

    Lingfei Wu, Ian En - Hsu Yen, Zhen Zhang, Kun Xu, Liang Zhao, Xi Peng, Yinglong Xia, and Charu C. Aggarwal. Scalable global alignment graph kernel using random features: From node embedding to graph embedding. In Ankur Teredesai, Vipin Kumar, Ying Li, R \' o mer Rosales, Evimaria Terzi, and George Karypis (eds.), Proceedings of the 25th ACM SIGKDD Interna...

    arXiv 2019

  35. [36]

    Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams (eds.), Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015 , pp.\ 1365--1374. ACM , 2015. d...

    arXiv 2015

  36. [37]

    An empirical study towards prompt-tuning for graph contrastive pre-training in recommendations

    Haoran Yang, Xiangyu Zhao, Yicong Li, Hongxu Chen, and Guandong Xu. An empirical study towards prompt-tuning for graph contrastive pre-training in recommendations. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information ...

    2023

  37. [38]

    Hgformer: Hyperbolic Graph Transformer for Recommendation

    Xin Yang, Xingrun Li, Heng Chang, Jinze Yang, Xihong Yang, Shengyu Tao, Ningkang Chang, Maiko Shigeno, Junfeng Wang, Dawei Yin, and Erxue Min. Hgformer: Hyperbolic graph transformer for recommendation. ICML 2025, abs/2502.15693, 2025. doi:10.48550/ARXIV.2502.15693. URL https://doi.org/10.48550/arXiv.2502.15693

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2502.15693 2025

  38. [39]

    geometric\_shapes : Representation of geometric shapes

    Yannick-S. geometric\_shapes : Representation of geometric shapes. https://github.com/Yannick-S/geometric_shapes, 2025. Commit snapshot as of

    2025

  39. [40]

    Equipocket: an e(3)-equivariant geometric graph neural network for ligand binding site prediction

    Yang Zhang, Zhewei Wei, Ye Yuan, Chongxuan Li, and Wenbing Huang. Equipocket: an e(3)-equivariant geometric graph neural network for ligand binding site prediction. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 . OpenReview.net, 2024. URL https://openreview.net/forum?id=1vGN3CSxVs

    2024

  40. [41]

    Thingi10k: A dataset of 10,000 3d-printing models

    Qingnan Zhou and Alec Jacobson. Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797, 2016

    Pith/arXiv arXiv 2016

  41. [42]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should not add it explicitly Type <Return> for now, but then later remove the command n...

  42. [43]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@first@sw \@firstoftwo \@ifundefined NAT@b*@#2 \@firstoftwo @num @NAT@ctr \@secondoft...

  43. [44]

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibsetup #1 @NAT@ctr @ @openbib .11em \@plus.33em \@minus.07em 4000 4000 `\.\@m @bibit...

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.