Articles

Spectral Clustering Interview Questions: Similarity Graphs, Laplacians, and Unstable Clusters

Practice spectral clustering interviews with similarity graphs, Laplacian conventions, a four-node spectrum, and checks that separate sources of instability.

Spectral clustering starts with a similarity graph, embeds its nodes using a graph Laplacian, and assigns groups in that embedding. A strong interview answer specifies the graph, the Laplacian convention, and the label-assignment method. When clusters change, identify which stage changed before blaming a random seed. A reproducible partition can still encode a poor definition of similarity.

This guide focuses on that debugging sequence for data science and ML candidates.

Evidence boundary: primary research and official library documentation support the mathematical and implementation facts. The four-node example and diagnostic exercises are original preparation material.

What does the similarity graph actually represent?

Begin with the unit: a user, document, image region, or another observation. Then explain what a large edge weight means. Friendship, recent messages, cosine similarity, and geographic proximity encode different relationships. Combining them without a rationale changes the problem before the eigenproblem begins.

Official documentation: scikit-learn describes spectral clustering as clustering a projection of a normalized Laplacian, with an affinity matrix constructed from features or supplied beforehand. Non-convex shapes can suit this representation when a center and spread do not describe a group well. That is a reason to consider the method, not a promise of better clusters. SpectralClustering API

Our original design exercise uses accounts as nodes and reciprocal recent interactions as weights. Ask whether repeated messages from one automated account should dominate similarity, whether old interactions decay, and whether missing interaction means dissimilarity or simply no observation. These are modeling questions that a more precise eigensolver cannot answer.

A useful response is: “I will define similarity using information available at the segmentation date, inspect the resulting neighborhood structure, and validate whether the partition supports the intended action.” If next month's behavior is included while evaluating a segment for today's decision, the apparent usefulness can come from information unavailable at deployment.

How would you choose and check the edges?

Three practical constructions create different failure modes. A distance threshold can disconnect sparse areas. A nearest-neighbor graph controls local neighbor counts but can connect distant observations in a low-density area. A fully weighted Gaussian graph avoids hard thresholds in exact arithmetic, while still depending strongly on its bandwidth.

For a Gaussian affinity exp(-gamma * distance²), increasing gamma makes off-diagonal weights fall faster. With distance 2, gamma 0.1 gives approximately 0.670; gamma 1 gives approximately 0.0183. These are original arithmetic checks. “Larger gamma makes everything more connected” reverses the direction.

Nearest-neighbor membership is usually directional: B may be among A's nearest neighbors without A being among B's. State your symmetrization rule. A union includes either direction; a mutual rule requires both. Those rules can produce different components even with identical features and the same neighbor count.

Before computing an embedding, inspect symmetry, nonnegative finite weights, degree distribution, isolates, and connected components. Also inspect several actual neighboring pairs. A histogram can look reasonable while pairs are linked through a duplicated identifier or an unintended unit conversion.

Distinguish a distance matrix from an affinity matrix. A large distance normally means less similarity. Passing distances into an interface expecting affinities can make the most distant points the strongest neighbors. Record matrix semantics explicitly rather than relying on its square shape.

Which Laplacian are you using?

For a symmetric nonnegative weight matrix W, let D contain weighted degrees. The unnormalized Laplacian is L = D - W. With positive degrees, two normalized forms are L_sym = I - D^(-1/2) W D^(-1/2) and L_rw = I - D^(-1) W.

Primary research: von Luxburg distinguishes these matrices and their associated algorithms. The unnormalized Laplacian is positive semidefinite; its zero-eigenvalue multiplicity equals the number of connected components. The symmetric normalized form uses a degree-weighted zero eigenvector rather than generally using the constant vector. A Tutorial on Spectral Clustering

Check one invariant directly: L @ ones = 0, because each diagonal degree equals its row's edge-weight sum. For any vector z, expanding the quadratic form gives a sum of edge weights times squared differences across endpoints. This explains why strongly connected nodes prefer similar coordinates in a low-energy embedding.

The degree inverses require care with isolates. Do not write 1/sqrt(0) and proceed with infinities. Identify those nodes and decide how to handle them under the implementation's convention. Official documentation: SciPy specifies its normalized-Laplacian treatment of zero degrees and explains that directed input need not produce a symmetric result. SciPy graph Laplacian

An interviewer can change “weighted undirected graph” to “directed follows.” Do not silently apply the same symmetric theory. Explain whether you deliberately discard direction or choose a formulation designed to retain it.

Work the four-node bridge example

Consider four nodes with edges A–B and C–D of weight 1. Add a B–C bridge of weight epsilon. All other edges are absent; there are no self-loops. This small graph lets you verify the matrix construction without needing a plot to infer the answer.

At epsilon 0, degrees are all 1, and L consists of two separate [[1,-1],[-1,1]] blocks. Each block has eigenvalues 0 and 2. The whole spectrum is therefore 0, 0, 2, 2: two zero eigenvalues match two components.

At epsilon 0.1, degrees are 1, 1.1, 1.1, 1. The graph is connected, so only one eigenvalue is exactly zero. The eigenvalues of this unnormalized example are approximately 0, 0.095012, 2, 2.104988. Our NumPy 2.5.3 calculation checked them against the analytic expressions 0, 1+epsilon-sqrt(1+epsilon²), 2, and 1+epsilon+sqrt(1+epsilon²).

