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/