Efficient Ranking on Entity Graphs with Personalized Relationships

作     者：Hristidis, Vagelis Wu, Yao Raschid, Louiqa 

作者机构：Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA Microsoft Corp Redmond WA 98052 USA Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA 

出 版 物：《IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING》 (IEEE Trans Knowl Data Eng)

年 卷 期：2014年第26卷第4期

页      面：850-863页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：US National Science Foundation (NSF) [IIS-0960963, IIS-0811922, IIS-0952347, HRD-0833093, CNS-1126619] Google Research Award 

主　　题：Object search personalization PageRank approximation algorithms 

摘      要：Authority flow techniques like PageRank and ObjectRank can provide personalized ranking of typed entity-relationship graphs. There are two main ways to personalize authority flow ranking: Node-based personalization, where authority originates from a set of user-specific nodes;edge-based personalization, where the importance of different edge types is user-specific. We propose the first approach to achieve efficient edge-based personalization using a combination of precomputation and runtime algorithms. In particular, we apply our method to ObjectRank, where a personalized weight assignment vector (WAV) assigns different weights to each edge type or relationship type. Our approach includes a repository of rankings for various WAVs. We consider the following two classes of approximation: (a) SchemaApprox is formulated as a distance minimization problem at the schema level;(b) DataApprox is a distance minimization problem at the data graph level. SchemaApprox is not robust since it does not distinguish between important and trivial edge types based on the edge distribution in the data graph. In contrast, DataApprox has a provable error bound. Both SchemaApprox and DataApprox are expensive so we develop efficient heuristic implementations, ScaleRank and PickOne respectively. Extensive experiments on the DBLP data graph show that ScaleRank provides a fast and accurate personalized authority flow ranking.