The small positive second eigenvalue describes weak coupling in this constructed graph. It is not evidence that every real dataset with a similar number contains two useful customer segments. Here the partition was built into the fixture; real affinities require substantive justification.

A useful follow-up is to multiply every weight by 10. The unnormalized L and its eigenvalues multiply by 10, while its eigenspaces remain the same. Consequently, comparing raw eigenvalues across differently scaled graphs without controlling scale can mislead. Normalized matrices behave differently under this uniform rescaling.

Which eigenvectors become the clustering features?

Specify the complete algorithm rather than saying “take the second eigenvector.” A two-way unnormalized partition and a multiway symmetric normalized method do not have identical preprocessing steps. In a common symmetric normalized construction, selected low-eigenvalue eigenvectors form columns of an embedding, rows represent nodes, and row normalization precedes label assignment.

A constant or degree-weighted first direction can be part of the selected subspace depending on the construction. Dropping it by habit, selecting the largest eigenvalues, or applying an extra normalization without naming the algorithm makes the explanation inconsistent.

Eigenvectors have arbitrary signs. Multiplying one column by -1 changes its printed values but preserves distances when every row is transformed consistently. Repeated eigenvalues also allow different bases for the same eigenspace. A file comparison showing different columns does not by itself demonstrate different geometry.

Our original diagnostic is to compare subspaces or node-to-node geometry before comparing raw coordinates. Then compare partitions with a measure insensitive to label renaming. Labels 0 and 1 have no intrinsic order; swapping their names leaves the partition unchanged.

Separate three kinds of instability

Freeze the feature preprocessing, affinity matrix, number of groups, and eigensolver configuration. Then vary only the label-assignment seed. If the graph and embedding stay fixed while partitions change, you have localized one source of variation to the final stage.

Official implementation fact: the scikit-learn API offers k-means, discretization, and cluster_qr label strategies. K-means assignment can depend on initialization. Removing that particular source of randomness does not remove sensitivity to the graph or data. Label-assignment options

Next vary a defensible graph parameter, such as neighbor count or bandwidth, while keeping the solver and labeling settings fixed. Track component counts, degree tails, selected eigenvalues, group sizes, and which observations switch groups. If a small graph change splits a population, calling the result “the same clusters with noise” hides a modeling dependency.

Finally perturb the observations: resample eligible units, change the time window, or introduce small measurement changes appropriate to the application. Keep the evaluation unit explicit. Repeated records from one user should not masquerade as independent new users.

A small separation between a selected eigenvalue and the next can make the selected subspace sensitive to perturbations. Treat an eigengap as a diagnostic alongside graph and application evidence. Choosing the largest visible gap from many tuned graphs does not certify a true number of clusters.

What should your debugging report contain?

An original compact report records three controlled comparisons: fixed graph with varied label initialization; fixed data with varied graph construction; and perturbed data with a fixed method. For each, include the changed input, unchanged inputs, component count, cluster-size distribution, and partition disagreement.

Add the affected examples. If switches mostly occur among low-degree boundary nodes, inspect their interactions. If whole dense components move together, inspect the chosen embedding dimension and graph connectivity. If every group is dominated by one high-volume account, revisit edge weighting rather than just requesting more solver iterations.

Numerical checks should include matrix shape, symmetry tolerance, finite values, eigenpair residuals, and a tiny known graph. A failed residual can indicate convergence trouble, but an accurate residual only verifies an eigenpair of the matrix you supplied. It cannot establish that the matrix represents the intended similarity.

There is a distinction between deterministic execution and stable meaning. Record seeds and software versions for reproduction; report sensitivity and domain review for interpretation. The local environment contained scikit-learn 1.7.2, while the reviewed stable documentation displayed 1.9.1. The numerical ledger used NumPy directly, not an asserted latest-version clustering benchmark.

When would you choose another approach?

Budget graph storage before choosing an eigensolver. A dense million-by-million float64 affinity matrix alone requires about 8 terabytes in decimal units. A sparse neighborhood graph may be far smaller, but constructing neighbors, retaining edges, and solving the selected eigenproblem still cost time and memory.

Also clarify how a new observation receives a group. Fitting a transductive graph partition does not automatically supply a production prediction rule for unseen nodes. A separately designed extension or periodic refit needs its own validation, particularly when graph membership changes.

If the problem concerns compact feature-space groups with fast future assignment, a centroid model may be easier to operate. If local density and noise are central, compare a density-based method. If directed community structure is essential, retain that structure in the method you select. These are preparation recommendations, not universal rankings.

Practice graph construction and the explanation

These verified records support related reasoning. The spectral follow-ups are original extensions, not claims that every linked prompt explicitly requests spectral clustering.

Practice question	Spectral follow-up
Which clustering algorithm would you use and why	Define whether features or relationships establish similarity.
Design cluster-randomized test under network effects	Explain what cutting a strong edge changes operationally.
Compare PCA and Autoencoders Under the Curse of Dimensionality	Distinguish a feature projection from a graph embedding.
Implement K-Means Clustering From Scratch	Isolate initialization during label extraction.
Derive eigenvalues and sum for inverse matrix	Explain why a Laplacian's zero eigenvalue prevents ordinary inversion.

Work the clustering-selection prompt, then draw the four-node graph, recover both spectra, and propose one experiment that isolates each source of instability.