16(3,1) Authors’ version; to appear in the Proceedings of 50th International
Conference on Very Large Databases (VLDB 2024).

# Everest: GPU-Accelerated System For Mining Temporal Motifs

Yichao Yuan  University of MichiganAnn Arbor, MichiganUSA<EMAIL_ADDRESS>,
Haojie Ye  University of MichiganAnn Arbor, MichiganUSA<EMAIL_ADDRESS>,
Sanketh Vedula  TechnionHaifaIsrael<EMAIL_ADDRESS>,  Wynn Kaza
University of MichiganAnn Arbor, MichiganUSA<EMAIL_ADDRESS>and  Nishil
Talati  University of MichiganAnn Arbor, MichiganUSA<EMAIL_ADDRESS>
###### Abstract.

Temporal motif mining is the task of finding the occurrences of subgraph
patterns within a large input temporal graph that obey the specified
structural and temporal constraints. Despite its utility in several critical
application domains that demand high performance (e.g., detecting fraud in
financial transaction graphs), the performance of existing software is limited
on commercial hardware platforms, in that it runs for tens of hours. This
paper presents Everest—a system that efficiently maps the workload of mining
(supports both enumeration and counting) temporal motifs to the highly
parallel GPU architecture. In particular, using an input temporal graph and a
more expressive user-defined temporal motif query definition compared to prior
works, Everest generates an execution plan and runtime primitives that
optimize the workload execution by exploiting the high compute throughput of a
GPU. Everest generates motif-specific mining code to reduce long-latency
memory accesses and frequent thread divergence operations. Everest
incorporates novel low-cost runtime mechanisms to enable load balancing to
improve GPU hardware utilization. To support large graphs that do not fit on
GPU memory, Everest also supports multi-GPU execution by intelligently
partitioning the edge list that prevents inter-GPU communication. Everest
hides the implementation complexity of presented optimizations away from the
targeted system user for better usability. Our evaluation shows that, using
proposed optimizations, Everest improves the performance of a baseline GPU
implementation by 19$\times$, on average.

PVLDB Reference Format:
PVLDB, 17(2): XXX-XXX, 2023.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 17, No. 2 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
https://github.com/yichao-yuan-99/Everest.

##  1\. Introduction

Graph (or network) is a ubiquitous data structure that models various types of
entities and their interactions through the collection of vertices and edges.
For example, graphs can model user interactions in social and communication
networks (Kovanen et al., 2011, 2013; Lahiri and Berger-Wolf, 2007; Paranjape
et al., 2017), transactions in financial networks (Hajdu and Krész, 2020), and
protein/drug interactions in biological networks (Meydan et al., 2013). Small
subgraph patterns called motifs enable the understanding of the structure and
function of complex systems encoded in real-world graphs (Shen-Orr et al.,
2002; Alon, 2007; Newman, 2003). Mining motifs within large graphs is one of
the fundamental problems in network science (Milo et al., 2002).

Most real-world phenomena are dynamic in nature. Static graphs aggregate the
interactions that occur over the graph by omitting the temporal information,
leading to information loss and performance degradation in downstream tasks.
Temporal graph is a type of dynamic graph that stores network interaction
information in terms of timestamped edges between nodes. Therefore, temporal
graphs capture richer information compared to static networks (Kovanen et al.,
2011; Pan and Saramäki, 2011). Temporal motif is a fundamental building block
of temporal graphs, similar to static motif for static graphs. Temporal motifs
are useful for several critical and main-stream applications including
financial fraud detection (Hajdu and Krész, 2020), insider threat
identification in an organization (Glasser and Lindauer, 2013; Mackey et al.,
2018), energy disaggregation monitoring on electrical grids (Shao et al.,
2013), and peptide binding prediction in structural biology (Meydan et al.,
2013). Furthermore, motif counts have been shown to resolve symmetries and
improve the expressive power of graph neural networks (Bouritsas et al., 2022;
Chamberlain et al., 2022).

The wide applicability and criticality of application domains necessitate high
performance of temporal motif mining. However, existing software solutions
(Paranjape et al., 2017; Mackey et al., 2018; Kumar and Calders, 2018; Wang et
al., 2020; Liu et al., 2018; Sarpe and Vandin, 2021b; Kovanen et al., 2011;
Pashanasangi and Seshadhri, 2021) offer sub-optimal performance on CPU
platforms. This is because of the high computation complexity of mining
temporal motifs. While GPU is an attractive solution to accelerate this
workload, our study shows that a straightforward GPU implementation based on
the state-of-the-art temporal motif mining algorithm (Mackey et al., 2018)
heavily under-utilizes GPU resources. For example, our experiments show that
mining a temporal motif four edges in a graph with about 600 million temporal
edges takes more than 18 GPU hours. This is due to long-latency memory
operations, frequent thread divergence due to excessive branching code, and
heavy load imbalance inherent to this workload. Furthermore, these solutions
are limited in terms of their expressive power representing temporal motif
queries.

This paper presents Everest—an optimized system to mine temporal motifs on the
GPU architecture. The inputs to Everest are 1) temporal graph (a type of
dynamic property graph), and 2) user-defined query that specifies a temporal
motif to mine within the input graph. Everest supports an expressive
definition of an input query, where a user can specify (a) the motif
structure/connectivity pattern, (b) temporal edge order, (c) both coarse
(between the last and first edge (Mackey et al., 2018; Paranjape et al.,
2017)) and fine-grained (between consecutive edges (Kovanen et al., 2011;
Pashanasangi and Seshadhri, 2021)) $\delta$-temporal window constraints, (d)
constraints on vertex/edge attributes, as well as (e) temporal anti-edge(s)
(i.e, absence of edge(s)). Using these inputs, Everest produces an optimized
execution plan and runtime that maps efficiently on the GPU architecture. For
scalability, we also support multi-GPU execution out–of–the–box. The outout of
Everest includes exact motif matches, supporting both enumeration and
counting.

To optimize the workload execution on the GPU architecture, Everest employs
the following optimizations. First, Everest extends each GPU thread’s context
to cache key metadata information (e.g., possible motif-graph edge matches)
that reduces the number of costly binary search operations that incur long-
latency memory accesses. Second, Everest generates motif-specific mining code
with auxiliary data structures and a modified algorithm based on pre-decoding
of the temporal motif structure and temporal constraints. This reduces the
amount of branching code and thread divergence, making the generated software
GPU architecture-friendly.

We further introduce sub-tree-level parallelism that enables the exploration
of different sub-trees within the same search tree concurrently. Using this
concept, third, we introduce intra-warp work stealing—a low-cost mechanism
that permits different threads in the same warp to steal work from each other.
Fourth, we propose tail warp work redistribution that reshuffles the work
assignments to different warps when a subset of warps are stuck processing
large volumes of work while others are idle. Everest runtime employs these two
techniques to perform load balancing for improved hardware utilization.
Everest employs the aforementioned optimization ”under-the-hood” by hiding
their implementation complexity within the system itself; a user only needs to
specify a query to mine a specific temporal motif. To scale workload execution
to multiple GPUs, Everest employs a low-cost edge list partitioning scheme
that completely prevents inter-GPU communication.

To evaluate the performance of Everest, we use 13 unique input temporal motifs
and four large-scale temporal graph datasets. Compared to a baseline CPU and
GPU implementations, the proposed optimizations improve the performance by
62.1$\times$ and 19$\times$, on average. The high performance of Everest is
attributed to improved compute and memory throughput. We also show that
Everest offers near-linear performance scaling for a multi-GPU system for
workloads with long execution times. Everest is the first work that designs a
domain-specific system that efficiently maps the workload of temporal motif
mining to the GPU architecture. The key contributions of this work are as
follows.

  * •

Characterization of challenges to efficiently execute the workload of temporal
motif mining on the GPU architecture.

  * •

Generalized motif query interface that supports fine-grained temporal
constraints, vertex/edge labels, and temporal anti-edges.

  * •

Data structure and algorithmic optimizations to reduce operations causing long
memory latency and frequent thread divergence.

  * •

Runtime load balancing techniques that redistribute work among different GPU
threads and warps to improve hardware utilization.

  * •

Everest: an end-to-end open-source system that enables high performance by
hiding all the implementation complexities from the user to provide 19$\times$
performance uplift compared to a baseline GPU implementation.

##  2\. Background

###  2.1. Problem definition

Temporal Graph. We define a temporal graph as an ordered set of temporal
edges, and a temporal edge as a timestamped directed edge between an ordered
pair of nodes. Explicitly, a temporal graph $G$ is represented as a set of
ordered tuples $G=\\{(u_{i},v_{i},t_{i})\\}_{i=1}^{m}$, with $u_{i}$ and
$v_{i}$ denoting the source and destination nodes of the temporal edge
$(u_{i},v_{i})$, respectively, and $t_{i}\in\mathbb{R}^{+}$ being the
timestamp of the edge. We assume that the edges in $G$ are temporally ordered
and have unique timestamps. Furthermore, nodes and edges can be optionally
endowed with discrete/continuous attributes/labels.

$\delta$-Temporal Motif. A $\delta$-temporal motif is defined as a sequence of
$l$ edges, $M=\\{(u_{i},v_{i},t_{i})\\}_{i=1}^{l}$ that are temporally ordered
and occur within a time $\delta\in\mathrm{R}^{+}$, i.e.,
$t_{1}<t_{2}\ldots<t_{l}$ and $t_{l}-t_{1}\leq\delta$. Prior works define
temporal motif mining as the problem of mining occurrences of the
$\delta$-temporal motif $M$ within a larger temporal graph $G$. Everest also
supports other constraints as detailed below.

Fine-Grained $\delta$-Temporal Motif. A fine-grained $\delta$-temporal motif
is a $\delta$-temporal motif with additional temporal constraints between
consecutive edges, $t_{i+1}-t_{i}\leq\delta_{i}$ where $\delta_{i}$ is the
maximum delay between edges $i$ and $i+1$. Notice that a $\delta$-temporal
motif is a fine-grained $\delta$-temporal motif with $\delta_{i}\geq
t_{i+1}-t_{i},\forall i$; thus, the notion of fine-grained $\delta$-temporal
motif subsumes $\delta$-temporal motif.

Temporal Anti-Edges (Kovanen et al., 2011; Pashanasangi and Seshadhri, 2021).
An edge $e_{i}=(u_{i},v_{i},t_{i})\in M$ can be “attached” with a temporal
anti-edge $\neg e_{ij}=\neg(u_{j},v_{j},\delta_{ij})$ implying that we are
matching for the absence of $e_{j}=(u_{j},v_{j},t_{j})$ where
$t_{j}\in[t_{i},t_{i}+\delta_{ij}]$. Intuitively, a temporal edge defines the
inclusion criteria, versus a temporal anti-edge defines the exclusion
criteria.

Generalized Temporal Motif Mining and Use Case. We define generalized temporal
motif mining as the problem of mining occurrences of a fine-grained
$\delta$-temporal motif with optionally added anti-edges and constraints
specified over the node and edge attributes. Typically there are two flavors
of output: the matched motifs can either be enumerated or counted. Our problem
definition targets the general demands of finding isomorphism-based motifs,
which seek bijections between motif patterns and sub-graphs in the data. While
using a similar structural and temporal definition, few other works (Kosyfaki
et al., 2018) adopt different semantics for their motifs from isomorphism
(e.g., matching motifs edges to sets of graph edges), which is out of the
scope of this paper.

Figure 1. A walk-through example of mining an input temporal motif (M) within
an input graph (G).

A Walk-Through Example. Fig. 1 presents an example that captures different
aspects of the definition of temporal motif introduced above. Illustrated in
Fig. 1 are an input temporal graph $G$, a fine-grained $\delta$-temporal motif
$M$ with an anti-edge attached to edge 2, and examples of a valid match and
invalid matches. All timestamps are in units of seconds. Three potential
matches (a), (b), (c) presented in Fig. 1 are considered invalid because: (a)
the edge $(3,0,120)$ happens 110 seconds after edge $(0,1,10)$, which is
larger than maximum allowed time window $\delta$, (b) the edge $(0,1,150)$
occurs 30 seconds after edge $(3,0,120)$, which violates the fine-grained
temporal constraint $\delta_{3}=20$, and (c) the edge $(0,2,130)$ happens 10
seconds after $(3,0,120)$, which is prohibited by the anti-edge $3$ that is
attached to edge $2$. The valid match, on the other hand, satisfies all the
requirements specified by the fine-grained $\delta$-temporal motif.

