Spectral clustering based on the graph p-Laplacian

ABSTRACT

We present a generalized version of spectral clustering using the graph p-Laplacian, a nonlinear generalization of the standard graph Laplacian. We show that the second eigenvector of the graph p-Laplacian interpolates between a relaxation of the normalized and the Cheeger cut. Moreover, we prove that in the limit as p → 1 the cut found by thresholding the second eigenvector of the graph p-Laplacian converges to the optimal Cheeger cut. Furthermore, we provide an efficient numerical scheme to compute the second eigenvector of the graph p-Laplacian. The experiments show that the clustering found by p-spectral clustering is at least as good as normal spectral clustering, but often leads to significantly better results.

REFERENCES

• 1: Amghibech, S. (2003). Eigenvalues of the discrete p-Laplacian for graphs. Ars Combin., 67, 283--302.
• 2: Bertsekas, D. (1999). Nonlinear programming. Athena Scientific.
• 3: Bühler, T., & Hein, M. (2009). Supplementary material. http://www.ml.uni-saarland.de/Publications/BueHei09tech.pdf.
• 4: Chung, F. (1997). Spectral graph theory. AMS.
• 5: Tijl De Bie , Nello Cristianini, Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems, The Journal of Machine Learning Research, 7, p.1409-1436, 12/1/2006
• 6: Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Math. J., 23, 298--305.
• 7: Hagen, L., & Kahng, A. B. (1991). Fast spectral methods for ratio cut partitioning and clustering. Proc. IEEE Intl. Conf. on Computer-Aided Design, 10--13.
• 8: Matthias Hein , Jean-Yves Audibert , Ulrike von Luxburg, Graph Laplacians and their Convergence on Random Neighborhood Graphs, The Journal of Machine Learning Research, 8, p.1325-1370, 12/1/2007
• 9: Paige, C., & Saunders, M. (1975). Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal., 12, 617--629.
• 10: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 11: Ulrike Luxburg, A tutorial on spectral clustering, Statistics and Computing, v.17 n.4, p.395-416, December 2007 [doi>10.1007/s11222-007-9033-z]
• 12: Zhou, D., & Schöölkopf, B. (2005). Regularization on discrete spaces. Deutsche Arbeitsgemeinschaft für Mustererkennung-Symposium (pp. 361--368).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)
      G.1.6 Optimization
          Subjects: Nonlinear programming
      G.1.8 Partial Differential Equations
          Subjects: Spectral methods

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory