A Survey of Graph Processing Paradigms, Version 1

The last decade has seen the growth of data sets that are not only extremely large, but also often unstructured and very dynamic, with the desire to extract not just specific facts about specific entities but also relationships between possibly arbitrary entities. Graphs have emerged as a valuable and productive paradigm for expressing such problems, and there has been an explosion in new graph algorithms, graph query languages, and graph engines that perform such computations. However, given the rapid introduction of such new paradigms, there has been little attempt to look across all of them and identify what are the key new principles that are most valuable for graph computation. This report is an attempt to remedy this by documenting as many of these new paradigms as possible. It was started as part of an NSF grant CCF-1642280 on Scalable Graph Computation, with the goal of having separate chapters document in a semi-standard way the properties of new languages and tools that are graph oriented. Early on, several dozen different variants were identified, with some chapters written by the primary author of this report, Peter Kogge. In addition, a Fall 2018 graduate class in Scalable Graph Processing, given at the University of Notre Dame, had each student develop a separate chapter on one of the uncovered topics. It is expected that future updates to this document will cover addition paradigms.