research-article

Weighted Graph Cuts without Eigenvectors A Multilevel Approach

Authors:

Inderjit S. Dhillon,

Brian KulisAuthors Info & Claims

IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 29, Issue 11

Pages 1944 - 1957

https://doi.org/10.1109/TPAMI.2007.1115

Published: 01 November 2007 Publication History

Abstract

A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions used in these seemingly different methods--in particular, a general weighted kernel k-means objective is mathematically equivalent to a weighted graph clustering objective. We exploit this equivalence to develop a fast, high-quality multilevel algorithm that directly optimizes various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous multilevel graph partitioning methods, such as Metis, have suffered from the restriction of equal-sized clusters; our multilevel algorithm removes this restriction by using kernel k-means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis and gene network analysis.

References

[1]

B. Schölkopf, A. Smola, and K.-R. Müller, “Nonlinear Component Analysis as a Kernel Eigenvalue Problem,” Neural Computation, vol. 10, pp. 1299-1319, 1998.

Digital Library

[2]

J. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,” Proc. Fifth Berkeley Symp. Math. Statistics and Probability, pp. 281-296, 1967.

[3]

W.E. Donath and A.J. Hoffman, “Lower Bounds for the Partitioning of Graphs,” IBM J. Research and Development, vol. 17, pp. 422-425, 1973.

Digital Library

[4]

K.M. Hall, “An R-Dimensional Quadratic Placement Algorithm,” Management Science, vol. 11, no. 3, pp. 219-229, 1970.

Digital Library

[5]

P. Chan, M. Schlag, and J. Zien, “Spectral $k$ -Way Ratio Cut Partitioning,” IEEE Trans. CAD-Integrated Circuits and Systems, vol. 13, pp. 1088-1096, 1994.

Digital Library

[6]

J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.

Digital Library

[7]

A.Y. Ng, M. Jordan, and Y. Weiss, “On Spectral Clustering: Analysis and an Algorithm,” Proc. 14th Advances in Neural Information Processing Systems, 2001.

[8]

F. Bach and M. Jordan, “Learning Spectral Clustering,” Proc. 17th Advances in Neural Information Processing Systems, 2004.

[9]

I. Dhillon, Y. Guan, and B. Kulis, “Kernel $k$ -Means, Spectral Clustering and Normalized Cuts,” Proc. 10th ACM Knowledge Discovery and Data Mining Conf., pp. 551-556, 2004.

Digital Library

[10]

H. Zha, C. Ding, M. Gu, X. He, and H. Simon, “Spectral Relaxation for $k$ -Means Clustering,” Proc. Neural Information Processing Systems, 2001.

[11]

V. Roth, J. Laub, M. Kawanabe, and J. Buhmann, “Optimal Cluster Preserving Embedding of Non-Metric Proximity Data,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 12, Dec. 2003.

Digital Library

[12]

G. Karypis and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” SIAM J. Scientific Computing, vol. 20, no. 1, pp. 359-392, 1999.

Digital Library

[13]

B. Hendrickson and R. Leland, “A Multilevel Algorithm for Partitioning Graphs,” Technical Report SAND93-1301, Sandia Nat'l Laboratories, 1993.

[14]

B. Kernighan and S. Lin, “An Efficient Heuristic Procedure for Partitioning Graphs,” The Bell System Technical J., vol. 49, no. 2, pp.291-307, 1970.

[15]

N. Cristianini and J. Shawe-Taylor, Introduction to Support Vector Machines: And Other Kernel-Based Learning Methods. Cambridge Univ. Press, 2000.

Digital Library

[16]

S.X. Yu and J. Shi, “Multiclass Spectral Clustering,” Proc. Int'l Conf. Computer Vision, 2003.

Digital Library

[17]

R. Zass and A. Shashua, “A Unifying Approach to Hard and Probabilistic Clustering,” Proc. 10th IEEE Conf. Computer Vision, 2005.

Digital Library

[18]

G. Golub and C. Van Loan, Matrix Computations. Johns Hopkins Univ. Press, 1989.

[19]

I. Dhillon, Y. Guan, and B. Kulis, “A Unified View of Kernel $k$ -Means, Spectral Clustering and Graph Cuts,” Technical Report TR-04-25, Univ. of Texas at Austin, 2004.

[20]

I.S. Dhillon, Y. Guan, and J. Kogan, “Iterative Clustering of High Dimensional Text Data Augmented by Local Search,” Proc. 2002 IEEE Int'l Conf. Data Mining, pp. 131-138, 2002.

Digital Library

[21]

M. Strong, T. Graeber, M. Beeby, M. Pellegrini, M. Thompson, T. Yeates, and D. Eisenberg, “Visualization and Interpretation of Protein Networks in Mycobacterium Tuberculosis Based on Hierarchical Clustering of Genome-Wide Functional Linkage Maps,” Nucleic Acids Research, vol. 31, no. 24, pp. 7099-7109, 2003.

[22]

E.M. Marcotte, M. Pellegrini, H.-L. Ng, D.W. Rice, T.O. Yeates, and D. Eisenberg, “Detecting Protein Function and Protein-Protein Interactions from Genome Sequences,” Science, vol. 285, pp. 751-753, 1999.

[23]

M. Pellegrini, E.M. Marcotte, M.J. Thompson, D. Eisenberg, and T.O. Yeates, “Detecting the Components of Protein Complexes and Pathways by Comparative Genome Analysis: Protein Phylogenetic Profiles,” Proc. Nat'l Academy of Sciences, vol. 96, pp. 4285-4288, 1999.

[24]

