An efficient out-of-core graph processing system for second-order random walks

Random walks have become a widely used tool for graph analysis. Unlike traditional first-order random walks, second-order random walks can better capture high-order structures in data by considering recent walk history. However, existing solutions face two major issues. First, they fail to fully account for the dependencies among graph blocks, resulting in that walkers with high correlation cannot be updated in time and thus reducing the I/O utilization of these blocks. Second, most systems handle random walk updates on a per-walker basis, causing repeated loading and computation of the same graph data, which in turn lowers update efficiency. To cope with these issues, this paper proposes an out-of-core graph processing system DSWalker for second-order random walks. It significantly reduces the data access cost of the existing random walk system by prioritizing the loading of graph block combinations that can activate more walkers, and by exploiting the data access similarity among concurrent walkers, thereby effectively improving the walk update efficiency and overall system performance. Specifically, DSWalker designs a novel dynamic I/O block scheduling strategy, which enables the graph data to be loaded in an optimal I/O accesses and effectively reduces the redundant data loaded into the memory. Meanwhile, DSWalker regularizes the update order of the graph partitions for concurrent walkers, enabling them to share access to the same graph structures in the cache, so as to amortize the data access overhead.Compared with SOWalker, the most advanced dynamic graph processing system for monotone graph algorithms, DSWalker speeds up dynamic directed graph processing by an average of 2.2 times.