We refer to cuGraph and other CUDA implementations to implement common graph analysis algorithms based on the WebGPU capabilities behind g-plugin-gpgpu to achieve large-scale node edge data volume.

This is a significant improvement over the CPU serial version currently offered by G6.

Pre-requisites

Before using it, you need to confirm the operating environment and data as two preconditions.

WebGPU Operating Environment

WebGPU is currently (2022-3-21) supported in Chrome 94 official version and above, but since we are using the latest WGSL syntax, it is recommended to update your browser to the latest version.

For production use at this time, Origin Trial will need to be enabled to support WebGPU features (no longer required for Chrome 100+).

• Get Token
• Add the <meta> tag to the page with the Token obtained in the previous step, e.g. via the DOM API.

const tokenElement = document.createElement('meta');
tokenElement.httpEquiv = 'origin-trial';
tokenElement.content = 'AkIL...5fQ==';
document.head.appendChild(tokenElement);

Graph data format

We use G6's graph data format, which is also the first fixed of all the following algorithms parameters.

const data = {
    // 点集
    nodes: [
        {
            id: 'node1', // String，该节点存在则必须，节点的唯一标识
            x: 100, // Number，可选，节点位置的 x 值
            y: 200, // Number，可选，节点位置的 y 值
        },
        {
            id: 'node2', // String，该节点存在则必须，节点的唯一标识
            x: 300, // Number，可选，节点位置的 x 值
            y: 200, // Number，可选，节点位置的 y 值
        },
    ],
    // 边集
    edges: [
        {
            source: 'node1', // String，必须，起始点 id
            target: 'node2', // String，必须，目标点 id
        },
    ],
};

If the data format does not meet the above requirements, the algorithm will not execute properly.

Usage

We offer the following two ways to use it.

• Canvas without G. You only want to use it to execute the algorithm, no rendering is involved. This is also the easiest way to use it.
• There is already a Canvas for G, e.g. it is being used for rendering, and only the algorithm needs to be called at this point.

Method 1

A WebGPUGraph is created and a series of initialization work such as canvas creation and plugin registration is done internally. Once completed, the algorithm is called directly.

import { WebGPUGraph } from '@antv/webgpu-graph';
const graph = new WebGPUGraph();

(async () => {
    const result = await graph.pageRank(data);
})();

Method 2

If you are already using G's Canvas for rendering, you can reuse it and do the following.

• Register g-plugin-gpgpu
• Waiting for the canvas to initialize
• Get GPU Device
• The algorithm is called, and the first parameter of the algorithm is the Device obtained in the previous step

import { Canvas } from '@antv/g';
import { Renderer } from '@antv/g-webgl';
import { Plugin } from '@antv/g-plugin-gpgpu';
import { pageRank } from '@antv/webgpu-graph';

const webglRenderer = new Renderer();
webglRenderer.registerPlugin(new Plugin());

const canvas = new Canvas({
    container: 'my-canvas-id',
    width: 1,
    height: 1,
    renderer: webglRenderer,
});

(async () => {
    // Wait for the canvas initialization to complete
    await canvas.ready;

    // Get Device by Renderer
    const plugin = renderer.getPlugin('device-renderer');
    const device = plugin.getDevice();

    // Call the algorithm, pass in Device and graph data
    const result = await pageRank(device, data);
})();

All the following algorithms are called asynchronously.

Link Analysis

PageRank

The list of parameters is as follows.

The return value is an array of results containing the id and score attributes, in the form [{ id: 'A', score: 0.38 }, { id: 'B', score: 0.32 }...].

The array elements have been sorted by score from highest to lowest, so the first element represents the node with the highest importance.

Refer to the following CUDA version implementation.

• https://github.com/princeofpython/PageRank-with-CUDA/blob/main/parallel.cu
• https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph.dask.link_analysis.pagerank.pagerank.html

It is used in the following way, example：

const result = await graph.pageRank(data);
// [{id: 'B', score: 0.3902697265148163}, {}...]

There is a very significant improvement in larger point-side scenarios.

Traversal

SSSP

Single source shortest path, i.e., the shortest path from one node to all other nodes.

The list of parameters is as follows.

Refer to the following CUDA version implementations.

• https://www.lewuathe.com/illustration-of-distributed-bellman-ford-algorithm.html
• https://github.com/sengorajkumar/gpu_graph_algorithms
• https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph.traversal.sssp.sssp.html

APSP

Accelerating large graph algorithms on the GPU using CUDA

BFS

• Scalable GPU Graph Traversal
• https://github.com/rafalk342/bfs-cuda
• https://github.com/kaletap/bfs-cuda-gpu

DFS

https://github.com/divyanshu-talwar/Parallel-DFS

Nodes clustering

K-Means

• A CUDA Implementation of the K-Means Clustering Algorithm
• "Yinyang" K-means and K-nn using NVIDIA CUDA

Community Detection

Louvain

• Demystifying Louvain’s Algorithm and Its implementation in GPU
• https://docs.rapids.ai/api/cugraph/stable/api_docs/api/cugraph.louvain.html
• https://github.com/rapidsai/cugraph/tree/branch-22.08/cpp/src/community

K-Core

K-Core Decomposition with CUDA

Label Propagation

• Parallel Graph Component Labelling with GPUs and CUDA
• GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection

minimumSpanningTree

• https://github.com/jiachengpan/cudaMST
• https://github.com/Dibyadarshan/GPU-Based-Fast-Minimum-Spanning-Tree

Similarity

Cosine Similarity

https://github.com/adamantmc/CudaCosineSimilarity

Nodes Cosine Similarity

Others

DFS

https://github.com/divyanshu-talwar/Parallel-DFS

Cycle Detection

https://github.com/hamham240/cudaGraph/blob/main/src/algos/cudaCD.cu