Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions

Inputs. Integers $n,p\ge 1$, data $x_1,\dots ,x_n\in {\mathbb{R}}^p$, a fixed deterministic graph-construction procedure $G:({\mathbb{R}}^p{)}^n\to {\mathbb{R}}^{n\times n}$, mode $\mathtt{\text{ratio}}$ or $\mathtt{\text{normalized}}$, and cluster count $k\ge 1$. In normalized mode also supply a Boolean row-normalization option, defaulting to false.

1. Compute $W=G(x_1,\dots ,x_n)$. Reject the input unless $W$ is symmetric, entrywise nonnegative, and zero-diagonal. Set $d_i={\sum }_j{w}_{ij}$, $D=\mathrm{diag}(d_i)$, $L=D-W$, and $V_{+}=\{i:d_i>0\}$.

2. In ratio mode require $k\le n$, use all vertices in increasing index order, and set $M=L$. In normalized mode, if $V_{+}=\mathrm{\varnothing }$, return every vertex as a separately reported singleton with status $\mathtt{\text{no-positive-degree-vertices}}$. Otherwise require $k\le \mathrm{\mid }{V}_{+}\mathrm{\mid }$, use only $V_{+}$ in increasing index order, and set $M=D_{+}^{-1\mathrm{/}2}{L}_{+}{D}_{+}^{-1\mathrm{/}2}$.

3. Compute the exact real eigenspaces of $M$ and order its eigenvalues increasingly with multiplicity. For each eigenspace $E_{\lambda }$, use the deterministic projected-coordinate basis rule: for $\lambda =0$, first use $n^{-1\mathrm{/}2}\mathbf{1}$ in ratio mode or $D_{+}^{1\mathrm{/}2}\mathbf{1}\mathrm{/}\sqrt{{\sum }_{i\in V_{+}}{d}_i}$ in normalized mode; then process the standard coordinate vectors in vertex order, project each onto $E_{\lambda }$, orthogonalize against accepted vectors, skip zero residuals, and normalize each nonzero residual. Take the first $k$ eigenvectors as columns of $U$.

4. In normalized mode, if row normalization is true, replace each row $u_i$ by $u_i\mathrm{/}\mathrm{\parallel }{u}_i{\mathrm{\parallel }}_2$, where $\mathrm{\parallel }v{\mathrm{\parallel }}_2=\sqrt{{\sum }_{j=1}^k{v}_j^2}$. The prescribed first zero-mode vector has positive entries on every active vertex, so every active row norm is positive.

5. Treat the rows of $U$ as points in ${\mathbb{R}}^k$ with Euclidean distance $\mathrm{\parallel }a-b{\mathrm{\parallel }}_2$. Initialize the first Lloyd center at the row whose vertex index is smallest among the vertices selected in Step 2. For each subsequent center, choose an unused row maximizing its minimum distance to previously chosen centers, breaking ties by smallest vertex index. Assign each row initially to a nearest center, breaking ties by smallest center index. At each later assignment retain its current label when it is among the nearest centers; otherwise choose the smallest nearest-center index. Replace each nonempty center by the mean of its assigned rows, leave empty-cluster centers unchanged, and repeat until both labels and centers stop changing.

6. Return the nonempty label sets. In normalized mode append every isolate as a separately reported singleton. Graph rule, edge weights, bandwidth, kNN symmetrization, and cluster count are modeling inputs; this procedure makes no rounding, approximation, graph-consistency, or manifold-recovery guarantee.

Finite weighted graph Laplacian

RatioCut and normalized cut for a finite weighted graph

Quadratic form and kernel of a weighted graph Laplacian

Weighted RatioCut and Ncut spectral relaxations

Lloyd's k-means algorithm with explicit tie handling

Lloyd iteration is objective-decreasing and terminates

Projected coordinate vectors give a deterministic orthonormal basis

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., corrected 12th printing