Clustering Large Graphs via the Singular Value Decomposition

By Petros Drineas, Alan M. Frieze, R. Kannan, Santosh Srinivas Vempala, V. Vinay. Machine-mediated learning, 2004

544 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/22e1af5abb62afc686ec7e5683bee3bb0d63b7b3

How researchers see this paper

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

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Generalized Low Rank Models (2014, methodology): “For example, it is NP-hard to compute an exact solution to kmeans [43], nonnegative matrix factorization [149], and weighted PCA and matrix completion [50] all of which are special cases of low rank models.”
Data clustering: 50 years beyond K-means (2008, unknown): “…the character ‘f’; (d) three different JðckÞ ¼ X xi2ck jjxi lkjj 2 : The goal of K-means is to minimize the sum of the squared error over all K clusters, JðCÞ ¼ XK k¼1 X xi2ck jjxi lkjj 2 : Minimizing this objective function is known to be an NP-hard problem (even for K = 2) (Drineas et al., 1999).”
Smart Tourist - Passive Mobility Tracking Through Mobile Application (2014, background): “However, the major drawback of his approach was to predeﬁne the value k , which is NP-Hard for arbitrary input [12].”
k-means++: the advantages of careful seeding (2007, background): “Solving this problem exactly is NP-hard, even with just two clusters [10], but twenty-five years ago, Lloyd [20] proposed a local search solution that is still very widely used today (see for example [1, 11, 15]).”
On constrained spectral clustering and its applications (2012, background): “This is a major advantage over constrained K-means clustering, which produces nondeterministic solutions while being intractable even for K = 2 (Drineas et al (2004); Davidson and Ravi (2007b)).”
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering (2018, background): “If we lift the clustering constraints on X and merely assume X to be orthogonal and rank k , A − XX T A 2 F becomes the rank k approximation problem. approximation k k The connection between rank k and k -means is well established, see for example [10, 18, 23].”
Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition (2015, result): “An×d ×Πd×poly(k/ ) = (AΠ)n×poly(k/ ) This approach was developed and refined in several pioneering results, including [33, 34, 35, 36] for column sampling, [37, 5] for random projection, and definitive work by Sarlós [4].”
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (2014, background): “SVD [20] [21] k O(k/ (2)) 2 1 + Thm 7 dk/ e 1 +”
The Effectiveness of Lloyd-Type Methods for the k-Means Problem (2006, background): “Thek-means problem isNP-hard even fork = 2 [13].”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, background): “…2001], recommendation systems [Drineas et al. 2002], information retrieval [Papadimitriou et al. 2000], web search [Achlioptas et al. 2001; Kleinberg 1999], clustering [Drineas et al. 2004; McSherry 2001], and learning mixtures of distributions [Kannan et al. 2008; Achlioptas and McSherry 2005].”
The singular values and vectors of low rank perturbations of large rectangular random matrices (2011, background): “This theoretical justification along with the fact that these vectors can be efficiently computed using now-standard numerical algorithms for the SVD [28] has led to the ubiquity of the SVD in applications such as array processing [51], genomics [1,52], wireless communications [25], information retr”
NP-hardness of Euclidean sum-of-squares clustering (2008, methodology): “Correcting an error in the proof presented in Drineas et al. (2004), we will show that this is always true for any MSSC instance constructed by the proposed transformation.”
Matrix approximation and projective clustering via volume sampling (2006, methodology): “The problem of efficiently finding an approximation to this subspace has received much attention in the past decade [19, 15 , 1, 14, 16].”
Weighted low rank approximations with provable guarantees (2016, background): “Low rank approximation is arguably one of the most wellstudied problems in randomized numerical linear algebra, with diverse applications to clustering [19, 23, 38, 18], data mining [5], distance matrix completion [13], information retrieval [45], learning mixtures of distributions [2, 32], recommen”