Date: 24 Oct 2013 From: jyrki@diku.dk Subject: 31/10–5/11: Fabio will be at our department Lunch talk: Machine learning on trees and graphs Speaker: Fabio Vitale, University of Lille 3 Time: Friday, 1 November 2013 at 12.30–13.00 Place: Room 3-1-25 (Universitetsparken 1) Abstract: Networked data are typically represented as a graph whose edges provide information about the relationships between different vertices. The edges often encode a form of semantic similarity between pairs of linked data items. Predictive analysis on networked data, such as the Web, online social networks, biological networks, is a vast and growing research area, whose applications include: spam detection, product recommendation, gene function prediction, link prediction, and link classification. When inference algorithms are applied to massive networks, scalability becomes a central issue. In this context, running times linear or even sublinear in the network size are sometimes the only viable option.Pursuing the goal of designing methods which may impact on practical and relevant applications, we addressed the problem of classifying networked data with highly scalable algorithms. In this talk, we survey recent results [N. Cesa-Bianchi, C. Gentile, F. Vitale, and G. Zappella. Random spanning trees and the prediction of weighted graphs, Journal of Machine Learning Research, 14:1251-1284, 2013.] on node classification problems, describing principled algorithmic solutions having very appealing computational performances. For each of the algorithms presented, we can provide a rigorous theoretical analysis, together with an interpretation of the obtained performance bounds, and design adversarial strategies achieving matching lower bounds. Astonishingly, these methods are also easy to implement. We then present an experimental validation on real-world datasets, and close with possible directions for future research activities, showing that our approach could easily be adapted to more complex prediction problems on networked data. (joint work with N. Cesa-Bianchi, C. Gentile, and G. Zappella) Fabio's home page: http://researchers.lille.inria.fr/vitale/ PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/