Clique Enumeration#

A clique in a graph is a fully connected subgraph. It is maximal if it is not contained in a larger clique. The goal of clique enumeration is to compute a list of all maximal cliques of a given graph.

Example of enumerating all
maximal cliques. — page 1 — Example of enumerating all maximal cliques.

Example of enumerating all
maximal cliques. — page 2 — Example of enumerating all maximal cliques.

Note that the problem is equivalent to enumerating maximal independent sets on the complement graph.

It’s Hard#

The number of maximal cliques $\alpha$ of a graph can be exponential. When removing the edges of $\frac{n}{3}$ disjoint triangles from the complete graph $K_n$ ($n$ divisible by $3$), then one obtains a maximal clique by selecting exactly one vertex for each of the $\frac{n}{3}$ triangles, yielding $\alpha = 3^{n / 3} \approx 1.44^n$ maximal cliques. This bound is tight [7].

One can enumerate all maximal cliques in $O(3^{n / 3})$ time [8]. This is worst-case optimal as it matches the above bound. Thus, one cannot get better bounds that only depend on the input size. When considering dependence on the output size $\alpha$, the best known bounds are:

$\alpha \cdot O(n \bar{m})$ [9] ($\bar{m}$: number of edges in the complement)
$\alpha \cdot O(n m)$ [10] (using that graphs have arboricity $O(n)$)
$\alpha \cdot O(n^{2.094})$ [11] ($2.094$ comes from rectangular matrix multiplication)

All three bounds are delay bounds, i.e., the time between outputting solutions is in $O(n \bar{m})$, $O(n m)$, and $O(n^{2.094})$, respectively.

Typical Inputs#

It is probably fair to say that real-world networks are an important type of input for enumerating cliques.

There are probably other applications or problems where it could be useful to know all maximal cliques. It would be nice to have a collection of instances coming from such applications.

Too Easy!#

The algorithm in [12] only needs seconds to enumerate all cliques of graphs millions of vertices and edges. Here are just two examples:

On the network web-Google with 875 k vertices and 4.3 M edges, all 1.4 M maximal cliques are enumerated in under 10 s.
On the network cit-Patents with 3.8 M vertices and 16.5 M edges, all 14.8 M maximal cliques are enumerated in under 30 s.

Observe that the number of cliques in these examples is far from being exponential. In fact, there are less maximal cliques than edges in both cases. These are not outliers. In experiments on 2740 real-world networks, the vast majority of 2552 networks have at most $m$ maximal cliques [1], while only 188 networks have more maximal cliques than edges.

But even given that the number of maximal cliques is so low, worst-case bounds of $O(nm)$ or $O(n^{2.094})$ per clique are way to pessimistic.

WTF?#

The paper [12] is actually great in that in not only provides the practically highly efficient algorithm but also a tight parameterized analysis. See the discussion for parameterized results below.

Parameterized by Sparsity#

Multiple parameters have been considered, all in some way related to sparsity. For a better overview, here a list of parameters used in the following:

symbol	parameter
$n$	number of vertices
$m$	number of edges
$\alpha$	number of maximal cliques
$\omega$	size of largest clique
$\Delta$	maximum degree
$a$	arboricity The minimum number of forests into which the edges can be partitioned.
$d$	degeneracy The minimum number $d$ such that every subgraph has maximum degree at most $d$. In other words, there is an order of vertices such that deleting the vertices in this order never deletes a vertex with degree larger than $d$.
$c$	weak closure The closure captures the property that vertices with many common neighbors are connected. Formally, call a vertex $v$ is $c$-deletable if there is no non-adjacent vertex $u$ that has at least $c$ common neighbors with $v$. A graph is weakly $c$-closed if exhaustively deleting $c$-deletable vertices results in the empty graph. The weak closure $c$ is the minimum number for which the graph is weakly $c$-closed.

The following table shows results on parameterized enumeration times. The note “delay” means that if the enumeration is $\alpha\cdot T$, then at most $T$ time elapses between outputting two solutions.

enumeration time	note	paper
$O(dn 3^{d / 3})$	$\alpha \le (n - d) 3^{d / 3}$	[12]
$\alpha \cdot O(\mathrm{poly}(d))$		[15]
$\alpha \cdot O(n \mathrm{poly}(c))$	$\alpha \le 3^{(c - 1)/3} n^2$	[16, 17]
$\alpha \cdot O(am)$	delay	[10]
$\alpha \cdot O(\Delta^4)$	delay	[18]
$\alpha \cdot \tilde O(\omega d(\Delta + \omega d))$	delay	[19]
$\alpha \cdot O(\min\{md, \omega d\Delta\})$	delay	[19]

There is probably a lot to say for each individual result. To keep it non-repetitive, I’ll focus on the degeneracy bound in [12] (which seems most relevant as the algorithm is highly efficient in practice) and discuss the other bounds where interesting.

Insight#

Enumerating cliques is fast on sparse graphs.

Explanatory power#

I think this already provides a rather good high-level explanation for the good performance in practice. Here are some highlights:

Good upper bound for specifically the algorithm that is fast in practice [12].

