Designing and Learning Substitutable Plane Graph Grammars

• Autorzy: Eyraud R. , Oates T. , Janodet J.-C. , Papadopoulos F.

Identyfikatory

DOI

10.3233/FI-2016-1393

• Języki publikacji: EN

Abstrakty

EN

Though graph grammars have been widely investigated for 40 years, few learning results exist for them. The main reasons come from complexity issues that are inherent when graphs, and a fortiori graph grammars, are considered. The picture is however different if one considers drawings of graphs, rather than the graphs themselves. For instance, it has recently been proved that the isomorphism and pattern searching problems could be solved in polynomial time for plane graphs, that is, planar embeddings of planar graphs. In this paper, we introduce the Plane Graph Grammars (PGG) and detail how they differ to usual graph grammar formalism’s while at the same time they share important properties with string context-free grammars. In particular, though exponential in the general case, we provide an appropriate restriction on languages that allows the parsing of a graph with a given PGG in polynomial time. We demonstrate that PGG are well-shaped for learning: we show how recent results on string grammars can be extended to PGG by providing a learning algorithm that identifies in the limit the class of substitutable plane graph languages. Our algorithm runs in polynomial time assuming the same restriction used for polynomial parsing, and the amount of data needed for convergence is comparable to the one required in the case of strings.

Słowa kluczowe

EN

plane graph; graph grammars; distributional learning; grammatical inference

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 146, nr 4
• Strony: 403--430
• Opis fizyczny: Bibliogr. 39 poz., rys.

Twórcy

autor

Eyraud R.

• Qarma Team, LIF Marseille, France

autor

Oates T.

• CoRaL lab, CSEE department, University of Maryland, Baltimore County, USA

autor

Janodet J.-C.

• IBISC lab, University of Evry, 23 Bd de France, F-91037 Evry, France

autor

Papadopoulos F.

• IBISC lab, University of Evry, 23 Bd de France, F-91037 Evry, France

Bibliografia

