An Efficient Algorithm for Enumerating Pseudo
Cliques
Takeaki Uno
National Institute of Informatics
2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan, uno@nii.jp
Abstract. The problem of finding dense structures in a given graphis quite basic in informatics including data mining and data engineering. Clique is a popular model to represent dense structures, and widelyused because of its simplicity and ease in handling. Pseudo cliques arenatural extension of cliques which are subgraphs obtained by removing
small number of edges from cliques. We here define a pseudo clique by
a subgraph such that the ratio of the number of its edges compared tothat of the clique with the same number of vertices is no less than agiven threshold value. In this paper, we address the problem of enumerating all pseudo cliques for given a graph and a threshold value. We
first show that it seems to be difficult to obtain polynomial time algorithms using straightforward divide and conquer approaches. Then, we
propose a polynomial time, polynomial delay in precise, algorithm basedon reverse search. We show the efficiency of our algorithm in practice bycomputational experiments.

1

Introduction

Let us consider the problem of finding dense structures from a given graph, i.e.,
finding vertex induced subgraphs including many edges. In graphs representing
similarity or relation, dense structures can be considered to represent groupsof similar objects or deeply related objects. Thus, the problem is important inmany scientific areas. This is especially true in data engineering and data mining,where it is one of basic problems, and has many applications such as clustering,
community discovering, machine learning, Web search, etc. [1, 6, 8–11, 14, 20]. A
clique is a subgraph that is a complete graph. It is a fundamental structure
for representing dense structures. It has several good mathematical properties,
and can be easily handled. As a result, clique detection has been used in many
researches. Cliques are considered as a part of dense structures, or seeds of dense
structures. The clique enumeration can be efficiently carried out thanks to theincrease of computation power, and new algorithms[12, 16]. Currently, the bottle
neck of the computation in the practice is usually the output process, thus thealgorithm is almost optimal.
Then, as a next step, people wanted to use a richer model than cliques. Invery sparse graphs, a subgraph containing only small cliques can be considered
as a dense structure if it has many edges when compared to the others. If thedata is incorrect so that some edges are missing, then a vertex set should be a

clique will not be a clique. For robust computation, “pseudo cliques” should be
used. For example, such pseudo cliques are used for web page clustering[9].
We can consider several models to represent pseudo cliques. A possible model
is a subgraph that is obtained from a clique by removing at most θ edges, whereθ is a given threshold constant number. An advantage of this model is that in thisdefinition any subset of a pseudo clique is also a pseudo clique in the sense of thevertex subset, thus the family of pseudo cliques satisfies the monotone property.
This is a useful property, and we can use many techniques in the literatures todevelop an efficient algorithm. However, a disadvantage of the model is that forgraphs of any size the threshold is the same, thus larger subgraphs can lose onlya small portion of its edges. This is contrary to the intuitions. Moreover, so manysmall vertex sets will become pseudo cliques.
Another model is to define a pseudo clique by a subgraph that has at least
a constant ratio of edges compared to a clique of the same size. Precisely, wedefine the density of a subgraphs by the number of edges over the number of allits vertex pairs. A subgraph is a pseudo clique if its density is no less than thegiven threshold value. In this definition, the family of pseudo cliques no longer
satisfies the monotone property. It is a disadvantage of this definition. On theother hand, small subgraphs are pseudo cliques only if they are cliques, since
the limitation of the number of edge removals changes as the size of subgraphs.
This is an advantage of this definition.
In the literatures, a subgraph having many edges compared to the numberof its vertices is often called dense subgraph, heavy graph, or maximum edge
subgraph. However, all these terms are used to represent the subgraph having thehighest ratio of edges, thus it is mainly used in optimization. On the other hand,in many areas in informatics, a subgraph having many edges thereby similar toclique is often called a “pseudo clique” or “quasi clique”. In this paper, we use
the term pseudo clique.
The problem of maximizing the density among subgraphs of given size k
is NP-complete since it includes the maximum clique problem as its special
case[4]. However, if k = Θ(|V |) holds, there is a PTAS algorithm[2]. For theedge weighted version, an O(|V |1/3−² ) approximation algorithm is known[4].
However, finding an induced subgraph maximizing average degree in it can besolved in polynomial time[4].
In this paper, we address the enumeration problem of all pseudo cliques in agiven graph. We choose the latter definition for pseudo cliques. We first show theexistence of polynomial delay algorithm is non-trivial, by proving that straightforward back-tracking (branch-and-bound) approaches involve an NP-complete
problem in each iteration. Note that it does not assure that non-existence of
output polynomial time algorithm even when P 6= N P .
In contrast, a reverse search works well for this problem. We will show thatfor any pseudo clique, one of its vertex satisfies that its removal is also a pseudoclique. From this, we can obtain an adjacency relation on pseudo cliques spanning
all the pseudo cliques. Then we define a tree-shaped traversal route on all pseudocliques by this adjacency. Our algorithm traverses the route in a depth-firstmanner with taking polynomial time on each pseudo clique, thus it is polynomial
delay algorithm. We then introduce a method to decrease the time complexityand practical computation time. By computational experiments we show theefficiency of our algorithm in practice.
The organization of this paper is as follows. Section 2 is for preliminaries. In
Section 3, we present the hardness result for straightforward approach. Section
4 describes the adjacency and the algorithm. In Section 5, we present the resultsof our computational experiments, and conclude the paper in Section 6.

