,

# Shared-Memory Parallel Maximal Clique Enumeration from Static and Dynamic
Graphs

Apurba Das  Iowa State University<EMAIL_ADDRESS>,  Seyed-Vahid Sanei-Mehri
Iowa State University<EMAIL_ADDRESS>and  Srikanta Tirthapura  Iowa State
University<EMAIL_ADDRESS>
###### Abstract.

Maximal Clique Enumeration (MCE) is a fundamental graph mining problem, and is
useful as a primitive in identifying dense structures in a graph. Due to the
high computational cost of MCE, parallel methods are imperative for dealing
with large graphs. We present shared-memory parallel algorithms for MCE, with
the following properties: (1) the parallel algorithms are provably work-
efficient relative to a state-of-the-art sequential algorithm (2) the
algorithms have a provably small parallel depth, showing they can scale to a
large number of processors, and (3) our implementations on a multicore machine
show good speedup and scaling behavior with increasing number of cores, and
are substantially faster than prior shared-memory parallel algorithms for MCE;
for instance, on certain input graphs, while prior works either ran out of
memory or did not complete in 5 hours, our implementation finished within a
minute using 32 cores. We also present work-efficient parallel algorithms for
maintaining the set of all maximal cliques in a dynamic graph that is changing
through the addition of edges.

##  1\. Introduction

We study Maximal Clique Enumeration (MCE) from a graph, which requires to
enumerate all cliques (complete subgraphs) in the graph that are maximal. A
clique $C$ in a graph $G=(V,E)$ is a (dense) subgraph such that every pair of
vertices in $C$ are directly connected by an edge. A clique $C$ is said to be
maximal when there is no clique $C^{\prime}$ such that $C$ is a proper
subgraph of $C^{\prime}$ (see Figure 1). Maximal cliques are perhaps the most
fundamental dense subgraphs, and MCE has been widely used in diverse research
areas, e.g. the works of Palla et al. (Palla et al., 2005) on discovering
protein groups by mining cliques in a protein-protein network, of Koichi et
al. (Koichi et al., 2014) on discovering chemical structures using MCE on a
graph derived from large-scale chemical databases, various problems on mining
biological data (Grindley et al., 1993; Hattori et al., 2003; Mohseni-Zadeh et
al., 2004; Chen and Crippen, 2005; Jonsson and Bates, 2006; Rokhlenko et al.,
2007; Zhang et al., 2008), overlapping community detection (Yuan et al.,
2017), location-based services on spatial databases (Zhang et al., 2019), and
inference in graphical models (Koller and Friedman, 2009). MCE is important in
static as well as dynamic networks, i.e. networks that change over time due to
the addition and deletion of vertices and edges. For example, Chateau et al.
(Chateau et al., 2011) use MCE in studying changes in the genetic
rearrangements of bacterial genomes, when new genomes are added to the
existing genome population. Maximal cliques are building blocks for computing
approximate common intervals of multiple genomes. Duan et al. (Duan et al.,
2012) use MCE on a dynamic graph to track highly interconnected communities in
a dynamic social network.

MCE is a computationally hard problem since it is harder than the maximum
clique problem, a classical NP-complete combinatorial problem that asks to
find a clique of the largest size in a graph. Note that maximal clique and
maximum clique are two related, but distinct notions. A maximum clique is also
a maximal clique, but a maximal clique need not be a maximum clique. The
computational cost of enumerating maximal cliques can be higher than the cost
of finding the maximum clique, since the output size (set of all maximal
cliques) can itself be very large. Moon and Moser (Moon and Moser, 1965)
showed that a graph on $n$ vertices can have as many as $3^{n/3}$ maximal
cliques, which is proved to be a tight bound. Real-world networks typically do
not have cliques of such high complexity and as a result, it is feasible to
enumerate maximal cliques from large graphs. The literature is rich on
sequential algorithms for MCE. Bron and Kerbosch (Bron and Kerbosch, 1973)
introduced a backtracking search method to enumerate maximal cliques. Tomita
et. al (Tomita et al., 2006) introduced the idea of “pivoting” in the
backtracking search, which led to a significant improvement in the runtime.
This has been followed up by further work such as due to Eppstein et al.
(Eppstein et al., 2010), who used a degeneracy-based vertex ordering on top of
the pivot selection strategy.

Sequential approaches to MCE can lead to high runtimes on large graphs. Based
on our experiments, a real-world network Orkut with approximately $3$ million
vertices, $117$ million edges requires approximately $8$ hours to enumerate
all maximal cliques using an efficient sequential algorithm due to Tomita et
al. (Tomita et al., 2006). Graphs that are larger and/or more complex cannot
be handled by sequential algorithms with a reasonable turnaround time, and the
high computational complexity of MCE calls for parallel methods.

|  |
---|---|---
(a) Input Graph $G$ |  (b) Non-Maximal Clique in $G$ |  (c) Maximal Clique in $G$
Figure 1. Maximal clique in a graph

In this work, we consider shared-memory parallel methods for MCE. In the
shared-memory model, the input graph can reside within globally shared memory,
and multiple threads can work in parallel on enumerating maximal cliques.
Shared-memory parallelism is of high interest today since machines with tens
to hundreds of cores and hundreds of Gigabytes of shared-memory are readily
available. The advantage of using shared-memory approach over a distributed
memory approach are: (1) Unlike distributed memory, it is not necessary to
divide the graph into subgraphs and communicate the subgraphs among
processors. In shared-memory, different threads can work concurrently on a
single shared copy of the graph (2) Sub-problems generated during MCE are
often highly imbalanced, and it is hard to predict which sub-problems are
small and which are large, while initially dividing the problem into sub-
problems. With a shared-memory method, it is possible to further subdivide
sub-problems and process them in parallel. With a distributed memory method,
handling such imbalances in sub-problem sizes requires greater coordination
and is more complex.

To show how imbalanced the sub-problems can be, in Figure 2, we show data for
two real-world networks As-Skitter and Wiki-Talk. These two networks have
millions of edges and tens of millions of maximal cliques (for statistics on
these networks, see Section 6). Consider a division of the MCE problem into
per-vertex sub-problems, where each sub-problem corresponds to the set of all
maximal cliques containing a single vertex in a network and suppose these sub-
problems were solved independently, while taking care to prune out search for
the same maximal clique multiple times. For As-Skitter, we observed that
$90\%$ of total runtime required for MCE is taken by only $0.022\%$ of the
sub-problems and less than $0.4\%$ of all sub-problems yield $90\%$ of all
maximal cliques. Even larger skew in sub-problem sizes is observed in the
Wiki-Talk graph. This data demonstrates that load balancing is a central issue
for parallel MCE.

|
---|---
(a) As-Skitter |  (b) Wiki-Talk

|
(c) As-Skitter |  (d) Wiki-Talk
Figure 2. Imbalanced in sizes of sub-problems for MCE, where each sub-problem
corresponds to the maximal cliques of a single vertex in the given graph. (a)
As-Skitter: $0.3\%$ of sub-problems form $90\%$ of total number of maximal
cliques. (b) Wiki-Talk: only $0.002\%$ of sub-problems yield $90\%$ of all
maximal cliques. (c) As-Skitter: $0.02\%$ of sub-problems take $90\%$ of total
runtime of MCE. (d) Wiki-Talk: only $0.004\%$ of sub-problems take $90\%$ of
total runtime of MCE

Prior works on parallel MCE have largely focused on distributed memory
algorithms (Wu et al., 2009; Schmidt et al., 2009; Lu et al., 2010; Svendsen
et al., 2015). There are a few works on shared-memory parallel algorithms
(Zhang et al., 2005; Du et al., 2009; Lessley et al., 2017). However, these
algorithms do not scale to larger graphs due to memory or computational
bottlenecks – either the algorithms miss out significant pruning opportunities
as in (Du et al., 2009), or they need to generate a large number of non-
maximal cliques as in (Zhang et al., 2005; Lessley et al., 2017).

###  1.1. Our Contributions

We make the following contributions towards enumerating all maximal cliques in
a simple graph.

Theoretically Efficient Parallel Algorithm: We present a shared-memory
parallel algorithm ${\tt ParTTT}$, which takes as input a graph $G$ and
enumerates all maximal cliques in $G$. ${\tt ParTTT}$ is an efficient
parallelization of the algorithm due to Tomita, Tanaka, and Takahashi (Tomita
et al., 2006). Our analysis of ${\tt ParTTT}$ using a work-depth model of
computation (Shun, 2017) shows that it is work-efficient when compared with
(Tomita et al., 2006) and has a low parallel depth. To our knowledge, this is
the first shared-memory parallel algorithm for MCE with such provable
properties.

Optimized Parallel Algorithm: We present a shared-memory parallel algorithm
${\tt ParMCE}$ that builds on ${\tt ParTTT}$ and yields improved practical
performance. Unlike ${\tt ParTTT}$, which starts with a single task at the top
level that spawns recursive subtasks as it proceeds, leading to a lack of
parallelism at the top level of recursion, ${\tt ParMCE}$ spawns multiple
parallel tasks at the top level. To achieve this, ${\tt ParMCE}$ uses per-
vertex parallelization, where a separate sub-problem is created for each
vertex and different sub-problems are processed in parallel. Each sub-problem
is required to enumerate cliques which contain the assigned vertex and care is
taken to prevent overlap between sub-problems. Each per-vertex sub-problem is
further processed in parallel using ${\tt ParTTT}$ – this additional
(recursive) level of parallelism using ${\tt ParTTT}$ is important since
different per-vertex sub-problems may have significantly different
computational costs, and having each run as a separate sequential task may
lead to uneven load balance. To further address load balance, we use a vertex
ordering in assigning cliques to different per-vertex sub-problems. For
ordering the vertices, we use various metrics such as degree, triangle count,
and the degeneracy number of the vertices.

Incremental Parallel Algorithm: Next, we present a parallel algorithm ${\tt
ParIMCE}$ that can maintain the set of maximal cliques in a dynamic graph,
when the graph is updated due to the addition of new edges. When a batch of
edges are added to the graph, ${\tt ParIMCE}$ can (in parallel) enumerate the
set of all new maximal cliques that emerged and the set of all maximal cliques
that are no longer maximal (subsumed cliques). ${\tt ParIMCE}$ consists of two
parts: ${\tt ParIMCENew}$ for enumerating new maximal cliques, and ${\tt
ParIMCESub}$ for enumerating subsumed maximal cliques. We analyze ${\tt
ParIMCE}$ using the work-depth model and show that it is work-efficient
relative to an efficient sequential algorithm, and has a low parallel depth. A
summary of our algorithms is shown in Table 1.

Table 1. Summary of shared-memory parallel algorithms for MCE.

Algorithm | Type | Description
---|---|---
${\tt ParTTT}$ | Static | A work-efficient parallel algorithm for MCE on a static graph
${\tt ParMCE}$ | Static | A practical parallel algorithm for MCE on a static graph dealing with load imbalance
${\tt ParIMCE}$ | Dynamic |  |  ${\tt ParIMCENew}$: A work-efficient parallel algorithm for enumerating new
---
maximal cliques in a dynamic graph.
|  ${\tt ParIMCESub}$: A work-efficient parallel algorithm for enumerating
subsumed
---
maximal cliques in a dynamic graph.

Experimental Evaluation: We implemented all our algorithms, and our
experiments show that ${\tt ParMCE}$ yields a speedup of 15x-21x when compared
with an efficient sequential algorithm (due to Tomita et al. (Tomita et al.,
2006)) on a multicore machine with $32$ physical cores and $1$ TB RAM. For
example, on the Wikipedia network with around $1.8$ million vertices, $36.5$
million edges, and $131.6$ million maximal cliques, ${\tt ParTTT}$ achieves a
16.5x parallel speedup over the sequential algorithm, and the optimized ${\tt
ParMCE}$ achieves a 21.5x speedup, and completed in approximately two minutes.
In contrast, prior shared-memory parallel algorithms for MCE (Zhang et al.,
2005; Du et al., 2009; Lessley et al., 2017) failed to handle the input graphs
that we considered, and either ran out of memory ((Zhang et al., 2005; Lessley
et al., 2017)) or did not complete in 5 hours ((Du et al., 2009)).

On dynamic graphs, we observe that ${\tt ParIMCE}$ gives a 3x-19x speedup over
a state-of-the-art sequential algorithm ${\tt IMCE}$ (Das et al., 2019) on a
multicore machine with 32 cores. Interestingly, the speedup of the parallel
algorithm increases with the magnitude of change in the set of maximal cliques
– the “harder” the dynamic enumeration task is, the larger is the speedup
obtained. For example, on a dense graph such as Ca-Cit-HepTh (with original
graph density of $0.01$), we get approximately a 19x speedup over the
sequential ${\tt IMCE}$. More details are presented in Section 6.

Techniques for Load Balancing: Our parallel methods can effectively balance
the load in solving parallel MCE. As shown in Figure 2, “natural” sub-problems
of MCE are highly imbalanced, and, therefore, load balancing is not trivial.
In our algorithms, sub-problems of MCE are broken down into smaller sub-
problems, according to the search used by the sequential algorithm (Tomita et
al., 2006), and this process continues recursively. As a result, the final
sub-problem that is solved in a single task is not so large as to create load
imbalances. Our experiments in Section 6 demonstrate that the recursive
splitting of sub-problems in MCE is essential for achieving a high speedup
over existing algorithms (Tomita et al., 2006). In order to efficiently assign
these (dynamically created) tasks to threads at runtime, we utilize a work
stealing scheduler (Blumofe, 1995; Blumofe and Leiserson, 1999).

