25-EFT.WP.STG.Dynamics v1.0 | Chapter 4 — Graph Operators and Kernels (Diffusion / Wave / Filtering)

Home ／ Docs-Technical WhitePaper ／ 25-EFT.WP.STG.Dynamics v1.0

Chapter 4 — Graph Operators and Kernels (Diffusion / Wave / Filtering)

One-Sentence Goal
Define and implement diffusion/wave/frequency-domain kernels g(L) on G = (V, E), and establish a verifiable loop that compares continuous kernels and discrete-step propagations with numerical approximations.

I. Scope and Objects

1. Objects
   • Node operators: L = D − A, L_norm = I − D^{−1/2} A D^{−1/2}, random-walk L_rw = I − D^{−1} A.
   • Edge / first-order operators (optional): L_1 = B^T B (Hodge-1 Laplacian, reserved for interfaces).
   • Kernels & filters: K_t = exp(−t L) (diffusion), W_t = { cos(t √L), (√L)^{−1} sin(t √L) } (wave), H = g(L) (general graph filtering).
2. Applicability
   Parallel treatment of continuous-time kernels and discrete-step propagation; multiple numerical approximations (Padé / Krylov / Chebyshev / Lanczos).
3. Boundaries & compliance
   • unit(field) and dim(field) must be explicit; if A has units, normalize before constructing L (Ch. 2).
   • Directed/negative weights must declare variants (magnetic Laplacian / symmetrization); this chapter assumes undirected nonnegative weights.

II. Terms and Variables

• Operators & spectra: L, L_norm, L_rw, U, Λ = diag(λ_i), λ_max = max_i λ_i.
• Kernels & filters: K_t, W_t, g(L), H; polynomial coefficients c_m, Krylov dimension m.
• Timescales & steps: t ∈ R_+, Δt, step count K; discrete propagator Φ_{Δt}.
• Errors & dual-form gap: ε_approx = || H_true − H_approx ||_2, delta_form_kernel (defined in S704-7).
• Environment & reference: RefCond, corr_env(x; RefCond).

III. Axioms P704-*

• P704-1 (Spectral functional calculus) — g(L) = U g(Λ) U^T, with g(Λ) = diag(g(λ_i)).
• P704-2 (Diffusion contraction) — K_t = exp(−t L) is a contraction semigroup, ||K_t||_2 ≤ 1 and K_{t+s} = K_t K_s.
• P704-3 (Wave energy conservation) — On connected graphs without damping, || x(t) ||_2^2 + || (√L)^{−1} ẋ(t) ||_2^2 is conserved.
• P704-4 (Parallel dual forms) — Compute continuous kernels K_t and discrete steps Φ_{Δt}^K in parallel; record delta_form_kernel.
• P704-5 (Explicit measures) — Any temporal/spectral integration declares domain & measure: ( ∫_{0}^{t} • dτ ), ( Σ_i • ).
• P704-6 (Notation & conflicts) — Do not mix T_fil with T_trans; strictly separate n and n_eff; formulas/symbols/definitions must not use Chinese.

IV. Minimal Equations S704-*

1. S704-1 (Diffusion kernel): K_t = exp(−t L), acting on x as x(t) = K_t x(0).
   Units: if L is dimensionless then dim(t) = "[1]"; if L has "[1/T]", declare unit(t) = "[T]" and check_dim.
2. S704-2 (Wave kernel): W_t x = cos(t √L) x + (√L)^{−1} sin(t √L) v0, v0 = ẋ(0).
3. S704-3 (Random-walk / de-absorption): H_α = (1−α) ( I − α D^{−1} A )^{−1} or personalized H = (1−α) ( I − α P )^{−1}, P = D^{−1} A.
4. S704-4 (General graph filtering): y = g(L) x, e.g., g(λ) = exp(−t λ), (1 + β λ)^{−p}, band-pass g(λ) = exp( − ( (log λ − μ)^2 / (2 σ^2) ) ) on (0, λ_max].
5. S704-5 (Chebyshev approximation): scale spectrum to [-1, 1], \tilde{L} = (2 L / λ_max) − I,
   g(L) x ≈ Σ_{m=0}^{M} c_m T_m(\tilde{L}) x, with T_m Chebyshev polynomials and c_m from ( ∫_{−1}^{1} g(•) T_m(•) dμ ).
6. S704-6 (Lanczos/Krylov approximation): on K_m(L, x) = span{ x, Lx, …, L^{m−1} x },
   g(L) x ≈ || x || Q_m g(T_m) e_1, where Q_m^T L Q_m = T_m (tridiagonal).
7. S704-7 (Dual-form gaps):
   • Continuous vs discrete: delta_form_kernel = || K_{K Δt} x − ( I − Δt L )^K x ||_2.
   • True vs approximate: ε_approx = || g(L) − \hat{g}_M(L) ||_2.
