Database Reference
In-Depth Information
7.4 Tree Recurrence: Subgraph Probability Calculation
The dominant subgraph
G
of a vertex
v
may contain multiple connected com-
ponents. The vertices in different components are independent. Therefore, we first
focus on computing the subgraph probabilities of each components
G
i
(
(
v
)
. Then, the
overall subgraph probabilities can be computed from the convolution of the sub-
graph probabilities of all components.
The cliques in each component
G
i
v
)
(
)
v
form a tree (as discussed in Section 7.2.5).
We scan the cliques in
G
i
in the depth first order. During the scan, we compute
subgraph probability of the scanned subtree based on an important property below.
(
v
)
Corollary 7.2 (Conditional independency).
Given a PME-graph G and its clique
tree T , for any clique C in G
C
, C partition G
C
into multiple subtrees T
1
,···,
T
m
and
any two vertices in different subtrees are conditionally independent given C.
To compute the conditional subgraph probability
Pr
(
G
(
v
)
|
v
)
, there are two cases,
depending on whether
v
is in
G
i
(
v
)
or not. We first discuss the case where
v
is not in
G
i
(
will
be discussed at the end of Section 7.4.2, since it is a straightforward extension of
the first case.
v
)
, then
Pr
(
G
i
(
v
)
,
j
|
v
)=
Pr
(
G
i
(
v
)
,
j
)
. The second case where
v
is in
G
i
(
v
)
7.4.1 A Chain of Cliques
First, let us consider the simple case where all cliques
C
1
,···,
C
m
in
G
i
(
v
)
form a
chain.
Example 7.4 (A chain of cliques). Consider G
i
(
in Figure 7.5(b). Let the darkened
vertices be the vertices satisfying the query predicate and ranked higher than v. We
want to compute the subgraph probabilities for subgraphs C
1
,C
1
v
)
∪
∪
∪
C
2
, and C
1
C
2
C
3
. The subgraph probabilities for C
1
is simply Pr
(
C
1
,
0
)=
1
−
Pr
(
v
1
)
−
Pr
(
v
3
)=
0
.
2
and Pr
8
.
We consider computing the probability Pr
(
C
1
,
1
)=
0
.
. All vertices in C
1
and C
2
are conditionally independent given v
3
. We consider two cases as illustrated in Fig-
ures 7.5(c) and (d), respectively.
Case 1:v
3
does not appear. The probability for this case is Pr
(
C
1
∪
C
2
,
2
)
8
. Under
this condition, v
1
and v
4
are independent. The probabilities that v
1
are v
4
appear in
this case are Pr
(
¬
v
3
)=
0
.
0
.
6
0
0
.
4
0
(
v
1
|¬
v
3
)=
8
=
0
.
75
and Pr
(
v
4
|¬
v
3
)=
8
=
0
.
5
, respectively. The
.
.
probability that v
1
and v
4
both appear is Pr
(
v
1
,
v
4
|¬
v
3
)=
Pr
(
v
1
|¬
v
3
)
Pr
(
v
4
|¬
v
3
)=
0
.
375
. Therefore, Pr
(
C
1
∪
C
2
,
2
|¬
v
3
)
, the conditional probability that
2
vertices ap-
pear in C
1
∪
C
2
when v
3
does not appear, is
0
.
375
.
Case 2:v
3
appears, with probability Pr
(
v
3
)=
0
.
2
. Then, the probability that
Pr
(
C
1
∪
C
2
,
2
)
is
0
since no other vertices in C
1
and C
2
can appear.
