Heat-Semigroup Persistence on Data Graphs: A Multiscale

Extension of Normalized Cut for Class-Separability Analysis

Nader Taffach1,* Mohammad Al-Shiekh1

1 Department of Mathematics, Idlib University, Idlib, Syria

Received: October 24, 2025 Revised: November 16, 2025 Accepted: January 02, 2026 ⋆ Corresponding author

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) =

Z T

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: Ggraph Laplacian Heat semigroup Normalized cut Spectral measure Diffusion geometry Class

separability

1. INTRODUCTION

For a weighted graph with nonnegative symmetric adjacency

matrix W = [wi j], degree matrix D = diag(d1, . . . ,dn), and

normalized Laplacian

L = I−D−1/2WD−1/2, 0 ⪯ L ⪯ 2I, (1)

a binary partition is commonly summarized by a cut energy.

If u is the degree-balanced partition signal defined below, the