2

Preliminary

Let G = (V, E) be a graph with a vertex set V and an edge set E ⊆ V × V . In
this paper we consider graphs with no multiple edge. We say vertex v is adjacent
to vertex u if there is an edge e = {u, v} in E. We denote the degree of v bydeg(v), and the maximum degree by ∆.
For a vertex set U ⊆ V , the induced subgraph by U , denoted by G[U ] =(U, E[U ]), is a graph composed of edges of G whose endpoints are both in U .
G[U ] is also called an induced subgraph. In Fig. 1, the subgraph induced byvertex set {3, 5, 6, 9, 11} is the graph inside the gray circle without edges one ofits endpoint outside the circle. If U = ∅, we define G[U ] by the empty graph(∅, ∅). If any two vertices in U are connected by an edge, U and G[U ] are calleda clique. In Fig 1, vertices {5, 7, 9, 11} form a clique. For a vertex v and a vertex
set U , we denote the number of edges connecting v and a vertex in U by degU (v).
Let clq(n) = n(n−1), where clq(n) is the number of edges in the clique of2n vertices. For a vertex subset U ⊆ V at a size of at least 2, the density ofG[U ] is defined by |E[U ]|/clq(|U |). The density is the ratio of the edges in G[U ]compared to the complete graph of |U | vertices. In Fig 1, the density of thesubgraph induced by K = {3, 5, 6, 9, 11} is 7/10. We define the density of G[∅]and graphs with one vertex by 1. Suppose that θ, 0 ≤ θ ≤ 1 be a constant number
called threshold. Then, an induced subgraph G[U ] is called a pseudo clique if its
density is no less than θ. We note that G[∅] and G[{v}] for any vertex v arepseudo cliques for any threshold.
Let w be an edge weight function w : E → R. For an edge subset F ⊆ E,
we define the weight of F by the sum of weights of edges in F , and denote it byw(F ). We also define the weight of G[U ] by w(E[U ]). For a given edge weightfunction w : E → R, we define the weighted density of an induced subgraph
G[U ] by w(E[U ])/clq(|U |). We define the weighted density of the graphs with at
most one vertex by +∞. For a threshold θ ∈ R, an induced subgraph G[U ] is aweighted pseudo clique if its weighted density is no less than θ.
We define the (weighted) density of a vertex set by that of the subgraphinduced by the vertex set. We often say U is a (weighted) pseudo clique if G[U ] isa (weighted) pseudo clique. We here address the following enumeration problem.
(Weighted) Pseudo Clique Enumeration Problem:
For given graph G = (V, E) and threshold θ, (edge weight function w), output
all vertex sets whose induced subgraphs are (weighted) pseudo cliques of G

8

K

10

7

9
4

3

11

6
2

5

1

Fig. 1. An example of pseudo clique and other vertices

If an enumeration algorithm which outputs a set of solutions terminates intime polynomial of the sum of the input and output sizes, the algorithm is said
to be output polynomial time. The longest computation time between the output
of any two consecutive solutions is called the delay. An algorithm is polynomial
delay if the delay is polynomial in the input size. The computation time of apolynomial delay algorithm is linear in the output size, thus it is optimal for the
output size and considered to be practically efficient. Our goal in this paper is todevelop a polynomial delay algorithm for pseudo clique enumeration problem.

