document: A fast kernel-based multilevel algorithm for graph clustering Graph clustering ( also called graph partitioning ) -- clustering the nodes of a graph -- is an important problem in diverse data mining applications . Traditional approaches involve optimization of graph clustering objectives such as normalized cut or ratio association ; spectral methods are widely used for these objectives , but they require eigenvector computation which can be slow . Recently , graph clustering with a general cut objective has been shown to be mathematically equivalent to an appropriate weighted kernel k-means objective function . In this paper , we exploit this equivalence to develop a very fast multilevel algorithm for graph clustering . Multilevel approaches involve coarsening , initial partitioning and refinement phases , all of which may be specialized to different graph clustering objectives . Unlike existing multilevel clustering approaches , such as METIS , our algorithm does not constrain the cluster sizes to be nearly equal . Our approach gives a theoretical guarantee that the refinement step decreases the graph cut objective under consideration . Experiments show that we achieve better final objective function values as compared to a state-of-the-art spectral clustering algorithm : on a series of benchmark test graphs with up to thirty thousand nodes and one million edges , our algorithm achieves lower normalized cut values in 67 % of our experiments and higher ratio association values in 100 % of our experiments . Furthermore , on large graphs , our algorithm is significantly faster than spectral methods . Finally , our algorithm requires far less memory than spectral methods ; we cluster a 1.2 million node movie network into 5000 clusters , which due to memory requirements can not be done directly with spectral methods .
doc_bio_tags: O O O O O O B I B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O