Summary of Iterative Methods Via Locally Evolving Set Process, by Baojian Zhou et al.
Iterative Methods via Locally Evolving Set Process
by Baojian Zhou, Yifan Sun, Reza Babanezhad Harikandeh, Xingzhi Guo, Deqing Yang, Yanghua Xiao
First submitted to arxiv on: 19 Oct 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: None
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary The paper explores whether standard iterative solvers can be effectively localized for approximating personalized PageRank (PPR) vectors. The authors propose a novel framework called locally evolving set process, which characterizes the algorithm locality and demonstrates that many standard solvers can be effectively localized. This leads to new runtime bounds for existing algorithms, including Approximate Personalized PageRank (APPR), and shows up to a hundredfold speedup over standard solvers on real-world graphs. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper asks if faster local algorithms can be developed for approximating PPR vectors. It explores this question by noticing that APPR is a local variant of Gauss-Seidel, and proposes a new framework called the locally evolving set process. This framework characterizes algorithm locality and shows that many standard solvers can be effectively localized, leading to new runtime bounds and faster performance. |
