FeatGraph: a flexible and efficient backend for graph neural network systems

Yuwei Hu, Zihao Ye, Minjie Wang, Jiali Yu, Da Zheng, Mu Li, Zheng Zhang, Zhiru Zhang, Yida Wang

Graph Neural Networks (GNNs) have emerged as a powerful tool for learning from structured data, yet they present a unique challenge for systems performance. By operating at the intersection of sparse graph structures and dense multi-dimensional feature tensors, GNNs create a "best of both worlds" nightmare for traditional optimization strategies. FeatGraph addresses this by introducing a high-performance backend that co-optimizes graph traversal and feature-dimension computation, achieving significant speedups over existing frameworks.

The Performance Bottleneck in GNNs

Traditional systems for graph processing and deep learning are often ill-equipped for GNN workloads. Traditional graph systems, such as Ligra or Gunrock, are designed for "scalar" workloads like PageRank. While they excel at traversing edges, they treat the computation on each edge as a "black box," failing to exploit the inherent parallelism within the feature dimensions. Conversely, deep learning frameworks like PyTorch or TensorFlow rely on vendor-provided sparse libraries (e.g., Intel MKL, NVIDIA cuSPARSE). While highly optimized, these libraries are inflexible and only support a narrow subset of the kernels required for diverse GNN models, such as multi-head attention or complex MLP aggregations.

Research indicates that 60-95% of GNN execution time is spent on these sparse operations. There is a critical need for a system that makes vertex and edge computations "white-box" to the scheduler, allowing for the co-optimization of graph movement and feature processing.

The FeatGraph Architecture

FeatGraph introduces a two-granularity programming interface that separates the definition of the computation from its optimization. This decoupling allows the system to target different hardware backends efficiently.

The FeatGraph system stack, showing the decoupling of coarse-grained templates and fine-grained UDF optimizations.

As shown in the architecture above, the system is built on three main pillars:

  1. Coarse-Grained Sparse Templates: Users select from primary patterns like Generalized SpMM (for vertex-wise aggregation) or Generalized SDDMM (for edge-wise updates). These templates manage the high-level graph traversal logic.
  2. Fine-Grained User-Defined Functions (UDFs): Users define feature-wise logic (e.g., dot products) using a tensor expression language. By making these UDFs "white-box," FeatGraph can parallelize inside an edge computation.
  3. Decoupled Optimization: The system optimizes the graph level (using partitioning for cache locality) and the feature level (using a Feature Dimension Schedule) independently before fusing them into a single kernel via the Apache TVM compiler.

Co-optimizing Graph and Feature Dimensions

A key insight of FeatGraph is the "Locality Trade-off." Tiling the feature dimension can improve cache reuse for features, but it may force the system to traverse the graph multiple times. FeatGraph allows users to tune this balance to find the optimal performance point for specific hardware and datasets.

Illustration of the feature dimension scheduling and graph partitioning strategy to balance cache locality.

On GPUs, FeatGraph employs a Hybrid Partitioning strategy. High-degree nodes, which often act as "cache hogs," are handled differently than low-degree nodes. By reordering the graph and selectively loading high-degree vertex features into shared memory, the system significantly boosts throughput for power-law graphs.

Evaluation and Results

FeatGraph was integrated into the Deep Graph Library (DGL) and evaluated against industry standards across various datasets, including ogbn-proteins and reddit.

  • CPU Performance: FeatGraph achieved a 1.4×–4.0× speedup over Ligra for GCN aggregation and outperformed Intel MKL in nearly all test cases, particularly as feature lengths increased.
  • GPU Performance: The system showed massive gains over Gunrock (up to 206× for GCN) by avoiding the overhead of atomic operations. It also consistently outperformed NVIDIA cuSPARSE by 10-20%.
  • End-to-End Training: For complex models like Graph Attention Networks (GAT), FeatGraph provided a 32× speedup on CPUs and a 7× speedup on GPUs compared to standard DGL implementations.

Conclusion and Future Work

FeatGraph demonstrates that decoupling graph traversal from feature computation is essential for GNN performance. While the current implementation requires some manual tuning for partitioning and tiling factors, future work involves integrating intelligent auto-tuners like AutoTVM. Additionally, extending these co-optimization techniques to distributed, multi-GPU environments remains a promising avenue for scaling GNN training to even larger datasets.

Summary updated

BibTeX
@inproceedings{hu2020featgraph,
  author = {Yuwei Hu and Zihao Ye and Minjie Wang and Jiali Yu and Da Zheng and Mu Li and Zheng Zhang and Zhiru Zhang and Yida Wang},
  title = {{FeatGraph: a flexible and efficient backend for graph neural network systems}},
  booktitle = {SC},
  year = {2020},
  url = {https://openreview.net/forum?id=DEG835pmfUQ},
}
Figure