TY - JOUR
T1 - Graph Ranking Auditing
T2 - Problem Definition and Fast Solutions
AU - Wang, Meijia
AU - Kang, Jian
AU - Cao, Nan
AU - Xia, Yinglong
AU - Fan, Wei
AU - Tong, Hanghang
N1 - Funding Information:
The faculty and students were supported by NSF (1947135, 1715385, and 1939725).
Publisher Copyright:
© 1989-2012 IEEE.
PY - 2021/10/1
Y1 - 2021/10/1
N2 - Ranking on graphs is a centerpiece in many high-impact application domains, such as information retrieval, recommender systems, team management, neuroscience and many more. PageRank, along with many of its variants, is widely used across these application domains thanks to its mathematical elegance and the superior performance. Although PageRank and its variants are effective in ranking nodes on graphs, they often lack an efficient and effective way to audit the ranking results in terms of the input graph structure, e.g., which node or edge in the graph contributes most to the top-1 ranked node; which subgraph plays a crucial role in generating the overall ranking result? In this paper, we propose to audit graph ranking by finding the influential graph elements (e.g., edges, nodes, attributes, and subgraphs) regarding their impact on the ranking results. First, we formulate graph ranking auditing problem as quantifying the influence of graph elements on the ranking results. Second, we show that our formulation can be applied to a variety of graph structures. Third, we propose effective and efficient algorithms to find the top-kk influential edges/nodes/subgraph. Finally, we perform extensive empirical evaluations on real-world datasets to demonstrate that the proposed methods (Aurora) provide intuitive auditing results with linear scalability.
AB - Ranking on graphs is a centerpiece in many high-impact application domains, such as information retrieval, recommender systems, team management, neuroscience and many more. PageRank, along with many of its variants, is widely used across these application domains thanks to its mathematical elegance and the superior performance. Although PageRank and its variants are effective in ranking nodes on graphs, they often lack an efficient and effective way to audit the ranking results in terms of the input graph structure, e.g., which node or edge in the graph contributes most to the top-1 ranked node; which subgraph plays a crucial role in generating the overall ranking result? In this paper, we propose to audit graph ranking by finding the influential graph elements (e.g., edges, nodes, attributes, and subgraphs) regarding their impact on the ranking results. First, we formulate graph ranking auditing problem as quantifying the influence of graph elements on the ranking results. Second, we show that our formulation can be applied to a variety of graph structures. Third, we propose effective and efficient algorithms to find the top-kk influential edges/nodes/subgraph. Finally, we perform extensive empirical evaluations on real-world datasets to demonstrate that the proposed methods (Aurora) provide intuitive auditing results with linear scalability.
KW - explainability
KW - Graph mining
KW - pagerank
UR - http://www.scopus.com/inward/record.url?scp=85114962713&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85114962713&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2020.2969415
DO - 10.1109/TKDE.2020.2969415
M3 - Article
AN - SCOPUS:85114962713
SN - 1041-4347
VL - 33
SP - 3366
EP - 3380
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 10
ER -