Roadmap. The rest of the paper is organized as follows. We discuss related
works in Section 2, we present preliminaries in Section 3, followed by a
description of algorithms for a static graph in Section 4, algorithms for a
dynamic graph in Section 5, an experimental evaluation in Section 6, and
conclusions in Section 7.

##  2\. Related Work

Maximal Clique Enumeration (MCE) from a graph is a fundamental problem that
has been extensively studied for more than two decades, and there are multiple
prior works on sequential and parallel algorithms. We first discuss sequential
algorithms for MCE, followed by parallel algorithms.

Sequential MCE: Bron and Kerbosch (Bron and Kerbosch, 1973) presented an
algorithm for MCE based on depth-first-search. Following their work, a number
of algorithms have been presented (Tsukiyama et al., 1977; Chiba and
Nishizeki, 1985; Tomita et al., 2006; Koch, 2001; Makino and Uno, 2004; Cazals
and Karande, 2008; Eppstein et al., 2010). The algorithm of Tomita et al.
(Tomita et al., 2006) has a worst-case time complexity $O(3^{\frac{n}{3}})$
for an $n$ vertex graph, which is optimal in the worst-case, since the size of
the output can be as large as $O(3^{\frac{n}{3}})$ (Moon and Moser, 1965).
Eppstein et al. (Eppstein et al., 2010; Eppstein and Strash, 2011) present an
algorithm for sparse graphs whose complexity can be parameterized by the
degeneracy of the graph, a measure of graph sparsity.

Another approach to MCE is a class of “output-sensitive” algorithms whose time
complexity for enumerating maximal cliques is a function of the size of the
output. There exist many such output-sensitive algorithms for MCE, including
(Conte et al., 2016; Chiba and Nishizeki, 1985; Makino and Uno, 2004;
Tsukiyama et al., 1977), which can be viewed as instances of a general
paradigm called “reverse-search” (Avis and Fukuda, 1993). A recent algorithm
(Conte et al., 2016) provides favorable tradeoffs for delay (time between two
enumerated maximal cliques), when compared with prior works. In terms of
practical performance, the best output-sensitive algorithms (Conte et al.,
2016; Chiba and Nishizeki, 1985; Makino and Uno, 2004) are not as efficient as
the best depth-first-search based algorithms (Tomita et al., 2006; Eppstein et
al., 2010). Other sequential methods for MCE include algorithms due to Kose et
al. (Kose et al., 2001), Johnson et al. (Johnson et al., 1988), Li et al. (Li
et al., 2019), on a special class of graphs due to Fox et al. (Fox et al.,
2018), on temporal graph due to Qin et al. (Qin et al., 2019). Multiple works
have considered sequential algorithms for maintaining the set of maximal
cliques (Das et al., 2019; Stix, 2004; Ottosen and Vomlel, 2010) on a dynamic
graph, and, to our knowledge, the most efficient algorithm is the one due to
Das et al. (Das et al., 2019).

Parallel MCE: There are multiple prior works on parallel algorithms for MCE
(Zhang et al., 2005; Du et al., 2006; Wu et al., 2009; Schmidt et al., 2009;
Lu et al., 2010; Svendsen et al., 2015; Yu and Liu, 2019). We first discuss
shared-memory algorithms and then distributed memory algorithms. Zhang et al.
(Zhang et al., 2005) present a shared-memory parallel algorithm based on the
sequential algorithm due to Kose et al. (Kose et al., 2001). This algorithm
computes maximal cliques in an iterative manner, and, in each iteration, it
maintains a set of cliques that are not necessarily maximal and, for each such
clique, maintains the set of vertices that can be added to form larger
cliques. This algorithm does not provide a theoretical guarantee on the
runtime and suffers for large memory requirement. Du et al. (Du et al., 2006)
present a output-sensitive shared-memory parallel algorithm for MCE, but their
algorithm suffers from poor load balancing as also pointed out by Schmidt et
al. (Schmidt et al., 2009). Lessley et al. (Lessley et al., 2017) present a
shared memory parallel algorithm that generates maximal cliques using an
iterative method, where in each iteration, cliques of size $(k-1)$ are
extended to cliques of size $k$. The algorithm of (Lessley et al., 2017) is
memory-intensive, since it needs to store a number of intermediate non-maximal
cliques in each iteration. Note that the number of non-maximal cliques may be
far higher than the number of maximal cliques that are finally emitted, and a
number of distinct non-maximal cliques may finally lead to a single maximal
clique. In the extreme case, a complete graph on $n$ vertices has $(2^{n}-1)$
non-maximal cliques, and only a single maximal clique. We present a comparison
of our algorithm with (Lessley et al., 2017; Zhang et al., 2005; Du et al.,
2006) in later sections.

Distributed memory parallel algorithms for MCE include works due to Wu et al.
(Wu et al., 2009), designed for the MapReduce framework, Lu et al. (Lu et al.,
2010), which is based on the sequential algorithm due to Tsukiyama et al.
(Tsukiyama et al., 1977), Svendsen et al. (Svendsen et al., 2015), Wang et al.
(Wang et al., 2017), and algorithm for sparse graph due to Yu and Liu (Yu and
Liu, 2019). Other works on parallel and sequential algorithms for enumerating
dense subgraphs from a massive graph include sequential algorithms for
enumerating quasi-cliques (Sanei-Mehri et al., 2018; Liu and Wong, 2008; Uno,
2010), parallel algorithms for enumerating $k$-cores (Montresor et al., 2013;
Dasari et al., 2014; Kabir and Madduri, 2017a; Sariyuce et al., 2017),
$k$-trusses (Sariyuce et al., 2017; Kabir and Madduri, 2017c, b), nuclei
(Sariyuce et al., 2017), and distributed memory algorithms for enumerating
$k$-plexes (Conte et al., 2018), bicliques (Mukherjee and Tirthapura, 2017).

##  3\. Preliminaries

We consider a simple undirected graph without self loops or multiple edges.
For graph $G$, let $V(G)$ denote the set of vertices in $G$ and $E(G)$ denote
the set of edges in $G$. Let $n$ denote the size of $V(G)$, and $m$ denote the
size of $E(G)$. For vertex $u\in V(G)$, let $\Gamma_{G}(u)$ denote the set of
vertices adjacent to $u$ in $G$. When the graph $G$ is clear from the context,
we use $\Gamma(u)$ to mean $\Gamma_{G}(u)$. Let $\mathcal{C}(G)$ denote the
set of all maximal cliques in $G$.

Sequential Algorithm ${\tt TTT}$:  The algorithm due to Tomita, Tanaka, and
Takahashi. (Tomita et al., 2006), which we call ${\tt TTT}$, is a recursive
backtracking-based algorithm for enumerating all maximal cliques in an
undirected graph, with a worst-case time complexity of $O(3^{n/3})$ where $n$
is the number of vertices in the graph. In practice, this is one of the most
efficient sequential algorithms for MCE. Since we use ${\tt TTT}$ as a
subroutine in our parallel algorithms, we present a short description here.

In any recursive call, ${\tt TTT}$ maintains three disjoint sets of vertices
$K$, ${\tt cand}$, and ${\tt fini}$, where $K$ is a candidate clique to be
extended, ${\tt cand}$ is the set of vertices that can be used to extend $K$,
and ${\tt fini}$ is the set of vertices that are adjacent to $K$, but need not
be used to extend $K$ (these are being explored along other search paths).
Each recursive call iterates over vertices from ${\tt cand}$ and in each
iteration, a vertex $q\in{\tt cand}$ is added to $K$ and a new recursive call
is made with parameters $K\cup\\{q\\}$, ${\tt cand}_{q}$, and ${\tt fini}_{q}$
for generating all maximal cliques of $G$ that extend $K\cup\\{q\\}$ but do
not contain any vertices from ${\tt fini}_{q}$. The sets ${\tt cand}_{q}$ and
${\tt fini}_{q}$ can only contain vertices that are adjacent to all vertices
in $K\cup\\{q\\}$. The clique $K$ is a maximal clique when both ${\tt cand}$
and ${\tt fini}$ are empty.

The ingredient that makes ${\tt TTT}$ different from the algorithm due to Bron
and Kerbosch (Bron and Kerbosch, 1973) is the use of a “pivot” where a vertex
$u\in{\tt cand}\cup{\tt fini}$ is selected that maximizes $|{\tt
cand}\cap\Gamma(u)|$. Once the pivot $u$ is computed, it is sufficient to
iterate over all the vertices of ${\tt cand}\setminus\Gamma(u)$, instead of
iterating over all vertices of ${\tt cand}$. The pseudo code of ${\tt TTT}$ is
presented in Algorithm 1. For the initial call, $K$ and ${\tt fini}$ are
initialized to an empty set, ${\tt cand}$ is the set of all vertices of $G$.

Input: ${G}$ \- the input graph

$K$ \- a clique to extend,

${\tt cand}$ \- a set of vertices that can be used extend $K$,

${\tt fini}$ \- a set of vertices that have been used to extend $K$

Output: Set of all maximal cliques of $G$ containing $K$ and vertices from
${\tt cand}$ but not containing any vertex from ${\tt fini}$

1 if  _$({\tt cand}=\emptyset)$ & $({\tt fini}=\emptyset)$_ then

2 Output $K$ and return

3

4${\tt pivot}\leftarrow(u\in{\tt cand}\cup{\tt fini})$ such that $u$ maximizes
the size of ${\tt cand}\cap\Gamma_{{G}}(u)$

5 ${\tt ext}\leftarrow{\tt cand}-\Gamma_{{G}}({\tt pivot})$

6 for  _$q\in$ ext_ do

7 $K_{q}\leftarrow K\cup\\{q\\}$

8 ${\tt cand}_{q}\leftarrow{\tt cand}\cap\Gamma_{{G}}(q)$

9 ${\tt fini}_{q}\leftarrow{\tt fini}\cap\Gamma_{{G}}(q)$

10 ${\tt cand}\leftarrow{\tt cand}-\\{q\\}$

11 ${\tt fini}\leftarrow{\tt fini}\cup\\{q\\}$

12 ${\tt TTT}({G},K_{q},{\tt cand}_{q},{\tt fini}_{q})$

13

Algorithm 1 ${\tt TTT}({G},K,{\tt cand},{\tt fini})$

Parallel Cost Model:  For analyzing our shared-memory parallel algorithms, we
use the CRCW PRAM model (Blelloch and Maggs, 2010), which is a model of shared
parallel computation that assumes concurrent reads and concurrent writes. Our
parallel algorithm can also work in other related models of shared-memory such
as EREW PRAM (exclusive reads and exclusive writes), with a logarithmic factor
increase in work as well as parallel depth. We measure the effectiveness of
the parallel algorithm using the work-depth model (Shun, 2017). Here, the
“work” of a parallel algorithm is equal to the total number of operations of
the parallel algorithm, and the “depth” (also called the “parallel time” or
the “span”) is the longest chain of dependent computations in the algorithm. A
parallel algorithm is said to be work-efficient if its total work is of the
same order as the work due to the best sequential algorithm.111Note that work-
efficiency in the CRCW PRAM model does not imply work-efficiency in the EREW
PRAM model We aim for work-efficient algorithms with a low depth, ideally
poly-logarithmic in the size of the input. Using Brent’s theorem (Blelloch and
Maggs, 2010), it can be seen that a parallel algorithm on input size $n$ with
a depth of $d$ can theoretically achieve $\Theta(p)$ speedup on $p$ processors
as long as $p=O(n/d)$.

We next restate a result on concurrent hash tables (Shalev and Shavit, 2006)
that we use in proving the work and depth bounds of our parallel algorithms.

###### Theorem 3.1 (Theorem 3.15 (Shalev and Shavit, 2006)).

There is an implementation of a hash table, which, given a hash function with
expected uniform distribution, performs $n_{1}$ insert, $n_{2}$ delete and
$n_{3}$ find operations in parallel using $O(n_{1}+n_{2}+n_{3})$ work and
$O(1)$ depth on average.

##  4\. Parallel MCE Algorithms on a Static Graph

In this section, we present new shared-memory parallel algorithms for MCE. We
first describe a parallel algorithm ${\tt ParTTT}$, a parallelization of the
sequential ${\tt TTT}$ algorithm and an analysis of its theoretical
properties. Then, we discuss bottlenecks in ${\tt ParTTT}$ that arise in
practice, leading us to another algorithm ${\tt ParMCE}$ with a better
practical performance. ${\tt ParMCE}$ uses ${\tt ParTTT}$ as a subroutine – it
creates appropriate sub-problems that can be solved in parallel and hands off
the enumeration task to ${\tt ParTTT}$.

###  4.1. Algorithm ${\tt ParTTT}$

Our first algorithm ${\tt ParTTT}$ is a work-efficient parallelization of the
sequential ${\tt TTT}$ algorithm. The two main components of ${\tt TTT}$
(Algorithm 1) are (1) Selection of the pivot element (Line $3$) and (2)
Sequential backtracking for extending candidate cliques until all maximal
cliques are explored (Line $5$ to Line $11$). We discuss how to parallelize
each of these steps.

##### Parallel Pivot Selection:

Within a single recursive call of ${\tt ParTTT}$, the pivot element is
computed in parallel using two steps, as described in ${\tt ParPivot}$
(Algorithm 2). In the first step, the size of the intersection ${\tt
cand}\cap\Gamma(u)$ is computed in parallel for each vertex $u\in{\tt
cand}\cup{\tt fini}$. In the second step, the vertex with the maximum
intersection size is selected. The parallel algorithm for selecting a pivot is
presented in Algorithm 2. The following lemma proves that the parallel pivot
selection is work-efficient with logarithmic depth:

###### Lemma 0.

The total work of ${\tt ParPivot}$ is $O(\sum_{w\in{\tt cand}\cup{\tt
fini}}(\min\\{|{\tt cand}|,|\Gamma(w)|\\}))$, which is $O(n^{2})$, and depth
is $O(\log n)$.

