On clusterings-good, bad and spectral

By R. Kannan, Santosh Srinivas Vempala, Adrian R. Vetta. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000

1,270 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/f36bfb04f8ff4d10aaa204b5338d2234f05c97d2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Spectral Sparsification of Graphs (2008, methodology): “ying such a guarantee to certify that the complement of a small cut has high conductance. If we were to just apply the algorithm until it cannot cut any more, as was done by Kannan, Vempala and Vetta [KVV04], our algorithm could take at least quadratic time. Theorem 8.1 (ApproxCut). Let φ,p ∈ (0,1) ”
Towards a theoretical foundation for Laplacian-based manifold methods (2005, methodology): “…graph-motivated learning methods have been recently proposed for various problems and applications, including [26,32,3,14,12] for visualization and data representation, [38,34,37,10,27,5,2,31] for partially supervised classi(cid:12)cation and [30,33,28,21,17], among others, for spectral clustering.”
Ant-based and swarm-based clustering (2007, methodology): “Classical clustering methods include deterministic algorithms, such as hierarchical clustering (Vorhees 1985) and spectral methods (Ng et al. 2001; Kannan et al. 2004), as well as randomized methods, such as k-means (MacQueen 1967) and Kohonen networks (Kohonen 1997).”
A Unified Framework for Model-based Clustering (2003, positive): “Indeed, both traditional k-means and HAC algorithms fail miserably on these two datasets, whereas the spectral clustering algorithms (Kannan et al., 2000; Ng et al., 2002) identify the four natural clusters in d4, and a hybrid graph partitioning approach (Karypis et al.”
Algorithmic Prediction of Health-Care Costs (2008, methodology): “Our prediction clustering method centers around the algorithm behind EigenCluster, a searchand-cluster engine developed in Kannan et al. (2004).”
Learning Segmentation by Random Walks (2000, methodology): “More recently, [2] uses them to define a new criterion for clustering.”
Statistical properties of community structure in large social and information networks (2008, background): “For point (3), we choose a natural and widely-adopted notion of community goodness called conductance, also known as the normalized cut metric [6, 31, 16].”
Neighborhood formation and anomaly detection in bipartite graphs (2005, methodology): “Graph Partitioning: Popular methods for partitioning graphs include the METIS algorithm [11], spectral partitioning techniques [10], flow-based methods [6] information-theoretic methods [5], and methods based on the “betweenness” of edges [7], among others.”
Graph mining: Laws, generators, and algorithms (2006, neutral): “In general, graph partitioning algorithms are slow; for example, spectral methods taking polynomial time might still be too slow for problems on large graphs [Kannan et al. 2000].”
Name disambiguation in author citations using a K-way spectral clustering method (2005, methodology): “Spectral clustering methods compute eigenvalues and eigenvectors of a Laplacian matrix (or singular values and singular vectors of certain matrix) related to the given graph, and construct data clusters based on such spectral information [19, 28, 36, 40, 42].”
On Modularity Clustering (2008, methodology): “However, structurally the two clusterings disagree on the two small clusters, whereas a clustering based on iterative conductance cutting [20] (shapes) achieves the same quality (0.”
SybilInfer: Detecting Sybil Nodes using Social Networks (2009, background): “· |TX | |TX | · 1 |X| ⇒ (3) EXX = 0 (4) As a result, by sufficiently increasing the number of random walks T performed on the social graph, we can get EXX arbitrarily close to zero.”
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning (2008, methodology): “kely to appear in a short random walk from the input vertex. In Section 3, we use a local graph exploration process to ﬁnd a cluster that is near the input vertex. Following Kannan, Vempala and Vetta [KVV04], we say that a set of vertices is a good cluster if it has low conductance; that is, if it h”
A Comprehensive Survey on Community Detection With Deep Learning (2021, background): “Combo [61] optimizes normalized mutual information (NMI) [62], [63] and conductance (CON) [64].”
Experiments on Graph Clustering Algorithms (2003, methodology): “Other more advanced partition techniques involve spectral information as in [3,7,8,9].”