3

Hardness Result for Straightforward Approaches

A popular scheme for constructing an enumeration algorithm is so called binary
partition, which is a variant of branch and bound method. For the problem
of enumerating all the elements of an implicitly given subset family F ⊆ 2E ,binary partition algorithm works in the following way. If |F| is less than a certain
constant number, it enumerates elements in F directly. Otherwise, it chooses anelement e ∈ E and divide F into two sets F + and F − so that F + consistsof all the elements of F including e, and F − consists of those not including e.
Then, we check whether each of F + and F − is the emptyset or not, and if it
is not empty, we enumerate the elements recursively, by dividing F + or F − bychoosing another element e0 .
The algorithms so called “depth first search” or “back tracking” are also
considered to be a variant of binary partition algorithms. Binary partition works
for many problems, such as spanning trees, paths, and cycles[15], cliques andindependent sets[12], perfect matchings in bipartite graphs[5], etc.
The number of iterations of a binary partition algorithm is linear in |F|,which is the size of output, thanks to the check whether either F + or F − is anemptyset. Thus, if the check can be done in polynomial time of the input size,
the binary partition algorithm is polynomial delay. When we want to enumerate
the pseudo cliques by binary partition, the check problem is defined as follows.
Problem: Pseudo Clique Existence
For given a graph G, a vertex subset U , and a threshold θ, check whether apseudo clique K including U exists.
However, as we prove below, this problem is NP-complete. Thus, a straightforward binary partition algorithm will possibly take exponential time in an
iteration. Note that this result does not assure that binary partition algorithms

input graph
G=(V,E)

density =|V|2 -1|V|2

2|V|2
verticesas Uθ=|V|2 -1
ε|V|2 +εFig. 2. Construction of the graph for reduction

will never be output polynomial time even if P 6= N P . For example, a goodordering of vertices in V can exist so that the pseudo clique existence in any
iteration can be solved in polynomial time. Moreover, even if one iteration takes
exponential time in the input size, the total computation time can be polynomialin the output size since the output size can be also exponential in the input size.
In general, it is not easy to prove such statements, but also not impossible.
Theorem 1. The problem pseudo clique existence is NP-complete.
Proof. The problem obviously belongs to NP, thus we prove NP-hardness by
reducing the k clique problem which is to answer whether given graph G0 =(V 0 , E 0 ) includes a clique of given size k. This problem is NP-complete[7].
We will construct a graph G = (V, E) from G0 as follows. Fig. 2 shows anexample. Without loss of generality we assume that G0 has at least a certain
number of vertices, say 10 vertices. Let V = V 0 ∪ U where U is a vertex set ofsize 2|V 0 |2 . We choose two arbitrary vertices z1 and z2 from U . The edge set E
is defined by
E = E 0 ∪ {(u, v) | v ∈ V 0 , u ∈ U, u 6= z1 , z2 } ∪ EU
where EU is an arbitrary edge subset EU ⊆ U × U such that |EU | = (2|V 0 |2 −1) × (|V 0 |2 − 1). Then, the density of G[U ] is equal to (|V 0 |2 − 1)/|V 0 |2 .
Let K be a subset of V 0 . If and only if G[K] is a clique, the density ofG[K ∪ U ] is greater than (|V 0 |2 − 1)/|V 0 |2 , since the density of G[{v} ∪ U ] isequal to (|V 0 |2 − 1)/|V 0 |2 for any v ∈ V 0 . For any K ⊂ V such that G[K] is aclique, the density of G[K ∪ U ] is determined by the size of K. When K is theempty set or composed of one vertex, its density is (|V 0 |2 − 1)/|V 0 |2 , and strictlyincreases as the increase of the size of K. If the size of K is k, the density isclq(k) + (2|V 0 |2 − 1) × (|V 0 |2 − 1) + k(2|V 0 |2 − 2).
clq(k + |V 0 |2 )Thus, by setting θ to this value, which is the density of G[U ∪ K], K ⊆ V 0
is no less than θ if and only if K is a clique of at least size k in G0 . Thus, theproblem pseudo clique existence is NP-complete.
ut

