A Combinatorial View of Graph Laplacians

Huang, J

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

A Combinatorial View of Graph Laplacians

MPS-Authors

/persons/resource/persons83983

Huang, J
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

MPIK-TR-144.pdf
(Publisher version), 204KB

Supplementary Material (public)

There is no public supplementary material available

Citation

Huang, J.(2005). A Combinatorial View of Graph Laplacians (144). Tübingen, Germany: Max Planck Institute for Biological Cybernetics.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0013-D499-0

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.