Inference of node replacement graph grammars

Article type: Research Article

Authors: Kukluk, Jacek P. | Holder, Lawrence B.^{; *} | Cook, Diane J.

Affiliations: Department of Computer Science and Engineering, University of Texas at Arlington, Box 19015, Arlington, TX 76019, USA

Correspondence: [*] Corresponding author. Tel.: +1 509 335 6138; Fax: +1 509 335 3818; E-mail: [email protected].

Abstract: Graph grammars combine the relational aspect of graphs with the iterative and recursive aspects of string grammars, and thus represent an important next step in our ability to discover knowledge from data. In this paper we describe an approach to learning node replacement graph grammars. This approach is based on previous research in frequent isomorphic subgraphs discovery. We extend the search for frequent subgraphs by checking for overlap among the instances of the subgraphs in the input graph. If subgraphs overlap by one node we propose a node replacement grammar production. We also can infer a hierarchy of productions by compressing portions of a graph described by a production and then infer new productions on the compressed graph. We validate this approach in experiments where we generate graphs from known grammars and measure how well our system infers the original grammar from the generated graph. We also describe results on several real-world tasks from chemical mining to XML schema induction. We briefly discuss other grammar inference systems indicating that our study extends classes of learnable graph grammars.

Keywords: Grammar induction, graph grammars, graph mining

DOI: 10.3233/IDA-2007-11405

Journal: Intelligent Data Analysis, vol. 11, no. 4, pp. 377-400, 2007