Technical Summary: Sinkhorn Normalization of Diffusion Kernels

1. Problem Statement

In geometric data analysis and machine learning, smoothing signals based on local neighborhoods is a fundamental operation. On well-structured domains like triangle meshes, the Laplace–Beltrami operator provides a principled framework for smoothing via heat diffusion, offering strong theoretical guarantees such as mass conservation and spectral properties. However, constructing such Laplacians requires explicit connectivity (e.g., mesh edges or cotangent weights), which is often unavailable for irregular data representations like point clouds, sparse voxel grids, or Gaussian splats.

Practitioners typically resort to simple convolution kernels or message-passing layers for these unstructured data. However, these raw smoothing operators suffer from significant structural deficiencies:

• Boundary Bias: They often fail to preserve mass, leading to signal decay or explosion, particularly at domain boundaries.
• Lack of Symmetry: Standard normalizations (e.g., row-normalization) break symmetry, while symmetric normalizations often fail to preserve constant signals.
• Spectral Instability: Truncated spectral approximations of heat diffusion can introduce ringing artifacts and are computationally expensive.

The core challenge is to define stable, Laplacian-like smoothing operators on arbitrary discrete domains without access to an underlying manifold structure or explicit connectivity.

2. Methodology

The authors propose a framework to transform arbitrary symmetric similarity or adjacency matrices into valid diffusion operators that mimic the behavior of heat diffusion. The core mechanism is Symmetric Sinkhorn Normalization.

2.1. Theoretical Framework

The paper establishes an algebraic framework distinguishing between three types of operators on a discrete measure space $(X, \mu)$:

1. Laplace-like Operators ($\Delta$): Linear maps satisfying self-adjointness, positive semi-definiteness, constant cancellation ($\Delta \mathbf{1} = 0$), and a Metzler structure (non-positive off-diagonals).
2. Diffusion Operators ($Q$): Linear maps representing heat diffusion ($e^{-t\Delta}$). They must satisfy:
   • Symmetry: Self-adjoint with respect to the mass-weighted inner product.
   • Mass Conservation: $Q\mathbf{1} = \mathbf{1}$ (preserves the total sum of the signal).
   • Spectral Bound: Eigenvalues in $[0, 1]$.
   • Positivity: Maps non-negative signals to non-negative signals.
3. Smoothing Operators ($S$): General positive, symmetric matrices (e.g., Gaussian kernels) that lack the strict mass conservation and spectral bounds of diffusion operators.

2.2. Symmetric Sinkhorn Normalization

Given a smoothing operator $S$ (represented as a matrix $S = KM$, where $K$ is a symmetric kernel and $M$ is the mass matrix), the method seeks a diagonal scaling matrix $\Lambda$ such that the rescaled operator $Q = \Lambda S \Lambda$ becomes a valid diffusion operator.

The algorithm iteratively updates the diagonal scaling factors $\lambda_i$ until convergence:
$$\lambda_i^{(k+1)} = \sqrt{\frac{\lambda_i^{(k)}}{\sum_j S_{ij} \lambda_j^{(k)}}}$$
This process, derived from a symmetric variant of the Sinkhorn algorithm (Knight et al., 2014), guarantees:

• Existence and Uniqueness: A unique positive diagonal matrix $\Lambda$ exists such that $Q\mathbf{1} = \mathbf{1}$.
• Mass Preservation: The resulting operator $Q$ preserves the total mass of the signal.
• Spectral Damping: The eigenvalues of $Q$ are bounded within $[0, 1]$, ensuring stability.
• Symmetry: $Q$ remains symmetric with respect to the mass-weighted inner product.

2.3. Implementation and Efficiency

The method is designed for GPU acceleration. It treats the smoothing operator as a black-box matrix-vector product, avoiding the need for explicit matrix factorization or eigendecomposition.

• Convergence: The algorithm typically converges in 5–10 iterations.
• Scalability: By leveraging libraries like KeOps or attention mechanisms (e.g., FlashAttention), the method scales to millions of points without materializing dense kernel matrices.
• Robustness: Theoretical analysis (Proposition 4.6) shows that the normalization is stable against perturbations in the mass matrix $M$, with errors damped by a factor of at least 2.

3. Key Contributions

1. Algebraic Framework: The paper defines a unified structure for smoothing, Laplacians, and diffusions on general discrete geometric representations, clarifying the axioms required for robust geometry processing.
2. Efficient Normalization Algorithm: It proposes a GPU-friendly algorithm to convert arbitrary similarity matrices into mass-preserving diffusion operators. Unlike manifold learning approaches that focus on asymptotic limits ($\sigma \to 0$), this method ensures stability at fixed diffusion scales relevant to practical applications.
3. Broad Applicability: The framework is demonstrated on diverse modalities, including point clouds, Gaussian mixtures, and voxel grids, without requiring explicit connectivity or manifold assumptions.

4. Results and Applications

The authors validate the method through several experiments:

• Spectral Shape Analysis: The leading eigenvectors of the normalized diffusion operator $Q$ approximate low-frequency Laplacian modes. Experiments on the Stanford Armadillo and other shapes show that the spectral distribution remains consistent across different representations (meshes, point clouds, voxels, Gaussian mixtures), even at fixed non-zero scales.
• Gradient Flow Stabilization: In energy distance minimization tasks, the normalized diffusion operator prevents the "lag" and boundary bias observed in raw kernel smoothing. It accelerates convergence and improves stability in inverse rendering and generative modeling contexts.
• Shape Correspondence (ULRSSM): Integrating the normalized operator into the ULRSSM pipeline (replacing spectral smoothing with $Q$-DiffNet) yields state-of-the-art results on the SHREC19 dataset, outperforming both point-based baselines and mesh-based upper bounds. The method is particularly robust to missing parts and topological noise.
• Geodesic Interpolation: In computational anatomy (LDDMM), the normalized operator mitigates the contraction-expansion dynamics often seen in standard kernel metrics, producing more plausible geodesic paths for pose interpolation and extrapolation.
• Runtime Performance: The method is significantly faster than implicit Laplacian diffusion (which requires sparse LU factorization) on GPUs. For 1 million points, the Sinkhorn approach takes ~6.8 seconds, whereas CPU-based sparse solvers take ~23 seconds, and dense GPU solvers run out of memory.

5. Significance and Claims

The paper claims to bridge the gap between the theoretical elegance of differential geometry (heat diffusion on manifolds) and the practical necessity of processing unstructured data.

• Drop-in Replacement: The normalized operator serves as a robust, "drop-in" replacement for diffusion in neural networks and geometric pipelines, requiring no knowledge of an underlying Laplacian.
• Preservation of Structure: By enforcing mass conservation and symmetry, the method retains the desirable physical and spectral properties of heat diffusion that are often lost in standard graph neural network layers or raw convolutions.
• Modesty on Convergence: The authors explicitly note that while their operator approximates the behavior of heat diffusion and recovers low-frequency Laplacian structure, it does not guarantee convergence to a specific "true" continuous Laplace-Beltrami operator in the limit of infinite sampling density, unlike some manifold learning theories. The focus is on the stability and utility of the operator at fixed, practical scales.

In conclusion, this work provides a principled, efficient, and flexible tool for smoothing and processing geometric data across a wide range of unstructured representations, enabling the application of heat-diffusion-based methods to domains where traditional Laplacians are infeasible to construct.