8. S704-8 (Energy & monotonicity): diffusion energy E(t) = (1/2) x(t)^T L x(t) satisfies dE/dt = − || ∇_G x ||^2 ≤ 0; discretely, E_{k+1} ≤ E_k.

V. Metrology Workflow M7-4 (Ready → Model → Check → Persist)

1. Ready
   Load L and estimate λ_max; for Chebyshev, build \tilde{L}; finalize RefCond and unit system.
2. Model / Approximate
   • Choose kernel family g (diffusion / wave / de-absorption / band-pass) and parameters { t, α, β, p, μ, σ }.
   • Choose approximator (Padé / Krylov / Chebyshev / Lanczos) and order M or subspace size m.
3. Checks
   • Sample S vectors x_s and evaluate ε_approx(s) = || g(L) x_s − \hat{g}(L) x_s || / || x_s ||; report percentiles.
   • Compute dual-form delta_form_kernel; test diffusion energy monotonicity and semigroup contraction.
   • For random-walk kernels, verify row-stochasticity: row_sum(H) ≈ 1 and nonnegativity.
4. Persist / Publish
   manifest.stg.kernel = { type: g, params, approx: { method, M|m }, λ_max, eps_p95, delta_form_p95, energy_test, RefCond, seed, method.hash }.

VI. Contracts & Assertions C70-4xx

• C70-401 (Approximation error): eps_p95 ≤ 1e−3 (default for diffusion/de-absorption); wave kernels suggest ≤ 1e−2.
• C70-402 (Dual-form gap): delta_form_kernel_p95 ≤ tol_Tarr_kernel (suggest tol_Tarr_kernel = 1e−3).
• C70-403 (Contraction / energy): diffusion || K_t ||_2 ≤ 1 + ε with ε ≤ 1e−6; ΔE_k ≤ 0.
• C70-404 (Random-walk validity): H ≥ 0 and H 1 = 1; bias ≤ 1e−6.
• C70-405 (Spectral support): filter support matches λ_max; band-pass attenuation outside the band ≥ 40 dB (numerical equivalent).
• C70-406 (Unit consistency): check_dim( g(L) x − y ) = "[0]" passes; dimensions of t and L are compatible.

VII. Implementation Bindings I70-4*

• I70-41 build_operator(G, mode) -> { L, L_norm, L_rw }
• I70-42 heat_kernel(L, t, method) -> K_t (method ∈ { pade, krylov, cheby, scaling-squaring })
• I70-43 wave_kernel(L, t, method) -> { C_t, S_t } (returns multipliers for cos(t√L) and (√L)^{−1} sin(t√L))
• I70-44 spectral_filter_apply(L, x, spec) -> y (spec = { g_type, params, approx: { method, M|m } })
• I70-45 random_walk_kernel(A, α) -> H (ensure row-stochastic & nonnegative)
• I70-46 cheby_coeffs(g, λ_max, M) -> { c_0..c_M }
• I70-47 lanczos_apply(L, x, g, m) -> y
• I70-48 estimate_spectral_bounds(L, k) -> { λ_min_est, λ_max_est }
• I70-49 check_kernel_contracts(K_or_spec, rules) -> report

Invariants: sym(L); λ_i ≥ 0; contraction/conservation contracts pass; delta_form_kernel ≤ tol_Tarr_kernel; traceable RefCond/method/params.

VIII. Cross-References

• Operator & spectral properties: Ch. 2.
• Mapping state/obs/noise into filtering: Ch. 3 (spectral parameterization of H and Σ).
• Numerical stability & step strategies: Ch. 9.
• Runtime panels & publication fields: Ch. 14; manifests: Appendix C.
• Dual-form contract philosophy for path corrections: EFT.WP.Metrology.PathCorrection v1.0, Chs. 10/11.

IX. Quality & Risk Control

• SLO/SLI: eps_p95, delta_form_kernel_p95, energy_dissipation_rate ≥ 0, row_stochastic_bias, runtime_per_apply.
• Fallbacks: if eps_p95 exceeds gate → increase M/m or change approximator; if ||K_t||_2 > 1 + ε → shrink t or switch methods;
  if random-walk invalid → renormalize A or adjust α; if spectral bounds unstable → re-estimate λ_max (I70-48).
• Audit: persist method.hash / params / seed, spectral-bound estimation, error percentiles, and contract pass rates.

Summary
This chapter unifies graph operators and kernels on STGs: definitions of g(L), diffusion/wave/de-absorption kernels, continuous–discrete dual-form comparisons, and error metrics. It provides the M7-4 workflow, C70-4xx contracts, and I70-4* interfaces. Key outputs: manifest.stg.kernel.* (kernel type, parameters, approximation method, errors & contract outcomes) serving operator-level dependencies for identification, control, and runtime publication.