Spectral clustering and graph cuts — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

KNN symmetrization changes a graph cut

Example

Take $x_{1} = 0$ , $x_{2} = 1$ , and $x_{3} = 3$ on $R$ , and let each point choose its unique nearest neighbor ( $k = 1$ ). Define the union graph to contain a unit-weight edge when either directed nearest-neighbor choice selects it, and the mutual graph to contain a unit-weight edge only when both directions select it. For the partition ${1, 2}, {3}$ , the RatioCut is $3 / 2$ on the union graph and $0$ on the mutual graph.

Example references

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

Graph diagrams

The labels are vertex indices, and each drawn edge has unit weight. The left path is the union symmetrization; the right single edge is the mutual symmetrization. The verification above computes the cuts from the stated edge sets.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (u1) at (0,0) {$1$};
\node[draw,circle] (u2) at (1.5,0) {$2$};
\node[draw,circle] (u3) at (3,0) {$3$};
\draw (u1)--node[above] {$1$}(u2);
\draw (u2)--node[above] {$1$}(u3);
\node at (1.5,-0.8) {Union};
\node[draw,circle] (m1) at (5,0) {$1$};
\node[draw,circle] (m2) at (6.5,0) {$2$};
\node[draw,circle] (m3) at (8,0) {$3$};
\draw (m1)--node[above] {$1$}(m2);
\node at (6.5,-0.8) {Mutual};
\end{tikzpicture}

Facts & Assumptions

Given: Three real data points $x_{1} = 0$ , $x_{2} = 1$ , $x_{3} = 3$ , one-nearest-neighbor selection with no distance ties, and the union and mutual graph rules in the Example.

[A1]

The Euclidean distance on $R$ is $d (x, y) = ∣ x - y ∣$ .

[F1]

Finite weighted graph Laplacian: an admissible graph has symmetric nonnegative weights and zero diagonal; its support edge ${i, j}$ is present exactly when $w_{i j} > 0$ .

[F2]

RatioCut and normalized cut for a finite weighted graph: $cut (A, A^{c}) = \sum_{i \in A, j \notin A} w_{i j}$ and $RatioCut (A_{1}, A_{2}) = cut (A_{1}, A_{1}^{c}) / ∣ A_{1} ∣ + cut (A_{2}, A_{2}^{c}) / ∣ A_{2} ∣$ .

Verification

1.1givenA1algebra

The pairwise Euclidean distances are $∣ x_{1} - x_{2} ∣ = 1$ , $∣ x_{2} - x_{3} ∣ = 2$ , and $∣ x_{1} - x_{3} ∣ = 3$ . Therefore the directed choices are $1 \to 2$ , $2 \to 1$ , and $3 \to 2$ .

2.1givenF1step 1.1algebra

The union rule keeps an edge selected in either direction, so its undirected edges are ${1, 2}$ and ${2, 3}$ . The mutual rule keeps only edges selected in both directions, so its only edge is ${1, 2}$ . Both weight matrices satisfy [F1].

3.1F1step 2.1algebra

In the union graph, the only crossing edge for $A_{1} = {1, 2}$ and $A_{2} = {3}$ is ${2, 3}$ , of weight $1$ ; hence both one-sided cuts equal $1$ . In the mutual graph there is no crossing edge, so both cuts equal $0$ .

4.1F2step 3.1algebra∎

By [F2], the union RatioCut is $1 / 2 + 1 = 3 / 2$ , while the mutual RatioCut is $0 / 2 + 0 / 1 = 0$ . Thus the fixed data, neighbor count, and partition have different cut values under the two symmetrizations.

Graph diagrams

The labels are vertex indices, and each drawn edge has unit weight. The left path is the union symmetrization; the right single edge is the mutual symmetrization. The verification above computes the cuts from the stated edge sets.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (u1) at (0,0) {$1$};
\node[draw,circle] (u2) at (1.5,0) {$2$};
\node[draw,circle] (u3) at (3,0) {$3$};
\draw (u1)--node[above] {$1$}(u2);
\draw (u2)--node[above] {$1$}(u3);
\node at (1.5,-0.8) {Union};
\node[draw,circle] (m1) at (5,0) {$1$};
\node[draw,circle] (m2) at (6.5,0) {$2$};
\node[draw,circle] (m3) at (8,0) {$3$};
\draw (m1)--node[above] {$1$}(m2);
\node at (6.5,-0.8) {Mutual};
\end{tikzpicture}

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

Disconnected weighted components are zero-cut clusters

Example

Let $V = {1, 2, 3, 4}$ and set $w_{12} = w_{21} = 2$ , $w_{34} = w_{43} = 3$ , with every other entry zero. For the algorithm inputs, take $n = 4$ , $p = 1$ , $x_{i} = i \in R$ for $1 \leq i \leq 4$ , and the constant deterministic graph builder $G : (R^{1})^{4} \to R^{4 \times 4}$ defined by $G (y_{1}, y_{2}, y_{3}, y_{4}) = W = (w_{i j})$ for every input tuple. Use mode $ratio$ and $k = 2$ . The partition ${1, 2}, {3, 4}$ has RatioCut and Ncut equal to $0$ , and deterministic unnormalized spectral clustering with $k = 2$ returns these two components under the specified eigenspace and farthest-first tie rules.

Example references

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

Graph diagram

The four circles are vertices; the left edge has weight $2$ and the right edge has weight $3$ . There are no other edges. The drawing separates components for readability; the verification uses the explicit matrix.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (v1) at (0,0) {$1$};
\node[draw,circle] (v2) at (1.5,0) {$2$};
\draw (v1)--node[above] {$2$}(v2);
\node[draw,circle] (v3) at (4,0) {$3$};
\node[draw,circle] (v4) at (5.5,0) {$4$};
\draw (v3)--node[above] {$3$}(v4);
\end{tikzpicture}

Facts & Assumptions

Given: $V = {1, 2, 3, 4}$ with the only positive weights $w_{12} = w_{21} = 2$ and $w_{34} = w_{43} = 3$ ; the data, dimensions, constant graph builder $G$ , mode $ratio$ , and $k = 2$ are as specified in the Example, so the algorithm computes exactly this $W$ ; RatioCut and Ncut use the definitions in the cited supplier.

[F1]

Finite weighted graph Laplacian: $d_{i} = \sum_{j} w_{i j}$ , $L = D - W$ , and support components are determined by edges with positive weight.

[F2]

RatioCut and normalized cut for a finite weighted graph: RatioCut divides each part cut by cardinality; Ncut divides by volume.

[F3]

Quadratic form and kernel of a weighted graph Laplacian: $\ker L$ consists of vectors constant on each support component.

[F4]

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions: the algorithm selects the first $k$ eigenvectors ordered by the eigenvalues of $L$ , then applies the stated deterministic farthest-first and Lloyd rules.

Verification

1.1givenF1F3algebra

The degrees are $(2, 2, 3, 3)$ and $L = (\begin{array}{cccc} 2 & - 2 & 0 & 0 \\ - 2 & 2 & 0 & 0 \\ 0 & 0 & 3 & - 3 \\ 0 & 0 & - 3 & 3 \end{array}) .$ Each $2 \times 2$ block with edge weight $a$ has eigenvectors $(1, 1)$ and $(1, - 1)$ with eigenvalues $0$ and $2 a$ . Thus the eigenvalues of $L$ are $0, 0, 4, 6$ , and [F3] identifies the zero eigenspace as the componentwise-constant vectors.

2.1givenF2step 1.1algebra

For $A_{1} = {1, 2}$ and $A_{2} = {3, 4}$ there is no crossing edge, so both cuts are $0$ ; the part sizes are $2, 2$ and volumes are $4, 6$ . Therefore both RatioCut and Ncut equal $0$ . Since their summands are nonnegative, this partition attains the combinatorial minimum for both objectives.

2.2givenF3F4step 1.1constructalgebra

The prescribed first zero-mode vector is $q_{0} = \frac{1}{2} (1, 1, 1, 1)$ . The projection of $e_{1}$ onto the zero eigenspace is $(1 / 2, 1 / 2, 0, 0)$ ; subtracting its projection onto $q_{0}$ gives $(1 / 4, 1 / 4, - 1 / 4, - 1 / 4)$ , whose norm is $1 / 2$ . Thus the second basis vector is $q_{1} = \frac{1}{2} (1, 1, - 1, - 1)$ . The first two eigenvectors therefore give the two row values $(1 / 2, 1 / 2)$ on vertices $1, 2$ and $(1 / 2, - 1 / 2)$ on vertices $3, 4$ .

