Header logo is

A Combinatorial View of Graph Laplacians


Technical Report


Discussions about different graph Laplacian, mainly normalized and unnormalized versions of graph Laplacian, have been ardent with respect to various methods in clustering and graph based semi-supervised learning. Previous research on graph Laplacians investigated their convergence properties to Laplacian operators on continuous manifolds. There is still no strong proof on convergence for the normalized Laplacian. In this paper, we analyze different variants of graph Laplacians directly from the ways solving the original graph partitioning problem. The graph partitioning problem is a well-known combinatorial NP hard optimization problem. The spectral solutions provide evidence that normalized Laplacian encodes more reasonable considerations for graph partitioning. We also provide some examples to show their differences.

Author(s): Huang, J.
Number (issue): 144
Year: 2005
Month: August
Day: 28

Department(s): Empirical Inference
Bibtex Type: Technical Report (techreport)

Institution: Max Planck Institute for Biological Cybernetics, Tübingen, Germany

Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik


  title = {A Combinatorial View of Graph Laplacians},
  author = {Huang, J.},
  number = {144},
  organization = {Max-Planck-Gesellschaft},
  institution = {Max Planck Institute for Biological Cybernetics, T{\"u}bingen, Germany},
  school = {Biologische Kybernetik},
  month = aug,
  year = {2005},
  month_numeric = {8}