.png){kind=icon}
.png){kind=icon}
Return
GoGraph: Accelerating Graph Processing Through Incremental Reordering
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2025.3623928.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A great number of graph analysis algorithms involve iterative computations, which dominate the runtime. Accelerating iterative graph computations has become the key to improving the performance of graph algorithms. While numerous studies have focused on reducing the runtime of each iteration to improve efficiency, the optimization of the number of iterations is often overlooked. In this work, we first establish a correlation between vertex processing order and the number of iterations, providing an opportunity to reduce the number of iterations. We propose a metric function to evaluate the effectiveness of vertex processing order in accelerating iterative computations. Leveraging this metric, we propose a novel graph reordering method, GoGraph, which constructs an efficient vertex processing order. Additionally, for evolving graphs, we further propose a metric function designed to evaluate the effectiveness of vertex processing orders in response to graph changes and provide three optional methods for dynamically adjusting the vertex processing order. Our experimental results illustrate that GoGraph surpasses current state-of-the-art reordering algorithms, improving runtime by an average of 1.83× (up to 3.34×). Compared to traditional synchronous computation methods, our approach enhances the speed of iterative computations by up to 4.46×. In dynamic scenarios, incremental GoGraph can reduce end-to-end time by 43% on average (up to 48%).
Keywords:
Graph reorder
iterative computation
asynchronous model
Journal
IF:
10.4
Papers:
6.7K
Citations:
3.2W