###### Proof.

If sets ${\tt cand}$ and $\Gamma(w)$ are stored as hashsets, then, for vertex
$w$, the size $t_{w}=|{\tt intersect}({\tt cand},\Gamma(w))|$ can be computed
sequentially in time $O(\min\\{|{\tt cand}|,|\Gamma(w)|\\})$ – the
intersection of two sets $S_{1}$ and $S_{2}$ can be found by considering the
smaller set among the two, say $S_{2}$, and searching for its elements within
the larger set, say $S_{1}$. It is possible to parallelize the computation of
${\tt intersect}(S_{1},S_{2})$ by executing the search elements of $S_{2}$ in
parallel, followed by counting the number of elements that lie in the
intersection, which can also be done in parallel in a work-efficient manner
using $O(1)$ depth using Theorem 3.1. Since computing the maximum of a set of
$n$ numbers can be accomplished using work $O(n)$ and depth $O(\log n)$, for
vertex $w$, $t_{w}$ can be computed using work $O(\min\\{|{\tt
cand}|,|\Gamma(w)|\\})$ and depth $O(\log n)$. Once $t_{w}$ (i.e. $|{\tt
cand}\cap\Gamma(w)|$) is computed for every vertex $w\in{\tt cand}\cup{\tt
fini}$, $argmax(\\{t_{w}:w\in{\tt cand}\cup{\tt fini}\\})$ can be obtained
using additional work $O(|{\tt cand}\cup{\tt fini}|)$ and depth $O(\log n)$.
Hence, the total work of ${\tt ParPivot}$ is $O(\sum_{w\in{\tt cand}\cup{\tt
fini}}(\min\\{|{\tt cand}|,|\Gamma(w)|\\})$. Since the size of ${\tt cand}$,
${\tt fini}$, and $\Gamma(w)$ are bounded by $n$, this is $O(n^{2})$, but
typically much smaller in practice. ∎

Input: $G$ \- the input graph; $K$ \- a clique in $G$ that may be further
extended; ${\tt cand}$ \- a set of vertices that may extend $K$; ${\tt fini}$
\- a set of vertices that have been used to extend $K$.  Output: Pivot vertex
$v\in{\tt cand}\cup{\tt fini}$.  1 for  _$w\in{\tt cand}\cup{\tt fini}$_ do in
parallel 2 In parallel, compute $t_{w}\leftarrow|{\tt intersect}({\tt
cand},\Gamma_{G}(w))|$ 3 4In parallel, find $v\leftarrow
argmax(\\{t_{w}:w\in{\tt cand}\cup{\tt fini}\\})$ 5 return _$v$_ Algorithm 2
${\tt ParPivot}(G,K,{\tt cand},{\tt fini})$

##### Parallelization of Backtracking:

We first note that there is a sequential dependency among the different
iterations within a recursive call of ${\tt TTT}$. In particular, the contents
of the sets ${\tt cand}$ and ${\tt fini}$ in a given iteration are derived
from the contents of ${\tt cand}$ and ${\tt fini}$ in the previous iteration.
Such sequential dependence of updates to ${\tt cand}$ and ${\tt fini}$
restricts us from calling the recursive ${\tt TTT}$ for different vertices of
${\tt ext}$ in parallel. To remove this dependency, we adopt a different view
of ${\tt TTT}$ which enables us to make the recursive calls in parallel. The
elements of ${\tt ext}$, the vertices to be considered for extending a maximal
clique, are arranged in a predefined total order. Then, we unroll the loop and
explicitly compute the parameters ${\tt cand}$ and ${\tt fini}$ for recursive
calls.

Suppose $\langle v_{1},v_{2},...,v_{\kappa}\rangle$ is the order of vertices
in ${\tt ext}$. Each vertex $v_{i}\in{\tt ext}$, once added to $K$, should be
removed from further consideration in ${\tt cand}$. To ensure this, in ${\tt
ParTTT}$, we explicitly remove vertices $v_{1},v_{2},...,v_{i-1}$ from ${\tt
cand}$ and add them to ${\tt fini}$, before making the recursive calls. As a
consequence, parameters of the $i$th iteration are computed independently of
prior iterations.

Input: ${G}$ \- the input graph  $K$ \- a non-maximal clique to extend  ${\tt
cand}$ \- set of vertices that may extend $K$ ${\tt fini}$ \- vertices that
have been used to extend $K$ Output: A set of all maximal cliques of $G$
containing $K$ and vertices from ${\tt cand}$ but not containing any vertex
from ${\tt fini}$ 1 if  _$({\tt cand}=\emptyset)$ & $({\tt fini}=\emptyset)$_
then 2 Output $K$ and return 3${\tt pivot}\leftarrow{\tt ParPivot}({G},{\tt
cand},{\tt fini})$ 4 ${\tt ext}[1..\kappa]\leftarrow{\tt
cand}-\Gamma_{{G}}({\tt pivot})$ // in parallel  5 for  _$i\in$ $[1..\kappa]$_
do in parallel 6 $q\leftarrow{\tt ext}[i]$ 7 $K_{q}\leftarrow K\cup\\{q\\}$ 8
${\tt cand}_{q}\leftarrow{\tt intersect}({\tt cand}\setminus{\tt
ext}[1..i-1],\Gamma_{{G}}(q))$ 9 ${\tt fini}_{q}\leftarrow{\tt intersect}({\tt
fini}\cup{\tt ext}[1..i-1],\Gamma_{{G}}(q))$ 10 ${\tt ParTTT}({G},K_{q},{\tt
cand}_{q},{\tt fini}_{q})$ 11 Algorithm 3 ${\tt ParTTT}({G},K,{\tt cand},{\tt
fini})$

Here, we prove the work efficiency and low depth of ${\tt ParTTT}$ in the
following lemma:

###### Lemma 0.

Total work of ${\tt ParTTT}$ (Algorithm 3) is $O(3^{n/3})$ and depth is
$O(M\log{n})$ where $n$ is the number of vertices in the graph, and $M$ is the
size of a maximum clique in $G$.

###### Proof.

First, we analyze the total work. Note that the computational tasks in ${\tt
ParTTT}$ is different from ${\tt TTT}$ at Line 8 and Line 9 of ${\tt ParTTT}$
where at an iteration $i$, we remove all vertices
$\\{v_{1},v_{2},...,v_{i-1}\\}$ from ${\tt cand}$ and add all these vertices
to ${\tt fini}$ as opposed to the removal of a single vertex $v_{i-1}$ from
${\tt cand}$ and addition of that vertex to ${\tt fini}$ as in ${\tt TTT}$
(Line 8 and Line 9 of Algorithm 1). Therefore, in ${\tt ParTTT}$, additional
$O(n)$ work is required due to independent computations of ${\tt cand}_{q}$
and ${\tt fini}_{q}$. The total work, excluding the call to ${\tt ParPivot}$
is $O(n^{2})$. Adding up the work of ${\tt ParPivot}$, which requires
$O(n^{2})$ work and $O(n^{2})$ total work for each single call of ${\tt
ParTTT}$ excluding further recursive calls (Algorithm 3, Line 10), which is
the same as in original sequential algorithm ${\tt TTT}$ (Section 4, (Tomita
et al., 2006)). Hence, using Lemma 2 and Theorem 3 of (Tomita et al., 2006),
we infer that the total work of ${\tt ParTTT}$ is the same as the sequential
algorithm ${\tt TTT}$ and is bounded by $O(3^{n/3})$.

Next, we analyze the depth of the algorithm. The depth of ${\tt ParTTT}$
consists of the (sum of the) following components: (1) Depth of ${\tt
ParPivot}$, (2) Depth of computation of ${\tt ext}$, (3) Maximum depth of an
iteration in the for loop from Line 5 to Line 10. According to Lemma 4.1, the
depth of ${\tt ParPivot}$ is $O(\log{n})$. The depth of computing ${\tt ext}$
is $O(\log n)$ since it takes $O(1)$ time to check whether an element in ${\tt
cand}$ is in the neighborhood of ${\tt pivot}$. Similarly, the depth of
computing ${\tt cand}_{q}$ and ${\tt fini}_{q}$ at Line 8 and Line 9 are
$O(\log n)$. The remaining is the depth of the call of ${\tt ParTTT}$ at Line
10. Notice that the recursive call of ${\tt ParTTT}$ continues until there is
no further vertex to add for expanding $K$, and this depth can be at most the
size of the maximum clique which is $M$ because, at each recursive call of
${\tt ParTTT}$, the size of $K$ increases by $1$. Thus, the overall depth of
${\tt ParTTT}$ is $O(M\log{n})$. ∎

###### Corollary 0.

Using $P$ parallel processors, which are shared-memory, ${\tt ParTTT}$
(Algorithm 3) is a parallel algorithm for MCE and can achieve a worst case
parallel time of $O\left(\frac{3^{n/3}}{M\log n}+P\right)$ using $P$ parallel
processors. This is work-optimal and work-efficient as long as
$P=O(\frac{3^{n/3}}{M\log n})$.

###### Proof.

The parallel time follows Brent’s theorem (Blelloch and Maggs, 2010), which
states that the parallel time using $P$ processors is $O(w/d+P)$, where $w$
and $d$ are the work and the depth of the algorithm respectively. If the
number of processors $P=O\left(\frac{3^{n/3}}{M\log n}\right)$, then using
Lemma 4.2, the parallel time is $O\left(\max\\{\frac{3^{n/3}}{P},{M\log
n}\\}\right)=O\left(\frac{3^{n/3}}{P}\right)$. The total work across all
processors is $O(3^{n/3})$, which is worst-case optimal, since the size of the
output can be as large as $3^{n/3}$ maximal cliques (Moon and Moser (Moon and
Moser, 1965)). ∎

###  4.2. Algorithm ${\tt ParMCE}$

While ${\tt ParTTT}$ is a theoretically work-efficient parallel algorithm, we
note that its runtime can be further improved. While the worst case work
complexity of ${\tt ParPivot}$ matches that of the pivoting routine in ${\tt
TTT}$, in practice, the work in ${\tt ParTTT}$ can be higher, since
computation of ${\tt cand}_{q}$ and ${\tt fini}_{q}$ has additional and
growing overhead as the sizes of the ${\tt cand}_{q}$ and ${\tt fini}_{q}$
increase. This can result in a lower speedup than the theoretically expected
one.

We set out to improve on this to derive a more efficient parallel
implementation through a more selective use of ${\tt ParPivot}$. In this way,
the cost of pivoting can be reduced by carefully choosing many pivots in
parallel instead of a single pivot element as in ${\tt ParTTT}$ at the
beginning of the algorithm. We first note that the cost of ${\tt ParPivot}$ is
the highest during the iteration when set $K$ (the clique in the search space)
is empty. During this iteration, the number of vertices in ${\tt cand}\cup{\tt
fini}$ can be high, as large as the number of vertices in the graph. To
improve upon this, we can perform the first few steps of pivoting, when $K$ is
empty, using a sequential algorithm. Once set $K$ contains at least one
element, the number of the vertices in ${\tt cand}\cup{\tt fini}$ is
decremented to no more than the size of the intersection of neighborhoods of
all vertices in $K$, which is typically a number much smaller than the number
of vertices in the graph (this number is smaller than the smallest degree of a
vertex in $K$). Problem instances with $K$, assigned to a single vertex, can
be seen as sub-problems, and, on each of these sub-problems, the overhead of
${\tt ParPivot}$ computation is much smaller since the number of vertices that
have to be dealt with is also much smaller.

Based on this observation, we present a parallel algorithm ${\tt ParMCE}$
which works as follows. The algorithm can be viewed as considering, for each
vertex $v\in V(G)$, a subgraph $G_{v}$ that is induced by the vertex $v$ and
its neighborhood $\Gamma_{G}(v)$. It enumerates all maximal cliques from each
subgraph $G_{v}$ in parallel using ${\tt ParTTT}$. While processing sub-
problem $G_{v}$, it is important to not enumerate maximal cliques that are
being enumerated elsewhere, in other sub-problems. To handle this, the
algorithm considers a specific ordering of all vertices in $V$ such that $v$
is the least ranked vertex in each maximal clique enumerated from $G_{v}$.
Subgraph $G_{v}$ for each vertex $v$ is handled in parallel – these subgraphs
need not be processed in any particular order. However, the ordering allows us
to populate the ${\tt cand}$ and ${\tt fini}$ sets accordingly such that each
maximal clique is enumerated in exactly one sub-problem. The order in which
the vertices are considered is defined by a “rank” function rank, which
indicates the position of a vertex in the total order. This global ordering on
vertices has impact on the total work of the algorithm, as well as the load
balance of the distribution of workloads across sub-problems.

Load Balancing: Notice that the sizes of the subgraphs $G_{v}$ may vary widely
because of two reasons: (1) The subgraphs themselves may be of different
sizes, depending on the vertex degrees. (2) The number of maximal cliques and
the sizes of the maximal cliques containing $v$ can vary widely from one
vertex to another. Clearly, the sub-problems that deal with a large number of
maximal cliques or maximal cliques of a large size are more computationally
expensive than others.

In order to maintain the size of the sub-problems approximately balanced, we
use an idea from PECO (Svendsen et al., 2015), where we choose the rank
function on the vertices in such a way that for any two vertices $v$ and $w$,
rank($v$) $>$ rank($w$) if the complexity of enumerating maximal cliques from
$G_{v}$ is higher than the complexity of enumerating maximal cliques from
$G_{w}$. Indeed, by giving a higher rank to $v$ than $w$, we are decreasing
the complexity of the sub-problem $G_{v}$ since the sub-problem at $G_{v}$
need not enumerate maximal cliques that involve any vertex whose rank is less
than $v$. Therefore, the higher the rank of vertex $v$, the lower is its
“share” (of maximal cliques it belongs to) of maximal cliques in $G_{v}$. We
use this idea for approximately balancing the workload across sub-problems.
The additional enhancements in ${\tt ParMCE}$ when compared with the idea from
PECO are as follows: (1) In PECO, the algorithm is designed for distributed
memory such that the subgraphs and sub-problems have to be explicitly copied
across the network. (2) In ${\tt ParMCE}$, the vertex specific sub-problem,
dealing with $G_{v}$ is itself handled through a parallel algorithm, ${\tt
ParTTT}$, while, in PECO, the sub-problem for each vertex was handled through
a sequential algorithm.

Note that it is computationally expensive to accurately count the number of
maximal cliques within $G_{v}$, and, hence, it is not possible to compute the
rank of each vertex exactly according to the complexity of handling $G_{v}$.
Instead, we estimate the cost of handling $G_{v}$ using some easy-to-evaluate
metrics on the subgraphs. In particular, we consider the following:

  * •

Degree Based Ranking:  For vertex $v$, define ${\tt rank}(v)=(d(v),id(v))$
where $d(v)$ and $id(v)$ are degree and identifier of $v$, respectively. For
two vertices $v$ and $w$, ${\tt rank}(v)>{\tt rank}(w)$ if $d(v)>d(w)$ or
$d(v)=d(w)$ and $id(v)>id(w)$, $rank(v)<rank(w)$ otherwise.

  * •

Triangle Count Based Ranking:  For vertex $v$, define ${\tt
rank}(v)=(t(v),id(v))$ where $t(v)$ is the number of triangles, which vertex
$v$ is a part of. Note that ranking based on triangle count is more expensive
to compute than degree based ranking but may yield a better estimate of the
complexity of maximal cliques within $G_{v}$.222A triangle is a cycle of
length three.

  * •

Degeneracy Based Ranking (Eppstein et al., 2010):  For a vertex $v$, define
${\tt rank}(v)=(degen(v),id(v))$ where $degen(v)$ is the degeneracy of a
vertex $v$. A vertex $v$ has degeneracy number $k$ when it belongs to a
$k$-core but no $(k+1)$-core, where a $k$-core is a maximal induced subgraph
such that the minimum degree of each vertex in the subgraph is $k$. A
computational overhead of using this ranking is due to computing the
degeneracy of vertices which takes $O(n+m)$ time, where $n$ is the number of
vertices and $m$ is the number of edges.

The different implementations of ${\tt ParMCE}$ using degree, triangle, and
degeneracy based rankings are called as ${\tt ParMCEDegree}$, ${\tt
ParMCETri}$, ${\tt ParMCEDegen}$ respectively.

Input: ${G}$ \- the input graph.  Output: $\mathcal{C}({G})$ \- a set of all
maximal cliques of ${G}$.  1 for  _$v\in V({G})$_ do in parallel 2 Create
${G}_{v}$, the subgraph of ${G}$ induced by $\Gamma_{{G}}(v)\cup\\{v\\}$ 3
$K\leftarrow\\{v\\}$, ${\tt cand}\leftarrow\phi$, ${\tt fini}\leftarrow\phi$ 4
for  _$w\in\Gamma_{{G}}(v)$_ do in parallel 5 if  _$rank(w) >rank(v)$_ then
${\tt cand}\leftarrow{\tt cand}\cup\\{w\\}$ 6 else ${\tt fini}\leftarrow{\tt
fini}\cup\\{w\\}$ 7 8 ${\tt ParTTT}({G}_{v},K,{\tt cand},{\tt fini})$
Algorithm 4 ${\tt ParMCE}({G})$

##  5\. Parallel MCE Algorithm on a Dynamic Graph

When the graph changes over time due to addition of edges, the maximal cliques
of the updated graph also change. The update in the set of maximal cliques
consists of (1) The set of new maximal cliques – the maximal cliques that are
newly formed (2) The set of subsumed cliques – maximal cliques of the original
graph that are subsumed by the new maximal cliques. The combined set of new
and subsumed maximal cliques is called the set of changes, and the size of
this set refers to the size of change in the set of maximal cliques (see
Figure 3).

|  |
---|---|---
(a) Input Graph $G$ |  (b) A new edge $(e,d)$ |  (c) Three new edges: $(a,c),(a,d),(c,e)$
Figure 3.  Maximal cliques change upon addition of new edges. (a) Two
subgraphs $\\{a,b,e\\}$ and $\\{b,c,d\\}$ are maximal cliques in the original
graph $G$. (b) A new maximal clique (i.e. $\\{b,d,e\\}$) is created when edge
$(e,d)$ is added to $G$. (c) When three more edges $(a,c)$, $(a,d)$, and
$(c,e)$ are added, the entire graph turns into a maximal clique, which
subsumes all maximal cliques in prior steps.  Input: $G$ \- the input graph
$H$ \- a set of $\rho$ edges being added to $G$ Output: Cliques in
$\Lambda^{new}=\mathcal{C}(G+H)\setminus\mathcal{C}(G)$ 1
$G^{\prime}\leftarrow G+H$ 2 Consider edges of $H$ in an arbitrary order
$e_{1},e_{2},\ldots,e_{\rho}$ 3 4for  _$i\leftarrow 1,2,\ldots,\rho$_ do in
parallel 5 $e\leftarrow e_{i}=(u,v)$ 6 7
$V_{e}\leftarrow\\{u,v\\}\cup\\{\Gamma_{G^{\prime}}(u)\cap\Gamma_{G^{\prime}}(v)\\}$
8 ${G}^{\prime\prime}\leftarrow$ Graph induced by $V_{e}$ on $G^{\prime}$ 9
$K\leftarrow\\{u,v\\}$ 10 ${\tt cand}\leftarrow V_{e}\setminus\\{u,v\\}$ ;
${\tt fini}\leftarrow\emptyset$ 11 $S\leftarrow{\tt
ParTTTExcludeEdges}({G}^{\prime\prime},K,{\tt cand},{\tt
fini},\\{e_{1},e_{2},...,e_{i-1}\\})$ 12
$\Lambda^{new}\leftarrow\Lambda^{new}\cup S$ 13 Algorithm 5 ${\tt
ParIMCENew}(G,H)$

Note that the size of change can be as small as $O(1)$ or as large as
exponential in the size of the graph upon addition of a new single edge. For
example, consider a graph of size $n$ which is missing a single edge from
being a clique. The size of change is only $3$ when that missing edge is added
to the graph because there will be only one new maximal clique of size $n$ and
two subsumed cliques, each of size $(n-1)$. On the other hand, consider a
Moon-Moser graph (Moon and Moser, 1965) of size $n$. Addition of a single edge
to this graph makes the size of the changes in the order of $O(3^{n/3})$.

In a previous work, we presented a sequential algorithm ${\tt IMCE}$ (Das et
al., 2019), which efficiently tackles the problem of updating the set of
maximal cliques of a dynamic graph in an incremental model when new edges are
added at a time. ${\tt IMCE}$ consists of ${\tt FastIMCENewClq}$ for computing
new maximal cliques and ${\tt IMCESubClq}$ for computing subsumed cliques.
However, ${\tt IMCE}$ is still unable to update the set of maximal cliques
when the size of change is large. For instance, it takes ${\tt IMCE}$ around
$9.4$ hours to update the set of maximal cliques, when the first $90K$ edges
of graph Ca-Cit-HepTh are added incrementally (with the original graph density
0.01). The high computational cost of ${\tt IMCE}$ calls for parallel methods.

In this section, we present parallel algorithms for enumerating the set of new
and subsumed cliques when an edge set $H=\\{e_{1},e_{2},...,e_{\rho}\\}$ is
added to a graph $G$. Our parallel algorithms are based on ${\tt IMCE}$ (Das
et al., 2019). In this work, we focus on (1) processing new edges in parallel,
(2) enumerating new maximal cliques using ${\tt ParTTT}$, and (3)
Parallelizing ${\tt IMCESubClq}$ (Das et al., 2019). First, we describe an
efficient parallel algorithm for generating new maximal cliques, i.e. the
maximal cliques in $G+H$, which are not present in $G$ and then an efficient
parallel algorithm for generating subsumed maximal cliques, i.e. the cliques
which are maximal in $G$ but not maximal in $G+H$. We present a shared-memory
parallel algorithm ${\tt ParIMCE}$ for the incremental maintenance of maximal
cliques. ${\tt ParIMCE}$ consists of (1) algorithm ${\tt ParIMCENew}$ for
enumerating new maximal cliques and (2) algorithm ${\tt ParIMCESub}$ for
enumerating subsumed cliques. A brief description of the algorithms is
discussed in Table 2. Figure 4 also sketches the parallel shared-memory setup
for enumerating maximal cliques in a dynamic graph upon addition of new
batches.

---
Figure 4.  Our shared-memory set up for processing a dynamic graph.  Table 2.
Brief description of the incremental algorithms in this work.

Objective |  | Sequential
---
Algorithm (Das et al., 2019)
| Parallel Algorithm
---
(this work)
Overview of Parallel Algorithms
| Enumerating new
---
maximal cliques
${\tt FastIMCENewClq}$ | ${\tt ParIMCENew}$ |  | (1) Process new edges in parallel.
---
(2) Enumerate maximal cliques using ${\tt ParTTTExcludeEdges}$.
| Enumerating
---
subsumed cliques
${\tt IMCESubClq}$ | ${\tt ParIMCESub}$ |  | (1) Generate candidates in parallel
---
(executing inner for loop of ${\tt IMCESubClq}$ in parallel).
(2) Process each candidate in parallel
(executing candidate processing step of ${\tt IMCESubClq}$ in parallel).

###  5.1. Parallel Enumeration of New Maximal Cliques

Here, we present a parallel algorithm ${\tt ParIMCENew}$ for enumerating the
set of new maximal cliques when a set of edges is added to the graph. The idea
is that we iterate over new edges in parallel and at each (parallel) iteration
we construct a subgraph of the original graph and enumerate the set of all
maximal cliques within the subgraph. We present an efficient parallel
algorithm ${\tt ParTTTExcludeEdges}$ (Algorithm 6) for this enumeration. The
description of ${\tt ParIMCENew}$ is presented in Algorithm 5.

Input: ${G}$ \- the input graph  $K$ \- Set of vertices forming a clique
${\tt cand}$ \- a set of vertices that may extend $K$ ${\tt fini}$ \- vertices
that are not used to extend $K$, but are connected to all vertices of $K$
$\mathcal{E}$ \- a set of edges to ignore  1 if  _$({\tt cand}=\emptyset)$ &
$({\tt fini}=\emptyset)$_ then 2 Output $K$ // K is a maximal clique  3 return
4 5${\tt pivot}\leftarrow{\tt ParPivot}({G},{\tt cand},{\tt fini})$ 6 ${\tt
ext}[1..\kappa]\leftarrow{\tt cand}-\Gamma_{{G}}({\tt pivot})$ // in parallel
7 for  _$i\in$ $[1..\kappa]$_ do in parallel 8 $q\leftarrow{\tt ext}[i]$ 9
$K_{q}\leftarrow K\cup\\{q\\}$ 10 if  _$K_{q}\cap\mathcal{E}\neq\emptyset$_
then 11 return 12 13 ${\tt cand}_{q}\leftarrow{\tt intersect}({\tt
cand}\setminus{\tt ext}[1..i-1],\Gamma_{{G}}(q))$ 14 ${\tt
fini}_{q}\leftarrow{\tt intersect}({\tt fini}\cup{\tt
ext}[1..i-1],\Gamma_{{G}}(q))$ 15 ${\tt ParTTTExcludeEdges}({G},K_{q},{\tt
cand}_{q},{\tt fini}_{q},\mathcal{E})$ 16 Algorithm 6 ${\tt
ParTTTExcludeEdges}({G},K,{\tt cand},{\tt fini},\mathcal{E})$

Note that ${\tt ParIMCENew}$ is based upon an existing sequential algorithm
${\tt FastIMCENewClq}$ (Das et al., 2019) for enumerating new maximal cliques
using ${\tt{TTTExcludeEdges}}$ (Algorithm 8) (Das et al., 2019), which lists
all new maximal cliques without any duplication. ${\tt ParTTTExcludeEdges}$
avoids the duplication in maximal clique enumeration similar to the technique
used in ${\tt{TTTExcludeEdges}}$ and uses a parallelization approach similar
to of ${\tt ParTTT}$. More specifically, ${\tt ParTTTExcludeEdges}$ follows a
global ordering of the new edges to avoid redundancy in the enumeration
process. Note that the correctness of ${\tt ParIMCENew}$ is followed by the
correctness of the sequential algorithm ${\tt FastIMCENewClq}$. Following
lemma shows the work efficiency and depth of ${\tt ParIMCENew}$.

###### Lemma 0.

Given a graph $G$ and a new edge set $H$, ${\tt ParIMCENew}$ is work-
efficient, i.e, the total work is of the same order of the time complexity of
${\tt FastIMCENewClq}$. The depth of ${\tt ParIMCENew}$ is
$O(\Delta^{2}+M\log{\Delta})$, where $\Delta$ is the maximum degree and $M$ is
the size of a maximum clique in $G+H$.

We prove this lemma in Appendix A by showing the equivalence of the operations
of ${\tt FastIMCENewClq}$ and ${\tt ParIMCENew}$.

###  5.2. Parallel Enumeration of Subsumed Cliques

Input: $G$ \- the input Graph  $H$ \- an edge set being added to $G$ $C$ \- a
set of maximal cliques in $G$ $\Lambda^{new}$ \- a set of new maximal cliques
in $G+H$ Output: All cliques in
$\Lambda^{del}=\mathcal{C}(G)\setminus\mathcal{C}(G+H)$ 1
$\Lambda^{del}\leftarrow\emptyset$ 2 for  _$c\in\Lambda^{new}$_ do in parallel
3 $S\leftarrow\\{c\\}$ 4 for  _$e=(u,v)\in E(c)\cap H$_ do 5
$S^{\prime}\leftarrow\phi$ 6 for  _$c^{\prime}\in S$_ do in parallel 7 if
_$e\in E(c^{\prime})$_ then 8 $c_{1}=c^{\prime}\setminus\\{u\\}$ ;
$c_{2}=c^{\prime}\setminus\\{v\\}$ 9 $S^{\prime}\leftarrow S^{\prime}\cup
c_{1}$ ; $S^{\prime}\leftarrow S^{\prime}\cup c_{2}$ 10 11 else 12 13
$S^{\prime}\leftarrow S^{\prime}\cup c^{\prime}$ 14 15 16 $S\leftarrow
S^{\prime}$ 17 18 for  _$c^{\prime}\in S$_ do in parallel 19 if
_$c^{\prime}\in C$_ then 20 $\Lambda^{del}\leftarrow\Lambda^{del}\cup
c^{\prime}$ 21 $C\leftarrow C\setminus c^{\prime}$ 22 23 24 Algorithm 7 ${\tt
ParIMCESub}(G,H,C,\Lambda^{new})$

In this section, we present a parallel algorithm ${\tt ParIMCESub}$ based on
the sequential algorithm ${\tt IMCESubClq}$ (Das et al., 2019) for enumerating
subsumed cliques. In ${\tt ParIMCESub}$, we perform parallelization in the
following order: (1) Removing a single new edges from all the candidates in
parallel and (2) Checking for the candidacy of the subsumed cliques in
parallel. We present ${\tt ParIMCESub}$ in Algorithm 7. In the following
lemma, we show the work efficiency and depth of ${\tt ParIMCESub}$:

###### Lemma 0.

Given a graph $G$ and a new edge set $H$, ${\tt ParIMCESub}$ is work-
efficient; the total work is of the same order of the time complexity of ${\tt
IMCESubClq}$. The depth of ${\tt ParIMCENew}$ is
$O(\mbox{min}\\{M^{2},\rho\\})$ for processing each new maximal clique, where
$M$ is the size of a maximum clique in $G+H$ and $\rho$ is the size of $H$.

###### Proof.

First, note that the procedure of ${\tt ParIMCESub}$ is exactly the same as
the procedure of ${\tt IMCESubClq}$ except for the parallel loops at Line 6
and Line 13 of ${\tt ParIMCESub}$ whereas these loops are sequential in ${\tt
IMCESubClq}$. Since all the computations in ${\tt ParIMCESub}$ is exactly the
same as the computations in ${\tt IMCESubClq}$, except for the loop
parallelization, ${\tt ParIMCESub}$ is work-efficient.

For proving the parallel depth of ${\tt ParIMCESub}$, first note that all the
elements of $S$ at Line 6 of ${\tt ParIMCESub}$ are processed in parallel, and
the total cost of executing Lines 7 to 11 is $O(1)$. In addition, the depth of
the operation at Line 12 of ${\tt ParIMCESub}$ is $O(1)$ using the concurrent
hashtable. Therefore, the overall depth of the procedures from Line 4 to Line
12 is the number of new edges in a new maximal clique $c$, processed at Line 2
of ${\tt ParIMCESub}$ which is $O(\mbox{min}\\{M^{2},\rho\\})$. Next, the
depth of Lines 14 to 16 is $O(1)$ because it only takes $O(1)$ to execute
Lines 15 and 16 using Theorem 3.1. As a result, for each new maximal clique,
the depth of the procedure for enumerating all subsumed cliques within the new
maximal clique is $O(\mbox{min}\\{M^{2},\rho\\})$. ∎

###  5.3. Decremental Case

We have so far discussed incremental maintenance of new and subsumed maximal
cliques when the stream only contains new edges. We note that our algorithm
can also support the deletion of edges through a reduction to the incremental
case, this is similar to the methods used for sequential algorithms. Please
see Sections 4.4 and 4.5 of (Das et al., 2019) for further details.

##  6\. Evaluation

In this section, we experimentally evaluate the performance of our shared-
memory parallel static (${\tt ParTTT}$ and ${\tt ParMCE}$) and dynamic (${\tt
ParIMCE}$) algorithms for ${\tt MCE}$ on static and dynamic (real world and
synthetic) graphs to show the parallel speedup and scalability of our
algorithms over efficient sequential algorithms ${\tt TTT}$ and ${\tt IMCE}$
respectively. We also compare our algorithms with state-of-the-art parallel
algorithms for MCE to show that the performance of our algorithm has
substantially improved over the prior works. We run the experiments on a
computer configured with Intel Xeon (R) CPU E5-4620 running at 2.20GHz , with
$32$ physical cores (4 NUMA nodes each with $8$ cores) and $1$TB RAM.

###  6.1. Datasets

We use eight different real-world static and dynamic networks from publicly
available repositories KONECT (Kunegis, 2013), SNAP (Leskovec and Krevl,
2014), and Network Repository (Rossi and Ahmed, 2015) for doing the
experiments. Dataset statistics are summarized in Table 3. For our
experiments, we convert these networks to simple undirected graphs by removing
self-loops, edge weights, parallel edges, and edge directions.

We consider networks DBLP-Coauthor, As-Skitter, Wikipedia, Wiki-Talk, and
Orkut for the evaluation of the algorithms on static graphs and networks DBLP-
Coauthor, Flickr, Wikipedia, LiveJournal, and Ca-Cit-HepTh for the evaluation
of the algorithms on dynamic graphs.

DBLP-Coauthor shows the collaboration of authors of papers from DBLP computer
science bibliography. In this graph, vertices represent authors, and there is
an edge between two authors if they have published a paper (Rossi and Ahmed,
2015). As-Skitter is an Internet topology graph which represents the
autonomous systems, connected to each other on the Internet (Kunegis, 2013).
Wikipedia is a network of English Wikipedia in 2013, where vertices represent
pages in English Wikipedia, and there is an edge between two pages $p$ and $q$
if there is a hyperlink in page $p$ to page $q$ (Leskovec and Krevl, 2014).
Wiki-Talk contains users of Wikipedia as vertices where each edge between two
users in this graph indicates that one of the users has edited the ”page talk”
of the other user on Wikipedia (Leskovec and Krevl, 2014). Orkut is a social
network where each vertex represents a user in the network, and there is an
edge if there is a friendship relation between two users (Kunegis, 2013).
Similar to Orkut, Flickr and LiveJournal are also social networks where a
vertex represents a user and an edge represents the friendship between two
users. Ca-Cit-HepTh is a citation network of high energy physics theory where
a vertex represents a paper and there is an edge between paper $u$ and paper
$v$ if $u$ cites $v$.

For the evaluation of ${\tt ParTTT}$ and ${\tt ParMCE}$, we give the entire
graph as input to the algorithm in the form of an edge list and for the
evaluation of the algorithms on dynamic graphs, we start with an empty graph
that contains all vertices but no edges, and, at a time, we add a set of edges
in an increasing order of timestamps for computing the changes in the set of
maximal cliques. For ${\tt ParIMCE}$, we use real dynamic graphs, where each
edge has a timestamp. In addition, we evaluate ${\tt ParIMCE}$ on LiveJournal,
which is a static graph. We convert this graph to a dynamic graph through
randomly permuting the edges and processing edges in that ordering.

|  |
---|---|---
(a) DBLP-Coauthor | (b) As-Skitter | (c) Wikipedia

|
---|---
(d) Wiki-Talk | (e) Orkut

Figure 5. Frequency distribution of sizes of maximal cliques across different
input graphs.

To understand the datasets better, we illustrated the frequency distribution
of sizes of maximal cliques in Figure 5. The size of maximal cliques in DBLP-
Coauthor can be as large as $100$ vertices. Although the number of such large
maximal cliques are small, the depth of the search space might increase
exponentially for discovering such large maximal cliques. As shown in Figure
5, most of the graphs contain more than tens of millions of maximal cliques.
For example, Orkut contains more than two billion maximal cliques. That being
said, the depth and breadth of the search space makes MCE a challenging
problem to solve.

Table 3. Static and Dynamic Networks, used for evaluation, and their
properties. For some of the graphs (e.g. Flickr and Ca-Cit-HepTh) used for
evaluating the incremental algorithms, we could not report the information
about maximal cliques as they did not finish within 10 days, even using
parallel algorithms.

Dataset | #Vertices | #Edges | #Maximal Cliques |  | Average Size of
---
Maximal Cliques
| Size of
---
Largest Clique
DBLP-Coauthor | 1,282,468 | 5,179,996 | 1,219,320 | 3 | 119
Orkut | 3,072,441 | 117,184,899 | 2,270,456,447 | 20 | 51
As-Skitter | 1,696,415 | 11,095,298 | 37,322,355 | 19 | 67
Wiki-Talk | 2,394,385 | 4,659,565 | 86,333,306 | 13 | 26
Wikipedia | 1,870,709 | 36,532,531 | 131,652,971 | 6 | 31
LiveJournal | 4,033,137 | 27,933,062 | 38,413,665 | 29 | 214
Flickr | 2,302,925 | 22,838,276 | ¿ 400 billion | - | -
Ca-Cit-HepTh | 22,908 | 2,444,798 | ¿ 400 billion | - | -

###  6.2. Implementation of the Algorithms

In our parallel implementations of ${\tt ParTTT}$, ${\tt ParMCE}$, and ${\tt
ParIMCE}$, we utilize parallel_for and parallel_for_each, developed by the
Intel TBB parallel library (Blumofe and Leiserson, 1999). We also utilize
concurrent_hash_map for atomic operations on hashtable. We use C++11 standard
for the implementation of the algorithms and compile all the sources using
Intel ICC compiler version 18.0.3 with optimization level ‘-O3’. We use the
command ‘numactl -i all’ for balancing the memory in a NUMA machine. System
level load balancing is performed using a dynamic work stealing scheduler
(Blumofe and Leiserson, 1999) in TBB.

To compare with prior works on MCE, we implement some of them such as (Tomita
et al., 2006; Eppstein et al., 2010; Du et al., 2009; Svendsen et al., 2015;
Zhang et al., 2005) in C++, and we use the executable of the C++
implementations for the rest of the algorithms (${\tt GreedyBB}$ (San Segundo
et al., 2018), ${\tt Hashing}$ (Lessley et al., 2017), and ${\tt GP}$ (Wang et
al., 2017)), provided by the respective authors. See Subsection 6.4 for more
details.

We compute the degeneracy number and triangle count for each vertex using
sequential procedures. While the computation of per-vertex triangle counts and
the degeneracy ordering could be potentially parallelized, implementing a
parallel method to rank vertices based on their degeneracy number or triangle
count is itself a non-trivial task. We decided not to parallelize these
routines since the degeneracy- and triangle-based ordering did not yield
significant benefits when compared with degree-based ordering, whereas the
degree-based ordering is trivially available, without any additional
computation.

We assume that the entire graph is available in a shared global memory. The
Total Runtime (TR) of ${\tt ParMCE}$ consists of (1) Ranking Time (RT): the
time required to rank vertices of the graph based on the ranking metric used
in the algorithm, i.e. degree, degeneracy number, or triangle count of
vertices and (2) Enumeration Time (ET): the time required to enumerate all
maximal cliques. For ${\tt ParMCEDegen}$ and ${\tt ParMCETri}$ algorithms, the
runtime of ranking is also reported. Figures 6 and 7 show the parallel speedup
(with respect to the runtime of ${\tt TTT}$) and the enumeration time of ${\tt
ParMCE}$ using different vertex ordering strategies. Table 5 shows the
breakdown of the Total Runtime (TR) into Ranking Time (RT) and Enumeration
Time (ET).

The runtime of ${\tt ParIMCE}$ consists of (1) the computation time of ${\tt
ParIMCENew}$ and (2) the computation time of ${\tt ParIMCESub}$. In the
implementation of ${\tt ParIMCENew}$, we follow the design of ${\tt ParMCE}$
and instead of executing ${\tt ParTTTExcludeEdges}$ on the entire (sub)graph
for an edge as in Line 9 of ${\tt ParIMCENew}$, we run ${\tt
ParTTTExcludeEdges}$ on per-vertex sub-problems in parallel. For dealing with
load balance, we use degree based ordering of the vertices of
${G}^{\prime\prime}$ in creating the sub-problems. We decided to implement
${\tt ParIMCENew}$ in this way as we observed a significant improvement in the
performance of ${\tt ParMCE}$ over ${\tt ParTTT}$ when we used a degree-based
vertex ordering. For experiment on dynamic graphs, we use the batch size of
$1000$ edges for all the graphs except for an extremely dense graph Ca-Cit-
HepTh (with original graph density 0.01) where we use batch size of $10$.

###  6.3. Discussion of the Results

Here, we empirically evaluate our parallel algorithms and prior methods.
First, we show the parallel speedup (with respect to the sequential
algorithms) and scalability (with respect to the number of cores) of our
algorithms. Next, we compare our works with the state-of-the-art sequential
and parallel algorithms for MCE. The results demonstrate that our solutions
are faster than prior methods with significant margins.

####  6.3.1. Parallel MCE on Static Graphs

The total runtime of the parallel algorithms with $32$ threads are shown in
Table 4. We observe that ${\tt ParTTT}$ achieves a speedup of 5x-14x over the
sequential algorithm ${\tt TTT}$. The three versions of ${\tt ParMCE}$, i.e.
${\tt ParMCEDegree}$, ${\tt ParMCEDegen}$, ${\tt ParMCETri}$, achieve a
speedup of 15x-21x with 32 threads, when we consider the runtime of
enumeration task alone. The speedup ratio decreases in ${\tt ParMCEDegen}$ and
${\tt ParMCETri}$ if we include the time taken by ranking strategies (See
Figure 6).

The runtime of ${\tt ParTTT}$ is higher than the runtime of ${\tt ParMCE}$,
due to a heavier cumulative overhead of pivot computation and of processing
sets ${\tt cand}$ and ${\tt fini}$ in ${\tt ParTTT}$. For example, in DBLP-
Coauthor graph, when we run ${\tt ParTTT}$, the cumulative overhead of
computing ${\tt pivot}$ is 248 seconds, and the cumulative overhead of
updating ${\tt cand}$ and ${\tt fini}$ is 38 seconds while, in ${\tt ParMCE}$,
these runtimes are 156 and 21 seconds, respectively. This helps ${\tt ParMCE}$
accelerate the entire process, which achieves 2x speedup over ${\tt ParTTT}$.

Table 4. Runtime (in sec.) of ${\tt TTT}$, ${\tt ParTTT}$, and ${\tt ParMCE}$
with different vertex orderings on 32 cores. The numbers exclude the time
taken for vertex ordering. Note that the best algorithm, which uses degree
based vertex ordering, has zero additional cost for computing the vertex
ordering.

Dataset | ${\tt TTT}$ | ${\tt ParTTT}$ | ${\tt ParMCEDegree}$ | ${\tt ParMCEDegen}$ | ${\tt ParMCETri}$
---|---|---|---|---|---
DBLP-Coauthor | 42 | 4 | 2 | 3 | 3
Orkut | 28923 | 3472 | 1676 | 2350 | 1959
As-Skitter | 660 | 68 | 39 | 43 | 48
Wiki-Talk | 961 | 109 | 52 | 78 | 58
Wikipedia | 2646 | 160 | 123 | 155 | 179

|  |
---|---|---
(a) DBLP-Coauthor | (b) As-Skitter | (c) Wikipedia

|
---|---
(d) Wiki-Talk | (e) Orkut

Figure 6. Parallel speedup when compared with ${\tt TTT}$ (sequential algo.
due to Tomita et al. (Tomita et al., 2006)) as a function of the number of
threads.

|  |
---|---|---
(a) DBLP-Coauthor | (b) As-Skitter | (c) Wikipedia

|
---|---
(d) Wiki-Talk | (e) Orkut

Figure 7.  The total runtime of parallel algorithms ${\tt ParMCEDegree}$,
${\tt ParMCETri}$, ${\tt ParMCEDegen}$, and ${\tt ParTTT}$ in milliseconds as
a function of the number of threads.

|  |
---|---|---
(a) DBLP-Coauthor | (b) Flickr | (c) LiveJournal

|
---|---
(d) Ca-Cit-HepTh | (e) Wikipedia

Figure 8. Parallel speedup of ${\tt ParIMCE}$ over ${\tt IMCE}$ as a function
of the size of the change in the set of maximal cliques. The size of the
change is measured by the total number of new maximal cliques and subsumed
maximal cliques when a batch of edges is added to the graph.

|  |
---|---|---
(a) DBLP-Coauthor | (b) Flickr | (c) LiveJournal

|
---|---
(d) Ca-Cit-HepTh | (e) Wikipedia

Figure 9. Parallel speedup of ${\tt ParIMCE}$ over ${\tt IMCE}$ as a function
of number of threads, using the cumulative time of ${\tt ParIMCE}$ and of
${\tt IMCE}$ for processing all batches of edges.

Impact of vertex ordering on overall performance of ${\tt ParMCE}$. Here, we
study the impact of different vertex ordering strategies, i.e. degree,
degeneracy, and triangle count, on the overall performance of ${\tt ParMCE}$.
Table 5 presents the total computation time when we use different orderings.
We observe that degree-based ordering (${\tt ParMCEDegree}$) in most cases is
the fastest strategy for clique enumeration, even when we do not consider the
computation time for generating degeneracy- and triangle-based orderings. If
we add up the runtime for the ordering step, degree-based ordering is
obviously better than degeneracy- or triangle-based orderings since degree-
based ordering is available for free when the input graph is read, while the
degeneracy- and triangle-based orderings require additional computations.

Scaling up with the degree of parallelism. As the number of threads (and the
degree of parallelism) increases, the runtime of ${\tt ParMCE}$ and of ${\tt
ParTTT}$ decreases. Figure 6 presents the speedup factor of ${\tt ParMCE}$
over the state-of-the-art sequential algorithm, i.e. ${\tt TTT}$, as a
function of the number of threads, and Figure 7 presents the runtime of ${\tt
ParMCE}$. ${\tt ParMCEDegree}$ achieves a speedup of more than 15x on all
graphs, when $32$ threads are used.

Table 5. Total Runtime (in sec.) of ${\tt ParMCE}$ with different vertex
orderings (using 32 threads). Total Runtime (TR) = Ranking Time (RT) +
Enumeration Time (ET).

Dataset | ${\tt ParMCEDegree}$ | ${\tt ParMCEDegen}$ | ${\tt ParMCETri}$
---|---|---|---
RT | ET | TR | RT | ET | TR
DBLP-Coauthor | 3 | 25 | 3 | 28 | 42 | 3 | 45
Orkut | 1676 | 928 | 2350 | 3278 | 2166 | 1959 | 4125
As-Skitter | 39 | 41 | 43 | 84 | 122 | 48 | 170
Wiki-Talk | 52 | 23 | 78 | 101 | 74 | 58 | 132
Wikipedia | 123 | 244 | 155 | 399 | 950 | 179 | 1129

####  6.3.2. Parallel MCE on Dynamic Graphs

The cumulative runtime of ${\tt IMCE}$ and ${\tt ParIMCE}$ are presented in
Table 6 which shows that the speedup achieved by ${\tt ParIMCE}$ is 3.6x-19.1x
over ${\tt IMCE}$. This wide spectrum of speedups is mainly due to the
variations in the size of the changes in the set of maximal cliques (number of
new maximal cliques + number of subsumed maximal cliques) in the course of the
incremental computation which can be observed in Figure 8. From this plot, we
can see that the speedup increases with the increase in the size of the
changes in the set of maximal cliques. This trend is as expected because the
effect of parallelism will be prominent whenever the number of parallel tasks
will become sufficiently large. This happens when the number of new and
subsumed maximal cliques are large.

Table 6. Cumulative runtime (in sec.) over the incremental computation across
all edges, with ${\tt IMCE}$ and ${\tt ParIMCE}$ using 32 threads. The total
number of edges that are processed is also presented.

Dataset | #Edges Processed | ${\tt IMCE}$ | ${\tt ParIMCE}$ | Parallel Speedup
---|---|---|---|---
DBLP-Coauthor | 5.1M | 6608 | 933 | 7x
Flickr | 4.1M | 35238 | 2416 | 14.6x
Wikipedia | 36.5M | 9402 | 2614 | 3.6x
LiveJournal | 19.2M | 30810 | 2497 | 12.3x
Ca-Cit-HepTh | 93.8K | 33804 | 1767 | 19.1x

Scalability. The degree of parallelism increase with the increase in the
number of threads. From Figure 9 we can see that the speedup increases
linearly with the number of threads. This behavior shows the scalability of
our parallel algorithm ${\tt ParIMCE}$. When the size of the changes will
become large, scalability will become prominent because otherwise, most of the
processors will remain idle when there will not be large amount of parallel
tasks to fully utilize all the available processors. This is observed in
Wikipedia (Figure 9) where the cumulative size of change is relatively small.
Additionally, the speedup observed on different input graphs vary with the
similar size of change. For example, as we can see in Figure 8, LiveJournal
gives more speedup than Wikipedia with the size of change around $10^{5}$. To
explain this, we first note that higher parallel speedup is observed when the
cost of maintenance (which is proportional to the size of change in the set of
maximal cliques) on a single batch is high. Following this, we see that in
adding around $19$K batches of new edges (with batch size of $1000$ edges)
starting from the empty graph, LiveJournal has more frequent (around $2000$)
size of change in the order of $10^{5}$ compared to Wikipedia (around $100$
size of changes in the order of $10^{5}$).

###  6.4. Comparison with prior work

We compare the performance of ${\tt ParMCE}$ with prior sequential and
parallel algorithms for MCE. We consider the following sequential algorithms:
${\tt GreedyBB}$ due to Segundo et al. (San Segundo et al., 2018), ${\tt TTT}$
due to Tomita et al. (Tomita et al., 2006), and ${\tt BKDegeneracy}$ due to
Eppstein et al. (Eppstein et al., 2010). For the comparison with parallel
algorithm, we consider algorithm ${\tt CliqueEnumerator}$ due to Zhang et al.
(Zhang et al., 2005), ${\tt Peamc}$ due to Du et al. (Du et al., 2009), ${\tt
PECO}$ due to Svendsen et al. (Svendsen et al., 2015), and the most recent
parallel algorithm ${\tt Hashing}$ due to Lessley et al. (Lessley et al.,
2017). The parallel algorithms ${\tt CliqueEnumerator}$, ${\tt Peamc}$, and
${\tt Hashing}$ are designed for the shared-memory model, while ${\tt PECO}$
is designed for distributed memory. We modified ${\tt PECO}$ to work with
shared-memory, by reusing the method for sub-problem construction and
eliminating the need to communicate subgraphs by storing a single copy of the
graph in shared-memory. We consider three different ordering strategies for
${\tt PECO}$, which we call ${\tt PECODegree},{\tt PECODegen}$, and ${\tt
PECOTri}$. The comparison of performance of ${\tt ParMCE}$ with ${\tt PECO}$
is presented in Table 7. We note that ${\tt ParMCE}$ is significantly better
than that of ${\tt PECO}$, no matter which ordering strategy was considered.
We also compare the performance of ${\tt ParMCE}$ with a recent shared-nothing
parallel algorithm ${\tt GP}$ to show that ${\tt ParMCE}$ outperforms ${\tt
GP}$ with resources equivalent to our shared memory setting.

Table 7. Comparison of parallel runtime (in sec.) of ${\tt ParMCE}$, excluding
the time for computing vertex ranking, with a version of ${\tt PECO}$ that is
modified to use shared-memory with 32 threads. Three different variants are
considered for each algorithm based on the vertex ordering strategy.

Dataset | ${\tt PECODegree}$ | ${\tt ParMCEDegree}$ | ${\tt PECODegen}$ | ${\tt ParMCEDegen}$ | ${\tt PECOTri}$ | ${\tt ParMCETri}$
---|---|---|---|---|---|---
DBLP-Coauthor | 6.4 | 2.6 | 6.9 | 3.1 | 6.8 | 2.9
Orkut | 2050.7 | 1676.4 | 2183.4 | 2350 | 2361.9 | 1959.3
As-Skitter | 261.5 | 39.2 | 331.8 | 42.8 | 260.9 | 48.2
Wiki-Talk | 1729.7 | 51.6 | 1728.2 | 77.8 | 1720 | 57.6
Wikipedia | 8982.5 | 123.3 | 9110.4 | 155.3 | 8938 | 178.8

Table 8. Comparison of runtimes (in sec.) of ${\tt ParMCE}$ with prior works
on shared-memory algorithms for MCE (with 32 threads).

Dataset | ${\tt ParMCEDegree}$ | ${\tt Hashing}$ | ${\tt CliqueEnumerator}$ | ${\tt Peamc}$
---|---|---|---|---
DBLP-Coauthor | 2.6 | Out of memory in 3 min. | Out of memory in 10 min. | Not complete in 5 hours.
Orkut | 1676.4 | Out of memory in 7 min. | Out of memory in 20 min. | Not complete in 5 hours.
As-Skitter | 39.2 | Out of memory in 5 min. | Out of memory in 10 min. | Not complete in 5 hours.
Wiki-Talk | 51.6 | Out of memory in 10 min. | Out of memory in 20 min. | Not complete in 5 hours.
Wikipedia | 123.3 | Out of memory in 10 min. | Out of memory in 20 min. | Not complete in 5 hours.

Table 9.  Speedup factor of ${\tt ParMCEDegree}$ over ${\tt GP}$ and ${\tt
PECODegree}$. A speedup factor greater than $1$ indicates that our algorithm
${\tt ParMCEDegree}$ is faster than the prior methods. 8${}^{\text{\char 72}}$
indicates that 8 threads for ${\tt ParMCEDegree}$ and 8 MPI nodes for ${\tt
GP}$ are used (${}^{\text{\char 72}}$ next to other numbers is interpreted
similarly). ✘ indicates that ${\tt GP}$ runs out of memory.

| Speedup factor of ${\tt ParMCEDegree}$ over ${\tt GP}$ | Speedup factor of ${\tt ParMCEDegree}$ over ${\tt PECODegree}$
---|---|---
Dataset | 2${}^{\text{\char 72}}$ | 4${}^{\text{\char 72}}$ | 8${}^{\text{\char 72}}$ | 16${}^{\text{\char 72}}$ | 32${}^{\text{\char 72}}$ | 2 threads | 4 threads | 8 threads | 16 threads | 32 threads
DBLP-Coauthor | 0.83 | 1.21 | 1.76 | 2.9 | 4.1 | 2.5 | 2.85 | 2.4 | 2.33 | 2.5
Orkut | 1.92 | 1.68 | 1.73 | ✘ | ✘ | 1.2 | 1.11 | 1.04 | 0.85 | 1.48
As-Skitter | 1.66 | 1.64 | 1.56 | 1.71 | 1.35 | 4.47 | 4.33 | 3.92 | 4.1 | 3.26
Wiki-Talk | 1.38 | 1.32 | 1.15 | 1.3 | 0.84 | 2.48 | 2.37 | 4.65 | 9.07 | 10.9
Wikipedia | 1.5 | 1.45 | 1.44 | 1.86 | 1.69 | 9.6 | 9.74 | 14.07 | 25.34 | 29.6

The comparison of ${\tt ParMCE}$ with other shared-memory algorithms ${\tt
Peamc}$, ${\tt CliqueEnumerator}$, and ${\tt Hashing}$ is shown in Table 8.
The performance of ${\tt ParMCE}$ is seen to be much better than that of any
of these prior shared-memory parallel algorithms. For the graph DBLP-Coauthor,
${\tt Peamc}$ did not finish within $5$ hours whereas ${\tt ParMCE}$ takes at
most around $50$ secs for enumerating $1.2$ million maximal cliques. The poor
running time of ${\tt Peamc}$ is due to two following reasons: (1) The
algorithm does not apply efficient pruning techniques such as pivoting, used
in ${\tt TTT}$, and (2) The method to determine the maximality of a clique in
the search space is not efficient. The ${\tt CliqueEnumerator}$ algorithm runs
out of memory after a few minutes. The reason is that ${\tt CliqueEnumerator}$
maintains a bit vector for each vertex that is as large as the size of the
input graph and, additionally, needs to store intermediate non-maximal
cliques. For each such non-maximal clique, it is required to maintain a bit
vector of length equal to the size of the vertex set of the original graph.
Therefore, in ${\tt CliqueEnumerator}$, a memory issue is inevitable for a
graph with millions of vertices.

A recent parallel algorithm in the literature, ${\tt Hashing}$, also has a
significant memory overhead and ran out of memory on the input graphs that we
considered. The reason for its high memory requirement is that ${\tt Hashing}$
enumerates intermediate non-maximal cliques before finally outputting maximal
cliques. The number of such intermediate non-maximal cliques may be very
large, even for graphs with few number of maximal cliques. For example, a
maximal clique of size $c$ contains $2^{c}-1$ non-maximal cliques.

Table 10. Total runtime (sec.) of parallel algorithm ${\tt ParMCE}$ (with
different vertex ranking, with 32 threads) and sequential algorithms ${\tt
BKDegeneracy}$ and ${\tt GreedyBB}$.

Dataset | ${\tt BKDegeneracy}$ | ${\tt GreedyBB}$ | ${\tt ParMCEDegree}$ | ${\tt ParMCEDegen}$ | ${\tt ParMCETri}$
---|---|---|---|---|---
DBLP-Coauthor | 53.6 | Not finish in 30 min. | 2.6 | 28.1 | 44.3
Orkut | 29812.3 | Out of memory in 5 min. | 1676.4 | 3278 | 4125.3
As-Skitter | 641.7 | Out of memory in 10 min. | 39.2 | 83.8 | 170.2
Wiki-Talk | 1003.2 | Out of memory in 10 min. | 51.6 | 100.8 | 131.2
Wikipedia | 2243.6 | Out of memory in 10 min. | 123.3 | 399 | 1128

Next, we compare the performance of ${\tt ParMCE}$ with that of sequential
algorithms ${\tt BKDegeneracy}$ and a recent sequential algorithm ${\tt
GreedyBB}$ – results are in Table 10. For large graphs, the performance of
${\tt BKDegeneracy}$ is almost similar to ${\tt TTT}$ whereas ${\tt GreedyBB}$
performs much worse than ${\tt TTT}$. Since our ${\tt ParMCE}$ algorithm
outperforms ${\tt TTT}$, we can conclude that ${\tt ParMCE}$ is significantly
faster than other sequential algorithms.

Next, we compare with ${\tt GP}$ (Wang et al., 2017), a recent distributed
algorithm for MCE based on MPI. This method first assigns each vertex $v$ to
an MPI worker, and then the worker constructs subproblems of vertex $v$ by
constructing the sets ${\tt cand}$ and ${\tt fini}$ for enumerating the
maximal cliques which vertex $v$ is part of. Through an iterative computation,
each sub-problem is broken down into smaller sub-problems, till a maximal
clique is obtained. Subproblems within an MPI worker might be sent to another
worker, where the receiver MPI process is chosen randomly. We compare the
runtime performance of our work ${\tt ParMCEDegree}$ with of ${\tt GP}$. Note
that ${\tt ParMCEDegree}$ is a shared-memory method while ${\tt GP}$ is
implemented in a distributed memory model.

We ran ${\tt GP}$ and ${\tt ParMCEDegree}$ on a machine configured with two
$18$-core Intel Skylake $6140$ Xeon processors. In every experiment, we use
$192$GB as the total memory. For a fair comparison, we use the same number of
threads for ${\tt ParMCEDegree}$ as the number of MPI processes for ${\tt
GP}$. In Table 9, we report the speedup of ${\tt ParMCEDegree}$ over ${\tt
GP}$. In most cases ${\tt ParMCEDegree}$ outperforms ${\tt GP}$. In DBLP-
Coauthor, we observed that ${\tt GP}$ cannot achieve a better runtime while
the number of MPI workers increases. For a better understanding of this case,
we measured the runtime performance of exchanged sub-problems among MPI nodes
and the runtime of clique enumeration. We observed that the enumeration takes
at most one second while the overhead for exchanging sub-problems among
workers is huge and skewed towards a few MPI nodes, which leads to an
unbalanced workload. As shown in Table 9, there are two cases that ${\tt GP}$
performs faster than ${\tt ParMCEDegree}$ – in both cases, the difference in
runtimes is small, about 8 seconds.

###  6.5. Summary of Experimental Results

We found that both ${\tt ParTTT}$ and ${\tt ParMCE}$ yield significant
speedups over the sequential algorithm ${\tt TTT}$nearly linear in the number
of cores available. ${\tt ParMCE}$ using the degree-based vertex ranking
always performs better than ${\tt ParTTT}$. The runtime of ${\tt ParMCE}$
using degeneracy/triangle count based vertex ranking is sometimes worse than
${\tt ParTTT}$ due to the overhead of sequential computation of vertex ranking
– note that this overhead is not needed in ${\tt ParTTT}$. The parallel
speedup of ${\tt ParMCE}$ is better when the input graph has many large sized
maximal cliques. Overall, ${\tt ParMCE}$ consistently outperforms prior
sequential and parallel algorithms for MCE. For a dynamic graph we found that
${\tt ParIMCE}$ consistently yields a substantial speedup over the efficient
sequential algorithm ${\tt IMCE}$. Further, the speedup of ${\tt ParIMCE}$
improves as the size of the change (to be enumerated) becomes larger.

##  7\. Conclusion

We presented shared-memory parallel algorithms for enumerating maximal cliques
from a graph. ${\tt ParTTT}$ is a work-efficient parallelization of a
sequential algorithm due to Tomita et al. (Tomita et al., 2006), and ${\tt
ParMCE}$ is an adaptation of ${\tt ParTTT}$ that has more opportunities for
parallelization and better load balancing. Our algorithms obtain significant
improvements compared with the current state-of-the-art on MCE. Our
experiments show that ${\tt ParMCE}$ has a speedup of up to 21x (on a 32 core
machine) when compared with an efficient sequential baseline. In contrast,
prior shared-memory parallel methods for MCE were either unable to process the
same graphs in a reasonable time or ran out of memory. We also presented a
shared-memory parallel algorithm ${\tt ParIMCE}$ that can enumerate the change
in the set of maximal cliques when new edges are added to the graph.

Many questions remain open: (1) Can these methods scale to even larger graphs
and to machines with larger numbers of cores (2) How can one adapt these
methods to other parallel systems such as a cluster of computers with a
combination of shared and distributed memory or GPUs?

Acknowledgment: The work of AD, SS, and ST is supported in part by the US
National Science Foundation through grants 1527541 and 1725702.

## References

  * (1)
  * Avis and Fukuda (1993) David Avis and Komei Fukuda. 1993.  Reverse Search for Enumeration.  _Discrete Applied Mathematics_ 65 (1993), 21–46.
  * Blelloch and Maggs (2010) Guy E Blelloch and Bruce M Maggs. 2010.  Parallel algorithms. In _Algorithms and theory of computation handbook_. 25–25.
  * Blumofe (1995) Robert David Blumofe. 1995\.  _Executing multithreaded programs efficiently_.  Ph.D. Dissertation. Massachusetts Institute of Technology.
  * Blumofe and Leiserson (1999) Robert D Blumofe and Charles E Leiserson. 1999.  Scheduling multithreaded computations by work stealing.  _Journal of the ACM (JACM)_ 46, 5 (1999), 720–748.
  * Bron and Kerbosch (1973) Coen Bron and Joep Kerbosch. 1973.  Algorithm 457: finding all cliques of an undirected graph.  _CACM_ 16, 9 (1973), 575–577.
  * Cazals and Karande (2008) Frédéric Cazals and Chinmay Karande. 2008.  A note on the problem of reporting maximal cliques.  _TCS_ 407, 1 (2008), 564–568.
  * Chateau et al. (2011) Annie Chateau, Pierre Riou, and Eric Rivals. 2011.  Approximate common intervals in multiple genome comparison. In _Bioinformatics and Biomedicine (BIBM), 2011 IEEE International Conference on_. IEEE, 131–134.
  * Chen and Crippen (2005) Yu Chen and Gordon M Crippen. 2005.  A novel approach to structural alignment using realistic structural and environmental information.  _Protein science_ 14, 12 (2005), 2935–2946.
  * Chiba and Nishizeki (1985) Norishige Chiba and Takao Nishizeki. 1985.  Arboricity and subgraph listing algorithms.  _SIAM J. Comput._ 14 (1985), 210–223.  Issue 1.
  * Conte et al. (2018) Alessio Conte, Tiziano De Matteis, Daniele De Sensi, Roberto Grossi, Andrea Marino, and Luca Versari. 2018.  D2K: Scalable Community Detection in Massive Networks via Small-Diameter k-Plexes. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. ACM, 1272–1281.
  * Conte et al. (2016) Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. 2016.  Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques. In _43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)_ , Vol. 148. 1–148.
  * Das et al. (2018) Apurba Das, Seyed-Vahid Sanei-Mehri, and Srikanta Tirthapura. 2018\.  Shared-memory parallel maximal clique enumeration. In _2018 IEEE 25th International Conference on High Performance Computing (HiPC)_. IEEE, 62–71.
  * Das et al. (2019) Apurba Das, Michael Svendsen, and Srikanta Tirthapura. 2019\.  Incremental maintenance of maximal cliques in a dynamic graph.  _The VLDB Journal_ (Apr 2019).
  * Dasari et al. (2014) Naga Shailaja Dasari, Ranjan Desh, and Mohammad Zubair. 2014\.  ParK: An efficient algorithm for k-core decomposition on multicore processors. In _Big Data_. IEEE, 9–16.
  * Du et al. (2006) Nan Du, Bin Wu, Liutong Xu, Bai Wang, and Xin Pei. 2006.  A parallel algorithm for enumerating all maximal cliques in complex network. In _ICDM Workshop_. IEEE, 320–324.
  * Du et al. (2009) Nan Du, Bin Wu, Liutong Xu, Bai Wang, and Pei Xin. 2009.  Parallel algorithm for enumerating maximal cliques in complex network.  In _Mining Complex Data_. Springer, 207–221.
  * Duan et al. (2012) Dongsheng Duan, Yuhua Li, Ruixuan Li, and Zhengding Lu. 2012\.  Incremental K-clique clustering in dynamic social networks.  _Artificial Intelligence Review_ (2012), 1–19.
  * Eppstein et al. (2010) David Eppstein, Maarten Löffler, and Darren Strash. 2010\.  Listing all maximal cliques in sparse graphs in near-optimal time. In _ISAAC_. 403–414.
  * Eppstein and Strash (2011) David Eppstein and Darren Strash. 2011.  Listing All Maximal Cliques in Large Sparse Real-World Graphs.  In _Experimental Algorithms_. Vol. 6630. 364–375.
  * Fox et al. (2018) James Fox, Tim Roughgarden, C Seshadhri, and Fan Wei. 2018.  Finding Cliques in Social Networks: A New Distribution-Free Model.  _SIAM journal on computing_ (2018).
  * Grindley et al. (1993) Helen M Grindley, Peter J Artymiuk, David W Rice, and Peter Willett. 1993.  Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm.  _JMB_ 229, 3 (1993), 707–721.
  * Hattori et al. (2003) Masahiro Hattori, Yasushi Okuno, Susumu Goto, and Minoru Kanehisa. 2003.  Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways.  _JACS_ 125, 39 (2003), 11853–11865.
  * Johnson et al. (1988) David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou. 1988\.  On generating all maximal independent sets.  _Inform. Process. Lett._ 27, 3 (1988), 119–123.
  * Jonsson and Bates (2006) Pall F Jonsson and Paul A Bates. 2006.  Global topological features of cancer proteins in the human interactome.  _Bioinformatics_ 22, 18 (2006), 2291–2297.
  * Kabir and Madduri (2017a) Humayun Kabir and Kamesh Madduri. 2017a.  Parallel k-core decomposition on multicore platforms. In _IPDPS Workshop_. IEEE, 1482–1491.
  * Kabir and Madduri (2017b) Humayun Kabir and Kamesh Madduri. 2017b.  Parallel k-truss decomposition on multicore systems. In _HPEC_. 1–7.
  * Kabir and Madduri (2017c) Humayun Kabir and Kamesh Madduri. 2017c.  Shared-memory graph truss decomposition. In _High Performance Computing (HiPC), 2017 IEEE 24th International Conference on_. IEEE, 13–22.
  * Koch (2001) Ina Koch. 2001.  Enumerating all connected maximal common subgraphs in two graphs.  _TCS_ 250, 1 (2001), 1–30.
  * Koichi et al. (2014) Shungo Koichi, Masaki Arisaka, Hiroyuki Koshino, Atsushi Aoki, Satoru Iwata, Takeaki Uno, and Hiroko Satoh. 2014.  Chemical structure elucidation from 13C NMR chemical shifts: Efficient data processing using bipartite matching and maximal clique algorithms.  _JCIM_ 54, 4 (2014), 1027–1035.
  * Koller and Friedman (2009) D Koller and N Friedman. 2009.  _Probabilistic Graphical Models: Principles and Techniques_.  MIT Press.
  * Kose et al. (2001) Frank Kose, Wolfram Weckwerth, Thomas Linke, and Oliver Fiehn. 2001.  Visualizing plant metabolomic correlation networks using clique-metabolite matrices.  _Bioinformatics_ 17, 12 (2001), 1198–1208.
  * Kunegis (2013) Jérôme Kunegis. 2013\.  Konect: the koblenz network collection. In _WWW_. ACM, 1343–1350.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Lessley et al. (2017) Brenton Lessley, Talita Perciano, Manish Mathai, Hank Childs, and E Wes Bethel. 2017.  Maximal Clique Enumeration with Data-Parallel Primitives. In _LDAV_. IEEE, 16–25.
  * Li et al. (2019) Yinuo Li, Zhiyuan Shao, Dongxiao Yu, Xiaofei Liao, and Hai Jin. 2019.  Fast Maximal Clique Enumeration for Real-World Graphs. In _International Conference on Database Systems for Advanced Applications_. Springer, 641–658.
  * Liu and Wong (2008) Guimei Liu and Limsoon Wong. 2008.  Effective pruning techniques for mining quasi-cliques. In _Joint European conference on machine learning and knowledge discovery in databases_. Springer, 33–49.
  * Lu et al. (2010) Li Lu, Yunhong Gu, and Robert Grossman. 2010.  dmaximalcliques: A distributed algorithm for enumerating all maximal cliques and maximal clique distribution. In _ICDM Workshop_. IEEE, 1320–1327.
  * Makino and Uno (2004) Kazuhisa Makino and Takeaki Uno. 2004.  New algorithms for enumerating all maximal cliques.  In _SWAT_. 260–272.
  * Mohseni-Zadeh et al. (2004) S Mohseni-Zadeh, Pierre Brézellec, and J-L Risler. 2004\.  Cluster-C, an algorithm for the large-scale clustering of protein sequences based on the extraction of maximal cliques.  _Comp. Biol. Chem._ 28, 3 (2004), 211–218.
  * Montresor et al. (2013) Alberto Montresor, Francesco De Pellegrini, and Daniele Miorandi. 2013.  Distributed k-core decomposition.  _TPDS_ 24, 2 (2013), 288–300.
  * Moon and Moser (1965) John W Moon and Leo Moser. 1965.  On cliques in graphs.  _Israel J. Math._ 3, 1 (1965), 23–28.
  * Mukherjee and Tirthapura (2017) Arko Provo Mukherjee and Srikanta Tirthapura. 2017.  Enumerating Maximal Bicliques from a Large Graph Using MapReduce.  _IEEE Trans. Services Computing_ 10, 5 (2017), 771–784.
  * Ottosen and Vomlel (2010) Thorsten J Ottosen and Jirı Vomlel. 2010.  Honour thy neighbour: clique maintenance in dynamic graphs. In _PGM_. 201–208.
  * Palla et al. (2005) Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. 2005.  Uncovering the overlapping community structure of complex networks in nature and society.  _Nature_ 435, 7043 (2005), 814–818.
  * Qin et al. (2019) Hongchao Qin, Rong-Hua Li, Guoren Wang, Lu Qin, Yurong Cheng, and Ye Yuan. 2019\.  Mining Periodic Cliques in Temporal Networks. In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_. IEEE, 1130–1141.
  * Rokhlenko et al. (2007) Oleg Rokhlenko, Ydo Wexler, and Zohar Yakhini. 2007\.  Similarities and differences of gene expression in yeast stress conditions.  _Bioinformatics_ 23, 2 (2007), e184–e190.
  * Rossi and Ahmed (2015) Ryan A. Rossi and Nesreen K. Ahmed. 2015.  The Network Data Repository with Interactive Graph Analytics and Visualization. In _AAAI_. 4292–4293.
  * San Segundo et al. (2018) Pablo San Segundo, Jorge Artieda, and Darren Strash. 2018\.  Efficiently enumerating all maximal cliques with bit-parallelism.  _Computers & Operations Research_ 92 (2018), 37–46.
  * Sanei-Mehri et al. (2018) Seyed-Vahid Sanei-Mehri, Apurba Das, and Srikanta Tirthapura. 2018\.  Enumerating top-k quasi-cliques. In _2018 IEEE International Conference on Big Data (Big Data)_. IEEE, 1107–1112.
  * Sariyuce et al. (2017) Ahmet Erdem Sariyuce, C Seshadhri, and Ali Pinar. 2017\.  Parallel local algorithms for core, truss, and nucleus decompositions.  _arXiv preprint arXiv:1704.00386_ (2017).
  * Schmidt et al. (2009) Matthew C Schmidt, Nagiza F Samatova, Kevin Thomas, and Byung-Hoon Park. 2009.  A scalable, parallel algorithm for maximal clique enumeration.  _JPDC_ 69, 4 (2009), 417–428.
  * Shalev and Shavit (2006) Ori Shalev and Nir Shavit. 2006.  Split-ordered lists: Lock-free extensible hash tables.  _Journal of the ACM (JACM)_ 53, 3 (2006), 379–405.
  * Shun (2017) Julian Shun. 2017\.  _Shared-memory parallelism can be simple, fast, and scalable_.  Morgan & Claypool.
  * Stix (2004) Volker Stix. 2004\.  Finding all maximal cliques in dynamic graphs.  _Comput. Optim. Appl._ 27, 2 (2004), 173–186.
  * Svendsen et al. (2015) Michael Svendsen, Arko Provo Mukherjee, and Srikanta Tirthapura. 2015.  Mining maximal cliques from a large graph using mapreduce: Tackling highly uneven subproblem sizes.  _JPDC_ 79 (2015), 104–114.
  * Tomita et al. (2006) Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006\.  The worst-case time complexity for generating all maximal cliques and computational experiments.  _TCS_ 363, 1 (2006), 28–42.
  * Tsukiyama et al. (1977) Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. 1977.  A new algorithm for generating all the maximal independent sets.  _SIAM J. Comput._ 6, 3 (1977), 505–517.
  * Uno (2010) Takeaki Uno. 2010\.  An efficient algorithm for solving pseudo clique enumeration problem.  _Algorithmica_ 56, 1 (2010), 3–16.
  * Wang et al. (2017) Zhuo Wang, Qun Chen, Boyi Hou, Bo Suo, Zhanhuai Li, Wei Pan, and Zachary G Ives. 2017.  Parallelizing maximal clique and k-plex enumeration over graph data.  _J. Parallel and Distrib. Comput._ 106 (2017), 79–91.
  * Wu et al. (2009) Bin Wu, Shengqi Yang, Haizhou Zhao, and Bai Wang. 2009\.  A distributed algorithm to enumerate all maximal cliques in mapreduce. In _FCST_. IEEE, 45–51.
  * Yu and Liu (2019) Ting Yu and Mengchi Liu. 2019.  A Memory Efficient Clique Enumeration Method for Sparse Graphs with a Parallel Implementation.  _Parallel Comput._ (2019).
  * Yuan et al. (2017) Long Yuan, Lu Qin, Wenjie Zhang, Lijun Chang, and Jianye Yang. 2017.  Index-based densest clique percolation community search in networks.  _IEEE Transactions on Knowledge and Data Engineering_ 30, 5 (2017), 922–935.
  * Zhang et al. (2008) Bing Zhang, Byung-Hoon Park, Tatiana Karpinets, and Nagiza F Samatova. 2008.  From pull-down data to protein interaction networks and complexes with biological relevance.  _Bioinformatics_ 24, 7 (2008), 979–986.
  * Zhang et al. (2019) Chen Zhang, Ying Zhang, Wenjie Zhang, Lu Qin, and Jianye Yang. 2019.  Efficient Maximal Spatial Clique Enumeration. In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_. IEEE, 878–889.
  * Zhang et al. (2005) Yun Zhang, Faisal N Abu-Khzam, Nicole E Baldwin, Elissa J Chesler, Michael A Langston, and Nagiza F Samatova. 2005.  Genome-scale computational approaches to memory-intensive applications in systems biology. In _SC_. IEEE Computer Society, 12.

