- #1
maverick_starstrider
- 1,119
- 6
I'm playing around with Spectral Bisections and Fiedler vectors as ways of bisecting a graph using the sparsest cut. However, I'm finding that even the most trivially simple graphs are bisected incorrectly by this approach. What am I missing?
Take for example a graph that is just a 4x4 square lattice (no-periodicity). There are clearly two possible bisections: a horizontal cut right across the middle, and a vertical cut right down the middle. The Laplacian matrix of this is just:
2 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0
-1 3 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0
0 -1 3 -1 0 0 -1 0 0 0 0 0 0 0 0 0
0 0 -1 2 0 0 0 -1 0 0 0 0 0 0 0 0
-1 0 0 0 3 -1 0 0 -1 0 0 0 0 0 0 0
0 -1 0 0 -1 4 -1 0 0 -1 0 0 0 0 0 0
0 0 -1 0 0 -1 4 -1 0 0 -1 0 0 0 0 0
0 0 0 -1 0 0 -1 3 0 0 0 -1 0 0 0 0
0 0 0 0 -1 0 0 0 3 -1 0 0 -1 0 0 0
0 0 0 0 0 -1 0 0 -1 4 -1 0 0 -1 0 0
0 0 0 0 0 0 -1 0 0 -1 4 -1 0 0 -1 0
0 0 0 0 0 0 0 -1 0 0 -1 3 0 0 0 -1
0 0 0 0 0 0 0 0 -1 0 0 0 2 -1 0 0
0 0 0 0 0 0 0 0 0 -1 0 0 -1 3 -1 0
0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 3 -1
0 0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 2
So I got to MATLAB and say eig(Laplacian) and the four smallest eigenvectors are: 0.0, 0.585, 0.585 and 1.1716. So, so far so good. The first eigenvalue is zero, as you expect, and the second eigenvalue has a multiplicity of two, corresponding to the two identical best cuts (horizontal or vertical).
But then when I look at the eigenvector of, say, the first non-zero eigenvalue, I get:
-0.0642
-0.1794
-0.3423
-0.4575
0.0886
-0.0266
-0.1895
-0.3047
0.3047
0.1895
0.0266
-0.0886
0.4575
0.3423
0.1794
0.0642
Which is wrong. The correct cut should have 1-8 as one sign (negative in this case) and 9-16 as the other sign (positive) in this case. But instead the method things node 5 should be on the other cut (which makes for a partition of 6 edges, instead of the optimal of 4).
This isn't the only case, I've tried all kinds of rectangular grids and the behaviour of this bisection method is unpredictable at best. Am I missing something, or is this how it is supposed to perform?
Take for example a graph that is just a 4x4 square lattice (no-periodicity). There are clearly two possible bisections: a horizontal cut right across the middle, and a vertical cut right down the middle. The Laplacian matrix of this is just:
2 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0
-1 3 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0
0 -1 3 -1 0 0 -1 0 0 0 0 0 0 0 0 0
0 0 -1 2 0 0 0 -1 0 0 0 0 0 0 0 0
-1 0 0 0 3 -1 0 0 -1 0 0 0 0 0 0 0
0 -1 0 0 -1 4 -1 0 0 -1 0 0 0 0 0 0
0 0 -1 0 0 -1 4 -1 0 0 -1 0 0 0 0 0
0 0 0 -1 0 0 -1 3 0 0 0 -1 0 0 0 0
0 0 0 0 -1 0 0 0 3 -1 0 0 -1 0 0 0
0 0 0 0 0 -1 0 0 -1 4 -1 0 0 -1 0 0
0 0 0 0 0 0 -1 0 0 -1 4 -1 0 0 -1 0
0 0 0 0 0 0 0 -1 0 0 -1 3 0 0 0 -1
0 0 0 0 0 0 0 0 -1 0 0 0 2 -1 0 0
0 0 0 0 0 0 0 0 0 -1 0 0 -1 3 -1 0
0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 3 -1
0 0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 2
So I got to MATLAB and say eig(Laplacian) and the four smallest eigenvectors are: 0.0, 0.585, 0.585 and 1.1716. So, so far so good. The first eigenvalue is zero, as you expect, and the second eigenvalue has a multiplicity of two, corresponding to the two identical best cuts (horizontal or vertical).
But then when I look at the eigenvector of, say, the first non-zero eigenvalue, I get:
-0.0642
-0.1794
-0.3423
-0.4575
0.0886
-0.0266
-0.1895
-0.3047
0.3047
0.1895
0.0266
-0.0886
0.4575
0.3423
0.1794
0.0642
Which is wrong. The correct cut should have 1-8 as one sign (negative in this case) and 9-16 as the other sign (positive) in this case. But instead the method things node 5 should be on the other cut (which makes for a partition of 6 edges, instead of the optimal of 4).
This isn't the only case, I've tried all kinds of rectangular grids and the behaviour of this bisection method is unpredictable at best. Am I missing something, or is this how it is supposed to perform?