Learning on Graph with Laplacian Regularization
Abstract
We consider a general form of transductive learning on graphs with Laplacian regularization, and derive margin-based generalization bounds using appropriate geometric properties of the graph. We use this analysis to obtain a better understanding of the role of normalization of the graph Laplacian matrix as well as the effect of dimension reduction. The results suggest a limitation of the standard degree-based normalization. We propose a remedy from our analysis and demonstrate empirically that the remedy leads to improved classification performance.
Cite
Text
Ando and Zhang. "Learning on Graph with Laplacian Regularization." Neural Information Processing Systems, 2006.Markdown
[Ando and Zhang. "Learning on Graph with Laplacian Regularization." Neural Information Processing Systems, 2006.](https://mlanthology.org/neurips/2006/ando2006neurips-learning/)BibTeX
@inproceedings{ando2006neurips-learning,
title = {{Learning on Graph with Laplacian Regularization}},
author = {Ando, Rie K. and Zhang, Tong},
booktitle = {Neural Information Processing Systems},
year = {2006},
pages = {25-32},
url = {https://mlanthology.org/neurips/2006/ando2006neurips-learning/}
}