###  2.2. Algorithmic Prior Work

This paper builds upon a state-of-the-art exact mining algorithm proposed by
Mackey et al. (Mackey et al., 2018), which is more general and efficient
compared to other prior works (Paranjape et al., 2017). In particular, high-
speed algorithms presented in Paranjape et al. (Paranjape et al., 2017) are
only applicable to 3-edge star and triangle mining, and their generic
algorithm requires mining static motifs first that leads to orders of
magnitude more unnecessary work (see Table 4 in §7). Mackey et al.’s algorithm
addresses this inefficiency by resolving both structural and temporal
constraints at each step of the search process.

Algorithm 1 presents the pseudocode for Mackey et al.’s algorithm. This
algorithm can mine $\delta$-temporal motifs without fine-grained temporal
constraints and anti-edges. The input temporal graph is stored as a
chronologically sorted temporal edge list as well as data structures that
describe its topology in a format similar to the Compressed Sparse Row (CSR).
Two CSR-like data structures are used to maintain incoming and outgoing edges
for each vertex, storing their indices in the temporal edge list. The
execution context of the algorithm comprises data structures that maintain
vertex mapping information ($MapMG[]$, $MapGM[]$, $eCount[]$), along with a
stack ($eStack[]$) to store the indices of matched graph edges.

The algorithm mines temporal motifs by expanding search trees in a Depth-First
Search (DFS) manner. The algorithm starts by mapping the first motif edge with
all graph edges, and expanding a search tree to match the rest of the edges
iteratively (line 8). In each iteration, the algorithm either finds a match or
backtracks. Each edge in the motif corresponds to a level in the search tree.
In the matching process, the edge is selected from a candidate edge list that
is generated (line 18) based on the nodes $u/v$ in the current partial match.
The list is a subset of $u/v$’s outgoing or incoming edges, denoted as
$\mathcal{N}_{out}(u)$ and $\mathcal{N}_{in}(v)$ that also obey temporal
constraints. When a valid match is found, the algorithm updates its execution
context and expands the search tree. Otherwise, it backtracks and voids
changes applied to the execution context for the current level. We refer to
the necessary actions to maintain execution context status during search tree
expansion and backtracking as book-keeping actions. The indices of the matched
edges are maintained as a stack (eStack[]). Mapping information in MapMG[] and
MapGM[] is used to check structural constraints (line 20) for candidate edges.

Algorithm 1 Pseudocode of temporal motif mining algorithm

1:Execution Context and Initialization

2: $MapMG[u]=-1\;\forall u\in V_{M};\;MapGM[u]=-1\;\forall u\in V_{G}$

3: $eCount[u]=0\;\forall u\in
V_{G},eStack=[],e_{M}=-1,e_{G}=-1,t^{\prime}\leftarrow\infty$

4:

5:procedure TemporalMotifMining($G,\ M,\ \delta$)

6: Input: temporal graph ($V_{G},E_{G}$), motif ($V_{M},E_{M}$), time limit
$\delta$.

7: Output: temporal motifs

8: while true do $\triangleright$ Loop until all motifs are found

9: $e_{G}$ = $\textsc{FindNextMatchingEdge}()$ $\triangleright$ Search for a
valid edge at the current level

10: if $e_{G}$ is valid then $\textsc{NextLevel}()$ $\triangleright$ A valid
edge is found and go to the next level

11: $e_{G}\;+=\;1$ $\triangleright$ No more matched edges at the current level

12: while $e_{G}>|E_{G}|$ or $time(e_{G})>t^{\prime}$ do $\triangleright$
Backtrack until a level with edges to match

13: if $eStack$ is not empty then $\textsc{Backtrack}()$

14: else return results

15:

16:procedure FindNextMatchingEdge( )

17: $(u_{M},v_{M})=E_{M}[e_{M}],\ (u_{G},v_{G})=MapMG[u_{M}],MapMG[v_{M}]$

18:
$S\leftarrow\textsc{GetCandidateEdgeList(}u_{G},v_{G}\textsc{)}$$\triangleright$
Get a list of candidate edges to match

19: for each edge $e$ in $S$ do $\triangleright$ Return the first edge that
satisfies constraints

20: if $\textsc{StructConstraints(}e,u_{G},v_{G}\textsc{)}$ and
${time}(e)<t^{\prime}$ then

21: return $e$

22:

23:procedure NextLevel( ) $\triangleright$ Prepare to explore the next level
in the search tree

24: if $e_{M}==|E_{M}|-1$ then $\triangleright$ Full motif found in the last
level

25: Output a motif $H$ using $eStack$

26: else$\triangleright$ Partial motif found and expanding the search

27: UpdateDataStructures( ); $e_{M}\;+=\;1$ $\triangleright$ Bookkeep and push
stack

28: $eStack.push(e_{G})$;

29: if $eStack$ is empty then $\triangleright$ Set time limit when the first
edge is mapped

30: $t^{\prime}\leftarrow{time}(e_{G})+\delta$

31:

32:procedure Backtrack( )

33: $e_{G}$ = $eStack.pop()+1$

34: RollbackDataStructures( ); $e_{M}\;-=\;1$ $\triangleright$ Void changes
from the context

35: if $eStack$ is empty then $t^{\prime}\leftarrow\infty$

36:

37:procedure StructConstraints($e,\ u_{G},\ v_{G}$) $\triangleright$ A valid
edge needs to be structurally

38: $(u_{G}^{\prime},v_{G}^{\prime})\leftarrow E_{G}[e]$ $\triangleright$
consistent with the existing partial motif

39: $u_{consistent}\leftarrow u_{G}=u_{G}^{\prime}$ or $(u_{G}<0$ and
$MapGM[u_{G}^{\prime}]<0)$

40: $v_{consistent}\leftarrow v_{G}=v_{G}^{\prime}$ or $(v_{G}<0$ and
$MapGM[v_{G}^{\prime}]<0)$

41: return $u_{consistent}$ and $v_{consistent}$

42:

43:procedure UpdateDataStructures( ) $\triangleright$ Maintain mapping
information

44: $(u_{G},v_{G})\leftarrow E_{G}[e_{G}],\;\,(u_{M},v_{M})\leftarrow
E_{M}[e_{M}]$

45: $MapMG[u_{M}]=u_{G},\;\;MapMG[v_{M}]=v_{G}$ $\triangleright$ Map motif
node to graph node

46: $MapGM[u_{G}]=u_{M},\;\;MapGM[v_{G}]=v_{M}$ $\triangleright$ Map graph
node to motif node

47: $eCount[u_{G}]+=1,\;\;eCount[v_{G}]+=1$ $\triangleright$ Increment mapped
edge cnt

48:

49:procedure RollbackDataStructures( ) $\triangleright$ Maintain mapping
information

50: $eCount[u_{G}]-=1,\;eCount[v_{G}]-=1$ $\triangleright$ Reduce mapped edge
cnt

51: if $eCount[u_{G}]==0$ then $\triangleright$ No edges of $u_{G}$ mapped

52: $u_{M}\leftarrow MapGM[u_{G}]$

53: $MapGM[u_{G}]=-1,\;MapMG[u_{M}]=-1$ $\triangleright$ Free $u_{G},u_{M}$

54: if $eCount[v_{G}]==0$ then $\triangleright$ No edges of $v_{G}$ mapped

55: $v_{M}\leftarrow MapGM[v_{G}]$

56: $MapGM[v_{G}]=-1,\;MapMG[v_{M}]=-1$ $\triangleright$ Free $v_{G},v_{M}$

57:

58:procedure GetCandidateEdgeList($u_{G}$, $v_{G}$) $\triangleright$ Gather
candidates by mapping information

59: if $u_{G}\geq 0$ and $v_{G}\geq 0$ then $\triangleright$ Both
$u_{G},v_{G}$ mapped to motif nodes

60: $S\
\leftarrow\\{e\in\mathcal{N}_{out}(u_{G})/\mathcal{N}_{in}(v_{G}):t_{e}>{time}(e_{G})\\}$
$\triangleright$ filter via binary search

61: else if $u_{G}>0$ then $\triangleright$ Only $u_{G}$ mapped to a motif
node

62: $S\ \leftarrow\\{e\in\mathcal{N}_{out}(u_{G}):t_{e}>{time}(e_{G})\\}$
$\triangleright$ filter via binary search

63: else if $v_{G}>0$ then $\triangleright$ Only $v_{G}$ mapped to a motif
node

64: $S\ \leftarrow\\{e\in\mathcal{N}_{in}(v_{G}):t_{e}>{time}(e_{G})\\}$
$\triangleright$ filter via binary search

65: else$\triangleright$ Both $u_{G},v_{G}$ not mapped

66: $S\ \leftarrow\\{e\in E_{G}:t_{e}>{time}(e_{G})\\}$

67: return $S$

###  2.3. GPU Architecture

To make our optimizations accessible to readers, we briefly discuss the basics
of GPU architecture. GPUs offer significantly higher compute throughput and
memory bandwidth compared to CPUs. A GPU consists of tens of Streaming
Multiprocessors (SMs). Host CPU launches kernels that contain thousands of
parallel threads for GPU execution. GPU threads are grouped into blocks to
execute on the SMs. Threads in a block are executed in a Single Instruction
Multiple Threads (SIMT) execution model. Threads among the same block are
grouped into warps to be executed together. GPU achieves peak throughput when
all threads are on the same execution path. However, when the threads in a
warp take a branch, their execution path may diverge. This is known as branch
divergence, where a GPU needs to execute the resulting two paths sequentially,
which reduces overall performance. Branch divergence leaves GPU hardware to be
idle when a subset of threads is not executed in each divergent path. Besides,
non-uniform amount of work assigned to GPU threads under-utilizes compute
resources.

GPUs are equipped with DRAM as their device memory to hold data for execution,
the size of which is often limited (in 10s of GB). DRAM in GPU can be accessed
by high-bandwidth interfaces such as GDDRx. To hide the memory latency of
fetching data from DRAM, GPUs also employ on-chip cache memory and large
register files. This physical memory hierarchy is used by several virtual
memory spaces, e.g., constant memory and shared memory. Read-only data
structures, e.g., input temporal graph, can be placed in constant memory.
Shared memory, on the other hand, can be used to enable communication between
different threads within a block. Furthermore, threads in the same warp can
also communicate via register shuffling at a much lower cost.

##  3\. Motivation

###  3.1. High Algorithmic Complexity

Exactly mining temporal motifs poses significant computational challenges due
to their inherent complexity. Denote by $|E_{G}|$ the number of temporal
edges, and by $|E_{M}|$ the number of temporal edges and anti-edges in the
motif, respectively. Let $k$ be the expected number of edges occurring in the
graph within a duration $\delta$. The algorithmic complexity of generalized
temporal motif mining is $\mathcal{O}\left(|E_{G}|\cdot k^{|E_{M}|-1}\right)$:
it grows exponentially with the size of the motif, polynomially with the
average number of edges occurring within time $\delta$, and linearly with the
size of the temporal graph. Extending the time constraint $\delta$ increases
the average number of edges occurring within the time duration. This means
that for each edge in $E_{M}$, there will be more edges to explore in $E_{G}$,
thereby extending the width of the DFS search tree. However, adding fine-
grained temporal constraints reduces the width of the search tree. Increasing
the size of the motif increases the depth of the search tree. In the worst
case, there are $|E_{G}|$ edges to match for each edge added to the motif,
thus the complexity grows exponentially with the tree depth. Notably, this
also holds for adding anti-edges because in the worst case, one needs to
explore $|E_{G}|$ edges to ensure the exclusion of the anti-edge.

###  3.2. Suboptimal Performance of Existing Software on GPUs

GPU is an attractive candidate to accelerate the complex temporal motif mining
workload due to its high compute throughput and memory bandwidth. Prior works
(Chen et al., 2020; Chen and Arvind, 2022) have already made a strong case for
accelerating static graph mining on GPUs. However, no work exists that
optimizes motif mining in temporal graphs. Next, we study the performance of
Mackey et al.’s algorithm on a GPU.

