Name
Abstract | ||
|---|---|---|
Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node s and a target node t, the PPR value π(s,t) represents the probability that a random walk from s terminates at t, and thus indicates the bidirectional importance between s and t. The majority of the existing work focuses on the single-source queries, which asks for the PPR value of a given source node s and every node t ∈ V. However, the single-source query only reflects the importance of each node t with respect to s. In this paper, we consider the single-target PPR query, which measures the opposite direction of importance for PPR. Given a target node t, the single-target PPR query asks for the PPR value of every node $s\in V$ to a given target node t. We propose RBS, a novel algorithm that answers approximate single-target queries with optimal computational complexity. We show that RBS improves three concrete applications: heavy hitters PPR query, single-source SimRank computation, and scalable graph neural networks. We conduct experiments to demonstrate that RBS outperforms the state-of-the-art algorithms in terms of both efficiency and precision on real-world benchmark datasets.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3394486.3403108 | KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Virtual Event
CA
USA
July, 2020 |
DocType | ISBN | Citations |
Conference | 978-1-4503-7998-4 | 3 |
PageRank | References | Authors |
0.39 | 48 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wang Hanzhi | 1 | 4 | 2.10 |
| Zhewei Wei | 2 | 215 | 20.07 |
| Junhao Gan | 3 | 121 | 6.63 |
| Sibo Wang | 4 | 217 | 18.27 |
| Zengfeng Huang | 5 | 136 | 13.65 |