Graph-harmonic label extension on a finite weighted graph

Let $n\ge 1$, $V=\{1,\dots ,n\}$, and let $W=(w_{ij})\in {\mathbb{R}}^{n\times n}$ be symmetric, entrywise nonnegative, and zero-diagonal. Put $d_i={\sum }_j{w}_{ij}$, $D=\mathrm{diag}(d_1,\dots ,d_n)$, and $L=D-W$. The support graph has edge $\{i,j\}$ exactly when $w_{ij}>0$; two vertices lie in the same connected component exactly when a finite path of support edges joins them; connected components include isolated singleton vertices. Let $B\subseteq V$ be nonempty, put $U=V\setminus B$, and prescribe $y_B\in {\mathbb{R}}^B$. Call the boundary anchored when every connected component meeting $U$ also meets $B$. For $f\in {\mathbb{R}}^V$ with $f{\mathrm{\mid }}_B=y_B$, define the Dirichlet graph energy $E(f)=\frac{1}{2}{f}^{T}Lf$. A function is harmonic on $U$ when $(Lf{)}_u=0$ for every $u\in U$. A graph-harmonic label extension is any minimizer of $E$ over the affine set of functions with the prescribed boundary values; the definition itself makes no uniqueness assertion.

Finite weighted graph Laplacian: fixes the degree matrix, combinatorial Laplacian, support edges, and isolated-component convention used above.

Zhu, Ghahramani, and Lafferty, Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions, §2

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 11