AURORA: Auditing PageRank on Large Graphs
AURORA: Auditing PageRank on Large Graphs
复制标题
DOI：
10.1109/bigdata.2018.8622563
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Jian Kang;Hanghang Tong;Yinglong Xia;Wei Fan
中科院分区：
文献类型：
--
作者：
Jian Kang;Hanghang Tong;Yinglong Xia;Wei Fan
大规模图上的排名在许多高影响力的应用领域中起着基础作用，从信息检索，推荐系统，运动队管理，生物学到神经科学等等。PageRank及其许多基于随机游走的变体已经成为最知名和最广泛使用的算法之一，这是由于其数学上的优雅和跨各种应用领域的上级性能。尽管它可能很重要，但最先进的技术缺乏一种直观的方式来解释PageRank（或其变体）的排名结果，例如，为什么它认为返回的top-k网页是整个图表中最重要的网页;为什么它在相对于rt的相关性方面给予演员约翰比演员史密斯更高的排名一部特别的电影？为了回答这些问题，本文提出了一个范式转换PageRank，从识别哪些节点是最重要的，以了解为什么排名算法给出了一个特定的排名结果。我们正式定义了PageRank审计问题，其中心思想是识别一组关键图形元素（例如，边、节点、子图）对排序结果具有最高影响。我们将其表述为一个优化问题，并提出了一系列有效的和可扩展的算法（Aurora）来解决这个问题。他们的梯度在排名结果。我们对现实世界的数据集进行了广泛的实证评估，这表明所提出的方法（Aurora）提供了直观的解释，具有线性可扩展性。
Ranking on large-scale graphs plays a fundamental role in many high-impact application domains, ranging from information retrieval, recommender systems, sports team management, biology to neuroscience and many more. PageRank, together with many of its random walk based variants, has become one of the most well-known and widely used algorithms, due to its mathematical elegance and the superior performance across a variety of application domains. Important as it might be, state-of-the-art lacks an intuitive way to explain the ranking results by PageRank (or its variants), e.g., why it thinks the returned top-k webpages are the most important ones in the entire graph; why it gives a higher rank to actor John than actor Smith in terms of their relevance w.r.t. a particular movie?In order to answer these questions, this paper proposes a paradigm shift for PageRank, from identifying which nodes are most important to understanding why the ranking algorithm gives a particular ranking result. We formally define the PageRank auditing problem, whose central idea is to identify a set of key graph elements (e.g., edges, nodes, subgraphs) with the highest influence on the ranking results. We formulate it as an opti-mization problem and propose a family of effective and scalable algorithms (Aurora) to solve it. Our algorithms measure the influence of graph elements and incrementally select influential elements w.r.t. their gradients over the ranking results. We perform extensive empirical evaluations on real-world datasets, which demonstrate that the proposed methods (Aurora) provide intuitive explanations with a linear scalability.