I'm trying to develop a simple algorithm to partition some finite-element mesh into a binary tree. I've been playing around with using the Fiedler vector to find the sparsest cut and starting with a very simple test case of a 4x4 square lattice (i.e. a graph made of just 4 rows of 4 nodes, connected in a square with no periodicity at the edges). However, computing the eigenvalues and eigenvectors of the Laplacian of this matrix yields obviously incorrect sparse cuts.
The multiplicity of the first non-zero eigenvalue is 2, which makes sense as you can cut down the middle of the graph/lattice either horizontally or vertically to make the best cut. However, the values of the eigenvectors corresponding to these eigenvalues (obtained using matlab) are, for example,
[0.4493 0.3491 0.2075 0.1074 0.2862 0.1861 0.0445 -0.0556 0.0556 -0.0445 -0.1861 -0.2862 -0.1074 -0.2075 -0.3491 -0.4493]
Which is very close to the correct cut (which would have nodes 1-8 as one sign and 9-16 as the other thus there are only 4 edges crossing the cut) except it randomly decides that 8 should be on the other cut, which makes a case with 6 edges crossing the cut.
The second degenerate eigenvector is essentially identical (almost a correct vertical slice except one node out of place).
I suspect the issue relates to the fact that the second eigenvalue has a multiplicity greater than one and, related, that the lattice is bipartite but I'm not sure what to do about that and I don't know why it doesn't give the clearly correct solution in such a simple case.