AURORA: Auditing PageRank on Large Graphs
Preprint
Abstract
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 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 optimization 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.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Supersparse linear integer models for optimized medical scoring systemsMachine Learning, 2015
- Googling the Brain: Discovering Hierarchical and Asymmetric Network Structures, with Applications in NeuroscienceInternet Mathematics, 2011
- Who Is the Best Player Ever? A Complex Network Analysis of the History of Professional TennisPLOS ONE, 2011
- TwitterRank2010
- Manifold-Ranking-Based Keyword Propagation for Image RetrievalEURASIP Journal on Advances in Signal Processing, 2006
- Influential Nodes in a Diffusion Model for Social Networks2005
- The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associationsBehavioral Ecology and Sociobiology, 2003
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999