Fiedler Vectors And Spectral Bottlenecks

From Laplacian Eigenvectors to Cuts

A graph cut separates its vertices into two nonempty sets. A useful cut often has relatively few edges crossing between its sides, especially when both sides contain many vertices. The Laplacian offers a way to search for such separations: instead of assigning each vertex directly to one of two groups, first assign it a real number. A second Laplacian eigenvector, called a Fiedler vector, gives these values. Vertices with similar values tend to be linked by edges without paying much squared difference in the vector’s edge energy, so a threshold between values can suggest a cut.

Throughout, \(G=(V,E)\) is a finite, simple, connected graph with \(n=|V|\ge 2\). Its Laplacian is \(\mathbf L=\mathbf D-\mathbf A\), where \(\mathbf D\) is the diagonal degree matrix and \(\mathbf A\) is the adjacency matrix. Since \(\mathbf L\) is real and symmetric, it has real eigenvalues, listed with multiplicity as \(0=\lambda_1<\lambda_2\le\cdots\le\lambda_n\). The strict inequality follows from the earlier result that a connected graph has a one-dimensional Laplacian nullspace. An eigenvector for \(\lambda_2\) is a Fiedler vector. If \(\lambda_2\) has multiplicity greater than one, there is more than one possible choice.

Sorting the coordinates of a Fiedler vector gives a natural family of candidates. If the distinct values are \(a_1<a_2<\cdots<a_r\), choose a threshold strictly between consecutive values. This puts all vertices with values at most \(a_i\) on one side and those with larger values on the other. Tied coordinates stay together under this scalar-threshold rule; splitting a tie requires an additional tie-breaking convention.

Why the Second Eigenvector Is Relevant

Proof. Because \(\mathbf L\) is real and symmetric, choose an orthonormal eigenbasis \(u_1,\ldots,u_n\), with \(u_1\) a constant unit vector and \(u_i\) having eigenvalue \(\lambda_i\). The condition \(\sum_v x_v=0\) says exactly that \(x\) is orthogonal to \(u_1\). Thus \(x=\sum_{i=2}^n c_i u_i\), with at least one \(c_i\ne0\). Orthonormality gives \(x^Tx=\sum_{i=2}^n c_i^2\) and \(x^T\mathbf Lx=\sum_{i=2}^n\lambda_i c_i^2\). Since each \(\lambda_i\ge\lambda_2\), the quotient is at least \(\lambda_2\). Equality holds exactly when every nonzero coefficient \(c_i\) has \(\lambda_i=\lambda_2\), which is precisely the condition that \(x\) lies in the \(\lambda_2\)-eigenspace. \(\square\)

The Laplacian quadratic form is \(x^T\mathbf Lx=\sum_{uv\in E}(x_u-x_v)^2\). Therefore a unit-length Fiedler vector, centered so that its coordinates sum to zero, has the smallest possible edge energy among centered unit vectors. This is a global statement about squared differences, not a promise that every edge has similar endpoint values. If \(\lambda_2\) is small, the total edge energy is small for such a vector, which can make groups of similar values informative.

A centered, nonzero vector must have at least one positive and one negative coordinate: if all its coordinates were nonnegative, a zero sum would force every coordinate to be zero, and the same argument applies if they were all nonpositive. In particular, a Fiedler vector has values on both sides of zero. The split at zero therefore gives a nonempty proper threshold set when the convention is \(S_0=\{v:x_v<0\}\). Other thresholds, especially those between sorted values, can give other candidate cuts.

What a Threshold Cut Measures

There is an exact connection between cuts and Laplacian energy. Write \(\mathbf 1_S\) for the vector that is \(1\) on \(S\) and \(0\) elsewhere, and let \(\mathbf 1\) be the all-ones vector. Center the indicator by defining \(y=\mathbf 1_S-(|S|/n)\mathbf 1\). Its coordinates sum to zero. Subtracting a constant does not change differences across edges, so each edge crossing the cut contributes \(1\) to \(y^T\mathbf Ly\), and every other edge contributes \(0\). Also, direct summation gives \(y^Ty=|S|(n-|S|)/n\). Hence

Applying the theorem to this nonzero centered vector shows that \(\lambda_2\) is at most this quotient for every nonempty proper \(S\). The quotient accounts for both the number of crossing edges and the sizes of the two sides. It is not the cut size alone. A Fiedler vector minimizes the quotient over all real centered vectors, whereas a cut can only supply a particular centered indicator vector. Thresholding takes the eigenvector and converts its real-valued coordinates into a discrete partition. That conversion is useful, but it does not preserve an optimization guarantee for cut size.

A Threshold Is Not a Minimum-Cut Certificate

This distinction matters in applications. A threshold rule must decide where to split; a size-two split, a split at zero, and a split chosen to balance the sides need not coincide. A practical variant sorts all coordinates and evaluates the cuts between consecutive distinct values, then chooses a candidate according to a specified objective. Such a sweep can compare its candidates, but a candidate chosen from the Fiedler ordering is still not automatically a minimum cut. The eigenvector optimizes a continuous Rayleigh quotient, not the discrete cut-size objective.

Repeated Eigenvalues and Choice of Vector

Using the Method with Care

The Fiedler vector is most useful as a structured source of candidate partitions. Its coordinate order reflects a global minimum-energy assignment, while a threshold converts that assignment into two groups. To interpret the result responsibly:

• Check that the graph is connected and has at least two vertices before using the connected-graph definition of \(\lambda_2\) and a Fiedler vector given above. If the graph is disconnected, \(\lambda_2=0\), and its zero-eigenvalue space has dimension greater than one; the connected-graph interpretation does not apply unchanged.
• State the threshold convention and keep tied coordinates together unless a separate tie-breaking rule is specified.
• Compute the actual crossing edges of the proposed cut. Similar vector values alone do not determine the cut size.
• Do not report a threshold result as a minimum cut unless a separate argument verifies that it is minimum.

Common mistake. It is incorrect to identify the second eigenvalue itself with the minimum cut size. In the \(K_4\) example, \(\lambda_2=4\), while the minimum cut size is \(3\). The relevant exact comparison is instead \(\lambda_2\le n|\partial(S)|/(|S|(n-|S|))\) for each nontrivial \(S\). This normalized expression also shows why a small eigenvalue signals a low-energy separation without specifying a minimum cut.