2011 SemiSupervisedRankingonVeryLarg

• (Gao et al., 2011) ⇒ Bin Gao, Tie-Yan Liu, Wei Wei, Taifeng Wang, and Hang Li. (2011). “Semi-supervised Ranking on Very Large Graphs with Rich Metadata.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020430

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Semi-supervised+Ranking+on+Very+Large+Graphs+with+Rich+Metadata
• http://dl.acm.org/citation.cfm?id=2020408.2020430&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; experimentation; hypertext/hypermedia; information search and retrieval; mapreduce; page importance; pagerank; theory

Abstract

Graph ranking plays an important role in many applications, such as page ranking on web graphs and entity ranking on social networks. In applications, besides graph structure, rich information on nodes and edges and explicit or implicit human supervision are often available. In contrast, conventional algorithms (e.g., PageRank and HITS) compute ranking scores by only resorting to graph structure information. A natural question arises here, that is, how to effectively and efficiently leverage all the information to more accurately calculate graph ranking scores than the conventional algorithms, assuming that the graph is also very large. Previous work only partially tackled the problem, and the proposed solutions are also not satisfying. This paper addresses the problem and proposes a general framework as well as an efficient algorithm for graph ranking. Specifically, we define a semi-supervised learning framework for ranking of nodes on a very large graph and derive within our proposed framework an efficient algorithm called Semi-Supervised PageRank. In the algorithm, the objective function is defined based upon a Markov random walk on the graph. The transition probability and the reset probability of the Markov model are defined as parametric models based on features on nodes and edges. By minimizing the objective function, subject to a number of constraints derived from supervision information, we simultaneously learn the optimal parameters of the model and the optimal ranking scores of the nodes. Finally, we show that it is possible to make the algorithm efficient to handle a billion-node graph by taking advantage of the sparsity of the graph and implement it in the MapReduce logic. Experiments on real data from a commercial search engine show that the proposed algorithm can outperform previous algorithms on several tasks.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 SemiSupervisedRankingonVeryLarg	Hang Li Wei Wei Bin Gao Tie-Yan Liu Taifeng Wang			Semi-supervised Ranking on Very Large Graphs with Rich Metadata				10.1145/2020408.2020430		2011