4Polynomial Delay Enumeration of Pseudo Cliques

In the previous section we showed that a straightforward approach to the pseudoclique enumeration may fail in the sense of the polynomiality. However, the problem can actually be solved in polynomial delay. In this section we describe apolynomial delay algorithm for the non-weighted version of our problem. Necessary modifications for adopting the weighted version is obvious, thus we omitted
them. The key to an efficient enumeration is that we construct a tree shaped
traversal route on the set of pseudo cliques, and perform a depth first search on
the tree, without having the traversal route explicitly on the memory. Such atransversal route can be obtained by looking at an adjacency relation on pseudocliques spanning on all the pseudo cliques. This technique is called reverse search,which is originally developed by Avis and Fukuda[3].
The idea of reverse search is as follows. We first define a parent for eachelement to be enumerated, except for specified element called the root. The definition of the parent has to be acyclic, that is, each element is not a proper
ancestor of itself. Then, the parent-child relation induces a spanning tree rooted
at the root on the set of elements to be enumerated. We call the tree the enumeration tree. The algorithm traverses the tree in a depth first manner. Reverse
search does not need to memorize the previously visit elements in memory space
to avoid duplications. It uses an algorithm for listing the children of an element.
By finding a child of an element, we can go deeper on the enumeration tree bya recursive call. After we come back from the recursive call, we find the next
child and make a recursive call for it. In this way, we can perform the depth firstsearch with memory space linear in the height of the enumeration tree1 .
First we observe the following property to obtain an adjacency relation on
pseudo cliques.
Lemma 1. Let v be a vertex in G[K] with the degree no greater than the averageof the degrees of vertices in G[K]. The density of K \ {v} is no less than thedensity of K.
Proof. If |K| = 1, then K \ {v} = ∅, thus the statement holds. Hence, we assume
that |K| ≥ 2. Let F1 and F2 be a partition of the set of pairs of vertices in U
such that F1 is the set of pairs of v and another vertex, and F2 is the set ofthe remaining pairs. Let E1 = E[K] ∩ F1 , and E2 = E[K] ∩ F2 . Then, we canobserve that the density of U is between |E1 |/|F1 | and |E2 |/|F2 |. The density
multiplied by |U | − 1 is equal to the average degree of vertices in G[K], and thus
it is no less than |E1 |/|F1 |. Since E[K \ {v}] = E[K] ∩ F2 , the density of K \ {v}
It concludes the proof.
ut
From the lemma, we can see that for any pseudo clique K, K \ {v} is alsoa pseudo clique for any vertex whose degree is no greater than the average.
This introduces an adjacency relation on pseudo cliques. Since any K has such avertex v, we can remove the vertices of K iteratively until K will be the emptyset,
passing through only pseudo cliques. Thus, the adjacency spans all the pseudocliques. The graph induced by the adjacency is not a tree, thus we introduce
parent-child relation to obtain a tree-shaped traverse route.
For a vertex set K 6= ∅, we define v ∗ (K) by the minimum degree vertex
in G[K]. If there are more than one minimum degree vertices, we choose the1

The space complexity of the original reverse search does not depend on the heightof the enumeration tree.

