An Interaction Pattern Kernel Approach for Protein-Protein Interaction Extraction from Biomedical Literature - Technologies and Applications of Artificial Intelligence - page 40

defined as G =( V , E ) (| V |= p , | E |= k ), a random walk process consisting of a series of
random selections on the graph. Every edge ( SC n , SC m ) has its own weight M nm ,
which denotes the probability of a semantic class SC n , followed by another class SC m .
For each class, the sum of weight to all neighboring classes N ( SC n ) is defined as (2),
and the whole graph's probability matrix is defined as (3). As a result, a series of a
random walk process becomes a Markov Chain. According to [4], the cover time of a
random walk process on a normal graph is . We select frequent

semantic classes and their neighborhoods as start nodes of a random walk process.
We can conclude that using random walk to find frequent patterns on the interactive
graph would help us capture even the low probability combinations and shorten the
processing time.

2

∀ SC , C ≤ 4 k

n SC

n

support ( SC ∪ SC )

i j

confidence (SC ⇒ SC ) = P(SC |SC ) = ,

i j j i

support ( SC ) (1)

i

where support min =20, confidence min =0.5

∑

∀ SC M = 1

(2)

n nm

m ∈ N ( SC ) n

(3)

Pr = [ X = SC | X = SC , X = SC ,..., X = SC ] = Pr [ X = SC | X = SC ] = M

t + 1 m t n t − 1 k 0 i t + 1 m t n

Fig. 3. An interactive graph for pattern generation

Although the random walk process can help us generate frames from frequent
patterns in semantic graphs, it can also create some redundancy. Hence, a merging
procedure is required to eliminate the redundant results by retaining the patterns, with
long length and high coverage, and dispose of bigram patterns that are completely
covered by another pattern. For example, the pattern [ PROTEIN1 ]->[ Binding ] is
completely covered by the pattern [ PROTEIN1 ]->[ Binding ]->[ Regulation ]-
>[ Transcription ]->[ PROTEIN2 ]. Thus, the former pattern is incorporated. Otherwise,
if a bigram pattern partially overlaps with another, the overlapping part is
concatenated to form a longer pattern. For instance, the pattern [ Positive_regulation ]-
>[ Regulation ] partially overlaps with [ Regulation ]->[ Gene_expression ]-
>[ PROTEIN1 ], thus the two patterns are merged into another single pattern