Finite graph-harmonic label propagation with a residual status

Inputs are $n\ge 1$, $V=\{1,\dots ,n\}$, a matrix $W\in {\mathbb{R}}^{n\times n}$, a nonempty labeled subset $B\subseteq V$, a boundary-label matrix $Y_B\in {\mathbb{R}}^{\mathrm{\mid }B\mathrm{\mid }\times r}$ with $r\ge 1$, an operation cap $K\in {\mathbb{N}}_0$ per label coordinate, and a residual tolerance $\epsilon \ge 0$. Use exact real arithmetic in the mathematical specification. Reject with status $\mathtt{\text{invalid-input}}$ unless $W$ is symmetric, entrywise nonnegative, and zero-diagonal. Set $U=V\setminus B$, $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 are in the same connected component exactly when a finite path of support edges joins them. Use increasing vertex order for every submatrix, boundary vector, and returned output coordinate.

Inspect every connected component in increasing vertex order. If some component meeting $U$ misses $B$, return status $\mathtt{\text{unanchored-component}}$ and the unanchored components before forming a solve. If $U=\mathrm{\varnothing }$, return $Y_B$, an empty unlabeled output, and status $\mathtt{\text{no-unlabeled-vertices}}$. Otherwise set $M=L_{UU}$.

For each column $c=1,\dots ,r$ in order, start a fresh counter at zero and form $b_c=-L_{UB}(Y_B{)}_{:,c}$, evaluating the matrix-vector product in increasing vertex order. Recompute a fresh lower-triangular Cholesky factor $R$ of $M$ for this column by the recurrence: initialize $R$ to zero; in increasing order $j=1,\dots ,\mathrm{\mid }U\mathrm{\mid }$, compute $p_j=M_{jj}-{\sum }_{k<j}{R}_{jk}^2$, return status $\mathtt{\text{factorization-failure}}$ if $p_j\le 0$, set $R_{jj}=\sqrt{p_j}$, and for $i>j$ set $R_{ij}=(M_{ij}-{\sum }_{k<j}{R}_{ik}{R}_{jk})\mathrm{/}{R}_{jj}$. Recompute $R$ for each column so that the factorization cost is part of that column's cap.

Count each real addition, subtraction, multiplication, division, comparison, and square root as one scalar operation. Evaluate every finite sum left-to-right in increasing index order, with an empty sum equal to zero. For each coordinate of $b_c$, implement the unary negation as one subtraction from zero and include that subtraction in the count. Input validation, degree/Laplacian construction, component scans, loop-control comparisons, and budget checks are outside the per-column count. The count for column $c$ includes forming $b_c$, its Cholesky recurrence, both triangular substitutions, and its residual calculation. Before each counted operation, if it would make the counter exceed $K$, return status $\mathtt{\text{budget-exhausted}}$ with outputs and residuals for only the fully completed columns before $c$. If a Cholesky pivot satisfies $p_j\le 0$, return status $\mathtt{\text{factorization-failure}}$ with outputs and residuals for only the fully completed columns before $c$.

Solve $R{v}_c=b_c$ by $v_{c,i}=((b_c{)}_i-{\sum }_{j<i}{R}_{ij}{v}_{c,j})\mathrm{/}{R}_{ii}$ in increasing $i$, and solve $R^T{z}_c=v_c$ by $z_{c,i}=(v_{c,i}-{\sum }_{j>i}{R}_{ji}{z}_{c,j})\mathrm{/}{R}_{ii}$ in decreasing $i$, using the same counter and sum convention. Compute $e_{c,i}={\sum }_{j=1}^{\mathrm{\mid }U\mathrm{\mid }}{M}_{ij}{z}_{c,j}-(b_c{)}_i$ in increasing $i$, then ${\rho }_c=({\sum }_{i=1}^{\mathrm{\mid }U\mathrm{\mid }}{e}_{c,i}^2{)}^{1\mathrm{/}2}$, again using the same counter. If ${\rho }_c>\epsilon$, return status $\mathtt{\text{residual-failure}}$ with candidate coordinates and residuals through column $c$. If all columns pass, return $Y_U=(z_1,\dots ,z_r)$, the residuals, and status $\mathtt{\text{residual-passed}}$.

Graph-harmonic label extension on a finite weighted graph: fixes the finite support graph, boundary data, componentwise anchor condition, and energy.

Anchored graph-harmonic extensions are unique and obey a maximum principle: proves that the anchored principal block is positive definite and gives the exact harmonic solution.

The real Cholesky recurrence computes the positive-diagonal factor: proves the displayed deterministic recurrence returns the real positive-diagonal Cholesky factor for the anchored positive-definite block.

Forward and backward substitution are correct, unique, and quadratic in scalar operations: supplies the unique triangular substitutions used to solve each column.

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

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 11 §§11.2–11.3