minimum index one. We define the parent P rt(K) of K 6= ∅ by K \ {v ∗ (K)}.
From Lemma 1, P rt(K) is a pseudo clique if K is a pseudo clique. Since any
K has a unique parent, the graph induced by the parent-child relation forms
a tree. In Fig 1, the degrees of vertices in G[K] are degK (3) = degK (6) =2, degK (5) = degK (9) = 3, degK (11) = 4, thus v ∗ (K) is vertex 3. The parent of
K = {3, 5, 6, 9, 11} is {5, 6, 9, 11}. We will describe an algorithm for traversing
the tree.
Now the remaining task is how to find the children of a pseudo clique. For
this task, we first observe the following property, immediately obtained from thedefinition of the parent.
Property 1. For a pseudo clique K ⊆ V , K 0 is a child of K if and only if K 0 \K ={v} and v = v ∗ (K 0 ).
From the property, we can see that K has at most |V | − |K| children, eachof which is obtained by adding a vertex v not in K to K. Thus, we can list
the children of K by computing the density of K ∪ {v} and v ∗ (K ∪ {v}) for
each vertex v 6∈ K. In this way, we can list the children thus can enumerate
all pseudo cliques. We describe the algorithm as follows, which enumerates all
pseudo cliques by calling with G and K = ∅.
Algorithm EnumPseudoClique (G = (V, E), K)
1: output K
2: for each v 6∈ K do
3: if K ∪ {v} is a pseudo clique then4:
if K ∪ {v} is a child of K then EnumPseudoClique (G = (V, E), K ∪ {v})
In a straightforward implementation, an iteration of the algorithm takes
O(|V |2 ) time, thus pseudo cliques can be enumerated O(|V |2 ) time for each.
The computation time can be reduced by a sophisticated process. We characterize vertices generating children in terms of degK , and describe a more efficientalgorithm. The density of K ∪ {v} is (|E[K]| + degK (v))/clq(|K| + 1), thus there
is a threshold value θ(K) = θclq(|K| + 1) − |E[K]| such that for any vertex v
with degK (v) ≥ θ(K), K ∪ {v} is a pseudo clique.
Lemma 2. Let K ⊆ V be a pseudo clique and v be a vertex not in K. Then,K ∪ {v} is a pseudo clique if and only if degK (v) ≥ θ(K)We use buckets for 0, ..., |V | − 1 so that the bucket for i stores vertices v
satisfying degK (v) = i. Then, we can take the vertices generating pseudo cliquesin constant time for each. We update the buckets in each iteration and it takesO(deg(v)) time for the last added vertex v.
To check whether v ∗ (K ∪ {v}) = v or not, we introduce a total order ≺U for
any vertex subset U 6= ∅, defined byu ≺U v ⇔ degU (u) < degU (v) or(degU (u) = degU (v) and u ≤ v),

here u ≤ v means that the index of u is less than that of v. Then, v ∗ (K) isthe vertex of U satisfying v ∗ (K) ≺U u for any other vertex u ∈ U . Then, we
have the following lemma.

Lemma 3. For any pseudo clique K and a vertex v not in K, K ∪ {v} is a childof K if and only if (1) K∪{v} is a pseudo clique, (2) the tuple (degK (v ∗ (K)), v ∗ (K))
is lexicographically larger than the tuple (degK (v) − 1, v), and (3) v is adjacent
to any vertex u ∈ K, u ≺K v.
Proof. We first observe that for any vertex u, degK∪{v} (u) = degK (u) + 1 if v
is adjacent to u, and degK∪{v} (u) = degK (u), otherwise. Then, the only if partof the statement is obvious; if (2) is violated, then v ∗ (K) ≺K∪{v} v. Hence weprove the if part. It is sufficient to prove that conditions (2) and (3) lead thatv ∗ (K ∪ {i}) is v. v ∗ (K ∪ {i}) is v when any vertex u ∈ K satisfies u ≺K∪{i} v.
Suppose that conditions (2) and (3) hold for v. Then, from condition (3),any vertex u ∈ K satisfying u ≺K v is adjacent to v. Thus, the vertex u satisfies
degK∪{v} (u) = degK (u) + 1. From condition (2), the tuple (degK∪{v} (u), u)
is lexicographically larger than (degK∪{v} (v), v) = (degK∪{v} (v), v). Thus, thestatement holds.
ut
We show an example in Fig. 1. K ∪ {v} is a child of K for v = 1, 2, 4. Vertex
7 does not satisfy (3), and vertex 10 does not satisfy (2).
If a vertex v satisfies that K ∪ {v} is a pseudo clique and v ≺K v ∗ (K), thenK ∪ {v} is always a child of K. By keeping the above bucket sorted in the orderof indices, we can find all such vertices in O(log |V |) time for each. We note thatusing a sophisticated heap algorithm which realizes constant time insertion, we
can still bound the computation time for update the buckets by O(deg(v)). We
then explain the way to efficiently find vertices v satisfying that v ∗ (K) ≺K v
but K ∪ {v} is a child of K.
Let L(K) be the sequence of first ∆ vertices of K sorted by the order ≺K . If
K has less than ∆ vertices then L(K) includes all vertices in K. For each vertex
v 6∈ K, we define l(v, K) by the first vertex in L(K) which is not adjacent tov. We define l(v, K) by +∞ if v is adjacent to all vertices in L(K). In Fig. 1,
L(K) = (3, 6, 5, 9, 11), l(2, K) = 10, and l(7, K) = 3. The following is obvious.
Lemma 4. Let v be a vertex satisfying that v ∗ (K) ≺K v and K ∪{v} is a pseudoclique. Then, K ∪ {v} is a child of K if and only if v ≺K l(v, K). In particular,
v is adjacent to v ∗ (K).
We choose the vertices u in L(K) in the order of ≺K and look at the vertices
adjacent to u, then l(v, k) can be computed for all vertices v adjacent to at least
one vertex of L(K). This is done in O(min{∆2 , |V | + |E|}) time, hence all thevertices v generating children and v ∗ (K) ≺K v can be found in O(min{∆2 , |V | +|E|}) time.
To perform our reverse search, we have to keep L(K) and the buckets in thememory. This requires O(|V | + |E|) space. We need no extra memory for otheroperations, thus we have the following theorem.
Theorem 2. For a given graph G and threshold θ, all pseudo cliques can beenumerated in O(min{∆2 , |V | +|E|}) time for each within O(|V |+|E|) memory.
In particular, the delay is O(min{∆2 , |V | + |E|}).
We note that the delay can be bounded by the computation time for one
iteration by using so called “odd-even output method”, described in [13, 18].

