Mathematical Foundations of the GraphBLAS

Abstract

The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. Mathematically the Graph- BLAS defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, the two are easily connected by matrix mul- tiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.

9 pages; 11 figures; accepted to IEEE High Performance Extreme Computing (HPEC) conference 2016. arXiv admin note: text overlap with arXiv:1504.01039

References in corpus (3)

• Engineering Parallel Algorithms for Community Detection in Massive Networks
• Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
• Graphulo Implementation of Server-Side Sparse Matrix Multiply in the Accumulo Database

Cited by in corpus (17)

• RedisGraph GraphBLAS Enabled Graph Database
• GraphChallenge.org: Raising the Bar on Graph Analytic Performance
• Acc-SpMM: Accelerating General-purpose Sparse Matrix-Matrix Multiplication with GPU Tensor Cores
• Delta-stepping SSSP: from Vertices and Edges to GraphBLAS Implementations
• Temporal State Machines: Using temporal memory to stitch time-based graph computations
• 75,000,000,000 Streaming Inserts/Second Using Hierarchical Hypersparse GraphBLAS Matrices
• Design, Generation, and Validation of Extreme Scale Power-Law Graphs
• GraphChallenge.org Triangle Counting Performance
• Anonymized Network Sensing Graph Challenge
• Mathematics of Digital Hyperspace
• Solving All-Pairs Shortest-Paths Problem in Large Graphs Using Apache Spark
• Effective implementation of the High Performance Conjugate Gradient benchmark on GraphBLAS
• Focusing and Calibration of Large Scale Network Sensors using GraphBLAS Anonymized Hypersparse Matrices
• TeraPool: A Physical Design Aware, 1024 RISC-V Cores Shared-L1-Memory Scaled-up Cluster Design with High Bandwidth Main Memory Link
• SAGE: A Storage-Based Approach for Scalable and Efficient Sparse Generalized Matrix-Matrix Multiplication
• BLEST: Blazingly Efficient BFS using Tensor Cores
• Easy Acceleration with Distributed Arrays