Baseline GPU Implementation. It is trivial to parallelize Algorithm 1 by
expanding each search tree using a different thread. However, the memory
complexity of MapGM[] and eCount[] is $O(|V_{G}|)$, making it infeasible to
allocate this large amount of memory for each thread on a GPU. Our GPU
baseline implementation removes MapGM[] and only uses MapMG[] to check the
structural constraints (line 20). The entire MapMG[] table is iterated to
verify whether a new edge is consistent with the current partial result,
instead of using MapGM[] (line 39 \- 40). On the other hand, eCount[] can only
use $|V_{M}|$ entries by slightly changing the book-keeping logic in
UpdateDataStructures() and RollbackDataStructure() subroutines. The resulting
GPU implementation expands an independent search tree on each thread.

Figure 2. Profiling results for mining M6 on wiki-talk: (a) instruction count
breakdown and (b) stall distribution.

Long Execution Times. Using this implementation, we measure the time to find
temporal motifs using an NVIDIA A40 GPU. We refer the reader to §6 for details
on input temporal motif queries and temporal graphs. Using our experimental
setup, we find that mining tasks run for several hours (e.g., mining M6, M11,
and M12 in ethereum graph takes 18.6 hours, 3.3 hours, and 3.4 hours,
respectively). While we use some of the largest graph datasets available in
the public domain, larger graphs used by the industry further exacerbate
runtime, motivating our optimization effort.

Execution Bottlenecks. Using our baseline implementation, we conduct a
detailed performance analysis to find execution bottlenecks as detailed below.
We use a representative workload of mining M6 in wiki-talk graph to conduct
this study.

1\. Long-latency binary search operations. In order to generate a list of
candidate edges, Algorithm 1 uses binary search to filter out neighboring
edges of a vertex that does not satisfy temporal constraints (lines 60, 62,
64). This induces random accesses to the input graph’s large CSR structures
which are not GPU cache friendly. This results in long latency device memory
accesses that stall GPU execution. Fig. 2 presents quantitative evidence for
this. In this figure, fetching and searching correspond to fetching
neighboring edges and performing binary search, respectively, in the
GetCandidateEdgeList() function. Fig. 2(a,b) show that binary search
contributes to 53.5% of GPU instructions and 57.2% of stall cycles.
Furthermore, these long-latency memory accesses contribute to 56.1% stalls
during the search phase (not shown due to space limit).

Figure 3. (a) Non-uniform size of search trees: percentage of nodes in the
largest search trees among all search tree nodes, (b) effect of load imbalance
on GPU performance metrics.

2\. Excessive thread divergence. As explained in §2.3, GPU handles branch/if
conditions in the code using the branch divergence mechanism that leaves a
subset of compute units mapped to a warp idle. Algorithm 1 clearly shows that
branch operations are ubiquitous in the temporal motif mining algorithm.
Furthermore, the outcome of these branch operations changes as the algorithm
progresses as they depend on dynamic runtime data. For example, the
GetCandidateEdgeList() function uses the information of which graph nodes are
previously mapped to motif nodes to decide which neighborhood information to
fetch from memory. The widespread nature of these branch operations results in
frequent branch divergence, and consequently, under-utilization of GPU
resources.

3\. Extreme load imbalance. The baseline implementation expands each search
tree using a unique GPU thread. The amount of work for expanding the search
tree depends on the motif and graph structures, and the extent of temporal
interactions between nodes. Because real-world graphs follow power-law
connectivity structure (i.e., a small subset of popular nodes connected to a
large fraction of edges) the size of each search tree, consequently, the
amount of work assigned to each thread varies significantly. Fig. 3(a) shows
that the top 0.1% of the search trees (by size) constitute 34% of explored
tree nodes in the entire execution. This clearly shows that the work
assignment to each thread is highly skewed. Fig. 3(b) shows the effect of this
on GPU performance metrics. Because of work imbalance, this implementation
only achieves 22.8% occupancy, and has 10.9 active warps per SM, much lower
than theoretical limits. Furthermore, on average, only 1 out of 32 threads are
active.

Next, we briefly explain the types of this load imbalance at different levels
of the GPU architecture. All threads within a GPU warp use same instructions
to execute in a SIMT fashion; when certain threads complete mining their
assigned search trees before others, this leads to intra-warp load imbalance.
All threads within a GPU block are implicitly synchronized; the compute
resources allocated to a block cannot be released until all threads return.
When a subset of threads explore large search trees while others finish
execution, this also results in intra-block load imbalance, rendering other
GPU resources idle. A GPU kernel finishes when all the blocks finish
execution. With extreme load imbalance, there are often a few blocks with
outstanding work, while others finish, that render GPU resources idle, causing
intra-kernel-launch load imbalance.

###  3.3. Need For More Expressive Queries

It is possible to make the definition of $\delta$-temporal motifs more
expressive using additional constraints. Certain algorithms (Kovanen et al.,
2011; Pashanasangi and Seshadhri, 2021) for mining temporal motifs adopt more
detailed temporal constraints on consecutive edges within the motifs. In some
static pattern mining systems like (Jamshidi et al., 2020), the concept of
anti-edge is introduced to let users further restrict their patterns. Missing
these constraints from users leads to unwanted results that increase execution
time for searching and post-processing. An ideal system should support the
most expressive query definition that includes labels on nodes/edges, fine-
grained temporal constraints, and temporal anti-edge. This abundant set of
constraints empowers users to accurately express their intention for practical
real-world mining use cases.

##  4\. Everest Design Overview

This section provides the design goals and overview of the execution pipeline,
user-defined query, and runtime components of Everest.

###  4.1. Design Goals

Everest addresses the unique challenges of efficiently executing temporal
motif mining on multi-GPU systems with the following specific design goals.

GPU-friendly algorithm and implementation. Naively mapping Mackey et al.’s
algorithm to GPU causes sub-optimal execution behavior (§3.2). The presence of
long-latency binary search and control flow operations significantly declines
the overall performance. Therefore, Everest needs to integrate GPU-friendly
adaptations into the original algorithm and provide high-quality
implementation to enhance high efficiency on GPUs.

Memory footprint reduction and multi-GPU support. While a single GPU offers
massive throughput, the amount of memory on each GPU is often limited. For
example, a state-of-the-art GPU used for our evaluation, i.e., NVIDIA A40,
only has 48GB of memory. Therefore, it is imperative to reduce the amount of
memory footprint used by the workload. Furthermore, many real-world graphs are
extremely large in size, entailing billions to trillions of nodes and edges.
This precludes a graph input itself to fit on a single GPU’s memory.
Therefore, important design goals of Everest include reducing the memory
footprint of the workload and offering multi-GPU support to scale to large
input graph sizes.

Load balancing at all levels. The skewed work distribution of temporal motif
mining results in harmful load imbalance at every level of GPU execution
(§3.2). Because the degree of imbalance depends on both the input temporal
graph and user-defined query, the imbalance can lead to exceedingly poor
system performance in certain scenarios. A key design goal of Everest runtime
system is to be able to intelligently detect load imbalance and execute load
re-distribution at runtime at all levels of the GPU execution to ensure
consistently high overall performance.

Expressive and user-friendly query interface. While a few prior works
(Paranjape et al., 2017; Mackey et al., 2018; Kumar and Calders, 2018; Wang et
al., 2020; Liu et al., 2018; Sarpe and Vandin, 2021b) optimize the execution
of temporal motif mining on CPUs, they can only support limited motif query
definitions (i.e., $\delta$-temporal motif discussed in §2.1). Everest strives
to adopt a broader definition of temporal motif, supporting additional
features such as fine-grained temporal constraints, labels on both nodes and
edges, and temporal anti-edges. Additionally, Everest supports both motif
counting and enumeration. Such a comprehensive and user-friendly interface is
essential to enhance the system’s usability.

###  4.2. Execution Pipeline

Figure 4. Everest execution pipeline overview. Input: temporal graph and user-
defined query. Output: optimized runtime and pre-processed data graph for
multi-GPU execution.

Fig. 4 provides a high-level overview of the execution pipeline of Everest.
The inputs to this pipeline include a temporal graph and a user-defined query.
The outputs of this pipeline are an optimized execution plan and intelligent
runtime, and pre-processed graph, which are used to mine user-defined queries
within an input graph on a multi-GPU system. Single-GPU system is a special
case of the multi-GPU system, and can be defined by the user.

Before a query is decoded, an input graph is processed. Following the
partition strategy elaborated later in §5.3.1, the data loader generates major
partitions from the temporal edge list ( 0). The generation of major
partitions occurs prior to any query processing and is not on the critical
path of resolving queries. The data loader uses GPUs to perform all the data
preprocessing for high efficiency. Next, the user-defined query ( 1) is
decoded and inputted to the code generator ( 2). Note that Everest supports
the most generalized definition of a temporal motif with an arbitrary number
of nodes/edges/connections, fine-grained temporal constraints, node/edge
labels, and anti-edges. The output of mining can be either motif enumeration
or counting. The code generator generates optimized code that uses the minimum
number of runtime variables for the mining to improve occupancy. This also
includes multiple runtime mechanisms to improve the execution efficiency and
routines to handle additional constraints ( 3), as detailed in §4.4. The
optimized code is compiled into a shared library (.so) ( 4) that will be later
loaded into Everest runtime. At the same time, minor graph partitions are
constructed based on the partitioning strategy ( 5, §5.3.1) for a given query.

The runtime system loads the optimized library ( 6), and uses it to construct
GPU workers on each GPU. Instructed by the GPU work scheduler, each GPU worker
loads and processes a different graph partition ( 7). The GPU work scheduler
assigns work to GPU workers, monitors their execution status, and performs
load balancing if necessary ( 8, §5.3.2). After all the partitions are
consumed, the results are collected from all GPU workers ( 9). The results
include motif matches (enumeration or counting) for a given user-defined query
on an input temporal graph.

###  4.3. User-Defined Query

Figure 5. Example user-defined query to mine a temporal 4-cycle with fine-
grained temporal constraints and an anti-edge in an input graph ethereum.

Fig. 5 shows the user-defined query input. There are four sections in this
query: 1) temporal motif pattern (pattern), 2) input temporal graph
(in_graph), 3) additional constraints (constraints), and 4) runtime parameters
(runtime_params). The first section details the basic shape and connectivity
of a temporal motif to be mined. While an actual query details the structure
and temporal order of motif edges, for brevity, we show it as a temporal
4-cycle. Additionally, the query specified the file location of an input
temporal graph.

The constraints section details additional constraints to be mined. Following
the formal definitions of these constraints from §2.1, this example query
attempts to mine a motif with the following labels: two yellow and two blue
nodes. While these labels are simplified as node colors for illustration, it
is possible to specify more realistic labels in Everest (e.g.,
customer/merchant labels for financial transaction network) for real-world
graph settings. Additionally, a temporal anti-edge is specified with a
temporal order (t:3). This means an anti-edge is attached to edge 2 and the
motif matches must not contain an edge between nodes 2 and 0 within a time
window ($\delta_{23}$) from edge 2. This follows temporal constraints: 1)
course-grained (cg_delta) and 2) fine-grained (fg_delta). The course-grained
temporal constraint is the time window ($\delta$) for an entire motif. Fine-
grained constraints, on the other hand, denote maximum time difference between
consecutive edges (e.g., $\delta_{1}$).

The last section specifies two runtime constraints. The example in Fig. 5
shows that a user is interested in counting the number of motifs (i.e.,
enumeration is false). In the case that enumeration is true, a user must
define the number of matches to be enumerated (not shown in the figure).
Furthermore, a user can also define the number of GPUs (default is set to
one).

###  4.4. Runtime Components

Figure 6. Everest runtime components overview.

Fig. 6 presents the runtime components as outlined below.

####  4.4.1. Thread-local Components.

Each GPU thread explores a search tree to mine a user-defined motif in an
input graph. Everest GPU code supports two types of runtime components that
execute at thread level as shown in green boxes in Fig. 6: 1) unique
structural and temporal constraints from the query, and 2) runtime
optimizations. As discussed in §4.3, motif constraints include fine-grained
temporal constraints, temporal anti-edges, and labels on vertices and/or
edges. Additionally, Everest proposes the following two optimizations to
improve performance.

