Online Learning over Graphs
Abstract
We apply classic online learning techniques similar to the perceptron algorithm to the problem of learning a function defined on a graph. The benefit of our approach includes simple algorithms and performance guarantees that we naturally interpret in terms of structural properties of the graph, such as the algebraic connectivity or the diameter of the graph. We also discuss how these methods can be modified to allow active learning on a graph. We present preliminary experiments with encouraging results.
Cite
Text
Herbster et al. "Online Learning over Graphs." International Conference on Machine Learning, 2005. doi:10.1145/1102351.1102390Markdown
[Herbster et al. "Online Learning over Graphs." International Conference on Machine Learning, 2005.](https://mlanthology.org/icml/2005/herbster2005icml-online/) doi:10.1145/1102351.1102390BibTeX
@inproceedings{herbster2005icml-online,
title = {{Online Learning over Graphs}},
author = {Herbster, Mark and Pontil, Massimiliano and Wainer, Lisa},
booktitle = {International Conference on Machine Learning},
year = {2005},
pages = {305-312},
doi = {10.1145/1102351.1102390},
url = {https://mlanthology.org/icml/2005/herbster2005icml-online/}
}