3.1F4step 2.1step 2.2algebra∎

The first farthest-first center is the row for vertex $1$ ; a farthest row is in the second component, and the smallest-index tie rule selects vertex $3$ . Each component's row has distance $0$ to its corresponding center and distance $1$ to the other. The initial assignments are therefore exactly ${1, 2}$ and ${3, 4}$ ; their means equal the two centers, so the first Lloyd update leaves both labels and centers unchanged and the algorithm returns this partition. Together with steps 2.1 and 2.2, this verifies the stated exact example output.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

An isolate is excluded from Ncut and reinserted separately

Example

Let $V = {1, 2, 3}$ with $w_{12} = w_{21} = 1$ and every other weight zero. For the algorithm inputs, take $n = 3$ , $p = 1$ , $x_{i} = i \in R$ for $1 \leq i \leq 3$ , and the constant deterministic graph builder $G : (R^{1})^{3} \to R^{3 \times 3}$ defined by $G (y_{1}, y_{2}, y_{3}) = W = (w_{i j})$ for every input tuple. In mode $normalized$ with $k = 1$ and row normalization disabled (the default), the positive-degree vertex set is $V_{+} = {1, 2}$ , the active Ncut cluster is ${1, 2}$ with value $0$ , and vertex $3$ is returned separately as the singleton ${3}$ without entering any Ncut denominator.

Example references

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

Graph diagram

Vertices $1$ and $2$ are joined by their unit-weight edge; vertex $3$ is isolated. The relative coordinates are only for display.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (v1) at (0,0) {$1$};
\node[draw,circle] (v2) at (1.5,0) {$2$};
\node[draw,circle] (v3) at (4,0) {$3$};
\draw (v1)--node[above] {$1$}(v2);
\end{tikzpicture}

Facts & Assumptions

Given: $V = {1, 2, 3}$ , with $w_{12} = w_{21} = 1$ and every other weight zero, the data, dimensions, and constant graph builder $G$ from the Example (so the computed matrix is exactly $W$ ), normalized mode, $k = 1$ , and row normalization disabled.

[F1]

Finite weighted graph Laplacian: $d_{i} = \sum_{j} w_{i j}$ , $V_{+} = {i : d_{i} > 0}$ , and $L_{s y m, +} = D_{+}^{- 1 / 2} L_{+} D_{+}^{- 1 / 2}$ .

[F2]

RatioCut and normalized cut for a finite weighted graph: Ncut sums $cut (A_{r}, A_{r}^{c}) / vol (A_{r})$ over a partition of $V_{+}$ into nonempty parts.

[F3]

Quadratic form and kernel of a weighted graph Laplacian: the kernel consists of vectors constant on each support component.

[F4]

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions: normalized mode uses only positive-degree vertices, chooses the prescribed zero-mode eigenvector first, runs the specified Lloyd updates, and appends isolates as separate singleton outputs.

Verification

1.1givenF1algebra

The degrees are $(1, 1, 0)$ , so $V_{+} = {1, 2}$ , $D_{+} = I_{2}$ , and $L_{+} = L_{s y m, +} = (\begin{array}{cc} 1 & - 1 \\ - 1 & 1 \end{array})$ .

2.1givenF3F4step 1.1algebra

The active support graph is connected, so [F3] gives a one-dimensional zero eigenspace spanned by $(1, 1)$ . Its prescribed unit vector is $q_{0} = (1, 1) / \sqrt{2}$ , and it is the single eigenvector used when $k = 1$ .

3.1givenF4step 2.1algebra

Both embedding rows are $1 / \sqrt{2}$ . The first and only Lloyd center is the first row; both points receive its label, its mean remains $1 / \sqrt{2}$ , and the labels and center are unchanged. Thus the active cluster returned is ${1, 2}$ , after which [F4] appends ${3}$ separately.

4.1F1F2step 1.1step 3.1algebra∎

The active part has cut $0$ and volume $d_{1} + d_{2} = 2$ , so its Ncut value is $0$ . Vertex $3$ has volume $0$ but is not in $V_{+}$ , so it appears in no Ncut denominator.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-6-luna)Open item page →

A disconnected graph on concentric circles separates the rings

Example

