text: Clustering is a fundamental task in data analysis, and spectral clustering has been recognized as a promising approach to it. Given a graph describing the relationship between data, spectral clustering explores the underlying cluster structure in two stages. The first stage embeds the nodes of the graph into real space, and the second stage groups the embedded nodes into several clusters. The use of the @math -means method in the grouping stage is currently standard practice. We present a spectral clustering algorithm that uses convex programming in the grouping stage, and study how well it works. The concept behind the algorithm design lies in the following observation. The nodes with the largest degree in each cluster may be found by computing an enclosing ellipsoid for embedded nodes in real space, and the clusters may be identified by using those nodes. We show that the observations are valid, and the algorithm returns clusters to provide the conductance of graph, if the gap assumption, introduced by Peng el al. at COLT 2015, is satisfied. We also give an experimental assessment of the algorithm's performance.
  @cite_20: In this paper we study variants of the widely used spectral clustering that partitions a graph into @math clusters by (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix and (2) grouping the embedded points into @math clusters via @math -means algorithms. We show that, for a wide class of graphs, spectral clustering gives a good approximation of the optimal clustering. While this approach was proposed in the early 1990s and has comprehensive applications, prior to our work similar results were known only for graphs generated from stochastic models. We also give a nearly linear time algorithm for partitioning well-clustered graphs based on computing a matrix exponential and approximate nearest neighbor data structures.
summary: We describe the results of in @cite_20 . Let @math be the clusters of an optimal @math -way partition for the conductance problem. We choose an algorithm for solving the minimization problem of @math shown in ) and suppose that the algorithm has an approximation ratio of @math . Let @math be the output of a spectral clustering algorithm that uses a @math -means method based on the @math -approximation algorithm. They showed the following statement in Theorem 1.2 of @cite_20 . Set @math as and suppose that @math is so large that @math . After suitable renumbering of the output of the algorithm, we have Accordingly, if @math , those can be written as Here, the notation @math denotes the symmetric difference of the sets @math and @math . The results tell us that, if @math is large, the difference between @math and @math is small and the conductance of @math is close to that of @math . also developed a nearly linear time algorithm and examined the performance.