Ravi Kannan, Santosh Vempala and Adrian Vetta<ref>{{cite journal|last1=Kannan|first1=Ravi|last2=Vempala|first2=Santosh|last3=Vetta|first3=Adrian|title=On Clusterings : Good, Bad and Spectral|journal=Journal of the ACM|volume= 51|issue=3|doi=10.1145/990308.990313|pages=497–515|year=2004|s2cid=207558562}}</ref> proposed a bicriteria measure to define the quality of a given clustering. They said that a clustering was an (α, ε)-clustering if the [[Conductance (graph)|conductance]] of each cluster (in the clustering) was at least α and the weight of the inter-cluster edges was at most ε fraction of the total weight of all the edges in the graph. They also look at two approximation algorithms in the same paper.
== Approximate solutions ==
Spectral clustering is computationally expensive unless the graph is sparse and the similarity matrix can be efficiently constructed. If the similarity matrix is an RBF kernel matrix, spectral clustering is expensive. There are approximate algorithms for making spectral clustering more efficient: power method,<ref>{{Cite journal|last=Boutsidis|first=Christos|date=2015|title=Spectral Clustering via the Power Method Provably|url=http://proceedings.mlr.press/v37/boutsidis15.pdf|journal=International Conference on Machine Learning}}</ref> Nystrom method,<ref>{{Cite journal|last=Fowlkes|first=C|date=2004|title=Spectral grouping using the Nystrom method.|url=https://escholarship.org/uc/item/29z29233|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=26|issue=2|pages=214–25|doi=10.1109/TPAMI.2004.1262185|pmid=15376896|s2cid=2384316}}</ref> etc. However, recent research<ref>{{Cite journal|last=S. Wang, A. Gittens, and M. W. Mahoney|year=2019|title=Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds|journal=Journal of Machine Learning Research|volume=20|pages=1–49|arxiv=1706.02803}}</ref> pointed out the problems with spectral clustering with Nystrom method; in particular, the similarity matrix with Nystrom approximation is not elementwisely positive, which can be problematic.
