Please use this identifier to cite or link to this item: https://doi.org/10.1109/TKDE.2016.2611584
Title: BiRank: Towards Ranking on Bipartite Graphs
Authors: He, Xiangnan
Gao, Ming
Kan, Min-Yen 
Wang, Dingxian
Keywords: Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science, Information Systems
Engineering, Electrical & Electronic
Computer Science
Engineering
Bipartite graph ranking
graph regularization
n-partite graphs
popularity prediction
personalized recommendation
Issue Date: 1-Jan-2017
Publisher: IEEE COMPUTER SOC
Citation: He, Xiangnan, Gao, Ming, Kan, Min-Yen, Wang, Dingxian (2017-01-01). BiRank: Towards Ranking on Bipartite Graphs. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 29 (1) : 57-71. ScholarBank@NUS Repository. https://doi.org/10.1109/TKDE.2016.2611584
Abstract: The bipartite graph is a ubiquitous data structure that can model the relationship between two entity types: for instance, users and items, queries and webpages. In this paper, we study the problem of ranking vertices of a bipartite graph, based on the graph's link structure as well as prior information about vertices (which we term a query vector). We present a new solution, BiRank, which iteratively assigns scores to vertices and finally converges to a unique stationary ranking. In contrast to the traditional random walk-based methods, BiRank iterates towards optimizing a regularization function, which smooths the graph under the guidance of the query vector. Importantly, we establish how BiRank relates to the Bayesian methodology, enabling the future extension in a probabilistic way. To show the rationale and extendability of the ranking methodology, we further extend it to rank for the more generic n-partite graphs. BiRank's generic modeling of both the graph structure and vertex features enables it to model various ranking hypotheses flexibly. To illustrate its functionality, we apply the BiRank and TriRank (ranking for tripartite graphs) algorithms to two real-world applications: a general ranking scenario that predicts the future popularity of items, and a personalized ranking scenario that recommends items of interest to users. Extensive experiments on both synthetic and real-world datasets demonstrate BiRank's soundness (fast convergence), efficiency (linear in the number of graph edges), and effectiveness (achieving state-of-the-art in the two real-world tasks).
Source Title: IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
URI: https://scholarbank.nus.edu.sg/handle/10635/228934
ISSN: 10414347
15582191
DOI: 10.1109/TKDE.2016.2611584
Appears in Collections:Elements
Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
1708.04396v1.pdf954.52 kBAdobe PDF

OPEN

PublishedView/Download

SCOPUSTM   
Citations

102
checked on Oct 1, 2022

Page view(s)

28
checked on Oct 6, 2022

Download(s)

1
checked on Oct 6, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.