Dynamic PageRank: Additive Error and Batch Recomputation
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore the challenges and solutions in maintaining PageRank distributions for dynamic graphs in this 51-minute lecture by Jakub Lacki from Google Research. Delve into the complexities of efficiently updating PageRank values as edges are inserted or deleted from a graph. Discover why achieving constant factor multiplicative approximations of PageRank in dynamic settings is provably hard, resolving a long-standing open question. Learn about a simple yet effective batch recomputation algorithm that maintains good approximations under the L1 error metric. Gain insights from empirical evaluations showing this approach can be up to two orders of magnitude faster than existing dynamic baselines. Understand the trade-offs between relative error goals and practical performance in dynamic graph algorithms.
Syllabus
Dynamic PageRank: Additive Error and Batch Recomputation
Taught by
Simons Institute
Related Courses
Data Visualization GUIs with Dash and PythonYouTube How to Get Started With Graph ML - Blog Walkthrough
Aleksa Gordić - The AI Epiphany via YouTube Temporal Graph Networks - GNN Paper Explained
Aleksa Gordić - The AI Epiphany via YouTube Parallel Batch-Dynamic Graph Representations
Simons Institute via YouTube Dynamic Algorithms for Center on Graphs
Simons Institute via YouTube