• [1] Bailly R, Denis F, Rabusseau G. Recognizable Series on Hypergraphs, Proc. 9th Intern. Conf. on Language and Automata Theory and Applications (LATA’15), LNCS 8977, 2015, pp. 639-651. doi:10.1007/978-3-319-15579-1_50.
• [2] Bohl E, Terraz O, Ghazanfarpour D. Modeling fruits and their internal structure using parametric 3Gmap L-systems, The Visual Computer, 2015;31(6-8):819-829. doi:10.1007/s00371-015-1108-9.
• [3] Brijder R, Blockeel H. On the inference of non-confluent NLC graph grammars, Journal of Logic and Computation, 2011;23(4):799-814. doi: 10.1093/logcom/exr046.
• [4] Clark A. Towards General Algorithms for Grammatical Inference, in: 21st International Conference, ALT 2010, Canberra, Australia, October 6-8, 2010. Proceedings, LNCS 6331, 2010, pp. 11-30. Invited Paper. doi:10.1007/978-3-642-16108-7_2.
• [5] Clark A, Eyraud R. Polynomial Identification in the Limit of Substitutable Context-free Languages, Journal of Machine Learning Research, 2007(8):1725-1745. Available from: http://www.jmlr.org/papers/v8/clark07a.html.
• [6] Cook DJ, Holder LB. Graph-Based Data Mining, IEEE Intelligent Systems, 2000;15(2):32-41. doi:10.1109/5254.850825.
• [7] Costa Florêncio C. Identification of Hyperedge-Replacement Graph Grammars, in: Proc. 7th Intern. Workshop on Mining and Learning with Graphs (MLG’09), Leuven, Belgium, 2009, 19-21.
• [8] Courcelle B. An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoretical Computer Science, 1987;55(2-3):141-181. doi:10.1016/0304-3975(87)90102-2.
• [9] Damiand G, Lienhardt P. Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing, A K Peters/CRC Press, 2014. ISBN-1482206528, 9781482206524.
• [10] Drewes F, Kreowski HJ, Habel A. Hyperedge Replacement Graph Grammars, in: Handbook of Graph Grammars, World Scientific Publishing Co., Inc., [33], 1997, pp. 95-162. ISBN: 9810228848.
• [11] Dupont P, Miclet L, Vidal E. What Is the Search Space of the Regular Inference?, in: Proc. 2nd Inter. Colloquium in Grammatical Inference (ICGI’94), LNCS 862, 1994, 25-37. doi: 10.1007/3-540-58473-0_134.
• [12] Engelfriet J. Tree automata and tree grammars, 1975, DAIMI FN-10 (Lecture Notes), Aarhus University.
• [13] Eyraud R, Heinz J, Yoshinaka R. Efficiency in the Identification in the Limit Learning Paradigm, in: Topics in Grammatical Inference (J. Heinz, J. M. Sempere, Eds.), Springer-Verlag, 2016, pp. 25-46. doi:10.1007/978-3-662-48395-4_2.
• [14] Eyraud R, Janodet JC, Oates T. Learning Substitutable Binary Plane Graph Grammars, in: Proc. 11th Intern. Colloquium in Grammatical Inference (ICGI’12) vol. 21 of JMLR Worshops and Conference Proceedings, 2012, pp. 114-128. Available from: http://dblp.uni-trier.de/db/journals/jmlr/jmlrp21.html#EyraudJO12.
• [15] Fáry I. On straight line representation of planar graphs, Acta Univ Szeged. Sect. Sci. Math, 1948;11:229-233.
• [16] Fusy E. Combinatoire des graphes planaires et applications algorithmiques (in English), Ph.D. Thesis, Ecole Polytechnique - ParisTech, 2007.
• [17] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. ISBN: 0716710447.
• [18] Gibbons A. Algorithmic graph theory, Cambridge University Press, 1985. ISBN: 9780521288811.
• [19] Gold E. Language Identification in the Limit, Information and Control, 1967;10(5):447-474. doi:10.1016/S0019-9958(67)91165-5.
• [20] Harchaoui Z, Bach FR. Image Classification with Segmentation Graph Kernels, in: Proc. 13th Conference on Computer Vision and Pattern Recognition (CVPR’07), IEEE Computer Society, 2007. doi:10.1109/CVPR.2007.383049.
• [21] de la Higuera C. Characteristic Sets for Polynomial Grammatical Inference, Machine Learning Journal, 1997;27(2):125-138. doi: 10.1023/A:1007353007695.
• [22] de la Higuera C, Janodet JC, Samuel E, Damiand G, Solnon C. Polynomial Algorithms for Open Plane Graph and Subgraph Isomorphisms, Theoretical Computer Science, 2013;498:76-99. Available from: http://dx.doi.org/10.1016/j.tcs.2013.05.026.
• [23] Huan J, Wang W, Prins J. Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, in: Proc. 3rd Intern. Conf. on Data Mining (ICDM’03), IEEE Computer Society, 2003, pp. 549-552. ISBN:0-7695-1978-4.
• [24] Jeltsch E, Kreowski HK. Grammatical Inference Based on Hyperedge Replacement, in: Proc. 4th International Workshop on Graph Grammars and their Application to Computer Science, LNCS 532, 1991, pp. 461-474. doi: 10.1007/BFb0017406.
• [25] Jonyer I, Holder LB, Cook DJ. MDL-Based Context-Free Graph Grammar Induction, International Journal of Artificial Intelligence Tools, 2004;13:65-79. Available from: http://dx.doi.org/10.1142/S0218213004001429.
• [26] Kadri H, Ghavamzadeh M, Preux P. A Generalized Kernel Approach to Structured Output Learning, in: Proc. 30th Intern. Conf. in Machine Learning (ICML’13) vol. 28 of JMLR Workshops and Conference Proceedings, 2013, pp. 471-479. Available from: https://hal.inria.fr/hal-00695631.
• [27] Kasprzik A, Yoshinaka R. Distributional Learning of Simple Context-Free Tree Grammars, in: Proc. 22nd Intern. Conf. on Algorithmic Learning Theory (ALT’11), LNAI 6925, 2011, pp. 398-412. doi: 10.1007/978-3-642-24412-4_31.
• [28] Kukluk J, Holder L, Cook D. Inference of Edge Replacement Graph Grammars, International Journal on Artificial Intelligence Tools, 2008;17(3):539-554. Available from: http://dx.doi.org/10.1142/S0218213008004047.
• [29] Lautemann C. The Complexity of Graph Languages Generated by Hyperedge Replacement, Acta Informatica, 1989;27(5):399-421. doi: 10.1007/BF00289017.
• [30] Lienhardt P. N-Dimensional Generalized Combinatorial Maps and Cellular Quasi-Manifolds, International Journal of Computational Geometry and Applications, 1994;4(3):275-324. Available from: http://dx. doi.org/10.1142/S0218195994000173.
• [31] Matsuda T, Motoda H, Washio T. Graph-based induction and its applications, Advanced Engineering Informatics, 2002;16(2):135-143. doi: 10.1016/S1474-0346(02)00005-8.
• [32] Nagl M. Formal languages of labelled graphs, Computing, 1976;16(1-2):113-137. doi: 10.1007/BF02241984.
• [33] Rozenberg G, Ehrig H. Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1-3, World Scientific, 1997. ISBN: 98-102288-48.
• [34] Samuel E, de la Higuera C, Janodet JC. Extracting Plane Graphs from Images, in: Proc. of 13th Intern. Workshop on Structural and Syntactic Pattern Recognition (SSPR’10), LNCS 6218, 2010, pp. 233-243. doi: 10.1007/978-3-642-14980-1_22.
• [35] Shibata C, Yoshinaka R. PAC Learning of Some Subclasses of Context-Free Grammars with Basic Distributional Properties, in: Proc. 24th Intern. Conf. in Algorithmic Learning Theory (ALT’13), LNCS 8139, 2013, pp. 143-157. doi: 10.1007/978-3-642-40935-6_11.
• [36] Vishwanathan S, Schraudolph N, Kondor RI, Borgwardt K. Graph Kernels, Journal of Machine Learning Research, 2010;11:1201-1242. Available from: http://dl.acm.org/citation.cfm?id=1756006.1859891.
• [37] Whitney H. Non-separable and planar graphs, Proc. of the National Academy of Science, U.S.A., 1931;17(2):125-127. doi: 10.1090/S0002-9947-1932-1501641-2.
• [38] Yoshinaka R. Identification in the Limit of (k,l)-Substitutable Context-Free Languages, in: Proc. 9th Intern. Colloquium in Grammatical Inference (ICGI’08), LNAI 5278, 2008, pp. 266-279. doi: 10.1007/978-3-540-88009-7_21.
• [39] Yoshinaka R. Efficient learning of multiple context-free languages with multidimensional substitutability from positive data., Theoretical Computer Science, 2011;412(19):1821-1831. doi:10.1016/j.tcs.2010.12.058.