A Survey of Graph Kernels, Version 1.0

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, to date, other than Breadth First and Single Source Shortest Path, there has been far less work on identifying and analyzing graph algorithms, especially in parallel form, than for scientific or conventional big data applications. This report was developed as part of an NSF grant CCF-1642280, to help rectify this problem, with chapters written as part of CSE 60742, a Fall 2018 class in Scalable Graph Processing, at the University of Notre Dame. Each chapter represented a nearly semester-long study of some graph kernel, notionally tied to the student's research. The chapters are written in a semi-standard format, with separate discussions of the general problem that can benefit from efficient implementations of some graph kernel, pointers to some representative data sets, and both scalar and parallel implementations, with scaling data presented as a function of variation in data set size and amount of parallelism.