##  Appendix A Proof of Work Efficiency of parallel MCE on Dynamic Graph

Here, we show the work efficiency of ${\tt ParIMCE}$ by proving Lemma 5.1.

Input: ${G}$ \- The input graph

$K$ \- a non-maximal clique to extend

${\tt cand}$ \- Set of vertices that may extend $K$

${\tt fini}$ \- vertices that have been used to extend $K$

$\mathcal{E}$ \- set of edges to ignore

1 if  _$({\tt cand}=\emptyset)$ & $({\tt fini}=\emptyset)$_ then

2 Output $K$ and return

3

4${\tt pivot}\leftarrow(u\in{\tt cand}\cup{\tt fini})$ such that $u$ maximizes
the size of the intersection of ${\tt cand}\cap\Gamma_{{G}}(u)$

5 ${\tt ext}\leftarrow{\tt cand}-\Gamma_{{G}}({\tt pivot})$

6 for  _$q\in$ ext_ do

7 $K_{q}\leftarrow K\cup\\{q\\}$

8 if  _$K_{q}\cap\mathcal{E}\neq\emptyset$_ then

9 ${\tt cand}\leftarrow{\tt cand}-\\{q\\}$

10 ${\tt fini}\leftarrow{\tt fini}\cup\\{q\\}$

