UPPR+: Scaling Uncertain Personalised PageRank Computation on Billion-Sized Graphs with Mutually Exclusive Edges

While Personalised PageRank (PPR) is widely used for ranking nodes in certain graphs, research on PPR for uncertain graphs remains limited. Real-world graphs often exhibit uncertainty in some edges with interdependent probabilities. The best-of-breed work by Kim et al.[13] proposed a fast approximate algorithm, UPPR, leveraging the Sherman-Morrison formula with singular value decomposition. However, UPPR lacks error guarantees, and struggles to scale on large graphs due to the high cost to precompute block matrix inverses over the certain part of the graph.