Caching candidate edges (§5.1.1). To avoid unnecessary binary search
operations during backtracking, per-thread context caches the candidate edges
at each search level. Moreover, the cached candidate edge entries enable work
sharing among threads.

Motif-specific code generation (§5.1.2). While our system supports mining any
arbitrary motifs, the proposed Everest backend generates motif-specific
optimized code for GPU execution. In particular, Everest generates code with
auxiliary data structures to simplify the program’s control flow at runtime.

####  4.4.2. Load balancing at a Single-GPU Level.

Beyond the scope of a single GPU thread, the following components enable the
detection and re-distribution of skewed workload at a single-GPU level to
improve hardware utilization.

Intra-warp work stealing (§5.2.1). This mechanism takes advantage of intra-
warp fast register shuffling and synchronization primitives to perform
frequent work stealing at a low cost.

Tail warp work redistribution (§5.2.2). This optimization redistributes the
work among all warps when there is no pending work to keep all warps busy
within a kernel launch. It aborts warps that are likely exploring large search
trees and share their work with other idle warps.

####  4.4.3. Multi-GPU support.

Everest provides a low-cost edge list partition strategy to divide work for
multiple GPUs. At runtime, a GPU work scheduler employs a queue-based work
scheduling to balance the load among multiple GPUs.

##  5\. Everest Design and Optimizations

This section discusses Everest design and optimizations in detail. Everest
completely hides the complexity of the proposed optimizations from a user. As
discussed in §4.2, these optimizations are conducted as part of Everest
backend.

###  5.1. Execution Efficiency Optimizations

Below, we discuss thread-local runtime optimizations.

Figure 7. (a) Input temporal motif and its corresponding search tree expansion
with the proposed cached candidate edges, and (b) per-thread execution context
while matching motif edge 4.

####  5.1.1. Caching Candidate Edges.

In the baseline algorithm, when a thread expands the search tree to the next
level, it discards the candidate edges at the current level (line 10 in
Algorithm 1). As a result, when the algorithm backtracks, it needs to search
for these edges again by performing expensive binary search that constitutes
around 50% of the total instructions and stalls (§3.2).

Proposed Optimization. Based on this observation, we find an opportunity to
reduce the number of costly binary search operations in the workload by
caching candidate edges. Specifically, when a match between a motif edge and a
graph edge is found, we propose to cache the rest of the candidate edges that
could have been matched in a thread context. The result of this caching is
used while backtracking from the same tree node. This converts a costly binary
search operation into a thread context read while backtracking. This results
in reducing the number of binary search operations by half at a marginal cost
of thread context storage increase.

Fig. 7(a) illustrates our solution, which shows the search tree status when
the algorithm is matching edge 4 in the motif. The search tree has two levels.
Level 0 corresponds to the motif edge 2 and level 1 is searching for an edge
in its candidate edge list to match the motif edge 4. The candidate edge list
at the current search level (level 1) is represented by Beg and End. Before
the search tree expands to level 1, the remaining candidate edges in level 0
are stored in sBeg0 and sEnd0. When the candidate edge list in level 1 is
exhausted, the algorithm backtracks and loads the remaining candidate edge
list to Beg and End to continue execution at level 0, avoiding a costly edge
search operation.

####  5.1.2. Motif-Specific Code Generation.

The baseline generalized algorithm supports mining of any arbitrary
$\delta$-temporal motif, precluding specific motif-specific optimizations.
While Everest is a versatile mining system supporting any arbitrary temporal
motif, the proposed code generator is further specialized to employ additional
optimizations for user-specific queries.

Proposed Optimizations. After decoding a specific input motif, Everest
generates a read-only data structure called minfo before the execution starts.
This is an array of structures whose an $i^{th}$ entry describes the execution
progress of the $i^{th}$ level of the search tree. In what follows, we
illustrate how to use this data structure to simplify various mining
operations including book-keeping, candidate edge generation, and structural
constraint checking. As discussed in §3.2, these operations result in
excessive thread divergences and under-utilize GPU resources.

1\. Simplifying Book-keeping Operations. Using minfo, it is possible to
specify the number of valid mappings at each search tree level. Using this, we
can remove the costly operations to vertex mapping data structures. For
example, Fig. 7(b) shows that m0-m3 store node mapping information. Among
them, only the first three are valid at level 1. When edge 4 is being
searched, only vertices 1, 2, and 3 are mapped for the partial motif. At each
book-keeping phase, minfo is used to avoid unnecessary operations to maintain
vertex mapping data structures by keeping the number of valid mappings at each
level. Voiding changes to mapping structures during backtracking is automatic
by loading the minfo entry at the lower level. Using this optimization,
Everest completely removes eCount[] and sub-routine RollbackDataStructures
from Algorithm 1.

2\. Simplifying Edge List Generation. In Algorithm 1 the candidate edge lists
are generated in GetCandidateEdgeList based on the runtime information of
which graph vertices are previously mapped. As vertex mappings depend on the
progression of the algorithm, this branching behavior results in thread
divergence and performance slowdown. Everest proposes to use minfo to
statically record where to get candidate edges for each search tree level
based on the structure and temporal order of motif edges. This way, the costly
branching behavior is transformed into minfo reads in most cases. The only
exception to this is when both source and destination vertices are mapped,
where Everest performs vertex mapping-based edge list selection.

3\. Simplifying Structural Constraint Checking. In the GPU baseline, the whole
mapping table is iterated over to check structural constraints for a new edge.
This can be greatly simplified with minfo. For example, to match edge 4 in
Fig. 7, the algorithm only needs to check whether its destination is
conflicting with the mapping for vertex 1 and 2 (m0-m1). minfo simplifies
structural constraint checking by using pre-decoded motif structure and
temporal edge order. Thus, fewer than half of the comparisons are used to
check structural constraints.

####  5.1.3. Lifting Thread Context to Registers.

We lift thread contexts to store them into the GPU registers to enable faster
access and the intra-warp work stealing mechanism (§5.2.1). The array-like
data structures including the stacks and the mapping table are declared as a
set of variables and be accessed via switch statements, such as sBeg, sEnd,
and m variables.

###  5.2. Load Balancing Optimizations

The baseline implementation maps the expansion of each search tree to a GPU
thread. This coarse-grained mapping exacerbates load imbalance as different
search trees explore vastly different numbers of tree nodes (Fig. 3). Next, we
introduce the concept of Sub-Tree-Level Parallelism (STLP) and load balancing
in Everest.

Sub-Tree-Level Parallelism (STLP). We refer to expanding sub-trees of a search
tree in parallel as sub-tree-level parallelism. Due to the DFS search order,
it is not possible to exploit STLP in Mackey et al. (Mackey et al., 2018)’s
algorithm as the nature and sizes of sub-trees within the same tree are
unknown at runtime. However, a sub-tree at each level can be expanded from the
candidate edges (§5.1.1). Everest proposes to speculatively exploit STLP by
sharing edges inside the candidate edge list with multiple threads.
Specifically, Everest speculates that the shared candidate edges imply
unexplored sub-trees. The speculative nature of this optimization may result
in unnecessary work when the candidate edges fail to meet structural/temporal
constraints, and thus discarded in the original algorithm. Below, we present
two sophisticated optimizations and their implementations that intelligently
employ STLP without hurting overall performance.

####  5.2.1. Intra-warp Work Stealing.

Figure 8. Example of intra-warp work stealing.

The goal of intra-warp work stealing is to reduce the impact of intra-warp
work imbalance using sub-tree-level parallelism. On average, the GPU baseline
only keeps 1 thread active in each warp due to the imbalanced load (§3.2).
Everest proposes a novel low-cost work stealing mechanism using warp-level
primitives in CUDA. The proposed design introduces minimum overheads and
selects candidate edges that are less likely to be discarded due to constraint
violations.

We define a thread to be active or idle depending on whether it has
outstanding work or not. At the end of each iteration, the presence of any
idle threads triggers this work stealing mechanism. Empirically, we enable
this after 20 iterations to avoid slowing down warps that have no threads with
much outstanding work. To realize this mechanism, all threads use
__balloc_sync to generate an Active Mask, where $i^{th}$ bit denotes whether
the $i^{th}$ thread is active. Using this mask, all threads in a warp are
divided into multiple subgroups, each with one active thread. Using this
thread grouping, an active thread shares work to other idle threads within the
same subgroup, as explained with an example below.

Fig. 8(a,b) illustrates how threads are combined in three subgroups, where
each subgroup has one active thread. Within each subgroup, an idle thread will
steal one candidate edge from the beginning of the candidate edge list at each
level. It also copies other execution contexts from the active thread. The
stealing is conducted via register shuffling to minimize overhead. The edges
are shared from the beginning of edge lists such that they are the most likely
to satisfy the temporal constraint. Fig. 8(c,d) further illustrates this work
stealing with an example of subgroup 3. The first two edges in the candidate
edge list at level 0 are A and B, and they are stolen by threads 5 and 6,
respectively. Similarly, thread 5 and 6 steal edge L and M from level 1. After
this work stealing, threads 5 and 6 independently expand their sub-trees in
parallel.

Theoretical Performance Analysis. The warp-level speedup of this optimization
can be roughly modeled as
$\frac{32}{t_{\text{imb}}\left(1+\frac{k\epsilon}{\mathcal{I}_{\text{opt}}}\right)}$,
where $\mathcal{I}_{\text{opt}}$ is the number of search iterations used by
the optimized code within a warp. $t_{\text{imb}}<32$ is the number of active
threads within a warp in the imbalanced baseline. $k<\mathcal{I}_{\text{opt}}$
is the number of times this optimization is triggered and $\epsilon<1$ is the
work-stealing overhead relative to a search iteration. We observe that
$t_{\text{imb}}$ is usually much smaller than warp width 32 due to intra-warp
work imbalance. Each trigger of this optimization steals multiple sub-trees,
resulting in a smaller $k$. Our warp-primitive-based efficient implementation
results in a smaller $\epsilon$. In practice, we observe
$t_{\text{imb}}\left(1+\frac{k\epsilon}{\mathcal{I}_{\text{opt}}}\right)<32$,
and a meaningful speedup on average across warps. Furthermore, the speedup is
correlated to the work, $\mathcal{I}_{\text{opt}}$, assigned to a warp.

####  5.2.2. Tail Warp Work Redistribution.

Figure 9. Illustration of tail warp work redistribution for a single thread.

Tail warps are defined as a few warps with outstanding work when most other
warps finish their execution and the task queues are empty. This phenomenon
exists because of the power-law nature of graph connectivity, where processing
a small subset of search trees takes significantly longer time than most other
trees. Tail warps lead to load imbalance within a GPU kernel. Consequently,
the GPU baseline only achieves 22.8% of occupancy and keeps 10 out of 48 warps
active per SM (§3.2). The goal of tail warp work redistribution is to
redistribute the work of the tail warps by exploiting sub-tree-level
parallelism.

Everest enables this optimization using a software work assignment mechanism.
Traditionally, GPU programs group parallel tasks using thread blocks and rely
on hardware schedulers to assign work to SMs. However, threads cannot inspect
the execution status of the kernel in this model, because it is managed by the
hardware. This prevents warps from realizing whether they are tail warps or
not. In contrast, Everest maintains a global work queue that dispatches work
at warp granularity, which can be inspected to find the amount of outstanding
work. As the number of concurrently executing warps is limited, the global
queue experiences minimal contention. Using this mechanism, Everest enables
tail warp work redistribution in three subsequent steps as detailed below.

Step 1. Abort tail warp execution. A warp aborts execution when the task queue
is empty. The first warp that exits signals all other warps to stop their
current work via a variable. Each warp checks the signaling variable
periodically. After receiving the signal, the threads in a warp set a timeout
for its current execution. If its work is not finished by the timeout, the
thread dumps its context into a buffer, which includes candidate edge lists at
all levels. Empirically, Everest reads the signaling variable every 1024
iterations and sets the timeout to 100 milliseconds.

