Recent research on partitioning has focussed on the ratio-cut cost metric which maintains a balance between the sizes of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two-way ratio-cut partitioning have yielded higher quality partitioning results. In this paper we develop a spectral approach to multiway ratio-cut partitioning which provides a generalization of the ratio-cut cost metric to k-way partitioning and a lower bound on this cost metric. Our approach involves finding the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors provide an embedding of the graph’s n vertices into a k-dimensional subspace. We devise a time and space efficient clustering heuristic to coerce the points in the embedding into k partitions. Advancement over the current work is evidenced by the results of experiments on the standard benchmarks.
%0 Conference Paper
%1 Chan1993Spectral
%A Chan, Pak K.
%A Schlag, Martine D. F.
%A Zien, Jason Y.
%B DAC '93: Proceedings of the 30th international conference on Design automation
%C New York, NY, USA
%D 1993
%I ACM
%K clustering entityguides graph
%P 749--754
%R http://dx.doi.org/10.1145/157485.165117
%T Spectral K-way ratio-cut partitioning and clustering
%U http://dx.doi.org/10.1145/157485.165117
%X Recent research on partitioning has focussed on the ratio-cut cost metric which maintains a balance between the sizes of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two-way ratio-cut partitioning have yielded higher quality partitioning results. In this paper we develop a spectral approach to multiway ratio-cut partitioning which provides a generalization of the ratio-cut cost metric to k-way partitioning and a lower bound on this cost metric. Our approach involves finding the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors provide an embedding of the graph’s n vertices into a k-dimensional subspace. We devise a time and space efficient clustering heuristic to coerce the points in the embedding into k partitions. Advancement over the current work is evidenced by the results of experiments on the standard benchmarks.
%@ 0-89791-577-1
@inproceedings{Chan1993Spectral,
abstract = {Recent research on partitioning has focussed on the ratio-cut cost metric which maintains a balance between the sizes of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two-way ratio-cut partitioning have yielded higher quality partitioning results. In this paper we develop a spectral approach to multiway ratio-cut partitioning which provides a generalization of the ratio-cut cost metric to k-way partitioning and a lower bound on this cost metric. Our approach involves finding the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors provide an embedding of the graph’s n vertices into a k-dimensional subspace. We devise a time and space efficient clustering heuristic to coerce the points in the embedding into k partitions. Advancement over the current work is evidenced by the results of experiments on the standard benchmarks.},
added-at = {2009-03-12T15:42:50.000+0100},
address = {New York, NY, USA},
author = {Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y.},
biburl = {https://www.bibsonomy.org/bibtex/228d328daa078e256593a2da3ef42c8e5/lillejul},
booktitle = {DAC '93: Proceedings of the 30th international conference on Design automation},
citeulike-article-id = {4043291},
doi = {http://dx.doi.org/10.1145/157485.165117},
interhash = {6345f0858370841043e0c4235722c672},
intrahash = {28d328daa078e256593a2da3ef42c8e5},
isbn = {0-89791-577-1},
keywords = {clustering entityguides graph},
location = {Dallas, Texas, United States},
pages = {749--754},
posted-at = {2009-02-13 12:15:50},
priority = {2},
publisher = {ACM},
timestamp = {2009-03-12T15:42:50.000+0100},
title = {Spectral K-way ratio-cut partitioning and clustering},
url = {http://dx.doi.org/10.1145/157485.165117},
year = 1993
}