We modify the algorithm so that in each iteration, the algorithm outputs thesolution before generating recursive calls if the depth of the recursion is odd,
and after the recursive calls otherwise. By this, during the execution, any threeconsecutive iterations output at least one solution, thus the delay is reduced tobe equal to the computation time for one iteration.
Considering the practice, the estimation of the computation time is too large,
since we are usually given a possibly large but sparse graphs thereby the pseudocliques are small in comparison to the graph sizes. Otherwise the number ofpseudo cliques explodes so that we can not handle the output. Thus, there will
be few candidates for children, and few vertices adjacent to v ∗ (K). Thus thecomplexity we state here is possibly far from the practical computation time.

5

Computational Experiments

We here present the results of computational experiments to show the practical efficiency of our algorithm. The implementation is coded by C, compiled
by gcc, and executed in a notebook PC with a Pentium M 1.1GHz processor
with 256MB memory with cygwin which is an emulator of Linux environments
on Windows. The implementation is a simpler version of our algorithm, which
maintains only degK (v) for each vertex v, thus the worst computation time for
an iteration is O(|E| + |V |). The reason that we did not use the technique tofind the children in O(log |V |) time for each is that in practice we expected that
only few vertices satisfy degK (v) = degK (v ∗ (K)) on average. This was observedin the computational experiments.
We examined several types of graphs as inputs of the implementation, randomly generated graphs and graph taken from real world data. We had threegroups of random graphs which are generated in the following three different
ways. The first group consists of ordinary random graphs. For each pair of vertices, we connected them by an edge with the same probability 0.1. The second
group is of so called locally dense graphs. Consider a necklace sequence obtainedby connecting the head and the tail of the vertex sequence (1, 2, . . . , |V |). For
each vertex v, we connected it to each its neighbor with probability 1/2. Here aneighbor of v is a vertex u with |u − v| ≤ r, or |u − v| ≥ |V | − r, for given r. In
the experiments we set r = 20.
The third was randomly generated scale free graphs. In a scale free graph,the probability that the degree of a vertex is λ is 1/λΓ . Such a distribution iscalled zip distribution, and such data is said to satisfy power law. The graphs
appearing in real world problems are often scale free graphs. Our scale freegraphs are generated by starting from a clique of k vertices and adding vertices
one-by-one to it, and then connect it to k vertices. The vertices to be connected
are chosen randomly such that a vertex is chosen with a probability proportional
to its degree. A graph generated in this way is known to be scale free. The graphtends to have few locally dense structures which we can see many in real world
data, thus the average size of cliques in this graph is often small.
We run the implementations for these graphs with the thresholds θ = 0.8
and θ = 0.9. Since we could not find any implementations for the pseudo cliquerandom graph p=0.1

locally dense random graph1000000000

10000000000

100000000

