Database Reference
In-Depth Information
Fo r
1
<
i
<
m, the conditional subgraph probability of G
i
given
¬
v
i
is
v
i
p
|¬
Pr
(
G
i
,
x
|¬
v
i
)=
Pr
(
¬
v
i
−
1
|¬
v
i
)
·
Pr
(
G
i
−
1
,
x
|¬
v
i
−
1
)
·
Pr
(
¬
v
i
−
1
¬
v
i
)
v
i
p
.
v
i
p
|¬
+
Pr
(
¬
v
i
−
1
|¬
v
i
)
·
Pr
(
G
i
−
1
,
x
−
F
|¬
v
i
−
1
)
·
Pr
(
v
i
−
1
¬
v
i
)
+
Pr
(
v
i
−
1
|¬
v
i
)
·
Pr
(
G
i
−
1
,
x
|
v
i
−
1
)
The conditional subgraph probability of G
i
given v
i
is
Pr
(
G
i
,
x
|
v
i
)=
Pr
(
G
i
−
1
,
x
−
v
i
.
F
|¬
v
i
−
1
)
To compute subgrph probabilities, we scan cliques
C
1
,···,
C
m
and calculate
Pr
(
G
i
,
x
|
v
i
)
and
Pr
(
G
i
,
x
|¬
v
i
)
for 0
≤
x
≤
i
. Then, we compute
Pr
(
G
m
,
x
)
for
G
m
=
1
≤
j
≤
m
C
j
using
Pr
(
G
m
,
x
)=
Pr
(
v
m
−
1
)
Pr
(
G
m
−
1
,
x
|
v
m
−
1
)
v
p
|¬
+
Pr
(
¬
v
m
−
1
)
Pr
(
G
m
−
1
,
x
|¬
v
m
−
1
)
Pr
(
¬
v
m
−
1
)
(7.7)
v
p
.
v
p
|¬
+
Pr
(
¬
v
m
−
1
)
Pr
(
G
m
−
1
,
x
−
F
|¬
v
m
−
1
)
Pr
(
v
m
−
1
)
m
2
The overall complexity is
O
(
)
.
7.4.2 A Tree of Cliques
(
)
Now let us consider the general case where the clique graph of
G
i
v
is a tree.
Example 7.5 (Connecting multiple cliques). Figure 7.6(b) shows three cliques C
1
,
C
2
and C
3
connected by clique C. C
1
,C
2
and C
3
are the end vertices of three clique
chains. Let v
1
,v
2
and v
3
be the three common vertices between C and C
1
,C
2
and C
3
,
respectively. Then, there are five possible value assignments of C: v
p
=
1
,v
1
=
1
,
v
2
=
1
). In any of the five
cases, the joint probability distribution of C
1
,C
2
and C
3
are conditionally indepen-
dent. The subgraph probability of the three cliques is simply the product of their
conditional subgraph probabilities.
1
,v
2
=
1
or no vertices taking value
1
(if
∑
v
∈
V
C
Pr
(
v
)
<
We scan the cliques in a clique tree in the depth first order. When we reach a leaf
clique
C
l
, its subgraph probability is calculated and sent to its parent clique
C
p
.If
C
p
only contains one child, then the subgraph probability of the subtree containing
C
l
and
C
p
is computed at
C
p
, using Theorem 7.4. If
C
p
contains more than one child,
then the subgraph probability of all cliques in the subtree with root
C
p
is computed at
C
p
as described in Example 7.5. The complete procedure is shown in Algorithm 7.1.
Generally, if there are
d
chains of cliques connecting to a clique
C
, calculating the
subgraph probability for each chain takes
O
n
i
)
where
n
i
is the number of cliques
contained in the
i
-th chain. Calculating the subgraph probability for all cliques takes
O
(
dn
2
(
)
, where
n
=
∑
1
≤
i
≤
d
n
i
is the number of cliques in all
d
chains.