# An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs

arXiv: https://arxiv.org/abs/2203.16123 · HTML: https://mlsanity.com/paper/2203.16123/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2022.

## Built on by (most cited first, 4 of 4)

- [Distributed Graph Neural Network Training: A Survey](https://mlsanity.com/paper/2211.00216/) (2022)
- [Multi-domain Recommendation with Embedding Disentangling and Domain Alignment](https://mlsanity.com/paper/2308.05508/) (2023)
- [NeutronStream: A Dynamic GNN Training Framework with Sliding Window for Graph Streams](https://mlsanity.com/paper/2312.02473/) (2023)
- [Distributed Graph Embedding with Information-Oriented Random Walks](https://mlsanity.com/paper/2303.15702/) (2023)

## Abstract (arXiv)

Random walk is widely used in many graph analysis tasks, especially the first-order random walk. However, as a simplification of real-world problems, the first-order random walk is poor at modeling higher-order structures in the data. Recently, second-order random walk-based applications (e.g., Node2vec, Second-order PageRank) have become attractive. Due to the complexity of the second-order random walk models and memory limitations, it is not scalable to run second-order random walk-based applications on a single machine. Existing disk-based graph systems are only friendly to the first-order random walk models and suffer from expensive disk I/Os when executing the second-order random walks. This paper introduces an I/O-efficient disk-based graph system for the scalable second-order random walk of large graphs, called GraSorw. First, to eliminate massive light vertex I/Os, we develop a bi-block execution engine that converts random I/Os into sequential I/Os by applying a new triangular bi-block scheduling strategy, the bucket-based walk management, and the skewed walk storage. Second, to improve the I/O utilization, we design a learning-based block loading model to leverage the advantages of the full-load and on-demand load methods. Finally, we conducted extensive experiments on six large real datasets as well as several synthetic datasets. The empirical results demonstrate that the end-to-end time cost of popular tasks in GraSorw is reduced by more than one order of magnitude compared to the existing disk-based graph systems.