A basic problem in spectral clustering is the following. If a solution obtained from the spectral relaxation is close to an integral solution, is it possible to find this integral solution even though they might be in completely different basis? In this paper, we propose a new spectral clustering algorithm. It can recover a @math -partition such that the subspace corresponding to the span of its indicator vectors is @math close to the original subspace in spectral norm with @math being the minimum possible ( @math always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a @math -partition closer than @math . We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest @math -partition in a graph where each cluster have expansion at most @math provided @math where @math is the @math eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required @math .
Perhaps the simplest case of is when there is a gap between the @math smallest eigenvalue of Laplacian matrix, @math , and @math of the form ( k+1 1 . ) One might think of this as a stability criteria: It implies that all @math -partitions with maximum expansion @math are @math -close to each other. To put it in another way, approximating the optimum @math -partition is at least as easy as finding a @math -partition with minimum possible expansion among all its clusters. For the case of @math , it is trivial to show that thresholding the second smallest eigenvector of Laplacian yields @math -close partition to the optimal one. On the other hand, when @math , the best prior result is due to @cite_6 , which can find a @math -partition that is @math -close to the optimal one. In other words, when @math , there is no algorithm known to find a non-trivial approximation of the optimum @math -partition.
@cite_6
2148070710
This paper presents a new spectral partitioning formulation which directly incorporates vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with arbitrary vertex size improve by 22 when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with arbitrary-size and unit-size vertices; average improvements of 17 and 18 are observed for graphs with arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.