Learning Unknown Graphs
Abstract
Motivated by a problem of targeted advertising in social networks, we introduce and study a new model of online learning on labeled graphs where the graph is initially unknown, and the algorithm is free to choose the next vertex to predict. After observing that natural nonadaptive exploration/prediction strategies (like depth-first with majority vote) badly fail on simple binary labeled graphs, we introduce an adaptive strategy that performs well under the hypothesis that the vertices of the unknown graph (i.e., the members of the social network) can be partitioned into a few well-separated clusters within which labels are roughly constant (i.e., members in the same cluster tend to prefer the same products). Our algorithm is efficiently implementable and provably competitive against the best of these partitions.
Cite
Text
Cesa-Bianchi et al. "Learning Unknown Graphs." International Conference on Algorithmic Learning Theory, 2009. doi:10.1007/978-3-642-04414-4_13Markdown
[Cesa-Bianchi et al. "Learning Unknown Graphs." International Conference on Algorithmic Learning Theory, 2009.](https://mlanthology.org/alt/2009/cesabianchi2009alt-learning/) doi:10.1007/978-3-642-04414-4_13BibTeX
@inproceedings{cesabianchi2009alt-learning,
title = {{Learning Unknown Graphs}},
author = {Cesa-Bianchi, Nicolò and Gentile, Claudio and Vitale, Fabio},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2009},
pages = {110-125},
doi = {10.1007/978-3-642-04414-4_13},
url = {https://mlanthology.org/alt/2009/cesabianchi2009alt-learning/}
}