Quasi-Monte Carlo Graph Random Features

• URL: http://arxiv.org/abs/2305.12470v1
• Date: Sun, 21 May 2023 14:12:02 GMT
• Title: Quasi-Monte Carlo Graph Random Features
• Authors: Isaac Reid, Krzysztof Choromanski, Adrian Weller
• Abstract summary: 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.
• Score: 38.762964164013226
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel mechanism to improve the accuracy of the recently-introduced class of graph random features (GRFs). Our method induces negative correlations between the lengths of the algorithm's random walks by imposing antithetic termination: a procedure to sample more diverse random walks which may be of independent interest. It has a trivial drop-in implementation. We derive strong theoretical guarantees on the properties of these quasi-Monte Carlo GRFs (q-GRFs), proving that they yield lower-variance estimators of the 2-regularised Laplacian kernel under mild conditions. Remarkably, our results hold for any graph topology. We demonstrate empirical accuracy improvements on a variety of tasks including a new practical application: time-efficient approximation of the graph diffusion process. To our knowledge, q-GRFs constitute the first rigorously studied quasi-Monte Carlo scheme for kernels defined on combinatorial objects, inviting new research on correlations between graph random walks.

Related papers

• Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective [0.0]
  We build upon a recently introduced class of quasi-graph random features (q-GRFs) We find that the Diffusion kernel performs most similarly to the 2-regularized Laplacian. We explore graph types that benefit from the previously established antithetic termination procedure.
  arXiv  Detail & Related papers  (2024-10-10T21:51:31Z)
• von Mises Quasi-Processes for Bayesian Circular Regression [57.88921637944379]
  We explore a family of expressive and interpretable distributions over circle-valued random functions. The resulting probability model has connections with continuous spin models in statistical physics. For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Markov Chain Monte Carlo sampling.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
  arXiv  Detail & Related papers  (2024-05-26T12:25:09Z)
• General Graph Random Features [42.75616308187867]
  We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation.
  arXiv  Detail & Related papers  (2023-10-07T15:47:31Z)
• Repelling Random Walks [42.75616308187867]
  We present a novel quasi-Monte Carlo mechanism to improve graph-based sampling, coined repelling random walks. We showcase the effectiveness of repelling random walks in a range of settings including estimation of graph kernels, the PageRank vector and graphlet concentrations. To our knowledge, repelling random walks constitute the first rigorously studied quasi-Monte Carlo scheme correlating the directions of walkers on a graph, inviting new research in this exciting nascent domain.
  arXiv  Detail & Related papers  (2023-10-07T15:30:23Z)
• 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)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• From Spectral Graph Convolutions to Large Scale Graph Convolutional Networks [0.0]
  Graph Convolutional Networks (GCNs) have been shown to be a powerful concept that has been successfully applied to a large variety of tasks. We study the theory that paved the way to the definition of GCN, including related parts of classical graph theory.
  arXiv  Detail & Related papers  (2022-07-12T16:57:08Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)
• 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)

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.