Heat-Semigroup Persistence on Data Graphs: A Multiscale Extension of Normalized Cut for Class-Separability Analysis
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.
Volume & Issue
Vol. Volume 6 / Iss. Issue 1