Spectral Clustering

Summary

Multilevel clustering of vertices of a triangle mesh using Spectral partitioning.

The first step is to apply vertex clustering using an octree, followed by spectral partitioning with the Fiedler Vector, until a certain depth is reached.

Vertex Clustering	Vertex + Spectral Clustering

The Fiedler Vector expresses the algebraic connectivity of a graph. A partition of the vertices is given by the sign of the components of the Fiedler Vector. Given the Laplacian matrix $\mathcal{L}$ of a mesh, the Fiedler vector is the eigenvector with the second-smallest eigenvalue.

The multilevel implementation is required because computing the Fiedler Vector of huge matrices is prohibitive, and vertex clustering is a good and fast approach to reduce the complexity.

One must note that vertex clustering may produce disconnect clusters, which spectral clustering does not like as input. A Union-Find algorithm has been implemented to separate the connected clusters and classify them separately.

The program also supports computing an optimized cache-oblivious mesh layout, following Yoon et al.¹, which optimizes each of the clusters’ vertices and sorts the faces of the mesh. It is important to note that it has $O(n!)$ complexity, where $n$ is the size of the clusters.

The implementation is written in C++, using Eigen and Spectra for the sparse support and computation of eigenvectors.