Normalizing Diffusion Kernels with Optimal Transport

Nathan Kessler, Robin Magnet, Jean Feydy · 2025

Read Normalizing Diffusion Kernels with Optimal Transport by Nathan Kessler, Robin Magnet, Jean Feydy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-06161.txt.

Introduction

Nathan Kessler, Robin Magnet, and Jean Feydy write a 2025 paper, with the short title Sinkhorn Normalization of Diffusion Kernels, on smoothing signals over uneven data. Smoothing by local links is a core step in learning and shape work. The best tool for it comes from heat spread, but that tool needs a clean domain shape, which real data often lack.

Their fix starts from plain similarity or link tables and rescales them with a balanced form of the Sinkhorn method. The result acts like heat spread and fixes the bias that plain kernels show at edges. The method works on point clouds, sparse grids, and mixed blobs, keeps key traits of the true heat operator, and helps with shape study and matching.

Catalog record

CREATORNathan Kessler, Robin Magnet, Jean Feydy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-06161

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Normalizing Diffusion Kernels with Optimal Transport Nathan Kessler, Robin Magnet, Jean Feydy Abstract Smoothing a signal based on local neighborhoods is a core operation in machine learning and geometry processing. On well-structured domains such as vector spaces and manifolds, the Laplace operator derived from differential geometry offers a principled approach to smoothing via heat diffusion, with strong theoretical guarantees. However, constructing such Laplacians requires a carefully defined domain structure, which is not always available. Most practitioners thus rely on simple convolution kernels and message-passing layers, which are biased against the boundaries of the domain. We bridge this gap by introducing a broad class of smoothing operators , derived from general similarity or adjacency matrices, and demonstrate that they can be normalized into diffusion-like operators that inherit desirable properties from Laplacians. Our approach relies on a symmetric variant of the Sinkhorn algorithm, which rescales positive smoothing operators to match the structural behavior of heat diffusion. This construction enables Laplacian-like smoothing and processing of irregular data such as point clouds, sparse voxel grids or mixture of Gaussians. We show that the resulting operators not only approximate heat diffusion but also retain spectral information from the Laplacian itself, with applications to shape analysis and matching. 1 Introduction Discrete Differential Geometry. Geometric data analysis is an active research field that provides a principled framework for understanding complex data [ 37 , 18 ] . These tools are especially effective in two or three dimensions, but also extend to graphs and higher-dimensional domains. While differential geometry provides elegant constructions on well-structured data, such as triangle meshes [ 25 , 16 ] , adapting these tools to less structured representations like point clouds or voxel grids remains a major challenge [ 7 , 53 , 33 ] . In many practical scenarios, high-quality triangular meshes are not available due to limitations in the acquisition process [ 13 ] or even to the nature of the data itself [ 9 ] . For example, in medical imaging, one often works with voxelized segmentation masks [ 57 ] and anatomical structures such as trabecular bones that cannot be neatly described as surfaces. Similarly, point clouds and recent representations like Gaussian splats [ 47 , 93 ] are widely used, but typically lack explicit connectivity information. Using classical geometric operators in these settings often requires local approximations of the underlying manifold [ 75 , 78 , 93 ] , which can introduce significant errors and degrade performance. Smoothing Operations. Bridging the gap between geometry-aware methods designed for clean meshes and more general unstructured data representations is crucial for scalable learning with shapes. Among the most fundamental operations in geometry processing is smoothing , which modifies a signal using local geometric information [ 84 , 78 ] . A key example is heat diffusion , which, on meshes, is controlled by the matrix exponential of the Laplacian [ 37 ] . This process plays a central role in many pipelines for shape analysis [ 27 ] , segmentation [ 78 ] , and correspondence [ 83 ] . Contributions. In this work, we generalize heat diffusion to arbitrary discrete domains such as point clouds, voxel grids, Gaussian mixtures and binary masks. Our approach ensures mass conservation , meaning that the total sum of the signal remains constant under diffusion, corresponding to physical conservation of heat over the domain. Our approach starts from a symmetric similarity matrix, akin to an adjacency matrix, and produces a heat-diffusion-like operator via a symmetric Sinkhorn normalization [ 50 ] . This results in a linear operator, symmetric with respect to a mass-weighted inner product, whose properties and spectrum closely resemble that of the exponential of a Laplacian, as displayed on Figure 1 . Our contributions can be summarized as follows: • We present an algebraic framework for defining smoothing, Laplacians and diffusions on general discrete geometric representations, clarifying their shared structure and assumptions. • We propose an efficient and GPU-friendly algorithm to transform symmetric similarity matrices into mass-preserving diffusion operators, inspired by recent theoretical works in manifold learning [ 90 , 23 ] and optimal transport [ 34 ] . • We demonstrate broad applicability to geometric data analysis, particularly for statistical shape analysis and generative modelling. Figure 1 : Heat-like diffusion and spectral analysis on general geometric data without Laplacian inversion. Left: Mass-preserving diffusion of a Dirac function on a sparse voxel grid (jaw bone). Right: Laplacian-like eigenvectors on a point cloud (human) and Gaussian mixture (bunny). 2 Related Works Laplacians and Heat Diffusions. The Laplace–Beltrami operator \Delta is an essential tool in discrete geometry processing, especially on triangle meshes [ 80 , 16 ] . Its spectral properties have been widely used for shape analysis [ 70 ] and correspondence [ 55 , 63 ] . A closely related tool is the heat equation \partial_{t}f=-\Delta f , whose solution f(t)=e^{-t\Delta}f_{0} acts as a smoothing operator on an initial signal f_{0} . Heat diffusion has been leveraged to compute shape descriptors [ 83 , 17 ] , geodesic distances [ 27 , 33 ] parallel transport [ 77 ] or shape correspondences [ 86 , 20 ] . Heat-based smoothing has also inspired neural architectures for geometric learning [ 78 , 38 ] and generative modelling [ 92 ] . Crucially, the matrix exponential e^{-t\Delta} is rarely computed directly. Instead, practical implementations rely on either implicit Euler integration [ 16 ] or spectral truncation using the first Laplacian eigenfunctions [ 78 ] . These approaches rely on mesh-based discretizations of the Laplacian [ 68 , 60 , 76 ] and pre-computed factorizations, such as Cholesky or sparse eigendecompositions, limiting scalability and flexibility. While extensions to non-manifold triangulations have been proposed [ 75 ] , generalizing diffusion-based smoothing to higher-dimensional or unstructured data such as noisy point clouds and sparse voxel grids remains challenging. Graph Laplacians. The Laplacian also plays a central role in graph-based learning and analysis [ 24 ] , supporting spectral clustering [ 88 ] , embedding, and diffusion. Unlike the cotangent Laplacian for mesh processing [ 68 , 60 ] , the graph Laplacian relies only on connectivity and optional edge weights, making it applicable to a broader range of data. Discrete approximations of heat diffusion, such as the explicit Euler step I-t\Delta , form the basis of many graph neural networks (GNNs) [ 49 , 42 , 21 ] . Recent works explore approximations of implicit time-stepping schemes [ 10 , 21 ] but lose key properties or limit the flexibility of the diffusion. Beyond Laplacians, message passing [ 40 ] or graph attention [ 85 ] offer alternative forms of smoothing. In this work, we take a step back and propose general axioms for defining smoothing operators on discrete domains, formalizing desirable properties such as symmetry or mass conservation. We show that popular approaches, as well as various Laplacian normalization techniques (e.g., symmetric, random-walk) can be interpreted as specific cases in this framework. These classical methods often trade-off symmetry or mass preservation. To address this, we study a Sinkhorn normalization that satisfies these properties jointly, producing operators which are symmetric under a mass-weighted inner product and spectrally similar to Laplacian exponentials, while remaining compatible with unstructured geometric data. Sinkhorn

Read the complete text