Research map / Graph learning / Graph algorithms and clustering
General Graph Random Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes general graph random features (g-GRFs), a random-walk estimator with a modulation function that gives unbiased subquadratic estimates of arbitrary power-series functions of a weighted adjacency matrix, and extends it with learnable neural modulation functions for kernel learning.
Problem
Exact graph node kernels (e.g. d-regularised Laplacian, diffusion, p-step random walk, inverse cosine) require O(N^3) computation, and existing graph random features only cover the 2-regularised Laplacian and (asymptotically unbiased) diffusion kernel.
Approach
Insert a modulation function f that reweights each random walker's load by walk length; unbiasedness holds when the convolution f1 * f2 equals the Taylor coefficients alpha of the target kernel, and symmetric f is the square root of the kernel generating function. The modulation function can also be a small neural network trained for kernel approximation or downstream regression.
Key results
- Unbiased g-GRF estimates of popular kernels converge with the number of walkers; relative Frobenius error around 0.005 on a 1000+ node graph in the scalability study, and g-GRFs are 7.8x faster than exact diffusion kernel computation at the largest size tested (N=12800).
- A learned neural modulation function (biased) reduces kernel approximation Frobenius error vs the unbiased f on all 8 graphs at m=16, e.g. eurosis 0.0551 -> 0.0484.
- On triangular mesh kernel regression, the learned kernel gives lower angular prediction error than fixed 1-regularised Laplacian, 2-regularised Laplacian and diffusion kernels on all six test graphs, including the 21384-node cycloidal graph.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train a neural modulation function instead of using the unbiased modulation (ablation) | g-GRF kernel approximation · Small ER, Larger ER, Binary tree, d-regular, Karate, Dolphins, Football, and Eurosis | Frobenius norm error: 0.0488(9) -> 0.0437(9); 0.0503(4) -> 0.0448(4); 0.0453(4) -> 0.0410(4); 0.0490(2) -> 0.0434(2); 0.0492(6) -> 0.0439(6); | Helped |
| Use a learned neural modulation function instead of a fixed 1-reg Laplacian kernel | g-GRF kernel regression · Triangular mesh graphs | Angular prediction error: +0.40(2), +0.81(5), +0.52(2), +0.81(2), +2.13(5), +0.065(4) | Helped |
| Use a learned neural modulation function instead of a fixed 2-reg Laplacian kernel | g-GRF kernel regression · Triangular mesh graphs | Angular prediction error: +0.85(4), +1.78(8), +1.12(1), +1.60(4), +5.3(1), +0.13(1) | Helped |
| Use a learned neural modulation function instead of the diffusion kernel | g-GRF kernel regression · Triangular mesh graphs | Angular prediction error: +0.029(3), +0.059(3), +0.042(2), +0.063(2), +0.067(2), +0.011(1) | Helped |
| Increase the number of random walkers | g-GRF kernel estimation · Eight graph datasets and four graph kernels | Relative Frobenius norm error | Helped |
| Increase the number of random walkers | g-GRF graph ODE simulation · Three real-world graphs | Normalized final-state error | Helped |
| Use g-GRF approximation for exp(σ²W) in k-means | Kernelised graph node clustering · Karate, Dolphins, Polbooks, Football, Databases, Eurosis, Cora, and Citeseer | Clustering error | Helped |
Surprising findings
- The learned neural modulation function converges to a biased f that gives lower MSE than the unbiased modulation function, because downweighting long walks reduces variance.
- Trained on the small cylinder graph, the learned modulation function generalises to graphs up to 21k nodes with different topologies.
Limitations
- Learned modulation functions are biased, so unbiasedness is lost and the bias depends on the number of walkers m.
- Asymmetric modulation pairs double parameters and training cost; optimal choice of (f1,f2) left open.
- Generalisation bound depends on spectral radius of W and is noted as not tight for general graphs.
Experimental setup
Datasets: karate dolphins football eurosis polbooks databases cora citeseer cylinder/teapot/idler-riser/busted/torus/cycloidal triangular mesh graphs synthetic Erdos-Renyi graphs
Benchmarks: karate dolphins football eurosis polbooks databases cora citeseer triangular mesh normal prediction graphs
Metrics: relative Frobenius norm error clustering error E_c Frobenius norm error on kernel estimate normalised difference in angular prediction error wall-clock time relative ODE state error
Baselines: exact graph kernel computation (matrix exponential / inversion) original GRFs (2-regularised Laplacian) fixed modulation functions (unbiased f)
Builds on: graph random features (GRFs) random Fourier features
Closest papers by meaning
- Taming graph kernels with random features (ICML 2023 · similarity 0.95)
- Computationally-efficient Graph Modeling with Refined Graph Random Features (ICML 2026 · similarity 0.93)
- Manifold Random Features (NeurIPS 2026 · similarity 0.90)
- RetGK: Graph Kernels based on Return Probabilities of Random Walks (NeurIPS 2018 · similarity 0.90)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.86)
- Revisiting Random Walks for Learning on Graphs (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.