M. Strong, P. Mallick, M. Pellegrini, M. Thompson, and D. Eisenberg, “Inference of Protein Function and Protein Linkages in Mycobacterium Tuberculosis Based on Prokaryotic Genome Organization: A Combined Computational Approach,” Genome Biology, vol. 4, R59.1-16, 2003.

[25]

R. Overbeek, M. Fonstein, M. D'Souza, G. Pusch, and N. Maltsev, “The Use of Gene Clusters to Infer Functional Coupling,” Proc. Nat'l Academy of Sciences, vol. 96, no. 6, pp. 2896-2901, 1999.

[26]

T. Davis, “Univ. of Florida Sparse Matrix Collection,” vol. 92, no. 42, 1994, vol. 96, no. 28, 1996; vol. 97, no. 23, 1997, http://www.cise.ufl.edu/research/sparse/matrices.

[27]

M. Girolami, “Mercer Kernel Based Clustering in Feature Space,” IEEE Trans. Neural Networks, vol. 13, no. 4, pp. 669-688, 2002.

Digital Library

[28]

N. Cristianini, J. Shawe-Taylor, and J. Kandola, “Spectral Kernel Methods for Clustering,” Proc. 14th Advances in Neural Information Processing Systems, 2001.

[29]

C. Chennubhotla and A. Jepson, “Hierarchical Eigensolver for Transition Matrices in Spectral Methods,” Proc. 17th Advances in Neural Information Processing Systems, 2004.

Digital Library

[30]

I. Dhillon, Y. Guan, and B. Kulis, “A Fast Kernel-Based Multilevel Algorithm for Graph Clustering,” Proc. 11th ACM Knowledge Discovery and Data Mining Conf., pp. 629-634, 2005.

Digital Library

Cited By

Cini AMandic DAlippi CSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Graph-based time series clustering for end-to-end hierarchical forecastingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692429(8985-8999)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692429
Hashemi MGong SNi JFan WPrakash BJin WLarson K(2024)A comprehensive survey on graph reductionProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/891(8058-8066)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/891
Yang ZZhang GWu JYang JSheng QXue SZhou CAggarwal CPeng HHu WHancock ELiò P(2024)State of the Art and Potentialities of Graph-level LearningACM Computing Surveys10.1145/369586357:2(1-40)Online publication date: 10-Oct-2024
https://dl.acm.org/doi/10.1145/3695863
Show More Cited By

Index Terms

Weighted Graph Cuts without Eigenvectors A Multilevel Approach

Recommendations

The global kernel k-means algorithm for clustering in feature space

Kernel k-means is an extension of the standard k-means clustering algorithm that identifies nonlinearly separable clusters. In order to overcome the cluster initialization problem associated with this method, we propose the global kernel k-means ...
Proficient Normalised Fuzzy K-Means With Initial Centroids Methodology

This article describes how data is relevant and if it can be organized, linked with other data and grouped into a cluster. Clustering is the process of organizing a given set of objects into a set of disjoint groups called clusters. There are a number ...
ModEx and Seed-Detective

In this paper we present two clustering techniques called ModEx and Seed-Detective. ModEx is a modified version of an existing clustering technique called Ex-Detective. It addresses some limitations of Ex-Detective. Seed-Detective is a combination of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Pattern Analysis and Machine Intelligence

IEEE Transactions on Pattern Analysis and Machine Intelligence Volume 29, Issue 11

November 2007

191 pages

ISSN:0162-8828

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 November 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

273
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cini AMandic DAlippi CSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Graph-based time series clustering for end-to-end hierarchical forecastingProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692429(8985-8999)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692429
Hashemi MGong SNi JFan WPrakash BJin WLarson K(2024)A comprehensive survey on graph reductionProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/891(8058-8066)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/891
Yang ZZhang GWu JYang JSheng QXue SZhou CAggarwal CPeng HHu WHancock ELiò P(2024)State of the Art and Potentialities of Graph-level LearningACM Computing Surveys10.1145/369586357:2(1-40)Online publication date: 10-Oct-2024
https://dl.acm.org/doi/10.1145/3695863
Zhou SXu HZheng ZChen JLi ZBu JWu JWang XZhu WEster M(2024)A Comprehensive Survey on Deep Clustering: Taxonomy, Challenges, and Future DirectionsACM Computing Surveys10.1145/368903657:3(1-38)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3689036
Fujiwara YKumagai AIda YNakano MNakatsuji MKimura A(2024)Efficient Algorithm for K-Multiple-MeansProceedings of the ACM on Management of Data10.1145/36392732:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639273
Hanauer KHenzinger MMünk RRäcke HVötsch MBaeza-Yates RBonchi F(2024)Expander Hierarchies for Normalized Cuts on GraphsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671978(1016-1027)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671978
Qin MZhang CGao YZhang WYeung DBaeza-Yates RBonchi F(2024)Pre-train and Refine: Towards Higher Efficiency in K-Agnostic Community Detection without Quality DegradationProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671686(2467-2478)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671686
Kumar MKumar S(2024)Unveiling Graph Structures for Machine Learning: Learning, Structuring, and CoarseningProceedings of the 7th Joint International Conference on Data Science & Management of Data (11th ACM IKDD CODS and 29th COMAD)10.1145/3632410.3633290(484-488)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3632410.3633290
Kang DMei QKim SChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Low Mileage, High Fidelity: Evaluating Hypergraph Expansion Methods by Quantifying the Information LossProceedings of the ACM Web Conference 202410.1145/3589334.3645657(959-968)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645657
Zhuang JZeng PZhuang WGuo XLiu P(2024)Supervertex Sampling Network: A Geodesic Differential SLIC Approach for 3D MeshIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.329484530:8(5553-5565)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3294845
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents