Scalable Algorithms for Random-Walk Probability Estimation

ABSTRACT

In the past decade, we have been experiencing a huge "Big Data" movement driven by the exponential blowup in data volumes. Algorithms that were once celebrated for their polynomial-time efficiency may no longer be adequate for solving today’s problems. Scalable algorithms, whose complexity is nearly linear or sublinear with respect to the problem size, are now in higher demand than ever before.

In this talk, I will introduce my research efforts aimed at designing scalable algorithms for computing random-walk probabilities on large graphs, a cornerstone problem and a critical algorithmic component in graph analysis. I will begin by providing an overview of sublinear-time algorithms and random-walk probability computations. Then, I will illustrate four different types of random-walk probability queries and summarize my contributions in achieving better complexity bounds for these four types of query problems. Next, I will describe several critical algorithmic techniques and demonstrate how to utilize these techniques to achieve my complexity results. Finally, I will discuss my future research plans, focusing on how these scalable algorithmic techniques can be adopted to advance data science research.

SPEAKER BIO

Hanzhi Wang recently obtained her PhD in Big Data Science and Engineering from Renmin University of China in May 2024, under the supervision of Professor Zhewei Wei. Her research interests lie in graph algorithms, with a particular focus on the design of provably good scalable algorithms for large graphs. She was a recipient of the 2021 Baidu Scholarship (awarded to 10 students worldwide) and the 2022 Microsoft Research PhD Fellowship (awarded to 12 students in the Asia-Pacific region). She has published in top venues in theoretical computer science (STOC), databases (SIGMOD, VLDB), and data mining (KDD). Previously, she received a B.E. in computer science and technology from Renmin University of China in 2019.