11 continue

12 ${\tt cand}_{q}\leftarrow{\tt cand}\cap\Gamma_{{G}}(q)$

13 ${\tt fini}_{q}\leftarrow{\tt fini}\cap\Gamma_{{G}}(q)$

14 ${\tt{TTTExcludeEdges}}({G},K_{q},{\tt cand}_{q},{\tt
fini}_{q},\mathcal{E})$

15 ${\tt cand}\leftarrow{\tt cand}-\\{q\\}$

16 ${\tt fini}\leftarrow{\tt fini}\cup\\{q\\}$

17

Algorithm 8 ${\tt{TTTExcludeEdges}}({G},K,{\tt cand},{\tt fini},\mathcal{E})$

Lemma 5.1: Given a graph $G$ and a new edge set $H$, ${\tt ParIMCENew}$ is
work-efficient, i.e, the total work is of the same order of the time
complexity of ${\tt FastIMCENewClq}$. The depth of ${\tt ParIMCENew}$ is
$O(\Delta^{2}+M\log{\Delta})$ where $\Delta$ is the maximum degree and $M$ is
the size of a maximum clique in $G+H$.

###### Proof.

First, we prove the work efficiency of ${\tt ParIMCENew}$ followed by the
depth of the algorithm. Note that, for proving the work-efficiency we will
show that procedure at each line from Line 4 to Line 10 of ${\tt ParIMCENew}$
is work-efficient. Lines 4, 6, 7, and 8 are work-efficient because, all these
procedures are sequential in ${\tt ParIMCENew}$. The parallel set operations
at Line 5 and Line 10 are work-efficient using Theorem 3.1. Now we will show
the work efficiency of ${\tt ParTTTExcludeEdges}$ as follows. If we disregard
Lines 7-10 of ${\tt{TTTExcludeEdges}}$ and Lines 9-10 of ${\tt
ParTTTExcludeEdges}$ then the total work of ${\tt ParTTTExcludeEdges}$ is the
same as the time complexity of ${\tt ParTTT}$ following the work efficiency of
${\tt ParTTT}$. Next, we say that the time complexity of Lines 7-10 of
${\tt{TTTExcludeEdges}}$ is the same as the time complexity of Lines 9-10 of
${\tt ParTTTExcludeEdges}$ because in ${\tt{TTTExcludeEdges}}$ we use two
global hashtables - one for maintaining the adjacent vertices of the currently
processing vertex in the set of new edges and another for maintaining the
indexes of the new edges that we define before the beginning of the
enumeration of new maximal cliques. With these two hashtables, we can check
the if condition at Line 9 of ${\tt ParTTTExcludeEdges}$ in parallel with
total work $O(n)$ using Theorem 3.1 which is of the same order of the time
complexity of performing if condition check at Line 7 of
${\tt{TTTExcludeEdges}}$. This completes the proof of work efficiency of ${\tt
ParTTTExcludeEdges}$. For proving the depth of ${\tt ParIMCENew}$, note that
the depth is the sum of the depths of procedures at Line 5, 6, 9, 10 of ${\tt
ParIMCENew}$ because the cost of all operations in other lines are $O(1)$
each. The depth of executing intersection in parallel at Line 5 is $O(1)$
using Theorem 3.1, the depth of the procedure for constructing the graph at
Line 6 is $O(\Delta^{2})$ as we construct the graph sequentially, the depth
${\tt ParTTTExcludeEdges}$ is $O(M\log{\Delta})$ following the depth of
${\tt{TTTExcludeEdges}}$, and the depth of Line 10 is $O(1)$ because we can do
this operation in parallel using Theorem 3.1. Thus, the overall depth of ${\tt
ParIMCENew}$ follows. ∎