Let $V = {1, \dots, 8}$ and, for $j \in {0, 1, 2, 3}$ , set $x_{j + 1} = (\cos (π j / 2), \sin (π j / 2))$ and $x_{j + 5} = 3 (\cos (π j / 2), \sin (π j / 2))$ . Build a graph with unit-weight edges ${1, 2}, {2, 3}, {3, 4}, {4, 1}$ and ${5, 6}, {6, 7}, {7, 8}, {8, 5}$ , and no other edges. Deterministic unnormalized spectral clustering with $k = 2$ and no row normalization returns the two concentric rings as its clusters. This finite graph example makes no statement about manifold recovery for other graph constructions.

Example references

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

Graph diagram

Nodes $1$ – $4$ lie on the inner radius-one circle and nodes $5$ – $8$ on the outer radius-three circle. Each polygon edge has unit weight; there are no edges between the circles. The drawing uses the exact vertex order and support specified in the Example.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (v1) at (0,1) {$1$};
\node[draw,circle] (v2) at (1,0) {$2$};
\node[draw,circle] (v3) at (0,-1) {$3$};
\node[draw,circle] (v4) at (-1,0) {$4$};
\node[draw,circle] (v5) at (0,3) {$5$};
\node[draw,circle] (v6) at (3,0) {$6$};
\node[draw,circle] (v7) at (0,-3) {$7$};
\node[draw,circle] (v8) at (-3,0) {$8$};
\draw (v1)--(v2)--(v3)--(v4)--cycle;
\draw (v5)--(v6)--(v7)--(v8)--cycle;
\end{tikzpicture}

Facts & Assumptions

Given: The eight vertices are ordered by radius as in the Example, and the graph consists of the two unit-weight four-cycles with no cross-edges.

[F1]

Finite weighted graph Laplacian: the support graph has edge ${i, j}$ exactly when $w_{i j} > 0$ .

[F2]

Quadratic form and kernel of a weighted graph Laplacian: $L$ is positive semidefinite and its kernel consists of vectors constant on each support component.

[F3]

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions: unnormalized mode chooses the first $k$ eigenvectors increasingly; the zero-mode basis starts at $n^{- 1 / 2} 1$ and then uses projected coordinate vectors in vertex order, and Lloyd centers use the smallest-index row followed by farthest-first selection.

Verification

1.1givenF1F2algebra

The support components are $C_{1} = {1, 2, 3, 4}$ and $C_{2} = {5, 6, 7, 8}$ . By [F2], $L ⪰ 0$ and $E_{0} = \ker L = span (1_{C_{1}}, 1_{C_{2}})$ has dimension $2$ , so the two smallest eigenvalues are both $0$ .

2.1givenF2F3step 1.1constructalgebra

The prescribed first vector is $q_{0} = 1 / \sqrt{8}$ . The projection of $e_{1}$ onto $E_{0}$ is $\frac{1}{4} 1_{C_{1}}$ . Its inner product with $q_{0}$ is $1 / \sqrt{8}$ , so subtracting that projection gives $\frac{1}{8} (1_{C_{1}} - 1_{C_{2}})$ , with norm $1 / \sqrt{8}$ . Thus the next vector is $q_{1} = (1_{C_{1}} - 1_{C_{2}}) / \sqrt{8}$ . The embedding rows are $(1 / \sqrt{8}, 1 / \sqrt{8})$ on $C_{1}$ and $(1 / \sqrt{8}, - 1 / \sqrt{8})$ on $C_{2}$ .

3.1F3step 2.1algebra∎

The first center is the row for vertex $1$ . Every outer-ring row is farther from it than any other inner-ring row, so farthest-first chooses vertex $5$ by the smallest-index tie rule. Each ring's rows equal its center, while the two ring row values are distinct; nearest-center assignments are therefore exactly $C_{1}, C_{2}$ . Their means equal the selected centers, so the first Lloyd update is fixed and the algorithm returns the two rings.

Spectral clustering and graph cuts — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

KNN symmetrization changes a graph cut

Example

Example references

Graph diagrams

Facts & Assumptions

Verification

Graph diagrams

Disconnected weighted components are zero-cut clusters

Example

Example references

Graph diagram

Facts & Assumptions

Verification

An isolate is excluded from Ncut and reinserted separately

Example

Example references

Graph diagram

Facts & Assumptions

Verification

A disconnected graph on concentric circles separates the rings

Example

Example references

Graph diagram

Facts & Assumptions

Verification

Sources