HedgeRank: Heterogeneity-Aware, Energy-Efficient Partitioning of Personalized PageRank at the Edge

Personalized PageRank (PPR) is a widely used graph processing algorithm used to calculate the importance of source nodes in a graph. Generally, PPR is executed by using a high-performance microprocessor of a server, but it needs to be executed on edge devices to guarantee data privacy and network latency. However, since PPR has a variety of computation/memory characteristics that vary depending on the graph datasets, it causes performance/energy inefficiency when it is executed on edge devices with limited hardware resources. In this paper, we propose HedgeRank, a heterogeneity-aware, energy-efficient, partitioning technique of personalized PageRank at the edge. HedgeRank partitions the PPR subprocesses and allocates them to appropriate edge devices by considering their computation capability and energy efficiency. When combining low-power and high-performance edge devices, HedgeRank improves the execution time and energy consumption of PPR execution by up to 26.7% and 15.2% compared to the state-of-the-art PPR technique.