  Personalized PageRank (PPR) is a graph algorithm that evaluates the
importance of the surrounding nodes from a source node. Widely used in social
network related applications such as recommender systems, PPR requires
real-time responses (latency) for a better user experience. Existing works
either focus on algorithmic optimization for improving precision while
neglecting hardware implementations or focus on distributed global graph
processing on large-scale systems for improving throughput rather than response
time. Optimizing low-latency local PPR algorithm with a tight memory budget on
edge devices remains unexplored. In this work, we propose a memory-efficient,
low-latency PPR solution, namely MeLoPPR, with largely reduced memory
requirement and a flexible trade-off between latency and precision. MeLoPPR is
composed of stage decomposition and linear decomposition and exploits the node
score sparsity: Through stage and linear decomposition, MeLoPPR breaks the
computation on a large graph into a set of smaller sub-graphs, that
significantly saves the computation memory; Through sparsity exploitation,
MeLoPPR selectively chooses the sub-graphs that contribute the most to the
precision to reduce the required computation. In addition, through
software/hardware co-design, we propose a hardware implementation on a hybrid
CPU and FPGA accelerating platform, that further speeds up the sub-graph
computation. We evaluate the proposed MeLoPPR on memory-constrained devices
including a personal laptop and Xilinx Kintex-7 KC705 FPGA using six real-world
graphs. First, MeLoPPR demonstrates significant memory saving by 1.5x to 13.4x
on CPU and 73x to 8699x on FPGA. Second, MeLoPPR allows flexible trade-offs
between precision and execution time: when the precision is 80%, the speedup on
CPU is up to 15x and up to 707x on FPGA; when the precision is around 90%, the
speedup is up to 70x on FPGA.
