GraphBIG Workloads

CPU Workloads

GraphBIG proposes 12 workloads and 4 micro-benchmarks. The workloads are summarized in the table below. For explanation purpose, we group our selected workloads into four categories according to their high level usages. The details are further explained below.

Category	Workload	Computation Type	Use Case Example
Graph traversal	BFS	CompStruct	Recommendation for Commerce
	DFS	CompStruct	Visualization for Navigation and Exploration
Graph update	Graph construction (GCons)	CompDyn	Graph Analysis for Image Processing
	Graph update (GUp)	CompDyn	Fraud Detection for Bank
	Graph topology morphing (TMorph)	CompDyn	Anomaly Detection at Multiple Scales
Graph analytics	Shortest path (SPath)	CompStruct	Smart Navigation
	K-core decomposition (kCore)	CompStruct	Large Cloud Monitoring
	Connected component (CComp)	CompStruct	Social Media Monitoring
	Triangle count (TC)	CompProp	Data Curation for Enterprise Data Management
	Gibbs Inference (GI)	CompProp	Detecting Cyber Attacks
Social analysis	Degree centrality (DCentr)	CompStruct	Social Media Monitoring
	Betweenness centrality (BCentr)	CompStruct	Social Network Analysis in Enterprise

Graph traversal

Graph traversal is the most fundamental operation of graph computing. Two workloads -- Breadth-first Search (BFS) and Depth-first Search (DFS) are selected. Both are widely-used graph traversal operations.

Graph update

Graph update workloads are performing computations on dynamic graphs. Three workloads are included as following.

(1) Graph construction (GCons) constructs a directed graph with a given number of vertices and edges.

(2) Graph update (GUp) deletes a given number of vertices and related edges from a existing graph.

(3) Topology morphing (TMorph) generates an undirected moral graph from a directed-acyclic (DAG) graph. It involves graph construction, graph traversal, and graph update operations.

Graph analytics

Among all of the graph analytical applications, there are basically three groups of analytics, topological analysis, graph search/match, and graph path/flow. Since basic graph traversal workloads already cover graph search behaviors, here we focus on topological analysis and graph path/flow. As shown in the table, four chosen workloads cover the two major graph analytic types and two computation types. The shortest path is a tool for graph path/flow analytics, while the others are all topological analysis.

In the implementations, the shortest path is following Dijkstra's algorithm. The k-core decomposition is using Matula & Beck's algorithm. The connected component is implemented on BFS traversals and the triangle count is based on Schank's algorithm.

Social analysis

Due to its importance, social analysis is handled as a separate category in our work, although generally social analysis can be considered as a special case of generic graph analytics. We select graph centrality to represent social analysis workloads. Since closeness centrality shares significant similarity with shortest path, we include the betweenness centrality with Brandes' algorithm and degree centrality.

GPU Workloads

Category	Workload	Computation Type	Use Case Example
Graph traversal	BFS	CompStruct	Recommendation for Commerce
Graph analytics	Graph coloring (GC)	CompStruct	Graph matching for genomic medicine
	Shortest path (SPath)	CompStruct	Smart Navigation
	K-core decomposition (kCore)	CompStruct	Large Cloud Monitoring
	Connected component (CComp)	CompStruct	Social Media Monitoring
	Triangle count (TC)	CompProp	Data Curation for Enterprise Data Management
Social analysis	Degree centrality (DCentr)	CompStruct	Social Media Monitoring
	Betweenness centrality (BCentr)	CompStruct	Social Network Analysis in Enterprise