Article

Learning on graph with Laplacian regularization

Authors:

Rie Kubota Ando,

Tong ZhangAuthors Info & Claims

NIPS'06: Proceedings of the 20th International Conference on Neural Information Processing Systems

Pages 25 - 32

Published: 04 December 2006 Publication History

Publisher Site

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.

References

[1]

M. Belkin and P. Niyogi. Semi-supervised learning on Riemannian manifolds. Machine Learning, Special Issue on Clustering:209-239, 2004.

Digital Library

Google Scholar

[2]

F. R. Chung. Spectral Graph Theory. Regional Conference Series in Mathematics. American Mathematical Society, Rhode Island, 1998.

Google Scholar

[3]

A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849-856, 2001.

Digital Library

Google Scholar

[4]

J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell, 22:888-905, 2000.

Digital Library

Google Scholar

[5]

M. Szummer and T. Jaakkola. Partially labeled classification with Markov random walks. In NIPS 2001, 2002.

Google Scholar

[6]

T. Zhang and R. K. Ando. Analysis of spectral kernel design based semi-supervised learning. In NIPS, 2006.

Google Scholar

[7]

D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schlkopf. Learning with local and global consistency. In NIPS 2003, pages 321-328, 2004.

Google Scholar

[8]

X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In ICML 2003, 2003.

Google Scholar

Cited By

View all

Verma SZhang ZTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Stability and Generalization of Graph Convolutional Neural NetworksProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330956(1539-1548)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330956
Gao HPei JHuang HTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Conditional Random Field Enhanced Graph Convolutional Neural NetworksProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330888(276-284)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330888
Sharpnack JSingh A(2010)Identifying graph-structured activation patterns in networksProceedings of the 24th International Conference on Neural Information Processing Systems - Volume 210.5555/2997046.2997134(2137-2145)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997046.2997134

Index Terms

Learning on graph with Laplacian regularization

Index terms have been assigned to the content through auto-classification.

Recommendations

Laplacian spectra of regular graph transformations

Given a graph G with vertex set V(G)=V and edge set E(G)=E, let G^l be the line graph and G^c the complement of G. Let G^0 be the graph with V(G^0)=V and with no edges, G^1 the complete graph with the vertex set V, G^+=G and G^-=G^c. Let B(G) (B^c(G)) ...
Local linear Laplacian eigenmaps

We have derived local linear Laplacian eigenmaps (LLLE) a manifold learning algorithm.The LLLE finds multiple local linear structures.The LLLE used P artificial neighbors to construct the adjacency graph.The experimental results indicate that it can ...
Supervised discriminant Isomap with maximum margin graph regularization for dimensionality reduction
Graphical abstract

Display Omitted
Highlights
- Two novel DR methods are proposed to extract critical discriminative information.
Abstract
As one of the most popular nonlinear dimensionality reduction methods, Isomap has been widely used in pattern recognition and machine learning. However, Isomap has the following problems: (1) Isomap is an unsupervised dimensionality ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

NIPS'06: Proceedings of the 20th International Conference on Neural Information Processing Systems

December 2006

1632 pages

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 04 December 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
1
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Verma SZhang ZTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Stability and Generalization of Graph Convolutional Neural NetworksProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330956(1539-1548)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330956
Gao HPei JHuang HTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Conditional Random Field Enhanced Graph Convolutional Neural NetworksProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330888(276-284)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330888
Sharpnack JSingh A(2010)Identifying graph-structured activation patterns in networksProceedings of the 24th International Conference on Neural Information Processing Systems - Volume 210.5555/2997046.2997134(2137-2145)Online publication date: 6-Dec-2010
https://dl.acm.org/doi/10.5555/2997046.2997134

Abstract

References

Cited By

Index Terms

Recommendations

Laplacian spectra of regular graph transformations

Local linear Laplacian eigenmaps

Supervised discriminant Isomap with maximum margin graph regularization for dimensionality reduction

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations