Common Mistakes and Best Practices in Spectral Clustering

Spectral clustering is only as meaningful as the graph it partitions. A visually convincing toy result does not validate the metric, graph scale, cluster count, or stability on new data.

1. Treating the affinity as a minor parameter

For the RBF affinity, $w_{ij}=\exp(-\gamma\lVert x_i-x_j\rVert^2)$. A very small gamma makes most similarities close to one, producing an almost complete, weakly differentiated graph. A very large value makes off-diagonal similarities approach zero and can effectively disconnect the graph. This corrects the common but reversed claim that small gamma makes entries vanish.

Inspect the similarity distribution and compare partitions over a scientifically plausible range. There is no built-in target for ordinary supervised cross-validation. GridSearchCV(SpectralClustering(...)) is invalid by default because the estimator has no general-purpose predictive score; choose graph parameters from domain knowledge, labeled validation data when legitimately available, or explicit stability analysis.

import numpy as np
from sklearn.datasets import make_moons
from sklearn.metrics.pairwise import rbf_kernel

X, reference = make_moons(n_samples=240, noise=0.05, random_state=42)
similarities = {gamma: rbf_kernel(X, gamma=gamma) for gamma in (0.1, 15.0, 100.0)}
off_diagonal = ~np.eye(len(X), dtype=bool)
medians = {gamma: float(matrix[off_diagonal].mean()) for gamma, matrix in similarities.items()}
assert medians[0.1] > medians[15.0] > medians[100.0]

Feature scaling and the metric are part of this decision: a high-variance coordinate otherwise dominates Euclidean affinities.

2. Ignoring connectivity in a neighbor graph

A nearest-neighbor graph is sparse, but sparsity alone does not make it correct. Too few neighbors can produce accidental connected components; too many can bridge groups that should remain weakly connected. The affinity graph defines the clustering problem.

from scipy.sparse.csgraph import connected_components
from sklearn.neighbors import kneighbors_graph

graph = kneighbors_graph(X, n_neighbors=10, mode="connectivity", include_self=True)
graph = graph.maximum(graph.T)
n_components, component_labels = connected_components(graph)
assert n_components == 1

scikit-learn symmetrizes its nearest-neighbor affinity. With affinity='precomputed', pass a square, symmetric, non-negative similarity matrix—not raw distances.

3. Assuming one Laplacian convention

The unnormalized Laplacian $L=D-W$, symmetric normalized Laplacian $L_{sym}=I-D^{-1/2}WD^{-1/2}$, and random-walk form solve related but different relaxations. Normalization is not universally superior; it changes the objective and the role of vertex degree. Isolated zero-degree vertices require explicit handling.

The number of zero eigenvalues equals the number of connected components. Do not blindly discard every zero-eigenvalue vector, and do not call an eigengap proof of the true number of clusters.

4. Reporting one stochastic labeling

assign_labels='kmeans' adds K-Means initialization after the embedding. Set random_state, use multiple initializations through n_init, and check partition stability. assign_labels='cluster_qr' is parameter-free and deterministic for a fixed embedding.

from sklearn.cluster import SpectralClustering
from sklearn.metrics import adjusted_rand_score

model = SpectralClustering(
    n_clusters=2,
    affinity="rbf",
    gamma=15.0,
    assign_labels="cluster_qr",
    random_state=42,
)
labels = model.fit_predict(X)
assert adjusted_rand_score(reference, labels) > 0.95

External labels are used only because this synthetic example has known membership. On real unlabeled data, report stability, graph diagnostics, and domain validation rather than presenting an internal index as ground truth.

5. Underestimating cost and deployment limits

A dense $n\times n$ affinity has quadratic memory, and dense eigenvalue work can approach cubic time. Sparse graphs and iterative solvers help, but the eigenproblem can still dominate. Record the number of vertices, edges, connected components, solver, and tolerances.

scikit-learn's estimator is transductive: it assigns the samples used to build the graph and does not provide a general predict method for unseen points. A production workflow needs an explicit out-of-sample strategy or a different model.

Conclusion

Reliable spectral clustering comes from a justified affinity graph, explicit Laplacian and label-assignment choices, connectivity and stability checks, and honest computational limits. Non-convex recovery is possible under suitable graph construction, not guaranteed by the algorithm's name.