Step 2. Refine thread context. Everest then post-processes the contexts of
tail warps such that all edges in the candidate edge list are within the
$\delta$-time window. The invalid edges are removed by moving the end pointer
of each candidate edge list forward. The resulting edges satisfy temporal
constraints and are most likely to spawn a sub-tree. Similar to §5.2.1, the
refined thread contexts can be shared by multiple threads to exploit STLP.
Fig. 9(a,b) illustrate this process with an example. Before refinement, the
thread context has two levels, each with a long candidate edge list. After
refinement, level 0 only has edge A and level 1 only contains edge L, M, and
N.

Step 3. Work redistribution. To complete the execution, Everest launches a new
kernel whose threads resume execution from the refined thread contexts. This
new kernel is treated as a regular kernel exhibiting all mechanisms including
tail warp work redistribution. If a refined context’s longest candidate edge
list has N edges, its candidate edges will be shared by N threads. Fig. 9(c)
illustrates how work is redistributed. The refined thread context’s longest
candidate edge is at level 1, containing 3 edges. Its candidate edges are
redistributed and form three search trees, which are expanded independently.
The first tree contains edges A and L, and edge M and edge N are expanded by
the other two trees.

Theoretical Performance Analysis. The speedup introduced by this optimization
can be approximated as follows:

$\frac{o}{1-\Phi\mathcal{L}_{\text{imb}}}\leq o\phi\text{, where
}\Phi=\frac{\phi-1}{\phi}$

We use $\phi$ to denote the total number of CUDA cores on a GPU divided by its
warp width, and $\phi=336$ on NVIDIA A40. $o\lessapprox 1$ represents the
small aggregated overhead of monitoring the signaling variable. Let
$0<\mathcal{L}_{\text{imb}}<1$ represent the fraction of total execution time
consumed by a tail warp. Note that $\mathcal{L}_{\text{imb}}$ can be
significant even if the tail warp processes only a tiny fraction of the total
work. When the tail warp is responsible for 1% of the total work,
$\mathcal{L}_{\text{imb}}\approx 0.77$. When the work distribution is highly
skewed, $\mathcal{L}_{\text{imb}}$ is large and this optimization can bring
significant speedup (up to $o\phi$). On the other hand, when
$\mathcal{L}_{\text{imb}}$ is small, the overhead becomes noticeable. When the
tail warp’s execution time is less than 100ms, this optimization does not take
effect, and workload slows down by a factor of $o$. The overhead is designed
to be small, as the signaling mechanism only involves a few branches per
iteration and one global memory access every 1024 iterations.

###  5.3. Multi-GPU Support

####  5.3.1. Edge List Partitioning.

The goal of Everest edge partitioning is to maximize efficiency by preventing
inter-GPU communication. Unlike prior graph partitioning techniques (LaSalle
and Karypis, 2016), Everest does not use a convoluted partitioning scheme,
because Everest needs to partition graph edges in temporal order to ensure
GPU-local accesses. To this end, we define major and minor edge list
partitions.

If a search tree is expanded using a root node with an edge timestamp of
$t_{0}$, and the coarse-grained time window is $\delta_{0}$, then this tree
will only access edges within the time interval of [$t_{0}$,
$t_{0}+\delta_{0}$]. Therefore, only a small subset of edges need to be
replicated on multiple GPUs at partition boundaries for all accesses to be
GPU-local. For an $N$-GPU system, the edge list is chronologically partitioned
into $N$ contiguous sub-lists, called major partitions. A major partition is
assigned to each GPU for processing.

Major partitions do not ensure all GPU-local accesses as trees expanded at
partition boundaries span multiple major partitions. Therefore, Everest also
generates minor partitions for these edges on-the-fly after a query is
provided to the system. Assume a query with $\delta=\delta_{0}$ and a major
partition contains all edges between the edges $e_{i}$ and $e_{j}$, where
$i<j$. Let $e_{k}$ be the last edge in this major partition such that
$t_{j}-t_{k}>\delta_{0}$, where $t_{k}$ is the timestamp of $e_{k}$. Edges in
the range [$k+1$, $j$] are not mined in a major partition, as they cannot
ensure GPU-local accesses. Let $e_{l}$ be the first edge that satisfies
$t_{l}-t_{j}>\delta_{0}$. The corresponding minor partition includes edges
within the range [$k+1$, $l$], and can be used to mine patterns starting with
edges in [$k+1$, $j$]. Although the construction of minor partitions is on the
critical path of resolving a query, it does not bottleneck performance for two
reasons. First, queries often use small time windows, resulting in small minor
partitions. Second, we use GPUs to construct minor partitions, which takes
negligible time compared to the mining itself.

####  5.3.2. Multi-GPU Scheduling.

To reduce the work imbalance among multiple GPUs, Everest runtime dynamically
schedules work on multiple GPUs. This mechanism is only enabled for major
partitions as minor partitions only use a small amount of time. Each major
partition is divided into 16 sub-partitions and placed into the task queue.
Each GPU gets a range of edges to mine from its task queue. In this scheme, an
idle GPU inspects the work queues of other busy GPUs, and identifies the queue
with the highest amount of outstanding work. Once one is identified, the idle
GPU steals work from the busy GPU at a sub-partition granularity. This
mechanism continues until all GPU work queues are drained.

###  5.4. Support for Additional Constraints

####  5.4.1. Vertex/Edge Labels.

Everest code generator generates functions that examine vertex and edge labels
based on the user-defined query. Whenever a new vertex/edge is matched, the
generated functions are used to check their validity.

####  5.4.2. Fine-Grained Temporal Constraints.

The fine-grained temporal constraints impose unique conditions over each level
of the search tree. The time constraint is computed after an edge is matched
and recovered after a backtrack through re-computation.

####  5.4.3. Temporal Anti Edges.

During search tree expansion, temporal anti-edges are expanded in a similar
fashion as a normal edge. In contrast to a motif edge, a presence/match of an
anti-edge results in the termination of a tree branch. When an anti-edge is
specified with fine-grained temporal constraints, the code generator generates
an array whose $i^{th}$ entry contains the last real edge before a valid edge
$i$. This array will be referred in order to compute a correct time limit. The
work in the levels corresponding to anti-edges cannot be shared through intra-
warp work stealing or tail warp work redistribution. These levels do not
produce candidate edges that spawn sub-trees, which makes the two
optimizations based on STLP inapplicable.

##  6\. Evaluation methodology

Input Temporal Graphs.

Graph | #Vertices | #Temporal | # Static | Time span
---|---|---|---|---
|  | Edges | Undirected Edges | (years)
wikitalk (wi) (Leskovec and Krevl, 2014) | 1,140,149 | 7,833,140 | 2,787,968 | 6.24
stackoverflow (so) (Leskovec and Krevl, 2014) | 2,601,977 | 63,497,050 | 34,875,685 | 7.6
reddit-reply (re) (Liu et al., 2018) | 8,901,033 | 646,044,687 | 435,290,421 | 10.1
ethereum (eth) (Kondor et al., 2021) | 66,323,478 | 628,810,973 | 186,064,655 | 3.58
Table 1. Temporal graph datasets used for evaluation.

To evaluate the performance of Everest, we use four real-world temporal graphs
as shown in Table 1. The chosen datasets are among the largest found in the
public domain, exhibiting diversity in terms of their sizes, connectivity, and
granularity of temporal interactions. wiki-talk represents Talk page editing
activities among Wikipedia users. stackoverflow includes interactions between
users on Stack Overflow. temporal-reddit-reply encompasses reddit replies.
ethereum is a transaction network extracted from Ethereum. Given that graphs
are non-attributed, we attach random node and edge features.

User-Defined Queries.

Figure 10. Temporal motifs used for evaluation.

We select 13 distinct motifs from prior works (Mackey et al., 2018; Sarpe and
Vandin, 2021b; Kosyfaki et al., 2018) with three to five edges in size, as
depicted in Fig. 10. We only use the pattern and edge order of motifs from
(Kosyfaki et al., 2018), ignoring flow-based matching rules. This set of
motifs enables a comprehensive evaluation on our system’s performance. Since
the difficulty of mining specific motif patterns varies across different
target graphs, we employ distinct time windows for each graph due to limited
time for experiments. Regardless of additional constraints, we set use
$\delta=1$ day for wiki-talk and stackoverflow, $\delta=10$ hours for
temporal-reddit-reply and $\delta=1$ hour for ethereum. We use wiki-talk and
motif M6 for all profiling activities.

Hardware Platform Configuration. We run CPU baselines on a dual-socket server
with two Intel Xeon Platinum 8380 processors, each with 40 physical cores (80
SMT threads) and 8 memory channels. The main memory capacity is 1TB. We use up
to four NVIDIA A40 GPUs to evaluate our design, each with 48GB GDDR6 memory.
We use Nsight Compute to collect profiling results.

##  7\. Evaluation Results

Effectiveness of Everest Optimizations.

Figure 11. Performance improvements ($\times$) of Everest with different
optimizations compared to the GPU baseline (§3.2).

Fig. 11 shows the improvements of Everest performance with various
combinations of optimizations enabled, normalized to the GPU baseline
discussed in §3.2. The figure shows that all proposed optimizations (last
column a of the heatmap) improve the performance by 3.7$\times$–60$\times$
(19$\times$), on average for different input graphs. These results are based
on single-GPU experiments. These significant performance improvements are
attributed to improved per-thread algorithmic efficiency, reduced memory
footprint, and intelligent load balancing techniques employed in Everest.
Everest system design hides all the implementation details of sophisticated
optimizations from the programmer; the user is only expected to set up a query
of interest and simple runtime parameters (Fig. 5).

The figure further shows that caching candidate edges (column c) and
generating query-specific mining plan (column g) improves the performance of
the baseline GPU by 1.2$\times$–4.8$\times$, on average. These optimizations
improve the per-thread algorithmic work performed for mining each motif, i.e.,
by reducing the number of costly binary search and control flow operations
that depend on dynamic runtime information. Adding intra-warp work stealing
(column wso) further improves performance by 4$\times$–10$\times$. This
mechanism balances work distribution among multiple threads in the same warp
by the proposed employing sub-tree-level parallelism. Another work balancing
mechanism, i.e., tail warp work redistribution (column two) shows a more
pronounced effect on performance with an uplift of 3.1$\times$–42.9$\times$.
This optimization redistributes work from large search trees that run for the
highest amount of time. A few long-running warps under-utilize GPU hardware
resources as most other warps remain idle. Employing tail warp work
redistribution enables Everest to exploit full potential of the GPU hardware
resources, resulting in a significant performance uplift. These results also
emphasize a heavy work imbalance while running this workload, underscoring the
significance of our optimizations.

By comparing column g and two in M2, M8, and M10, note that applying tail warp
work redistribution occasionally slows the execution down marginally. This is
because they do not trigger this optimization due to short tail warps, and
only pay for the overhead of signal monitoring as a result. More frequent
slowdowns are observed when this optimization is applied after the application
of intra-warp work stealing (columns wso and a). This is because intra-warp
work stealing can shorten long tail warps, making tail warp work
redistribution less likely to happen. This small overhead varies for different
inputs due to the different micro-architecture resource requirements. Such
minor slowdowns do not dim the overall effectiveness of tail warp work
redistribution, as the speedups in the most-common highly-skewed cases
necessitate its existence.

Interestingly, the effectiveness of Everest optimizations can be vastly
different for mining different motifs from graphs. Take an example of the
largest ethereum input graph for example (row eth in different heatmaps). The
performance improvement brought by Everest ranges from 1.2$\times$ (M9) to
1022.1$\times$ (M13). Mining M4 achieves high efficiency due to load balancing
mechanisms, while M5 takes more advantage over the GPU-friendly
implementation. Overall, the motifs with more edges are more likely to induce
load imbalance and emphasize the importance of load balancing mechanisms, and
Everest consistently delivers performance improvements.

Detailed Performance Analysis.

Figure 12. Detailed performance analysis for a representative mining of M6 on
wiki-talk, relative to the GPU baseline.

