Ranking and Semi-supervised Classification on Large Scale Graphs Using Map-Reduce Export

@inproceedings{Rao2009text-mapred, abstract = {Label Propagation, a standard algorithm for semi-supervised classification, suffers from scalability issues involving memory and computation when used with largescale graphs from real-world datasets. In this paper we approach Label Propagation as solution to a system of linear equations which can be implemented as a scalable parallel algorithm using the map-reduce framework. In addition to semi-supervised classification, this approach to Label Propagation allows us to adapt the algorithm to make it usable for ranking on graphs and derive the theoretical connection between Label Propagation and PageRank. We provide empirical evidence to that effect using two natural language tasks – lexical relatedness and polarity induction. The version of the Label Propagation algorithm presented here scales linearly in the size of the data with a constant main memory requirement, in contrast to the quadratic cost of both in traditional approaches.}, author = {Rao, Delip and Yarowsky, David}, booktitle = {Workshop on Graph-based Methods for Natural Language Processing}, citeulike-article-id = {5032959}, keywords = {classification, graph, map, ranking, reduce, semi-supervised, text}, posted-at = {2009-07-01 14:59:09}, priority = {2}, title = {Ranking and Semi-supervised Classification on Large Scale Graphs Using Map-Reduce}, year = {2009} }

TY - CONF ID - Rao2009text-mapred L3 - citeulike-article-id:5032959 N2 - Label Propagation, a standard algorithm for semi-supervised classification, suffers from scalability issues involving memory and computation when used with largescale graphs from real-world datasets. In this paper we approach Label Propagation as solution to a system of linear equations which can be implemented as a scalable parallel algorithm using the map-reduce framework. In addition to semi-supervised classification, this approach to Label Propagation allows us to adapt the algorithm to make it usable for ranking on graphs and derive the theoretical connection between Label Propagation and PageRank. We provide empirical evidence to that effect using two natural language tasks – lexical relatedness and polarity induction. The version of the Label Propagation algorithm presented here scales linearly in the size of the data with a constant main memory requirement, in contrast to the quadratic cost of both in traditional approaches. TI - Ranking and Semi-supervised Classification on Large Scale Graphs Using Map-Reduce T2 - Workshop on Graph-based Methods for Natural Language Processing KW - classification KW - graph KW - map KW - ranking KW - reduce KW - semi-supervised KW - text AU - Rao, Delip AU - Yarowsky, David PY - 2009/// ER -