The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Weighted Graph Cuts without Eigenvectors A Multilevel Approach
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
(1967) · Cited by 23,719
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
An Introduction to Support Vector Machines and Other Kernel-based Learning Methods
Cristianini, N., & Shawe-Taylor, J. (2000) · doi:10.1017/cbo9780511801389 · Cited by 13,855
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159
Nonlinear Component Analysis as a Kernel Eigenvalue Problem
Schölkopf, B., Smola, A., & Müller, K.-R. (1998) · Neural Computation · doi:10.1162/089976698300017467 · Cited by 8,084
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
Karypis, G., & Kumar, V. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827595287997 · Cited by 5,762
An Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305
Detecting Protein Function and Protein-Protein Interactions from Genome Sequences
Marcotte, E. M., Pellegrini, M., Ng, H.-L., Rice, D. W., Yeates, T. O., & Eisenberg, D. (1999) · Science · doi:10.1126/science.285.5428.751 · Cited by 1,670
Assigning protein functions by comparative genome analysis: Protein phylogenetic profiles
Pellegrini, M., Marcotte, E. M., Thompson, M. J., Eisenberg, D., & Yeates, T. O. (1999) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.96.8.4285 · Cited by 1,585
Cited by
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000
Graph neural networks: A review of methods and applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020) · AI Open · doi:10.1016/j.aiopen.2021.01.001 · Cited by 6,880
Advances In Deep Learning On Graphs (Gsp'18 Workshop)
Defferrard, M. (2016) · Figshare · doi:10.5281/zenodo.1286817 · Cited by 4,613
Spectral Networks and Locally Connected Networks on Graphs
Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2013) · arXiv · doi:10.48550/arxiv.1312.6203 · Cited by 3,983
Graph convolutional networks: a comprehensive review
Zhang, S., Tong, H., Xu, J., & Maciejewski, R. (2019) · Computational Social Networks · doi:10.1186/s40649-019-0069-y · Cited by 1,888
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs
Monti, F., Boscaini, D., Masci, J., Rodola, E., Svoboda, J., & Bronstein, M. M. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.576 · Cited by 1,820
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
Defferrard, M., Bresson, X., & Vandergheynst, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.09375 · Cited by 1,673
Deep Learning on Graphs: A Survey
Zhang, Z., Cui, P., & Zhu, W. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.2981333 · Cited by 1,633
Defining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-013-0693-z · Cited by 1,411
Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., & Hsieh, C.-J. (2019) · Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3292500.3330925 · Cited by 1,331
Fast Graph Representation Learning with PyTorch Geometric
Fey, M., & Lenssen, J. E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.02428 · Cited by 1,132
Empirical comparison of algorithms for network community detection
Leskovec, J., Lang, K. J., & Mahoney, M. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772755 · Cited by 918
Statistical properties of community structure in large social and information networks
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367591 · Cited by 860
Overlapping community detection at scale: a nonnegative matrix factorization approach
Yang, J., & Leskovec, J. (2013) · Proceedings of the sixth ACM international conference on Web search and data mining · doi:10.1145/2433396.2433471 · Cited by 852
A survey of kernel and spectral methods for clustering
Filippone, M., Camastra, F., Masulli, F., & Rovetta, S. (2008) · Pattern Recognition · doi:10.1016/j.patcog.2007.05.018 · Cited by 827
Hierarchical Graph Representation Learning with Differentiable Pooling
Ying, R., You, J., Morris, C., Ren, X., Hamilton, W. L., & Leskovec, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.08804 · Cited by 798
Defining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2012) · Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics · doi:10.1145/2350190.2350193 · Cited by 762
Towards Internet-scale multi-view stereo
Furukawa, Y., Curless, B., Seitz, S. M., & Szeliski, R. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539802 · Cited by 751
CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters
Levie, R., Monti, F., Bresson, X., & Bronstein, M. M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2879624 · Cited by 685
Learning Deep Representations for Graph Clustering
Tian, F., Gao, B., Cui, Q., Chen, E., & Liu, T.-Y. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8916 · Cited by 657
Community detection in Social Media: Performance and application considerations
Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. (2012) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-011-0224-z · Cited by 615
Parallel Spectral Clustering in Distributed Systems
Chen, W.-Y., Song, Y., Bai, H., Lin, C.-J., & Chang, E. Y. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.88 · Cited by 603
Superpixel segmentation using Linear Spectral Clustering
Li, Z., & Chen, J. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298741 · Cited by 479
Fast approximate spectral clustering
Yan, D., Huang, L., & Jordan, M. I. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557118 · Cited by 474
SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels
Fey, M., Lenssen, J. E., Weichert, F., & Muller, H. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00097 · Cited by 459
3D Hand Shape and Pose Estimation From a Single RGB Image
Ge, L., Ren, Z., Li, Y., Xue, Z., Wang, Y., Cai, J., & Yuan, J. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.01109 · Cited by 458
A Survey on Multiview Clustering
Chao, G., Sun, S., & Bi, J. (2021) · IEEE Transactions on Artificial Intelligence · doi:10.1109/tai.2021.3065894 · Cited by 427
Graph Neural Networks with Convolutional ARMA Filters
Bianchi, F. M., Grattarola, D., Livi, L., & Alippi, C. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3054830 · Cited by 426
Pose2Mesh: Graph Convolutional Network for 3D Human Pose and Mesh Recovery from a 2D Human Pose
Choi, H., Moon, G., & Lee, K. M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-58571-6_45 · Cited by 392
Lee, J., Lee, I., & Kang, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.08082 · Cited by 349
GRAPH MATCHING AND LEARNING IN PATTERN RECOGNITION IN THE LAST 10 YEARS
FOGGIA, P., PERCANNELLA, G., & VENTO, M. (2014) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001414500013 · Cited by 337
FeaStNet: Feature-Steered Graph Convolutions for 3D Shape Analysis
Verma, N., Boyer, E., & Verbeek, J. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00275 · Cited by 324
Graph dual regularization non-negative matrix factorization for co-clustering
Shang, F., Jiao, L. C., & Wang, F. (2012) · Pattern Recognition · doi:10.1016/j.patcog.2011.12.015 · Cited by 314
A gentle introduction to deep learning for graphs
Bacciu, D., Errica, F., Micheli, A., & Podda, M. (2020) · Neural Networks · doi:10.1016/j.neunet.2020.06.006 · Cited by 305
ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations
Ranjan, E., Sanyal, S., & Talukdar, P. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i04.5997 · Cited by 300
Yan, X., Ai, T., Yang, M., & Yin, H. (2019) · ISPRS Journal of Photogrammetry and Remote Sensing · doi:10.1016/j.isprsjprs.2019.02.010 · Cited by 269
Revisiting k-means: New Algorithms via Bayesian Nonparametrics
Kulis, B., & Jordan, M. I. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.0352 · Cited by 262
Self-citationDefining and Evaluating Network Communities Based on Ground-Truth
Yang, J., & Leskovec, J. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.138 · Cited by 254
Large-Scale Image Clustering Based on Camera Fingerprints
Lin, X., & Li, C.-T. (2016) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2636086 · Cited by 46
Inferring lockstep behavior from connectivity pattern in large graphs
Jiang, M., Cui, P., Beutel, A., Faloutsos, C., & Yang, S. (2016) · Knowledge and Information Systems · doi:10.1007/s10115-015-0883-y · Cited by 43
Global and Local Differential Privacy for Collaborative Bandits
Wang, H., Zhao, Q., Wu, Q., Chopra, S., Khaitan, A., & Wang, H. (2020) · Fourteenth ACM Conference on Recommender Systems · doi:10.1145/3383313.3412254 · Cited by 28
Metadata
- Authors
- Dhillon, I. S., Guan, Y., & Kulis, B.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2007-11
- Volume
- 29
- Issue
- 11
- Pages
- 1944-1957
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2135957668
- Cited by
- 1,003
- References
- 25
- FWCI
- 44.13
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.