Fig. 12 compares detailed performance metrics outputted by the GPU profiler
for 1) GPU baseline, 2) thread-local optimizations, and 3) all optimizations
that also include load balancing. The thread-local optimizations reduce the
total number of executed instructions by 64%. This further verifies the
reduction in costly binary search operations. On the other hand, load-
balancing mechanisms improve resource utilization on GPUs at all levels. These
increase the number of active threads per warp by 8.9$\times$ and improve
occupancy and warps per SM by 3.3$\times$. As a result, the compute throughput
and memory throughput are improved by 6.0$\times$ and 7.8$\times$. Although
the load balancing at runtime uses GPU instructions, the final effect of this
optimization reduces the number of execution instructions overall. In
particular, Everest only executes 11.7% of the instructions compared to the
baseline. This is because GPU follows Single Instructions Multiple Thread
(SIMT) execution model, where one instruction is issued for multiple threads
in a warp. As the number of active threads in a warp increases as a result of
load balancing, more threads share the same instruction, reducing the total
instruction count.

Comparison with a CPU Baseline.

| stackoverflow | reddit-reply | ethereum
---|---|---|---
Impl. | M5 | M6 | M7 | M5 | M6 | M7 | M5 | M6 | M7
CPU BL | 7.4 | 12.6 | 6.6 | 1247.9 | ¿10 hr | 2895.5 | 929.6 | ¿1 day | 16802.3
GPU BL | 1.0 | 2.1 | 0.9 | 2920.0 | 7952.1 | 474.6 | 300.6 | 67099.1 | 5273.1
Everest | 0.2 | 0.5 | 0.3 | 17.2 | 510.2 | 148.8 | 2.2 | 1717.1 | 726.7
Impl. | M8 | M11 | M12 | M8 | M11 | M12 | M8 | M11 | M12
CPU BL | 9.3 | 8.6 | 8.7 | 6031.1 | 3881.8 | 13493.0 | ¿10 hr | 33024.6 | 32812.6
GPU BL | 2.2 | 1.7 | 1.7 | 3704.8 | 3105.2 | 3118.6 | 7856.5 | 11921.2 | 12843.8
Everest | 0.4 | 0.4 | 0.4 | 117.6 | 64.0 | 90.0 | 665.6 | 38.6 | 45.2
Table 2. Execution time comparison (sec). GPU BL: GPU Baseline; CPU BL: CPU
Baseline based on Mackey et al. (Mackey et al., 2018).

Next, we compare the runtime of long-running motifs on the three large input
graphs (due to space limitation) for a baseline CPU and GPU baselines (based
on Mackey et al. (Mackey et al., 2018)), and Everest. The CPU baseline uses an
in-house parallel version of the open-source implementation of Mackey et al.’s
algorithm with 64 threads. Table 2 compares the absolute mining time in
seconds for three baselines. Everest outperforms the state-of-the-art CPU
baseline by 62.1$\times$, on average. This table shows that merely
transforming CPU code into GPU code is not enough as the baseline CPU can
outperform GPU in some cases (e.g., the CPU baseline outperforms the GPU
baseline by 2.3$\times$ when mining M5 on reddit-reply). This is especially
true for irregular workloads like graph mining that suffer from long memory
latency, frequent thread divergence, and load imbalance. Table 2 emphasizes
the Everest optimization effort that significantly improves workload
performance. For example, Everest can mine M6 in less than 30 minutes, versus
¿18 hours for a GPU baseline.

Scaling with Multiple GPUs.

Figure 13. Effectiveness of multi-GPU support. re-M6 means mining M6 on
reddit-reply. Other experiments follow the same naming convention.

To study the performance scaling with multiple GPUs, we compare the
performance of Everest for different number of GPUs that mine M5-M8 in reddit
and ethereum. Fig. 13 shows that the performance of Everest scales well with
multiple GPUs for most workloads. The speedup numbers can sometimes surpass
the number of GPUs due to the side effect of partitioning the edge list. This
is because it is cheaper to generate candidate edge lists using a partition
than using the whole graph as there are fewer visible neighbors to search for
a given vertex. Neglecting this effect, Everest scales linearly with the
number of GPUs for motifs M6 \- M8 on both graphs. One exception to this trend
is mining M5 on the ethereum graph, where the proposed work partitioning
scheme results in a disproportionately high amount of work assigned to one of
the GPUs due to the large population of motif matches in one of the
partitions. Furthermore, this workload takes only 2.2s (Table 2) to run on a
single-GPU, leaving very little work for a multi-GPU system to scale.

We compare Everest with two additional implementations to showcase the
benefits of multi-GPU optimization strategies. If we statically assign each
major partition to a GPU without using our dynamic scheduling mechanism, the
system’s performance stops scaling beyond 2$\times$, showcasing the
effectiveness of the proposed dynamic scheduling. Without partitioning graphs,
graphs have to be replicated on multiple GPUs, preventing them from processing
large graphs. GPUs can oversubscribe GPU memory via Unified Virtual Memory
(UVM), however, it only delivers $<1$% performance compared to a single GPU
due to the overhead of demand paging (NVB, 2022b). This shows the
effectiveness of proposed major/minor partitions.

Incorporating Additional Constraints.

| wiki-talk | stackoverflow | reddit-reply | ethereum
---|---|---|---|---
Cons. | matches | time | matches | time | matches | time | matches | time
N | 1.5e5 | 20 | 5.0e5 | 215 | 7.4e8 | 13868 | 6.4e9 | 2348
V | 8.8e3 | 8 | 3.1e4 | 50 | 3.2e7 | 1620 | 3.4e5 | 367
V+T | 2.0e3 | 6 | 1.4e4 | 36 | 1.7e7 | 916 | 9.2e4 | 198
V+T+A | 1.5e3 | 7 | 1.2e4 | 44 | 6.3e6 | 1076 | 8.7e4 | 254
Table 3. Effect of incorporating additional mining constraints on the number
of matches and execution time (in milliseconds) for 4-cycle. N: No
constraints; V: vertex labels; T: fine-grained temporal constraints; A: anti-
edge, additive.

Table 3 demonstrates the effects of applying vertex labels, fine-grained
temporal constraints, and anti-edges to mine temporal 4-cycles. After applied
all the constraints, the query is similar to the one shown in Fig. 5. As the
labels are randomly generated, we only conduct experiments for vertex labeling
without loss of generality. Both vertex labels and additional temporal
constraints reduce the number of valid matches and execution time by orders of
magnitude. Anti-edge constraints, on the other hand, results in a reduced
matches but increased execution time due to overhead in verifying this
constraint.

Comparison with Static Graph Mining Algorithms. One valid way to mine temporal
motifs is to first mine static motifs, and then resolve temporal constraints
(Paranjape et al., 2017). This however, often leads to significantly more
amount of algorithmic work as many valid static motifs do not follow temporal
constraints. Table 4 presents the ratio of the number of static to temporal
motifs matched, which clearly shows that static mining algorithms perform
large amounts of unnecessary work. When multiple temporal motifs map to the
same static motif, we present the ratio with the lowest motif ID. This is the
reason to base Everest on Mackey et al.’s algorithm that resolves both
structural and temporal constraints together.

##  8\. Related Works

Software Frameworks for Temporal Motif Mining. Several software frameworks are
proposed for temporal motif mining, as discussed in §2.2. Most of them aim at
finding $\delta$-window temporal motifs. Algorithms proposed in (Paranjape et
al., 2017; Mackey et al., 2018; Kumar and Calders, 2018) target exactly
matching motifs from graphs, while the ones from (Wang et al., 2020; Liu et
al., 2018; Sarpe and Vandin, 2021b) approximately mining motifs by sampling a
subset of edges to achieve better scalability. A few other works (Kovanen et
al., 2011; Pashanasangi and Seshadhri, 2021) adopt a more general problem
definition that considers the timestamp difference between consecutive edges.
All of them are CPU-based solutions that focus on a specific temporal motif
setting. In contrast, Everest is a high-performance GPU-based system that can
process a wide range of temporal motifs via queries.

Static (Temporal) Motif | wiki-talk | stackoverflow | reddit-reply | ethereum
---|---|---|---|---
3-path (M1) | 9.6e6 | 5.7e8 | 9.8e5 | 2.7e3
tailed-tri (M3) | 1.1e5 | 7.1e5 | 5.6e4 | 1.5e4
fourcycle (M4) | 1.6e4 | 9.2e4 | 1.3e4 | 1.7e2
static M8 (M8) | 1.4e8 | 1.5e8 | 9.5e6 | 2.2e6
diamonds (M10) | 1.9e4 | 9.6e5 | 1.3e3 | 1.8
static M13 (M13) | 4.8e10 | 1.3e7 | ¿9.5e11 | 3.7e6
Table 4. Ratio of the number of matches generated by static graph mining
algorithms versus temporal motif mining.

Software Frameworks for Static Graph Mining. Multiple systems are proposed for
static graph pattern mining (Teixeira et al., 2015; Jamshidi et al., 2020;
Jamshidi and Vora, 2021; Mawhirter et al., 2019; Mawhirter and Wu, 2019; Shi
et al., 2020; Gao et al., 2022; Sarpe and Vandin, 2021a; Porter et al., 2022;
Wei and Jiang, 2022; Chen and Arvind, 2022). The problem of temporal motif
mining adds temporal constraints to the static mining problem, which none of
these prior systems can support. CPU execution is more tolerant to load
imbalance and complex control flow due to fewer cores and sophisticated branch
prediction hardware. While (Chen and Arvind, 2022) performs mining code
generation on GPUs, temporal motif mining imposes additional challenges.
Utilizing temporal motifs increases programs’ control flow complexity and per-
thread resource usage are unfavorable for GPU execution and require a
carefully designed load-balancing mechanism. Everest is the first system that
generates high-performance GPU code for temporal motif mining.

##  9\. Conclusion

This paper presented Everest—an optimized system for mapping the workload of
temporal motif mining onto the GPU architecture. Our study showed that
existing software for executing this workload yields poor performance on a GPU
due to long-latency memory instructions, frequent thread divergence
operations, and heavy load imbalance. Everest presented domain-specific
optimizations to address these inefficiencies. In particular, we showed how
Everest generates per-thread code using motif structure and temporal
constraints to cache key metadata information to reduce costly memory and
thread divergent operations. Furthermore, we presented Everest runtime
primitives that enable load balancing to improve the GPU hardware utilization.
For large input graphs that do not fit in the GPU memory, Everest employs low-
cost edge list partitioning that prevents inter-GPU communication. Everest is
easy to use, where a targeted user only needs to write an input query, and the
heavy lifting of code generation is automatic by the system. We showed that
compared to a baseline GPU implementation, Everest uplifts the performance of
19$\times$, on average. While Everest is designed for a specific workload, its
design philosophy will inspire future research on efficiently mapping data-
intensive irregular workloads onto GPU hardware.

###### Acknowledgements.

This research is based upon work supported by the Office of the Director of
National Intelligence (ODNI), Intelligence Advanced Research Projects Activity
(IARPA), through the Advanced Graphical Intelligence Logical Computing
Environment (AGILE) research program, under Army Research Office (ARO)
contract number W911NF22C0085. The views and conclusions contained herein are
those of the authors and should not be interpreted as necessarily representing
the official policies or endorsements, either expressed or implied, of the
ODNI, IARPA, ARO, or the U.S. Government. This work was also supported by the
United States-Israel BSF grant number 2020135.

##  Appendix A Theoretical Performance Analysis for Load Balancing Mechanisms

Intra-warp Work Stealing: Each trigger of this optimization uses around 25
fast warp-level primitives (NVB, 2022a) for work stealing. Because these warp-
level primitives use GPU registers and do not introduce complicated control
flow, their aggregated cost is far less than a normal search iteration’s cost.
The warp-level speedup of this optimization can be roughly modeled as follows:

$\frac{\mathcal{I}_{\text{imb}}}{\mathcal{I}_{\text{opt}}+k\epsilon}=\frac{\mathcal{I}_{\text{imb}}}{\mathcal{I}_{\text{opt}}}\frac{\mathcal{I}_{\text{opt}}}{\mathcal{I}_{\text{opt}}+k\epsilon}=\frac{32}{t_{\text{imb}}}\frac{\mathcal{I}_{\text{opt}}}{\mathcal{I}_{\text{opt}}+k\epsilon}=\frac{32}{t_{\text{imb}}\left(1+\frac{k\epsilon}{\mathcal{I}_{\text{opt}}}\right)}$

$\mathcal{I}_{\text{imb}}$ and $\mathcal{I}_{\text{opt}}$ are the number of
search iterations used by the imbalanced baseline and optimized code.
$k<\mathcal{I}_{\text{opt}}$ is the times this mechanism is triggered and
$\epsilon<1$ is the work-stealing overhead relative to a search iteration.
$t_{\text{imb}}$ is the number of active threads within a warp in the
imbalanced baseline.

We observe that $t_{\text{imb}}$ is usually much smaller than warp width 32
due to intra-warp work imbalance. Each trigger of this optimization steals
multiple sub-trees, resulting in a smaller $k$. Our warp-primitive-based
efficient implementation results in a smaller $\epsilon$. In practice, we
observe
$t_{\text{imb}}\left(1+\frac{k\epsilon}{\mathcal{I}_{\text{opt}}}\right)<32$,
and a meaningful speedup on average across warps. In theory, when the work
within a warp is naturally balanced, this optimization can slightly slow down
the execution by a factor of $\frac{k\epsilon}{\mathcal{I}_{\text{opt}}}$.
However, as most of the large graphs are power-law graphs, it is unlikely to
happen in practice. A trivial exception is all threads in a warp do not have
much work, so we enable this optimization after 20 iterations to filter out
these warps. Another interesting fact is that the speedup is correlated to
$\mathcal{I}_{\text{opt}}$. In other words, the more work is assigned to a
warp, the more speedup it can enjoy from this optimization. This observation
helps explain the interaction between this optimization and tail warp work
redistribution mechanism.

For simplicity, we ignore the negligible overhead of detecting idle threads
within warps, which additionally uses a warp vote and a branch in each search
iteration. Also, we assume that all threads can be busy after this
optimization is enabled. This is the usual case except near the end of a
warp’s execution, where there is not enough work for 32 threads to do.

The above model explains the benefit of this optimization at the warp level,
while it is overly complicated to infer the benefit for the entire kernel from
this model. Factors like hardware schedulers’ algorithms and work distribution
are either not released to the public or are dependent on the user’s input.

Tail Warp Work Redistribution: For simplicity, we assume that the imbalanced
work distribution causes one tail warp keeps running while all others finish.
Our analysis can be generalized to cases with multiple tail warps. We first
model the negative impact of tail warps. Let $0<\mathcal{L}_{\text{imb}}<1$
represent the fraction of total execution time consumed by a tail warp. Note
that $\mathcal{L}_{\text{imb}}$ can be significant even if the tail warp only
processes a tiny fraction of all work. We use $\phi$ to represent the total
number of CUDA cores on a GPU divided by its warp width, and $\phi=336$ on
NVIDIA A40. Assume that one warp near the end of the execution handles 1% of
all work, which is reasonable based on our profiling result as shown in Figure
3(a). In such case, $\mathcal{L}_{\text{imb}}=\frac{1}{(99/336)+1}\approx
77\%$, and GPU is severely underutilized in most of its execution time. Such,
or even worse, scenario frequently happens in practice and is hard to foresee
as it depends on graphs, motifs, and constraints.

Then, we model the benefit of our tail warp work redistribution optimization.
Let $c$ represent the cost to abort execution, refine thread context, and
redistribute the work via kernel launch, which is around several microseconds.
We use $k$ to represent the times this optimization is triggered, and
$T_{\text{imb}}$ to model the total execution time. We use $o\lessapprox 1$ to
represent the small aggregated overhead of monitoring the signaling variable.
The overhead is designed to be small, as the signaling mechanism only involves
a few branches per iteration and one global memory access every 64 iterations.
Note that the overhead also weakly depends on mining queries. Different
queries stress micro-architecture resources differently, resulting in
different degrees of resource competition between normal execution and signal
monitoring. The speedup introduced by this optimization can be roughly modeled
as follows:

$\frac{T_{\text{imb}}}{(1-\mathcal{L}_{\text{imb}}+\frac{\mathcal{L}_{\text{imb}}}{\phi})T_{\text{imb}}+kc}\cdot
o=\frac{o}{(1-\frac{\phi-1}{\phi}\mathcal{L}_{\text{imb}})+\frac{kc}{T_{\text{imb}}}}$

Usually, a couple of times work redistribution is enough, so
$\frac{kc}{T_{\text{imb}}}$ is small enough to ignore. The speedup is further
approximated by

$\frac{o}{1-\frac{\phi-1}{\phi}\mathcal{L}_{\text{imb}}}=\frac{o}{1-\Phi\mathcal{L}_{\text{imb}}}\leq
o\phi\text{, where }\Phi=\frac{\phi-1}{\phi}$

When the work distribution is highly skewed, $\mathcal{L}_{\text{imb}}$ is
large and this optimization can bring significant speedup (up to $o\phi$). On
the other hand, when $\mathcal{L}_{\text{imb}}$ is small, the overhead becomes
noticeable. When the tail warp’s execution time is less than 100ms, this
optimization does not take effect, and workload slows down by a factor of $o$.

Interaction between Optimizations: Applying intra-warp work stealing can
decrease $\mathcal{L}_{\text{imb}}$. Tail warps are the warps that are
assigned with large amounts of work. As demonstrated by the performance model,
such kinds of warps are privileged with regard to intra-warp work stealing.
Plus, many warps with little work do not trigger intra-warp work stealing due
to the threshold. There is a net difference between the speedup gained from
intra-warp work stealing for tail warps and normal warps. If we use $\theta>1$
to represent the ratio between these two values, then intra-warp work stealing
decreases $\mathcal{L}_{\text{imb}}$ to

$\mathcal{L}_{\text{imb}}^{\prime}=\frac{\frac{\mathcal{L}_{\text{imb}}}{\theta}}{1-\mathcal{L}_{\text{imb}}+\frac{\mathcal{L}_{\text{imb}}}{\theta}}=\frac{1}{\theta(1-\mathcal{L}_{\text{imb}})+\mathcal{L}_{\text{imb}}}\cdot\mathcal{L}_{\text{imb}}<\mathcal{L}_{\text{imb}}$

Effectively, intra-warp work stealing eases the tail warps problem.

As a result, applying tail warp work redistribution upon intra-warp work
stealing results in a smaller speedup number compared to the case without
intra-warp work stealing results. When the work distribution is only slightly
skewed, intra-warp work stealing is good enough to tame the tail warps
problem. In such cases, the tail warp’s execution time is less than 100ms, and
tail warp work redistribution exhibits a factor of $o$ slowdown.

##  Appendix B Qualitative Comparison with Closely Related Works

Next, we discuss the unique features of Everest system design compared to
closely related prior works (Aberger et al., 2017; Mawhirter et al., 2019;
Mawhirter and Wu, 2019; Shi et al., 2020; Chen and Arvind, 2022; Chen et al.,
2020; Wei and Jiang, 2022).

Code Generation Strategy. Many prior graph mining systems adopt the idea of
code generation (Aberger et al., 2017; Mawhirter et al., 2019; Mawhirter and
Wu, 2019; Shi et al., 2020; Chen and Arvind, 2022), for CPUs or GPUs.
Nevertheless, none of them takes temporal constraints into consideration, and
can only generate code to mine static patterns. While CPU-based code
generation has been done by (Aberger et al., 2017; Mawhirter et al., 2019;
Mawhirter and Wu, 2019; Shi et al., 2020), CPU execution is more tolerant to
load imbalance and complex control flow due to fewer cores and sophisticated
branch prediction hardware. Because of the complexity of GPU programming, only
(Chen and Arvind, 2022) has done GPU code generation for static pattern
mining. However, its strategy falls short in the temporal settings, because
mining temporal motifs on GPU poses unique challenges compared to mining
static motifs on GPU. Utilizing temporal constraints increases programs’
control flow complexity and per-thread resource usage, which are unfavorable
for GPU execution and require a carefully designed load-balancing mechanism.
The lack of parallelizable operations, like vertex set operations in (Chen and
Arvind, 2022), makes it infeasible to utilize warps via SIMD-style
programming. This requires the code generator to generate highly efficient
thread-granularity load balancing code that is precisely based on resource
allocation status. Therefore, unlike (Chen and Arvind, 2022), Everest’s code
generator focuses on reducing control flow complexity, minimizing resource
usage, and is coupled with load-balancing mechanisms. These observations are
shown to be the key to good performance for temporal motif mining, which are
not addressed in (Chen and Arvind, 2022)’s code generator for GPUs.

Load Balancing Techniques. While GPU-based graph mining systems can achieve a
balanced work distribution using BFS search order (Chen et al., 2020), it is
at the expense of excessive memory usage, which is not acceptable for large
graphs on GPUs. Many high-performance GPU-based graph mining systems thus
switch to DFS search order (Chen and Arvind, 2022; Wei and Jiang, 2022), and
propose their load balancing optimizations for skewed work distribution. These
methods differ significantly from the ones in Everest. G2Miner (Chen and
Arvind, 2022) only has one load balancing mechanism for single GPU execution,
which neither uses work stealing nor is applicable to all patterns. STMatch
(Wei and Jiang, 2022) does not redistribute work for tail warps and its intra-
block/grid work stealing mechanisms are at the expense of maintaining
complicated data structures in memory. Both (Chen and Arvind, 2022; Wei and
Jiang, 2022) use SIMD vertex set operation primitives to fully utilize warps.
These methods are not applicable in temporal settings, due to the differences
in workload characteristics between DFS-based temporal motif mining and static
pattern mining. First, search trees in temporal settings are expanded by
mapping new edges and do not require vertex set operations or anything
similar, thus warps cannot be efficiently utilized via SIMD-style programming.
Second, the time constraints on motifs shorten most of the search trees, make
warp-granularity execution (Wei and Jiang, 2022; Chen and Arvind, 2022)
inefficient, and call for thread-granularity load balancing mechanisms like
the ones in Everest. Third, the neighborhood information depends on search
tree roots due to temporal constraints, which vagues the remaining work in
search trees and forbids high-overhead work stealing mechanisms that rely on
accurate work representations (Wei and Jiang, 2022). As a result, Everest
proposes two novel load balancing solutions, intra-warp load balancing and
tail-warp work redistribution, without maintaining expensive data structures
or defining new SIMD operation primitives. Intra-warp load balancing can do
work stealing at thread granularity only using registers, in contrast to the
intra-block solution in (Wei and Jiang, 2022) that only works at warp
granularity and has to use shared memory. Tail-warp work redistribution relies
only on a signaling variable to redistribute work among the whole GPU, while
the intra-grid solution in (Wei and Jiang, 2022) maintains a complicated data
structure in global memory for remaining work and requires busy waiting on
locks for work stealing.

Memoization Technique. While, on the surface, the caching mechanisms of
Everest and STMatch (Wei and Jiang, 2022) sound similar, the designs are
fundamentally different. Everest caches two pointers on the edge list in
registers, without using shared memory. On the other hand, STMatch (Wei and
Jiang, 2022) only manages to cache the iterators and size of candidate arrays
in shared memory, and still keep the content of candidate arrays in global
memory (DRAM) due to its size. Its candidate arrays residing in global memory
store its results for expensive vertex set operations, which are absent in the
context of temporal motif mining. As a result, Everest can do caching in the
fastest registers instead of using slower shared memory or global memory, like
the solution in (Wei and Jiang, 2022).

##  Appendix C Impact of $\delta$

Figure 14 illustrates how changing $\delta$ influences the execution time and
speedup of Everest over the baseline, mining two representative motifs on
stackoverflow and reddit-reply as a case study. In practice, the execution
time grows polynomially (close to linearly) with the time window $\delta$,
which is better than the expectation from the worst case complexity analysis
in Section 3.1 of the manuscript. While Everest always outperforms the
baseline significantly, the speedup brought by Everest varies for different
$\delta$. This is because $\delta$ determines the valid neighbors of vertices
within search trees, thus changing the control flow behaviors and work
distribution.

Figure 14.  Influence of $\delta$ on execution time and speedup over the
baseline . so-M8 means mining M8 on stackoverflow. Other experiments follow
the same naming convention.

##  Appendix D Impact of Hyper-parameters

