EFFICIENT RANKING ON ENTITY GRAPHS WITH PERSONALIZED RELATIONSHIPS

Authority flow techniques like Page Rank and Object Rank 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 pre computation and runtime algorithms. In particular, we apply our method to Object Rank, 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) Schema Approx is formulated as a distance minimization problem at the schema level; (b) Data Approx is a distance minimization problem at the data graph level. Schema Approx 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, Data Approx has a provable error bound. Both Schema Approx and Data Approx are expensive so we develop efficient heuristic implementations, Scale Rank and Pick One respectively. Extensive experiments on the DBLP data graph show that Scale Rank provides a fast and accurate personalized authority flow ranking.