Weighted Graph Cuts without Eigenvectors A Multilevel Approach
Pourquoi ce travail est-il dans la base ?
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Aucune affiliation canadienne. Une base fondée sur la seule affiliation (le devis habituel) n'aurait jamais vu ce travail. C'est l'un des travaux qui justifient l'inversion de la base.
Résumé
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.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
La notice
- Revue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Thématique
- Complex Network Analysis Techniques
- Domaine
- Physics and Astronomy
- Établissements canadiens
- —
- Organismes subventionnaires
- National Science Foundation
- Mots-clés
- Cluster analysisCorrelation clusteringSpectral clusteringRand indexComputer sciencePattern recognition (psychology)Kernel (algebra)Hierarchical clusteringCanopy clustering algorithmClustering coefficientGraph partitionComputationCURE data clustering algorithmGraphAlgorithmMathematicsArtificial intelligenceTheoretical computer scienceCombinatorics
- Résumé présent dans OpenAlex
- oui