Choice of Intra-Warp Work Stealing Threshold. By default, intra-warp work
stealing is enabled after 20 iterations to minimize the warp overhead that
cannot benefit from load-balancing mechanisms. Such overhead can cause
noticeable slowdowns when there is no severe work imbalance. As shown in
Figure 15, mining certain motifs on stackoverflow graph without using a
threshold can consume 25% more time than our default setting (the upper cap of
so-0). This 20-iteration threshold improves the speedup numbers in the cases
where intra-warp work imbalance is not severe at the expense of a few percent
slowdown in the highly-skewed cases, which benefit greatly from this
optimization. Thus, Everest can more uniformly deliver high performance for
all kinds of users’ inputs. We use 20 iterations as the threshold, because we
do not observe additional benefit using a larger value like 40, which is
demonstrated in Figure 15.

Figure 15.  Average execution time of the cases with different intra-warp work
stealing threshold over the cases using default 20 iterations, all normalized
to the cases with default settings. The error bars show the maximum and
minimum execution time mining different motifs in graphs.

Figure 16.  Average execution time of the cases with different tail warp work
redistribution signal checking intervals over the cases using default 1024
iterations, all normalized to the cases with default settings. The error bars
show the maximum and minimum execution time mining different motifs in graphs.

Figure 17.  Average execution time of the cases with different tail warp work
redistribution timeout over the cases using default 100 ms, all normalized to
the cases with default settings.

Choice of Signal Checking Interval in Tail Warp Work Redistribution. To detect
abortion signals, warps have to periodically check a signaling variable in
global memory. By default, Everest uses 1024 iterations as the signal checking
interval to amortize the memory accesses costs. We experiment with different
intervals for signal checking, as demonstrated in Figure 16. If the signal
checking intervals are set small (64 iterations), the system suffers from the
overhead of frequent global memory accesses. It does not slow down mining
certain motifs due to their short search tree (especially the case for
stackoverflow) which results in fewer signal checking. However, on average, a
small interval slows down the system by a few times for most of the graphs and
is close to $100\times$ in the worst case. Our choice, 1024 iterations, is a
sweet point as no meaningful speedup is observed when we further increase this
value.

Choice of Timeout in Tail Warp Work Redistribution. We include a timeout value
for this optimization to avoid too frequent recursive calls of tail warp work
redistribution. After receiving the abortion signals, warps will abort their
execution after the timeout. As shown in Figure 17, the overall performance of
the system is not sensitive to this hyper-parameter. The system performance
will be roughly the same as long as we use reasonable values within the range
shown in the figure.

## References

  * (1)
  * NVB (2022a) 2022a.  https://developer.nvidia.com/blog/using-cuda-warp-level-primitives/
  * NVB (2022b) 2022b.  Unified Memory for CUDA Beginners.  https://developer.nvidia.com/blog/unified-memory-cuda-beginners/
  * Aberger et al. (2017) Christopher R. Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Olukotun, and Christopher Ré. 2017.  EmptyHeaded: A Relational Engine for Graph Processing.  _ACM Trans. Database Syst._ 42, 4, Article 20 (oct 2017), 44 pages.  https://doi.org/10.1145/3129246
  * Alon (2007) Uri Alon. 2007.  Network motifs: theory and experimental approaches.  _Nature Reviews Genetics_ 8, 6 (2007), 450–461.
  * Bouritsas et al. (2022) Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. 2022.  Improving graph neural network expressivity via subgraph isomorphism counting.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2022).
  * Chamberlain et al. (2022) Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M Bronstein, and Max Hansmire. 2022.  Graph Neural Networks for Link Prediction with Subgraph Sketching.  _arXiv preprint arXiv:2209.15486_ (2022).
  * Chen and Arvind (2022) Xuhao Chen and Arvind. 2022.  Efficient and Scalable Graph Pattern Mining on GPUs. In _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_. USENIX Association, Carlsbad, CA, 857–877.  https://www.usenix.org/conference/osdi22/presentation/chen
  * Chen et al. (2020) Xuhao Chen, Roshan Dathathri, Gurbinder Gill, and Keshav Pingali. 2020.  Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU.  _Proc. VLDB Endow._ 13, 8 (April 2020), 1190–1205.  https://doi.org/10.14778/3389133.3389137
  * Gao et al. (2022) Z. Gao, C. Cheng, Y. Yu, L. Cao, C. Huang, and J. Dong. 2022.  Scalable Motif Counting for Large-scale Temporal Graphs. In _2022 IEEE 38th International Conference on Data Engineering (ICDE)_. IEEE Computer Society, Los Alamitos, CA, USA, 2656–2668.  https://doi.org/10.1109/ICDE53745.2022.00244
  * Glasser and Lindauer (2013) Joshua Glasser and Brian Lindauer. 2013.  Bridging the gap: A pragmatic approach to generating insider threat data. In _2013 IEEE Security and Privacy Workshops_. IEEE, 98–104.
  * Hajdu and Krész (2020) László Hajdu and Miklós Krész. 2020.  Temporal network analytics for fraud detection in the banking sector. In _ADBIS, TPDL and EDA 2020 Common Workshops and Doctoral Consortium_. Springer, 145–157.
  * Jamshidi et al. (2020) Kasra Jamshidi, Rakesh Mahadasa, and Keval Vora. 2020.  Peregrine: A Pattern-Aware Graph Mining System.  , Article 13 (2020), 16 pages.  https://doi.org/10.1145/3342195.3387548
  * Jamshidi and Vora (2021) Kasra Jamshidi and Keval Vora. 2021.  A Deeper Dive into Pattern-Aware Subgraph Exploration with PEREGRINE.  _SIGOPS Oper. Syst. Rev._ 55, 1 (June 2021), 1–10.  https://doi.org/10.1145/3469379.3469381
  * Kondor et al. (2021) Dániel Kondor, Nikola Bulatovic, József Stéger, István Csabai, and Gábor Vattay. 2021.  _Ethereum Transaction Network_.  https://doi.org/10.5281/zenodo.4543269 Data used in our upcoming paper: Kondor D, Bulatovic N, Stéger J, Csabai I, Vattay G (2021). The rich still get richer: Empirical comparison of preferential attachment via linking statistics in Bitcoin and Ethereum. Under review. https://arxiv.org/abs/2102.12064.
  * Kosyfaki et al. (2018) Chrysanthi Kosyfaki, Nikos Mamoulis, Evaggelia Pitoura, and Panayiotis Tsaparas. 2018.  Flow Motifs in Interaction Networks. In _International Conference on Extending Database Technology_.
  * Kovanen et al. (2011) Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. 2011.  Temporal motifs in time-dependent networks.  _Journal of Statistical Mechanics: Theory and Experiment_ 2011, 11 (2011), P11005.
  * Kovanen et al. (2013) Lauri Kovanen, Kimmo Kaski, János Kertész, and Jari Saramäki. 2013.  Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences.  _Proceedings of the National Academy of Sciences_ 110, 45 (2013), 18070–18075.
  * Kumar and Calders (2018) Rohit Kumar and Toon Calders. 2018.  2scent: An efficient algorithm to enumerate all simple temporal cycles.  _Proceedings of the VLDB Endowment_ 11, 11 (2018), 1441–1453.
  * Lahiri and Berger-Wolf (2007) Mayank Lahiri and Tanya Y. Berger-Wolf. 2007.  Structure Prediction in Temporal Networks using Frequent Subgraphs. In _2007 IEEE Symposium on Computational Intelligence and Data Mining_. 35–42.  https://doi.org/10.1109/CIDM.2007.368850
  * LaSalle and Karypis (2016) Dominique LaSalle and George Karypis. 2016.  A parallel hill-climbing refinement algorithm for graph partitioning. In _2016 45th International Conference on Parallel Processing (ICPP)_. IEEE, 236–241.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Liu et al. (2018) Paul Liu, Austin Benson, and Moses Charikar. 2018.  A sampling framework for counting temporal motifs.  _arXiv preprint arXiv:1810.00980_ (2018).
  * Mackey et al. (2018) Patrick Mackey, Katherine Porterfield, Erin Fitzhenry, Sutanay Choudhury, and George Chin. 2018.  A chronological edge-driven approach to temporal subgraph isomorphism. In _2018 IEEE international conference on big data (big data)_. IEEE, 3972–3979.
  * Mawhirter et al. (2019) D. Mawhirter, S. Reinehr, C. Holmes, T. Liu, , and B. Wu. 2019.  Graphzero: Breaking symmetry for efficient graph mining. In _arXiv preprint arXiv:1911.12877_.
  * Mawhirter and Wu (2019) Daniel Mawhirter and Bo Wu. 2019.  AutoMine: Harmonizing High-Level Abstraction and High Performance for Graph Mining.  (2019), 509–523.  https://doi.org/10.1145/3341301.3359633
  * Meydan et al. (2013) Cem Meydan, Hasan H Otu, and Osman Uğur Sezerman. 2013.  Prediction of peptides binding to MHC class I and II alleles by temporal motif mining. In _BMC bioinformatics_ , Vol. 14. Springer, 1–11.
  * Milo et al. (2002) Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002.  Network motifs: simple building blocks of complex networks.  _Science_ 298, 5594 (2002), 824–827.
  * Newman (2003) Mark EJ Newman. 2003.  The structure and function of complex networks.  _SIAM review_ 45, 2 (2003), 167–256.
  * Pan and Saramäki (2011) Raj Kumar Pan and Jari Saramäki. 2011.  Path lengths, correlations, and centrality in temporal networks.  _Physical Review E_ 84, 1 (2011), 016105.
  * Paranjape et al. (2017) Ashwin Paranjape, Austin R Benson, and Jure Leskovec. 2017.  Motifs in temporal networks. In _Proceedings of the tenth ACM international conference on web search and data mining_. 601–610.
  * Pashanasangi and Seshadhri (2021) Noujan Pashanasangi and C. Seshadhri. 2021.  Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_ (Virtual Event, Singapore) _(KDD ’21)_. Association for Computing Machinery, New York, NY, USA, 1319–1328.  https://doi.org/10.1145/3447548.3467374
  * Porter et al. (2022) Alexandra Porter, Baharan Mirzasoleiman, and Jure Leskovec. 2022.  Analytical Models for Motifs in Temporal Networks. In _Companion Proceedings of the Web Conference 2022_ (Virtual Event, Lyon, France) _(WWW ’22)_. Association for Computing Machinery, New York, NY, USA, 903–909.  https://doi.org/10.1145/3487553.3524669
  * Sarpe and Vandin (2021a) Ilie Sarpe and Fabio Vandin. 2021a.  OdeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_ (Virtual Event, Queensland, Australia) _(CIKM ’21)_. Association for Computing Machinery, New York, NY, USA, 1568–1577.  https://doi.org/10.1145/3459637.3482459
  * Sarpe and Vandin (2021b) Ilie Sarpe and Fabio Vandin. 2021b.  PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts. In _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_. SIAM, 145–153.
  * Shao et al. (2013) Huijuan Shao, Manish Marwah, and Naren Ramakrishnan. 2013.  A temporal motif mining approach to unsupervised energy disaggregation: Applications to residential and commercial buildings. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 27. 1327–1333.
  * Shen-Orr et al. (2002) Shai S Shen-Orr, Ron Milo, Shmoolik Mangan, and Uri Alon. 2002.  Network motifs in the transcriptional regulation network of Escherichia coli.  _Nature genetics_ 31, 1 (2002), 64–68.
  * Shi et al. (2020) T. Shi, M. Zhai, Y. Xu, and J. Zhai. 2020.  _GraphPi: High Performance Graph Pattern Matching through Effective Redundancy Elimination_.  Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis.
  * Teixeira et al. (2015) Carlos H. C. Teixeira, Alexandre J. Fonseca, Marco Serafini, Georgos Siganos, Mohammed J. Zaki, and Ashraf Aboulnaga. 2015.  Arabesque: A System for Distributed Graph Mining.  (2015), 425–440.  https://doi.org/10.1145/2815400.2815410
  * Wang et al. (2020) Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yuchen Li, and Kian-Lee Tan. 2020.  Efficient sampling algorithms for approximate temporal motif counting. In _Proceedings of the 29th ACM international conference on information & knowledge management_. 1505–1514.
  * Wei and Jiang (2022) Yihua Wei and Peng Jiang. 2022.  STMatch: Accelerating Graph Pattern Matching on GPU with Stack-Based Loop Optimizations. In _Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis_ (Dallas, Texas) _(SC ’22)_. IEEE Press, Article 53, 13 pages.