{
  "id": "2007.05627",
  "version": "v1",
  "published": "2020-07-10T22:03:43.000Z",
  "updated": "2020-07-10T22:03:43.000Z",
  "title": "A Performance Guarantee for Spectral Clustering",
  "authors": [
    "March Boedihardjo",
    "Shaofeng Deng",
    "Thomas Strohmer"
  ],
  "categories": [
    "stat.ML",
    "cs.LG"
  ],
  "abstract": "The two-step spectral clustering method, which consists of the Laplacian eigenmap and a rounding step, is a widely used method for graph partitioning. It can be seen as a natural relaxation to the NP-hard minimum ratio cut problem. In this paper we study the central question: when is spectral clustering able to find the global solution to the minimum ratio cut problem? First we provide a condition that naturally depends on the intra- and inter-cluster connectivities of a given partition under which we may certify that this partition is the solution to the minimum ratio cut problem. Then we develop a deterministic two-to-infinity norm perturbation bound for the the invariant subspace of the graph Laplacian that corresponds to the $k$ smallest eigenvalues. Finally by combining these two results we give a condition under which spectral clustering is guaranteed to output the global solution to the minimum ratio cut problem, which serves as a performance guarantee for spectral clustering.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-10T22:03:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "spectral clustering",
      "performance guarantee",
      "np-hard minimum ratio cut problem",
      "deterministic two-to-infinity norm perturbation bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}