mlsanityData to 14 Oct 2026

Computationally-efficient Graph Modeling with Refined Graph Random Features

arXiv 2510.07716 ↗First posted 9 Oct 2025cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 31 of its 51 references that are in the map. First posted on arXiv 9 Oct 2025.

Builds on

31 of 51 references.

References · 31

  1. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  5. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  6. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  7. 2020Benchmarking Graph Neural Networkscited by 680
  8. 2022Long Range Graph Benchmarkcited by 263
  9. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  10. 2016Thingi10K: A Dataset of 10,000 3D-Printing Modelscited by 183
  11. 2019A Survey on Graph Kernelscited by 148
  12. 2021A Survey of Graph Neural Networks for Recommender Systems: Challenges, Methods, and Directionscited by 144
19 more
  1. 2019Graph Kernels: A Surveycited by 44
  2. 2023Towards Self-Interpretable Graph-Level Anomaly Detectioncited by 41
  3. 2022Graph Anomaly Detection with Graph Neural Networks: Current Status and Challengescited by 23
  4. 2023Taming graph kernels with random featurescited by 17
  5. 2025SpaceGNN: Multi-Space Graph Neural Network for Node Anomaly Detection with Extremely Limited Labelscited by 17
  6. 2018A Simple Baseline Algorithm for Graph Classificationcited by 15
  7. 2023EquiPocket: an E(3)-Equivariant Geometric Graph Neural Network for Ligand Binding Site Predictioncited by 15
  8. 2021An Introduction to Johnson-Lindenstrauss Transformscited by 11
  9. 2023General Graph Random Featurescited by 10
  10. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  11. 2024DiffGAD: A Diffusion-based Unsupervised Graph Anomaly Detectorcited by 9
  12. 2019Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embeddingcited by 8
  13. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  14. 2023Repelling Random Walkscited by 6
  15. 2024Molecule Graph Networks with Many-body Equivariant Interactionscited by 3
  16. 2024Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformerscited by 3
  17. 2024Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphscited by 3
  18. 2024Hgformer: Hyperbolic Graph Transformer for Recommendationcited by 2
  19. 2023Label-based Graph Augmentation with Metapath for Graph Anomaly Detectioncited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Manifold Random Featurescited by 1
  2. 2026SWING: Unlocking Implicit Graph Representations for Graph Random Featurescited by 0