10
1
0.1
6400

4524

3200

2262

800

1600

565

1131

400

282

200

0.01

#vertices

10000
100
1
0.01
3E+05

100

64000

1000

16000

10000

4000

1000001000000

1000#cliquetime per 1M cliquetime clique#p-clique 0.9
time per 1M 0.9
time 0.9#p-clique 0.8
time per 1M 0.8
time 0.8

time (sec) & #cliques

1000000

time (sec) & #cliques#cliquetime per 1M cliquetime clique#p-clique 0.9
time per 1M 0.9
time 0.9#p-clique 0.8
time per 1M 0.8
time 0.8

100000000

10000000#verticesFig. 3. Results for random graphs (left) and locally dense random graphs (right)

10000
1000
100

1
0.1

80
00
16
00
0
32
00
0
64
00
0
12
80
00
25
60
00

40
00

20
00

0.01
10
00

time & #cliques

10#vertices

real-world data#p-cliquetime
time per 1M

11000001000000000
100000000
10000000
1000000
100000
10000
1000
100
10
1
0.1

0. 9 175
0. 9
0. 9 525
0
0. 8 . 975
0. 8
0. 8 525#cliquetime per 1M cliquetime clique#p-clique 0.9
time per 1M 0.9
time 0.9#p-clique 0.8
time per 1M 0.8
time 0.8

1000000

time & #p-cliques

scale free graph10000000thresholdFig. 4. Results for scale free graphs (left) and co-author graph (right)

enumeration problem, we compare the performance to that of an ordinary backtracking clique enumeration algorithm, which maintains degK (v) to find candidates for the addition. Since the clique enumeration is a special case of ourproblem, it can be considered as a kind of upper bound of the performance ofthe pseudo clique enumeration.
The results of the experiments are shown in figures. The left side of Fig. 3
shows the results for ordinary random graphs, and the right side of Fig. 3 is for
locally dense random graphs The left side of Fig. 4 is for scale free graphs. The
horizontal axis is the number of vertices in the input graphs, and the vertical axis
is for the computation time, computation time for 1 million (pseudo) cliques, andthe number of output (pseudo) cliques. All these are shown in log scales. The line
almost horizontal in the figures display the computation time per one million
pseudo cliques. The computation time for each pseudo clique does not changewith the change in the threshold value θ, and does not differ very much fromthat of the clique enumeration. This means that the performance of the pseudoclique enumeration is close to optimal, thus in the practice a high performanceis expected.
The computation time is increasing with the increase of the graph sizes inthe scale free graphs and slightly increasing in random graphs. This is possibly
because of the increase in the average degree, and the decrease in the ratioof children in the candidates of children. When we set threshold value θ toa small value, the number of vertices v satisfying degK (v ∗ (K)) ≤ degK (v) ≤degK (v ∗ (K)) + 1 increases. Since scale free graphs has a kind of locality, few ofthem will be the children of K, on average.
For all the results, the diagonal lines represents the numbers of pseudo cliquesand cliques. For the random graphs, the ratio of these three values increases with
the increase in graph size. This could be because of the increase in the average
degree. It is interesting to note that the ratio does not change much in locallydense random graphs, and is reduced for the scale graphs.
The right side of Fig. 4 is the result for the graph taken from the real world
data. The graph is a co-author graph[19] such that each vertex is a researcher
and two researchers are connected if they have a joint paper. The number ofvertices is about 30,000 and the number of edges is about 125,000. It is known
that the graph is a scale free graph. For this graph we observe the results bychanging the threshold θ. The leftmost point indicates the computation time of
the clique enumeration, thus it is faster than the others, but not different muchfrom that of the pseudo clique enumeration. The computation time does notseem to depend on the threshold value.

6

Conclusion

