Scalable algorithms for learning on graphs

author: Nicolò Cesa-Bianchi, University of Milan
published: July 20, 2010,   recorded: June 2010,   views: 3649

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Networked data are found in a variety of domains: Web, social networks, biological networks, and many others. In learning tasks, networked data are often represented as a weighted graph whose edge weights reflect the similarity between incident nodes. In this talk, we consider the problem of classifying the nodes of an arbitrary given graph in the game-theoretic mistake bound model. We characterize the optimal predictive performance in terms of the cutsize of the graph's random spanning tree, and describe a randomized prediction algorithm achieving the optimal performance while running in expected time sublinear in the graph size (on most graphs). These results are then extended to the active learning model, where training labels are obtained by querying nodes selected by the algorithm. We describe a fast query placement strategy that, in the special case of trees, achieves the optimal number of mistakes when classifying the non-queried nodes. Joint work with: Claudio Gentile, Fabio Vitale and Giovanni Zappella.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: