18  Lab 02 — Graph Heat Equation

Anchor chapter: Chapter 2 — Graph Laplacians, Dirichlet Energy, Harmonic Functions.

Goal. Integrate \(\dot{x} = -Lx\) on a weighted graph, verify that the solution decays to the harmonic function, and measure the spectral-gap \(\lambda_2\) from the convergence rate.

Build the graph heat equation for path graphs of varying lengths and observe convergence to the harmonic extension. Starting from random initial values, run the pinned dynamics (2.3) with the two endpoints fixed, and watch the interior values relax to linear interpolation. Plot the Dirichlet energy \(E(x(t))\) on a log scale; the slope gives \(-2\alpha\lambda_2\). Then compare path graphs of length 2, 5, and 10, observing how the spectral gap shrinks and convergence slows — a preview of the depth-dependence of the neural sheaf.

TipRuns in your browser

This lab requires only NumPy, Matplotlib, and NetworkX, loaded automatically via Pyodide. Code cells run directly in the page via WebAssembly — no local Python installation needed.

Prefer a local Jupyter environment? Download lab-02-graph-heat-equation.ipynb

18.1 Setup

18.2 1. Build the object

We construct the graph Laplacian \(L\) of a path on \(n\) vertices with optional edge weights: \(L_{ii}\) equals the sum of incident edge weights, and \(L_{ij} = -w_{ij}\) for adjacent vertices. Pinning the two endpoints to boundary values \(x_B\) and isolating the free interior vertices gives the block decomposition \(L_{\Omega\Omega}\), \(L_{\Omega B}\). The harmonic extension \(x_\Omega^* = -L_{\Omega\Omega}^{-1} L_{\Omega B} x_B\) is the unique minimiser of the Dirichlet energy \(E(x) = \tfrac{1}{2} x^\top L x\) subject to the boundary conditions; for a uniform path graph it is simply linear interpolation.

18.3 2. Verify a theorem / run an experiment

Starting from a random initial state, we integrate \(\dot{x}_\Omega = -(L_{\Omega\Omega} x_\Omega + L_{\Omega B} x_B)\) with forward Euler using a step size \(\Delta t < 1/\lambda_{\max}(L_{\Omega\Omega})\) to guarantee stability. The Dirichlet energy excess \(E(t) - E(\infty)\) decays as \(e^{-2\lambda_1 t}\), where \(\lambda_1\) is the smallest eigenvalue of \(L_{\Omega\Omega}\); the right panel compares convergence rates for path graphs of lengths 5, 10, and 20, illustrating that longer paths have smaller spectral gaps and therefore slower convergence.

18.4 Exercises

  1. Harmonic = linear. For a uniform path graph the harmonic extension is linear interpolation between boundary values. Verify this analytically (by solving \(L_{\Omega\Omega} x_\Omega = -L_{\Omega B} x_B\)) and numerically for \(n = 20\) with non-uniform boundary values \(x_0 = -1\), \(x_{n-1} = 3\).

  2. Spectral gap scaling. The smallest eigenvalue of \(L_{\Omega\Omega}\) for a uniform path of length \(n\) scales as \(\lambda_1 \approx \pi^2 / n^2\). Plot \(\lambda_1\) versus \(n\) for \(n = 5, 10, 20, 50, 100\) on a log–log axis and fit a power law.

  3. Non-uniform weights. Modify make_path_laplacian to accept random positive edge weights. How does the harmonic extension change? How does the convergence rate change relative to the uniform case?

  4. Interior pinning. Add a third pinned vertex in the interior of the path and solve the resulting two-Dirichlet-region problem. Verify that the solution is piecewise-linear on each segment.