In this paper we addressed the problem of finding dense structures from a graph.
The density is given by the ratio of the existing edges compared to a completegraph, and we define a pseudo clique as a dense structure by a subgraph withdensity no less than the given threshold value. In this term we define our problem
of enumerating all pseudo cliques of given a graph and a threshold.
We first showed that it is not easy to get polynomial time algorithm bystraightforward approach since in this way we encounter an NP-complete problem. On the other hand, we show that any pseudo clique has a proper subset
being a pseudo clique with one fewer vertices. This induces a relation spanningall pseudo cliques. Using the relation we developed a reverse search algorithm
whose delay is O(min{∆2 , |E| + |V |}), thus computation time for each pseudoclique is O(min{∆2 , |E| + |V |}).
Recently, it has become popular to use dense structures to represent related
objects. One of the problems on practice is that the number of output solutions
is often larger than that of the cliques. The ”maximal” pseudo clique enumeration may help, but it is not straightforward to introduce maximality because thefamily of pseudo cliques does not satisfy the monotone property. Detailed characterizations of the dense structures which would allow us to develop efficientalgorithms are important for applications, and an interesting open problem.

Acknowledgment
This research was partly supported by the Ministry of Education, Science, Sports
and Culture, Grant-in-Aid for Specially Promoted Research, 18017015 for developing high-speed high-quality algorithms for analyzing huge genome database.

References
1. J. Aslam, K. Pelekhov and D. Rus, A Practical Clustering Algorithms for Staticand Dynamic Information Organization, SODA 99, ACM Press, 1999.

2. S. Arora, D. Karger and M. Karpinski, Polynomial time approximation schemes
for dense instances of NP-hard problems, Proc. ACM Symp. on Theory of Comp.,
pp. 284–293, 1995.
3. D. Avis and K. Fukuda, Reverse Search for Enumeration, Discrete Applied Mathematics 65, pp. 21–46, 1996.
4. U. Feige, D. Peleg and G. Kortsarz, The dense k-subgraph problem, Algorithmica
29, pp. 410-421, 2001.
5. K. Fukuda and T. Matsui, Finding All Minimum-Cost Perfect Matchings in Bipartite Graphs, Networks 22, pp. 461–468, 1992.
6. K. Fujisawa, Y. Hamuro, N. Katoh, T. Tokuyama and K. Yada, Approximationof Optimal Two-Dimensional Association Rules for Categorical Attributes Using
Semidefinite Programming, LNCS 1721, pp. 148–159, 1999.
7. M. R. Garey, D. S. Johnson and L. Stockmeyer, Some Simplified NP-complete
Problems, Proc. ACM Symp. on Theory of Comp., pp. 47–63, 1974.
8. D. Gibson, R. Kumar and A. Tomkins, Discovering Large Dense Subgraphs in
Massive Graphs, Proc. VLDB, pp. 721–732, 2005.
9. M. Haraguchi, Y. Okubo, A method for clustering of web pages with pseudo-cliquesearch, LNAI 3847, pp. 59–78, 2006.
10. H. Hu, X. Yan, Y. Huang, J. Han and X. J. Zhou, Mining Coherent Dense Subgraphs Across Massive Biological Networks for Functional Discovery, Bioinformatics 21, pp. 213–221, 2005.
11. R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins Extracting Large-Scale
Knowledge Bases from the Web, Proc. VLDB, pp. 639–650, 1999.
12. K. Makino and T. Uno, New Algorithms for Enumerating All Maximal Cliques,
LNCS 3111, pp. 260–272, 2004.
13. S. Nakano and T. Uno, Constant Time Generation of Trees with Specified Diameter, LNCS 3353, pp. 33–45, 2004.
14. G. Palla, I. Derenyi, I. Farkas and T. Vicsek, Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society, Nature, 435 7043,
pp. 814–818, 2005.
15. R. C. Read and R. E. Tarjan, Bounds on Backtrack Algorithms for Listing Cycles,
Paths, and Spanning Trees, Networks 5, pp. 237–252, 1975.
16. E. Tomita, A. Tanaka and H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer
Science 363, pp.28-42, 2006.
17. T. Uno, Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs, LNCS 1350, pp. 92–101, 1997.
18. T. Uno, Two General Methods to Reduce Delay and Change of Enumeration Algorithms, National Institute of Informatics (in Japan) Technical Report, 004E, 2003.
19. S. Warner, E-prints and the Open Archives Initiative, Library Hi Tech 21, pp.
151–158, 2003.
20. Y. Zhang, C. H. Chu, X. Ji and H. Zha, Correlating Summarization of Multisource
News with k Way Graph Biclustering, ACM SIGKDD Explo. Newslett. arch. 6,
pp. 34–42, 2004.