Accelerating Personalized PageRank Vector Computation

• Published in: arXiv.org 2023-06
• Main Authors: Chen, Zhen, Guo, Xingzhi, Zhou, Baojian, Yang, Deqing, Skiena, Steven
• Format: Article
• Language: English
• Subjects: Acceleration; Algorithms; Customization; Graph neural networks; Graphs; Heuristic methods; Iterative methods; Learning
• ISSN: 2331-8422

Personalized PageRank Vectors are widely used as fundamental graph-learning tools for detecting anomalous spammers, learning graph embeddings, and training graph neural networks. The well-known local FwdPush algorithm approximates PPVs and has a sublinear rate of \(O\big(\frac{1}{\alpha\epsilon}\big)\). A recent study found that when high precision is required, FwdPush is similar to the power iteration method, and its run time is pessimistically bounded by \(O\big(\frac{m}{\alpha} \log\frac{1}{\epsilon}\big)\). This paper looks closely at calculating PPVs for both directed and undirected graphs. By leveraging the linear invariant property, we show that FwdPush is a variant of Gauss-Seidel and propose a Successive Over-Relaxation based method, FwdPushSOR to speed it up by slightly modifying FwdPush. Additionally, we prove FwdPush has local linear convergence rate \(O\big(\tfrac{\text{vol}(S)}{\alpha} \log\tfrac{1}{\epsilon}\big)\) enjoying advantages of two existing bounds. We also design a new local heuristic push method that reduces the number of operations by 10-50 percent compared to FwdPush. For undirected graphs, we propose two momentum-based acceleration methods that can be expressed as one-line updates and speed up non-acceleration methods by\(\mathcal{O}\big(\tfrac{1}{\sqrt{\alpha}}\big)\). Our experiments on six real-world graph datasets confirm the efficiency of FwdPushSOR and the acceleration methods for directed and undirected graphs, respectively.