Random Wavelet Features for Graph Kernel Machines

• URL: http://arxiv.org/abs/2602.15711v1
• Date: Tue, 17 Feb 2026 16:45:15 GMT
• Title: Random Wavelet Features for Graph Kernel Machines
• Authors: Valentin de Bassompierre, Jean-Charles Delvenne, Laurent Jacques,
• Abstract summary: A key goal is to design node embeddings whose dot products capture meaningful notions of node similarity induced by the graph.<n>Graph kernels offer a principled way to define such similarities, but their direct computation is often prohibitive for large networks.<n>We introduce randomized spectral node embeddings whose dot products estimate a low-rank approximation of any specific graph kernel.
• Score: 4.306374407145905
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Node embeddings map graph vertices into low-dimensional Euclidean spaces while preserving structural information. They are central to tasks such as node classification, link prediction, and signal reconstruction. A key goal is to design node embeddings whose dot products capture meaningful notions of node similarity induced by the graph. Graph kernels offer a principled way to define such similarities, but their direct computation is often prohibitive for large networks. Inspired by random feature methods for kernel approximation in Euclidean spaces, we introduce randomized spectral node embeddings whose dot products estimate a low-rank approximation of any specific graph kernel. We provide theoretical and empirical results showing that our embeddings achieve more accurate kernel approximations than existing methods, particularly for spectrally localized kernels. These results demonstrate the effectiveness of randomized spectral constructions for scalable and principled graph representation learning.

Related papers

• Metric Graph Kernels via the Tropical Torelli Map [0.0]
  We propose new graph kernels grounded in the study of metric graphs via tropical algebraic geometry.<n>Our graph kernels are based on the geometry and topology of the underlying metric space.<n> Empirically, our kernels outperform existing methods in label-free settings.
  arXiv  Detail & Related papers  (2025-05-17T20:00:50Z)
• 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)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  We propose an efficient feature map construction of the Neural Tangent Kernel (NTK) of fully-connected ReLU network. We show that dimension of the resulting features is much smaller than other baseline feature map constructions to achieve comparable error bounds both in theory and practice.
  arXiv  Detail & Related papers  (2021-04-03T09:08:12Z)
• Neighborhood Preserving Kernels for Attributed Graphs [0.9176056742068812]
  We describe the design of a reproducing kernel suitable for attributed graphs. The similarity between the two graphs is defined based on the neighborhood information of the graph nodes. By incorporating the proposed kernel on support vector machines we analyzed the real-world data sets.
  arXiv  Detail & Related papers  (2020-10-13T09:58:50Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)
• 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.