Toward Enabling efficient uncertain graph processing on multi-accelerator systems.

• BPGraph: Path-Sampling Centric Uncertain Graph Processing

BPGraph is released under the MIT license.

If you use BPGraph in your research, please cite our paper:

• ICS'22, BPGraph

BPGraph is based on a novel runtime path sampling method, which is able to identify and eliminate unnecessary edge sampling via incremental path identification and filtering, resulting in significant reduction in computation and data movement. BPGraph is a general uncertain graph processing framework for multi-GPU systems, and provides general support for users to design and optimize a wide-range of uncertain graph algorithms and applications without concerning about the underlying complexity. For more details, see BPGraph's Overview.

BPGraph New Features:

• Path Sampling Methodology
• Path-Sampling Centric Programming APIs
• High-Performance Supporting on GPUs

BPGraph supports the following applications in the implementation, and other algorithms are under developing.

• Source-Target Path Query
• K-Nearest Neighbors
• Any-Pair Shortest Path Search

Before building BPGraph, we recommend our software environment configuration of CMake 3.12, GCC 5.4 and CUDA 11 are required. The later version of the software dependencies are not tested in this time. Meanwhile, the third party code contained in our repository includes the following external dependencies: NCCL, BOOST, and other optional repository. For complete build guide, see Building BPGraph.

git clone --recursive https://github.com/bpgraph/bpgraph.git
cd bpgraph
mkdir build && cd build
cmake .. && make -j$(nproc)
bin/bpgraph --edgelist ../toy.mtx (--st ../st_toy.txt --app ...)

Fast start to run a simple example of source-to-target query in BPGraph system.

bin/bpgraph --edgelist ../toy.mtx --st ../st_toy.txt

The dataset for this artifact contains all graphs listed the paper, converted to the edgelist matrix format (.mtx or .txt files). Also, we separately give the scripts of small and large datasets for automatically downloaded from open source repositories. Each graph is located in a separate subdirectory, with three additional files:

• {graphfile}_mtx.txt Raw uncertain graph file.
• {graphfile}.metadata Description file contains the basic information (#vertex, #edge, #diameter) for uncertain graphs.
• {st-graphfile}.txt Source-target query datasets containing the generated source-target query pairs.
• Monte-Carlo.txt Result datasets containing the final execution time, memory consumption and the reliability data.

Execute uncetain graph query with the following command. --edgelist sets the input graph file, -st sets the source-to-target node pair list file, -app sets the application and -d sets the number of GPU devices.

bin/bpgraph --edgelist ../toy.mtx --st ../st_toy.txt -d 2 -app st

Execute KNN with the following command.

bin/bpgraph --edgelist ../friendster.mtx -d 2 -app knn -sid 0

Execute ASAP with the follwoing command.

bin/bpgraph --edgelist ../twitter.mtx --st ../st_toy.txt -d 2 -app asap

The source files are under scripts folder. The parameters have been configured in the source files. You can rewrite the default setting (e.g., the number of devices, the sampling method and the distance metrics) in the source files or through parameters with the instructions in the files. Here, we demonstrate the input of graph data.

You can download the graphs used in our paper by following the instructions.

The source files are under scripts folder.