Volume 6 • Issue 1 • PP: 07–14 • 2026
Heat-Semigroup Persistence on Data Graphs: A Multiscale Extension of Normalized Cut for Class-Separability Analysis
Open Access & Copyright
© 2026 The Author(s). Published by ASPG. This article is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
View PDF Abstract
Let G = (V,W) be a weighted data graph with symmetric normalized Laplacian L = I−D−1/2WD−1/2, and let u denote the degree-balanced signal associated with a binary partition C∪ ¯C =V. Instead of reducing the partition geometry to the single Rayleigh quotient u⊤Lu/∥u∥22 , we study the heat-semigroup persistence Pu(t) = ∥e−tLu∥22 ∥u∥22 , HT (u) = 1 T Z T 0 Pu(t)dt. Writing Lφj = λjφj and ωj = |⟨u,φj⟩|2/∥u∥22 yields Pu(t) = Σj ωje−2tλj , so the complete curve is the Laplace transform of the label spectral measure νu = Σj ωjδλj . We prove four identities that give this construction a cut-theoretic interpretation. First, Pu is completely monotone. Second, −P′u(0)/2 = Ncut(C, ¯C). Third, for the instantaneous leakage rate κu(t) = −12 d logPu(t)/dt, one has κu(0) = Ncut and κ′u (t) = −2Varνu,t (λ) ≤ 0 under the exponentially tilted spectral measure. Fourth, when u ⊥ kerL, R ∞ 0 Pu(t)dt = u⊤L†u/(2∥u∥22). Hence normalized cut is only the zero-time slope of a multiscale diffusion object whose higher derivatives recover all spectral moments. A perturbation bound |HT (L)−HT (eL)| ≤ T∥L−eL∥2 is also established for a fixed partition signal. Numerical evaluation on a 1,797-sample, 64-variable handwritten-digit benchmark uses all 45 class pairs and ten repeated stratified train/test splits. With graphs formed exclusively from training observations, mean H1 has Spearman correlation −0.924 with held-out pairwise error (95% bootstrap interval [−0.957,−0.850]); normalized cut gives 0.927, and the second spectral central moment gives 0.930. The comparable predictive rankings are material: the proposed functional is not presented as a replacement for normalized cut, but as its multiscale completion, retaining spectral information that a first moment necessarily discards.
Keywords
References
[1] C. L. Wormell and S. Reich, “Spectral convergence of diffusion maps: Improved error bounds and an alternative normalization,” SIAM Journal on Numerical Analysis, vol. 59, no. 3, pp. 1687–1734, 2021.
[2] J. Calder and N. García Trillos, “Improved spectral convergence rates for graph laplacians on ε-graphs and k-NN graphs,” Applied and Computational Harmonic Analysis, vol. 60, pp. 123–175, 2022.
[3] X. Cheng and H.-T. Wu, “Convergence of graph laplacian with kNN self-tuned kernels,” Information and inference: A Journal of the IMA, vol. 11, no. 3, pp. 889–957, 2022.
[4] X. Cheng and N. Wu, “Eigen-convergence of gaussian kernelized graph laplacian by manifold heat interpolation,” Applied and Computational Harmonic Analysis, vol. 61, pp. 132–190, 2022.
[5] J. Calder, N. García Trillos, and M. Lewicka, “Lipschitz regularity of graph laplacians on random data clouds,” SIAM Journal on Mathematical Analysis, vol. 54, no. 1, pp. 1169–1222, 2022.
[6] T. Roith and L. Bungert, “Continuum limit of lipschitz learning on graphs,” Foundations of Computational Mathematics, vol. 23, pp. 393–431, 2023.
[7] M. M. Dunlop, D. Slepˇcev, A. M. Stuart, and M. Thorpe, “Large data and zero noise limits of graph-based semisupervised learning algorithms,” Applied and Computational Harmonic Analysis, vol. 49, no. 2, pp. 655–697, 2020.
[8] M. Boedihardjo, S. Deng, and T. Strohmer, “A performance guarantee for spectral clustering,” SIAM Journal on Mathematics of Data Science, vol. 3, no. 1, pp. 369– 387, 2021.
[9] H.-L. de Kergorlay and D. J. Higham, “Consistency of anchor-based spectral clustering,” Information and Inference: A Journal of the IMA, vol. 11, no. 3, pp. 801–822, 2022.
[10] D. Pasadakis, C. L. Alappat, O. Schenk, and G. Wellein, “Multiway p-spectral graph cuts on grassmann manifolds,” Machine Learning, vol. 111, pp. 791–829, 2022.
[11] N. García Trillos, R. Murray, and M. Thorpe, “From graph cuts to isoperimetric inequalities: Convergence rates of cheeger cuts on data clouds,” Archive for Rational Mechanics and Analysis, vol. 244, pp. 541–598, 2022.
[12] M. Flores, J. Calder, and G. Lerman, “Analysis and algorithms for ℓp-based semi-supervised learning on graphs,” Applied and Computational Harmonic Analysis, vol. 60, pp. 77–122, 2022.
[13] B. Landa, R. R. Coifman, and Y. Kluger, “Doubly stochastic normalization of the gaussian kernel is robust to heteroskedastic noise,” SIAM Journal on Mathematics of Data Science, vol. 3, no. 1, pp. 388–413, 2021.
[14] B. Landa and X. Cheng, “Robust inference of manifold density and geometry by doubly stochastic scaling,” SIAM Journal on Mathematics of Data Science, vol. 5, no. 3, pp. 589–614, 2023.
[15] J. Ah-Pine, “Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering,” European Journal of Operational Research, vol. 299, no. 3, pp. 1069–1078, 2022.
[16] H. Antil, T. Berry, and J. Harlim, “Fractional diffusion maps,” Applied and Computational Harmonic Analysis, vol. 54, pp. 145–175, 2021.
[17] G. Huguet, A. Tong, B. Rieck, J. Huang, M. Kuchroo, M. Hirn, G. Wolf, and S. Krishnaswamy, “Timeinhomogeneous topology,” SIAM Journal on Mathematics of Data Science, vol. 5, no. 2, pp. 346–372, 2023.
[18] A. Aldroubi, I. A. Krishtal, and S. Tang, “Phaseless reconstruction from space–time samples,” Applied and Computational Harmonic Analysis, vol. 48, no. 1, pp. 395–414, 2020.
[19] M. Benzi, M. Rinelli, and I. Simunec, “Computation of the von neumann entropy of large matrices via trace estimators and rational krylov methods,” Numerische Mathematik, vol. 155, pp. 377–414, 2023.
[20] K. Miller and J. Calder, “Poisson reweighted laplacian uncertainty sampling for graph-based active learning,” SIAM Journal on Mathematics of Data Science, vol. 5, no. 4, pp. 1160–1190, 2023.
Cite This Article
Choose your preferred format
Publisher's Note
The statements, opinions, and data presented in this article are solely those of the author(s) and do not necessarily represent those of ASPG, the journal, or its editors. ASPG and the editors disclaim responsibility for any harm arising from the use of any ideas, methods, instructions, or products described in this article, to the fullest extent permitted by applicable law.