2006
 315–331 54
©2006 1,2
5 2
Downward Closure Property 1. NP- Garey and Johnson, 1979
54 2006 2 1994 GBI  Yoshida et al., 1994 WARMR 1990 S UBDUE  Cook and Holder, 1999 Dehaspe and Toivonen, 1999 2000 Apriori AGM Inokuchi et al., 2000 DFS FSG  Kuramochi and Karypis, 2001 gSpan  Yan and Han, 2002 AcGM   Inokuchi et al., 2002 Gaston  Nijssen and Kok, 2004 MolFea   de Raedt and Kramer, 2001 CloseGraph  Yan and Han, 2003 FreeTreeMiner   Ruckert and Kramer, 2004 1 SiGraM Kuramochi and Karypis, 2004 SPIN  Huan et al., 2004 Taxonomy Generalized AcGM  Inokuchi, 2004 B-AGM  Inokuchi et al., 2005 Washio and Motoda, 2003 "Homepage for Mining Structured Data" Nijssen, 2005 2. 2.1 G(V, E, f, l) v Fi
f : E → V × V Lev Le L lv : V → Lv lc : E → Lc 2 316 1. ℓ(ℓv,ℓc) E = {e1,e2,e3,e4,e5,e6,e7,e5,e9} f(eh)=(vi,vj) f(e4)=(v1,v4)    f(e7)=(v4,v4) ℓν       ℓ c G(V, E, f, l) l a E 1
l v ( v i ) lc(eh)
1   Vs ⊂ V and  Es ⊂ E 2   ∀eh ∈ Es, ℓsc(eh) = ℓc(eh) and vi, vj ∈ Vs where fs(eh) = (vi, vj) 3   ∀ v i ∈ V s , ℓ s v ( v i ) = ℓ v ( v i ) G s (V s , E s , f s , l s ) 4. e4,e6,e7,e8,e9
4   ∀eh ∈ E   eh ∈ Es if vi,vj ∈ Vs where f(eh) = (vi,vj) 4 G s (V s , E s , f s , l s )
2.2 “ 1,...,n} Gsd
1 ∀G d (Va, E d, f d, l d) ∈ D, G s (V s, E s, f s, l s ) ⊂ G d (Va, E d, f d, l d), 2   ∀d = 1, . . . , n, ∀e sh ∈ E s , Hedh E Ed   fs(esh) = (vsi,vsj) and fa(edh) = (gsd(vsi),gsd(vsj)) G。 ⊆ G " 318 1 G g (V g , E g , f g , l g ) 1 b c
E s = {e s1,e s5} Vs = { Vs1, Vs2, Vs3} vdi = 9sd(vsi) (i = 1,2,3,d = (b),(c)) G 。 1 b G     D c Es = {es1,es2,es3,es5} D G s 1 1
Garey and NP- Johnson, 1979 2.3 R G ž ei V , a Inokuchi et al., 2000, 2003 i, j {lc(eh){Veh E E where f(eh) = (vi,vj)} Vi υ չ 0
C
code(G) = x 1,1x1,2x2,2x1,3x2,3x3,3 · · · x 1,n · · x n – 1,nxn,n 2.4 "Downward Closure
" Property  DCP " .. u

54
2006
2
319 2 a ∪ b = b ∪ a a ∪ (b ∪ c) = (a ∪ b) ∪ c L
L
L . L “ " " a " L P P
α ⊆ b⇒ P(b) → P(a). DCP t D sup(a) = |{ t | t ∈ D, a ⊂ t } | |D| a minsup (2.1) P(α) ≡ [sup(α) ≥ minsup] Agrwal and Srikant, 1994 3. D D DCP DCP DCP 3.1 Agrwal and Srikant, 1994 I = { item1 , item2 , . . . , itemm } I t ⊆ I D = { td | td ⊂ I , d = 1, . . . , n } 1 a b 320 54
2006
2
1) F 1 = { Frequent itemsets of cardinality=1} ; 2) for(k = 1; Fk yi 0; k + +) do begin 3) Ck+1 =apriori-gen(Fk); //New candidates 4) forall transactions t E D do begin 5) C'; =subset(Ck+, t); //Candidates contained in t 6) forall candidate c ∈ C ′ do 7) c.count++; 8) end 9) Fk+1 = { c E Ck+1 |c.count> minimum support } 10) end 11) Answer= U k Fk ; 2. Apriori 2.1 DCP α ⊆ I D Agrwal and Srikant, 1994
Apriori
Apriori 2 Ck join 1 k + 1 F k k: Apriori-gen
k: k: k — 1た2 (3.1) α k = {item1,item2,...,itemk_1,item1,} b k = {item1,item2,...,itemk_1,item'k} 2 k + 1 (3.2) Ck+1 = ak U bk = {item1,...,item1-1,item1,item1,} item 1 < item 2 < ··· < item k < item ' k Ck ÷ 1 DCP ακ bk k
321た3.2 3.1 prune DCP k: 2 subset k + 1 t 1
DCP kmax + 1 D kmax Apriori 3.2 D = {Gd(Vd,Ed,fd,ld)|d = 1,...,n} G d (V d , E d , f d , l d )
D G”
sup(Gs) ≥ minsup
DCP
(3.3) code(Ga k ) = x 1,1x1,2x2,2x1,3x2,3x3,3 · · · x 1,k · · x k − 1,kxk,k code(G b k ) = x 1,1x 1,2x 2,2x 1,3x 2,3x 3,3 · · · x ′ 1,k · · · x ′ k − 1,kx ′ k ,k (3.4) code(Gck+1) = code(Gak) U code(Gbk) = x1,1x1,2x2,2 · · · x1,k · · xk − 1,kxk,kx1,k · · xk − 1,kzk,k+1xk,k code(G α k ) ≤ code(G b k ) code(Ga k )
322 “0” Zk,k+1 “{ℓε(ei)| fck+1 (ej) = (vk,vk+1)}" (k − 1) × (k − 1) Gbk G b k Zk+1,k Zk,k÷1 Fi k + 1 G C K +1 3.3 k: 3.4 Apriori-gen prune k DCP i ( i = 1, ..., k = 1) i i k × k subset Gdん2 1 1 F k k k:た323 k + 1 1 DCP D kmax 4. 4.1 DNA gene 3 4.2 gene z gene 1 nonparametric additive regression model Hastie and Tibshirani, 1990; Imoto et al., 2002a 324 54
3.
Eilers and Marx, 1996 Bayesian network and nonparametric regression model
n
Θς
π(G)
Θς
Regression  Criterion et al., 2002b BNRC  Bayesian network and Nonparametric Imoto MAP Greedy π(G) Imoto et al., 2004 T gener gene j ΔBNRC is 4.3 △BNRCザ△BNRC s △BNRC* 5 {G1,...,Gr} Gr Gh gener G h gene; → gene; Δ B N R C min
Gh(C Gh) minsup
YBR088C(POL30)
4. 325 92.3 
 
 326 54
2
2006
{x1,...,xn} 5000 801 ΔBNRC ti 2600 {G1,...,G500} 20 Δ B N R C min {G1,...,G5000} 115 minsup = 0.9 184 4 17 92.3 4.4 1 2
5000
△BNRC is
20 Δ B N R C min G h Gene Ontology Consortium, 2000, 2005 Process, Function, ComponentしGO Term Gene Ontology  GO  Term GO 1 33 Process GO Term Process GO Term G h 3.2 AcGM Inokuchi et al., 2002 AcGM 2/3し801 6. 1/3
327
5 2006 2 54 6 1/3 10 organization and biogenesis DNA metabolism DNA metabolism organelle cell cycle protein modification 5. Agrwal, R. and Srikant, R.  1994 .  First algorithms for mining association rules, Proceedings of the 20th VLDB Conference, 487–499. Cook, J. and Holder, L.  1994 .  Substructure discovery using minimum description length and back- ground knowledge, Journal of Artificial Intelligence Research, 1, 231–255. de Raedt, L. and Kramer, S.  2001 .  The levelwise version space algorithm and its application to molecular fragment finding, Proceedings of IJCAI01 : Seventeenth International Joint Confer- ence on Artificial Intelligence, 2, 853–859. Dehaspe, L. and Toivonen, H.  1999 .  Discovery of frequent datalog patterns, Data Mining and Knowledge Discovery, 3 1 , 7–36. Eilers, P. H. C. and Marx, B.   1996  . Flexible smoothing with B-splines and penalties   with discussion  , Statistical Science, 11, 89–121. Garey, M. and Johnson, D.  1979 .  Computers and Intractability: A Guide to the Theory of NP- Completeness , W. H. Freeman and Company, New York. Gene Ontology Consortium  2000 .  Gene Ontology: Tool for the unification of biology, Nature Ge- netics, 25, 25–29. Gene Ontology Consortium 2005 . Saccharomyces Genome Database, http://www.yeastgenome. 328 7 org/GOContents.shtml. Hastie, T. and Tibshirani, R.  1990 .  Generalized Additive Models , Chapman & Hall, Florida. Huan, L., Wang, W. and Prins, J.  2004 .  SPIN: Mining maximal frequent subgraphs from graph databases, Proceedings of the 2004 Conference on Knowledge Discovery and Data Mining SIGKDD2004 , 581–586. Imoto, S., Goto, T. and Miyano, S.   2002a . Estimation of genetic networks and functional structures between genes by using Bayesian network and nonparametric regression, Proceedings of Pacific Symposium on Biocomputing, 7, 175–186. Imoto, S., Kim, S., Goto, T., Aburatani, S., Tashiro, K., Kuhara, S. and Miyano, S.  2002b  .   Bayesian network and nonparametric heteroscedastic regression for nonlinear modeling of genetic net- work, Proceedings of 1st IEEE Computer Society Bioinformatics Conference, 219–227. Imoto, S., Higuchi, T., Goto, T., Tashiro, K., Kuhara, S. and Miyano, S. 2004 . Combining microar- rays and biological knowledge for estimating gene networks via bayesian networks, Journal of Bioinformatics and Computational Biology, 2 1 , 77–98. Inokuchi, A.  2004 .  Mining generalized substructures from a set of labeled graphs, Proceedings of Fourth IEEE International Conference on Data Mining  ICDM2004 , 415–418. Inokuchi, A., Washio, T. and Motoda, H.  2000 .  An apriori-based algorithm for mining frequent substructures from graph data, Proceedings of PKDD2000: Principles of Data Mining and Knowledge Discovery, 4th Europian Conference, Lecture notes in Artificial Intelligence 1910 ed. Jan Zytkow , 13–23, Springer, London. Inokuchi, A., Washio, T., Nishimura, K. and Motoda, H.  2002 .  A fast algorithm for mining fre- quent connected subgraphs, IBM Technical Research Report: RT0448, IBM Tokyo Research Laboratory. Inokuchi, A., Washio, T. and Motoda, H.  2003 .  Complete mining of frequent patterns from graphs: Mining graph data, Machine Learning, 50, 321–354. Inokuchi, A., Washio, T. and Motoda, H.  2005 . A general framework for mining frequent subgraphs from labeled graphs, Journal of Fundamenta Informatiae, Special Issue on Advances in Mining Graphs, Trees and Sequence, 66 1–2 , 53–82. Kuramochi, M. and Karypis, G.  2001 .  Frequent subgraph discovery, Proceedings of ICDM'01 : 1st IEEE International Conference on Data Mining , 313–320. Kuramochi, M. and Karypis, G.  2004 .  Finding frequent patterns in a large sparse graph, Pro- ceedings of the 2004 SIAM Data Mining Conference , http://www.siam.org/meetings/sdm04/ proceedings/index.htm. Nijssen, S.  2005 .  Homepage for Mining Structured Data, http://hms.liacs.nl/index.html. Nijssen, S. and Kok, J. N.  2004 .  A quickstart in frequent structure mining can make a difference, Proceedings of the 2004 International Conference Knowledge Discovery and Data Mining SIGKDD'04 , 647–652. Ruckert, U. and Kramer, S.  2004 .   Frequent free tree discovery in graph data, Proceedings of ACM Symposium on Applied Computing  SAC2004 , Special Track on Data Mining , 564–570. Washio, T. and Motoda, M.  2003 .  State of the art of graph-based data mining, ACM, SIGKDD Explorations, 5 1 , 59–68. Yan, X. and Han, J.  2002 .  gSpan: Graph-based substructure pattern mining, Proceedings of ICDM'02: 2nd IEEE International Conference on Data Mining, 721–724. Yan, X. and Han, J.  2003 .  CloseGraph: Mining closed frequent graph patterns, Proceedings of the 2003 Conference on Knowledge Discovery and Data Mining  SIGKDD2003 , 286–295. Yoshida, H., Motoda, K. and Indurkhya, N.  1994 .  Graph-based induction as a unified learning framework, Journal of Applied Intelligence, 4, 297–328.
329
Proceedings of the Institute of Statistical Mathematics Vol. 54, No. 2, 315–331
(2006)
330
Graph Mining and Its Application to Statistical Modeling Takashi Washio 1.2 , Tomoyuki Higuchi 1 , Seiya Imoto 3 , Yoshinori Tamada 1 , Ken Sato 4 and Hiroshi Motoda 2 1The Institute of Statistical Mathematics 2The Institute of Scientific and Industrial Research, Osaka Univrsity 3 Human Genome Center, Institute of Medical Science, University of Tokyo 4 National Institute of Informatics This report introduces graph mining techniques actively explored in a recent datamin- ing study, and demonstrates its application to gene network analysis in conjunction with statistical modeling. The study on graph mining was initiated in the mid 1990's, and became widely explored after 2000 upon the proposal of its complete search algorithm. Graph mining is used to find characteristic substructures shared by some graphs in a given massive graph data. In particular, the exhaustive search of frequent subgraphs widely seen in the data is a representative task of graph mining. As this task contains subgraph isomorphism problems, which are known to be NP-complete, its high computa- tional complexity is essential. Accordingly, the development of a practical fast algorithm for graph mining is a key issue in the study. A property for characterizing the substructures is used to mine characteristic sub- structures in massive graph data. A naive way to search the characteristic substructures is to check the property on every substructure in the data. However, this approach faces the combinatorial explosion of the substructures in the check. For efficient mining, most graph mining approaches limit the property to a "Downward Closure Property (DCP)." A DCP P is defined as a ⊆ b ⇒ P(b) → P(a) by using two structures a and b where P( · ) means that the property P holds on a structure. Representative DCPs are a fre- quent itemset and a frequent graph where any of their subitemsets and subgraphs are also frequent. By this definition, if P does not hold on a substructure a , P does not hold on any superstructure of a either. Accordingly, under a set of all substructures of size k and DCP P , candidate substructures of larger size k + 1 and DCP P are limited to the join of the substructures in the set. This strongly limits the search space of characteristic substructures, and enables practical and fast graph mining. The graph mining technique was introduced to the post processing of the statistical gene network models obtained from microarray gene expression data. Bayesian network and nonparametric regression models of the gene network were in greedy manner searched in the data. We are interested that subnetworks widely appear over searched networks, since the credibility of such subnetworks are considered to be very high. Basket Analysis and a connected induced subgraph mining AcGM are applied to mine frequent subnet- works over searched networks where each network contains 801 genes. In the results of both Basket Analysis and AcGM, the frequent subnetworks are limited to very small sizes compared with the total size of the gene networks. This indicates that wide varieties of interpretations on a gene network structure are obtained from microarray gene expression data. In this study, graph mining was applied to the post processing stage of statistical Proceedings of the Institute of Statistical Mathematics Vol. 54, No. 2 (2006) modeling to extract credible gene subnetworks. Other possibilities such as direct intro- duction of graph mining to the search process of statistical model structures should be explored in future work. 331