hide
Free keywords:
-
Abstract:
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.
