Taming graph kernels with random features
- URL: http://arxiv.org/abs/2305.00156v1
- Date: Sat, 29 Apr 2023 03:04:49 GMT
- Title: Taming graph kernels with random features
- Authors: Krzysztof Choromanski
- Abstract summary: 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.
- Score: 17.482280753348288
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce in this paper the mechanism of graph random features (GRFs).
GRFs can be used to construct unbiased randomized estimators of several
important kernels defined on graphs' nodes, in particular the regularized
Laplacian kernel. As regular RFs for non-graph kernels, they provide means to
scale up kernel methods defined on graphs to larger networks. Importantly, they
give substantial computational gains also for smaller graphs, while applied in
downstream applications. Consequently, GRFs address the notoriously difficult
problem of cubic (in the number of the nodes of the graph) time complexity of
graph kernels algorithms. We provide a detailed theoretical analysis of GRFs
and an extensive empirical evaluation: from speed tests, through Frobenius
relative error analysis to kmeans graph-clustering with graph kernels. We show
that the computation of GRFs admits an embarrassingly simple distributed
algorithm that can be applied if the graph under consideration needs to be
split across several machines. We also introduce a (still unbiased) quasi Monte
Carlo variant of GRFs, q-GRFs, relying on the so-called reinforced random
walks, that might be used to optimize the variance of GRFs. As a byproduct, we
obtain a novel approach to solve certain classes of linear equations with
positive and symmetric matrices.
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) - 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) - Analysis and Approximate Inference of Large Random Kronecker Graphs [4.417282202068703]
We show that the adjacency of a large random Kronecker graph can be decomposed.
We propose a denoise-and-solve'' approach to infer the key graph parameters.
arXiv Detail & Related papers (2023-06-14T13:09:38Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
We propose a novel distance between distributions and signals on graphs.
GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation.
We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
arXiv Detail & Related papers (2023-06-05T00:01:17Z) - 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) - Graph Neural Network Bandits [89.31889875864599]
We consider the bandit optimization problem with the reward function defined over graph-structured data.
Key challenges in this setting are scaling to large domains, and to graphs with many nodes.
We show that graph neural networks (GNNs) can be used to estimate the reward function.
arXiv Detail & Related papers (2022-07-13T18:12:36Z) - Graph Based Gaussian Processes on Restricted Domains [13.416168979487118]
In nonparametric regression, it is common for the inputs to fall in a restricted subset of Euclidean space.
We propose a new class of Graph Laplacian based GPs (GL-GPs) which learn a covariance that respects the geometry of the input domain.
We provide substantial theoretical support for the GL-GP methodology, and illustrate performance gains in various applications.
arXiv Detail & Related papers (2020-10-14T17:01:29Z) - Dirichlet Graph Variational Autoencoder [65.94744123832338]
We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors.
Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
arXiv Detail & Related papers (2020-10-09T07:35:26Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN)
We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE)
EGAE consists of one encoder and dual decoders.
arXiv Detail & Related papers (2020-02-20T09:53:28Z) - 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.