Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Weighted graph cuts without eigenvectors a multilevel approach.

Inderjit S Dhillon1, Yuqiang Guan, Brian Kulis

  • 1Department of Computer Science, University of Texas at Austin, 1 University Station C0500, Austin, TX 78712-0500, USA. inderjit@cs.utexas.edu

IEEE Transactions on Pattern Analysis and Machine Intelligence
|September 13, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Observation of the blood pressure changes in preterm infants with gestational age of 28 to <37 weeks within 7 days after birth: a single center retrospective study.

Frontiers in pediatrics·2026
Same author

Retrospective study: clinical analysis of Kawasaki disease complicated with macrophage activation syndrome.

Italian journal of pediatrics·2026
Same author

A nonlinear association and threshold effect of healthy eating index-2015 with hypertension in US children and adolescents: a cross-sectional analysis of NHANES 1999-2020.

Journal of health, population, and nutrition·2026
Same author

Non-Exhaustive, Overlapping Clustering.

IEEE transactions on pattern analysis and machine intelligence·2018
Same author

Dynamic Clustering Algorithms via Small-Variance Analysis of Markov Chain Mixture Models.

IEEE transactions on pattern analysis and machine intelligence·2018
Same author

Dual Decomposed Learning with Factorwise Oracles for Structural SVMs of Large Output Domain.

Advances in neural information processing systems·2018
Same journal

HardFlow: Hard-Constrained Sampling for Flow-Matching Models Via Trajectory Optimization.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Industrial Brain: Self-Evolving Neuro-Symbolic Autonomy with Causal Resilience for Cyber-Physical Systems.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Adaptive Hardness-Driven Dictionary Distillation for Incomplete Streaming View Clustering.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Mixture of Global and Local Experts with Diffusion Transformer for Controllable Face Generation.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Task-KV: Task-aware KV Cache Optimization via Semantic Differentiation of Attention Heads.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Achieving Text-based Person Retrieval with Any Granularity.

IEEE transactions on pattern analysis and machine intelligence·2026
See all related articles

This study reveals an equivalence between kernel k-means and graph clustering, enabling a faster, high-quality multilevel algorithm. This new method optimizes graph cuts without eigenvector computations, outperforming spectral clustering for large-scale data analysis.

Area of Science:

  • Machine Learning
  • Data Mining
  • Computational Science

Background:

  • Non-linearly separable data requires advanced clustering algorithms like spectral clustering and kernel k-means.
  • Existing methods often face computational challenges with large datasets.

Purpose of the Study:

  • To establish a mathematical equivalence between kernel k-means and weighted graph clustering objectives.
  • To develop a novel, efficient multilevel algorithm for optimizing graph clustering criteria.

Main Methods:

  • Demonstrated the mathematical equivalence between general weighted kernel k-means and weighted graph clustering objectives.
  • Developed a multilevel algorithm that directly optimizes weighted graph clustering criteria (ratio cut, normalized cut, ratio association).
  • Utilized kernel k-means to optimize weighted graph cuts, removing restrictions on cluster sizes.

Related Experiment Videos

Main Results:

  • The proposed multilevel algorithm achieves high quality and speed, outperforming state-of-the-art spectral clustering.
  • Eliminated the need for computationally expensive eigenvector calculations for graph clustering.
  • Successfully applied to large-scale clustering tasks including image segmentation, social network analysis, and gene network analysis.

Conclusions:

  • The equivalence provides a new perspective on kernel k-means and graph clustering.
  • The developed algorithm offers a significant improvement in efficiency and scalability for large graph clustering problems.
  • The method is versatile and applicable to diverse real-world data analysis challenges.