Home

Paper abstract

Semi-supervised Classification from Discriminative Random Walks

Jerome Callut - Universite catholique de Louvain, Belgium
Kevin Francoisse - Universite catholique de Louvain, Belgium
Marco Saerens - Universite catholique de Louvain, Belgium
Pierre Dupont - Universite catholique de Louvain, Belgium

Session: Semi Supervised Learning
Springer Link: http://dx.doi.org/10.1007/978-3-540-87479-9_29

This paper describes a novel technique, called D-walks, to tackle semi-supervised classi?cation problems in large graphs. We introduce here a betweenness measure based on passage times during random walks of bounded lengths. Such walks are further constrained to start and end in nodes within the same class, de?ning a distinct betweenness for each class. Unlabeled nodes are classi?ed according to the class showing the highest betweenness. Forward and backward recurrences are derived to efficiently compute the passage times. D-walks can deal with directed or undirected graphs with a linear time complexity with respect to the number of edges, the maximum walk length considered and the number of classes. Experiments on various real-life databases show that D-walks outperforms NetKit, the approach of Zhou et al. and the regularized laplacian kernel. The bene?t of D-walks is particularly noticeable when few labeled nodes are available. The computation time of D-walks is also substantially lower in all cases.