A Survey of Graph Pre-processing Methods: From Algorithmic to Hardware Perspectives

Zhengyang Lv, Mingyu Yan, Xin Liu, Mengyao Dong, Xiaochun Ye, Dongrui Fan, Ninghui SunarXiv 2023 · DOI · arXiv

Abstract

Graph processing is foundational to modern applications ranging from social network analysis to bioinformatics. However, the "formal" execution of graph algorithms is often preceded by a significant, yet frequently ignored, Graph Pre-processing (GPP) stage. This stage, which includes partitioning, sampling, and reordering, can consume orders of magnitude more time than the actual computation. This paper provides a comprehensive double-level taxonomy of GPP methods, analyzing them from both algorithmic and hardware perspectives to bridge the gap between theoretical optimization and practical acceleration.

Introduction: The Hidden Tax of Graph Processing

Modern graph-related applications deal with massive, irregular datasets that follow power-law distributions. To make these graphs "digestible" for hardware architectures like CPUs, GPUs, or custom accelerators, Graph Pre-processing (GPP) is essential. GPP tasks, such as partitioning a graph across a cluster or sampling neighborhoods for Graph Neural Networks (GNNs), have become a critical bottleneck. For instance, on the Fugaku supercomputer, pre-processing for a Breadth-First Search (BFS) can take 390 seconds, while the actual search takes a mere 0.25 seconds. This "GPP tax" necessitates a systematic study of pre-processing methods across different hardware and algorithmic paradigms.

The Two-Stage Processing Pipeline

The processing of graph data is generally divided into two distinct steps: Graph Pre-processing (GPP) and Graph Formal Processing (GFP). While GFP is the stage where the actual algorithm (e.g., PageRank, GCN training) runs, GPP prepares the raw data for efficient execution.

The two-stage graph processing pipeline: Graph Pre-processing (GPP) followed by Graph Formal Processing (GFP).

A Double-Level Taxonomy of GPP Methods

The authors propose a taxonomy to categorize GPP methods through two primary lenses: the algorithmic "how" and the hardware "why."

1. Algorithmic Perspective

  • Graph Representation Optimization: This involves modifying the graph's topology to improve processing efficiency. Key techniques include Partitioning (splitting graphs for parallel processing), Sampling (selecting representative subsets), Sparsification (removing non-essential edges), and Reconstruction (merging redundant nodes).
  • Data Representation Optimization: This focuses on how graph data is stored in memory without altering its topology. Techniques include Quantization (reducing bit-precision), Reordering (sorting node IDs to improve cache locality), and Reorganization (sharding data into intervals or chunks).
Common graph storage formats including Coordinate List (COO), Compressed Sparse Row (CSR), and Compressed Sparse Column (CSC) for both edge and vertex values.

2. Hardware Perspective

GPP methods are designed to address specific hardware constraints:

  • Efficient Computing: Reducing redundant calculations and ensuring load balance across processing units.
  • Efficient Storage: Minimizing memory footprint and reducing data movement between storage and the processor.
  • Efficient Communication: Lowering the frequency and latency of inter-processor communication.

Key Insights and Performance Impact

The survey highlights several critical trade-offs in GPP:

  • The GPP Dominance Paradox: In many systems, the setup phase (GPP) is the dominant overhead. If a graph is not reused frequently, the time spent in GPP may never be amortized by faster execution.
  • Lossy vs. Lossless Trade-offs: Methods like reordering are "free lunches" that improve performance via data layout optimization without affecting accuracy. In contrast, sampling and quantization are "lossy" techniques that trade a degree of accuracy for significant gains in speed and memory efficiency.
  • The GNN Challenge: Graph Neural Networks combine irregular graph structures with regular neural network computations, requiring GPP methods that can handle both indirect memory access and high-intensity arithmetic.

Results and Future Directions

Empirical evidence from the literature shows that GPP can have a transformative impact. For example, quantization can reduce memory requirements by up to 31.9x, while reordering can drastically improve cache utility. However, challenges remain:

  1. High Overhead: There is a need for hardware-accelerated GPP to reduce the pre-processing bottleneck.
  2. Dynamic Graphs: Current GPP methods largely assume static graphs; real-time applications require "online" GPP.
  3. Heterogeneous Graphs: Specialized GPP is needed for graphs with multiple types of nodes and relationships.
  4. Pipeline Integration: Future systems should aim to overlap GPP and GFP stages to hide latency.

Summary updated

Abstract

Graph-related applications have experienced significant growth in academia and industry, driven by the powerful representation capabilities of graph. However, efficiently executing these applications faces various challenges, such as load imbalance, random memory access, etc. To address these challenges, researchers have proposed various acceleration systems, including software frameworks and hardware accelerators, all of which incorporate graph pre-processing (GPP). GPP serves as a preparatory step before the formal execution of applications, involving techniques such as sampling, reorder, etc. However, GPP execution often remains overlooked, as the primary focus is directed towards enhancing graph applications themselves. This oversight is concerning, especially considering the explosive growth of real-world graph data, where GPP becomes essential and even dominates system running overhead. Furthermore, GPP methods exhibit significant variations across devices and applications due to high customization. Unfortunately, no comprehensive work systematically summarizes GPP. To address this gap and foster a better understanding of GPP, we present a comprehensive survey dedicated to this area. We propose a double-level taxonomy of GPP, considering both algorithmic and hardware perspectives. Through listing relavent works, we illustrate our taxonomy and conduct a thorough analysis and summary of diverse GPP techniques. Lastly, we discuss challenges in GPP and potential future directions.
BibTeX
@misc{lv2023survey,
  author = {Zhengyang Lv and Mingyu Yan and Xin Liu and Mengyao Dong and Xiaochun Ye and Dongrui Fan and Ninghui Sun},
  title = {{A Survey of Graph Pre-processing Methods: From Algorithmic to Hardware Perspectives}},
  year = {2023},
  eprint = {2309.07581},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2309.07581},
}
Figure