ABSTRACT / There is increasing interest to apply graph analytical techniques to a wide array of problems, many operating on large-scale graphs with billions of edges. While graph algorithms and their complexity is textbook material, efficient implementation of such algorithms is still a major challenge due to a number of reasons. First, the irregular and unstructured nature of graphs leads to a massive amount of random data access, which makes it difficult to use typical caching and parallelization techniques. Second, to optimize their code, developers need to be aware of the nuances of the underlying hardware which, at the very least consists of multiple CPU cores but often also incorporates heterogeneous components such as GPUs or even FPGAs. During the last decade, a number of graph programming models (such as Google's Pregel) have been proposed but most of these focused on defining high-level abstractions for distributed execution environments and introduced a significant runtime overhead. A potential approach for defining efficient graph processing algorithms is to exploit the well-known duality of graphs and sparse adjacency matrices, using matrix operations to capture algorithms. Surprisingly, only a few recent research prototypes have used this model with little consensus on the set of necessary building blocks. The GraphBLAS initiative (launched in 2013) aims to define a standard to capture graph algorithms in the language of linear algebra - following the footsteps of the BLAS standard which, starting four decades ago, revolutionized scientific computing by defining constructs on dense matrices. In this talk, I give an overview of the GraphBLAS standard and its key components. First, I illustrate how matrix operations on various semirings correspond to the steps in graph algorithms. I then use these operations to present fundamental graph algorithms such as breadth-first search, shortest paths, and the clustering coefficient. Finally, I demonstrate the scalability of the GraphBLAS-based algorithms with the LDBC Graphalytics benchmark. The presented implementations are available open-source as part of LAGraph, a library built on top of GraphBLAS to demonstrate how to design efficient algorithms in linear algebra.
BIO / Gabor Szarnyas is a researcher working on graph processing techniques. His core areas are incremental graph pattern matching, benchmarking graph processing systems, and analyzing large-scale networks. He is the leader of the Social Network Benchmark task force of the LDBC (Linked Data Benchmark Council) and a key contributor to the LDBC Graphalytics benchmark. Gabor holds a research position at the Hungarian Academy of Sciences while teaching database systems and conceptual modelling at the Budapest University of Technology and Economics. He is a frequent speaker at industrial conferences (FOSDEM, GraphConnect) and participates in multiple collaborations between academia and industry (LDBC, openCypher Implementers Group, Property Graph Schema Working Group).