sorting adjacency matrix by the Fiedler vector

Question

I have a fairly sparse adjacency matrix showing connections between approx 5,000 points in my dataset. I'm looking at various ways to analyze the relationships between the data points.

This approach looks interesting: https://www.cs.purdue.edu/homes/dgleich/demos/matlab/spectral/spectral.html

The author sorts the adjacency matrix by the Fiedler vector and obtains what look like interesting results.

I'm looking for reference material about this approach. I've found plenty of references describing using the sign of the Fiedler vector to partition data into two sets (and this can be applied recursively). A direct sort using the Fiedler vector is something I haven't found in the literature. Can anyone tell me whether this is a known technique, and if so, point me towards some reference material about it?

Thanks! Jeremy

Answer 1

Not sure if this has a name, but if $v_1$ is the Fiedler vector (for the first nonzero eigenvalue), and $v_2$, $v_3$ are the eigenvectors for the next two smallest eigenvalues, you can plot them against each other to possibly reveal partitioning into multiple blocks.

For example, I constructed a simple adjacency matrix with 4 groups that I later permute randomly.

If we plot the Fiedler vector, we can see that we can't really tell more than 2 groups (it may look like 3, but that's just cause we've plotted the indices in order).

If we plot instead now the Fiedler vector $v_1$ against $v_2$ and $v_3$, it reveals 4 clusters in 3D.

This, of course, still means you have to somehow detect clusters in the resulting data that you have, so it may not be too useful in practice. However, it's a way to force out a little more information from the eigenvectors of the graph Laplacian. What you definitely don't want to do is to use the Fiedler vector $v_1$ in partitioning into more than two groups.

More often, folks will just use recursive spectral partitioning, along with enough hardcoded safeguards to force your resulting partitions to work well (i.e. being careful about interfaces, for example).

Answer 2

We gave with a colleague (Richard Hao Zhang) a course at SIGGRAPH 2010 on spectral mesh processing. We give different intuitions of spectral decomposition, as a constrained optimization problem (Rayleigh quotient), as vibrating modes (Chladni plates), as an algebraic problem, as a geometric problem and connections with the heat kernel.

Reference on ACM Digital Library:

https://dl.acm.org/citation.cfm?id=1837109

The slides are here:

http://alice.loria.fr/WIKI/index.php/Graphite/SpectralMeshProcessing

My (older) articles on the subject:

https://members.loria.fr/Bruno.Levy/papers/Laplacian_SMI_2006.pdf

https://hal.inria.fr/inria-00186931/

Answer 3

I created a demo for sorting Distance matrix with the Fiedler Vector using PyTorch. You can take a look at the source code here: https://github.com/dimkastan/PyTorch-Spectral-clustering