AntV Graph Algorithm based on WebGPU

webgpu-graph is a GPU accelerated graph analytics library, with functionality like WebGPU which provides modern features such as compute shader(in WGSL). Compared with CPU version, we almost gain ~100x speed up with big datasets.

It's inspired by cuGraph and other implementations based on CUDA.

Docs:

- Link Analysis
- PageRank
- Traversal
- SSSP

Prerequisite

How to use WebGPU

For our examples, we use origin trial. The origin trial is expected to end in Chrome 101 (May 18, 2022).

Since we are using latest syntax of WGSL, you'd better update your Chrome to the latest version.

Usage

``js
import { pageRank, WebGPUGraph } from '@antv/webgpu-graph';

// initialize WebGPU context
const graph = new WebGPUGraph();

// call async method
const result = await graph.pageRank(graph_data, eps, alpha, max_iter);
`

Building

- Install dependencies: yarn install
- For production, compile the project: yarn build`

Benchmark

| name | vertices and edges | CPU time elapsed | GPU time elapsed | Speed up |
| -------- | ------------------------ | ---------------- | ---------------- | -------- |
| SSSP | 1k vertices & 5k edges | 27687.10 ms | 261.60 ms | ~100x |
| PageRank | 1k vertices & 500k edges | 13641.50 ms | 130.20 ms | ~100x |