Spectral K-way ratio-cut partitioning and clustering

摘要: Recent research on partitioning has focused the ratio-cut cost metric, which maintains a balance between of edges cut and sizes partitions without fixing size priori. Iterative approaches spectral to two-way have yielded higher quality results. In this paper, we develop approach multi-way that provides generalization metric L-way lower bound metric. Our involves finding k smallest eigenvalue/eigenvector pairs Laplacian graph. The eigenvectors provide an embedding graph's n vertices into k-dimensional subspace. We devise time space efficient clustering heuristic coerce points in partitions. Advancement over current work is evidenced by results experiments standard benchmarks. >