Motivated by a problem of targeted advertising in social networks, we introduce a new model of online learning on labeled graphs where the graph is initially unknown and the algorithm is free to choose which vertex to predict next. For this learning model, we define an appropriate measure of regularity of a graph labeling called the merging degree. In general, the merging degree of a graph is small when its vertices can be partitioned into a few well-separated clusters within which labels are roughly constant. For the special case of binary labeled graphs, the merging degree is a more refined measure than the cutsize. After observing that natural nonadaptive exploration/prediction strategies, like depth-first with majority vote, do not behave satisfactorily on graphs with small merging degree, we introduce an efficiently implementable adaptive strategy whose cumulative loss is controlled by the merging degree. A matching lower bound shows that in the case of binary labels our analysis cannot be improved.
Predicting the labels of an unknown graph via adaptive exploration / N. Cesa-Bianchi, C. Gentile, F. Vitale. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 412:19(2011), pp. 1791-1804.
|Titolo:||Predicting the labels of an unknown graph via adaptive exploration|
CESA BIANCHI, NICOLO' ANTONIO (Primo)
|Parole Chiave:||online learning ; graph prediction ; graph clustering|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2011|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.tcs.2010.12.056|
|Appare nelle tipologie:||01 - Articolo su periodico|