Carnegie Mellon University
file.pdf (2.23 MB)

Graph Partitioning by Spectral Rounding: Applications in Image Segmentation and Clustering

Download (2.23 MB)
journal contribution
posted on 1994-02-01, 00:00 authored by Gary L. Miller, David Tolliver
We introduce a new family of spectral partitioning methods. Edge separators of a graph are produced by iteratively reweighting the edges until the graph disconnects into the prescribed number of components. At each iteration a small number of eigenvectors with small eigenvalue are computed and used to determine the reweighting. In this way spectral rounding directly produces discrete solutions where as current spectral algorithms must map the continuous eigenvectors to discrete solutions by employing a heuristic geometric separator (e.g. k-means). We show that spectral rounding compares favorably to current spectral approximations on the Normalized Cut criterion (NCut). Results are given in the natural image segmentation, medical image segmentation, and clustering domains. A practical version is shown to converge.


Publisher Statement

Copyright © 1994 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.



Usage metrics


    Ref. manager