Multiple of the papers check whether the considered are reasonably small in real-world networks.

For the 188 networks in [1] that have more than $m$ cliques, there is a strong positive correlation between the degeneracy and the number of cliques. The bound in [12] seems to be a great fit here.

Limitations#

Experiments with 2740 real-world networks [1] show that the density-explanation (while fitting for 188 networks) is not satisfying for the vast majority of 2552 networks that have less than $m$ cliques:

The exponential upper bound with respect to the degeneracy is too pessimistic to explain less than $m$ maximal cliques.

There is no (or in fact slight negative) correlation with the degeneracy.

There is a strong correlation with locality, i.e., graphs with high locality tend to have fewer maximal cliques (more details).

While the weak closure $c$ in theory captures the concept of locality, there is no correlation. In practice, the weak closure and degeneracy are essentially the same, with degeneracy being usually only a small factor larger than $c - 1$.

Even accepting that the number of maximal cliques $\alpha$ is very small, does not explain enumerating 1.4 M and 14.8 M cliques in under 10 s and 30 s, respectively:

The bound in [12] is not output-sensitive, unless $\alpha$ matches the upper bound, which is exponential in $d$.

The other bounds have rather high cost per clique. The bound of $O(\mathrm{poly}(d))$ per clique [15] is the most reasonable but still too pessimistic for the practical observations.

Probabilistic Network Models#

The experiments in [1] study the number of maximal cliques depending on locality and heterogeneity, comparing generated graphs with real-world networks.

Locality, heterogeneity, and graph models.

The locality of a graph measures how distant the endpoints of an edge are in the rest of the graph. Think of high locality as: the graph has an underlying geometry, it has many triangles, there is a high dependence between the edges.

The heterogeneity of a graph describes the variance of the degree distribution. Road networks are homogeneous with all vertices having roughly the same degree. Social networks tend to be heterogeneous with low average degree and a heavy tail of few high-degree vertices (think power-law).

The experiment setup in [1] is roughly as follows. Generate graphs with varying locality and heterogeneity (and constant average degree). Locality is achieved with an underlying geometry. Heterogeneity is achieved with connection probabilities depending on vertex weights. This essentially provides a clean lab-environment, where one can observe how the running time of algorithms changes depending on locality and heterogeneity in isolation from other graph properties. These experiments on generated graphs are complemented and compared with experiments on a large number of real-world networks from different domains.

Insight#

We can expect sparse graphs to have at most $m$ maximal cliques. The exact number depends on the locality: Graphs without locality have close to $m$ maximal cliques and this number shrinks with increasing locality.

The above insight is purely based on experiments [1]. There is also a theoretical analysis for hyperbolic random graphs [22] and geometric inhomogeneous random graphs [23]; network models with locality and heterogeneity. We note that these theoretical bounds for the models seem to disagree with the previous experiments on the same models.

Insight#

We can expect graphs with graphs locality and a heterogeneous degree distribution to have a super-polynomial number of maximal cliques.

Explanatory Power#

The models fit exceptionally well to the large majority of 2552 out of 2740 real-world networks:

They consistently have at most $m$ maximal cliques.

When representing the number of maximal cliques as $\alpha = x \cdot m$, then even the value of $x$ (which decreases for increasing locality) is consistent between the models and the real-world networks.

Limitations#

This can only explain the number of maximal cliques. It does not explain why the algorithm does also find them efficiently.

There are still the remaining 188 real-world networks, with different behavior. We do not know the difference between them.

Asymptotics are broken here: While the models agree with the real world in experiments, the asymptotic analysis seems to contradict these observations. The reason for this is that the super-polynomial growth only supersedes the linear terms for really large graphs.

References#

On the External Validity of Average-case Analyses of Graph Algorithms by Thomas Bläsius, Philipp Fischbeck (2023)
On cliques in graphs by J. W. Moon, Leo Moser (1965)
The worst-case time complexity for generating all maximal cliques and computational experiments by Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi (2006)
A New Algorithm for Generating All the Maximal Independent Sets by Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa (1977)
Arboricity and Subgraph Listing Algorithms by Norishige Chiba, Takao Nishizeki (1985)
An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication by Carlo Comin, Roméo Rizzi (2018)
Listing All Maximal Cliques in Large Sparse Real-World Graphs by David Eppstein, Maarten Löffler, Darren Strash (2013)
A new decomposition technique for maximal clique enumeration for sparse graphs by George Manoussakis (2018)
Finding Cliques in Social Networks: A New Distribution-Free Model by Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, Nicole Wein (2020)
Efficient maximal cliques enumeration in weakly closed graphs by George Manoussakis (2023)
New Algorithms for Enumerating All Maximal Cliques by Kazuhisa Makino, Takeaki Uno (2004)
Sublinear-Space and Bounded-Delay Algorithms for Maximal Clique Enumeration in Graphs by Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari (2019)
On the Number of Maximal Cliques in Two-Dimensional Random Geometric Graphs: Euclidean and Hyperbolic by Hodaka Yamaji (2023)
Maximal cliques in scale-free random graphs by Thomas Bläsius, Maximilian Katzmann, Clara Stegehuis (2024)