Design of high-performance parallel Graph interface supporting efficient Dynamic batch updates.

Research in graph-structured data has grown rapidly due to graphs' ability to represent complex real-world information and capture intricate relationships, particularly as many real-world graphs evolve dynamically through edge/vertex insertions and deletions. This has spurred interest in programming frameworks for managing, maintaining, and processing such dynamic graphs. In our report, we evaluate the performance of PetGraph (Rust), Stanford Network Analysis Platform (SNAP), SuiteSparse:GraphBLAS, cuGraph, Aspen, and our custom implementation in tasks including loading graphs from disk to memory, cloning loaded graphs, applying in-place edge deletions/insertions, and performing a simple iterative graph traversal algorithm. Our implementation demonstrates significant performance improvements: it outperforms PetGraph, SNAP, SuiteSparse:GraphBLAS, cuGraph, and Aspen by factors of 177x, 106x, 76x, 17x, and 3.3x in graph loading; 20x, 235x, 0.24x, 1.3x, and 0x in graph cloning; 141x/45x, 44x/25x, 13x/11x, 28x/34x, and 3.5x/2.2x in edge deletions/insertions; and 67x/63x, 86x/86x, 2.5x/2.6x, 0.25x/0.24x, and 1.3x/1.3x in traversal on updated graphs with deletions/insertions.

Below, we plot the runtime (in seconds, logarithmic scale) for loading a graph from file into memory with PetGraph, SNAP, SuiteSparse:GraphBLAS, cuGraph, Aspen, and Our DiGraph for each graph in the dataset.

Next, we plot the runtime (in milliseconds, logarithmic scale) of deleting a batch of 10^−7|𝐸| to 0.1|𝐸| randomly generated edges into a graph, in-place, in multiples of 10. Here, we evaluate PetGraph, SNAP, SuiteSparse:GraphBLAS, cuGraph, Aspen, and Our DiGraph on each graph in the dataset. The left subfigure presents overall runtimes using the geometric mean for consistent scaling, while the right subfigure shows runtimes for individual graphs.

Below, we plot the runtime of inserting a batch of edges into a graph, in-place, using PetGraph, SNAP, SuiteSparse:GraphBLAS, cuGraph, Aspen, and Our DiGraph.

Finally, we plot the runtime of traversing a graph using a simple iterative algorithm (42-step reverse walks from each vertex in a graph) on graphs with edge deletions. We evaluate PetGraph, SNAP, SuiteSparse:GraphBLAS, cuGraph, Aspen, and Our DiGraph on each graph in the dataset.

Refer to our technical report for more details:
Performance Comparison of Graph Representations Which Support Dynamic Graph Updates.

Note

You can just copy main.sh to your system and run it.
For the code, refer to main.cxx.

Code structure

The code structure is as follows:

- inc/_*.hxx: Utility functions
- inc/**.hxx: Common graph functions
- inc/_memory.hxx: The memory allocators (FAA, AA, CP2AA)
- inc/csr.hxx: Compressed Sparse Row (CSR) data structure functions
- inc/Graph.hxx: Graph data structure
- inc/io.hxx: Graph file reader (MTX format)
- inc/main.hxx: Main header
- main.cxx: Experimentation code
- main.sh: Experimentation script
- process.js: Node.js script for processing output logs

Note that each branch in this repository contains code for a specific experiment. The main branch contains code for the final experiment. If the intention of a branch in unclear, or if you have comments on our technical report, feel free to open an issue.

References

• Algorithm 1037: SuiteSparse:GraphBLAS: Parallel Graph Algorithms in the Language of Sparse Linear Algebra; Timothy A. Davis et al. (2023)
• Low-latency graph streaming using compressed purely-functional trees; Laxman Dhulipala et al. (2019)
• cuGraph C++ primitives: vertex/edge-centric building blocks for parallel graph computing; Seunghwa Kang et al. (2023)
• SNAP: A General-Purpose Network Analysis and Graph-Mining Library; Jure Leskovec et al. (2016)
• The University of Florida Sparse Matrix Collection; Timothy A. Davis et al. (2011)
• How can I convert a std::string to int?
• Fastest way to read numerical values from text file in C++ (double in this case)
• What's the difference between istringstream, ostringstream and stringstream? / Why not use stringstream in every case?
• c++ stringstream is too slow, how to speed up?
• Best Approach to read huge files utilizing multithreading; Stephan van Hulst :: Coderanch
• How to get current time and date in C++?
• Signed variant of size_t in standard C++ library
• Is 'signed size_t' different from 'ssize_t'?
• How to create a temporary directory?
• How to amend a commit without changing commit message (reusing the previous one)?
• Syntax for a single-line while loop in Bash
• How can I save username and password in Git?
• How do I tell git to use fewer cores/threads when compressing?
• Containers library :: cppreference
• Date and time utilities :: cppreference
• Standard library header <string> :: cppreference
• Standard library header <algorithm> :: cppreference