Computationally-efficient Graph Modeling with Refined Graph Random Features

• URL: http://arxiv.org/abs/2510.07716v1
• Date: Thu, 09 Oct 2025 02:53:26 GMT
• Title: Computationally-efficient Graph Modeling with Refined Graph Random Features
• Authors: Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish, Isaac Reid,
• Abstract summary: We propose a new class of Graph Random Features (GRFs) for efficient and accurate computations.<n>GRFs++ resolve some of the long-standing limitations of regular GRFs.<n>They reduce dependence on sampling long graph random walks via a novel walk-stitching technique.
• Score: 13.71262071974362
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Efficient Graph Condensation via Gaussian Process [8.099774846541438]
  Graph condensation reduces the size of large graphs while preserving performance.<n>Existing methods often rely on bi-level optimization, requiring extensive GNN training and limiting their scalability.<n>This paper proposes Graph Condensation via Gaussian Process (GCGP), a novel and computationally efficient approach to graph condensation.
  arXiv  Detail & Related papers  (2025-01-05T14:43:07Z)
• Learning Long Range Dependencies on Graphs via Random Walks [6.7864586321550595]
  Message-passing graph neural networks (GNNs) excel at capturing local relationships but struggle with long-range dependencies in graphs. graph transformers (GTs) enable global information exchange but often oversimplify the graph structure by representing graphs as sets of fixed-length vectors. This work introduces a novel architecture that overcomes the shortcomings of both approaches by combining the long-range information of random walks with local message passing.
  arXiv  Detail & Related papers  (2024-06-05T15:36:57Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  We introduce SparseDiff, a novel diffusion model based on the observation that almost all large graphs are sparse. By selecting a subset of edges, SparseDiff effectively leverages sparse graph representations both during the noising process and within the denoising network. Our model demonstrates state-of-the-art performance across multiple metrics on both small and large datasets.
  arXiv  Detail & Related papers  (2023-11-03T16:50:26Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Quasi-Monte Carlo Graph Random Features [38.762964164013226]
  We present a novel mechanism to improve the accuracy of graph random features (GRFs) Our method induces negative correlations between the lengths of the algorithm's random walks by imposing antithetic termination. We derive strong theoretical guarantees on the properties of these quasi-Monte Carlo GRFs.
  arXiv  Detail & Related papers  (2023-05-21T14:12:02Z)
• Taming graph kernels with random features [17.482280753348288]
  We introduce the mechanism of graph random features (GRFs) GRFs can be used to construct unbiased randomized estimators of several important kernels defined on graphs' nodes.
  arXiv  Detail & Related papers  (2023-04-29T03:04:49Z)
• OrthoReg: Improving Graph-regularized MLPs via Orthogonality Regularization [66.30021126251725]
  Graph Neural Networks (GNNs) are currently dominating in modeling graphstructure data. Graph-regularized networks (GR-MLPs) implicitly inject the graph structure information into model weights, while their performance can hardly match that of GNNs in most tasks. We show that GR-MLPs suffer from dimensional collapse, a phenomenon in which the largest a few eigenvalues dominate the embedding space. We propose OrthoReg, a novel GR-MLP model to mitigate the dimensional collapse issue.
  arXiv  Detail & Related papers  (2023-01-31T21:20:48Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGAT is a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks.
  arXiv  Detail & Related papers  (2020-06-15T22:07:54Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Gated Graph Recurrent Neural Networks [176.3960927323358]
  We introduce Graph Recurrent Neural Networks (GRNNs) as a general learning framework for graph processes. To address the problem of vanishing gradients, we put forward GRNNs with three different gating mechanisms: time, node and edge gates. The numerical results also show that GRNNs outperform GNNs and RNNs, highlighting the importance of taking both the temporal and graph structures of a graph process into account.
  arXiv  Detail & Related papers  (2020-02-03T22:35:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.