Manifold Random Features

Ananya Parashar, Derek Long, Dwaipayan Saha, Krzysztof Choromański

TL;DR

Manifold Random Features (MRFs) provide a new way to approximate complex functions (kernels) on curved surfaces by training neural networks to "mimic" random walks on graphs. This approach yields positive, bounded features that are significantly faster than traditional spectral methods, offering up to 60x speedups for tasks like 3D mesh interpolation.

What Problem Does This Paper Address?

In machine learning, "kernel methods" allow us to model complex, non-linear relationships by effectively mapping data into high-dimensional spaces. However, these methods usually scale poorly—calculating a kernel matrix for $N$ points takes $O(N^2)$ time and memory, which becomes impossible for large datasets or high-resolution 3D meshes.

"Random Features" (RFs) solve this by approximating the kernel as a simple dot product of two low-dimensional vectors. While we have great RF recipes for flat, Euclidean spaces (like the standard Gaussian kernel), things get messy when data lives on a manifold (a curved surface like a sphere, a torus, or a complex 3D engine part). Finding analytical RF mappings for these geometries is often mathematically impossible. Researchers usually fall back on "spectral decomposition," which involves solving complex differential equations—a process that is computationally heavy and doesn't scale.

Methods

The authors introduce Manifold Random Features (MRFs), a paradigm that uses discrete graph theory to solve continuous geometric problems.

  1. Discretization: They first turn the continuous manifold into a dense graph (a mesh or point cloud).
  2. Graph Random Features (GRFs) as Teachers: They use a recently developed technique called GRFs to generate "signature vectors" based on random walks on this graph. These vectors act as a discrete ground truth.
  3. Neural Supervision: They train a small neural network (a "g-function") to regress these signature vectors. Essentially, the network learns the "field" of the manifold.
  4. Continuous Inference: Once trained, this network can produce feature vectors for any point on the manifold, not just the original grid points.

Unlike standard trigonometric random features, MRFs are positive and bounded. This is a crucial property for stability in modern architectures like linear-attention Transformers.

Datasets

The paper validates the method across several geometric scenarios:

  • Synthetic Manifolds: Standard mathematical shapes including the Sphere, Ellipsoid, Torus, and the non-orientable Mobius Strip.
  • Thingi10k: A large-scale dataset of 10,000 3D-printing models used to test vertex normal prediction on complex, "real-world" rigid objects.
  • flag_simple: A dataset of cloth simulations used to evaluate the prediction of velocity fields on deforming meshes.

Key Insights and Ideas

  • The Combinatorial-Continuous Bridge: The most striking theoretical finding is that as a graph grid becomes infinitely fine, the discrete random walks (GRFs) converge exactly to the continuous heat kernel of the manifold.
  • Rediscovering the Gaussian: The authors show that by applying their graph-based method to a simple Euclidean grid, they "re-discover" the Gaussian kernel. This suggests that many classic continuous kernels can be viewed as the limit of simple discrete processes.
  • Bypassing the "Spectral Wall": Traditional methods require calculating eigenvectors of a Laplacian matrix, which hits a memory wall at around $10^5$ vertices. Because MRFs use a fixed training budget and local random walks, they bypass this bottleneck entirely.

Key Results

  • Massive Speedups: In inference tests, MRFs were 37x to 61x faster than baseline spectral decomposition methods across various manifolds.
  • High Fidelity: The approximations achieved $R^2$ values between 0.983 and 0.997, meaning they captured nearly all the variance of the true heat kernels.
  • Robust Interpolation: On the Thingi10k dataset, the model successfully predicted 80% of missing vertex normals with high cosine similarity, proving it can handle the "messy" geometry of real-world CAD models.
  • Scalability: For large meshes (approx. 50k vertices), kernel construction took nearly 3,000 seconds for the baseline, while the MRF approach (data generation + training) took only 171 seconds.

Limitations and Future Work

  • Preprocessing Overhead: While inference is lightning-fast, there is an upfront cost to discretizing the manifold and training the neural network. This makes the method best suited for scenarios where the manifold is fixed (like a specific 3D character or a geographical map) and many queries are needed.
  • Geodesic Inputs: The current neural network architecture often relies on an approximation of the geodesic distance (the shortest path along the surface) between points, which itself can be expensive to compute for very complex shapes.
  • Generalization: The paper focuses on learning features for a specific manifold. A promising future direction is "Meta-MRFs"—models that can generalize across different manifolds without needing to be retrained from scratch for every new shape.

Summary updated

Abstract

We present a new paradigm for creating random features to approximate bi-variate functions (in particular, kernels) defined on general manifolds. This new mechanism of Manifold Random Features (MRFs) leverages discretization of the manifold and the recently introduced technique of Graph Random Features (GRFs) to learn continuous fields on manifolds. Those fields are used to find continuous approximation mechanisms that otherwise, in general scenarios, cannot be derived analytically. MRFs provide positive and bounded features, a key property for accurate, low-variance approximation. We show deep asymptotic connection between GRFs, defined on discrete graph objects, and continuous random features used for regular kernels. As a by-product of our method, we re-discover recently introduced mechanism of Gaussian kernel approximation applied in particular to improve linear-attention Transformers, considering simple random walks on graphs and by-passing original complex mathematical computations. We complement our algorithm with a rigorous theoretical analysis and verify in thorough experimental studies.
BibTeX
@misc{parashar2026manifold,
  author = {Ananya Parashar and Derek Long and Dwaipayan Saha and Krzysztof Choromański},
  title = {{Manifold Random Features}},
  year = {2026},
  eprint = {2602.03797},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.03797},
}
Figure