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.
Categories: cs.DS