Node Classification [A]  [A] Submitted as a final project in the course Machine Learning: Foundations, Fall 2012/13.

Ofir Geri, Or Ozery

School of Computer Science, Tel Aviv University, Israel.


In this paper we review the Node Classification problem, in which the algorithm has to determine the labeling of samples (represented as nodes) by looking at the labels of their neighbors. This problem has many applications in social network studies and in recommendation systems. We review some of the basic algorithms for this problem in both offline and online scenarios. We also present a new randomized online algorithm and compare it to the other presented online algorithm.

1 Paper


[1] S. Bhagat, G. Cormode, S. Muthukrishnan. Node Classification in Social Networks. In Social Network Data Analytics (Springer) Ed. Charu Aggarwal, 2011.

[2] A. Blum, S. Chawla. Learning from Labeled and Unlabeled Data using Graph Mincuts. ICML 01’.

[3] M. Brautbar. Online Learning a Binary Labeling of a Graph. MLG 09’.

[4] O. Goldschmidt, D.S. Hochbaum. Polynomial Algorithm for the k-Cut Problem. FOCS 88’.